.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
mem/
heap/
heap.rad
5.8 KiB
tests.rad
6.2 KiB
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/mem/heap.rad
raw
| 1 | //! Heaps for growable slices. |
| 2 | //! |
| 3 | //! The compiler knows these declarations by name. A `Heap` is a region that slices grow in. It is |
| 4 | //! a static, a Page that the kernel turned into a heap, or, in hosted code, storage that [`over`] |
| 5 | //! took. An `Allocator` is the view of a heap for plain elements: |
| 6 | //! |
| 7 | //! static POOL: mem::heap::Heap = mem::heap::new(65536); |
| 8 | //! try xs.append(1, &POOL); |
| 9 | //! |
| 10 | //! The size of a static heap in a verified package is limited like any layout, by the loader's |
| 11 | //! limit on layout sizes. Memory that a heap hands out is not the memory of a Page, so a call |
| 12 | //! cannot take it as a buffer unless the plain slice is in a static heap, which is data of the |
| 13 | //! package. |
| 14 | @test mod tests; |
| 15 | |
| 16 | /// Size of the header of a heap: four words. The first holds the bytes handed out, the second |
| 17 | /// the size of the pool in bytes, the third the address of the pool. The fourth is zero, except |
| 18 | /// in a heap made by [`over`], where it holds a mutable pointer to the first. A heap made by |
| 19 | /// a constant initializer or by the kernel from a Page has this header too. Its pool follows |
| 20 | /// the header or has another symbol. |
| 21 | export constant HEADER_SIZE: u32 = 32; |
| 22 | /// Alignment of the pool of a heap, which is the largest alignment of an element. |
| 23 | export constant POOL_ALIGNMENT: u32 = 16; |
| 24 | |
| 25 | /// A region of memory for growable slices. It holds elements of any type and is |
| 26 | /// never reset. |
| 27 | @language export record Heap {} |
| 28 | |
| 29 | /// Allocate a heap with `size` bytes of backing storage during compilation. |
| 30 | /// The size must be positive. The call must be in a top-level static or |
| 31 | /// constant initializer. |
| 32 | @intrinsic export constant fn new(size: u32) -> Heap; |
| 33 | |
| 34 | /// The view of a heap for plain elements, which holds no pointers. |
| 35 | @language export record Allocator {} |
| 36 | |
| 37 | /// Number of bytes from the start of `bytes` to the first 16-byte boundary, where a heap puts its |
| 38 | /// header. Only the address is read, and it does not leave this function. |
| 39 | fn skewOf(bytes: &[u8]) -> u32 { |
| 40 | unsafe { |
| 41 | let address = bytes.ptr as u64; |
| 42 | return ((POOL_ALIGNMENT as u64 - address % POOL_ALIGNMENT as u64) |
| 43 | % POOL_ALIGNMENT as u64) as u32; |
| 44 | } |
| 45 | } |
| 46 | |
| 47 | /// Make a heap that carves from `bytes`, which it takes: nothing else can reach them. |
| 48 | /// |
| 49 | /// The header of the heap is in the first bytes, at a 16-byte boundary, and the pool follows it. |
| 50 | /// A fourth word of the header holds a mutable pointer to the first word, which is how the unsafe |
| 51 | /// functions of this module move the offset through a shared handle. The caller supplies storage |
| 52 | /// large enough for the header, so a smaller slice is a program error. The heap hands out each |
| 53 | /// byte once, except after the unsafe [`rewind`]. |
| 54 | /// |
| 55 | /// Safety argument: the owned slice is consumed, and the ownership checker refuses any later use of |
| 56 | /// it, so the returned pointer is the only way to the storage. The header is written before the |
| 57 | /// pointer is returned. The function casts pointers, so verified code cannot call it: a package |
| 58 | /// that calls into std fails verification. Hosted code is not verified, and may build a heap over |
| 59 | /// storage that it wrote before. |
| 60 | export fn over(bytes: *mut [u8]) -> *Heap { |
| 61 | let skew = skewOf(&bytes[..]); |
| 62 | assert bytes.len >= skew + HEADER_SIZE; |
| 63 | unsafe { |
| 64 | let start: *mut u8 = &mut bytes[skew]; |
| 65 | let raw: *unsafe mut u8 = &mut *start; |
| 66 | let erased = raw as *unsafe mut opaque; |
| 67 | let header = @sliceOf(erased as *unsafe mut u64, 3); |
| 68 | let alias = @sliceOf(erased as *unsafe mut *unsafe mut u64, 4); |
| 69 | set header[0] = 0; |
| 70 | set header[1] = (bytes.len - skew - HEADER_SIZE) as u64; |
| 71 | set header[2] = raw as u64 + HEADER_SIZE as u64; |
| 72 | set alias[3] = erased as *unsafe mut u64; |
| 73 | let owner: *mut opaque = start; |
| 74 | return owner as *Heap; |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | /// Make a heap like [`over`] whose pool has exactly `capacity` bytes, which lets a test try every |
| 79 | /// size. The slice must hold the header, the skew to the first 16-byte boundary, and the pool. |
| 80 | export fn withCapacity(bytes: *mut [u8], capacity: u32) -> *Heap { |
| 81 | let skew = skewOf(&bytes[..]); |
| 82 | let total = skew + HEADER_SIZE + capacity; |
| 83 | assert bytes.len >= total; |
| 84 | return over(&mut bytes[.. total]); |
| 85 | } |
| 86 | |
| 87 | /// The header of a heap, as words. |
| 88 | unsafe fn words(heap: &Heap) -> *unsafe [u64] { |
| 89 | return @sliceOf(heap as &opaque as *unsafe opaque as *unsafe u64, 4); |
| 90 | } |
| 91 | |
| 92 | /// The word that holds the offset of a heap made by [`over`], through the pointer that it kept. |
| 93 | /// Any other heap has a zero in that place, and is a program error here. |
| 94 | unsafe fn offset(heap: &Heap) -> *unsafe mut [u64] { |
| 95 | let aliases = @sliceOf(heap as &opaque as *unsafe opaque as *unsafe *unsafe mut u64, 4); |
| 96 | assert aliases[3] as u64 <> 0, "heap: not made by over"; |
| 97 | return @sliceOf(aliases[3], 1); |
| 98 | } |
| 99 | |
| 100 | /// Number of bytes that the heap has handed out, including padding. The size of a pool is below |
| 101 | /// 4 GiB, because a slice has a 32-bit length. |
| 102 | export fn used(heap: &Heap) -> u32 { |
| 103 | unsafe { |
| 104 | return words(heap)[0] as u32; |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | /// Number of bytes that the heap can still hand out. |
| 109 | export fn remaining(heap: &Heap) -> u32 { |
| 110 | unsafe { |
| 111 | let header = words(heap); |
| 112 | return (header[1] - header[0]) as u32; |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | /// The state of the heap, for [`rewind`]. |
| 117 | export fn mark(heap: &Heap) -> u32 { |
| 118 | return used(heap); |
| 119 | } |
| 120 | |
| 121 | /// Return a heap made by [`over`] to the state of an earlier [`mark`], so that it hands out the |
| 122 | /// same memory again. |
| 123 | /// |
| 124 | /// Caller obligation: `state` comes from [`mark`] of this heap, and no pointer or slice into |
| 125 | /// memory that the heap handed out since that mark is used afterward. |
| 126 | export unsafe fn rewind(heap: &Heap, state: u32) { |
| 127 | set offset(heap)[0] = state as u64; |
| 128 | } |
| 129 | |
| 130 | /// Return a heap made by [`over`] to its empty state. The caller obligations of [`rewind`] hold |
| 131 | /// for all the memory the heap handed out. |
| 132 | export unsafe fn reset(heap: &Heap) { |
| 133 | rewind(heap, 0); |
| 134 | } |