Linear Address Spaces: Unsafe at any speed [article]

By: Adrian (a.delete@this.acm.org), July 1, 2022 12:55 am
Room: Moderated Discussions
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.


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 fragmntation is caused by the most normal kind of using malloc and free.
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
Linear Address Spaces: Unsafe at any speed [article]Kester L2022/06/29 01:49 PM
  Linear Address Spaces: Unsafe at any speed [article]Rayla2022/06/29 02:14 PM
    Linear Address Spaces: Unsafe at any speed [article]Kester L2022/06/29 02:43 PM
      Not just worse-is-betterMark Roulo2022/06/29 03:21 PM
        Not just worse-is-better---2022/06/29 07:07 PM
  Linear Address Spaces: Unsafe at any speed [article]2022/06/30 12:08 AM
    Linear Address Spaces: Unsafe at any speed [article]Groo2022/06/30 12:56 PM
      Linear Address Spaces: Unsafe at any speed [article]Michael S2022/06/30 02:17 PM
  Linear Address Spaces: Unsafe at any speed [article]Eric Fink2022/06/30 01:43 AM
  Linear Address Spaces: Unsafe at any speed [article]dmcq2022/06/30 03:17 AM
  Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 05:36 AM
    Linear Address Spaces: Unsafe at any speed [article]anonymou52022/06/30 07:28 AM
      Linear Address Spaces: Unsafe at any speed [article]Anon42022/06/30 04:37 PM
        Linear Address Spaces: Unsafe at any speed [article]anonymou52022/06/30 06:19 PM
          Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 04:16 AM
            Linear Address Spaces: Unsafe at any speed [article]anonymou52022/07/01 05:40 AM
              Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 06:11 AM
                Linear Address Spaces: Unsafe at any speed [article]anonymou52022/07/01 08:09 AM
              Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 06:11 AM
                Why the duplicates?dmcq2022/07/01 06:18 AM
              Linear Address Spaces: Unsafe at any speed [article]2022/07/01 10:41 PM
    Linear Address Spaces: Unsafe at any speed [article]Foo_2022/06/30 07:43 AM
      Fragmentation: Both Size and LifetimeMark Roulo2022/06/30 08:25 AM
        Fragmentation: Both Size and Lifetime2022/06/30 10:09 AM
          Fragmentation: Both Size and Lifetimedmcq2022/06/30 11:12 AM
          Fragmentation: Both Size and LifetimeBrendan2022/06/30 04:08 PM
            Fragmentation: Both Size and Lifetime2022/07/02 03:12 AM
              Fragmentation: Both Size and LifetimeBrendan2022/07/02 01:56 PM
                Fragmentation: Both Size and Lifetime2022/07/04 05:34 AM
                  Fragmentation: Both Size and LifetimeBrendan2022/07/04 06:33 AM
                    Fragmentation: Both Size and Lifetime2022/07/04 07:35 AM
                      Fragmentation: Both Size and LifetimeBrendan2022/07/04 04:21 PM
                    Atom is just living at the Dunning-Krueger peakHeikki Kultala2022/07/04 09:26 AM
                      Atom is just living at the Dunning-Krueger peak2022/07/04 09:57 AM
      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 08:31 AM
        Linear Address Spaces: Unsafe at any speed [article]Foo_2022/06/30 09:07 AM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 09:43 AM
            Linear Address Spaces: Unsafe at any speed [article]Foo_2022/07/01 03:21 AM
              Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 09:58 PM
                Linear Address Spaces: Unsafe at any speed [article]Foo_2022/07/03 02:45 AM
                  Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/03 10:04 PM
                    Linear Address Spaces: Unsafe at any speed [article]ananon2022/07/04 02:35 AM
                    Linear Address Spaces: Unsafe at any speed [article]Foo_2022/07/04 03:11 AM
                      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/05 01:36 AM
                    Linear Address Spaces: Unsafe at any speed [article]2022/07/04 04:18 AM
                    Linear Address Spaces: Unsafe at any speed [article]TAG2022/07/04 07:50 AM
                    Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/04 04:54 PM
                      Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/04 05:05 PM
                      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/05 02:18 AM
                        Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/06 05:16 PM
                          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/07 12:33 AM
        Linear Address Spaces: Unsafe at any speed [article]2022/06/30 10:40 AM
    Linear Address Spaces: Unsafe at any speed [article]---2022/06/30 08:28 AM
      Linear Address Spaces: Unsafe at any speed [article]Michael S2022/06/30 01:00 PM
    Linear Address Spaces: Unsafe at any speed [article]Jörn Engel2022/06/30 05:34 PM
      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 12:55 AM
        Sorry, typo correctionAdrian2022/07/01 01:04 AM
        Linear Address Spaces: Unsafe at any speed [article]2022/07/01 04:01 AM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 11:00 PM
            Linear Address Spaces: Unsafe at any speed [article]rwessel2022/07/02 07:16 AM
        Linear Address Spaces: Unsafe at any speed [article]Jörn Engel2022/07/01 09:40 AM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 11:15 PM
  Linear Address Spaces: Unsafe at any speed [article]Brendan2022/06/30 11:09 AM
    Linear Address Spaces: Unsafe at any speed [article]dmcq2022/06/30 11:20 AM
      Linear Address Spaces: Unsafe at any speed [article]Brendan2022/06/30 03:52 PM
        Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 06:06 AM
          Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/01 01:24 PM
            Linear Address Spaces: Unsafe at any speed [article]rwessel2022/07/01 08:55 PM
  Linear Address Spaces - Free lunch?Björn Ragnar Björnsson2022/07/02 06:44 PM
    Linear Address Spaces - Free lunch?dmcq2022/07/03 04:30 AM
      Linear Address Spaces - Free lunch?Björn Ragnar Björnsson2022/07/03 04:50 PM
  Linear Address Spaces: Unsafe at any speed [article]Paul A. Clayton2022/07/18 07:49 AM
    Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/18 10:21 AM
      Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/18 03:11 PM
        Linear Address Spaces: Unsafe at any speed [article]anon22022/07/18 04:54 PM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/18 10:22 PM
            Linear Address Spaces: Unsafe at any speed [article]Michael S2022/07/19 01:00 AM
              Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/19 05:50 AM
        Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/18 11:02 PM
          Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/19 08:29 PM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell tangerine? 🍊