Linuxのllist (Lock-less NULL terminated single linked list)についてLinux IntelのHuang Yingさんによって導入された(条件によっては)ロックを使わなくてもよい単方向リストについての分析メモ。 LListとは リストへの(単一・複数)追加と全削除についてはロックなしに並行してリストの操作が可能。 また、リストからの単一エントリの削除同士が競合しなければ、リストへの追加の操作と並行してもロックは不要。 ただし、複数の並行するスレッドからリストからの単一削除と全削除あるいは単一削除が競合する場合については、ロックが必要になる。 単一削除の操作はリスト先頭からのみをサポート。llist_add()は先頭に追加するだけなので、基本的にはpush/popをリストで実装できるという話。 Lockが必要な条件 add del_fir