Hazard pointers e reclamação por épocas

Uma pilha sem travas nunca bloqueia, mas não pode simplesmente liberar um nó que removeu: outra thread pode ter lido o topo há um instante e estar prestes a ler o next desse nó. Memória liberada pode ser reutilizada ou desmapeada, então essa leitura é um uso após liberação. Há duas curas clássicas. Os hazard pointers deixam uma thread anunciar o nó que usa. As épocas deixam anunciar quando entrou. Em ambos, um nó desligado só é liberado quando ninguém mais pode segurá-lo.

O modelo é a pilha do tópico ABA. Uma thread lê o topo, lê o nó e depois troca o topo num único compare-and-swap. O pop inseguro libera o nó no mesmo turno em que a troca tem sucesso. Um nó liberado é um nó que ninguém pode tocar, e read_node registra um uso após liberação sempre que uma thread lê um. Duas threads que removem uma vez cada dão apenas 20 escalonamentos, e o explorador acha logo os ruins: aqueles em que uma thread leu o topo, a outra removeu e liberou esse nó e a primeira depois o lê.

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

Um hazard pointer transforma a liberação numa conversa. Antes de ler um nó a thread escreve o número dele no seu espaço. Só isso não basta, porque o nó pode ter sido removido e liberado entre ler o topo e escrever o espaço, então a thread valida: lê o topo de novo e recomeça se ele mudou. Depois de um pop bem-sucedido a thread não libera o nó, põe-no na sua própria lista de aposentados e varre: lê uma vez o espaço de cada thread e libera só os nós aposentados que nenhum espaço cita. Os que restam na lista esperam uma varredura 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

A reclamação por épocas anuncia muito menos. Há um contador global de época. Uma thread escreve a época atual no seu espaço ao entrar numa operação e -1 ao sair, e nunca anuncia nós individuais. Um nó aposentado na época e só pode estar com uma thread que entrou na época e ou antes, então é seguro liberá-lo quando toda thread dentro de uma operação anunciou uma época maior que e. O preço é que uma thread que fica muito tempo dentro segura todos os nós aposentados desde que entrou, enquanto um hazard pointer segura só o nó que cita.

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

A segurança custa escalonamentos, porque cada anúncio, validação e varredura é mais um passo em que a outra thread pode se infiltrar: 20 virou 12 122 e 9012. É exatamente por isso que o explorador é útil aqui. Ele não precisa saber por que o esquema está certo, verifica cada um desses escalonamentos.

O laboratório segue a aula: o estado compartilhado com um conjunto de espaços por thread, o pop inseguro, o pop com hazard pointers, o pop com épocas, a verificação dos dois invariantes (nenhum uso após liberação, nada perdido), o verificador que explora todos os escalonamentos de um esquema e o estudo dos três esquemas em fechamentos do SPY.

• Função · perguntaBaseia-se em
• make_heap(values, threads)O que é compartilhado?Aritmética simples
• pop_unsafe(shared, tid)Remover e liberar na horaAritmética simples
• pop_hazard(shared, tid)Anunciar, validar, aposentar, varrerAritmética simples
• pop_epoch(shared, tid)Entrar, aposentar com a época, reclamarAritmética simples
• violations(final)Quais invariantes quebraram?Aritmética simples
• verify(scheme, values, pops)Um esquema é seguro sob todos os escalonamentos?explore_allviolations
• study(bars)Qual esquema sobrevive à pilha do SPY?verify

Próximo tópico: isto era uma pilha, e de brinquedo. O projeto final uma distribuição de dados de mercado sem travas coloca a habilidade inteira para trabalhar: ticks do SPY vão de um produtor a vários consumidores por uma estrutura sem travas, e o explorador prova seus invariantes sob todos os escalonamentos.