Messages in this thread |  | | Subject | Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion | From | "Paul McKenney" <> | Date | Sat, 13 Oct 2001 07:42:49 -0700 |
| |
> > > > And the read side is: > > lock > > loopup > > atomic_inc > > unlock > > > > With RCU, read side is: > > loopup > > atomic_inc > > Yes. With maybe > > non_preempt() > .. > preempt() > > around it for the pre-emption patches. > > However, you also need to make your free _free_ be aware of the count. > Which means that the current RCU patch is really unusable for this. You > need to have the "count" always in a generic place (put it with the hash),
???
Ah! Are you thinking of the trick that associates a reference counter with each pointer, and where one uses a double-compare-and-swap instruction to do updates? That is definitely -not- what we are proposing here, since it is important to avoid writes during read-only traversals.
Instead, we use side information to deduce when it is no longer possible for there to be any references to a given data structure.
It -is- possible to use RCU in Linux -without- reference counts. See the Maneesh Soni's FD-management patch and description at:
http://lse.sourceforge.net/locking/patches/files_struct_rcu-2.4.10-04.patch http://lse.sourceforge.net/locking/files_struct_rcu.txt
The reference counts are needed -only- in cases where references to an RCU-protected data structure may be held across a sleep. Dipankar Sarma's IPV4 route-cache lookup patch at:
http://lse.sourceforge.net/locking/patches/rt_rcu-2.4.6-02.patch
is an example use of RCU where reference counts are used, since entries can be queued.
Thanx, 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/
|  |