Adrian (a.delete@this.acm.org) on July 1, 2022 12:55 am wrote:
> Jörn Engel (joern.delete@this.purestorage.com) on June 30, 2022 5:34 pm wrote:
> > Adrian (a.delete@this.acm.org) on June 30, 2022 5:36 am wrote:
> > >
> > > With CHERI, the memory protection and dynamic relocation functions of paging would become redundant, so the
> > > only valid justification for the great hardware complexity
> > > added by the support for paging in 64-bit ISAs would
> > > remain the avoidance of memory fragmentation in the memory allocators used by the operating systems.
> > >
> > >
> > > In the memory allocators used by individual processes it is possible to completely avoid
> > > memory fragmentation, e.g. by using separate memory pools for different object sizes.
> >
> > While I usually value what you read, I have to join the huge choir that calls BS
> > on these claims. You're basically saying that slab allocators completely avoid
> > fragmentation because they have separate pools for different object sizes.
> >
> > Let's run a simple thought experiment. We have 4k slabs split up into size classes of 64B, 128B, 256B,
> > etc. The program allocates 1M 64B objects, then randomly frees 99.9% of them, holding on to just 1k.
> >
> > In the common case, you end up with slabs containing a single object. Theoretically they could hold 63
> > objects (64 minus metadata overhead). The difference between 63 and ~1 is what? Not fragmentation?
> >
> > If the program then wants to allocation a 128B objects, can it use any of the almost-free slabs
> > for that purpose? You have nearly 4MB of free space available. So without fragmentation, why
> > would you have to allocate a new slab for your allocation if you have that much free space?
>
>
> By slabs I assume that you refer to memory allocators like those used internally by gcc.
>
> I do not remember right now how the gcc slabs work, but I have referred to a somewhat related but not
> identical variant of implementing "malloc", where the list containing the free blocks of one size, e.g.
> 64 B, is a stack implemented as a linked list, and no problem like that described by you can appear.
>
> Any request allocation for a size from 33 B to 64 B would result in popping a block from the 64-B stack,
> while freeing a block formerly taken from the 64-B stack will push the block back in the stack.
>
> After allocating 1 million objects of sizes 33-64 and randomly freeing all
> but 1 thousand, the 64-B stack will have at least 1 thousand free blocks ready
> to satisfy any allocation request for sizes in the 33-64 bytes range.
>
> There is no difference whatsoever caused by the order of allocation and free requests. When the 64-B stack
> is empty, some more pages are requested from the OS and used to push in the stack additional free blocks.
>
> If the stacks are based on power-of-two boundaries, that could waste up to almost a half of the heap memory and
> maybe around 25% on the average. To use the memory more efficiently, for small sizes where allocations requests
> are more frequent, a larger number of stacks can be used, e.g. with 2 or 3 size thresholds per octave, e.g. ...
> 32 byte 48 byte 64 byte 96 byte ..., or ... 32 byte 40 byte, 48 byte 64 byte 80 byte 96 byte ... .
>
> This style of malloc guarantees no fragmentation (i.e. no memory from the heap
> ever reaches a state when it cannot be reused for new allocations) and it can be
> very fast, because there are no searches when allocating or freeing blocks.
>
> Nevertheless, it is not used often, because it is not very efficient in using the available
> heap size, as most allocated blocks are not fully used and every memory block must contain
> a pointer, to allow being pushed and popped to/from the stacks with free blocks.
>
>
> Another problem that can lead to inefficient use of memory is that mentioned by you, i.e. if the process
> allocates 1 million objects of one size and then it frees them and then it never allocates objects of that
> size again, there would be a large stack storing unused free memory blocks. However, this can be mitigated
> if the memory allocator detects this and it attempts to pop the free blocks and either return pages to
> the OS or make from them free blocks for other sizes, but this cannot always be successful.

The worst-case scenario for the memory allocator you are describing IS NOT when first allocating 1_000_000 objects of the same size and then deallocating 999_999 of those objects. The reason for that is that the pattern remaining after deallocation of the 999_999 objects - which leaves only 1 object allocated - has a very low descriptive complexity.

The worst-case scenario is: allocate 1_000_000 objects and then use an RNG (random number generator) to deallocate 500_000 randomly selected objects. The reason why this is the worst-case scenario is that the resulting sequence of 0 and 1 (zeroes and ones, or it can be interpreted as boolean values) is incompressible (assuming we want to avoid re-running the RNG every time a malloc() or free() is called to serve additional allocation/deallocation requests after the 500_000 deallocations finish executing).

> I agree that this problem that can appear when a process never allocates again objects of some
> size after allocating and freeing a very large number of objects of that size is similar to heap
> fragmentation in other styles of allocators, but it also has essential differences, because it
> is much more unlikely to happen and its consequences are much less severe, if it happens.
>
> The process in which this happens does not suffer any negative consequence whatsoever. The entire
> system may suffer because of too much memory used by that process, but this is very unlikely.
> For the stacks corresponding to objects of large size, which are more likely to accumulate too
> much unused memory, it is also much more likely that the memory allocator can succeed in popping
> most of the free blocks and merge them into free pages that can be returned to the OS.
>
> Even when that is not possible, this behavior of using a very large number of objects of 1 size and never
> using that size again is a much more unlikely behavior than those that cause heap fragmentation in other
> styles of malloc, where heap fragmentation is caused by the most normal kind of using malloc and free.

Basically, you are claiming that if a program has for example reached a point/state in which it has the following counts and sizes of memory allocated (COUNT*SIZE):

4*AA 3*BBBB 1*CCCCCCCC

then the memory layout (=L1):

AA .... AA .... AA .... AA ....

BBBB .... BBBB .... BBBB ....

CCCCCCCC ....

somehow results in lower _total_ memory consumption compared to a memory layout (=L2) such as:

AA .... BBBB .... AA .... BBBB .... AA .... CCCCCCCC .... BBBB .... AA ....

There exist many "...." regions in both cases. So, please post a sufficiently thorough explanation why you believe that the combined/total memory usage of those "...." is lower in the memory allocator layout L1 you are defending here and is higher in allocator L2.

The main advantage of L1 over L2 isn't lower memory fragmentation - the main advantage is that L1 can fulfill a request in O(1) time, but L2 requires O(log(N)) time.

-atom