Re: [Fwd: [PATCH 2/7] lock_list: a fine grain locked double linked list]

On Sun, 2007-01-28 at 17:20 +0000, Christoph Hellwig wrote:
Provide a simple fine grain locked double link list.

It is build upon the regular double linked list primitives, spinlocks and RCU.

Locking is peculiar in that edges are locked, this avoid the circular lock
dependancy created by the fact that the regular linked lists are circular.

Item deletion requires that both surrounding elements are locked, however since
the locking rules dictate that we lock elements in a single direction we have
to lock the previous element while it might be deleted under us. Hence the
requirement that all elements are RCU freed.

I think implicitly locked data structures are very bad for code readability
and debugability. What's even worse here is that we have a requirement that
all members are RCU freed.

Note that we also have another implicitly locked (and refcounted) list
implementation in klist.[ch] - if we find consensus that we want implicitly
locked list we should figure out whether we want lock_list or klist semantics
and stick to one of them.

klist is quite different in that it locks the whole list. The proposed
data structure locks each edge, that is it will allow concurrent
deletion of elements as long as they don't share neighbours.

What uses do you have planned for this data structure? In general I think
we'd be better off to simplify the data structures as in my files_list_lock
proposal instead of complicating the locking.

Getting rid of the s_files list like you proposed would of course be a
much better solution, and I'll look into that.

Not having the VFS knowledge you do I just smashed the lock and kept
current semantics.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: CMultiLock example
    ... Then, of course, there is the issue of "why lock at all?" ... For me, this means designing a ... avoids unnecessary locking. ... There are multiple link lists modified within the thread. ...
    (microsoft.public.vc.mfc)
  • Re: CMultiLock example
    ... Seriously, though, locking is *mandatory* if two or more threads are accessing non-scalar ... lists ever be modified while the threads are running. ... without a lock. ... You must prevent that one piece of data is modified from multiple ...
    (microsoft.public.vc.mfc)
  • Re: [PATCH 17/18] fs: icache remove inode_lock
    ... If you understand inode locking today, ... can understand the inode scaling series quite easily. ... filesystems to lock down the object without taking a global ... fine-grained per-zone LRU lists and locking. ...
    (Linux-Kernel)
  • Re: review of ocfs2
    ... > of the more advanced file system level AIO code. ... > What lock protects steady queue here? ... > Looks quite obfuscated with the separate argument lists. ...
    (Linux-Kernel)
  • [patch 3/6] lightweight robust futexes: docs
    ... +The robust futex ABI ... for kernel assist of cleanup of held locks on task exit. ... will attempt to process both lists on each task ... pointer to a single linked list of 'lock entries', one per lock, ...
    (Linux-Kernel)