Linux kernelのチェーンテーブルを巡回するときに要素を削除する方法
カーネルのチェーンテーブルlist_ヘッドのデザインはかなり巧みだ.今日はリストについてお話ししますheadチェーンテーブルの遍歴時に要素を削除する方法.
チェーンテーブルの遍歴は、現在の要素を削除すると一般的にエラーが発生します.すべての言語のさまざまなライブラリのチェーンテーブルがそうです.list_ヘッドも同じです.
たとえば、javaのループで現在の要素を削除すると、java.util.C o n c u r r r e ntModificationException例外が放出されます.
参照:『Javaで1つのコレクションの複数の要素を削除する方法』http://blog.csdn.net/shendl/archive/2007/12/28/1999907.aspx 一文.
リストの使用for_eachはチェーンテーブルを遍歴し、現在の要素を脱チェーンすると、システムは容赦なくcrashを落とす.何のヒントもありません.そのため、このようなバグは非常に位置決めしにくい.
list_for_eachソース:
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) /
for (pos = (head)->next; prefetch(pos->next), pos != (head); /
pos = pos->next)
list_del脱鎖要素の後、nextとprevはそれぞれ次のように割り当てられます.
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTAlist_del_Init脱鎖要素の後、nextとprevはすべて自分に設定されます.
したがってlist_for_eachで現在の要素を削除すると、チェーンテーブルの次の要素が正しく見つかりません.
リストを巡回する場合はheadチェーンテーブルの場合、現在の要素を削除するにはlist_を使用する必要があります.for_each_safe関数はlist_を使用できませんfor_each関数.
list_for_each_safeソース:
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) /
for (pos = (head)->next, n = pos->next; pos != (head); /
pos = n, n = pos->next)
この関数はlist_よりfor_each関数にはnパラメータが1つ増えた.このパラメータもlist_headタイプです.
次の要素を保存することで、現在の要素を安全に削除でき、後続の要素が見つからないことはありません.
ループが終了すると、posはposのnext要素ではなくn要素を指す.posが脱鎖した後、pos要素のnextは空のポインタ、またはLIST_POISO N 1という無意味な値です.
リストが空の場合、pos=nの後もheadに等しく、遍歴はこれで終わります!
， lisf_for_each_safe list_head ， 。