Subversion Repositories HelenOS-historic

Rev

Rev 1224 | Rev 1428 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1224 Rev 1248
Line 24... Line 24...
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
27
 */
28
 
28
 
29
/*
29
/**
-
 
30
 * @file    slab.c
-
 
31
 * @brief   Slab allocator.
-
 
32
 *
30
 * The SLAB allocator is closely modelled after OpenSolaris SLAB allocator
33
 * The slab allocator is closely modelled after OpenSolaris slab allocator.
31
 * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
34
 * @see http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
32
 *
35
 *
33
 * with the following exceptions:
36
 * with the following exceptions:
34
 *   - empty SLABS are deallocated immediately
37
 * @li empty slabs are deallocated immediately
35
 *     (in Linux they are kept in linked list, in Solaris ???)
38
 *     (in Linux they are kept in linked list, in Solaris ???)
36
 *   - empty magazines are deallocated when not needed
39
 * @li empty magazines are deallocated when not needed
37
 *     (in Solaris they are held in linked list in slab cache)
40
 *     (in Solaris they are held in linked list in slab cache)
38
 *
41
 *
39
 *   Following features are not currently supported but would be easy to do:
42
 * Following features are not currently supported but would be easy to do:
40
 *   - cache coloring
43
 * @li cache coloring
41
 *   - dynamic magazine growing (different magazine sizes are already
44
 * @li dynamic magazine growing (different magazine sizes are already
42
 *     supported, but we would need to adjust allocation strategy)
45
 *     supported, but we would need to adjust allocation strategy)
43
 *
46
 *
44
 * The SLAB allocator supports per-CPU caches ('magazines') to facilitate
47
 * The slab allocator supports per-CPU caches ('magazines') to facilitate
45
 * good SMP scaling.
48
 * good SMP scaling.
46
 *
49
 *
47
 * When a new object is being allocated, it is first checked, if it is
50
 * When a new object is being allocated, it is first checked, if it is
48
 * available in CPU-bound magazine. If it is not found there, it is
51
 * available in CPU-bound magazine. If it is not found there, it is
49
 * allocated from CPU-shared SLAB - if partial full is found, it is used,
52
 * allocated from CPU-shared slab - if partial full is found, it is used,
50
 * otherwise a new one is allocated.
53
 * otherwise a new one is allocated.
51
 *
54
 *
52
 * When an object is being deallocated, it is put to CPU-bound magazine.
55
 * When an object is being deallocated, it is put to CPU-bound magazine.
53
 * If there is no such magazine, new one is allocated (if it fails,
56
 * If there is no such magazine, new one is allocated (if it fails,
54
 * the object is deallocated into SLAB). If the magazine is full, it is
57
 * the object is deallocated into slab). If the magazine is full, it is
55
 * put into cpu-shared list of magazines and new one is allocated.
58
 * put into cpu-shared list of magazines and new one is allocated.
56
 *
59
 *
57
 * The CPU-bound magazine is actually a pair of magazine to avoid
60
 * The CPU-bound magazine is actually a pair of magazine to avoid
58
 * thrashing when somebody is allocating/deallocating 1 item at the magazine
61
 * thrashing when somebody is allocating/deallocating 1 item at the magazine
59
 * size boundary. LIFO order is enforced, which should avoid fragmentation
62
 * size boundary. LIFO order is enforced, which should avoid fragmentation
60
 * as much as possible.
63
 * as much as possible.
61
 *  
64
 *  
62
 * Every cache contains list of full slabs and list of partialy full slabs.
65
 * Every cache contains list of full slabs and list of partialy full slabs.
63
 * Empty SLABS are immediately freed (thrashing will be avoided because
66
 * Empty slabs are immediately freed (thrashing will be avoided because
64
 * of magazines).
67
 * of magazines).
65
 *
68
 *
66
 * The SLAB information structure is kept inside the data area, if possible.
69
 * The slab information structure is kept inside the data area, if possible.
67
 * The cache can be marked that it should not use magazines. This is used
70
 * The cache can be marked that it should not use magazines. This is used
68
 * only for SLAB related caches to avoid deadlocks and infinite recursion
71
 * only for slab related caches to avoid deadlocks and infinite recursion
69
 * (the SLAB allocator uses itself for allocating all it's control structures).
72
 * (the slab allocator uses itself for allocating all it's control structures).
70
 *
73
 *
71
 * The SLAB allocator allocates lot of space and does not free it. When
74
 * The slab allocator allocates lot of space and does not free it. When
72
 * frame allocator fails to allocate the frame, it calls slab_reclaim().
75
 * frame allocator fails to allocate the frame, it calls slab_reclaim().
73
 * It tries 'light reclaim' first, then brutal reclaim. The light reclaim
76
 * It tries 'light reclaim' first, then brutal reclaim. The light reclaim
74
 * releases slabs from cpu-shared magazine-list, until at least 1 slab
77
 * releases slabs from cpu-shared magazine-list, until at least 1 slab
75
 * is deallocated in each cache (this algorithm should probably change).
78
 * is deallocated in each cache (this algorithm should probably change).
76
 * The brutal reclaim removes all cached objects, even from CPU-bound
79
 * The brutal reclaim removes all cached objects, even from CPU-bound
77
 * magazines.
80
 * magazines.
78
 *
81
 *
-
 
82
 * TODO:@n
79
 * TODO: For better CPU-scaling the magazine allocation strategy should
83
 * For better CPU-scaling the magazine allocation strategy should
80
 * be extended. Currently, if the cache does not have magazine, it asks
84
 * be extended. Currently, if the cache does not have magazine, it asks
81
 * for non-cpu cached magazine cache to provide one. It might be feasible
85
 * for non-cpu cached magazine cache to provide one. It might be feasible
82
 * to add cpu-cached magazine cache (which would allocate it's magazines
86
 * to add cpu-cached magazine cache (which would allocate it's magazines
83
 * from non-cpu-cached mag. cache). This would provide a nice per-cpu
87
 * from non-cpu-cached mag. cache). This would provide a nice per-cpu
84
 * buffer. The other possibility is to use the per-cache
88
 * buffer. The other possibility is to use the per-cache
85
 * 'empty-magazine-list', which decreases competing for 1 per-system
89
 * 'empty-magazine-list', which decreases competing for 1 per-system
86
 * magazine cache.
90
 * magazine cache.
87
 *
91
 *
88
 * - it might be good to add granularity of locks even to slab level,
92
 * @li it might be good to add granularity of locks even to slab level,
89
 *   we could then try_spinlock over all partial slabs and thus improve
93
 *     we could then try_spinlock over all partial slabs and thus improve
90
 *   scalability even on slab level
94
 *     scalability even on slab level
91
 */
95
 */
92
 
96
 
93
 
-
 
94
#include <synch/spinlock.h>
97
#include <synch/spinlock.h>
95
#include <mm/slab.h>
98
#include <mm/slab.h>
96
#include <adt/list.h>
99
#include <adt/list.h>
97
#include <memstr.h>
100
#include <memstr.h>
98
#include <align.h>
101
#include <align.h>
Line 111... Line 114...
111
static slab_cache_t mag_cache;
114
static slab_cache_t mag_cache;
112
/** Cache for cache descriptors */
115
/** Cache for cache descriptors */
113
static slab_cache_t slab_cache_cache;
116
static slab_cache_t slab_cache_cache;
114
/** Cache for external slab descriptors
117
/** Cache for external slab descriptors
115
 * This time we want per-cpu cache, so do not make it static
118
 * This time we want per-cpu cache, so do not make it static
116
 * - using SLAB for internal SLAB structures will not deadlock,
119
 * - using slab for internal slab structures will not deadlock,
117
 *   as all slab structures are 'small' - control structures of
120
 *   as all slab structures are 'small' - control structures of
118
 *   their caches do not require further allocation
121
 *   their caches do not require further allocation
119
 */
122
 */
120
static slab_cache_t *slab_extern_cache;
123
static slab_cache_t *slab_extern_cache;
121
/** Caches for malloc */
124
/** Caches for malloc */
Line 139... Line 142...
139
#ifdef CONFIG_DEBUG
142
#ifdef CONFIG_DEBUG
140
static int _slab_initialized = 0;
143
static int _slab_initialized = 0;
141
#endif
144
#endif
142
 
145
 
143
/**************************************/
146
/**************************************/
144
/* SLAB allocation functions          */
147
/* Slab allocation functions          */
145
 
148
 
146
/**
149
/**
147
 * Allocate frames for slab space and initialize
150
 * Allocate frames for slab space and initialize
148
 *
151
 *
149
 */
152
 */
Line 188... Line 191...
188
    atomic_inc(&cache->allocated_slabs);
191
    atomic_inc(&cache->allocated_slabs);
189
    return slab;
192
    return slab;
190
}
193
}
191
 
194
 
192
/**
195
/**
193
 * Deallocate space associated with SLAB
196
 * Deallocate space associated with slab
194
 *
197
 *
195
 * @return number of freed frames
198
 * @return number of freed frames
196
 */
199
 */
197
static count_t slab_space_free(slab_cache_t *cache, slab_t *slab)
200
static count_t slab_space_free(slab_cache_t *cache, slab_t *slab)
198
{
201
{
Line 210... Line 213...
210
{
213
{
211
    return (slab_t *)frame_get_parent(ADDR2PFN(KA2PA(obj)), 0);
214
    return (slab_t *)frame_get_parent(ADDR2PFN(KA2PA(obj)), 0);
212
}
215
}
213
 
216
 
214
/**************************************/
217
/**************************************/
215
/* SLAB functions */
218
/* Slab functions */
216
 
219
 
217
 
220
 
218
/**
221
/**
219
 * Return object to slab and call a destructor
222
 * Return object to slab and call a destructor
220
 *
223
 *
Line 271... Line 274...
271
 
274
 
272
    spinlock_lock(&cache->slablock);
275
    spinlock_lock(&cache->slablock);
273
 
276
 
274
    if (list_empty(&cache->partial_slabs)) {
277
    if (list_empty(&cache->partial_slabs)) {
275
        /* Allow recursion and reclaiming
278
        /* Allow recursion and reclaiming
276
         * - this should work, as the SLAB control structures
279
         * - this should work, as the slab control structures
277
         *   are small and do not need to allocte with anything
280
         *   are small and do not need to allocte with anything
278
         *   other ten frame_alloc when they are allocating,
281
         *   other ten frame_alloc when they are allocating,
279
         *   that's why we should get recursion at most 1-level deep
282
         *   that's why we should get recursion at most 1-level deep
280
         */
283
         */
281
        spinlock_unlock(&cache->slablock);
284
        spinlock_unlock(&cache->slablock);
Line 507... Line 510...
507
    return 0;
510
    return 0;
508
}
511
}
509
 
512
 
510
 
513
 
511
/**************************************/
514
/**************************************/
512
/* SLAB CACHE functions */
515
/* Slab cache functions */
513
 
516
 
514
/** Return number of objects that fit in certain cache size */
517
/** Return number of objects that fit in certain cache size */
515
static int comp_objects(slab_cache_t *cache)
518
static int comp_objects(slab_cache_t *cache)
516
{
519
{
517
    if (cache->flags & SLAB_CACHE_SLINSIDE)
520
    if (cache->flags & SLAB_CACHE_SLINSIDE)
Line 787... Line 790...
787
    link_t *cur;
790
    link_t *cur;
788
    ipl_t ipl;
791
    ipl_t ipl;
789
   
792
   
790
    ipl = interrupts_disable();
793
    ipl = interrupts_disable();
791
    spinlock_lock(&slab_cache_lock);
794
    spinlock_lock(&slab_cache_lock);
792
    printf("SLAB name\t  Osize\t  Pages\t Obj/pg\t  Slabs\t Cached\tAllocobjs\tCtl\n");
795
    printf("slab name\t  Osize\t  Pages\t Obj/pg\t  Slabs\t Cached\tAllocobjs\tCtl\n");
793
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
796
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
794
        cache = list_get_instance(cur, slab_cache_t, link);
797
        cache = list_get_instance(cur, slab_cache_t, link);
795
        printf("%s\t%7zd\t%7zd\t%7zd\t%7zd\t%7zd\t%7zd\t\t%s\n", cache->name, cache->size,
798
        printf("%s\t%7zd\t%7zd\t%7zd\t%7zd\t%7zd\t%7zd\t\t%s\n", cache->name, cache->size,
796
               (1 << cache->order), cache->objects,
799
               (1 << cache->order), cache->objects,
797
               atomic_get(&cache->allocated_slabs),
800
               atomic_get(&cache->allocated_slabs),