Pointeurs de danger et récupération par époques

Une pile sans verrou ne bloque jamais, mais elle ne peut pas simplement libérer un nœud qu'elle a dépilé : un autre thread a pu lire la tête il y a un instant et s'apprêter à lire le next de ce nœud. La mémoire libérée peut être réutilisée ou retirée, donc cette lecture est un usage après libération. Il existe deux remèdes classiques. Les pointeurs de danger laissent un thread annoncer le nœud qu'il utilise. Les époques lui font annoncer quand il est entré. Dans les deux cas, un nœud détaché n'est libéré que lorsque plus personne ne peut le tenir.

Le modèle est la pile du sujet ABA. Un thread lit la tête, lit le nœud, puis échange la tête en un seul compare-and-swap. Le dépilage dangereux libère le nœud dans le tour même où l'échange réussit. Un nœud libéré est un nœud que personne ne doit toucher, et read_node enregistre un usage après libération chaque fois qu'un thread en lit un. Deux threads qui dépilent une fois chacun donnent seulement 20 ordonnancements, et l'explorateur trouve aussitôt les mauvais : ceux où un thread a lu la tête, l'autre a dépilé et libéré ce nœud, et le premier le lit ensuite.

def pop_unsafe(shared, tid):    while True:        yield        idx = shared["head"]        if idx == -1:            return None        yield        nxt, value = read_node(shared, idx)        yield        if compare_and_swap(shared, "head", idx, nxt):            shared["popped"] = shared["popped"] + (value,)            free_node(shared, idx)            return valuedef two_pops(shared):    return [pop_unsafe(shared, 0), pop_unsafe(shared, 1)]outcomes = explore_all(two_pops, make_heap([9369, 9305]))hits = sum(n for key, n in outcomes.items() if dict(key)["uaf"])print(sum(outcomes.values()), "schedules,", hits, "of them read a freed node")

20 schedules, 6 of them read a freed node

Un pointeur de danger transforme la libération en dialogue. Avant de lire un nœud, le thread écrit son numéro dans son emplacement. Cela ne suffit pas, car le nœud a pu être dépilé et libéré entre la lecture de la tête et l'écriture de l'emplacement ; le thread valide donc : il relit la tête et recommence si elle a bougé. Après un dépilage réussi, le thread ne libère pas le nœud, il le met dans sa propre liste de retraite et balaie : il lit une fois l'emplacement de chaque thread et ne libère que les nœuds retirés qu'aucun emplacement ne nomme. Les nœuds restants attendent un balayage ultérieur.

def pop_hazard(shared, tid):    while True:        yield        idx = shared["head"]        if idx == -1:            shared["hp%d" % tid] = -1            return None        yield        shared["hp%d" % tid] = idx        yield        if shared["head"] != idx:            continue        yield        nxt, value = read_node(shared, idx)        yield        if compare_and_swap(shared, "head", idx, nxt):            shared["popped"] = shared["popped"] + (value,)            shared["hp%d" % tid] = -1            shared["retired%d" % tid] = shared["retired%d" % tid] + (idx,)            break    yield    hazards = tuple(shared["hp%d" % t] for t in range(shared["threads"]))    yield    keep = []    for node in shared["retired%d" % tid]:        if node in hazards:            keep.append(node)        else:            free_node(shared, node)    shared["retired%d" % tid] = tuple(keep)    return valuedef two_pops(shared):    return [pop_hazard(shared, 0), pop_hazard(shared, 1)]outcomes = explore_all(two_pops, make_heap([9369, 9305]))hits = sum(n for key, n in outcomes.items() if dict(key)["uaf"])waiting = max(sum(len(dict(key)["retired%d" % t]) for t in (0, 1)) for key in outcomes)print(sum(outcomes.values()), "schedules,", hits, "read a freed node, up to", waiting, "node waiting at the end")

12122 schedules, 0 read a freed node, up to 1 node waiting at the end

La récupération par époques annonce bien moins. Il y a un compteur global d'époque. Un thread écrit l'époque courante dans son emplacement en entrant dans une opération et -1 en la quittant, et n'annonce jamais de nœud individuel. Un nœud retiré à l'époque e ne peut être tenu que par un thread entré à l'époque e ou avant ; on peut donc le libérer quand chaque thread dans une opération a annoncé une époque supérieure à e. Le prix : un thread resté longtemps à l'intérieur retient tous les nœuds retirés après son entrée, alors qu'un pointeur de danger ne retient que le nœud qu'il nomme.

def pop_epoch(shared, tid):    yield    shared["ep%d" % tid] = shared["epoch"]    while True:        yield        idx = shared["head"]        if idx == -1:            shared["ep%d" % tid] = -1            return None        yield        nxt, value = read_node(shared, idx)        yield        if compare_and_swap(shared, "head", idx, nxt):            shared["popped"] = shared["popped"] + (value,)            shared["ep%d" % tid] = -1            shared["retired%d" % tid] = shared["retired%d" % tid] + ((idx, shared["epoch"]),)            shared["epoch"] = shared["epoch"] + 1            break    announced = []    for t in range(shared["threads"]):        yield        if shared["ep%d" % t] != -1:            announced.append(shared["ep%d" % t])    yield    keep = []    for node, epoch in shared["retired%d" % tid]:        if announced and epoch >= min(announced):            keep.append((node, epoch))        else:            free_node(shared, node)    shared["retired%d" % tid] = tuple(keep)    return valuedef two_pops(shared):    return [pop_epoch(shared, 0), pop_epoch(shared, 1)]outcomes = explore_all(two_pops, make_heap([9369, 9305]))hits = sum(n for key, n in outcomes.items() if dict(key)["uaf"])waiting = max(sum(len(dict(key)["retired%d" % t]) for t in (0, 1)) for key in outcomes)print(sum(outcomes.values()), "schedules,", hits, "read a freed node, up to", waiting, "node waiting at the end")

9012 schedules, 0 read a freed node, up to 1 node waiting at the end

La sûreté coûte des ordonnancements, car chaque annonce, validation et balayage est une étape de plus où l'autre thread peut s'insérer : 20 est devenu 12 122 et 9 012. C'est exactement pourquoi l'explorateur est utile ici. Il n'a pas besoin de savoir pourquoi la méthode est correcte, il vérifie chacun de ces ordonnancements.

Le labo suit le cours : l'état partagé avec un jeu d'emplacements par thread, le dépilage dangereux, le dépilage à pointeurs de danger, le dépilage à époques, la vérification des deux invariants (aucun usage après libération, rien de perdu), le vérificateur qui explore tous les ordonnancements d'une méthode, et l'étude des trois méthodes sur les clôtures SPY.

• Fonction · questionS'appuie sur
• make_heap(values, threads)Qu'est-ce qui est partagé ?De l'arithmétique simple
• pop_unsafe(shared, tid)Dépiler et libérer tout de suiteDe l'arithmétique simple
• pop_hazard(shared, tid)Annoncer, valider, retirer, balayerDe l'arithmétique simple
• pop_epoch(shared, tid)Entrer, retirer avec l'époque, récupérerDe l'arithmétique simple
• violations(final)Quels invariants sont brisés ?De l'arithmétique simple
• verify(scheme, values, pops)Une méthode est-elle sûre sous tous les ordonnancements ?explore_allviolations
• study(bars)Quelle méthode survit à la pile SPY ?verify

Sujet suivant : c'était une pile, et un jouet. Le projet final une diffusion de données de marché sans verrou met toute la compétence au travail : des ticks SPY vont d'un producteur à plusieurs consommateurs par une structure sans verrou, et l'explorateur prouve ses invariants sous tous les ordonnancements.