sandpit 0.5.2

A concurrent garbage collected arena
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

use super::trace::Trace;
use crate::header::{GcHeader, SizedHeader, SliceHeader, StrHeader};

use alloc::alloc::Layout;
use core::marker::PhantomData;
use core::ptr::{slice_from_raw_parts, NonNull};

// Gc pointer types are capable of pointing to [T]. However, you can not
// have an AtomicPtr<T> where T: ?Sized b/c atomic operations can only operate
// on the word size of the machine, which is smaller than the size of a fat pointer.
//
// So in order to support the atomic operations on a pointer to [T],
// you can hold a `*const Thin<[T]>` (which is a thin pointer).
// However, due to being a thin pointer, the length of the [T] must be stored
// somewhere else. So the length of a Gc<[T]> is stored in the header to the [T].
pub struct Thin<T: ?Sized> {
    kind: PhantomData<T>,
}

// The two basic kinds of GcPointee's are T and [T] where T: Sized.
// Due to the usage of thin pointers, the length of [T], needs
// to be stored in the header.
pub trait GcPointee {
    type GcHeader: GcHeader;

    fn as_fat<'a>(thin_ptr: NonNull<Thin<Self>>) -> *const Self;
    fn deref<'a>(thin_ptr: NonNull<Thin<Self>>) -> &'a Self {
        let fat_ptr = Self::as_fat(thin_ptr);
        debug_assert!(!fat_ptr.is_null(), "Attempting to dereference null pointer");
        unsafe { &*fat_ptr }
    }
    fn get_header<'a>(thin_ptr: NonNull<Thin<Self>>) -> &'a Self::GcHeader {
        unsafe { &*Self::get_header_ptr(thin_ptr) }
    }
    fn get_header_ptr(thin_ptr: NonNull<Thin<Self>>) -> *const Self::GcHeader;
}

impl<T: Trace> GcPointee for T {
    type GcHeader = SizedHeader<T>;

    fn as_fat<'a>(thin_ptr: NonNull<Thin<Self>>) -> *const Self {
        let ptr = thin_ptr.cast().as_ptr();
        debug_assert!(
            ptr as usize % core::mem::align_of::<T>() == 0,
            "Pointer {:p} is not aligned to {} bytes (required for type {})",
            ptr,
            core::mem::align_of::<T>(),
            core::any::type_name::<T>()
        );
        ptr
    }

    fn get_header_ptr(thin_ptr: NonNull<Thin<Self>>) -> *const Self::GcHeader {
        let (_, item_offset) = sized_alloc_layout::<T>();

        let header_ptr =
            unsafe { thin_ptr.as_ptr().byte_sub(item_offset) as *const Self::GcHeader };
        debug_assert!(
            header_ptr as usize % core::mem::align_of::<Self::GcHeader>() == 0,
            "Header pointer {:p} is not aligned to {} bytes (required for SizedHeader<{}>)",
            header_ptr,
            core::mem::align_of::<Self::GcHeader>(),
            core::any::type_name::<T>()
        );
        header_ptr
    }
}

impl<T: Trace> GcPointee for [T] {
    type GcHeader = SliceHeader<T>;

    fn as_fat<'a>(thin_ptr: NonNull<Thin<Self>>) -> *const Self {
        let slice_ptr: *const T = thin_ptr.cast().as_ptr();
        debug_assert!(
            slice_ptr as usize % core::mem::align_of::<T>() == 0,
            "Slice pointer {:p} is not aligned to {} bytes (required for [{}])",
            slice_ptr,
            core::mem::align_of::<T>(),
            core::any::type_name::<T>()
        );

        let header: &SliceHeader<T> = Self::get_header(thin_ptr);
        let len = header.len();

        slice_from_raw_parts(slice_ptr, len)
    }

    fn get_header_ptr(thin_ptr: NonNull<Thin<Self>>) -> *const Self::GcHeader {
        // we can just pretend the array has a length of 1 here, doesn't effect the offset
        let (_, item_offset) = slice_alloc_layout::<T>(1);

        let ptr: *mut Self::GcHeader = thin_ptr.cast().as_ptr();
        let header_ptr = unsafe { ptr.byte_sub(item_offset) as *const Self::GcHeader };

        debug_assert!(
            header_ptr as usize % core::mem::align_of::<Self::GcHeader>() == 0,
            "Header pointer {:p} is not aligned to {} bytes (required for SliceHeader<{}>)",
            header_ptr,
            core::mem::align_of::<Self::GcHeader>(),
            core::any::type_name::<T>()
        );
        header_ptr
    }
}

impl GcPointee for str {
    type GcHeader = StrHeader;

    fn as_fat<'a>(thin_ptr: NonNull<Thin<Self>>) -> *const Self {
        let str_ptr: *const u8 = thin_ptr.cast().as_ptr();
        debug_assert!(
            str_ptr as usize % core::mem::align_of::<u8>() == 0,
            "Str pointer {:p} is not aligned to {} bytes",
            str_ptr,
            core::mem::align_of::<u8>()
        );

        let header: &StrHeader = Self::get_header(thin_ptr);
        let len = header.len();

        let byte_slice = slice_from_raw_parts(str_ptr, len);
        byte_slice as *const [u8] as *const str
    }

    fn get_header_ptr(thin_ptr: NonNull<Thin<Self>>) -> *const Self::GcHeader {
        // we can just pretend the str has a length of 1 here, doesn't affect the offset
        let (_, item_offset) = str_alloc_layout(1);

        let ptr: *mut Self::GcHeader = thin_ptr.cast().as_ptr();
        let header_ptr = unsafe { ptr.byte_sub(item_offset) as *const Self::GcHeader };

        debug_assert!(
            header_ptr as usize % core::mem::align_of::<Self::GcHeader>() == 0,
            "Header pointer {:p} is not aligned to {} bytes (required for StrHeader)",
            header_ptr,
            core::mem::align_of::<Self::GcHeader>()
        );
        header_ptr
    }
}

pub fn sized_alloc_layout<T>() -> (Layout, usize) {
    let header_layout = Layout::new::<SizedHeader<T>>();
    let val_layout = Layout::new::<T>();
    let (unpadded_layout, offset) = header_layout.extend(val_layout).unwrap();
    let layout = unpadded_layout.pad_to_align();

    (layout, offset)
}

pub fn slice_alloc_layout<T>(len: usize) -> (Layout, usize) {
    let header_layout = Layout::new::<SliceHeader<T>>();
    let slice_layout = Layout::array::<T>(len).unwrap();
    let (unpadded_layout, offset) = header_layout.extend(slice_layout).unwrap();
    let layout = unpadded_layout.pad_to_align();

    (layout, offset)
}

pub fn str_alloc_layout(len: usize) -> (Layout, usize) {
    let header_layout = Layout::new::<StrHeader>();
    let str_layout = Layout::array::<u8>(len).unwrap();
    let (unpadded_layout, offset) = header_layout.extend(str_layout).unwrap();
    let layout = unpadded_layout.pad_to_align();

    (layout, offset)
}