voroskoi/skiplist.zig - Change ZICZD2NLRUKJL4PUQSNFRYCBVYU27QMVNFFUHTTZSWW6HVVFTUSAC

Fix SIGSEGV

Created by voroskoi on December 31, 2024

ZICZD2NLRUKJL4PUQSNFRYCBVYU27QMVNFFUHTTZSWW6HVVFTUSAC

Dependencies

In channels

main

Change contents

Replacement in src/main.zig at line 104 [5.33]

B:BD[3.3174] → [4.2058:2142]

    try pool.init(std.Thread.Pool.Options{ .allocator = std.heap.page_allocator });

[3.3174]

[3.3271]

    try pool.init(std.Thread.Pool.Options{
        .allocator = std.heap.page_allocator,
        .n_jobs = null,
    });

Deletion in src/lazy.zig at line 62 [7.108]

B:BD[4.7206] → [6.177:695]

∅:D[6.695] → [4.7254:7255]

B:BD[4.7254] → [4.7254:7255]

                // Various checks
                std.debug.assert(n.nexts.len == level + 1);
                std.debug.assert(n.marked == false);
                std.debug.assert(n.fully_linked == false);
                if (builtin.mode == .Debug) {
                    // Unnecessary lock test ;-)
                    n.lock.lock();
                    defer n.lock.unlock();
                    for (n.nexts) |next| {
                        std.debug.assert(next == null);
                    }
                }

Insertion in src/lazy.zig at line 97 [7.108]
[8.1003]
[7.3502]
Insertion in src/lazy.zig at line 179 [7.108]
[8.1539]
[7.5577]
```
            // TODO: use a lookup table!
```

Replacement in src/lazy.zig at line 243 [7.108]

B:BD[9.1439] → [9.1439:1531]

∅:D[10.149] → [7.8669:8670]

∅:D[6.964] → [7.8669:8670]

∅:D[9.1531] → [7.8669:8670]

∅:D[11.9468] → [7.8669:8670]

B:BD[7.8669] → [7.8669:8670]

B:BD[7.8670] → [9.1532:1741]

∅:D[9.1741] → [4.7834:7835]

B:BD[11.9678] → [4.7834:7835]

B:BD[4.7835] → [9.1742:2025]

                var node = try Node.init(self.allocator, insert_key, insert_value, rlevel);
                LEVELS: for (0..node.nexts.len) |level| {
                    node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet
                    preds[level].?.nexts[level] = node;
                    if (builtin.mode == .Debug) {
                        // If the next is not null, make sure its key is set
                        if (node.nexts[level]) |next_node| {
                            std.debug.assert(next_node.key != null);
                        }

[9.1439]

[10.399]

                {
                    var node = try Node.init(self.allocator, insert_key, insert_value, rlevel);

Replacement in src/lazy.zig at line 246 [7.108]

B:BD[10.400] → [9.2026:2312]

∅:D[9.2312] → [4.8654:8680]

B:BD[4.8654] → [4.8654:8680]

B:BD[4.8680] → [9.2313:2371]

                        // Check if all pred nodes were locked when we inserted this node.
                        var lit = locks.bitset.iterator(.{});
                        while (lit.next()) |lvl| {
                            if (preds[lvl].? == preds[level].?) continue :LEVELS;
                        }
                        @panic("level is not locked...");

[10.400]

[11.9678]

                    for (0..node.nexts.len) |level| {
                        node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet
                        preds[level].?.nexts[level] = node;

Insertion in src/lazy.zig at line 250 [7.108]

[11.9700]

[9.2372]

                    node.fully_linked = true;

Deletion in src/lazy.zig at line 252 [7.108]
B:BD[9.2390] → [9.2390:2432]
```
                node.fully_linked = true;
```
Insertion in src/lazy.zig at line 262 [7.108]
[12.121]
[9.2566]
```
            _ = self;
```

Replacement in src/lazy.zig at line 316 [7.108]

B:BD[9.3819] → [9.3819:4108]

B:BD[9.4108] → [2.385:586]

∅:D[2.586] → [4.8749:8750]

∅:D[9.4108] → [4.8749:8750]

B:BD[12.2010] → [4.8749:8750]

B:BD[4.8750] → [9.4109:4374]

∅:D[9.4374] → [4.9122:9152]

B:BD[4.9122] → [4.9122:9152]

B:BD[4.9152] → [9.4375:4437]

                    std.debug.assert(node_delete.?.nexts.len >= 1);
                    var level: usize = node_delete.?.nexts.len;
                    LEVELS: while (level > 0) : (level -= 1) {
                        preds[level - 1].?.nexts[level - 1] = node_delete.?.nexts[level - 1];
                        // Make sure that the newly set next node does not equal to the one marked for removal
                        std.debug.assert(node_delete.?.nexts[level - 1] != node_delete);
                        if (builtin.mode == .Debug) {
                            var lit = locks.bitset.iterator(.{});
                            while (lit.next()) |lvl| {
                                if (preds[lvl].? == preds[level - 1].?) continue :LEVELS;
                            }
                            @panic("level is not locked...");

[9.3819]

[12.2010]

                    {
                        var level: usize = node_delete.?.nexts.len;
                        while (level > 0) : (level -= 1) {
                            preds[level - 1].?.nexts[level - 1] = node_delete.?.nexts[level - 1];

Insertion in src/lazy.zig at line 321 [7.108]

[12.2036]

[9.4438]

                        node_delete.?.lock.unlock();
                        // TODO: If we free up the memory right here then any findNode() call in other
                        // threads can SIGSEGV. We have to count the references or never free up removed Nodes.
                        // node_delete.?.deinit(self.allocator);

Deletion in src/lazy.zig at line 327 [7.108]

B:BD[9.4460] → [9.4460:4567]

                    node_delete.?.lock.unlock();
                    node_delete.?.deinit(self.allocator);