user2233706 user2233706 - 3 months ago 25
Linux Question

Add to tail of lock-less list

I'm using the Linux kernel's lock-less list as defined in

llist.h
.
llist_add
adds to the list, but it adds the new node right after the head. How can I add to the tail of the list in constant time?

Answer

How can I add to the tail of the list in constant time?

You cannot.

Lockless property for llist's comes at the cost of reduced functionality: only addition to the beginning, removing the first element and removing all elements are supported. And even this reduction is not sufficient for make it lockless always, see description at the beginning of the header inclide/linux/llist.h.

Actually, lockless property of some objects is rarely a requirement. In most cases usage of spinlocks is acceptible. If it is your case, instead of lockfree llist you may use double-linked lists list_head, protected by spinlocks. Double-linked lists stores pointer to the last element and supports addition after it (function list_add_tail).

Comments