slab allocator question

Question about which tools to use, bugs, the best way to implement a function, etc should go here. Don't forget to see if your question is answered in the wiki first! When in doubt post here.
Post Reply
ITchimp
Member
Member
Posts: 134
Joined: Sat Aug 18, 2018 8:44 pm

slab allocator question

Post by 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?
User avatar
bzt
Member
Member
Posts: 1584
Joined: Thu Oct 13, 2016 4:55 pm
Contact:

Re: slab allocator question

Post by bzt »

ITchimp wrote: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.
ITchimp wrote: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.
ITchimp wrote: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).
ITchimp wrote:/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
User avatar
iansjack
Member
Member
Posts: 4703
Joined: Sat Mar 31, 2012 3:07 am
Location: Chichester, UK

Re: slab allocator question

Post by 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
Member
Member
Posts: 134
Joined: Sat Aug 18, 2018 8:44 pm

Re: slab allocator question

Post by 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...
User avatar
bzt
Member
Member
Posts: 1584
Joined: Thu Oct 13, 2016 4:55 pm
Contact:

Re: slab allocator question

Post by bzt »

iansjack wrote: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.
ITchimp wrote: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
User avatar
iansjack
Member
Member
Posts: 4703
Joined: Sat Mar 31, 2012 3:07 am
Location: Chichester, UK

Re: slab allocator question

Post by iansjack »

We're talking about home-brew OSs here, not Linux, not POSIX, not even libc. Anything is possible!
User avatar
bzt
Member
Member
Posts: 1584
Joined: Thu Oct 13, 2016 4:55 pm
Contact:

Re: slab allocator question

Post by bzt »

iansjack wrote: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
Post Reply