Ein Analyse-Hinweis zu einer unidirektionalen Liste, für die (abhängig von den Bedingungen) keine Sperren erforderlich sind, die von Huang Ying von Intel eingeführt wurden.
Sie können die Liste parallel betreiben, ohne sie zu sperren, um der Liste (einzeln / mehrfach) hinzuzufügen und alle zu löschen. Wenn kein Konflikt zwischen dem Löschen eines einzelnen Eintrags aus der Liste besteht, ist parallel zum Hinzufügen zum Vorgang keine Sperre erforderlich. Eine Sperre ist jedoch erforderlich, wenn ein einzelner Löschvorgang aus einer Liste und ein vollständiger Löschvorgang oder ein einzelner Löschvorgang aus mehreren parallelen Threads in Konflikt stehen. Ein einzelner Löschvorgang wird nur vom Anfang der Liste an unterstützt. Da llist_add () nur am Anfang hinzugefügt wird, kann push / pop grundsätzlich als Liste implementiert werden.
| add | del_first | del_all | |
|---|---|---|---|
| add | - | - | - |
| del_first | L | L | |
| del_all | - |
Es wird zusammengefasst, dass del_first und del_all gesperrt werden sollten, wenn sie abgedeckt sind.
Die Implementierung ist in lib / llist.c geschrieben.
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;
}
Wenn man sich die zusätzliche Implementierung der Liste ansieht, die sich im Grunde wie bei Spinlock wiederholt, soll sie wiederholt werden, bis die atomare Einfügung oben in der Liste erfolgreich ist. Der wichtige Punkt ist, dass keine kritischen Abschnitte auftreten, da Sie (außer unter extremen Umständen) normalerweise nur um einen Speicherzugriff konkurrieren müssen.
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;
}
Das Löschen ist im Grunde auch eine Variante von Spinlock. Versuchen Sie nach dem Löschen, den nächsten Eintrag oben in der Liste mit der Anweisung atomar cmpxchg zu registrieren. Wenn dies fehlschlägt, werden andere Einträge vor dem Update hinzugefügt. Usw.) Es soll sich wiederholen. Ebenso tritt kein kritischer Abschnitt auf.
Allein damit scheint es kein Problem zu geben, selbst wenn Dels miteinander konkurrieren. Lesen wir den Header noch einmal im Detail.
* 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.
Mit anderen Worten, es kommt zu Konflikten, wenn die Add-> Add-Sequenz nach del auf einer anderen CPU auftritt, während del vorbelegt ist. Es wird so sein.
(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
Das? Wo ist C hingegangen? Mit anderen Worten, das Problem tritt parallel zum Prozess "Ein einmal gelöschter Eintrag wird aufgrund eines Verarbeitungsfehlers usw. wiederhergestellt" und zum Prozess "Hinzufügen eines Eintrags" und zum "Löschen eines Eintrags" auf. Es scheint auf den Fall von beschränkt zu sein. Es ist zu beachten, dass das gleiche Problem auch dann auftritt, wenn mehrere Prozesse "Einen Eintrag löschen und dann denselben Eintrag hinzufügen" ausgeführt werden. Kurz gesagt, es wird bestätigt, indem der Adresswert von head-> first als Schlüssel verwendet wird. Daher ist es gefährlich, wenn derselbe Adresswert zurückgegeben wird.
* 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.
Daher in einer Architektur ohne architektonisch NMI-sicheres cmpxchg im NMI-Handler Dies sollte nicht verwendet werden.