Skip to content

Lightpanda: the headless browser designed for AI and automation

8.8 KB
Raw Blame
// Copyright (C) 2023-2026  Lightpanda (Selecy SAS)
//
// Francis Bouvier <[email protected]>
// Pierre Tachoire <[email protected]>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

// Allocator for the Factory. Almost everything allocated here lives until the
// child arena goes: DOM nodes are never destroyed. The frees that do happen
// are mostly GC-finalized wrappers (collections, iterators), in batches.
//
// So an allocation is a plain allocation from the child (an arena), and a freed
// slot goes on the free list for its class, to be handed to the next
// allocation of that class. The free lists are only looked at once something
// has been freed. Nothing is ever returned to the child.

const std = @import("std");
const lp = @import("lightpanda");

const Allocator = std.mem.Allocator;
const Alignment = std.mem.Alignment;

const RecyclingAllocator = @This();

child_allocator: Allocator,

// Slots currently sitting on a free list. While 0, alloc skips the lookup.
free_slots: usize = 0,
free_lists: std.array_hash_map.Custom(Class, ?[*]u8, Class.Context, false) = .empty,

// Every slot can hold the free-list link. Alignments below usize's share a
// class, e.g. a 34-byte string and a 40-byte node recycle each other.
const Class = packed struct(u64) {
    alignment: Alignment,
    size: @Int(.unsigned, 64 - @bitSizeOf(Alignment)),

    fn of(len: usize, alignment: Alignment) Class {
        const class_alignment = Alignment.max(alignment, .of(usize));
        return .{
            .size = @intCast(class_alignment.forward(@max(len, @sizeOf(usize)))),
            .alignment = class_alignment,
        };
    }

    const Context = struct {
        pub fn hash(_: Context, class: Class) u32 {
            // A few dozen classes per page: a multiply spreads them well enough.
            return @truncate((@as(u64, @bitCast(class)) *% 0x9e3779b97f4a7c15) >> 32);
        }

        pub fn eql(_: Context, a: Class, b: Class, _: usize) bool {
            return a == b;
        }
    };
};

const Link = *align(1) ?[*]u8;

pub fn init(child_allocator: Allocator) RecyclingAllocator {
    return .{ .child_allocator = child_allocator };
}

pub fn allocator(self: *RecyclingAllocator) Allocator {
    return .{
        .ptr = self,
        .vtable = &.{
            .alloc = alloc,
            .free = free,
            .remap = Allocator.noRemap,
            .resize = Allocator.noResize,
        },
    };
}

fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
    const self: *RecyclingAllocator = @ptrCast(@alignCast(ctx));
    const class = Class.of(len, alignment);

    if (self.free_slots > 0) {
        if (self.free_lists.getPtr(class)) |head| {
            if (head.*) |slot| {
                head.* = @as(Link, @ptrCast(slot)).*;
                self.free_slots -= 1;
                return slot;
            }
        }
    }

    return self.child_allocator.rawAlloc(class.size, class.alignment, ret_addr);
}

fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, _: usize) void {
    const self: *RecyclingAllocator = @ptrCast(@alignCast(ctx));
    const class = Class.of(memory.len, alignment);

    // On OOM the slot just isn't recycled; the child still owns it.
    const gop = self.free_lists.getOrPut(self.child_allocator, class) catch return;
    if (gop.found_existing == false) {
        gop.value_ptr.* = null;
    }

    const slot = memory.ptr;
    if (comptime lp.IS_DEBUG) {
        // Make a use-after-free read garbage rather than the old object.
        @memset(slot[0..class.size], undefined);
    }
    @as(Link, @ptrCast(slot)).* = gop.value_ptr.*;
    gop.value_ptr.* = slot;
    self.free_slots += 1;
}

const testing = @import("testing.zig");
const TestAllocator = struct {
    arena: std.heap.ArenaAllocator,
    recycling: RecyclingAllocator,

    fn init(self: *TestAllocator) void {
        self.arena = .init(testing.allocator);
        self.recycling = .init(self.arena.allocator());
    }

    fn deinit(self: *TestAllocator) void {
        self.arena.deinit();
    }
};

test "RecyclingAllocator: allocation without frees never touches the free lists" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    for (0..100) |i| {
        const ptr = try recycler.alloc(u8, 24 + i);
        @memset(ptr, 42);
    }

    try testing.expectEqual(0, t.recycling.free_lists.count());
}

test "RecyclingAllocator: reuses freed memory of the same class" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    const ptr1 = try recycler.alloc(u8, 64);
    recycler.free(ptr1);

    const ptr2 = try recycler.alloc(u8, 64);
    try testing.expect(ptr1.ptr == ptr2.ptr);

    // free list is LIFO
    const a = try recycler.alloc(u8, 64);
    const b = try recycler.alloc(u8, 64);
    recycler.free(a);
    recycler.free(b);
    try testing.expectEqual(2, t.recycling.free_slots);
    try testing.expect(b.ptr == (try recycler.alloc(u8, 64)).ptr);
    try testing.expect(a.ptr == (try recycler.alloc(u8, 64)).ptr);
    try testing.expectEqual(0, t.recycling.free_slots);
}

test "RecyclingAllocator: different classes don't interfere" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    const ptr_64 = try recycler.alloc(u8, 64);
    recycler.free(ptr_64);

    const ptr_128 = try recycler.alloc(u8, 128);
    try testing.expect(ptr_64.ptr != ptr_128.ptr);

    try testing.expect(ptr_64.ptr == (try recycler.alloc(u8, 64)).ptr);
}

test "RecyclingAllocator: sizes share a class after rounding" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    // 34 and 40 bytes both round to 40, even at alignment 1
    const small = try recycler.alloc(u8, 34);
    recycler.free(small);
    const ptr = try recycler.alignedAlloc(u8, .@"8", 40);
    try testing.expect(small.ptr == ptr.ptr);

    // anything smaller than a pointer still fits the free-list link
    const tiny = try recycler.alloc(u8, 1);
    recycler.free(tiny);
    try testing.expect(tiny.ptr == (try recycler.alloc(u8, 3)).ptr);

    // u64 and u32 share the 8-byte class
    const int64 = try recycler.create(u64);
    recycler.destroy(int64);
    try testing.expectEqual(@intFromPtr(int64), @intFromPtr(try recycler.create(u32)));
}

test "RecyclingAllocator: never hands out a slot with weaker alignment" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    const ptr8 = try recycler.alignedAlloc(u8, .@"8", 64);
    recycler.free(ptr8);

    const ptr32 = try recycler.alignedAlloc(u8, .@"32", 64);
    try testing.expect(std.mem.isAligned(@intFromPtr(ptr32.ptr), 32));
    try testing.expect(ptr8.ptr != ptr32.ptr);
}

test "RecyclingAllocator: no resize support" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    const slice = try recycler.alloc(u8, 100);
    try testing.expect(!recycler.resize(slice, 90));
    try testing.expect(!recycler.resize(slice, 200));
}

test "RecyclingAllocator: stress" {
    var t: TestAllocator = undefined;
    t.init();
    defer t.deinit();
    const recycler = t.recycling.allocator();

    var prng = std.Random.DefaultPrng.init(0);
    const random = prng.random();

    var live: std.ArrayList([]u8) = .empty;
    defer live.deinit(testing.allocator);

    var frees: usize = 0;
    for (0..2000) |_| {
        if (random.boolean() and live.items.len > 0) {
            const slice = live.swapRemove(random.uintLessThan(usize, live.items.len));
            // still holds what we wrote: the slot wasn't handed out twice
            for (slice) |b| try testing.expectEqual(@as(u8, @truncate(slice.len)), b);
            recycler.free(slice);
            frees += 1;
        } else {
            const slice = try recycler.alloc(u8, random.uintAtMost(usize, 256) + 1);
            @memset(slice, @truncate(slice.len));
            try live.append(testing.allocator, slice);
        }
    }

    // some frees were handed back out
    try testing.expect(t.recycling.free_slots < frees);
}