 |
lua-l archive |
|
|
||
|
On Sep 6, 2013 4:02 AM, "Sean Conner" <sean@conman.org> wrote:
>
> It was thus said that the Great Andres Perera once stated:
> > On Sep 5, 2013 10:53 PM, "Tim Hill" <drtimhill@gmail.com> wrote:
> > […]
> > > As for malloc(), nope, not confused at all, and while I am making a
> > > general assumption about malloc(), I've yet to find a help allocator
> > > underneath the C malloc() API that only allocates multiples of VM pages
> > > (I'm not sure when you mean "greater" granularity of you mean finer or
> > > coarser grained).
> >
> > Sigh.
> >
> > Whether or not malloc() organizes objects into buckets sized n^2, malloc()
> > can only acquire multiples of pagesize of virtual memory at a time. One
> > page can hold multiple objects.
> >
> > In function ``f'',
> >
> > int f()
> > {
> > /*pa*/
> > z = malloc(x);
> > /*pb*/
> > }
> >
> > f at pa the process has allocated n bytes, and malloc(x) is successful,
> > then at pb the process vm will be (n + x + PAGESIZE-1) & ~(PAGESIZE-1), in
> > other words, rounded to the nearest greater pagesize multiple.
>
Below you've written a nicer rundown that takes in account common syscall-reducing optimizations.
It's easy to see that malloc behavior potentially varies to a greater degree than architecture vm specs wrt fixed minimal allocation.
At least you recognize the difference between minimal allocation and size separated pools.
> int f(void)
> {
> void *p[10];
>
> p[0] = malloc(10);
>
> /*--------------------------------
> ;
> ; At this point, let's assume that malloc() had to allocate some more
> ; memory from the operating system. Under Unix, this can be done via
> ; brk()/sbrk() (older Unix systems) or mmap() (modern Unix systems).
> ; brk()/sbrk() increase the size of the data segment, which *may* cause a
> ; page to be allocated, but you are assuming that a generic Unix system is
> ; paged---not all were.
> ;
> ; But that's somewhat academic---let's just go with a modern system using
> ; mmap() to provide backing memory pages. And in this case, let's use a
> ; 32-bit system with 4K page sizes. So now, the underlying malloc()
> ; implementation has increased the virtual memory size of the process by a
> ; page.
> ;
> ; There is some overhead that malloc() uses, so our 10 byte structure
> ; probably has an additional 4 bytes allocated to indicate the size of the
> ; block, we we are now up to 14 bytes, plus padding bytes to ensure
> ; alignment and let's go easy and say we can align everything on a 4-byte
> ; boundary, so our overhead for this 10-byte block is 6 bytes for a total
> ; of 16 bytes used in the 4k page just freshly allocated.
> ;
> ;------------------------------------------*/
>
> p[1] = malloc(10);
>
> /*------------------------------------------------------------
> ; there's no need for malloc() to allocate a new page, since this will
> ; easily fit in the remaining space. So, mark off another 16 bytes (6
> ; bytes overhead, 10 bytes actual allocation).
> ;------------------------------------------------------------*/
>
> p[2] = malloc(10);
>
> /*----------------------------------------------
> ; same as p[1]. Nothing to see, move along
> ;----------------------------------------------*/
>
> free(p[1]);
>
> /*--------------------------------------------------------
> ; malloc() now marks the 16 (6 overhead, 10 allocated) as free, available
> ; to be reallocated, if an allocation request that can be satisfied is
> ; made.
> ;------------------------------------------------------------*/
>
> p[3] = malloc(25);
>
> /*------------------------------------------------------------
> ; Now here's where things get interesting. malloc() can't use the the
> ; recently released space since it's not large enough to fulfill the
> ; request. So it has to eat some more space out of the 4k. 25 bytes,
> ; plus 4 for the size of the block is 29. Again, because of alignment
> ; issues, we need a few bytes for padding, in this case, 3. We've
> ; allocated another 32 bytes in the 4k memory page. So far, we have 16
> ; (p[0]) plus 16 (p[2]) plus 32 (p[3]) for a total of 64 bytes allocated;
> ; there is still 4,032 bytes free in the page in two segments---one 16
> ; bytes in size (the freed p[1]) and 4,016 in the other segment.
> ;-----------------------------------------------------------------*/
>
> p[4] = malloc(8);
>
> /*-------------------------------------------------------------------
> ; Another interesting action. We're asking for 8 bytes, which that
> ; 16-byte free space will easily hold. Plus the size overhead gives us 12
> ; bytes, leaving a 4-byte free space, which isn't enough to satisfy any
> ; other requests at all, so the entire space is given over to this request
> ; (4 bytes wasted, even though we don't need padding as 4 bytes is too
> ; small to hand out, given that the space on either side is taken up with
> ; previous allocations).
> ;---------------------------------------------------------------------*/
>
> p[5] = malloc(4012);
>
> /*----------------------------------------------------------------------
> ; And here we suck up the rest of the page into a single allocation.
> ;---------------------------------------------------------------------*/
>
> free(p[0]);
> p[6] = malloc(1);
>
> /*------------------------------------------------------------------
> ; We free up the first 16 bytes, then allocate 1 byte, but because of
> ; alignment and size, gets upped to 8 bytes.
> ;---------------------------------------------------------------------*/
>
> free(p[2]);
> free(p[3]);
> free(p[4]);
> free(p[5]);
> free(p[6]);
>
> /*-------------------------------------------------------------------
> ; Here we've free all the memory we've allocated. At this point, malloc()
> ; could return the memory back to the operating system, or it could hold
> ; onto it, in case we call malloc() again and thus, avoid the overhead of
> ; going to the operating system if we can satisfy the request.
> ;-----------------------------------------------------------------*/
> }
>
> This describes a simple malloc() implementation. Others are more elaborate,
> creating pools of memory to satisfy allocations of certain sizes (say,
> certain pages will be carved out for allocations of 8 bytes or less, other
> pages for allocations between 8 and 32 bytes say, etc.).
>
> > Please show a system where this is false.
>
> Certainly. The AmigaOS. Ran on a Motorola 68000 sans memory management
> unit and thus, no concept at all of a "page". The OS memory allocation
> schemes had an overhead of 12 bytes, with a 4-byte memory alignment (so a
> system request for 1 byte would actually allocate 16 bytes).
>
> Then there are systems that use the protected mode of the 80286. Again,
> no concept of "pages"---and in sucy a system (say, OS/2 1.x) you could
> request from the OS a 1 byte region of memory and you would get, a literal 1
> byte region of memory that was fully protected (it used variable sized
> "segments").
>
> So there *are* systems out there that do not have the concept of a "page".
>
> Are they still in use?
>
> Yes.
>
> Are they indicative of modern systems? Probably not, but you did ask for
> "a system".
>
> -spc (Will belabor the inanimate equus pleonastically for food)
>
>
>