diff options
| -rw-r--r-- | doc/0/0-value.md | 63 | ||||
| -rw-r--r-- | src/zisp/gc.zig | 39 | ||||
| -rw-r--r-- | src/zisp/gc/ListPool.zig (renamed from src/zisp/gc/CodePool.zig) | 6 | ||||
| -rw-r--r-- | src/zisp/value.zig | 32 | ||||
| -rw-r--r-- | src/zisp/value/array.zig | 137 | ||||
| -rw-r--r-- | src/zisp/value/pair.zig | 23 |
6 files changed, 177 insertions, 123 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index 2067842..f30735e 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -97,7 +97,7 @@ payload, which would step on Forbidden Pattern #2, Negative Infinity. This region of 51-bit non-zero values is divided as follows, based on the three highest bits, providing a payload value of 48 bits for each. - 000 :: Pointer to list (code) + 000 :: Pointer to list 001 :: Pointer to heap @@ -123,25 +123,26 @@ highest bits, providing a payload value of 48 bits for each. (etc.) +Forbidden Pattern #3, Positive cqNaN, is avoided thanks to the fact that some +bits of a list pointer are always set; see below. + Zisp splits the native program heap provided by the platform into three regions -of virtual memory: The code heap of 32 GiB, addressed in 64-bit (8-byte) units; +of virtual memory: The list heap of 32 GiB, addressed in 64-bit (8-byte) units; the main heap of 32 GiB, also addressed in 64-bit units; and the 4 GiB heap for `istr` objects (interned strings) which is addressed in bytes. Each region can thus be addressed via 32-bit indices instead of larger direct pointers. ### List pointers -In Zisp, a list is a contiguous array of a fixed number of Values. These may -reside in the main heap or the code heap; this pointer type here is used to -represent lists in the code heap only. - -These code lists are allocated with little or no padding and no metadata on the -heap, to achieve optimal memory density and cache locality of code. Therefore, -we must encode the length of the list directly in the pointer itself. +In Zisp, a list is a contiguous array of a fixed number of Values. To improve +memory density and cache locality, especially for the interpreter, lists of up +to 255 elements are allocated in tight blocks with little or no padding and no +metadata headers on the heap. Their length is therefore encoded directly with +an 8-bit metadata field within the NaN-packed pointer. The exact layout of the 48-bit payload is as follows: -The low 32 bits are an index into the code heap, while the higher 16 bits are +The low 32 bits are an index into the list heap, while the higher 16 bits are divided into 8 high bits for the length, and 8 low bits for garbage collector or other internal metadata. @@ -149,18 +150,10 @@ The length bits cannot be zero. The empty list is represented by a different bit pattern to provide a minor benefit during garbage collection: Zero-length lists can't needlessly trigger the code branch that handles list pointers. -The 8-bit length field means we can only encode lists of up to 255 elements -using this Value type. However, this doesn't mean that source code cannot -contain longer lists: - -Lists of arbitrary length can be allocated as regular heap objects of the Array -type; the difference is hidden when using a generic list API. This means that -*some* parts of source code may actually end up on the main heap, though lists -of greater than 255 elements should be extremely rare, typically only used to -embed static data arrays in source code anyway. - -Forbidden Pattern #3, Positive cqNaN, is avoided thanks to the fact that the -high 8 bits of the payload, encoding the list length, cannot be zero. +Note that "list pointer" and "list heap" are slightly misleading terms, since +arbitrary-length lists can be allocated on the main heap as Array objects with +element type Value. In this case, they are represented by a main heap pointer, +and the generic list API hides the difference. ### Heap pointers @@ -260,14 +253,17 @@ almost purely in-place mutations of the original source code tree. 011 :: Short string as constant - 100 :: Pointer to opcodes in code list + 100 :: Pointer to opcodes in list heap - 101 :: Pointer to opcodes in heap list + 101 :: Pointer to opcodes in main heap 110 :: Local variable reference index 111 :: Lexical capture reference index +Forbidden Pattern #4, Positive Infinity, is avoided thanks to the fact that +pointers to lists always have non-zero length bits. + ### Constant Values The first four categories simply mirror those of the previous 51-bit range, but @@ -275,20 +271,17 @@ mark the Value as being a constant rather than code to evaluate. This way, we can inject constant data into the AST without needing to worry about it being confused for code to evaluate, and without needing the `(quote ...)` wrapper. -Forbidden Pattern #4, Positive Infinity, is avoided thanks to the fact that -pointers to lists always have non-zero length bits. - ### Opcode array pointers -These types are derived from the regular code list pointers (length <= 255) and -heap list pointers (length > 255) by flipping 2 bits. +These types are derived from the regular list pointers (length <= 255) and main +heap Value Array pointers (length > 255) by flipping 2 bits. -A heap list pointer of this kind would result from a list of longer than 255 -that represents actual code to execute. (Had it been a quoted list, it would -have become a "pointer to heap as constant" instead.) This will be exceedingly -rare, given that regular code expressions almost never have such length, but we -must support it; it may result, for instance, from heavy macro use or otherwise -machine-generated source code. +A main heap pointer of this kind can only result from a list of more than 255 +elements which represents actual code to execute. (Had it been a quoted list, +it would have become a "pointer to heap as constant" instead.) This will be +exceedingly rare, given that regular code expressions almost never have such +length, but we must support it; it may result, for instance, from heavy macro +use or otherwise machine-generated source code. Either way, what this means is that a list has been analyzed to ensure it's a well-formed code expression, and transformed into an optimized form: diff --git a/src/zisp/gc.zig b/src/zisp/gc.zig index 0e26aa9..b36628f 100644 --- a/src/zisp/gc.zig +++ b/src/zisp/gc.zig @@ -5,25 +5,26 @@ const Alloc = std.mem.Allocator; const value = @import("value.zig"); -pub const CodePool = @import("gc/CodePool.zig"); +pub const ListPool = @import("gc/ListPool.zig"); pub const IstrPool = @import("gc/IstrPool.zig"); const HeapPtr = value.HeapPtr; +const HeapType = value.HeapType; var main_alloc: Alloc = undefined; -var code_heap_start: usize = undefined; +var list_heap_start: usize = undefined; var main_heap_start: usize = undefined; var istr_heap_start: usize = undefined; var main_list_pool: ListPool = undefined; var main_istr_pool: IstrPool = undefined; -pub fn codePtrFromIdx(idx: u32) [*]Value { - return @ptrFromInt(code_heap_start + idx * 8); +pub fn listPtrFromIdx(idx: u32) [*]Value { + return @ptrFromInt(list_heap_start + idx * 8); } -pub fn heapPtrFromIdx(idx: u32) HeapPtr { +pub fn heapPtrFromIdx(comptime typ: HeapType, idx: u32) typ.PtrType() { return @ptrFromInt(main_heap_start + idx * 8); } @@ -31,8 +32,8 @@ pub fn istrPtrFromIdx(idx: u32) [*]const u8 { return @ptrFromInt(istr_heap_start + idx); } -pub fn codeIdxFromPtr(ptr: [*]Value) u32 { - return @intCast(@intFromPtr(ptr - code_heap_start) / 8); +pub fn listIdxFromPtr(ptr: [*]Value) u32 { + return @intCast(@intFromPtr(ptr - list_heap_start) / 8); } pub fn heapIdxFromPtr(ptr: HeapPtr) u32 { @@ -43,6 +44,26 @@ pub fn istrIdxFromPtr(ptr: [*]const u8) u32 { return @intCast(@intFromPtr(ptr - istr_heap_start)); } +pub fn allocHeap(comptime typ: HeapType, len: usize) !typ.PtrType() { + const aln = std.mem.Alignment.of(HeapPtr); + return @ptrCast(main_alloc.alignedAlloc(u8, aln, len)); +} + +pub fn createHeap(comptime typ: HeapType) !typ.PtrType() { + return @ptrCast(main_alloc.create(typ.ObjType())); +} + +pub fn packHeap(ptr: anytype) Value { + const idx = heapIdxFromPtr(ptr); + const typ = value.HeapType.of(ptr); + return .{ .hptr = .{ .idx = idx, .typ = typ } }; +} + +pub fn unpackHeap(comptime typ: HeapType, v: Value) typ.PtrType() { + if (!v.isHptrTyp(typ)) @panic("Wrong type."); + return heapPtrFromIdx(typ, v.hptr.idx); +} + // init var init_done = false; @@ -53,10 +74,10 @@ pub fn init() !void { main_alloc = std.heap.smp_allocator; - //code_heap_start = ...; + //list_heap_start = ...; main_list_pool = try ListPool.init(main_alloc); - main_istr_set = try IstrPool.init(main_alloc); + main_istr_pool = try IstrPool.init(main_alloc); } pub fn mainAlloc() Alloc { diff --git a/src/zisp/gc/CodePool.zig b/src/zisp/gc/ListPool.zig index 56bf384..42bb50e 100644 --- a/src/zisp/gc/CodePool.zig +++ b/src/zisp/gc/ListPool.zig @@ -91,7 +91,7 @@ //! This shouldn't affect programs that simply load up all their modules, run //! forever without dynamic modification, and thus never deallocate code. //! -//! Otherwise, a simple solution is to use separate CodePool instances for +//! Otherwise, a simple solution is to use separate ListPool instances for //! modules, or just forget about all of this and rely on a compacting GC. //! @@ -106,8 +106,8 @@ const seg_stack = @import("../util/seg_stack.zig"); const Value = value.Value; const SegStack = seg_stack.SegStack; -const i2p = gc.codePtrFromIdx; -const p2i = gc.codeIdxFromPtr; +const i2p = gc.listPtrFromIdx; +const p2i = gc.listIdxFromPtr; const Self = @This(); diff --git a/src/zisp/value.zig b/src/zisp/value.zig index 9262a17..1a63349 100644 --- a/src/zisp/value.zig +++ b/src/zisp/value.zig @@ -19,6 +19,7 @@ pub const sval = @import("value/sval.zig"); pub const char = @import("value/char.zig"); pub const misc = @import("value/misc.zig"); +pub const pair = @import("value/pair.zig"); pub const array = @import("value/array.zig"); pub const boole = @import("value/boole.zig"); @@ -50,7 +51,7 @@ pub fn runeXsstr(v: Value) Value { } pub const MiscValue = enum(u8) { - // Make f/t only differ in one bit, to make `bool?` more efficient. + // Make sure f/t only differ in one bit, to make `bool?` more efficient. /// False f = 0, /// True @@ -71,20 +72,39 @@ pub const eof = Value{ .misc = .{ .value = .eof } }; pub const none = Value{ .misc = .{ .value = .none } }; // zig fmt: on -/// A plain (unpacked, untagged) pointer into the Zisp heap. -pub const HeapPtr = *anyopaque; +/// A plain (unpacked, untagged, uncompressed) pointer into the main heap. +pub const HeapPtr = *align(8) anyopaque; -/// Values for the lowest 4 bits of a heap pointer, indicating the heap type. +/// Values for the 8 type bits on main heap pointers. pub const HeapType = enum(u8) { + /// Pair (car, cdr) + pair, /// Array of various types: see `ArrayPtr`. array, + pub fn ObjType(self: HeapType) type { + return switch (self) { + .pair => pair.Pair, + .array => array.ArrayHeader, + else => @panic("Invalid HeapType."), + }; + } + pub fn PtrType(self: HeapType) type { return switch (self) { + .pair => pair.PairPtr, .array => array.ArrayPtr, else => @panic("Invalid HeapType."), }; } + + pub fn of(ptr: anytype) HeapType { + return switch (@TypeOf(ptr)) { + PairPtr => .pair, + ArrayHeader => .array, + else => @panic("Unknown heap pointer."), + }; + } }; fn hi16(comptime tag: u4) u16 { @@ -275,8 +295,8 @@ pub const Value = packed union { } /// Check for heap pointer (given type). - pub fn isHptrTyp(v: Value, comptime htype: HeapType) bool { - return v.hptr._hi == hi16_hptr and v.htptr.typ == htype; + pub fn isHptrTyp(v: Value, comptime typ: HeapType) bool { + return v.hptr._hi == hi16_hptr and v.hptr.typ == typ; } /// Check for istr pointer. diff --git a/src/zisp/value/array.zig b/src/zisp/value/array.zig index cdc5f75..88baf41 100644 --- a/src/zisp/value/array.zig +++ b/src/zisp/value/array.zig @@ -1,8 +1,6 @@ const builtin = @import("builtin"); const std = @import("std"); -const Alloc = std.mem.Allocator; - const gc = @import("../gc.zig"); const value = @import("../value.zig"); @@ -12,25 +10,24 @@ const Value = value.Value; /// /// The low 48 bits are either the length (element count, not buffer size) of /// the array contents that follow immediately, or a pointer to the header of -/// another array whose memory is shared with this one, or a null pointer that -/// has special meaning; see below. +/// another array whose memory is shared with this one, or null, which has a +/// special meaning; see below. /// /// NOTE: For strings, the length is in fact the size in bytes of the buffer. /// To get the "length" of a string according to other definitions of length, -/// such as count of Unicode Scalar Values, or count of Grapheme Clusters, +/// such as count of Unicode Scalar Values, count of UTF-16 code units, etc., /// different encoding-specific string APIs must be used. /// /// If this is a pointer (`is_ptr` is set) it means it's a re-interpretation of /// the contents of the array that is being pointed to. (But see below.) /// /// If this is a slice (`is_slice` is set) then two more u64 values follow this -/// one, marking the start and end of the slice of the pointed-to array that +/// one, marking the start and end byte offsets of the slice of the array that /// this one represents. (But see next paragraph.) /// /// If this is a pointer or slice, but the pointer value is null, then another -/// u64 follows this one immediately, and points directly to a memory buffer -/// (not array head) whose contents are used. In this case, if it's a slice, -/// the start and end u64 values come after that pointer instead. +/// u64 is found at the end, which is a direct pointer to a memory buffer (not +/// array head) whose contents are used. /// /// If this header encodes a non-slice, non-array, direct buffer pointer, then /// there is no length information, so the count of elements is unknown and @@ -48,7 +45,19 @@ const Value = value.Value; /// another array with the same buffer pointer and different type info. /// /// Other remaining bits provide information about element type and size. -pub const ArrayPtr = *align(@alignOf(value.Zptr)) ArrayHeader; +pub const ArrayPtr = *align(@alignOf(value.HeapPtr)) ArrayHeader; + +const ArrayType = enum(u2) { int, flt, val, str }; + +const Endian = enum(u1) { + little, + big, + + const native: Endian = switch (builtin.target.cpu.arch.endian()) { + .little => .little, + .big => .big, + }; +}; // Important: We may or may not use a hack one day in which an algorithm, like // for GC purposes, scans through certain memory regions looking for NaN-packed @@ -71,7 +80,7 @@ pub const ArrayHeader = packed struct(u64) { }, flt: packed struct(u12) { endian: Endian = .native, - _DONTUSE: bool = false + _DONTUSE: bool = false, size: u10, }, val: packed struct(u12) { @@ -98,26 +107,39 @@ pub const ArrayHeader = packed struct(u64) { return @ptrCast(self); } - fn bufContent(self: *Self) [*]u8 { + fn bufOfDirect(self: *Self) [*]u8 { std.debug.assert(!self.is_ptr); - return @ptrCast(self.bufU64() + 1); + return @ptrCast(&self.bufU64()[1]); } - fn bufPointer(self: *Self) [*]u8 { + fn bufOfPointer(self: *Self) [*]u8 { std.debug.assert(self.is_ptr); std.debug.assert(self.len_or_ptr == 0); return @ptrFromInt(self.bufU64()[1]); } + fn sliceInfo(self: *Self) [2]u64 { + std.debug.assert(self.is_slice); + const buf = self.bufU64(); + return .{ buf[1], buf[2] }; + } + + fn bufOfSlice(self: *Self) [*]u8 { + std.debug.assert(self.is_slice); + std.debug.assert(self.len_or_ptr == 0); + return @ptrFromInt(self.bufU64()[3]); + } + fn eltSize(self: *Self) u16 { std.debug.assert(!self.is_ptr); return switch (self.type) { .str => 1, + .val => 8, else => @panic("not implemented"), }; } - fn size(self: *Self) usize { + fn sizeInBytes(self: *Self) usize { std.debug.assert(!self.is_ptr); return self.len_or_ptr * self.eltSize(); } @@ -128,77 +150,76 @@ pub const ArrayHeader = packed struct(u64) { return if (p != 0) @ptrFromInt(p) else null; } - fn sliceInfo(self: *Self) [2]u64 { - std.debug.assert(self.is_slice); - const ptr = self.len_or_ptr; - const buf = self.bufU64(); - if (ptr != 0) { - return .{ buf[1], buf[2] }; - } else { - return .{ buf[2], buf[3] }; - } - } - - pub fn bufU8(self: *Self) [*]u8 { + /// Get a pointer to the array's contents as a u8 multi-pointer. + pub fn bufU8RW(self: *Self) [*]u8 { if (self.is_ptr) { - if (self.arrPointer()) |a| { - return a.bufContent(); + if (self.arrPointer()) |dest| { + std.debug.assert(!dest.is_ptr); + return dest.bufOfDirect(); + } else if (self.is_slice) { + return self.bufOfSlice(); } else { - return self.bufPointer(); + return self.bufOfPointer(); } - } else { - return self.bufContent(); } + return self.bufOfDirect(); + } + + /// Get a pointer to the array's contents as a const u8 multi-pointer. + pub fn bufU8RO(self: *Self) [*]const u8 { + return self.bufU8RW(); } - pub fn bytes(self: *Self) []u8 { + /// Get a u8 slice of the array's contents. + pub fn sliceU8RW(self: *Self) []u8 { if (self.is_slice) { - const buf = self.bufU8(); + std.debug.assert(self.is_ptr); const start, const end = self.sliceInfo(); + var buf = undefined; + if (self.arrPointer()) |dest| { + std.debug.assert(!dest.is_ptr); + std.debug.assert(end <= dest.sizeInBytes()); + buf = dest.bufOfDirect(); + } else { + buf = self.bufOfSlice(); + } return buf[start..end]; } var arr = self; if (self.is_ptr) { arr = self.arrPointer() orelse { - @panic("Called bytes() on array with direct buffer pointer."); + @panic("Array lacks length information; can't take slice."); }; } - return arr.bufContent()[0..arr.size()]; + return arr.bufContent()[0..arr.sizeInBytes()]; } - pub fn bytesRO(self: *Self) []const u8 { - return self.bytes(); + /// Get a const u8 slice of the array's contents. + pub fn sliceU8RO(self: *Self) []const u8 { + return self.sliceU8RW(); } }; -const ArrayType = enum(u2) { int, flt, val, str }; - -const Endian = enum(u1) { - little, - big, - - const native: Endian = switch (builtin.target.cpu.arch.endian()) { - .little => .little, - .big => .big, - }; -}; - -pub fn newString(alloc: Alloc, s: []const u8) !Value { +pub fn newString(s: []const u8) !Value { std.debug.assert(s.len <= std.math.maxInt(u48)); - const algn = std.mem.Alignment.of(ArrayPtr); - const size = @sizeOf(ArrayHeader) + s.len; - const arr: ArrayPtr = @ptrCast(try alloc.alignedAlloc(u8, algn, size)); + const len = @sizeOf(ArrayHeader) + s.len; + const arr = try gc.allocHeap(.array, len); arr.* = .{ .len_or_ptr = @intCast(s.len), .type = .str, .info = .{ .str = .{} }, }; - const buf = arr.bufContent(); + const buf = arr.bufOfDirect(); @memcpy(buf[0..s.len], s); - return value.ptr.pack(.array, arr); + return gc.packHeap(arr); +} + +pub fn checkAny(v: Value) ?ArrayPtr { + if (!v.isHptrTyp(.array)) return null; + return @ptrCast(gc.heapPtrFromIdx(v.hptr.idx)); } pub fn check(comptime t: ArrayType, v: Value) ?ArrayPtr { - if (v.getPtr(.array)) |p| if (p.type == t) return p; - return null; + const ptr = checkAny(v); + return if (ptr.type == t) ptr else null; } diff --git a/src/zisp/value/pair.zig b/src/zisp/value/pair.zig index 09e50f2..c4b6f2c 100644 --- a/src/zisp/value/pair.zig +++ b/src/zisp/value/pair.zig @@ -1,12 +1,13 @@ +const std = @import("std"); + const gc = @import("../gc.zig"); const value = @import("../value.zig"); -const ptr = @import("ptr.zig"); +const Alloc = std.mem.Allocator; -const PairPool = gc.PairPool; const Value = value.Value; -pub const PairPtr = *align(@alignOf(value.Zptr)) Pair; +pub const PairPtr = *align(@alignOf(value.HeapPtr)) Pair; pub const Pair = struct { car: Value, @@ -16,7 +17,8 @@ pub const Pair = struct { // Zig API pub fn check(v: Value) ?PairPtr { - return v.getPtr(.pair); + if (!v.isHptrTyp(.pair)) return null; + return @ptrCast(gc.heapPtrFromIdx(v.hptr.idx)); } pub fn assert(v: Value) PairPtr { @@ -30,20 +32,17 @@ pub fn unpack(v: Value) PairPtr { return assert(v); } -pub fn consInPool(pool: *PairPool, car: Value, cdr: Value) !Value { - const pair = try pool.cons(car, cdr); - return ptr.pack(.pair, pair); -} - // Zisp API pub fn pred(v: Value) Value { return value.boole.pack(check(v) != null); } -pub fn cons(car: Value, cdr: Value) Value { - const pool = gc.mainPairPool(); - return consInPool(pool, car, cdr) catch @panic("OOM"); // TODO +pub fn cons(car: Value, cdr: Value) !Value { + const pair = try gc.createHeap(.pair); + pair.car = car; + pair.cdr = cdr; + return gc.packHeap(pair); } pub fn getCar(v: Value) Value { |