Linear Address Spaces: Unsafe at any speed [article]

By: Adrian (a.delete@this.acm.org), July 7, 2022 12:33 am
Room: Moderated Discussions
Brendan (btrotter.delete@this.gmail.com) on July 6, 2022 5:16 pm wrote:
> Hi,
>
> Adrian (a.delete@this.acm.org) on July 5, 2022 2:18 am wrote:
> > There should be 2 completely different words for them, as both the conditions that
> > make them happen and the consequences of fragmentation are very different.
> >
> >
> > What causes "fragmentation" to appear:
> >
> > For standard heaps: normal use of "malloc" and "free" with random sizes.
> >
> > For stack-based heaps: an extremely large number of allocations for small
> > objects, much smaller than a memory page, followed by freeing most of them
> > and followed by never requesting allocations in that size range again.
>
> The standard heap has both causes. In other words, fragmentation is exactly the same
> (regardless of "stack vs. standard heap") in all possible cases (where "all possible
> cases" excludes the lone impossible case of allocating random sizes from a stack).


The condition that causes fragmentation for the stack-based heap is an extremely specific variant of the condition that causes fragmentation for a standard heap.

Therefore you are of course right that both causes are valid for a standard heap.

The difference between a standard heap and a stack-based heap is that a standard heap may split a large block into small blocks, to satisfy a request for a small block, while a stack-based heap will never split the free memory blocks, after they have been created by obtaining memory pages from the operating system.

So the "fragmentation" for the stack-based heap is not a state that has any influence upon how the process using dynamic memory allocation works, it is just the state after a lot of memory has been taken from the operating system and used for some time, but that memory will never be used again, so it would be nice to return it to the OS. Returning the memory is trivial for block sizes equal or larger than a page and it is also easy and likely to succeed for blocks not much smaller than a page, e.g. of 512 bytes or larger.

For smaller blocks it may not be possible to return the memory to the OS, due to fragmentation. However, for such smaller free memory blocks, there must be many millions of them, which will never be needed again, so that their total size would be large enough to matter for the memory usage of a modern computer, with multi-gigabyte DRAM.

In theory, such a behavior, of allocating at some time many millions of small objects, then freeing them and never needing again objects of that size class, might be as likely as any other process behavior. In practice, I have never seen any daemon/service with this kind of behavior.




>
>
> > What happens after "fragmentation" has occurred:
> >
> > For standard heaps: "malloc" requests for the same sizes that have succeeded before are
> > no longer successful, unless the heap is extended with new memory pages from the OS.
> > The heap memory previously used is definitively lost, unless for some reason the process
> > begins to need a much larger number of small objects than it has needed before.
> >
> >
> > For stack-based heaps: usually nothing happens for the process itself. However the process
> > keeps occupied more memory than it needs, which can cause problems when new processes
> > are started and they request memory from the OS, requests that may fail now.
>
> For standard heap; the only case where you can free an area then fail to allocate a an area
> of the same size is if a different size (smaller) allocation allocated the memory you freed.
> For stack, in the same scenario it's the same - to satisfy the smaller allocation you allocate
> the previously freed area then waste RAM by padding the smaller size up to the stack's fixed
> size, and then the next allocation (the "next for the same size") fails.

Here you are right that any advantage of a stack-based heap is paid by padding the requested size up to the maximum size of the corresponding size class, wasting thus some of the heap memory.

Also, all the disadvantages of a standard heap have their primary cause in not padding the requested size to a higher value, but splitting a larger block when no blocks of the right size are available.

Any of the 2 choices comes with advantages and disadvantages.



>
> However, if you free a large area, then try to allocate many tiny areas, there will be a
> difference - the stack will waste all the RAM for padding for the first tiny allocation
> and then fail to have RAM that wasn't wasted left over for the subsequent allocations.
>
> In other words, its exactly the same (regardless of "stack vs. standard heap") in almost
> all possible cases (where "all possible cases" excludes the lone impossible case of
> allocating random "larger than stack's fixed size" sizes from a stack); except that
> stack can be much worse for "tiny allocations padded up to fixed block size".
>
> > This condition can be easily detected in a server, by looking
> > at the memory usage of the processes, where the
> > processes holding too much memory are easily seen. The internal
> > heap fragmentation causing memory unavailability
> > in standard heaps is invisible, unless some diagnostic logging is incorporated in the offending program.
>
> The only meaningful difference (which has nothing to do with fragmentation but relates
> to memory consumption) is that standard heap needs a little extra meta-data to keep track
> of allocated block sizes and determine how many bytes to free. Due to minimum alignment
> requirements this typically means 16 bytes extra memory consumed per allocation.
>
> > So in my opinion it is very wrong to use the same name for these 2 states,
> > even if I do not know which would be the best alternative words for them.
>
> In my opinion; there's no need for alternative words when something is exactly the
> same in all possible cases (where "all possible cases" excludes the lone impossible
> case of allocating random "larger than stack's fixed size" sizes from a stack).


Here our opinions are different, because I consider the differences between the 2 kinds of heap implementation to be large enough to be important to distinguish them.


I cannot prove this, because I have never made a thorough investigation to determine in which proportion the externally-visible behavior of many programs is caused by bugs in the way how they use dynamic memory allocation or by inherent properties of their memory allocators.

I see from time to time problems in many GUI programs after a long uptime, the worst offenders being Chrome, followed by Firefox, and then by LibreOffice, problems that appear to be caused by failures to allocate some sort of objects. The problems are always solved completely by closing and restarting the process.

I have never seen any memory allocation problems in daemons or in embedded computers running for years with stack-based heaps.

Of course it is possible that all the problems that I have ever seen in standard programs are caused by bugs and without bugs a standard heap might also have worked fine for long times, but because a standard heap cannot guarantee that, I would be reluctant to trust it.






< 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? 🍊