lib/std/mem/heap.rad 5.8 KiB 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
}