Capacity-based allocations: Allow ZSTs but forbid allocations with zeroed-capacity.

[TimDiekmann]

Allocating currently is based on a size in bytes and an alignment. For a given type T align is simply the alignment of T in most cases and size is a multiple of the size of T. More exotic layouts can be constructed with a [repr(align(...))] struct containing [u8; N]. Currently Layout looks like this:

struct Layout {
    size: usize,
    align: NonZeroUsize,
}

size is a multiple of mem::size_of::<T>() and align is almost always mem::align_of::<T>(). If we would add T to this struct, we could simply remove align, so Layout would look like this (Renamed to MemoryLayout as Layout is stable. Also MemoryLayout is more describtive.):

struct MemoryLayout<T> {
    capacity: usize,
}

We want mem::size_of::<Option<MemoryLayout<T>>>() == mem::size_of::<MemoryLayout<T>>(). Do we really need a layout with zero capacity? We have allowed ZSTs in AllocRef, which is fine, but I really don't think we need to support zeroed-capacity allocations.

AllocRef has to support unsized types to deallocate Box<T: !Sized>, this must be changed to MemoryLayout<T: ?Sized>, but size_of and align_of requires T: Sized so we need to store the alignment for T: !Sized. Also we can't use capacity, as we don't know the size of T but we can still use size instead.

struct MemoryLayout<T: !Sized> {
    size: usize,
    align: NonZeroUsize
}

Okay, thats the same as Layout. However we can abuse the layout of pointers: T: Sized pointers are 8 bytes wide, T: !Sized are 16 bytes wide, a fat pointer. Putting everything in one struct:

type MemoryLayoutRepr<T> = NonNull<T>;

Now we have to interpret the data. For T: Sized

• T: Sized:

  fn capacity<T>(repr: MemoryLayoutRepr<T>) -> NonZeroUsize {
      unsafe { NonZeroUsize::new_unchecked(repr.as_ptr() as usize) }
  }
  fn bytes(repr: MemoryLayoutRepr<T>) -> usize {
      capacity(repr).get() * mem::size_of::<T>()
  }
  fn align() -> NonZeroUsize {
      unsafe { NonZeroUsize::new_unchecked(mem::align_of::<T>()) }
  }

• T: !Sized:

  union FatPtr<T: ?Sized> {
      as_ptr: *mut T,
      as_values: [usize; 2],
  }
  fn bytes(repr: MemoryLayoutRepr<T>) -> usize {
      let ptr = FatPtr {
          as_ptr: repr.as_ptr(),
      };
      unsafe { ptr.as_values[1] }
  }
  fn align(repr: MemoryLayoutRepr<T>) -> NonZeroUsize {
      let ptr = FatPtr {
          as_ptr: repr.as_ptr(),
      };
      unsafe { NonZeroUsize::new_unchecked(ptr.as_values[0]) }
  }

Then we just change MemoryLayout to

struct MemoryLayout<T: ?Sized> {
    repr: MemoryLayoutRepr<T>,
}

and wrap the different functions. Our layout is now capacity-based for sized types.

I think this is a pretty big deal, as we halfed the size of Layout which is regularly used in the allocator API (for sized types, which is almost always the case. For unsized types nothing changes).

[Amanieu]

I don't think this is the right abstraction for the AllocRef trait. Your proposed API seems primarily aimed at array-like allocations, but most of the capacity-based allocation logic should be handled by RawVec instead of messing with the generic allocation API.

[Lokathor]

As a person who has made some simple custom data structures myself, I would not use any of this myself.

That doesn't make is definitely bad, just that I would retain maximum control on my side of things and compute a Layout value myself.

Actually, even Layout is an awkward and poor type to use, but it's what we've got, so oh well.

[Amanieu]

I'm pretty happy with the current Layout type, it describes exactly what information needs to be passed to an allocator: the size of a block of memory and its alignment.

[Wodann]

Like @Amanieu, I feel that this focuses too much on a particular use case, while adding a lot of complexity. The Layout is a simple yet versatile solution to the same(?) problem.