Allocate/Free of Redis zskiplistNode that cannot be implemented in pure Zig with same memory layout and size

Help
,
1

I am using Zig to rewrite Redis 3.0.x for learning Zig and Redis.

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
    zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->obj = obj;
    return zn;
}

void zslFreeNode(zskiplistNode *node) {
    decrRefCount(node->obj);
    zfree(node);
}

Not allowed to use anything of glibc like c_allocator. The following code is a compromise solution:

/// SkipList.zig
pub const Node = struct {
    level: []Level,
    obj: ?*Object,
    score: f64,
    backward: ?*Node,
    _: [0]Level,

    const Level = struct {
        forward: ?*Node,
        span: u32,
    };

    pub fn create(
        allocator: Allocator,
        level: u32,
        score: f64,
        obj: ?*Object,
    ) Allocator.Error!*Node {
        const memsize: usize = @sizeOf(Node) + level * @sizeOf(Level);
        const mem = try allocator.alignedAlloc(
            u8,
            .of(Node),
            memsize,
        );
        const node: *Node = @ptrCast(@alignCast(mem));
        // CPU cache friendly.
        node.level.ptr = @ptrCast(@alignCast(mem.ptr + @sizeOf(Node)));
        node.level.len = level;
        node.obj = obj;
        node.score = score;
        node.backward = null;

        return node;
    }

    pub fn free(self: *Node, allocator: Allocator) void {
        if (self.obj) |obj| {
            obj.decrRefCount(allocator);
        }
        const mem: [*]align(@alignOf(Node)) u8 = @ptrCast(@alignCast(self));
        const memsize = @sizeOf(Node) + self.level.len * @sizeOf(Level);

        allocator.free(mem[0..memsize]);
    }
};

I’m a newbie to Zig. Is what I said in the title correct?

2

“Cannot” is a strong word, but it’s not as easy, no.

We had a nice Brainstorming thread about this a few months ago actually. In Zig, allocators do not keep track of how much memory they allocated, so you can’t simply give them a pointer and call it a day, you have to tell them how much memory you’re returning.

There are some strong tradeoffs here, I prefer what Zig does (for one thing, many a pwn starts with doing mischief to the length annotations of the heap), but just asking for more memory than fits in your struct and dishing it out is complicated and hard to get right.

3

Yes, it is tradeoffs. I just want to make sure there really isn’t an equivalent solution, because this is the first time I’m using system level language like Zig.

1 Like
4

I don’t think the _ : [0]Level field in your version is doing anything useful, ftr.

You can replace the extra []level slice with an inline function which casts through a [*]u8 multipointer and retrieve the trailing level list that way, if you really want to go the distance.

1 Like
5

You are right. _ : [0]Level just is a hint here.

You can replace the extra []level slice with an inline function which casts through a [*]u8 multipointer and retrieve the trailing level list that way, if you really want to go the distance.

My first solution was the one you’r advice. But self.level()[i] is so noisy.

6

Fair, and a zero-sized field is harmless enough.

There’s certainly a tradeoff between what’s idiomatic and ‘clean’ vs. doing it identically to the C code. The only necessary difference is that in Zig, the data structure has to keep track of the total allocation size somehow, in C malloc will do it.

Same amount of memory in principle, because willy nilly that amount does have to be tracked. Just a question of who is responsible for that, so to speak.

1 Like
7

This usage is also found in the standard library, for example in keys() and values() in ArrayHashMap.
It’s also possible to design it as self.level(i).

1 Like
8

+1 to self.level()[i] or self.level(i). Just in case the object is copied as a whole block of memory, you don’t have to deal with fixing up the level[] reference post copying.

2 Likes
9

It’s also possible to design it as self.level(i) .

After refactoring it as follows, I agree with you.

const SizedNode = struct {
    size: usize,
    node: Node,
};

pub const Node = struct {
    obj: ?*Object,
    score: f64,
    backward: ?*Node,

    const Level = struct {
        forward: ?*Node,
        span: u32,
    };

    pub fn create(
        allocator: Allocator,
        num_level: u32,
        score: f64,
        obj: ?*Object,
    ) Allocator.Error!*Node {
        const memsize: usize = @sizeOf(SizedNode) + num_level * @sizeOf(Level);
        const mem = try allocator.alignedAlloc(
            u8,
            .of(SizedNode),
            memsize,
        );
        const sno: *SizedNode = @ptrCast(@alignCast(mem));
        sno.size = memsize;
        sno.node = .{
            .obj = obj,
            .score = score,
            .backward = null,
        };
        return &sno.node;
    }

    pub inline fn level(self: *Node, i: usize) *Level {
        const offset = @sizeOf(Node) + @sizeOf(Level) * i;
        return @ptrFromInt(@intFromPtr(self) + offset);
    }

    pub fn free(self: *Node, allocator: Allocator) void {
        if (self.obj) |obj| {
            obj.decrRefCount(allocator);
        }
        const parent: *SizedNode = @fieldParentPtr("node", self);
        const mem: [*]align(@alignOf(SizedNode)) u8 = @ptrCast(@alignCast(parent));
        allocator.free(mem[0..parent.size]);
    }
};

It’s as noise-free as self.level[i], and restricted the layout view to be as same as C.

2 Likes