user2233706 user2233706 - 1 year ago 119
Linux Question

Add to tail of lock-less list

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

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 Source

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).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download