slab allocator question

[ITchimp]

If I type "sudo cat /proc/slabinfo" I get a list of slabs current in use by OS...

A couple of question..

does slab allocator internally use any kind of metadata describing the pointers being returned to the calling function?
I am asking this because if I call "kfree(ptr)", how does the allocater know the size of the block and the associated slab
to which to return the block? some kind of meta data has to be kept right?

if the allocation is, say, for the size of 1024 byte... does the mean the maximum data is 1024 byte or, the maximum usable
of block is 1024 - sizeof (metadata)?

/proc/slabinfo returns the size of the object.. is that the same as size of usable data area?

[bzt]

If I type "sudo cat /proc/slabinfo" I get a list of slabs current in use by OS...

A couple of question..

does slab allocator internally use any kind of metadata describing the pointers being returned to the calling function?

Yes, of course, all memory allocators do.

I am asking this because if I call "kfree(ptr)", how does the allocater know the size of the block and the associated slab
to which to return the block? some kind of meta data has to be kept right?

It simply looks up the "ptr" in the slabs list, and when it's found, depending on in which slab it's found, the allocator will know the size. For example, let's say a,b,c are memory addresses, a in 512 bytes list, and b,c in the 128 bytes list. When you call "kfree(b)", the slab allocator will look up b in these lists, and it will find b in one of the 128 bytes list, thus knowing b's size.

if the allocation is, say, for the size of 1024 byte... does the mean the maximum data is 1024 byte or, the maximum usable
of block is 1024 - sizeof (metadata)?

Slab allocator does not intermix allocated data with allocator meta data. So 1024. (Btw the Linux slab allocator's unit is not a byte but one page, 4096 bytes).

/proc/slabinfo returns the size of the object.. is that the same as size of usable data area?

Yes.

Read this (good explanations and comparition to buddy) and this (very detailed description) on Linux slab allocator.

Cheers,
bzt

[iansjack]

Yes, of course, all memory allocators do.

That's not true. It would be perfectly possible to define a pair of allocate/free functions where free() took the size of the freed block as a second parameter.

[ITchimp]

if a look up is needed in order to return the object to free list of free objects... it could be a linear
search... and remember that the slab list could be so long (30+ slabs to lookup plus possible calculation involving
offset and length ) that could be slow!!!! ouch!

On the other hand, the meta data size seems fixed regardless of the object size, this is a strong plus...
much better than if metadata and data are mixed together...

[bzt]

That's not true. It would be perfectly possible to define a pair of allocate/free functions where free() took the size of the freed block as a second parameter.

It would be possible, but Linux does not use that. All allocators in the Linux kernel and in all libc implementations store meta data. Win32 API, UEFI API as well as POSIX expects only the address upon freeing memory.

if a look up is needed in order to return the object to free list of free objects... it could be a linear
search... and remember that the slab list could be so long (30+ slabs to lookup plus possible calculation involving
offset and length ) that could be slow!!!! ouch!

It doesn't has to be a linear search. You could store the pointers in an ordered list and use bsearch for example. However looking up if the pointer to be freed was indeed allocated is important, because you cannot free a memory block that wasn't allocated in the first place.

Cheers,
bzt

[iansjack]

We're talking about home-brew OSs here, not Linux, not POSIX, not even libc. Anything is possible!

[bzt]

We're talking about home-brew OSs here, not Linux, not POSIX, not even libc. Anything is possible!

Well, no and no.

First, the OP asked about /proc/slabinfo which is pretty much Linux specific.

Second, without allocator meta info, how does an allocator know which memory is already allocated? How does it know if the address passed to free() isn't already free? Keeping record of the allocated sizes is just one thing, but you need to know the next free address as well, and malloc must not return already allocated area. For these, you need to keep track of memory allocations, that's what allocator meta info is about (regardless what kind of data representation you choose, could it be bitmap, linked list, binary tree, red-black tree, buddy groups, page stack etc. etc. etc. or whether you mix meta info with allocated data or not)

Even the simplest possible memory allocator (that does not implement free at all) needs some sort of meta info, like a pointer at a minimum:

Code: Select all

void *nextfreeaddr;
void *malloc(int size) {
    void *tmp = nextfreeaddr;
    nextfreeaddr += size;
    return tmp;
}

Cheers,
bzt