kernel malloc() and free()

[Dan Nelson]

In the last episode (Mar 01), Shrivatsan said:
> I am looking at the code that allocates and frees kernel memory. I
> understand that allocating kernel memory is quite different from the user
> level mallocs.  In case of user level mallocs, we allocate requested size
> + 4 bytes and store the requested size in the additional 4 bytes.

Actually FreeBSD's userland malloc hasn't ever had a 4-byte-per-element
overhead like this.  All BSD mallocs have been block-based, where all
objects in a page are the same size.  The original bsd malloc had power-of-2
size groupings (blocks holding the same size objects were linked in a list). 
phkmalloc was imported in 1995 which moves the block metadata into a "page
directory", which is separated from the memory returned by malloc().  The
current malloc (jemalloc) has a similar setup but scales much better on SMP
systems.
 
http://phk.freebsd.dk/pubs/malloc.pdf
http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf

> However, in the case of kernel, allocating an additional 4 bytes is a
> overhead since the request might fall in the next bucket.  I looked into
> the code and the documentation in the file uma_int.h, but I don't quite
> understand the relation between slabs, zones and keg.  How do we determine
> the size of the memory that we are trying to free from given the virtual
> address?

I'm not too familiar with the kernel malloc, but it looks like each keg
holds objects of the same size (and a keg may hold multiple slabs), so once
you get a pointer to the slab header with the vtoslab() macro,
slab->us_keg->uk_size points to the size of the allocation.

Hm.  Even after some reading, I'm not sure how the slabs keep track of which
elements are allocated or free.  I expected to find a bitmap somewhere that
malloc() sets and free() clears, but I don't see it.  Maybe some kernel
hacker can explain it better :) Regardless, the size of the allocation at
this point isn't important, since you know all the items in the page are the
same size.

-- 
	Dan Nelson
	dnelson at allantgroup.com