WebSVN – HelenOS – Diff – /branches/dd/kernel/generic/src/mm/slab.c

 /**
  * Allocate frames for slab space and initialize
+ *
  */
-static slab_t * slab_space_alloc(slab_cache_t *cache, int flags)
+static slab_t *slab_space_alloc(slab_cache_t *cache, int flags)
+{
     void *data;
     slab_t *slab;
     size_t fsize;
     unsigned int i;
-    unsigned int zone = 0;
+    count_t zone = 0;
     data = frame_alloc_generic(cache->order, FRAME_KA | flags, &zone);
     if (!data) {
         return NULL;
+    }
-    if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {
+    if (!(cache->flags & SLAB_CACHE_SLINSIDE)) {
         slab = slab_alloc(slab_extern_cache, flags);
         if (!slab) {
             frame_free(KA2PA(data));
             return NULL;
+        }
     slab->available = cache->objects;
     slab->nextavail = 0;
     slab->cache = cache;
     for (i = 0; i < cache->objects; i++)
-        *((int *) (slab->start + i*cache->size)) = i+1;
+        *((int *) (slab->start + i*cache->size)) = i + 1;
     atomic_inc(&cache->allocated_slabs);
     return slab;
+}
+ *
  * @param slab If the caller knows directly slab of the object, otherwise NULL
+ *
  * @return Number of freed pages
  */
-static count_t slab_obj_destroy(slab_cache_t *cache, void *obj,
+static count_t slab_obj_destroy(slab_cache_t *cache, void *obj, slab_t *slab)
-                slab_t *slab)
+{
     int freed = 0;
     if (!slab)
         slab = obj2slab(obj);
     spinlock_lock(&cache->slablock);
     ASSERT(slab->available < cache->objects);
     *((int *)obj) = slab->nextavail;
-    slab->nextavail = (obj - slab->start)/cache->size;
+    slab->nextavail = (obj - slab->start) / cache->size;
     slab->available++;
     /* Move it to correct list */
     if (slab->available == cache->objects) {
         /* Free associated memory */
 /**
  * Take new object from slab or create new if needed
+ *
  * @return Object address or null
  */
-static void * slab_obj_create(slab_cache_t *cache, int flags)
+static void *slab_obj_create(slab_cache_t *cache, int flags)
+{
     slab_t *slab;
     void *obj;
     spinlock_lock(&cache->slablock);
         slab = slab_space_alloc(cache, flags);
         if (!slab)
             return NULL;
         spinlock_lock(&cache->slablock);
     } else {
-        slab = list_get_instance(cache->partial_slabs.next, slab_t, link);
+        slab = list_get_instance(cache->partial_slabs.next, slab_t,
+            link);
         list_remove(&slab->link);
+    }
     obj = slab->start + slab->nextavail * cache->size;
     slab->nextavail = *((int *)obj);
     slab->available--;
  * Finds a full magazine in cache, takes it from list
  * and returns it
+ *
  * @param first If true, return first, else last mag
  */
-static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache,
+static slab_magazine_t *get_mag_from_cache(slab_cache_t *cache, int first)
-                        int first)
+{
     slab_magazine_t *mag = NULL;
     link_t *cur;
     spinlock_lock(&cache->maglock);
 /**
  * Free all objects in magazine and free memory associated with magazine
+ *
  * @return Number of freed pages
  */
-static count_t magazine_destroy(slab_cache_t *cache,
+static count_t magazine_destroy(slab_cache_t *cache, slab_magazine_t *mag)
-                slab_magazine_t *mag)
+{
     unsigned int i;
     count_t frames = 0;
     for (i = 0; i < mag->busy; i++) {
 /**
  * Find full magazine, set it as current and return it
+ *
  * Assume cpu_magazine lock is held
  */
-static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)
+static slab_magazine_t *get_full_current_mag(slab_cache_t *cache)
+{
     slab_magazine_t *cmag, *lastmag, *newmag;
     cmag = cache->mag_cache[CPU->id].current;
     lastmag = cache->mag_cache[CPU->id].last;
 /**
  * Try to find object in CPU-cache magazines
+ *
  * @return Pointer to object or NULL if not available
  */
-static void * magazine_obj_get(slab_cache_t *cache)
+static void *magazine_obj_get(slab_cache_t *cache)
+{
     slab_magazine_t *mag;
     void *obj;
     if (!CPU)
  *  If full, try the last.
  *   If full, put to magazines list.
  *   allocate new, exchange last & current
+ *
  */
-static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)
+static slab_magazine_t *make_empty_current_mag(slab_cache_t *cache)
+{
     slab_magazine_t *cmag,*lastmag,*newmag;
     cmag = cache->mag_cache[CPU->id].current;
     lastmag = cache->mag_cache[CPU->id].last;
 /** Return number of objects that fit in certain cache size */
 static unsigned int comp_objects(slab_cache_t *cache)
+{
     if (cache->flags & SLAB_CACHE_SLINSIDE)
-        return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size;
+        return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) /
+            cache->size;
     else
         return (PAGE_SIZE << cache->order) / cache->size;
+}
 /** Return wasted space in slab */
+{
     unsigned int i;
     ASSERT(_slab_initialized >= 2);
-    cache->mag_cache = malloc(sizeof(slab_mag_cache_t)*config.cpu_count,0);
+    cache->mag_cache = malloc(sizeof(slab_mag_cache_t) * config.cpu_count,
+);
     for (i = 0; i < config.cpu_count; i++) {
-        memsetb((uintptr_t)&cache->mag_cache[i],
+        memsetb(&cache->mag_cache[i], sizeof(cache->mag_cache[i]), 0);
-            sizeof(cache->mag_cache[i]), 0);
+        spinlock_initialize(&cache->mag_cache[i].lock,
-        spinlock_initialize(&cache->mag_cache[i].lock, "slab_maglock_cpu");
+            "slab_maglock_cpu");
+    }
+}
 /** Initialize allocated memory as a slab cache */
 static void
-_slab_cache_create(slab_cache_t *cache,
+_slab_cache_create(slab_cache_t *cache, char *name, size_t size, size_t align,
-           char *name,
-           size_t size,
-           size_t align,
-           int (*constructor)(void *obj, int kmflag),
+    int (*constructor)(void *obj, int kmflag), int (*destructor)(void *obj),
-           int (*destructor)(void *obj),
-           int flags)
+    int flags)
+{
     int pages;
     ipl_t ipl;
-    memsetb((uintptr_t)cache, sizeof(*cache), 0);
+    memsetb(cache, sizeof(*cache), 0);
     cache->name = name;
     if (align < sizeof(unative_t))
         align = sizeof(unative_t);
     size = ALIGN_UP(size, align);
     list_initialize(&cache->full_slabs);
     list_initialize(&cache->partial_slabs);
     list_initialize(&cache->magazines);
     spinlock_initialize(&cache->slablock, "slab_lock");
     spinlock_initialize(&cache->maglock, "slab_maglock");
-    if (! (cache->flags & SLAB_CACHE_NOMAGAZINE))
+    if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
         make_magcache(cache);
     /* Compute slab sizes, object counts in slabs etc. */
     if (cache->size < SLAB_INSIDE_SIZE)
         cache->flags |= SLAB_CACHE_SLINSIDE;
     pages = SIZE2FRAMES(cache->size);
     /* We need the 2^order >= pages */
     if (pages == 1)
         cache->order = 0;
     else
-        cache->order = fnzb(pages-1)+1;
+        cache->order = fnzb(pages - 1) + 1;
     while (badness(cache) > SLAB_MAX_BADNESS(cache)) {
         cache->order += 1;
+    }
     cache->objects = comp_objects(cache);
     spinlock_unlock(&slab_cache_lock);
     interrupts_restore(ipl);
+}
 /** Create slab cache  */
-slab_cache_t * slab_cache_create(char *name,
-                 size_t size,
+slab_cache_t *
-                 size_t align,
+slab_cache_create(char *name, size_t size, size_t align,
-                 int (*constructor)(void *obj, int kmflag),
+    int (*constructor)(void *obj, int kmflag), int (*destructor)(void *obj),
-                 int (*destructor)(void *obj),
-                 int flags)
+    int flags)
+{
     slab_cache_t *cache;
     cache = slab_alloc(&slab_cache_cache, 0);
     _slab_cache_create(cache, name, size, align, constructor, destructor,
-               flags);
+        flags);
     return cache;
+}
 /**
  * Reclaim space occupied by objects that are already free
     /* We count up to original magazine count to avoid
      * endless loop
      */
     magcount = atomic_get(&cache->magazine_counter);
-    while (magcount-- && (mag=get_mag_from_cache(cache,0))) {
+    while (magcount-- && (mag=get_mag_from_cache(cache, 0))) {
         frames += magazine_destroy(cache,mag);
         if (!(flags & SLAB_RECLAIM_ALL) && frames)
             break;
+    }
     /* Destroy all magazines */
     _slab_reclaim(cache, SLAB_RECLAIM_ALL);
     /* All slabs must be empty */
-    if (!list_empty(&cache->full_slabs) \
+    if (!list_empty(&cache->full_slabs) ||
-        || !list_empty(&cache->partial_slabs))
+        !list_empty(&cache->partial_slabs))
         panic("Destroying cache that is not empty.");
     if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
         free(cache->mag_cache);
     slab_free(&slab_cache_cache, cache);
+}
-/** Allocate new object from cache - if no flags given, always returns
+/** Allocate new object from cache - if no flags given, always returns memory */
-    memory */
-void * slab_alloc(slab_cache_t *cache, int flags)
+void *slab_alloc(slab_cache_t *cache, int flags)
+{
     ipl_t ipl;
     void *result = NULL;
     /* Disable interrupts to avoid deadlocks with interrupt handlers */
+{
     ipl_t ipl;
     ipl = interrupts_disable();
-    if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \
+    if ((cache->flags & SLAB_CACHE_NOMAGAZINE) ||
-        || magazine_obj_put(cache, obj)) {
+        magazine_obj_put(cache, obj)) {
         slab_obj_destroy(cache, obj, slab);
+    }
     interrupts_restore(ipl);
     atomic_dec(&cache->allocated_objs);
     /* TODO: Add assert, that interrupts are disabled, otherwise
      * memory allocation from interrupts can deadlock.
      */
-    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
+    for (cur = slab_cache_list.next; cur != &slab_cache_list;
+        cur = cur->next) {
         cache = list_get_instance(cur, slab_cache_t, link);
         frames += _slab_reclaim(cache, flags);
+    }
     spinlock_unlock(&slab_cache_lock);
 /* Print list of slabs */
 void slab_print_list(void)
+{
+    int skip = 0;
+    printf("slab name        size     pages  obj/pg slabs  cached allocated"
+        " ctl\n");
+    printf("---------------- -------- ------ ------ ------ ------ ---------"
+        " ---\n");
+    while (true) {
-    slab_cache_t *cache;
+        slab_cache_t *cache;
-    link_t *cur;
+        link_t *cur;
-    ipl_t ipl;
+        ipl_t ipl;
+        int i;
+        /*
+         * We must not hold the slab_cache_lock spinlock when printing
+         * the statistics. Otherwise we can easily deadlock if the print
+         * needs to allocate memory.
+         *
+         * Therefore, we walk through the slab cache list, skipping some
+         * amount of already processed caches during each iteration and
+         * gathering statistics about the first unprocessed cache. For
+         * the sake of printing the statistics, we realese the
+         * slab_cache_lock and reacquire it afterwards. Then the walk
+         * starts again.
+         *
+         * This limits both the efficiency and also accuracy of the
+         * obtained statistics. The efficiency is decreased because the
+         * time complexity of the algorithm is quadratic instead of
+         * linear. The accuracy is impacted because we drop the lock
+         * after processing one cache. If there is someone else
+         * manipulating the cache list, we might omit an arbitrary
+         * number of caches or process one cache multiple times.
+         * However, we don't bleed for this algorithm for it is only
+         * statistics.
+         */
-    ipl = interrupts_disable();
+        ipl = interrupts_disable();
-    spinlock_lock(&slab_cache_lock);
+        spinlock_lock(&slab_cache_lock);
-    printf("slab name        size     pages  obj/pg slabs  cached allocated ctl\n");
+        for (i = 0, cur = slab_cache_list.next;
-    printf("---------------- -------- ------ ------ ------ ------ --------- ---\n");
+            i < skip && cur != &slab_cache_list;
+            i++, cur = cur->next)
+            ;
-    for (cur = slab_cache_list.next; cur != &slab_cache_list; cur = cur->next) {
+        if (cur == &slab_cache_list) {
+            spinlock_unlock(&slab_cache_lock);
+            interrupts_restore(ipl);
+            break;
+        }
+        skip++;
         cache = list_get_instance(cur, slab_cache_t, link);
+        char *name = cache->name;
+        uint8_t order = cache->order;
+        size_t size = cache->size;
+        unsigned int objects = cache->objects;
+        long allocated_slabs = atomic_get(&cache->allocated_slabs);
+        long cached_objs = atomic_get(&cache->cached_objs);
+        long allocated_objs = atomic_get(&cache->allocated_objs);
+        int flags = cache->flags;
+        spinlock_unlock(&slab_cache_lock);
+        interrupts_restore(ipl);
+        printf("%-16s %8" PRIs " %6d %6u %6ld %6ld %9ld %-3s\n",
+            name, size, (1 << order), objects, allocated_slabs,
+            cached_objs, allocated_objs,
-        printf("%-16s %8zd %6zd %6zd %6zd %6zd %9zd %-3s\n", cache->name, cache->size, (1 << cache->order), cache->objects, atomic_get(&cache->allocated_slabs), atomic_get(&cache->cached_objs), atomic_get(&cache->allocated_objs), cache->flags & SLAB_CACHE_SLINSIDE ? "in" : "out");
+            flags & SLAB_CACHE_SLINSIDE ? "in" : "out");
+    }
-    spinlock_unlock(&slab_cache_lock);
-    interrupts_restore(ipl);
+}
 void slab_cache_init(void)
+{
     int i, size;
     /* Initialize magazine cache */
-    _slab_cache_create(&mag_cache,
+    _slab_cache_create(&mag_cache, "slab_magazine",
-               "slab_magazine",
-               sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*),
+        sizeof(slab_magazine_t) + SLAB_MAG_SIZE * sizeof(void*),
-               sizeof(uintptr_t),
+        sizeof(uintptr_t), NULL, NULL, SLAB_CACHE_NOMAGAZINE |
-               NULL, NULL,
-               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
+        SLAB_CACHE_SLINSIDE);
     /* Initialize slab_cache cache */
-    _slab_cache_create(&slab_cache_cache,
+    _slab_cache_create(&slab_cache_cache, "slab_cache",
-               "slab_cache",
-               sizeof(slab_cache_cache),
+        sizeof(slab_cache_cache), sizeof(uintptr_t), NULL, NULL,
-               sizeof(uintptr_t),
-               NULL, NULL,
-               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
+        SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
     /* Initialize external slab cache */
-    slab_extern_cache = slab_cache_create("slab_extern",
+    slab_extern_cache = slab_cache_create("slab_extern", sizeof(slab_t), 0,
-                          sizeof(slab_t),
-, NULL, NULL,
-                          SLAB_CACHE_SLINSIDE | SLAB_CACHE_MAGDEFERRED);
+        NULL, NULL, SLAB_CACHE_SLINSIDE | SLAB_CACHE_MAGDEFERRED);
     /* Initialize structures for malloc */
-    for (i=0, size=(1<<SLAB_MIN_MALLOC_W);
+    for (i = 0, size = (1 << SLAB_MIN_MALLOC_W);
-         i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1);
+        i < (SLAB_MAX_MALLOC_W - SLAB_MIN_MALLOC_W + 1);
-         i++, size <<= 1) {
+        i++, size <<= 1) {
-        malloc_caches[i] = slab_cache_create(malloc_names[i],
+        malloc_caches[i] = slab_cache_create(malloc_names[i], size, 0,
-                             size, 0,
-                             NULL,NULL, SLAB_CACHE_MAGDEFERRED);
+            NULL, NULL, SLAB_CACHE_MAGDEFERRED);
+    }
 #ifdef CONFIG_DEBUG
     _slab_initialized = 1;
 #endif
+}
     _slab_initialized = 2;
 #endif
     spinlock_lock(&slab_cache_lock);
-    for (cur=slab_cache_list.next; cur != &slab_cache_list;cur=cur->next){
+    for (cur = slab_cache_list.next; cur != &slab_cache_list;
+        cur = cur->next){
         s = list_get_instance(cur, slab_cache_t, link);
-        if ((s->flags & SLAB_CACHE_MAGDEFERRED) != SLAB_CACHE_MAGDEFERRED)
+        if ((s->flags & SLAB_CACHE_MAGDEFERRED) !=
+            SLAB_CACHE_MAGDEFERRED)
             continue;
         make_magcache(s);
         s->flags &= ~SLAB_CACHE_MAGDEFERRED;
+    }
     spinlock_unlock(&slab_cache_lock);
+}
 /**************************************/
 /* kalloc/kfree functions             */
-void * malloc(unsigned int size, int flags)
+void *malloc(unsigned int size, int flags)
+{
     ASSERT(_slab_initialized);
     ASSERT(size && size <= (1 << SLAB_MAX_MALLOC_W));
     if (size < (1 << SLAB_MIN_MALLOC_W))
     int idx = fnzb(size - 1) - SLAB_MIN_MALLOC_W + 1;
     return slab_alloc(malloc_caches[idx], flags);
+}
-void * realloc(void *ptr, unsigned int size, int flags)
+void *realloc(void *ptr, unsigned int size, int flags)
+{
     ASSERT(_slab_initialized);
     ASSERT(size <= (1 << SLAB_MAX_MALLOC_W));
     void *new_ptr;

Subversion Repositories HelenOS

(root)/branches/dd/kernel/generic/src/mm/slab.c – Rev 3022 → 4055