Punteros de peligro y recuperación por épocas

Una pila sin cerrojos nunca bloquea, pero no puede simplemente liberar un nodo que ha sacado: otro hilo puede haber leído la cabeza hace un instante y estar a punto de leer el next de ese nodo. La memoria liberada puede reutilizarse o desasignarse, así que esa lectura es un uso tras liberar. Hay dos curas clásicas. Los punteros de peligro dejan que un hilo anuncie el nodo que usa. Las épocas le dejan anunciar cuándo entró. En ambos, un nodo desenlazado solo se libera cuando nadie puede seguir teniéndolo.

El modelo es la pila del tema ABA. Un hilo lee la cabeza, lee el nodo y luego cambia la cabeza en un solo compare-and-swap. El pop inseguro libera el nodo en el mismo turno en que el cambio tiene éxito. Un nodo liberado es un nodo que nadie puede tocar, y read_node registra un uso tras liberar cada vez que un hilo lee uno. Dos hilos que sacan una vez cada uno dan solo 20 planificaciones, y el explorador encuentra enseguida las malas: aquellas en que un hilo leyó la cabeza, el otro sacó y liberó ese nodo y el primero lo lee después.

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 puntero de peligro convierte la liberación en una conversación. Antes de leer un nodo el hilo escribe su número en su ranura. Eso solo no basta, porque el nodo puede haberse sacado y liberado entre leer la cabeza y escribir la ranura, así que el hilo valida: vuelve a leer la cabeza y empieza de nuevo si se movió. Tras un pop con éxito el hilo no libera el nodo, lo pone en su propia lista de retirados y barre: lee una vez la ranura de cada hilo y libera solo los nodos retirados que ninguna ranura nombra. Los que quedan en la lista esperan a un barrido posterior.

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 recuperación por épocas anuncia mucho menos. Hay un contador global de época. Un hilo escribe la época actual en su ranura al entrar en una operación y -1 al salir, y nunca anuncia nodos individuales. Un nodo retirado en la época e solo puede estar en manos de un hilo que entró en la época e o antes, así que es seguro liberarlo cuando cada hilo dentro de una operación anunció una época mayor que e. El precio es que un hilo que permanece mucho tiempo dentro retiene todos los nodos retirados desde que entró, mientras que un puntero de peligro retiene solo el nodo que nombra.

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 seguridad cuesta planificaciones, porque cada anuncio, validación y barrido es un paso más en el que el otro hilo puede colarse: 20 pasó a 12 122 y 9012. Por eso el explorador es útil aquí. No necesita saber por qué el esquema es correcto, comprueba cada una de esas planificaciones.

El laboratorio sigue la lección: el estado compartido con un juego de ranuras por hilo, el pop inseguro, el pop con punteros de peligro, el pop con épocas, la comprobación de los dos invariantes (ningún uso tras liberar, nada perdido), el verificador que explora todas las planificaciones de un esquema y el estudio de los tres esquemas sobre cierres de SPY.

• Función · preguntaSe apoya en
• make_heap(values, threads)¿Qué se comparte?Aritmética simple
• pop_unsafe(shared, tid)Sacar y liberar de inmediatoAritmética simple
• pop_hazard(shared, tid)Anunciar, validar, retirar, barrerAritmética simple
• pop_epoch(shared, tid)Entrar, retirar con la época, recuperarAritmética simple
• violations(final)¿Qué invariantes se rompieron?Aritmética simple
• verify(scheme, values, pops)¿Es seguro un esquema bajo todas las planificaciones?explore_allviolations
• study(bars)¿Qué esquema sobrevive a la pila de SPY?verify

Siguiente tema: esto era una pila, y de juguete. El proyecto final una difusión de datos de mercado sin cerrojos pone a trabajar toda la habilidad: los ticks de SPY van de un productor a varios consumidores por una estructura sin cerrojos, y el explorador demuestra sus invariantes bajo todas las planificaciones.