About Linux llist (Lock-less NULL terminated single linked list)

An analysis note about a unidirectional list that does not require the use of locks (depending on the conditions) introduced by Huang Ying of Intel.

What is List?

You can operate the list in parallel without locking for adding (single / multiple) to the list and deleting all. Also, if deleting a single entry from the list does not conflict with each other, no lock is required in parallel with the add operation to the list. However, a lock is required when a single delete from a list and a full delete or a single delete from multiple parallel threads conflict. Single delete operation is supported only from the beginning of the list. Since llist_add () is only added at the beginning, basically push / pop can be implemented as a list.

Conditions that require Lock

It is summarized that if del_first and del_all are affected, they should be locked.

Implementation of core part

The implementation is written in lib / llist.c.

bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
                     struct llist_head *head)
{
        struct llist_node *first;

        do {
                new_last->next = first = READ_ONCE(head->first);
        } while (cmpxchg(&head->first, first, new_first) != first);

        return !first;
}

Looking at the additional implementation to the list, basically like spinlock, it is supposed to repeat until the atomic insertion at the top of the list is successful, which is lockless but repeats. The important point is that no critical sections occur, because (unless in extreme circumstances) you'll usually only have to compete for one memory access.

struct llist_node *llist_del_first(struct llist_head *head)
{
        struct llist_node *entry, *old_entry, *next;

        entry = smp_load_acquire(&head->first);
        for (;;) {
                if (entry == NULL)
                        return NULL;
                old_entry = entry;
                next = READ_ONCE(entry->next);
                entry = cmpxchg(&head->first, old_entry, next);
                if (entry == old_entry)
                        break;
        }

        return entry;
}

Deletion is also basically a variant of spinlock, and after trying to delete it, try to register the next entry at the top of the list with the atomic cmpxchg instruction, and if it fails (other entries are added before the update). Etc.) It is designed to repeat. Similarly, no critical section occurs.

Conflict conditions

With this alone, it seems that there is no problem even if dels compete with each other. Let's read the header in detail again.

 * Cases where locking is needed:
 * If we have multiple consumers with llist_del_first used in one consumer, and
 * llist_del_first or llist_del_all used in other consumers, then a lock is
 * needed.  This is because llist_del_first depends on list->first->next not
 * changing, but without lock protection, there's no way to be sure about that
 * if a preemption happens in the middle of the delete operation and on being
 * preempted back, the list->first is the same as before causing the cmpxchg in
 * llist_del_first to succeed. For example, while a llist_del_first operation
 * is in progress in one consumer, then a llist_del_first, llist_add,
 * llist_add (or llist_del_all, llist_add, llist_add) sequence in another
 * consumer may cause violations.

In other words, it conflicts if the add-> add sequence occurs on another CPU after del while del is preempted. It will be like this.

(LLIST)A->B

(cpu1) entry[A] = smp_load_acquire(&head->first); (cpu1) old_entry[A] = entry; next[B] = READ_ONCE(entry->next);

(LLIST)A->B

(cpu0) entry[A] = smp_load_acquire(&head->first); (cpu0) old_entry[A] = entry; next[B] = READ_ONCE(entry->next); (cpu0) entry[A] = cmpxchg(&head->first[A], old_entry[A], next[B]);

(LLIST)B

(cpuX) new_last->next[B] = first[B] = READ_ONCE(head->first[B]); (cpuX) } while (cmpxchg(&head->first[B], first[B], new_first[C]) != first);

(LLIST)C->B

(cpu0) new_last->next[C] = first[C] = READ_ONCE(head->first[C]); (cpu0) } while (cmpxchg(&head->first[C], first[C], new_first[A]) != first);

(LLIST)A->C->B

(cpu1) entry = cmpxchg(&head->first[A], old_entry[A], next[B]);

(LLIST)B

that? Where did C go? In other words, the problem occurs in parallel with the process of "an entry that has been deleted once is restored due to a processing failure, etc.", and the process of "adding an entry" and the process of "deleting an entry". It seems to be limited to the case of. It should be noted that the same problem occurs even if multiple processes of "delete an entry and then add the same entry" are executed. In short, it is confirmed by using the address value of head-> first as a key, so it is dangerous if the same address value is returned.

Other notes

 * The basic atomic operation of this list is cmpxchg on long.  On
 * architectures that don't have NMI-safe cmpxchg implementation, the
 * list can NOT be used in NMI handlers.  So code that uses the list in
 * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.

Therefore, in an architecture that does not have an architecturally NMI-safe cmpxchg, in the NMI handler This should not be used.