3

I discovered recently that the hazard pointer technique has a patent application if not an actual patent assigned to it. Can I get clarification on this?

Also, would like some indication on whether the following idea would even remotely violate any possible patent on the hazard pointer technique:

Given:

  1. Some structure containing pointers to objects which can be iterated. Take some tree or map as an example.

  2. Some set of threads which iterate the tree using a reader writer lock.

  3. The readers need to keep the read lock held for a long time thus writers get starved in this system.

Solution: Readers and writers obtain a handle to resource before starting to access the resource and drop the handle after accessing the resource. The handle is obtained from an array of counters. These counters serve as the "hazard pointer". Each active array entry is an indication of a thread with interest in a set of objects potentially marked for deletion. This is described below:

When a writer updates an entry it doesn't update in place. Instead, the original entry is marked as deleted and stamped with the the current handle counter value of the handle system and placed on a delete queue. The writer then stores a new value into the structure and the handle counter is incremented.

When readers obtain a handle, the current handle counter is stored in a slot in the handle array assigned to the reader.

So how is the data the reader has a pointer to protected? Via the counter handle. The processor of the deletion queue ensures that no value in the handle counter array is less or equal to the counter value stamped on the item to be deleted before actually deleting it.

The handle counter is a 64 bit integer which won't overflow easily. I have a procedure for re-setting the counter in the event of imminent overflow but I won't describe it here in the interest of space. ( Ala Fermat's last theorem. )

  • kernel.org/doc/Documentation/RCU/RTFP.txt seems to describe ideas similar to what I describe. I just cannot make heads or tails of whether deferred deletion idea I describe is in anyway covered by existing patents on hazard pointers or any of the RCU type techniques described in the paper. Thanks. – Kuberan Naganathan Sep 13 '14 at 13:45
3

The application that you cited is owned by IBM but was been abandoned after the USPTO Examiner identified prior art that would have blocked the patenting.

To find this information, I looked up the application docket (File history) using the USPTO's system known as PAIR: http://portal.uspto.gov/external/portal/pair.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.