ハザードポインタとエポックベースの回収

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

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

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