bstack_raii 0.1.0

Typed, RAII-style ownership and lifetime layer over the bstack allocation primitives
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
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
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
//! Shared on-disk plumbing for the stdlib collections.
//!
//! These helpers are the common core the pointer-based containers
//! ([`crate::BStackLinkedList`], [`crate::stdlib::BStackDeque`]) build their
//! atomic mutators on: a `u64` field read, a whole-image block allocation, and
//! the [`atomic_update`] read-modify-write generator.

use core::cell::Cell;
use std::io;

use crate::BStackRaiiAllocator;
use bstack::{BStack, BStackGenOp, BStackRange};

use super::hash::fnv1a;
use crate::io_core::dealloc_range;
use crate::primitives::checked_off_mul;
use crate::types::compiled::HEADER_SIZE;
use crate::util::{SmallBuf, get_u64, io_error, read_u64};

/// Build a `(offset, value)` write-tuple for a `u64` field: little-endian into
/// an inline [`SmallBuf::Buf8`], no allocation. Replaces the repeated
/// `(off, val.to_le_bytes().to_vec())` shape.
pub(super) fn w8(off: u64, val: u64) -> (u64, SmallBuf) {
    (off, SmallBuf::Buf8(val.to_le_bytes()))
}

/// A `Vec<(u64, SmallBuf)>` substitute for [`atomic_update`] `plan` closures
/// whose write count is a small compile-time constant (metadata bumps, a
/// single slot write) — the array sits on the stack, so building the batch
/// takes no heap allocation. `push` panics past `N`; callers size `N` to the
/// closure's exact, statically-known maximum. Not for batches whose size
/// depends on runtime data (e.g. copying every live element on a resize) —
/// those still need `Vec`.
pub(super) struct WriteBuf<const N: usize> {
    buf: [(u64, SmallBuf); N],
    len: usize,
}

impl<const N: usize> WriteBuf<N> {
    pub(super) fn new() -> Self {
        Self {
            buf: core::array::from_fn(|_| (0, SmallBuf::Buf8([0; 8]))),
            len: 0,
        }
    }
    pub(super) fn push(&mut self, item: (u64, SmallBuf)) {
        self.buf[self.len] = item;
        self.len += 1;
    }
    pub(super) fn len(&self) -> usize {
        self.len
    }
    pub(super) fn as_slice(&self) -> &[(u64, SmallBuf)] {
        &self.buf[..self.len]
    }
}

/// Read `N` **contiguous** little-endian `u64` fields starting at `off` in a
/// *single* I/O call, returning them as an array. Use this instead of several
/// [`read_u64`] calls when the fields are adjacent (e.g. a handle's metadata) —
/// one `get_into` is one lock/seek/read, not `N`.
pub(super) fn read_fields<const N: usize>(stack: &BStack, off: u64) -> io::Result<[u64; N]> {
    debug_assert!(N <= 8, "read_fields: at most 8 u64 fields");
    let buf = &mut [0u8; 64][..N * 8];
    stack.get_into(off, buf)?;
    let mut out = [0u64; N];
    // `chunks_exact_to_as_chunks` is a newer clippy lint; also allow `unknown_lints`
    // so an older clippy (e.g. in CI) doesn't error on the name it doesn't know.
    #[allow(unknown_lints, clippy::chunks_exact_to_as_chunks)]
    for (dst, chunk) in out.iter_mut().zip(buf.chunks_exact(8)) {
        *dst = get_u64(chunk);
    }
    Ok(out)
}

/// Inline capacity of a [`Scratch`] buffer. Sized to hold a B-tree node (or a
/// map bucket / key) for any reasonably-small `Pod` key entirely on the stack;
/// unusually large keys spill to the heap. A `BStackBTreeMap` node with minimum
/// degree 8 is `280 + 15 * size_of::<K>()` bytes, so this covers keys up to
/// ~49 bytes without a heap allocation.
const SCRATCH_INLINE: usize = 1024;

/// A reusable read buffer whose storage is **inline (stack)** for the common
/// small case and spills to the heap only when a requested length exceeds
/// [`SCRATCH_INLINE`].
///
/// This lets the hot lookup paths (`get`) read a whole node/bucket without a heap
/// allocation for typical `Pod` keys, while imposing **no** compile-time cap on
/// the key size — the generic-dependent buffer length rules out a plain stack
/// array (`[u8; node_size()]` is rejected as "constant expression depends on a
/// generic parameter"), so this hand-rolled small-buffer stands in for it.
pub(super) struct Scratch {
    inline: [u8; SCRATCH_INLINE],
    spill: Vec<u8>,
}

impl Scratch {
    pub(super) fn new() -> Self {
        Scratch {
            inline: [0u8; SCRATCH_INLINE],
            spill: Vec::new(),
        }
    }

    /// A `&mut [u8]` of length `n` to read into. The bytes are not cleared — the
    /// caller overwrites the whole slice with a `get_into`.
    pub(super) fn buf(&mut self, n: usize) -> &mut [u8] {
        if n <= SCRATCH_INLINE {
            &mut self.inline[..n]
        } else {
            if self.spill.len() < n {
                self.spill.resize(n, 0);
            }
            &mut self.spill[..n]
        }
    }
}

/// Allocate a block and write `bytes` as its whole image (one write; released
/// without leaking on write failure).
pub(super) fn alloc_image<A: BStackRaiiAllocator>(
    allocator: &A,
    bytes: &[u8],
) -> io::Result<BStackRange> {
    let mut slice = allocator.alloc(bytes.len() as u64)?;
    if let Err(e) = slice.write_range(0, bytes) {
        let _ = allocator.dealloc(slice);
        return Err(e);
    }
    Ok(slice.as_range())
}

/// Commit an atomic, **external-lock-free** read-modify-write to a container's
/// on-disk metadata via [`BStack::inplace_gen`].
///
/// `reads1` are absolute offsets of `u64` slots read in a first round; the values
/// are handed to `reads2` to compute a second round of offsets that may *depend*
/// on the first (e.g. the `prev`/`value` slots of a node found via a pointer, or
/// the live element slots of a ring found via `head`/`cap`). `plan` then turns
/// both read rounds into the writes to commit, returned as a borrow of a buffer
/// the caller owns (typically declared just above the [`atomic_update`] call) —
/// `plan` is `FnOnce`, so that buffer only needs to outlive this one call.
///
/// The point of routing every mutator through this: all reads happen **inside**
/// the generator, under bstack's single write lock, so the values reflect the
/// committed state at the one commit point and no other thread can interleave
/// between the reads and the dependent writes — no external lock, no torn
/// structure. Every write lands as one crash-atomic batch (all-or-nothing).
///
/// Only in-place reads/writes ride the generator; allocations and frees, which
/// change the stack's size, are done by the caller *around* it (a freshly
/// allocated block is an orphan until the commit links it; a freed block is
/// already unlinked), so a crash can at worst leak, never tear the structure.
pub(super) fn atomic_update<'w, A, R2, W>(
    allocator: &A,
    reads1: &[u64],
    reads2: R2,
    plan: W,
) -> io::Result<()>
where
    A: BStackRaiiAllocator,
    R2: FnOnce(&[u64]) -> io::Result<Vec<u64>>,
    W: FnOnce(&[u64], &[u64]) -> io::Result<&'w [(u64, SmallBuf)]>,
{
    // Buffers that must outlive the whole `inplace_gen` call (bstack's documented
    // generator pattern): read-back values and the computed writes.
    let mut buf1: Vec<[u8; 8]> = vec![[0u8; 8]; reads1.len()];
    let mut vals1: Vec<u64> = Vec::new();
    let mut offs2: Vec<u64> = Vec::new();
    let mut buf2: Vec<[u8; 8]> = Vec::new();
    let mut writes: &'w [(u64, SmallBuf)] = &[];
    // `plan` can fail (e.g. an overflowing offset computed from a corrupted
    // on-disk pointer); the generator closure itself can't return `Result`, so
    // a failure is captured here, the generator aborts (commits nothing), and
    // the error surfaces after `inplace_gen` returns.
    let mut plan_err: Option<io::Error> = None;
    // A failed `Read` op is reported here as the *previous* op's result. This
    // closure derives its writes from the read-back buffers, so a swallowed read
    // error would commit writes computed from stale/zero bytes (or, if aborted
    // silently, return a false `Ok` for an update that never happened). Capture it
    // in the read phase — nothing is staged yet, so ending commits nothing — and
    // surface it after `inplace_gen` returns.
    let mut read_err: Option<io::Error> = None;

    let mut reads2 = Some(reads2);
    let mut plan = Some(plan);

    let mut r1 = 0usize;
    let mut did_a = false;
    let mut r2 = 0usize;
    let mut did_b = false;
    let mut w = 0usize;

    allocator.stack().inplace_gen(|feedback| {
        if let Err(e) = feedback {
            read_err = Some(e);
            return None; // read phase, nothing staged → commits nothing
        }
        // Round 1 — read the fixed offsets.
        if r1 < reads1.len() {
            let i = r1;
            r1 += 1;
            // SAFETY: `buf1` outlives this call; one read op uses slot `i` at a time.
            let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut buf1[i][..]) };
            return Some(BStackGenOp::Read {
                offset: reads1[i],
                buf: b,
            });
        }
        // Transition A — compute the (possibly dependent) round-2 offsets.
        if !did_a {
            did_a = true;
            vals1 = buf1.iter().map(|x| u64::from_le_bytes(*x)).collect();
            match (reads2.take().unwrap())(&vals1) {
                Ok(offs) => offs2 = offs,
                Err(e) => {
                    plan_err = Some(e);
                    return None; // abort: commit nothing
                }
            }
            buf2 = vec![[0u8; 8]; offs2.len()];
        }
        // Round 2 — read the dependent offsets.
        if r2 < offs2.len() {
            let i = r2;
            r2 += 1;
            // SAFETY: `buf2` outlives this call and is not resized after Transition A.
            let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut buf2[i][..]) };
            return Some(BStackGenOp::Read {
                offset: offs2[i],
                buf: b,
            });
        }
        // Transition B — compute the writes from both read rounds.
        if !did_b {
            did_b = true;
            let vals2: Vec<u64> = buf2.iter().map(|x| u64::from_le_bytes(*x)).collect();
            match (plan.take().unwrap())(&vals1, &vals2) {
                Ok(ws) => writes = ws,
                Err(e) => {
                    plan_err = Some(e);
                    return None; // abort: commit nothing
                }
            }
        }
        // Commit phase — emit every write; they land together atomically.
        if w < writes.len() {
            let i = w;
            w += 1;
            let (off, ref bytes) = writes[i];
            // SAFETY: `writes` outlives this call and is not mutated after Transition B.
            let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(bytes.as_slice()) };
            return Some(BStackGenOp::Write {
                offset: off,
                data: d,
            });
        }
        None
    })?;
    match read_err.or(plan_err) {
        Some(e) => Err(e),
        None => Ok(()),
    }
}

/// A snapshot of an open-addressing table's four handle metadata fields
/// (`table`, `cap`, `len`, `used`), read inside a generator. Both
/// [`crate::BStackHashMap`] and [`crate::stdlib::BStackHashSet`] lay these out
/// contiguously at `handle + HEADER_SIZE`.
pub(super) struct Meta {
    pub(super) table: u64,
    pub(super) cap: u64,
    pub(super) len: u64,
    pub(super) used: u64,
}

/// A probe step returned by the `inspect` closure of [`probe_commit`].
pub(super) enum ProbeStep {
    /// This bucket isn't the target — keep probing.
    Continue,
    /// Stop here and commit these writes (empty = commit nothing), or fail
    /// (e.g. an overflowing bucket offset computed from a corrupted `m.table`).
    Stop(io::Result<Vec<(u64, SmallBuf)>>),
}

/// Run an atomic, external-lock-free linear probe over an open-addressing bucket
/// table under one [`BStack::inplace_gen`].
///
/// Reads the four-`u64` handle metadata (at `handle + HEADER_SIZE`), then linearly
/// probes buckets from `hash & (cap-1)`, reading the full `stride`-byte bucket
/// each step and handing it to `inspect`. The first `inspect` returning
/// [`ProbeStep::Stop`] commits its writes and ends; if all `cap` buckets are
/// probed without a stop, `exhausted` produces the final writes. Every read and
/// write rides the one generator, so the probe sees a consistent snapshot and the
/// writes land as one crash-atomic batch. Shared by the hash map and hash set.
pub(super) fn probe_commit<A, I, E>(
    allocator: &A,
    handle: u64,
    stride: u64,
    hash: u64,
    mut inspect: I,
    exhausted: E,
) -> io::Result<()>
where
    A: BStackRaiiAllocator,
    I: FnMut(&Meta, u64, &[u8]) -> ProbeStep,
    E: FnOnce(&Meta) -> io::Result<Vec<(u64, SmallBuf)>>,
{
    let mut meta_buf = [0u8; 32];
    let mut bucket_buf = vec![0u8; stride as usize];
    let mut writes: Vec<(u64, SmallBuf)> = Vec::new();

    let mut meta_issued = false;
    let mut meta: Option<Meta> = None;
    let mut mask = 0u64;
    let mut cur = 0u64;
    let mut idx_at_read = 0u64;
    let mut probe_pending = false;
    let mut probed = 0u64;
    let mut decided = false;
    let mut exhausted = Some(exhausted);
    let mut w = 0usize;
    // `m.table` is an on-disk pointer that can be corrupted/forged; the
    // generator closure can't return `Result`, so an overflowing bucket
    // offset is captured here, the probe aborts (commits nothing), and the
    // error surfaces after `inplace_gen` returns.
    let mut probe_err: Option<io::Error> = None;
    // A failed `Read` (bad metadata/bucket read) is reported here as the previous
    // op's result. `inspect`/`exhausted` run on the read-back buffers, so a
    // swallowed read error would commit a decision made on stale/zero bytes (or a
    // false `Ok` for a probe that read nothing). Capture it in the read phase —
    // nothing is staged yet — and surface it after `inplace_gen` returns.
    let mut read_err: Option<io::Error> = None;

    allocator.stack().inplace_gen(|feedback| {
        if let Err(e) = feedback {
            read_err = Some(e);
            return None; // read phase, nothing staged → commits nothing
        }
        // 1. Read the 32-byte metadata block.
        if !meta_issued {
            meta_issued = true;
            // SAFETY: `meta_buf` outlives the call; used by this one read.
            let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut meta_buf[..]) };
            return Some(BStackGenOp::Read {
                offset: handle + HEADER_SIZE,
                buf: b,
            });
        }
        // 2. Parse it once.
        if meta.is_none() {
            let m = Meta {
                table: get_u64(&meta_buf[0..8]),
                cap: get_u64(&meta_buf[8..16]),
                len: get_u64(&meta_buf[16..24]),
                used: get_u64(&meta_buf[24..32]),
            };
            mask = m.cap.wrapping_sub(1);
            cur = if m.cap == 0 { 0 } else { hash & mask };
            meta = Some(m);
        }
        let m = meta.as_ref().unwrap();

        // 3a. Inspect a completed bucket read.
        if probe_pending {
            probe_pending = false;
            if let ProbeStep::Stop(ws) = inspect(m, idx_at_read, &bucket_buf) {
                match ws {
                    Ok(ws) => writes = ws,
                    Err(e) => {
                        probe_err = Some(e);
                        return None; // abort: commit nothing
                    }
                }
                decided = true;
            }
        }
        // 3b. Issue the next probe, or finish by exhaustion.
        if !decided {
            if m.cap == 0 || probed >= m.cap {
                match (exhausted.take().unwrap())(m) {
                    Ok(ws) => writes = ws,
                    Err(e) => {
                        probe_err = Some(e);
                        return None; // abort: commit nothing
                    }
                }
                decided = true;
            } else {
                idx_at_read = cur;
                probe_pending = true;
                probed += 1;
                cur = (cur + 1) & mask;
                let off = match checked_off_mul(m.table, idx_at_read, stride) {
                    Ok(off) => off,
                    Err(e) => {
                        probe_err = Some(e);
                        return None; // abort: commit nothing
                    }
                };
                // SAFETY: `bucket_buf` outlives the call; each read completes
                // (and is inspected) before the next is issued.
                let b: &mut [u8] =
                    unsafe { core::mem::transmute::<&mut [u8], _>(&mut bucket_buf[..]) };
                return Some(BStackGenOp::Read {
                    offset: off,
                    buf: b,
                });
            }
        }
        // 4. Commit the chosen writes together.
        if w < writes.len() {
            let i = w;
            w += 1;
            let (off, ref bytes) = writes[i];
            // SAFETY: `writes` outlives the call and is not mutated after this point.
            let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(bytes.as_slice()) };
            return Some(BStackGenOp::Write {
                offset: off,
                data: d,
            });
        }
        None
    })?;
    match read_err.or(probe_err) {
        Some(e) => Err(e),
        None => Ok(()),
    }
}

/// Grow an open-addressing bucket table to at least double its capacity,
/// rehashing every live bucket (dropping tombstones) atomically. A no-op
/// (beyond a freed spare block) if another writer already grew it at least
/// this far.
///
/// Shared by [`crate::BStackHashMap`] and [`crate::stdlib::BStackHashSet`] —
/// the two bucket layouts differ only in whether the `stride - 8 - ksz`
/// trailing bytes after the key hold a value ref (map) or nothing (set), and
/// this treats those bytes as opaque payload: copied alongside the key,
/// never hashed or interpreted. So one rehash loop covers both. `ksz` is the
/// key size in bytes, `occupied` the bucket-state value marking a live entry
/// (a rebuilt bucket starts zeroed, so `0` always means empty), and `min_cap`
/// the capacity an empty table grows to.
pub(super) fn grow_table<A: BStackRaiiAllocator>(
    allocator: &A,
    handle: u64,
    stride: u64,
    ksz: usize,
    occupied: u64,
    min_cap: u64,
) -> io::Result<()> {
    let cap0 = read_u64(allocator.stack(), handle + HEADER_SIZE + 8)?;
    let newcap = if cap0 == 0 {
        min_cap
    } else {
        cap0.saturating_mul(2)
    };
    let overflow_err = || io_error!("corrupt bucket table capacity");
    // Allocate the new bucket block up front (an orphan until the swap).
    let new_size = newcap.checked_mul(stride).ok_or_else(overflow_err)?;
    let newtable = allocator.alloc(new_size)?.as_range().start();

    let mut meta_buf = [0u8; 32];
    let old_size = cap0.checked_mul(stride).ok_or_else(overflow_err)?;
    let mut old_buf = vec![0u8; old_size as usize];
    let mut new_image: Vec<u8> = Vec::new();
    let grown = Cell::new(false);
    let old_table = Cell::new(0u64);
    let old_cap = Cell::new(0u64);

    let mut meta_issued = false;
    let mut meta: Option<Meta> = None;
    let mut abort = false;
    let mut read_i = 0u64;
    let mut built = false;
    let mut writes: WriteBuf<4> = WriteBuf::new();
    let mut w = 0usize;
    // `m.table` is an on-disk pointer that can be corrupted/forged; the
    // generator closure can't return `Result`, so an overflowing bucket
    // offset is captured here, the generator aborts (commits nothing), and
    // the error surfaces after `inplace_gen` returns.
    let mut grow_err: Option<io::Error> = None;

    allocator.stack().inplace_gen(|feedback| {
        // A failed `Read` is reported here as the previous op's result. The rebuild
        // below runs on the read-back `meta_buf`/`old_buf`, so a swallowed read
        // error would rebuild from stale/zero bytes (or return a false `Ok`).
        // Capture it in `grow_err` (read phase, nothing staged → commits nothing)
        // so it flows through the orphan-`newtable` reclaim path after the call.
        if let Err(e) = feedback {
            grow_err = Some(e);
            return None;
        }
        if !meta_issued {
            meta_issued = true;
            // SAFETY: `meta_buf` outlives the call.
            let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut meta_buf[..]) };
            return Some(BStackGenOp::Read {
                offset: handle + HEADER_SIZE,
                buf: b,
            });
        }
        if meta.is_none() {
            let m = Meta {
                table: get_u64(&meta_buf[0..8]),
                cap: get_u64(&meta_buf[8..16]),
                len: get_u64(&meta_buf[16..24]),
                used: get_u64(&meta_buf[24..32]),
            };
            // Abort if someone already grew to at least this size.
            if newcap <= m.cap {
                abort = true;
            }
            meta = Some(m);
        }
        if abort {
            return None; // commit nothing
        }
        let m = meta.as_ref().unwrap();

        // Snapshot every old bucket.
        if read_i < m.cap {
            let i = read_i;
            read_i += 1;
            let lo = (i * stride) as usize;
            let hi = lo + stride as usize;
            if hi > old_buf.len() {
                // `m.cap` (read fresh, under the lock) exceeds `cap0` (read
                // before this generator started) — either a concurrent grow
                // the abort check above didn't catch, or a corrupted `cap`;
                // either way `old_buf` (sized for `cap0`) can't hold slot `i`.
                grow_err = Some(io_error!("bucket table capacity changed during grow"));
                return None;
            }
            let off = match checked_off_mul(m.table, i, stride) {
                Ok(off) => off,
                Err(e) => {
                    grow_err = Some(e);
                    return None; // abort: commit nothing
                }
            };
            // SAFETY: `old_buf` outlives the call; each slice read once.
            let b: &mut [u8] =
                unsafe { core::mem::transmute::<&mut [u8], _>(&mut old_buf[lo..hi]) };
            return Some(BStackGenOp::Read {
                offset: off,
                buf: b,
            });
        }

        // Rebuild the table into the new block (dropping tombstones).
        if !built {
            built = true;
            grown.set(true);
            old_table.set(m.table);
            old_cap.set(m.cap);

            new_image = vec![0u8; new_size as usize]; // all EMPTY (0)
            let newmask = newcap - 1;
            for j in 0..m.cap {
                let lo = (j * stride) as usize;
                if get_u64(&old_buf[lo..lo + 8]) != occupied {
                    continue;
                }
                let kb = &old_buf[lo + 8..lo + 8 + ksz];
                // Trailing payload after the key (a map's value ref; empty for a set).
                let rest = &old_buf[lo + 8 + ksz..lo + stride as usize];
                let mut idx = fnv1a(kb) & newmask;
                loop {
                    let nlo = (idx * stride) as usize;
                    if get_u64(&new_image[nlo..nlo + 8]) == 0 {
                        new_image[nlo..nlo + 8].copy_from_slice(&occupied.to_le_bytes());
                        new_image[nlo + 8..nlo + 8 + ksz].copy_from_slice(kb);
                        new_image[nlo + 8 + ksz..nlo + stride as usize].copy_from_slice(rest);
                        break;
                    }
                    idx = (idx + 1) & newmask;
                }
            }
            writes.push((
                newtable,
                SmallBuf::Heap(std::mem::take(&mut new_image).into_boxed_slice()),
            ));
            writes.push(w8(handle + HEADER_SIZE, newtable));
            writes.push(w8(handle + HEADER_SIZE + 8, newcap));
            // Tombstones dropped: used == len now.
            writes.push(w8(handle + HEADER_SIZE + 24, m.len));
        }
        if w < writes.len() {
            let i = w;
            w += 1;
            let (off, ref bytes) = writes.as_slice()[i];
            // SAFETY: `writes` outlives this call and is not mutated after build.
            let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(bytes.as_slice()) };
            return Some(BStackGenOp::Write {
                offset: off,
                data: d,
            });
        }
        None
    })?;
    if let Some(e) = grow_err {
        // SAFETY: `newtable` was never linked into the descriptor.
        let _ = unsafe { dealloc_range(allocator, BStackRange::new(newtable, new_size)) };
        return Err(e);
    }

    if grown.get() {
        if old_cap.get() > 0 {
            // SAFETY: the descriptor no longer points at the old table.
            let _ = unsafe {
                dealloc_range(
                    allocator,
                    BStackRange::new(old_table.get(), old_cap.get().saturating_mul(stride)),
                )
            };
        }
    } else {
        // SAFETY: `newtable` was never linked into the descriptor.
        let _ = unsafe { dealloc_range(allocator, BStackRange::new(newtable, new_size)) };
    }
    Ok(())
}