Something went wrong. Try again.
[WIP] A toy kernel written in Zig
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341const std = @import("std");const Reader = std.Io.Reader;
const kernel = @import("../root.zig");const mem = kernel.mem;
extern const _start: u0;extern const _end: u0;
pub const FreeMemoryIterator = struct { dt: *const kernel.DeviceTree, offset: usize = 0, state: union(enum) { lookAtOffset: usize, shrinkBlok: mem.Range, finished, } = .{ .lookAtOffset = 0 },
pub fn init(dt: *const kernel.DeviceTree) FreeMemoryIterator { return .{ .dt = dt }; }
pub fn next(self: *FreeMemoryIterator) !?mem.Range { search: while (true) { switch (self.state) { .lookAtOffset => |offset| { var memory_it = MemoryIterator.init(self.dt); var found_memory: ?mem.Range = null;
while (try memory_it.next()) |memory| { if (memory.start < offset) { continue; }
if (found_memory) |best_memory| { if (memory.start < best_memory.start) { found_memory = memory; } } else { found_memory = memory; } }
if (found_memory) |memory| { self.state = .{ .shrinkBlok = memory }; } else { self.state = .finished; } }, .shrinkBlok => |*block| { if (block.len() == 0) { self.state = .{ .lookAtOffset = block.end }; continue :search; }
var current_block = block.*; var it = ReservedMemoryIterator.init(self.dt);
shrink: while (try it.next()) |rvmem| { if (rvmem.start >= current_block.end) { continue :shrink; }
if (rvmem.end <= current_block.start) { continue :shrink; }
if (rvmem.start <= current_block.start) { current_block.start = @min(current_block.end, rvmem.end); } else { current_block.end = rvmem.start; }
if (current_block.len() == 0) { break :shrink; } } block.start = current_block.end;
if (current_block.len() != 0) { return current_block; } }, .finished => return null, } } }};
pub const ReservedMemoryIterator = struct { dt: *const kernel.DeviceTree, state: union(enum) { binary_sections, dt_location, dt_rsvmem: kernel.DeviceTree.ReservationIterator, dt_nodes: ScanNodesState, finished, } = .binary_sections,
const ScanNodesState = struct { entries: kernel.DeviceTree.EntryIterator, address_cells: usize = 2, size_cells: usize = 1, state: union(enum) { at_root, in_reserved_memory_node, in_child_node, in_property: Reader, } = .at_root, };
pub const Error = kernel.DeviceTree.EntryIterator.Error || kernel.DeviceTree.ReservationIterator.Error || error{UnexpectedDTShape};
pub fn init(dt: *const kernel.DeviceTree) ReservedMemoryIterator { return .{ .dt = dt }; }
pub fn next(self: *ReservedMemoryIterator) !?mem.Range { while (true) { switch (self.state) { .binary_sections => { self.state = .dt_location; return .{ .start = @intFromPtr(&_start), .end = @intFromPtr(&_end), }; }, .dt_location => { self.state = .{ .dt_rsvmem = self.dt.reservations() }; return .fromSlice(self.dt.bytes.toplevel); }, .dt_rsvmem => |*reservations| { if (try reservations.next()) |reservation| { return reservation; }
var entries = self.dt.entries(); try entries.skip_begin_root();
self.state = .{ .dt_nodes = .{ .entries = entries } }; }, .dt_nodes => |*nodes| { if (try process_dt_nodes(nodes)) |result| { return result; }
self.state = .finished; return null; }, .finished => return null, } } }
fn process_dt_nodes(nodes: *ScanNodesState) !?mem.Range { while (true) { switch (nodes.state) { .at_root => { switch (try nodes.entries.next() orelse return null) { .begin_node => |node| { if (std.mem.eql(u8, node.full_name, "reserved-memory")) { nodes.state = .in_reserved_memory_node; } else { try nodes.entries.skip_out_of_node(); } }, .prop => |prop| { try try_parse_cell_prop(&nodes.address_cells, &nodes.size_cells, prop); }, .end_node => return null, } }, .in_reserved_memory_node => { switch (try nodes.entries.next() orelse return Error.UnexpectedDTShape) { .begin_node => { nodes.state = .in_child_node; }, .prop => |prop| { try try_parse_cell_prop(&nodes.address_cells, &nodes.size_cells, prop); }, .end_node => { nodes.state = .at_root; }, } }, .in_child_node => { switch (try nodes.entries.next() orelse return Error.UnexpectedDTShape) { .begin_node => { try nodes.entries.skip_out_of_node(); }, .end_node => { nodes.state = .in_reserved_memory_node; }, .prop => |prop| { if (std.mem.eql(u8, prop.name, "reg")) { nodes.state = .{ .in_property = .fixed(prop.value) }; } }, } }, .in_property => |*reg| { if (reg.seek == reg.buffer.len) { nodes.state = .in_child_node; continue; }
const address = try parse_cells(nodes.address_cells, reg); const size = try parse_cells(nodes.size_cells, reg);
return .{ .start = address, .end = address + size, }; }, } } }};
pub const MemoryIterator = struct { entries: kernel.DeviceTree.EntryIterator, address_cells: u32 = 2, size_cells: u32 = 1, state: State = .initial,
const State = union(enum) { initial, at_root, in_memory, in_reg_prop: Reader, };
pub fn init(dt: *const kernel.DeviceTree) MemoryIterator { return .{ .entries = dt.entries(), }; }
pub fn next(self: *MemoryIterator) !?mem.Range { while (true) { switch (self.state) { .initial => { try self.entries.skip_begin_root(); self.state = .at_root; }, .at_root => { const entry = try self.entries.next() orelse return null;
switch (entry) { .prop => |prop| { try try_parse_cell_prop(&self.address_cells, &self.size_cells, prop); }, .begin_node => |node| { if (std.mem.eql(u8, node.node_name, "memory")) { self.state = .in_memory; } else { try self.entries.skip_out_of_node(); } }, .end_node => { return null; }, } }, .in_memory => { const entry = try self.entries.next() orelse return null;
switch (entry) { .prop => |prop| { if (std.mem.eql(u8, prop.name, "reg")) { self.state = .{ .in_reg_prop = .fixed(prop.value) }; } }, .begin_node => { try self.entries.skip_out_of_node(); }, .end_node => { self.state = .at_root; }, } }, .in_reg_prop => |*reader| { if (reader.seek == reader.buffer.len) { self.state = .in_memory; continue; }
const address = try parse_cells(self.address_cells, reader); const size = try parse_cells(self.address_cells, reader);
return .{ .start = address, .end = address + size, }; }, } } }};
fn try_parse_cell_prop( address_cells: *u32, size_cells: *u32, prop: kernel.DeviceTree.PropEntry,) !void { const maybe_field = if (std.mem.eql(u8, prop.name, "#address-cells")) address_cells else if (std.mem.eql(u8, prop.name, "#size-cells")) size_cells else null;
if (maybe_field) |field| { var reader = Reader.fixed(prop.value); const value = try reader.takeInt(u32, .big); if (reader.seek != reader.buffer.len) { return Reader.Error.ReadFailed; } field.* = value; }}
fn parse_cells(n_cells: u32, reg: *std.Io.Reader) !usize { if (n_cells > 1) { for (0..n_cells - 1) |_| { if (try reg.takeInt(u32, .big) != 0) { return std.Io.Reader.Error.ReadFailed; } } } return if (n_cells > 0) try reg.takeInt(u32, .big) else 0;}