Linear Address Spaces: Unsafe at any speed [article]

By: Adrian (a.delete@this.acm.org), July 3, 2022 10:04 pm
Room: Moderated Discussions
Foo_ (foo.delete@this.nomail.com) on July 3, 2022 2:45 am wrote:
> Adrian (a.delete@this.acm.org) on July 1, 2022 9:58 pm wrote:
> > Foo_ (foo.delete@this.nomail.com) on July 1, 2022 3:21 am wrote:
> > > Adrian (a.delete@this.acm.org) on June 30, 2022 9:43 am wrote:
> > > >
> > > > When all the allocation and free requests are done from stacks, each stack corresponding
> > > > to a certain size class, nothing ever changes from the point of view of fragmentation.
> > >
> > > This is delusional. Allocation may be done "from stacks", but given that deallocations
> > > happen in random order (random from the POV of the allocator, of course), they
> > > cannot be done in a simple stack-like (i.e. LIFO) fashion.
> >
> >
> > When the size is variable, you are right.
> >
> > But when the size of a memory block is fixed (being used to satisfy any allocation
> > requests between 2 thresholds), the allocations and deallocations are really
> > done as LIFO from the stack containing the free memory blocks.
>
> You don't read what you reply to, do you?
>


Actually I have read carefully, but maybe I have not explained clearly enough.

Even when the "free" invocations happen in a random order compared with the corresponding "malloc" invocations, if the size of the allocation requests is the same (in practice it is enough for the size to belong to a certain range, for which the allocation requests are satisfied using free memory blocks of the same size), then the memory allocator can make the allocation and freeing actions for memory blocks in a last-in-first-out-manner, which allows the implementation of the heap as a stack (in practice as a set of stacks, corresponding to the set of size ranges).

The reason why this is possible is that when a new "malloc" invocation happens (for a given size range), it will be possible to satisfy the request by pulling the last freed memory block from the list of free memory block, because it has the same size.

It does not matter to which previous "malloc" the last "free" corresponded. The last freed block will always be good for the next "malloc", so it will be the first to be allocated again.



This contrasts with the standard heap implementation, where in order to satisfy a new "malloc" request, the heap must be searched to find a memory block whose size matches the new "malloc" and that will be a block who might have been freed a long time ago, and many other "malloc" and "free" invocations might have happened since that time. With this kind of heap, what you have written, i.e. "they cannot be done in a simple stack-like (i.e. LIFO) fashion", is definitely true.

With a heap implemented as a set of stacks, corresponding to size ranges, that phrase is false, because the memory blocks are always freed, then allocated, in a LIFO manner, more precisely in a last-freed-first-allocated manner.

This simplification of a heap into a stack is possible only for memory blocks of the same size, which makes them equivalent.
< 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? 🍊