Messages in this thread |  | | From | Paul Mackerras <> | Date | Wed, 10 Oct 2001 16:16:21 +1000 (EST) | Subject | Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion |
| |
Linus Torvalds writes:
> And THAT is the hard part. Doing lookup without locks ends up being > pretty much worthless, because you need the locks for the removal > anyway, at which point the whole thing looks pretty moot. > > Did I miss something?
I believe this all becomes (much more) useful when you are doing read-copy-update.
There is an assumption that anyone modifying the list (inserting or deleting) would take a lock first, so the deletion is just a pointer assignment. Any reader traversing the list (without a lock) sees either the old pointer or the new, which is fine.
The difficulty is in making sure that no reader is still inspecting the list element you just removed before you free it, or modify any field that the reader would be looking at (particularly the `next' field :). One way of doing that is to defer the free or modification to a quiescent point. If you have a separate `next_free' field, you could safely put the element on a list of elements to be freed at the next quiescent point.
Paul. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
|  |