Index: arch/amd64/src/interrupt.c =================================================================== --- arch/amd64/src/interrupt.c (revision 086a600fe7c9cab7730f6c6d5879feb9121926be) +++ arch/amd64/src/interrupt.c (revision fb10289bf2bf13f3538082bb9a71b6d317f1c27c) @@ -43,5 +43,5 @@ #include - +/* static void messy_stack_trace(__native *stack) { @@ -58,5 +58,5 @@ printf("\n"); } - +*/ static void print_info_errcode(int n, void *st) { @@ -84,5 +84,5 @@ printf(" %Q, %Q, %Q\n", x[20], x[21], x[22]); printf(" %Q, %Q, %Q\n", x[23], x[24], x[25]); - messy_stack_trace(&x[5]); +// messy_stack_trace(&x[5]); } Index: generic/src/mm/slab.c =================================================================== --- generic/src/mm/slab.c (revision 086a600fe7c9cab7730f6c6d5879feb9121926be) +++ generic/src/mm/slab.c (revision fb10289bf2bf13f3538082bb9a71b6d317f1c27c) @@ -26,4 +26,58 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ + +/* + * The SLAB allocator is closely modelled after Opensolaris SLAB allocator + * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/ + * + * with the following exceptions: + * - empty SLABS are deallocated immediately + * (in Linux they are kept in linked list, in Solaris ???) + * - empty magazines are deallocated when not needed + * (in Solaris they are held in linked list in slab cache) + * + * Following features are not currently supported but would be easy to do: + * - cache coloring + * - dynamic magazine growing (different magazine sizes are already + * supported, but we would need to adjust allocating strategy) + * + * The SLAB allocator supports per-CPU caches ('magazines') to facilitate + * good SMP scaling. + * + * When a new object is being allocated, it is first checked, if it is + * available in CPU-bound magazine. If it is not found there, it is + * allocated from CPU-shared SLAB - if partial full is found, it is used, + * otherwise a new one is allocated. + * + * When an object is being deallocated, it is put to CPU-bound magazine. + * If there is no such magazine, new one is allocated (if it fails, + * the object is deallocated into SLAB). If the magazine is full, it is + * put into cpu-shared list of magazines and new one is allocated. + * + * The CPU-bound magazine is actually a pair of magazine to avoid + * thrashing when somebody is allocating/deallocating 1 item at the magazine + * size boundary. LIFO order is enforced, which should avoid fragmentation + * as much as possible. + * + * Every cache contains list of full slabs and list of partialy full slabs. + * Empty SLABS are immediately freed (thrashing will be avoided because + * of magazines). + * + * The SLAB information structure is kept inside the data area, if possible. + * The cache can be marked that it should not use magazines. This is used + * only for SLAB related caches to avoid deadlocks and infinite recursion + * (the SLAB allocator uses itself for allocating all it's control structures). + * + * The SLAB allocator allocates lot of space and does not free it. When + * frame allocator fails to allocate the frame, it calls slab_reclaim(). + * It tries 'light reclaim' first, then brutal reclaim. The light reclaim + * releases slabs from cpu-shared magazine-list, until at least 1 slab + * is deallocated in each cache (this algorithm should probably change). + * The brutal reclaim removes all cached objects, even from CPU-bound + * magazines. + * + * + */ + #include @@ -41,9 +95,20 @@ SPINLOCK_INITIALIZE(slab_cache_lock); -LIST_INITIALIZE(slab_cache_list); - -slab_cache_t mag_cache; - - +static LIST_INITIALIZE(slab_cache_list); + +/** Magazine cache */ +static slab_cache_t mag_cache; +/** Cache for cache descriptors */ +static slab_cache_t slab_cache_cache; + +/** Cache for external slab descriptors + * This time we want per-cpu cache, so do not make it static + * - using SLAB for internal SLAB structures will not deadlock, + * as all slab structures are 'small' - control structures of + * their caches do not require further allocation + */ +static slab_cache_t *slab_extern_cache; + +/** Slab descriptor */ typedef struct { slab_cache_t *cache; /**< Pointer to parent cache */ @@ -60,5 +125,4 @@ * Allocate frames for slab space and initialize * - * TODO: Change slab_t allocation to slab_alloc(????), malloc with flags!! */ static slab_t * slab_space_alloc(slab_cache_t *cache, int flags) @@ -77,5 +141,5 @@ } if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { - slab = malloc(sizeof(*slab)); // , flags); + slab = slab_alloc(slab_extern_cache, flags); if (!slab) { frame_free((__address)data); @@ -115,5 +179,5 @@ frame_free((__address)slab->start); if (! (cache->flags & SLAB_CACHE_SLINSIDE)) - free(slab); + slab_free(slab_extern_cache, slab); atomic_dec(&cache->allocated_slabs); @@ -244,4 +308,44 @@ /** + * 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) +{ + slab_magazine_t *cmag, *lastmag, *newmag; + + cmag = cache->mag_cache[CPU->id].current; + lastmag = cache->mag_cache[CPU->id].last; + if (cmag) { /* First try local CPU magazines */ + if (cmag->busy) + return cmag; + + if (lastmag && lastmag->busy) { + cache->mag_cache[CPU->id].current = lastmag; + cache->mag_cache[CPU->id].last = cmag; + return lastmag; + } + } + /* Local magazines are empty, import one from magazine list */ + spinlock_lock(&cache->lock); + if (list_empty(&cache->magazines)) { + spinlock_unlock(&cache->lock); + return NULL; + } + newmag = list_get_instance(cache->magazines.next, + slab_magazine_t, + link); + list_remove(&newmag->link); + spinlock_unlock(&cache->lock); + + if (lastmag) + slab_free(&mag_cache, lastmag); + cache->mag_cache[CPU->id].last = cmag; + cache->mag_cache[CPU->id].current = newmag; + return newmag; +} + +/** * Try to find object in CPU-cache magazines * @@ -255,35 +359,9 @@ spinlock_lock(&cache->mag_cache[CPU->id].lock); - mag = cache->mag_cache[CPU->id].current; - if (!mag) - goto out; - - if (!mag->busy) { - /* If current is empty && last exists && not empty, exchange */ - if (cache->mag_cache[CPU->id].last \ - && cache->mag_cache[CPU->id].last->busy) { - cache->mag_cache[CPU->id].current = cache->mag_cache[CPU->id].last; - cache->mag_cache[CPU->id].last = mag; - mag = cache->mag_cache[CPU->id].current; - goto gotit; - } - /* If still not busy, exchange current with some from - * other full magazines */ - spinlock_lock(&cache->lock); - if (list_empty(&cache->magazines)) { - spinlock_unlock(&cache->lock); - goto out; - } - /* Free current magazine and take one from list */ - slab_free(&mag_cache, mag); - - mag = list_get_instance(cache->magazines.next, - slab_magazine_t, - link); - list_remove(&mag->link); - - spinlock_unlock(&cache->lock); - } -gotit: + mag = get_full_current_mag(cache); + if (!mag) { + spinlock_unlock(&cache->mag_cache[CPU->id].lock); + return NULL; + } obj = mag->objs[--mag->busy]; spinlock_unlock(&cache->mag_cache[CPU->id].lock); @@ -291,12 +369,9 @@ return obj; -out: - spinlock_unlock(&cache->mag_cache[CPU->id].lock); - return NULL; } /** * Assure that the current magazine is empty, return pointer to it, or NULL if - * no empty magazine available and cannot be allocated + * no empty magazine is available and cannot be allocated * * We have 2 magazines bound to processor. @@ -355,6 +430,8 @@ mag = make_empty_current_mag(cache); - if (!mag) - goto errout; + if (!mag) { + spinlock_unlock(&cache->mag_cache[CPU->id].lock); + return -1; + } mag->objs[mag->busy++] = obj; @@ -363,7 +440,4 @@ atomic_inc(&cache->cached_objs); return 0; -errout: - spinlock_unlock(&cache->mag_cache[CPU->id].lock); - return -1; } @@ -461,5 +535,5 @@ slab_cache_t *cache; - cache = malloc(sizeof(*cache) + config.cpu_count*sizeof(cache->mag_cache[0])); + cache = slab_alloc(&slab_cache_cache, 0); _slab_cache_create(cache, name, size, align, constructor, destructor, flags); @@ -484,6 +558,8 @@ /* First lock all cpu caches, then the complete cache lock */ - for (i=0; i < config.cpu_count; i++) - spinlock_lock(&cache->mag_cache[i].lock); + if (flags & SLAB_RECLAIM_ALL) { + for (i=0; i < config.cpu_count; i++) + spinlock_lock(&cache->mag_cache[i].lock); + } spinlock_lock(&cache->lock); @@ -519,6 +595,8 @@ spinlock_unlock(&cache->lock); - for (i=0; i < config.cpu_count; i++) - spinlock_unlock(&cache->mag_cache[i].lock); + if (flags & SLAB_RECLAIM_ALL) { + for (i=0; i < config.cpu_count; i++) + spinlock_unlock(&cache->mag_cache[i].lock); + } return frames; @@ -543,5 +621,5 @@ spinlock_unlock(&slab_cache_lock); - free(cache); + slab_free(&slab_cache_cache, cache); } @@ -565,9 +643,8 @@ } + interrupts_restore(ipl); + if (result) atomic_inc(&cache->allocated_objs); - - interrupts_restore(ipl); - return result; @@ -588,6 +665,6 @@ spinlock_unlock(&cache->lock); } + interrupts_restore(ipl); atomic_dec(&cache->allocated_objs); - interrupts_restore(ipl); } @@ -640,5 +717,17 @@ sizeof(__address), NULL, NULL, - SLAB_CACHE_NOMAGAZINE); + SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); + /* Initialize slab_cache cache */ + _slab_cache_create(&slab_cache_cache, + "slab_cache", + sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]), + sizeof(__address), + NULL, NULL, + SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); + /* Initialize external slab cache */ + slab_extern_cache = slab_cache_create("slab_extern", + sizeof(slab_t), + 0, NULL, NULL, + SLAB_CACHE_SLINSIDE); /* Initialize structures for malloc */