Simple slab allocator in C

Question

Here is the plan:

• a slab takes up 1 page and it has PGSIZE / blocksize amount of blocks
• the minimum blocksize is 8 bytes, otherwise the pointer to the next block will get overwritten
• when a block is allocated, the free block is removed from the linked list
• when a block is freed, it is added back to the slab's free blocks linked list, but if the slab has no more blocks in use, free the whole slab
• the slab metadata is stored at the start of the slab, and the blocks come after it
• when allocating a block, the correct slab is found by iterating the linked list and comparing the slab block size, with the allocation size and checking if the slab has free blocks

And here is the code:

#include <stddef.h>
static struct slab* new_slab(size_t);
static struct block* block_alloc(struct slab*);
static void freeslab(struct slab *);
// block of memory, all the blocks of a slab
// are stored in a linked list
struct block {
 struct block *next;
};
struct slab {
 struct slab *next; // all slabs are in a linked list
 size_t size; // size of a block
 size_t refcount; // the amount of blocks that are in use
 struct block *freelist; // all the free blocks, if NULL the slab is all in use
};
static struct slab *slab_head; // linked list of slabs
static struct slab* new_slab(size_t size) {
 struct slab *slab;
 struct block *blk;
 size_t i = 1;
 // palloc(1) allocates one page, and returns the physical address
 // P2V converts it into a virtual address
 slab = (struct slab*) P2V((uintptr_t)palloc(1));
 slab->size = size;
 slab->refcount = 0;
 slab->next = slab_head;
 slab_head = slab;
 blk = (struct block*) ((char*)slab + sizeof(struct slab));
 slab->freelist = blk;
 // setup linked list of free blocks
 for (; (char*)blk < (char*)slab + PGSIZE; i++) {
 blk->next = (struct block*) ((char*)slab->freelist + (i * size));
 blk = blk->next;
 }
 return slab;
}
// allocate one block in the slab
static struct block* block_alloc(struct slab *slab) {
 struct block *blk;
 slab->refcount++;
 blk = slab->freelist;
 slab->freelist = slab->freelist->next;
 return blk;
};
// allocate 'size' amount of bytes
void* kalloc(size_t size) {
 struct slab *slab;
 // MIN block size is 8
 if (size < 8)
 size = 8;
 for (slab = slab_head; slab; slab = slab->next) {
 if (slab->size == size && slab->freelist)
 return (void*)block_alloc(slab);
 }
 // if there is no free slab for the corresponding size,
 // make a new slab
 slab = new_slab(size);
 // and then allocate a block in that slab
 return (void*)block_alloc(slab);
}
// free a block in a slab
void kfree(void *ptr) {
 struct slab* slab;
 struct block* blk = (struct block*)ptr;
 for (slab = slab_head; slab; slab = slab->next) {
 if ((void*)slab > ptr || (char*)ptr > ((char*)slab + PGSIZE))
 continue;
 // if refcount is already 0, it means the slab was already freed
 // and there can be no blocks in the slab
 if (slab->refcount == 0)
 panic("kfree, double free");
 slab->refcount--;
 // free the slab if there are no more blocks in use
 if (slab->refcount == 0)
 freeslab(slab);
 else {
 // otherwise add it to the linked list of free blocks
 blk->next = slab->freelist;
 slab->freelist = blk;
 }
 return;
 }
};
static void freeslab(struct slab *slab) {
 // free the page starting at address 'slab'
 // V2P converts it to a physical address
 freepg(V2P((uintptr_t)slab), 1);
}

Answer 1

Naming things

Names are mostly OK, but there are some inconsistencies. For example, new_slab() with an underscore versus freeslab() without one. Also, new_slab() is verb_noun(), but block_alloc() is noun_verb(). Try to be consistent, as that makes it much easier to remember what the names of your functions are.

Also, don't abbreviate unnecessarily. Instead of blk, you could just write block.

Unnecessary forward declarations

You are forward-declaring new_slab(), block_alloc() and freeslab(), but it doesn't look like that is necessary. I recommend you avoid forward declarations where possible, that way you don't have to repeat things unnecessarily, and it can avoid some types of errors (especially if you are using a C++ compiler).

Doesn't handle large sizes correctly

Your code doesn't handle requests for allocations close to or larger than PGSIZE correctly, as your slabs are always one page large. Either forbid large allocations by checking if size is not too large, or support large allocations by allocating multi-page slabs. Since you have a virtual memory system, the slabs don't have to be contiguous in physical memory.

Potential out of bounds access

When you are setting up the linked list of free blocks, your for-loop goes on as long as the pointer blk is within the page allocated for the slab. But depending on the requested size, this pointer could end up right before the end of the page, but then the block itself would extend outside of the page. You should take the size of a block into account:

for (; (char*)blk + size <= (char*)slab + PGSIZE; i++) {
 ...
}

Inefficiencies

While using a linked list for the blocks makes block_alloc() an \$O(1)\$ operation, using a linked list for the slabs is inefficient. If you have a lot of allocations of different sizes, the list of slabs will be long, and then every call to kalloc() and kfree() will require you to traverse this list.

Secondly, suppose I make many allocations, each with a different size. Then each allocation gets assigned its own slab. This makes the linked list of slabs long, and it wastes a lot of memory. It makes more sense to round up the requested size in some way (for example, to multiples of some value, or to a power of two), so slightly different sized allocations can share the same slab.

Incorrect freeing of slabs

If you detect that the refcount of a slab is zero, you call freeslab(). However, that code just frees the page, but it doesn't unlink the slab from the linked list of slabs. This means that subsequent calls to kalloc() or kfree() can read from a freed page, which could have been reallocated by something else and overwritten. Make sure you unlink slabs you are going to free, or alternatively, don't free them.

Safety

Consider calling kfree() with a pointer that is inside a valid slab, but not pointing to an allocated block. It could even point to some address between two blocks. Adding this back to the freelist will then cause corruption.

There's also the possibility that kfree() is called with a pointer that is not inside a slab. Your code silently ignores that case.

Either kfree() is only ever called with valid pointers (for example, only other kernel code can directly call it, and there are no bugs elsewhere), in which case you shouldn't have to do any error checking in kfree(), or it might be called with invalid pointers (maybe some call from userspace can pass a pointer that the kernel will pass on to kfree()), in which case you should thoroughly check that this pointer is valid and pointing to a currently allocated block.

Also consider whether it is safe to not zero the contents of a block before returning it from kalloc(). What if there is sensitive data in the memory that you return? You might not need to deal with this in your slab allocator, but instead let the caller deal with that at allocation or deallocation time, but it might make sense to do it here. You could also consider keeping kalloc() as it is, but adding a kzalloc() helper function that both allocates and zeroes.

• runningupthatroad: "Shouldn't you return a pointer to the space right after that pointer?" No, an in use block will just hold the data there's no need for it to point at a block
• G. Sliepen: I missed that! Then that is fine of course.