Une note d'analyse sur une liste unidirectionnelle qui ne nécessite pas l'utilisation de verrous (selon les conditions) introduits par Huang Ying d'Intel.
Vous pouvez faire fonctionner la liste en parallèle sans verrouiller pour ajouter (simple / multiple) à la liste et tout supprimer. De plus, si la suppression d'une seule entrée de la liste n'entre pas en conflit, aucun verrou n'est requis en parallèle avec l'opération d'ajout à la liste. Cependant, un verrou est requis lorsqu'une seule suppression d'une liste et une suppression complète ou une seule suppression de plusieurs threads parallèles sont en conflit. L'opération de suppression unique n'est prise en charge qu'à partir du début de la liste. Puisque llist_add () n'est ajouté qu'au début, push / pop peut être implémenté sous forme de liste.
| add | del_first | del_all | |
|---|---|---|---|
| add | - | - | - |
| del_first | L | L | |
| del_all | - |
Il est résumé que si del_first et del_all sont couverts, ils devraient être verrouillés.
L'implémentation est écrite dans 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;
}
En regardant l'implémentation supplémentaire de la liste, essentiellement comme le verrou tournant, il est censé se répéter jusqu'à ce que l'insertion atomique en haut de la liste soit réussie, ce qui est sans verrouillage mais se répète. Le point important est qu'aucune section critique ne se produit, car (sauf dans des circonstances extrêmes) vous n'aurez généralement à rivaliser que pour un accès mémoire.
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;
}
La suppression est également fondamentalement une variante de spinlock, et après avoir essayé de supprimer, essayez d'enregistrer l'entrée suivante en haut de la liste avec l'instruction atomic cmpxchg, et si elle échoue (d'autres entrées sont ajoutées avant la mise à jour). Etc.) Il est conçu pour se répéter. De même, aucune section critique ne se produit.
Rien qu'avec cela, il semble qu'il n'y ait pas de problème même si les dels se font concurrence. Lisons à nouveau l'en-tête en détail.
* 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.
En d'autres termes, il entre en conflit si la séquence add-> add se produit sur un autre CPU après del alors que del est préempté. Ce sera comme ça.
(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
cette? Où est allé C? En d'autres termes, le problème se produit en parallèle avec le processus de "une entrée qui a été supprimée une fois est restaurée en raison d'un échec de traitement, etc.", et le processus "d'ajout d'une entrée" et le processus de "suppression d'une entrée". Cela semble se limiter au cas de. Il est important de noter que le même problème se produit même si plusieurs processus de "supprimer une entrée puis ajouter la même entrée" sont exécutés. En bref, il est confirmé en utilisant la valeur d'adresse de head-> first comme clé, il est donc dangereux si la même valeur d'adresse est renvoyée.
* 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.
Par conséquent, dans une architecture qui n'a pas de cmpxchg de manière architecturale NMI-safe, dans le gestionnaire NMI Cela ne doit pas être utilisé.