[libc][malloc] Reuse the prev_ field for allocated blocks (#101265)

This applies a standard trick from Knuth for storing boundary tags with
only one word of overhead for allocated blocks. The prev_ block is now
only valid if the previous block is free.

This is safe, since only coalescing with a free node requires walking
the blocks backwards. To allow determining whether it's safe to traverse
backwards, the used flag is changed to a prev_free flag. Since it's
still possible to unconditionally traverse forward, the prev_free flag
for the next block can be used wherever the old used flag is, so long as
there is always a next block.

To ensure there is always a next block, a sentinel last block is added
at the end of the range of blocks. Due to the above, this costs only a
single word per heap. This sentinel essentially just stores whether the
last real block of the heap is free. The sentinel is always considered
used and to have a zero inner size.

This completes the block optimizations needed to address #98086. The
block structure should now be size-competitive with dlmalloc, although
there are still a couple of broader fragmentation concerns to address.

0 files changed, 0 insertions, 0 deletions