Re: malloc()'s interaction with the kernel

Matti E Aarnio (
Wed, 21 Aug 1996 11:28:13 +0300 (EET DST)

> Hi,
> The main situation I'm having trouble understanding is this:
> imagine that a process's heap is full of malloc()ed stuff, so
> that on the next call to malloc it is going to run out of heap
> space. So when it calls malloc(), malloc is (I assume) going to
> call brk() to increase the process's data segment size. Then,
> when the task tries to use the new memory, it will page fault,
> and the OS will have to map some more pages into its address
> space, calling something like page_alloc() and then putting the
> pages into its page table in the new space made by brk().

First of all, malloc() and free() are libc things,
that is, they happen entirely in user space.
They use some system services, but more of that below.

Actually a call to malloc is always going to run out of
the heap space, but for performance reasons it may be able
to reuse previously free()d space.

Also for systen platform reasons, the underlying memory
resource gathering does operate in page-size chunks, and
will allocate them from system. If you want to malloc()
a couple bytes, it may be carveable from existing page(s),
or the page-pool gathering must fo sbrk() or mmap() to
get more memory. (DEC OSF/1 uses mmap(), and documents
warn that there pages requested to be allocated without
pre-defined address may appear at ANY address -- above or
below code and/or stack.)

USUALLY systems don't release their memory back to system,
when they do free().

> My question is: how do we determine when we can free these new
> pages? If they are used to hold several malloc()ed blocks, it
> seems difficult to keep track of when _all_ the blocks within a
> particular page are free()d so that the page itself may be freed
> with a system call. Does the C library keep a count of how many
> blocks are malloc()ed inside each page?

There are several malloc() implementations, all of them
do keep some book at which blocks are free, and which
are not. Some even do merge adjacent free blocks into
larger, and can carve out small bits of them out.
However it might not be that easy to detect, when some
page has truly become free, and can be removed.

I have written applications that do this explicitely
by mmap()ing huge blocks of memory, and latter munmap()
it away.

One of the problems in C is that it lacks a generic way
to handle storage compaction -- and a jokingly presented
``SIGBSD -- your program uses too little memory''
is apparently the way that people do programs...
( "It does not use 32 MB ? malloc() more!" )

In sbrk() model: one raising/lowering boundary,
all pages above highest used block can be freed,
but if up there is any single byte in use, it can't
be released... Ok, in that model it is rather
simple thing to do with detecting when we are
freeing highest block, and by doing free-space
merge, or some such, we can search for the next
highest used block, reset the pointer, and sbrk()

In a scatter mmap(), the book-keeping needs to be
more complex.

> I'd appreciate it if someone could clear this point up for me, as
> well as pointing out the inevitable errors in my guesswork above.
> Apologies if this isn't strongly kernel-related, but I couldn't
> think of a better place to ask.
> Jason.

/Matti Aarnio <>
(Who has been using all kinds of weird
malloc()s at ZMailer router internal