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