Linuxのllist (Lock-less NULL terminated single linked list)について

IntelのHuang Yingさんによって導入された（条件によっては）ロックを使わなくてもよい単方向リストについての分析メモ。

LListとは

リストへの(単一・複数）追加と全削除についてはロックなしに並行してリストの操作が可能。
また、リストからの単一エントリの削除同士が競合しなければ、リストへの追加の操作と並行してもロックは不要。
ただし、複数の並行するスレッドからリストからの単一削除と全削除あるいは単一削除が競合する場合については、ロックが必要になる。
単一削除の操作はリスト先頭からのみをサポート。llist_add()は先頭に追加するだけなので、基本的にはpush/popをリストで実装できるという話。

Lockが必要な条件

	add	del_first	del_all
add	-	-	-
del_first		L	L
del_all			-

del_firstとdel_allが被る場合はロックしておけ、ということがサマライズされている。

コア部分の実装

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;
}

リストへの追加の実装を見ると、基本的にはspinlockと同じく、リスト先頭へのatomicな挿入が成功するまで繰り返すことになっていて、まあlocklessではあるけど繰り返しは発生する。クリティカルセクションが発生しないというのが重要なポイント、というのは（極端な状況でなければ）大体は1メモリアクセス分の競合で済むからだ。

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;
}

削除も基本的にはspinlockの亜種であり、削除を試したあと、atomicなcmpxchg命令で次のエントリをリストの先頭に登録しようとしてみて、失敗だったら（更新前に他のエントリが追加されたなど）繰り返すようになっている。同じくクリティカルセクションは発生しない。

競合の条件

これだけだとdel同士が競合しても問題なさそうに見えるんだけども。もう一度詳しくヘッダを読んでみよう。

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

つまりdelがpreemptされている間にdelしてからadd->addのシーケンスが他のCPUで起きると競合する。
こういう風になる。

(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

あれ？Cは何処に行った?　となる。
つまり、問題が発生するのは「一度削除したエントリが、処理に失敗するなどして元に戻される」処理が、他に「エントリを追加する」処理と「エントリを削除する」処理が並行している場合に限られそう。注意が必要なのは、「一度エントリを削除してから同じエントリを追加する」処理が複数走っても同じ問題が起きる。
要するにhead->firstのアドレス値をキーにして確認しているため、同じアドレス値が戻ってきた場合には危険であると。

その他注意点

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

とあるので、アーキテクチャ的にNMI-safeなcmpxchgがないアーキテクチャではNMIハンドラ内では
これは使ってはならないとのこと。