課題1: カスタムアロケータ実装

マンダトリー要件 (80点)

Part 1: Stack Allocator実装 (30点)

スタック上に固定サイズのバッファを持ち、LIFOで解放を行うアロケータを実装してください。

要件:

const std = @import("std");
const Allocator = std.mem.Allocator;

pub const StackAllocator = struct {
    buffer: []u8,
    head: usize,
    allocations: std.ArrayList(Allocation),

    const Allocation = struct {
        offset: usize,
        size: usize,
    };

    pub fn init(buffer: []u8, base_allocator: Allocator) !StackAllocator {
        // TODO: 実装
        // - bufferをメモリプールとして使用
        // - allocationsリストを初期化（base_allocatorを使用）
    }

    pub fn deinit(self: *StackAllocator) void {
        // TODO: 実装
        // - allocationsリストを解放
    }

    pub fn allocator(self: *StackAllocator) Allocator {
        // TODO: 実装
        // - VTableを設定してAllocatorを返す
    }

    fn alloc(
        ctx: *anyopaque,
        len: usize,
        ptr_align: u8,
        ret_addr: usize,
    ) ?[*]u8 {
        // TODO: 実装
        // 1. アライメントを計算
        // 2. 十分な空き容量をチェック
        // 3. allocationを記録
        // 4. headを更新
        // 5. ポインタを返す
    }

    fn resize(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        new_len: usize,
        ret_addr: usize,
    ) bool {
        // TODO: 実装
        // 最後の割り当てのみリサイズ可能にする
    }

    fn free(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        ret_addr: usize,
    ) void {
        // TODO: 実装
        // LIFO順序での解放をチェック
        // 順序違反の場合はパニック
    }
};

テストコード:

test "StackAllocator basic operations" {
    var buffer: [4096]u8 = undefined;
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var stack = try StackAllocator.init(&buffer, gpa.allocator());
    defer stack.deinit();

    const allocator = stack.allocator();

    // 割り当て
    const ptr1 = try allocator.alloc(u8, 100);
    try std.testing.expect(ptr1.len == 100);

    const ptr2 = try allocator.alloc(i32, 50);
    try std.testing.expect(ptr2.len == 50);

    // LIFO順で解放
    allocator.free(ptr2);
    allocator.free(ptr1);
}

test "StackAllocator LIFO enforcement" {
    var buffer: [4096]u8 = undefined;
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var stack = try StackAllocator.init(&buffer, gpa.allocator());
    defer stack.deinit();

    const allocator = stack.allocator();

    const ptr1 = try allocator.alloc(u8, 100);
    const ptr2 = try allocator.alloc(u8, 100);

    // 逆順での解放を試みる（パニックするはず）
    // このテストは@panicでの失敗を期待
    allocator.free(ptr1);  // これはptr2の前なのでエラー
    allocator.free(ptr2);
}

Part 2: Pool Allocator実装 (30点)

固定サイズのオブジェクトを効率的に管理するプールアロケータを実装してください。

要件:

pub fn PoolAllocator(comptime T: type) type {
    return struct {
        const Self = @This();

        const Node = struct {
            next: ?*Node,
            data: T,
        };

        parent_allocator: Allocator,
        free_list: ?*Node,
        blocks: std.ArrayList([]Node),
        block_size: usize,

        pub fn init(parent_allocator: Allocator, block_size: usize) Self {
            // TODO: 実装
            // - block_sizeはブロックあたりのノード数
            // - 初期状態ではブロックを割り当てない（遅延割り当て）
        }

        pub fn deinit(self: *Self) void {
            // TODO: 実装
            // - 全ブロックを解放
            // - blocksリストを解放
        }

        pub fn allocator(self: *Self) Allocator {
            // TODO: 実装
        }

        fn allocBlock(self: *Self) !void {
            // TODO: 実装
            // 1. block_size個のNodeを割り当て
            // 2. 各Nodeをfree_listに追加
            // 3. blocksリストに追加
        }

        fn alloc(
            ctx: *anyopaque,
            len: usize,
            ptr_align: u8,
            ret_addr: usize,
        ) ?[*]u8 {
            // TODO: 実装
            // 1. サイズが@sizeOf(T)であることを確認
            // 2. free_listが空なら新しいブロックを割り当て
            // 3. free_listから1つ取り出す
            // 4. dataのポインタを返す
        }

        fn resize(
            ctx: *anyopaque,
            buf: []u8,
            buf_align: u8,
            new_len: usize,
            ret_addr: usize,
        ) bool {
            // プールアロケータはリサイズをサポートしない
            return false;
        }

        fn free(
            ctx: *anyopaque,
            buf: []u8,
            buf_align: u8,
            ret_addr: usize,
        ) void {
            // TODO: 実装
            // 1. サイズが@sizeOf(T)であることを確認
            // 2. bufからNodeのポインタを計算（@offsetOf使用）
            // 3. Nodeをfree_listの先頭に追加
        }
    };
}

テストコード:

test "PoolAllocator performance" {
    const Point = struct { x: f32, y: f32, z: f32 };

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var pool = PoolAllocator(Point).init(gpa.allocator(), 64);
    defer pool.deinit();

    const allocator = pool.allocator();

    // 大量の割り当て
    var points: [1000]*Point = undefined;
    for (&points) |*ptr| {
        ptr.* = try allocator.create(Point);
        ptr.*.* = .{ .x = 1.0, .y = 2.0, .z = 3.0 };
    }

    // 解放
    for (points) |ptr| {
        allocator.destroy(ptr);
    }

    // 再割り当て（free_listから再利用される）
    const new_point = try allocator.create(Point);
    allocator.destroy(new_point);
}

Part 3: メモリ使用量トラッキング (20点)

アロケータをラップして、メモリ使用量を追跡するラッパーを実装してください。

要件:

pub const TrackingAllocator = struct {
    parent_allocator: Allocator,
    total_allocated: usize,
    total_freed: usize,
    peak_allocated: usize,
    allocation_count: usize,
    free_count: usize,

    pub fn init(parent_allocator: Allocator) TrackingAllocator {
        // TODO: 実装
    }

    pub fn allocator(self: *TrackingAllocator) Allocator {
        // TODO: 実装
    }

    pub fn dumpStats(self: *TrackingAllocator) void {
        // TODO: 実装
        // 統計情報を標準出力に表示
        // - 総割り当て量
        // - 総解放量
        // - ピークメモリ使用量
        // - 割り当て回数
        // - 解放回数
        // - 現在のメモリ使用量
    }

    fn alloc(
        ctx: *anyopaque,
        len: usize,
        ptr_align: u8,
        ret_addr: usize,
    ) ?[*]u8 {
        // TODO: 実装
        // 1. 親アロケータで割り当て
        // 2. 統計を更新
        // 3. ポインタを返す
    }

    fn resize(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        new_len: usize,
        ret_addr: usize,
    ) bool {
        // TODO: 実装
        // リサイズ成功時に統計を更新
    }

    fn free(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        ret_addr: usize,
    ) void {
        // TODO: 実装
        // 1. 統計を更新
        // 2. 親アロケータで解放
    }
};

テストコード:

test "TrackingAllocator statistics" {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var tracking = TrackingAllocator.init(gpa.allocator());
    const allocator = tracking.allocator();

    // 複数の割り当て
    const buf1 = try allocator.alloc(u8, 1000);
    const buf2 = try allocator.alloc(i32, 500);
    const buf3 = try allocator.alloc(f64, 200);

    // 統計を確認
    try std.testing.expect(tracking.allocation_count == 3);
    try std.testing.expect(tracking.total_allocated > 0);

    // 一部解放
    allocator.free(buf2);
    try std.testing.expect(tracking.free_count == 1);

    // 残り解放
    allocator.free(buf1);
    allocator.free(buf3);

    // 最終統計
    tracking.dumpStats();
    try std.testing.expect(tracking.total_allocated == tracking.total_freed);
}

ボーナス課題 (20点)

Bonus 1: Slab Allocator実装 (10点)

複数のサイズクラスを管理するスラブアロケータを実装してください。

要件:

pub const SlabAllocator = struct {
    const SIZE_CLASSES = [_]usize{
        16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
    };

    const Slab = struct {
        size_class: usize,
        free_list: ?*Node,
        memory: []u8,

        const Node = struct {
            next: ?*Node,
        };

        // TODO: Slabの実装
    };

    parent_allocator: Allocator,
    slabs: [SIZE_CLASSES.len]std.ArrayList(Slab),

    // TODO: SlabAllocatorの実装
    // - サイズクラスに基づいて適切なスラブを選択
    // - 大きすぎる割り当ては親アロケータに委譲
    // - 各スラブでフリーリストを管理
};

パフォーマンス要件:

10万回の小さい割り当て（16-256バイト）が1秒以内
フラグメンテーションを最小化

Bonus 2: Buddy Allocator実装 (10点)

2のべき乗サイズでメモリを管理するバディアロケータを実装してください。

要件:

pub const BuddyAllocator = struct {
    const MIN_SIZE = 16;
    const MAX_ORDER = 20;  // 2^20 = 1MB

    const Block = struct {
        order: u5,
        is_free: bool,
        next: ?*Block,
        prev: ?*Block,
    };

    memory: []u8,
    free_lists: [MAX_ORDER + 1]?*Block,

    // TODO: BuddyAllocatorの実装
    // - 割り当て時にブロックを分割
    // - 解放時にバディとマージ
    // - フラグメンテーションを最小化
};

アルゴリズム:

要求サイズに適した最小のorderを計算
適切なサイズのフリーブロックを探す
大きすぎる場合は再帰的に分割
解放時にバディブロックを探してマージ

評価基準

項目	配点
Part 1: Stack Allocator	30点
Part 2: Pool Allocator	30点
Part 3: Tracking Allocator	20点
マンダトリー合計	80点
Bonus 1: Slab Allocator	10点
Bonus 2: Buddy Allocator	10点
ボーナス合計	20点

採点詳細

Stack Allocator (30点):

正しいalloc実装 (10点)
LIFOチェック機能 (10点)
アライメント処理 (5点)
リサイズサポート (5点)

Pool Allocator (30点):

正しいalloc/free (12点)
ブロック管理 (8点)
パフォーマンス (5点)
メモリリークなし (5点)

Tracking Allocator (20点):

正しい統計収集 (10点)
親アロケータへの委譲 (5点)
dumpStats実装 (5点)

合格基準

マンダトリー: 64点以上（80%）で合格
ボーナス: 優秀な実装に対する追加評価

提出方法

すべてのコードを exercise01/ ディレクトリに配置
ファイル構成:

exercise01/
├── stack_allocator.zig
├── pool_allocator.zig
├── tracking_allocator.zig
├── tests.zig
├── bonus1_slab.zig      (オプション)
└── bonus2_buddy.zig     (オプション)

テスト実行:

zig test exercise01/tests.zig

ヒント

Stack Allocator

// アライメント計算
const alignment = @as(usize, 1) << @as(u6, @intCast(ptr_align));
const aligned_offset = std.mem.alignForward(usize, self.head, alignment);

// LIFO検証
if (self.allocations.items.len == 0) return;  // エラー
const last_alloc = self.allocations.items[self.allocations.items.len - 1];
if (@intFromPtr(buf.ptr) != @intFromPtr(self.buffer.ptr) + last_alloc.offset) {
    @panic("Stack allocator: free must be in LIFO order");
}

Pool Allocator

// Nodeからdataポインタへの変換
const data_ptr = @as([*]u8, @ptrCast(&node.data));

// dataポインタからNodeへの逆変換
const node_ptr = @as(*Node, @ptrFromInt(
    @intFromPtr(buf.ptr) - @offsetOf(Node, "data")
));

Tracking Allocator

// ピーク更新
const current = self.total_allocated - self.total_freed;
if (current > self.peak_allocated) {
    self.peak_allocated = current;
}

Buddy Allocator

// バディアドレスの計算
fn getBuddy(self: *Self, block: *Block) ?*Block {
    const block_addr = @intFromPtr(block);
    const memory_start = @intFromPtr(self.memory.ptr);
    const offset = block_addr - memory_start;
    const size = @as(usize, 1) << @as(u6, block.order);
    const buddy_offset = offset ^ size;  // XORでバディを計算

    if (buddy_offset >= self.memory.len) return null;
    return @as(*Block, @ptrFromInt(memory_start + buddy_offset));
}

デバッグのコツ

メモリリーク検出:

var gpa = std.heap.GeneralPurposeAllocator(.{
    .safety = true,
    .verbose_log = true,
}){};
defer {
    const leaked = gpa.deinit();
    if (leaked == .leak) std.debug.print("LEAK!\n", .{});
}

アドレスの可視化:

std.debug.print("Address: 0x{x}, Size: {}, Align: {}\n", .{
    @intFromPtr(ptr),
    size,
    alignment,
});

状態のダンプ:

pub fn debugDump(self: *StackAllocator) void {
    std.debug.print("=== Stack Allocator ===\n", .{});
    std.debug.print("Buffer: 0x{x} - 0x{x}\n", .{
        @intFromPtr(self.buffer.ptr),
        @intFromPtr(self.buffer.ptr) + self.buffer.len,
    });
    std.debug.print("Head: {}\n", .{self.head});
    std.debug.print("Allocations: {}\n", .{self.allocations.items.len});
}

参考資料

Zig Standard Library Allocators: https://ziglang.org/documentation/master/std/#A;std:heap
Memory Pool Pattern: https://gameprogrammingpatterns.com/object-pool.html
Buddy Memory Allocation: https://en.wikipedia.org/wiki/Buddy_memory_allocation
Slab Allocation: https://en.wikipedia.org/wiki/Slab_allocation