aboutsummaryrefslogtreecommitdiff
path: root/kernel/lib/slab_alloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/lib/slab_alloc.c')
-rw-r--r--kernel/lib/slab_alloc.c196
1 files changed, 106 insertions, 90 deletions
diff --git a/kernel/lib/slab_alloc.c b/kernel/lib/slab_alloc.c
index d9efc4f..8e8c0a3 100644
--- a/kernel/lib/slab_alloc.c
+++ b/kernel/lib/slab_alloc.c
@@ -5,24 +5,25 @@ typedef struct object {
} object_t;
typedef struct cache {
- struct { // pack this so that it takes less space...
- uint32_t is_a_cache : 1; // if not, this is a region allocated alone
- uint32_t n_free_objs : 31;
- };
+ void* region_addr;
+
+ uint32_t n_free_objs;
+ object_t* first_free_obj;
- union {
- struct { // when this is a cache
- object_t* first_free_obj;
- struct cache *next_cache;
- } c;
- struct { // when this is a region allocated alone
- size_t region_size;
- } sr;
- };
+ struct cache *next_cache; // next cache in this slab
+} cache_t;
+typedef struct region {
void* region_addr;
- struct cache *next_region;
-} cache_t;
+ size_t region_size;
+ struct region *next_region;
+} region_t;
+
+typedef union descriptor {
+ cache_t c;
+ region_t r;
+ union descriptor *next_free;
+} descriptor_t;
typedef struct slab {
cache_t *first_cache; // linked list of caches
@@ -31,8 +32,9 @@ typedef struct slab {
struct mem_allocator {
const slab_type_t *types;
slab_t *slabs;
- cache_t *first_free_region_descriptor;
- cache_t *all_caches, *all_other_regions;;
+
+ descriptor_t *first_free_descriptor;
+ region_t *all_regions;
page_alloc_fun_t alloc_fun;
page_free_fun_t free_fun;
@@ -42,23 +44,36 @@ struct mem_allocator {
// Helper functions for the manipulation of lists //
// ============================================== //
-void add_free_region_descriptor(mem_allocator_t *a, cache_t *c) {
- c->next_region = a->first_free_region_descriptor;
- a->first_free_region_descriptor = c;
+static void add_free_descriptor(mem_allocator_t *a, descriptor_t *c) {
+ c->next_free = a->first_free_descriptor;
+ a->first_free_descriptor = c;
}
-cache_t *take_region_descriptor(mem_allocator_t *a) {
- if (a->first_free_region_descriptor == 0) {
+static descriptor_t *take_descriptor(mem_allocator_t *a) {
+ if (a->first_free_descriptor == 0) {
void* p = a->alloc_fun(PAGE_SIZE);
if (p == 0) return 0;
- void* end = p + PAGE_SIZE;
- for (cache_t *i = (cache_t*)p; i + 1 <= (cache_t*)end; i++) {
- add_free_region_descriptor(a, i);
+ const void* end = p + PAGE_SIZE;
+ for (descriptor_t *i = (descriptor_t*)p; i + 1 <= (descriptor_t*)end; i++) {
+ add_free_descriptor(a, i);
}
+
+ // register the descriptor region
+ descriptor_t *dd = a->first_free_descriptor;
+ ASSERT(dd != 0);
+ a->first_free_descriptor = dd->next_free;
+
+ region_t *drd = &dd->r;
+ drd->region_addr = p;
+ drd->region_size = PAGE_SIZE;
+ drd->next_region = a->all_regions;
+ a->all_regions = drd;
}
- cache_t *x = a->first_free_region_descriptor;
- a->first_free_region_descriptor = x->next_region;
+
+ descriptor_t *x = a->first_free_descriptor;
+ ASSERT(x != 0);
+ a->first_free_descriptor = x->next_free;
return x;
}
@@ -71,7 +86,7 @@ mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_
void* addr;
mem_allocator_t *a;
slab_t *s;
- cache_t *c;
+ descriptor_t *d;
} ptr;
ptr.addr = af(PAGE_SIZE);
@@ -81,27 +96,28 @@ mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_
mem_allocator_t *a = ptr.a;
ptr.a++;
- a->all_caches = a->all_other_regions = 0;
+ a->all_regions = 0;
a->alloc_fun = af;
a->free_fun = ff;
a->types = types;
a->slabs = ptr.s;
for (const slab_type_t *t = types; t->obj_size != 0; t++) {
+ ASSERT(t->obj_size >= sizeof(object_t));
ptr.s->first_cache = 0;
ptr.s++;
}
- a->first_free_region_descriptor = 0;
- while ((void*)(ptr.c + 1) <= end_addr) {
- add_free_region_descriptor(a, ptr.c);
- ptr.c++;
+ a->first_free_descriptor = 0;
+ while ((void*)(ptr.d + 1) <= end_addr) {
+ add_free_descriptor(a, ptr.d);
+ ptr.d++;
}
return a;
}
-static void stack_and_destroy_regions(page_free_fun_t ff, cache_t *r) {
+static void stack_and_destroy_regions(page_free_fun_t ff, region_t *r) {
if (r == 0) return;
void* addr = r->region_addr;
ASSERT(r != r->next_region);
@@ -109,8 +125,12 @@ static void stack_and_destroy_regions(page_free_fun_t ff, cache_t *r) {
ff(addr);
}
void destroy_slab_allocator(mem_allocator_t *a) {
- stack_and_destroy_regions(a->free_fun, a->all_caches);
- stack_and_destroy_regions(a->free_fun, a->all_other_regions);
+ for (int i = 0; a->types[i].obj_size != 0; i++) {
+ for (cache_t *c = a->slabs[i].first_cache; c != 0; c++) {
+ a->free_fun(c->region_addr);
+ }
+ }
+ stack_and_destroy_regions(a->free_fun, a->all_regions);
a->free_fun(a);
}
@@ -121,61 +141,66 @@ void* slab_alloc(mem_allocator_t* a, size_t sz) {
// find a cache with free space
cache_t *fc = a->slabs[i].first_cache;
while (fc != 0 && fc->n_free_objs == 0) {
- ASSERT(fc->c.first_free_obj == 0); // make sure n_free == 0 iff no object in the free stack
- fc = fc->c.next_cache;
+ ASSERT(fc->first_free_obj == 0); // make sure n_free == 0 iff no object in the free stack
+ fc = fc->next_cache;
}
// if none found, try to allocate a new one
if (fc == 0) {
- fc = take_region_descriptor(a);
- if (fc == 0) return 0;
+ descriptor_t *fcd = take_descriptor(a);
+ if (fcd == 0) return 0;
+
+ fc = &fcd->c;
+ ASSERT((descriptor_t*)fc == fcd);
const size_t cache_size = a->types[i].pages_per_cache * PAGE_SIZE;
fc->region_addr = a->alloc_fun(cache_size);
if (fc->region_addr == 0) {
- add_free_region_descriptor(a, fc);
+ add_free_descriptor(a, fcd);
return 0;
}
- fc->is_a_cache = 1;
fc->n_free_objs = 0;
- fc->c.first_free_obj = 0;
- for (void* i = fc->region_addr; i + obj_size <= fc->region_addr + cache_size; i += obj_size) {
- object_t *x = (object_t*)i;
- x->next = fc->c.first_free_obj;
- fc->c.first_free_obj = x;
+ fc->first_free_obj = 0;
+ for (void* p = fc->region_addr; p + obj_size <= fc->region_addr + cache_size; p += obj_size) {
+ object_t *x = (object_t*)p;
+ x->next = fc->first_free_obj;
+ fc->first_free_obj = x;
fc->n_free_objs++;
}
ASSERT(fc->n_free_objs == cache_size / obj_size);
- fc->next_region = a->all_caches;
- a->all_caches = fc;
- fc->c.next_cache = a->slabs[i].first_cache;
+ fc->next_cache = a->slabs[i].first_cache;
a->slabs[i].first_cache = fc;
}
// allocate on fc
ASSERT(fc != 0 && fc->n_free_objs > 0);
- object_t *x = fc->c.first_free_obj;
- fc->c.first_free_obj = x->next;
+
+ object_t *x = fc->first_free_obj;
+ fc->first_free_obj = x->next;
fc->n_free_objs--;
+
+ ASSERT((fc->n_free_objs == 0) == (fc->first_free_obj == 0));
+
// TODO : if fc is full, put it at the end
return x;
}
}
// otherwise directly allocate using a->alloc_fun
- cache_t *r = take_region_descriptor(a);
- if (r == 0) return 0;
+ descriptor_t *rd = take_descriptor(a);
+ if (rd == 0) return 0;
+ region_t *r = &rd->r;
+ ASSERT((descriptor_t*)r == rd);
r->region_addr = a->alloc_fun(sz);
if (r->region_addr == 0) {
- add_free_region_descriptor(a, r);
+ add_free_descriptor(a, rd);
return 0;
} else {
- r->is_a_cache = 0;
- r->sr.region_size = sz;
+ r->region_size = sz;
- r->next_region = a->all_other_regions;
- a->all_other_regions = r;
+ r->next_region = a->all_regions;
+ a->all_regions = r;
return (void*)r->region_addr;
}
@@ -185,39 +210,29 @@ void slab_free(mem_allocator_t* a, void* addr) {
for (int i = 0; a->types[i].obj_size != 0; i++) {
size_t region_size = PAGE_SIZE * a->types[i].pages_per_cache;
- for (cache_t *r = a->slabs[i].first_cache; r != 0; r = r->c.next_cache) {
+ for (cache_t *r = a->slabs[i].first_cache; r != 0; r = r->next_cache) {
if (addr >= r->region_addr && addr < r->region_addr + region_size) {
ASSERT((addr - r->region_addr) % a->types[i].obj_size == 0);
- ASSERT(r->is_a_cache);
+
object_t *o = (object_t*)addr;
- o->next = r->c.first_free_obj;
- r->c.first_free_obj = o;
+ o->next = r->first_free_obj;
+ r->first_free_obj = o;
r->n_free_objs++;
if (r->n_free_objs == region_size / a->types[i].obj_size) {
// region is completely unused, free it.
if (a->slabs[i].first_cache == r) {
- a->slabs[i].first_cache = r->c.next_cache;
- } else {
- for (cache_t *it = a->slabs[i].first_cache; it->c.next_cache != 0; it = it->c.next_cache) {
- if (it->c.next_cache == r) {
- it->c.next_cache = r->c.next_cache;
- break;
- }
- }
- }
- if (a->all_caches == r) {
- a->all_caches = r->next_region;
+ a->slabs[i].first_cache = r->next_cache;
} else {
- for (cache_t *it = a->all_caches; it->next_region != 0; it = it->next_region) {
- if (it->next_region == r) {
- it->next_region = r->next_region;
+ for (cache_t *it = a->slabs[i].first_cache; it->next_cache != 0; it = it->next_cache) {
+ if (it->next_cache == r) {
+ it->next_cache = r->next_cache;
break;
}
}
}
a->free_fun(r->region_addr);
- add_free_region_descriptor(a, r);
+ add_free_descriptor(a, (descriptor_t*)r);
}
return;
}
@@ -225,21 +240,22 @@ void slab_free(mem_allocator_t* a, void* addr) {
}
// otherwise the block was directly allocated : look for it in regions.
- a->free_fun(addr);
- ASSERT(a->all_other_regions != 0);
-
- if (a->all_other_regions->region_addr == addr) {
- cache_t *r = a->all_other_regions;
- ASSERT(r->is_a_cache == 0);
- a->all_other_regions = r->next_region;
- add_free_region_descriptor(a, r);
+ ASSERT(a->all_regions != 0);
+
+ if (a->all_regions->region_addr == addr) {
+ a->free_fun(addr); // found it, free it
+
+ region_t *r = a->all_regions;
+ a->all_regions = r->next_region;
+ add_free_descriptor(a, (descriptor_t*)r);
} else {
- for (cache_t *i = a->all_other_regions; i->next_region != 0; i = i->next_region) {
+ for (region_t *i = a->all_regions; i->next_region != 0; i = i->next_region) {
if (i->next_region->region_addr == addr) {
- cache_t *r = i->next_region;
- ASSERT(r->is_a_cache == 0);
+ a->free_fun(addr); // found it, free it
+
+ region_t *r = i->next_region;
i->next_region = r->next_region;
- add_free_region_descriptor(a, r);
+ add_free_descriptor(a, (descriptor_t*)r);
return;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 20:44:27 +0000