alloc_layout_slow and guarantees for iter_allocated_chunks

[TethysSvensson]

I agree that the fix made in #45 is the right one, however it has a problem: It can introduce padding bytes in the output of iter_allocated_chunks for large alignments.

I think it is fine to introduce padding for large alignments, but we need to decide where to draw the line between support and not supported -- and we need to improve the documentation to reflect this.

I do not have any strong opinions on how large an alignment we should support. I guess it would be nice to support up to alignment 16, since that is largest alignment of that real world code can sometimes need.

However I do not think that anybody who has 16-byte alignment requirements would also want to use iter_allocated_chunks.

Here is some code I used to test this:

const SUPPORTED_ALIGNMENTS: &[usize] = &[1, 2, 4, 8];

quickcheck::quickcheck! {
    fn test_alignment_chunks(sizes: Vec<usize>) -> () {
        for &alignment in SUPPORTED_ALIGNMENTS {
            let mut b = Bump::new();
            let mut sizes = sizes.iter().map(|&size| (size % 10) * alignment).collect::<Vec<_>>();

            for &size in &sizes {
                let layout = std::alloc::Layout::from_size_align(size, alignment).unwrap();
                let ptr = b.alloc_layout(layout).as_ptr() as *const u8 as usize;
                assert_eq!(ptr % alignment, 0);
            }

            for chunk in b.iter_allocated_chunks() {
                let mut remaining = chunk.len();
                while remaining > 0 {
                    let size = sizes.pop().expect("too many bytes in the chunk output");
                    assert!(remaining >= size, "returned chunk contained padding");
                    remaining -= size;
                }
            }
            assert_eq!(sizes.into_iter().sum::<usize>(), 0);
        }
    }
}

[fitzgen]

If I am understanding correctly, the issue is:

• We want to support safe iter_allocated_chunks for when callers know they've only allocated valid things (all the same alignment and therefore no padding between an allocated object A and the next allocated object B)

• The first allocation in a chunk might have to introduce padding downwards from the chunk footer to the first allocation. Callers do not have any way to guarantee that this padding doesn't get inserted other than only using unaligned / packed structs.

• iter_allocated_chunks includes that padding (if it exists) in the yielded chunks, because it is always returning the slice from ptr..footer.

Correct?

It seems to me we can continue to support arbitrary alignments with minimal changes by adding a field to the chunk footer that is the end of the first allocation in a chunk. If there wasn't any padding inserted due to rounding down allocation, then this will point at the chunk footer itself, otherwise it will point at the start of the padding we added. When we create slices to give out in iter_allocated_chunks, we use the range ptr..end_of_first_allocation rather than ptr..footer. Now the user is completely in control of the range of bytes, and they are now able to correctly fulfill the safety responsibilities to use the slice.

What do you think of this plan?

[TethysSvensson]

Yes, your understanding mirrors mine.

I think your plan is a good one.

[fitzgen]

Would you be willing to implement this?

[TethysSvensson]

I have implemented two alternative fixes for this issue. I personally believe #48 to be the better one. It should be faster and waste less memory. The downside of it is that we will no longer support iter_allocated_chunks used with alignments greater than 16 bytes. I do no believe this downside to be very important.

[fitzgen]

Fixed in #48