Slab Allocator

The Slab Allocator

The Linux kernel allocates many short-lived, fixed-size objects — inodes, dentries, task_structs, file descriptors. Calling a general-purpose allocator for each one would be slow and cause fragmentation.

The slab allocator (introduced by Jeff Bonwick, used in Linux since 1996) solves this with pre-allocated pools of identically-sized objects. Each slab holds N objects and a bitmap marking which slots are free:

slot:   0  1  2  3  4  5  6  7
used:   0  0  0  0  0  0  0  0   (0 = free, 1 = used)

Allocating finds the first 0 bit and sets it to 1. Freeing clears the bit.

Bitmap Operations

// Check if bit i is free
int bit_free(int bitmap, int i)   { return !(bitmap & (1 << i)); }

// Set bit i (mark used)
void bit_set(int *bitmap, int i)  { *bitmap |= (1 << i); }

// Clear bit i (mark free)
void bit_clr(int *bitmap, int i)  { *bitmap &= ~(1 << i); }

Your Implementation

Write int slab_alloc(int *bitmap, int n) that finds the first free slot (returns its index, or -1 if full), and void slab_free(int *bitmap, int idx) that frees a slot.

int slab_alloc(int *bitmap, int n) {
    for (int i = 0; i < n; i++)
        if (!(*bitmap & (1 << i))) { *bitmap |= (1 << i); return i; }
    return -1;
}

void slab_free(int *bitmap, int idx) {
    *bitmap &= ~(1 << idx);
}

Your Task

Implement slab_alloc and slab_free. Use an int as a 32-bit bitmap (supports up to 32 slots).