Re: void* in Lua_State for Application?

[Sean Conner <sean@...>]

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. 

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)