lkml.org 
[lkml]   [2001]   [Oct]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

In article <Pine.LNX.4.33.0110092236210.1305-100000@penguin.transmeta.com> Linus Torvalds wrote:

> Now, in all fairness I can imagine hacky lock-less removals too. To get
> them to work, you have to (a) change the "next" pointer to point to the
> next->next (and have some serialization between removals, but removals
> only, to make sure you don't have next->next also going away from you) and
> (b) leave the old "next" pointer (and thus the data structure) around
> until you can _prove_ that nobody is looking anything up any more, and
> that the now-defunct data structure can truly be removed.

This is exactly what Read-Copy Update does. You keep the old data
structure around until you are sure that all the CPUs have lost
references to it by context switching. There are more than
one relatively non-intrusive ways of detecting completion of such a cycle
and "deleted" data can be freed afterwards.

The details are in http://lse.sourceforge.net/locking/rcupdate.html.

Thanks
Dipankar
--
Dipankar Sarma <dipankar@in.ibm.com> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.
-
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/

\
 
 \ /
  Last update: 2005-03-22 13:05    [W:0.040 / U:2.328 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site