I have been working on my local allocators, and now have a local allocator that keeps chains of freed memory ( for different size classes ).
But something I don’t understand is if I return the full amount reserved from allocate, rather than the amount requested, everything goes haywire and it seems like my hashbrown HashMaps don’t work any more. I haven’t investigated at all yet, it is also quite possible the problem is with my code rather than hashbrown.
Code for allocate:
fn allocate(&mut self, lay: Layout) -> Result<NonNull<[u8]>, AllocError> {
self.alloc_count += 1;
let n = lay.size();
if NOT_MIRI && n <= MAX_SIZE {
#[cfg(feature = "log-bump")]
{
self._alloc_bytes += n;
self._total_count += 1;
self._total_alloc += n;
};
let (sc, xn) = Self::sc(n);
let p = self.free[sc];
if !p.is_null() {
let next = unsafe { (*p).next };
self.free[sc] = next;
let p = p as *mut u8;
let p = slice_from_raw_parts_mut(p, n);
Ok(unsafe { NonNull::new_unchecked(p) })
} else {
let m = lay.align();
let mut i = self.idx.checked_next_multiple_of(m).unwrap();
let e = i + xn;
// Make a new block if necessary.
if e > BSIZE {
let old = mem::replace(&mut self.cur, Block::new());
self.overflow.push(old);
i = 0;
}
self.idx = i + xn;
Ok(self.cur.alloc(i, n)) // Ought to be able to return xn, but that causes problems!
}
} else {
Global::allocate(&Global, lay)
}
}
Hmm, I just realised I may have a (maybe unrelated) alignment problem when allocating from previously freed memory.
I cannot quite figure out if it is wrong yet, need to look at alignment rules more carefully.
But I think there is an issue if first request is say 64 bytes, unaligned, then that is freed (it will still be MIN_SIZE=8 aligned) and later request is 64 bytes with alignment of 16, well the alignment could only be 8 not 16.
I could simply route requests with alignment of more than MIN_SIZE to the global allocator ( I don’t think they will be common ).
[ I wonder if hashbrown is doing clever things with alignment, like using the low bits of pointers to store stuff ]
Update: well I think I fixed the alignment issue (as above). I am seeing 16 byte alignment requests (but not larger), so I decided on setting MIN_SIZE to 16 for now. But strangely I still get errors if I return the full amount reserved. So I still have a mystery for now.
Well I discovered that hashbrown does use “Utilize over-sized allocations”,
let ptr: NonNull<u8> = match do_alloc(alloc, layout) {
Ok(block) => {
// The allocator can't return a value smaller than was
// requested, so this can be != instead of >=.
if block.len() != layout.size() {
// Utilize over-sized allocations.
let x = maximum_buckets_in(block.len(), table_layout, Group::WIDTH);
debug_assert!(x >= buckets);
// Calculate the new ctrl_offset.
let (oversized_layout, oversized_ctrl_offset) =
match table_layout.calculate_layout_for(x) {
Some(lco) => lco,
None => unsafe { hint::unreachable_unchecked() },
};
debug_assert!(oversized_layout.size() <= block.len());
debug_assert!(oversized_ctrl_offset >= ctrl_offset);
ctrl_offset = oversized_ctrl_offset;
buckets = x;
}
While it may well still be a bug in my allocator, I am starting to suspect there is a flaw in hashbrown here.
Looking closer, there is this at line 1550:
/// Finds the largest number of buckets that can fit in `allocation_size`
/// provided the given TableLayout.
///
/// This relies on some invariants of `capacity_to_buckets`, so only feed in
/// an `allocation_size` calculated from `capacity_to_buckets`.
fn maximum_buckets_in(
allocation_size: usize,
table_layout: TableLayout,
group_width: usize,
) -> usize
But where it calls it, doesn’t use “capacity_to_buckets”, it just uses the raw oversized allocation block.len(). So maybe that explains it?
I eventually found the problem, nothing to do with hashbrown at all, it was my implementation of Box<str>, which was using the over-allocation as the length of the string.