課題12: メモリ管理の実践

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

Part 1: カスタムアロケータ実装 (20点)

統計情報を記録するカスタムアロケータを実装してください。

ファイル: part1/custom_allocator.zig

const std = @import("std");

const TrackingAllocator = struct {
    parent_allocator: std.mem.Allocator,
    total_allocated: usize,
    total_freed: usize,
    current_allocated: usize,
    peak_allocated: usize,
    allocation_count: usize,
    free_count: usize,

    const Self = @This();

    pub fn init(parent: std.mem.Allocator) Self {
        return Self{
            .parent_allocator = parent,
            .total_allocated = 0,
            .total_freed = 0,
            .current_allocated = 0,
            .peak_allocated = 0,
            .allocation_count = 0,
            .free_count = 0,
        };
    }

    pub fn allocator(self: *Self) std.mem.Allocator {
        return .{
            .ptr = self,
            .vtable = &.{
                .alloc = alloc,
                .resize = resize,
                .free = free,
            },
        };
    }

    // TODO: alloc関数を実装
    fn alloc(
        ctx: *anyopaque,
        len: usize,
        ptr_align: u8,
        ret_addr: usize,
    ) ?[*]u8 {
        // 実装
    }

    // TODO: resize関数を実装
    fn resize(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        new_len: usize,
        ret_addr: usize,
    ) bool {
        // 実装
    }

    // TODO: free関数を実装
    fn free(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        ret_addr: usize,
    ) void {
        // 実装
    }

    pub fn printStats(self: Self) void {
        std.debug.print("=== Allocator Statistics ===\n", .{});
        std.debug.print("Total allocated: {} bytes\n", .{self.total_allocated});
        std.debug.print("Total freed: {} bytes\n", .{self.total_freed});
        std.debug.print("Currently allocated: {} bytes\n", .{self.current_allocated});
        std.debug.print("Peak allocation: {} bytes\n", .{self.peak_allocated});
        std.debug.print("Allocation count: {}\n", .{self.allocation_count});
        std.debug.print("Free count: {}\n", .{self.free_count});
    }
};

pub fn main() !void {
    var tracking = TrackingAllocator.init(std.heap.page_allocator);
    const allocator = tracking.allocator();

    const data1 = try allocator.alloc(u8, 1024);
    const data2 = try allocator.alloc(u8, 2048);
    const data3 = try allocator.alloc(u8, 512);

    allocator.free(data1);
    allocator.free(data2);

    const data4 = try allocator.alloc(u8, 4096);

    allocator.free(data3);
    allocator.free(data4);

    tracking.printStats();
}

Part 2: メモリプール実装 (20点)

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

ファイル: part2/memory_pool.zig

const std = @import("std");

fn MemoryPool(comptime T: type, comptime capacity: usize) type {
    return struct {
        pool: [capacity]T,
        free_list: [capacity]bool,
        allocator: std.mem.Allocator,

        const Self = @This();

        // TODO: 初期化
        pub fn init(allocator: std.mem.Allocator) Self {
            // 実装
        }

        // TODO: オブジェクトを確保
        pub fn alloc(self: *Self) ?*T {
            // 実装
        }

        // TODO: オブジェクトを解放
        pub fn free(self: *Self, ptr: *T) void {
            // 実装
        }

        // TODO: 統計情報を取得
        pub fn stats(self: Self) struct {
            total: usize,
            used: usize,
            free: usize,
        } {
            // 実装
        }

        // TODO: すべてを解放
        pub fn reset(self: *Self) void {
            // 実装
        }
    };
}

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

pub fn main() !void {
    var pool = MemoryPool(Node, 10).init(std.heap.page_allocator);

    std.debug.print("=== Memory Pool ===\n\n", .{});

    // ノードを確保してリンクリストを作成
    const n1 = pool.alloc() orelse return error.OutOfMemory;
    const n2 = pool.alloc() orelse return error.OutOfMemory;
    const n3 = pool.alloc() orelse return error.OutOfMemory;

    n1.* = .{ .value = 1, .next = n2 };
    n2.* = .{ .value = 2, .next = n3 };
    n3.* = .{ .value = 3, .next = null };

    var s = pool.stats();
    std.debug.print("After allocation: {}/{} used\n", .{s.used, s.total});

    // リンクリストを辿る
    var current: ?*Node = n1;
    std.debug.print("List: ", .{});
    while (current) |node| {
        std.debug.print("{} -> ", .{node.value});
        current = node.next;
    }
    std.debug.print("null\n\n", .{});

    // 一部を解放
    pool.free(n2);
    s = pool.stats();
    std.debug.print("After free: {}/{} used\n", .{s.used, s.total});

    // 再確保
    const n4 = pool.alloc() orelse return error.OutOfMemory;
    n4.* = .{ .value = 4, .next = null };

    s = pool.stats();
    std.debug.print("After realloc: {}/{} used\n", .{s.used, s.total});
}

Part 3: アリーナアロケータの活用 (20点)

ArenaAllocatorを使った効率的なメモリ管理を実装してください。

ファイル: part3/arena_usage.zig

const std = @import("std");

const JsonValue = union(enum) {
    Null,
    Bool: bool,
    Number: f64,
    String: []const u8,
    Array: []JsonValue,
    Object: std.StringHashMap(JsonValue),
};

// TODO: Arenaを使ってJSONをパース（簡易版）
fn parseJson(arena: std.mem.Allocator, json_str: []const u8) !JsonValue {
    _ = json_str;
    // 実装（簡略化のため固定値を返す）
    const array = try arena.alloc(JsonValue, 3);
    array[0] = JsonValue{ .Number = 1.0 };
    array[1] = JsonValue{ .Number = 2.0 };
    array[2] = JsonValue{ .Number = 3.0 };

    return JsonValue{ .Array = array };
}

// TODO: Arenaを使って文字列を連結
fn concatStrings(arena: std.mem.Allocator, strings: []const []const u8) ![]const u8 {
    // 実装
}

// TODO: Arenaを使って動的配列を構築
fn buildDynamicArray(arena: std.mem.Allocator, count: usize) ![]i32 {
    // 実装
}

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const allocator = arena.allocator();

    std.debug.print("=== Arena Allocator Usage ===\n\n", .{});

    // JSON パース
    const json = try parseJson(allocator, "[1, 2, 3]");
    switch (json) {
        .Array => |arr| {
            std.debug.print("Parsed array with {} elements\n\n", .{arr.len});
        },
        else => {},
    }

    // 文字列連結
    const parts = [_][]const u8{ "Hello", ", ", "World", "!" };
    const concatenated = try concatStrings(allocator, &parts);
    std.debug.print("Concatenated: {s}\n\n", .{concatenated});

    // 動的配列
    const array = try buildDynamicArray(allocator, 10);
    std.debug.print("Dynamic array: ", .{});
    for (array) |item| {
        std.debug.print("{} ", .{item});
    }
    std.debug.print("\n", .{});

    // すべてのメモリが一度に解放される
}

Part 4: メモリリーク検出 (20点)

GeneralPurposeAllocatorを使ってメモリリークを検出し、修正してください。

ファイル: part4/leak_detection.zig

const std = @import("std");

const LeakyContainer = struct {
    data: []u8,
    allocator: std.mem.Allocator,

    // TODO: 初期化（正しく実装）
    pub fn init(allocator: std.mem.Allocator, size: usize) !LeakyContainer {
        // 実装
    }

    // TODO: 解放（忘れずに実装）
    pub fn deinit(self: *LeakyContainer) void {
        // 実装
    }

    // TODO: データをコピー
    pub fn clone(self: LeakyContainer) !LeakyContainer {
        // 実装（メモリリークに注意）
    }
};

// TODO: リークのあるバージョン
fn processDataLeaky(allocator: std.mem.Allocator) !void {
    const data = try allocator.alloc(u8, 1024);
    // freeを忘れている！
    _ = data;
}

// TODO: 修正版
fn processDataFixed(allocator: std.mem.Allocator) !void {
    const data = try allocator.alloc(u8, 1024);
    defer allocator.free(data);

    // 処理
    for (data, 0..) |*byte, i| {
        byte.* = @intCast(i % 256);
    }
}

pub fn main() !void {
    std.debug.print("=== Memory Leak Detection ===\n\n", .{});

    // テスト1: リークあり
    {
        std.debug.print("Test 1: Leaky version\n", .{});
        var gpa = std.heap.GeneralPurposeAllocator(.{}){};
        const allocator = gpa.allocator();

        try processDataLeaky(allocator);

        const leaked = gpa.deinit();
        if (leaked == .leak) {
            std.debug.print("Result: LEAK DETECTED ❌\n\n", .{});
        }
    }

    // テスト2: 修正版
    {
        std.debug.print("Test 2: Fixed version\n", .{});
        var gpa = std.heap.GeneralPurposeAllocator(.{}){};
        const allocator = gpa.allocator();

        try processDataFixed(allocator);

        const leaked = gpa.deinit();
        if (leaked == .ok) {
            std.debug.print("Result: NO LEAKS ✓\n\n", .{});
        }
    }

    // テスト3: Container
    {
        std.debug.print("Test 3: Container\n", .{});
        var gpa = std.heap.GeneralPurposeAllocator(.{}){};
        const allocator = gpa.allocator();

        var container = try LeakyContainer.init(allocator, 512);
        defer container.deinit();

        const leaked = gpa.deinit();
        if (leaked == .ok) {
            std.debug.print("Result: NO LEAKS ✓\n", .{});
        }
    }
}

ボーナス課題 (20点)

Bonus 1: スラブアロケータ (10点)

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

ファイル: bonus1/slab_allocator.zig

const std = @import("std");

const SlabAllocator = struct {
    small_pool: [64]*[32]u8,
    medium_pool: [32]*[128]u8,
    large_pool: [16]*[512]u8,
    parent_allocator: std.mem.Allocator,

    const Self = @This();

    // TODO: 実装
    pub fn init(parent: std.mem.Allocator) !Self {
        // 実装
    }

    pub fn deinit(self: *Self) void {
        // 実装
    }

    pub fn allocator(self: *Self) std.mem.Allocator {
        // 実装
    }

    // TODO: サイズに応じて適切なプールから確保
    fn alloc(
        ctx: *anyopaque,
        len: usize,
        ptr_align: u8,
        ret_addr: usize,
    ) ?[*]u8 {
        _ = ctx;
        _ = len;
        _ = ptr_align;
        _ = ret_addr;
        // 実装
    }

    fn resize(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        new_len: usize,
        ret_addr: usize,
    ) bool {
        _ = ctx;
        _ = buf;
        _ = buf_align;
        _ = new_len;
        _ = ret_addr;
        // 実装
    }

    fn free(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        ret_addr: usize,
    ) void {
        _ = ctx;
        _ = buf;
        _ = buf_align;
        _ = ret_addr;
        // 実装
    }
};

pub fn main() !void {
    var slab = try SlabAllocator.init(std.heap.page_allocator);
    defer slab.deinit();

    const allocator = slab.allocator();

    const small = try allocator.alloc(u8, 16);
    defer allocator.free(small);

    const medium = try allocator.alloc(u8, 64);
    defer allocator.free(medium);

    const large = try allocator.alloc(u8, 256);
    defer allocator.free(large);

    std.debug.print("Allocated small, medium, and large buffers\n", .{});
}

Bonus 2: コピーオンライト (10点)

コピーオンライトの仕組みを実装してください。

ファイル: bonus2/copy_on_write.zig

const std = @import("std");

fn CowString(comptime max_size: usize) type {
    return struct {
        data: *[max_size]u8,
        len: usize,
        ref_count: *usize,
        allocator: std.mem.Allocator,

        const Self = @This();

        // TODO: 実装
        pub fn init(allocator: std.mem.Allocator, str: []const u8) !Self {
            // 実装
        }

        pub fn deinit(self: *Self) void {
            // 実装: ref_countをデクリメント、0なら解放
        }

        pub fn clone(self: Self) !Self {
            // 実装: ref_countをインクリメント
        }

        pub fn get(self: Self) []const u8 {
            return self.data[0..self.len];
        }

        // TODO: 書き込み時にコピー
        pub fn makeWritable(self: *Self) !void {
            if (self.ref_count.* > 1) {
                // コピーを作成
                const new_data = try self.allocator.create([max_size]u8);
                @memcpy(new_data[0..self.len], self.data[0..self.len]);

                const new_ref = try self.allocator.create(usize);
                new_ref.* = 1;

                self.ref_count.* -= 1;
                self.data = new_data;
                self.ref_count = new_ref;
            }
        }

        pub fn set(self: *Self, str: []const u8) !void {
            try self.makeWritable();
            @memcpy(self.data[0..str.len], str);
            self.len = str.len;
        }
    };
}

pub fn main() !void {
    const allocator = std.heap.page_allocator;

    std.debug.print("=== Copy-on-Write String ===\n\n", .{});

    var str1 = try CowString(128).init(allocator, "Hello");
    defer str1.deinit();

    std.debug.print("str1: {s}\n", .{str1.get()});

    // クローン（データはコピーされない）
    var str2 = try str1.clone();
    defer str2.deinit();
    std.debug.print("str2 (cloned): {s}\n", .{str2.get()});

    // str2を変更（この時点でコピーされる）
    try str2.set("World");
    std.debug.print("str2 (modified): {s}\n", .{str2.get()});
    std.debug.print("str1 (unchanged): {s}\n", .{str1.get()});
}

評価基準

項目 配点
Part 1: カスタムアロケータ実装 20点
Part 2: メモリプール実装 20点
Part 3: アリーナアロケータの活用 20点
Part 4: メモリリーク検出 20点
**マンダトリー合計** **80点**
Bonus 1: スラブアロケータ 10点
Bonus 2: コピーオンライト 10点
**ボーナス合計** **20点**

合格基準

  • マンダトリー: 64点以上で合格（80点満点の80%）
  • ボーナス: 追加評価（最終成績の加算）

    • 提出方法

    exercise12/
├── part1/
│   └── custom_allocator.zig
├── part2/
│   └── memory_pool.zig
├── part3/
│   └── arena_usage.zig
├── part4/
│   └── leak_detection.zig
├── bonus1/
│   └── slab_allocator.zig
└── bonus2/
    └── copy_on_write.zig

    テスト実行

    # マンダトリー
zig run part1/custom_allocator.zig
zig run part2/memory_pool.zig
zig run part3/arena_usage.zig
zig run part4/leak_detection.zig

# ボーナス
zig run bonus1/slab_allocator.zig
zig run bonus2/copy_on_write.zig

    参考資料

  • Zig Language Reference - Memory: https://ziglang.org/documentation/master/#Memory
  • Zig Standard Library - Heap: https://ziglang.org/documentation/master/std/#std.heap
  • Ziglearn - Allocators: https://ziglearn.org/chapter-2/#allocators

Previous
第12章: メモリ管理
Next
第13章: テスト