blots 0.20.1

A small, simple, expression-oriented programming language.
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
//! The allocator of the `blots` binary: pools for small blocks, the system allocator for the
//! rest, plus a hint for large blocks.
//!
//! An interpreter allocates small blocks at a furious rate (the nodes of a syntax tree, the
//! code of a statement, every list, string and closure a program creates) and gives most of
//! them back almost at once. A general-purpose allocator spends a few hundred instructions on
//! each round trip once its shortcuts overflow, which is more than the interpreter spends on
//! whatever it wanted the block for. So blocks of up to [`pool::MAX_SIZE`] bytes are served
//! from per-thread free lists, one for each size, where taking or returning a block is a
//! handful of instructions. See [`pool`] for what that costs.
//!
//! A program that builds a list of a few million elements writes to tens of megabytes of
//! memory the process has never touched, and with 4 KiB pages the kernel is asked for every
//! one of them separately; those page faults can take longer than computing the elements. On
//! Linux, blocks that are large enough are therefore marked as candidates for transparent
//! huge pages, which are faulted in 2 MiB at a time. (Where the system's huge page policy is
//! "always" that happens anyway; the more common "madvise" policy leaves it to programs to
//! ask.)

use std::alloc::{GlobalAlloc, Layout, System};
use std::ptr;

pub struct Allocator;

// SAFETY: a block comes either from a pool or from the system allocator, and which of the two
// is a function of its layout alone, so every block goes back to where it came from. Pooled
// blocks are aligned to `pool::GRANULE`, which is all a pooled layout may ask for. The hint
// does not alter the content or the validity of a block.
unsafe impl GlobalAlloc for Allocator {
    #[inline]
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        if pool::takes(layout.size(), layout.align()) {
            return pool::alloc(layout.size());
        }

        // SAFETY: the caller upholds the contract of `GlobalAlloc::alloc`.
        let block = unsafe { System.alloc(layout) };
        huge_pages::suggest(block, layout.size());

        block
    }

    #[inline]
    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
        if pool::takes(layout.size(), layout.align()) {
            let block = pool::alloc(layout.size());
            if !block.is_null() {
                // SAFETY: the block is at least as long as the layout.
                unsafe { ptr::write_bytes(block, 0, layout.size()) };
            }

            return block;
        }

        // SAFETY: the caller upholds the contract of `GlobalAlloc::alloc_zeroed`.
        let block = unsafe { System.alloc_zeroed(layout) };
        huge_pages::suggest(block, layout.size());

        block
    }

    #[inline]
    unsafe fn dealloc(&self, block: *mut u8, layout: Layout) {
        if pool::takes(layout.size(), layout.align()) {
            // SAFETY: a block of a layout the pools take came from them.
            return unsafe { pool::dealloc(block, layout.size()) };
        }

        // SAFETY: the caller upholds the contract of `GlobalAlloc::dealloc`.
        unsafe { System.dealloc(block, layout) }
    }

    #[inline]
    unsafe fn realloc(&self, block: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
        let was_pooled = pool::takes(layout.size(), layout.align());
        let is_pooled = pool::takes(new_size, layout.align());

        if !was_pooled && !is_pooled {
            // SAFETY: the caller upholds the contract of `GlobalAlloc::realloc`.
            let block = unsafe { System.realloc(block, layout, new_size) };
            huge_pages::suggest(block, new_size);

            return block;
        }

        if was_pooled && is_pooled && pool::same_block(layout.size(), new_size) {
            return block;
        }

        let Ok(new_layout) = Layout::from_size_align(new_size, layout.align()) else {
            return ptr::null_mut();
        };

        // SAFETY: the new layout has a non-zero size, since the caller passes one; the two
        // blocks are distinct, and each is at least as long as the smaller of the two sizes.
        unsafe {
            let new_block = self.alloc(new_layout);
            if !new_block.is_null() {
                ptr::copy_nonoverlapping(block, new_block, layout.size().min(new_size));
                self.dealloc(block, layout);
            }

            new_block
        }
    }
}

/// Free lists of small blocks.
///
/// Every size that is a multiple of [`GRANULE`] up to [`MAX_SIZE`] has a list of its own. A
/// block that is given back goes to the front of the list of its size and is the first to be
/// handed out again; when a list is empty, a block is cut from a chunk obtained from the
/// system allocator. Blocks carry no header: Rust says how large a block is when it returns
/// it.
///
/// The simplicity has a price. A block never changes size, and chunks are never returned to
/// the system, so memory freed at one size cannot serve requests of another: a program that
/// frees a great many small blocks of one size and then allocates as many of a different size
/// uses the sum of the two. Blocks above [`MAX_SIZE`], which is where most of the memory of
/// such a program would be, are not affected.
///
/// Each thread has its own lists, which is what makes them cheap. A block may be returned on
/// another thread than the one it was allocated on; it then joins that thread's lists. The
/// lists of a thread that ends are not reclaimed.
mod pool {
    use super::huge_pages;
    use std::alloc::{GlobalAlloc, Layout, System};
    use std::cell::Cell;
    use std::ptr;

    /// Block sizes are multiples of this, and blocks are aligned to it.
    pub const GRANULE: usize = 16;

    /// The largest block that comes from the pools.
    pub const MAX_SIZE: usize = 512;

    const CLASSES: usize = MAX_SIZE / GRANULE;

    /// The size of the first chunk a thread gets from the system; each one after it is twice
    /// as large as the one before, up to [`MAX_CHUNK`]. Pages of a chunk that are never
    /// written to are never backed by memory.
    const FIRST_CHUNK: usize = 64 << 10;

    const MAX_CHUNK: usize = 4 << 20;

    struct Pools {
        /// For each size class, the block that was freed last. The first word of a free block
        /// holds the address of the one freed before it.
        free: [Cell<*mut u8>; CLASSES],

        /// The part of the current chunk that has not been handed out.
        fresh: Cell<*mut u8>,
        fresh_end: Cell<*mut u8>,

        next_chunk: Cell<usize>,
    }

    thread_local! {
        // A constant initialiser and nothing to drop: reaching the pools takes no check and
        // never allocates, on the targets with native thread-locals that `build.rs` allows.
        static POOLS: Pools = const {
            Pools {
                free: [const { Cell::new(ptr::null_mut()) }; CLASSES],
                fresh: Cell::new(ptr::null_mut()),
                fresh_end: Cell::new(ptr::null_mut()),
                next_chunk: Cell::new(FIRST_CHUNK),
            }
        };
    }

    /// The size class of blocks that hold `size` bytes. A size of zero has none: its class is
    /// out of range.
    #[inline(always)]
    fn class(size: usize) -> usize {
        size.wrapping_sub(1) / GRANULE
    }

    /// Whether blocks of this layout come from the pools.
    #[inline(always)]
    pub fn takes(size: usize, align: usize) -> bool {
        class(size) < CLASSES && align <= GRANULE
    }

    /// Whether a block that holds `size` bytes is exactly as long as one that holds
    /// `other_size`.
    #[inline(always)]
    pub fn same_block(size: usize, other_size: usize) -> bool {
        class(size) == class(other_size)
    }

    /// A block that holds `size` bytes and is aligned to a granule, or null if there is none
    /// to be had (or the pools do not take that size).
    #[inline(always)]
    pub fn alloc(size: usize) -> *mut u8 {
        POOLS.with(|pools| {
            let class = class(size);
            let Some(head) = pools.free.get(class) else {
                return ptr::null_mut();
            };

            let block = head.get();
            if !block.is_null() {
                // SAFETY: a free block holds the address of the one freed before it (or null).
                head.set(unsafe { block.cast::<*mut u8>().read() });

                return block;
            }

            pools.cut((class + 1) * GRANULE)
        })
    }

    /// # Safety
    /// `block` must have come from [`alloc`] with a size of the same class as `size`, and
    /// must not be used again. It may be returned on another thread than the one it came
    /// from because chunks are never given back to the system.
    #[inline(always)]
    pub unsafe fn dealloc(block: *mut u8, size: usize) {
        POOLS.with(|pools| {
            let Some(head) = pools.free.get(class(size)) else {
                return;
            };

            // SAFETY: the block is at least a granule long and aligned to one, so there is
            // room for an address in it, and nothing else uses it any more.
            unsafe { block.cast::<*mut u8>().write(head.get()) };
            head.set(block);
        })
    }

    impl Pools {
        /// Cut a block of `bytes` bytes, a multiple of the granule, from the current chunk.
        #[inline(always)]
        fn cut(&self, bytes: usize) -> *mut u8 {
            let block = self.fresh.get();
            if (self.fresh_end.get() as usize) - (block as usize) < bytes {
                return self.cut_from_new_chunk(bytes);
            }

            self.fresh.set(block.wrapping_add(bytes));

            block
        }

        #[cold]
        #[inline(never)]
        fn cut_from_new_chunk(&self, bytes: usize) -> *mut u8 {
            let size = self.next_chunk.get();
            if bytes > size {
                return ptr::null_mut();
            }

            let Ok(layout) = Layout::from_size_align(size, GRANULE) else {
                return ptr::null_mut();
            };

            // SAFETY: a chunk is at least `FIRST_CHUNK` bytes long.
            let chunk = unsafe { System.alloc(layout) };
            if chunk.is_null() {
                return chunk;
            }

            huge_pages::suggest(chunk, size);

            // What is left of the old chunk is too short for this block, but it is a whole
            // number of granules: a block of a smaller size, unless it is empty.
            let rest = self.fresh.get();
            let rest_size = (self.fresh_end.get() as usize) - (rest as usize);
            if let Some(head) = self.free.get(class(rest_size)) {
                // SAFETY: the rest of the chunk is unused, at least a granule long and aligned
                // to one.
                unsafe { rest.cast::<*mut u8>().write(head.get()) };
                head.set(rest);
            }

            self.next_chunk.set((size * 2).min(MAX_CHUNK));
            self.fresh.set(chunk.wrapping_add(bytes));
            self.fresh_end.set(chunk.wrapping_add(size));

            chunk
        }
    }
}

#[cfg(target_os = "linux")]
mod huge_pages {
    use std::ffi::c_void;
    use std::sync::atomic::{AtomicUsize, Ordering};

    /// The size of a transparent huge page on the common configurations; smaller blocks
    /// cannot contain one.
    const HUGE_PAGE: usize = 2 << 20;

    /// The page size of the system, once it has been asked for.
    static PAGE_SIZE: AtomicUsize = AtomicUsize::new(0);

    /// Tell the kernel that the memory of a freshly allocated block may be backed by huge
    /// pages, if the block is large enough for that to matter.
    #[inline]
    pub fn suggest(block: *mut u8, size: usize) {
        if size >= HUGE_PAGE && !block.is_null() {
            suggest_range(block, size);
        }
    }

    #[cold]
    fn suggest_range(block: *mut u8, size: usize) {
        let page_size = match PAGE_SIZE.load(Ordering::Relaxed) {
            0 => {
                // SAFETY: `sysconf` only reads its argument.
                let page_size =
                    usize::try_from(unsafe { libc::sysconf(libc::_SC_PAGESIZE) }).unwrap_or(0);
                if !page_size.is_power_of_two() {
                    return;
                }

                PAGE_SIZE.store(page_size, Ordering::Relaxed);
                page_size
            }
            page_size => page_size,
        };

        // The hint covers every page the block touches. A block this large has its pages
        // (almost) to itself, and a hint that also reaches a neighbour does no harm.
        let start = block as usize & !(page_size - 1);
        let Some(end) = (block as usize)
            .checked_add(size)
            .and_then(|end| end.checked_next_multiple_of(page_size))
        else {
            return;
        };

        // SAFETY: the advice changes how the kernel backs the pages, not what they hold. It
        // is only a hint: failure (for instance on a kernel without huge page support)
        // leaves everything as it was.
        unsafe { libc::madvise(start as *mut c_void, end - start, libc::MADV_HUGEPAGE) };
    }
}

#[cfg(not(target_os = "linux"))]
mod huge_pages {
    #[inline]
    pub fn suggest(_block: *mut u8, _size: usize) {}
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A small deterministic generator, so the tests need no dependency and no seed.
    struct Random(u64);

    impl Random {
        fn next(&mut self) -> u64 {
            self.0 ^= self.0 << 13;
            self.0 ^= self.0 >> 7;
            self.0 ^= self.0 << 17;

            self.0
        }

        fn below(&mut self, bound: usize) -> usize {
            (self.next() % bound as u64) as usize
        }

        /// A size that is usually small and often right at the edge of a size class.
        fn size(&mut self) -> usize {
            match self.below(8) {
                0 => 1 + self.below(4096),
                1 => pool::GRANULE * (1 + self.below(40)),
                2 => pool::GRANULE * (1 + self.below(40)) + 1,
                3 => pool::MAX_SIZE - 1 + self.below(3),
                _ => 1 + self.below(600),
            }
        }
    }

    /// A live block and the byte each of its positions should hold.
    struct Block {
        start: *mut u8,
        layout: Layout,
        seed: u8,
    }

    impl Block {
        fn expected(&self, position: usize) -> u8 {
            self.seed.wrapping_add(position as u8).wrapping_mul(31)
        }

        fn fill(&self, from: usize) {
            for position in from..self.layout.size() {
                // SAFETY: the position lies within the block.
                unsafe { self.start.add(position).write(self.expected(position)) };
            }
        }

        fn check(&self, len: usize) {
            for position in 0..len {
                // SAFETY: the position lies within the block.
                let byte = unsafe { self.start.add(position).read() };
                assert_eq!(
                    byte,
                    self.expected(position),
                    "byte {} of a block",
                    position
                );
            }
        }
    }

    /// Allocate, resize and free blocks at random, checking that each one keeps its content
    /// (and so shares no memory with any other) and is aligned as asked.
    fn churn(seed: u64, rounds: usize) {
        let mut random = Random(seed);
        let mut blocks: Vec<Block> = Vec::new();

        for round in 0..rounds {
            match random.below(if blocks.len() > 400 { 6 } else { 4 }) {
                0 | 1 => {
                    let align = 1 << random.below(7);
                    let layout = Layout::from_size_align(random.size(), align).unwrap();
                    let zeroed = random.below(4) == 0;

                    // SAFETY: the layout has a non-zero size.
                    let start = unsafe {
                        if zeroed {
                            Allocator.alloc_zeroed(layout)
                        } else {
                            Allocator.alloc(layout)
                        }
                    };
                    assert!(!start.is_null());
                    assert_eq!(start as usize % align, 0);

                    if zeroed {
                        for position in 0..layout.size() {
                            // SAFETY: the position lies within the block.
                            assert_eq!(unsafe { start.add(position).read() }, 0);
                        }
                    }

                    let block = Block {
                        start,
                        layout,
                        seed: round as u8,
                    };
                    block.fill(0);
                    blocks.push(block);
                }
                2 if !blocks.is_empty() => {
                    let index = random.below(blocks.len());
                    let block = &mut blocks[index];
                    let old_size = block.layout.size();
                    let new_size = random.size();

                    // SAFETY: the block is live and was allocated with this layout.
                    let start = unsafe { Allocator.realloc(block.start, block.layout, new_size) };
                    assert!(!start.is_null());
                    assert_eq!(start as usize % block.layout.align(), 0);

                    block.start = start;
                    block.layout = Layout::from_size_align(new_size, block.layout.align()).unwrap();
                    block.check(old_size.min(new_size));
                    block.fill(old_size.min(new_size));
                }
                _ if !blocks.is_empty() => {
                    let block = blocks.swap_remove(random.below(blocks.len()));
                    block.check(block.layout.size());

                    // SAFETY: the block is live and was allocated with this layout.
                    unsafe { Allocator.dealloc(block.start, block.layout) };
                }
                _ => {}
            }
        }

        for block in blocks {
            block.check(block.layout.size());

            // SAFETY: the block is live and was allocated with this layout.
            unsafe { Allocator.dealloc(block.start, block.layout) };
        }
    }

    #[test]
    fn blocks_keep_their_content() {
        churn(0x9E37_79B9_7F4A_7C15, 200_000);
    }

    #[test]
    fn threads_have_pools_of_their_own() {
        let threads: Vec<_> = (1..=4u64)
            .map(|thread| std::thread::spawn(move || churn(thread * 0x2545_F491_4F6C_DD1D, 50_000)))
            .collect();

        for thread in threads {
            thread.join().unwrap();
        }
    }

    #[test]
    fn a_block_may_be_freed_on_another_thread() {
        let boxes: Vec<Box<[u64; 5]>> = (0..10_000).map(|value| Box::new([value; 5])).collect();

        let sum = std::thread::spawn(move || boxes.iter().map(|values| values[4]).sum::<u64>())
            .join()
            .unwrap();
        assert_eq!(sum, 9_999 * 10_000 / 2);

        // Blocks of that size are still to be had here, and are distinct.
        let again: Vec<Box<[u64; 5]>> = (0..10_000).map(|value| Box::new([value; 5])).collect();
        assert!(
            again
                .iter()
                .enumerate()
                .all(|(value, values)| values[0] == value as u64)
        );
    }

    #[test]
    fn a_freed_block_is_the_next_of_its_size() {
        let layout = Layout::from_size_align(40, 8).unwrap();

        // SAFETY: the layout has a non-zero size, and each block is freed once, with it.
        unsafe {
            let first = Allocator.alloc(layout);
            let second = Allocator.alloc(layout);
            assert_ne!(first, second);

            Allocator.dealloc(first, layout);
            assert_eq!(
                Allocator.alloc(Layout::from_size_align(33, 1).unwrap()),
                first
            );

            Allocator.dealloc(first, layout);
            Allocator.dealloc(second, layout);
        }
    }

    #[test]
    fn growing_within_a_block_does_not_move_it() {
        let layout = Layout::from_size_align(17, 1).unwrap();

        // SAFETY: the layout has a non-zero size; the block is resized and freed with the
        // layout it has at the time.
        unsafe {
            let block = Allocator.alloc(layout);
            assert_eq!(Allocator.realloc(block, layout, 32), block);

            let grown = Layout::from_size_align(32, 1).unwrap();
            let moved = Allocator.realloc(block, grown, 33);
            assert_ne!(moved, block);

            Allocator.dealloc(moved, Layout::from_size_align(33, 1).unwrap());
        }
    }
}