Subversion Repositories HelenOS

Rev

Rev 775 | Rev 778 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 775 Rev 776
1
/*
1
/*
2
 * Copyright (C) 2006 Ondrej Palkovsky
2
 * Copyright (C) 2006 Ondrej Palkovsky
3
 * All rights reserved.
3
 * All rights reserved.
4
 *
4
 *
5
 * Redistribution and use in source and binary forms, with or without
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
6
 * modification, are permitted provided that the following conditions
7
 * are met:
7
 * are met:
8
 *
8
 *
9
 * - Redistributions of source code must retain the above copyright
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
15
 *   derived from this software without specific prior written permission.
16
 *
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
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
 * The SLAB allocator is closely modelled after Opensolaris SLAB allocator
30
 * The SLAB allocator is closely modelled after Opensolaris SLAB allocator
31
 * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
31
 * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
32
 *
32
 *
33
 * with the following exceptions:
33
 * with the following exceptions:
34
 *   - empty SLABS are deallocated immediately
34
 *   - empty SLABS are deallocated immediately
35
 *     (in Linux they are kept in linked list, in Solaris ???)
35
 *     (in Linux they are kept in linked list, in Solaris ???)
36
 *   - empty magazines are deallocated when not needed
36
 *   - empty magazines are deallocated when not needed
37
 *     (in Solaris they are held in linked list in slab cache)
37
 *     (in Solaris they are held in linked list in slab cache)
38
 *
38
 *
39
 *   Following features are not currently supported but would be easy to do:
39
 *   Following features are not currently supported but would be easy to do:
40
 *   - cache coloring
40
 *   - cache coloring
41
 *   - dynamic magazine growing (different magazine sizes are already
41
 *   - dynamic magazine growing (different magazine sizes are already
42
 *     supported, but we would need to adjust allocating strategy)
42
 *     supported, but we would need to adjust allocating strategy)
43
 *
43
 *
44
 * The SLAB allocator supports per-CPU caches ('magazines') to facilitate
44
 * The SLAB allocator supports per-CPU caches ('magazines') to facilitate
45
 * good SMP scaling.
45
 * good SMP scaling.
46
 *
46
 *
47
 * When a new object is being allocated, it is first checked, if it is
47
 * 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
48
 * 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,
49
 * allocated from CPU-shared SLAB - if partial full is found, it is used,
50
 * otherwise a new one is allocated.
50
 * otherwise a new one is allocated.
51
 *
51
 *
52
 * When an object is being deallocated, it is put to CPU-bound magazine.
52
 * 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,
53
 * 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
54
 * 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.
55
 * put into cpu-shared list of magazines and new one is allocated.
56
 *
56
 *
57
 * The CPU-bound magazine is actually a pair of magazine to avoid
57
 * The CPU-bound magazine is actually a pair of magazine to avoid
58
 * thrashing when somebody is allocating/deallocating 1 item at the magazine
58
 * thrashing when somebody is allocating/deallocating 1 item at the magazine
59
 * size boundary. LIFO order is enforced, which should avoid fragmentation
59
 * size boundary. LIFO order is enforced, which should avoid fragmentation
60
 * as much as possible.
60
 * as much as possible.
61
 *  
61
 *  
62
 * Every cache contains list of full slabs and list of partialy full slabs.
62
 * Every cache contains list of full slabs and list of partialy full slabs.
63
 * Empty SLABS are immediately freed (thrashing will be avoided because
63
 * Empty SLABS are immediately freed (thrashing will be avoided because
64
 * of magazines).
64
 * of magazines).
65
 *
65
 *
66
 * The SLAB information structure is kept inside the data area, if possible.
66
 * 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
67
 * 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
68
 * only for SLAB related caches to avoid deadlocks and infinite recursion
69
 * (the SLAB allocator uses itself for allocating all it's control structures).
69
 * (the SLAB allocator uses itself for allocating all it's control structures).
70
 *
70
 *
71
 * The SLAB allocator allocates lot of space and does not free it. When
71
 * 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().
72
 * frame allocator fails to allocate the frame, it calls slab_reclaim().
73
 * It tries 'light reclaim' first, then brutal reclaim. The light reclaim
73
 * It tries 'light reclaim' first, then brutal reclaim. The light reclaim
74
 * releases slabs from cpu-shared magazine-list, until at least 1 slab
74
 * releases slabs from cpu-shared magazine-list, until at least 1 slab
75
 * is deallocated in each cache (this algorithm should probably change).
75
 * is deallocated in each cache (this algorithm should probably change).
76
 * The brutal reclaim removes all cached objects, even from CPU-bound
76
 * The brutal reclaim removes all cached objects, even from CPU-bound
77
 * magazines.
77
 * magazines.
78
 *
78
 *
79
 * TODO: For better CPU-scaling the magazine allocation strategy should
79
 * TODO: For better CPU-scaling the magazine allocation strategy should
80
 * be extended. Currently, if the cache does not have magazine, it asks
80
 * 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
81
 * 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
82
 * 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
83
 * from non-cpu-cached mag. cache). This would provide a nice per-cpu
84
 * buffer. The other possibility is to use the per-cache
84
 * buffer. The other possibility is to use the per-cache
85
 * 'empty-magazine-list', which decreases competing for 1 per-system
85
 * 'empty-magazine-list', which decreases competing for 1 per-system
86
 * magazine cache.
86
 * magazine cache.
87
 *
87
 *
-
 
88
 * - 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
-
 
90
 *   scalability even on slab level
88
 */
91
 */
89
 
92
 
90
 
93
 
91
#include <synch/spinlock.h>
94
#include <synch/spinlock.h>
92
#include <mm/slab.h>
95
#include <mm/slab.h>
93
#include <list.h>
96
#include <list.h>
94
#include <memstr.h>
97
#include <memstr.h>
95
#include <align.h>
98
#include <align.h>
96
#include <mm/heap.h>
99
#include <mm/heap.h>
97
#include <mm/frame.h>
100
#include <mm/frame.h>
98
#include <config.h>
101
#include <config.h>
99
#include <print.h>
102
#include <print.h>
100
#include <arch.h>
103
#include <arch.h>
101
#include <panic.h>
104
#include <panic.h>
102
#include <debug.h>
105
#include <debug.h>
103
#include <bitops.h>
106
#include <bitops.h>
104
 
107
 
105
SPINLOCK_INITIALIZE(slab_cache_lock);
108
SPINLOCK_INITIALIZE(slab_cache_lock);
106
static LIST_INITIALIZE(slab_cache_list);
109
static LIST_INITIALIZE(slab_cache_list);
107
 
110
 
108
/** Magazine cache */
111
/** Magazine cache */
109
static slab_cache_t mag_cache;
112
static slab_cache_t mag_cache;
110
/** Cache for cache descriptors */
113
/** Cache for cache descriptors */
111
static slab_cache_t slab_cache_cache;
114
static slab_cache_t slab_cache_cache;
112
 
115
 
113
/** Cache for external slab descriptors
116
/** Cache for external slab descriptors
114
 * This time we want per-cpu cache, so do not make it static
117
 * This time we want per-cpu cache, so do not make it static
115
 * - using SLAB for internal SLAB structures will not deadlock,
118
 * - using SLAB for internal SLAB structures will not deadlock,
116
 *   as all slab structures are 'small' - control structures of
119
 *   as all slab structures are 'small' - control structures of
117
 *   their caches do not require further allocation
120
 *   their caches do not require further allocation
118
 */
121
 */
119
static slab_cache_t *slab_extern_cache;
122
static slab_cache_t *slab_extern_cache;
120
/** Caches for malloc */
123
/** Caches for malloc */
121
static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1];
124
static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1];
122
char *malloc_names[] =  {
125
char *malloc_names[] =  {
123
    "malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",
126
    "malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",
124
    "malloc-256","malloc-512","malloc-1K","malloc-2K",
127
    "malloc-256","malloc-512","malloc-1K","malloc-2K",
125
    "malloc-4K","malloc-8K","malloc-16K","malloc-32K",
128
    "malloc-4K","malloc-8K","malloc-16K","malloc-32K",
126
    "malloc-64K","malloc-128K"
129
    "malloc-64K","malloc-128K"
127
};
130
};
128
 
131
 
129
/** Slab descriptor */
132
/** Slab descriptor */
130
typedef struct {
133
typedef struct {
131
    slab_cache_t *cache; /**< Pointer to parent cache */
134
    slab_cache_t *cache; /**< Pointer to parent cache */
132
    link_t link;       /* List of full/partial slabs */
135
    link_t link;       /* List of full/partial slabs */
133
    void *start;       /**< Start address of first available item */
136
    void *start;       /**< Start address of first available item */
134
    count_t available; /**< Count of available items in this slab */
137
    count_t available; /**< Count of available items in this slab */
135
    index_t nextavail; /**< The index of next available item */
138
    index_t nextavail; /**< The index of next available item */
136
}slab_t;
139
}slab_t;
137
 
140
 
138
/**************************************/
141
/**************************************/
139
/* SLAB allocation functions          */
142
/* SLAB allocation functions          */
140
 
143
 
141
/**
144
/**
142
 * Allocate frames for slab space and initialize
145
 * Allocate frames for slab space and initialize
143
 *
146
 *
144
 */
147
 */
145
static slab_t * slab_space_alloc(slab_cache_t *cache, int flags)
148
static slab_t * slab_space_alloc(slab_cache_t *cache, int flags)
146
{
149
{
147
    void *data;
150
    void *data;
148
    slab_t *slab;
151
    slab_t *slab;
149
    size_t fsize;
152
    size_t fsize;
150
    int i;
153
    int i;
151
    zone_t *zone = NULL;
154
    zone_t *zone = NULL;
152
    int status;
155
    int status;
153
    frame_t *frame;
156
    frame_t *frame;
154
 
157
 
155
    data = (void *)frame_alloc(FRAME_KA | flags, cache->order, &status, &zone);
158
    data = (void *)frame_alloc(FRAME_KA | flags, cache->order, &status, &zone);
156
    if (status != FRAME_OK) {
159
    if (status != FRAME_OK) {
157
        return NULL;
160
        return NULL;
158
    }
161
    }
159
    if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {
162
    if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {
160
        slab = slab_alloc(slab_extern_cache, flags);
163
        slab = slab_alloc(slab_extern_cache, flags);
161
        if (!slab) {
164
        if (!slab) {
162
            frame_free((__address)data);
165
            frame_free((__address)data);
163
            return NULL;
166
            return NULL;
164
        }
167
        }
165
    } else {
168
    } else {
166
        fsize = (PAGE_SIZE << cache->order);
169
        fsize = (PAGE_SIZE << cache->order);
167
        slab = data + fsize - sizeof(*slab);
170
        slab = data + fsize - sizeof(*slab);
168
    }
171
    }
169
       
172
       
170
    /* Fill in slab structures */
173
    /* Fill in slab structures */
171
    /* TODO: some better way of accessing the frame */
174
    /* TODO: some better way of accessing the frame */
172
    for (i=0; i < (1 << cache->order); i++) {
175
    for (i=0; i < (1 << cache->order); i++) {
173
        frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));
176
        frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));
174
        frame->parent = slab;
177
        frame->parent = slab;
175
    }
178
    }
176
 
179
 
177
    slab->start = data;
180
    slab->start = data;
178
    slab->available = cache->objects;
181
    slab->available = cache->objects;
179
    slab->nextavail = 0;
182
    slab->nextavail = 0;
180
    slab->cache = cache;
183
    slab->cache = cache;
181
 
184
 
182
    for (i=0; i<cache->objects;i++)
185
    for (i=0; i<cache->objects;i++)
183
        *((int *) (slab->start + i*cache->size)) = i+1;
186
        *((int *) (slab->start + i*cache->size)) = i+1;
184
 
187
 
185
    atomic_inc(&cache->allocated_slabs);
188
    atomic_inc(&cache->allocated_slabs);
186
    return slab;
189
    return slab;
187
}
190
}
188
 
191
 
189
/**
192
/**
190
 * Deallocate space associated with SLAB
193
 * Deallocate space associated with SLAB
191
 *
194
 *
192
 * @return number of freed frames
195
 * @return number of freed frames
193
 */
196
 */
194
static count_t slab_space_free(slab_cache_t *cache, slab_t *slab)
197
static count_t slab_space_free(slab_cache_t *cache, slab_t *slab)
195
{
198
{
196
    frame_free((__address)slab->start);
199
    frame_free((__address)slab->start);
197
    if (! (cache->flags & SLAB_CACHE_SLINSIDE))
200
    if (! (cache->flags & SLAB_CACHE_SLINSIDE))
198
        slab_free(slab_extern_cache, slab);
201
        slab_free(slab_extern_cache, slab);
199
 
202
 
200
    atomic_dec(&cache->allocated_slabs);
203
    atomic_dec(&cache->allocated_slabs);
201
   
204
   
202
    return 1 << cache->order;
205
    return 1 << cache->order;
203
}
206
}
204
 
207
 
205
/** Map object to slab structure */
208
/** Map object to slab structure */
206
static slab_t * obj2slab(void *obj)
209
static slab_t * obj2slab(void *obj)
207
{
210
{
208
    frame_t *frame;
211
    frame_t *frame;
209
 
212
 
210
    frame = frame_addr2frame((__address)obj);
213
    frame = frame_addr2frame((__address)obj);
211
    return (slab_t *)frame->parent;
214
    return (slab_t *)frame->parent;
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
 *
221
 * Assume the cache->lock is held;
-
 
222
 *
-
 
223
 * @param slab If the caller knows directly slab of the object, otherwise NULL
224
 * @param slab If the caller knows directly slab of the object, otherwise NULL
224
 *
225
 *
225
 * @return Number of freed pages
226
 * @return Number of freed pages
226
 */
227
 */
227
static count_t slab_obj_destroy(slab_cache_t *cache, void *obj,
228
static count_t slab_obj_destroy(slab_cache_t *cache, void *obj,
228
                slab_t *slab)
229
                slab_t *slab)
229
{
230
{
230
    count_t frames = 0;
231
    count_t frames = 0;
231
 
232
 
232
    if (!slab)
233
    if (!slab)
233
        slab = obj2slab(obj);
234
        slab = obj2slab(obj);
234
 
235
 
235
    ASSERT(slab->cache == cache);
236
    ASSERT(slab->cache == cache);
236
 
237
 
-
 
238
    spinlock_lock(&cache->slablock);
-
 
239
 
237
    *((int *)obj) = slab->nextavail;
240
    *((int *)obj) = slab->nextavail;
238
    slab->nextavail = (obj - slab->start)/cache->size;
241
    slab->nextavail = (obj - slab->start)/cache->size;
239
    slab->available++;
242
    slab->available++;
240
 
243
 
241
    /* Move it to correct list */
244
    /* Move it to correct list */
242
    if (slab->available == 1) {
245
    if (slab->available == 1) {
243
        /* It was in full, move to partial */
246
        /* It was in full, move to partial */
244
        list_remove(&slab->link);
247
        list_remove(&slab->link);
245
        list_prepend(&slab->link, &cache->partial_slabs);
248
        list_prepend(&slab->link, &cache->partial_slabs);
246
    }
249
    }
247
    if (slab->available == cache->objects) {
250
    if (slab->available == cache->objects) {
248
        /* Free associated memory */
251
        /* Free associated memory */
249
        list_remove(&slab->link);
252
        list_remove(&slab->link);
250
        /* Avoid deadlock */
253
        /* This should not produce deadlock, as
-
 
254
         * magazine is always allocated with NO reclaim,
251
        spinlock_unlock(&cache->lock);
255
         * keep all locks */
252
        frames = slab_space_free(cache, slab);
256
        frames = slab_space_free(cache, slab);
253
        spinlock_lock(&cache->lock);
-
 
254
    }
257
    }
255
 
258
 
-
 
259
    spinlock_unlock(&cache->slablock);
-
 
260
 
256
    return frames;
261
    return frames;
257
}
262
}
258
 
263
 
259
/**
264
/**
260
 * Take new object from slab or create new if needed
265
 * Take new object from slab or create new if needed
261
 *
266
 *
262
 * Assume cache->lock is held.
-
 
263
 *
-
 
264
 * @return Object address or null
267
 * @return Object address or null
265
 */
268
 */
266
static void * slab_obj_create(slab_cache_t *cache, int flags)
269
static void * slab_obj_create(slab_cache_t *cache, int flags)
267
{
270
{
268
    slab_t *slab;
271
    slab_t *slab;
269
    void *obj;
272
    void *obj;
270
 
273
 
-
 
274
    spinlock_lock(&cache->slablock);
-
 
275
 
271
    if (list_empty(&cache->partial_slabs)) {
276
    if (list_empty(&cache->partial_slabs)) {
272
        /* Allow recursion and reclaiming
277
        /* Allow recursion and reclaiming
273
         * - this should work, as the SLAB control structures
278
         * - this should work, as the SLAB control structures
274
         *   are small and do not need to allocte with anything
279
         *   are small and do not need to allocte with anything
275
         *   other ten frame_alloc when they are allocating,
280
         *   other ten frame_alloc when they are allocating,
276
         *   that's why we should get recursion at most 1-level deep
281
         *   that's why we should get recursion at most 1-level deep
277
         */
282
         */
278
        spinlock_unlock(&cache->lock);
283
        spinlock_unlock(&cache->slablock);
279
        slab = slab_space_alloc(cache, flags);
284
        slab = slab_space_alloc(cache, flags);
280
        spinlock_lock(&cache->lock);
285
        spinlock_lock(&cache->slablock);
281
        if (!slab) {
286
        if (!slab)
282
            return NULL;
287
            goto err;
283
        }
-
 
284
    } else {
288
    } else {
285
        slab = list_get_instance(cache->partial_slabs.next,
289
        slab = list_get_instance(cache->partial_slabs.next,
286
                     slab_t,
290
                     slab_t,
287
                     link);
291
                     link);
288
        list_remove(&slab->link);
292
        list_remove(&slab->link);
289
    }
293
    }
290
    obj = slab->start + slab->nextavail * cache->size;
294
    obj = slab->start + slab->nextavail * cache->size;
291
    slab->nextavail = *((int *)obj);
295
    slab->nextavail = *((int *)obj);
292
    slab->available--;
296
    slab->available--;
293
    if (! slab->available)
297
    if (! slab->available)
294
        list_prepend(&slab->link, &cache->full_slabs);
298
        list_prepend(&slab->link, &cache->full_slabs);
295
    else
299
    else
296
        list_prepend(&slab->link, &cache->partial_slabs);
300
        list_prepend(&slab->link, &cache->partial_slabs);
-
 
301
 
-
 
302
    spinlock_unlock(&cache->slablock);
297
    return obj;
303
    return obj;
-
 
304
err:
-
 
305
    spinlock_unlock(&cache->slablock);
-
 
306
    return NULL;
298
}
307
}
299
 
308
 
300
/**************************************/
309
/**************************************/
301
/* CPU-Cache slab functions */
310
/* CPU-Cache slab functions */
302
 
311
 
303
/**
312
/**
304
 * Free all objects in magazine and free memory associated with magazine
313
 * Free all objects in magazine and free memory associated with magazine
305
 *
314
 *
306
 * Assume cache->lock is held
-
 
307
 *
-
 
308
 * @return Number of freed pages
315
 * @return Number of freed pages
309
 */
316
 */
310
static count_t magazine_destroy(slab_cache_t *cache,
317
static count_t magazine_destroy(slab_cache_t *cache,
311
                slab_magazine_t *mag)
318
                slab_magazine_t *mag)
312
{
319
{
313
    int i;
320
    int i;
314
    count_t frames = 0;
321
    count_t frames = 0;
315
 
322
 
316
    for (i=0;i < mag->busy; i++) {
323
    for (i=0;i < mag->busy; i++) {
317
        frames += slab_obj_destroy(cache, mag->objs[i], NULL);
324
        frames += slab_obj_destroy(cache, mag->objs[i], NULL);
318
        atomic_dec(&cache->cached_objs);
325
        atomic_dec(&cache->cached_objs);
319
    }
326
    }
320
   
327
   
321
    slab_free(&mag_cache, mag);
328
    slab_free(&mag_cache, mag);
322
 
329
 
323
    return frames;
330
    return frames;
324
}
331
}
325
 
332
 
326
/**
333
/**
327
 * Find full magazine, set it as current and return it
334
 * Find full magazine, set it as current and return it
328
 *
335
 *
329
 * Assume cpu_magazine lock is held
336
 * Assume cpu_magazine lock is held
330
 */
337
 */
331
static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)
338
static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)
332
{
339
{
333
    slab_magazine_t *cmag, *lastmag, *newmag;
340
    slab_magazine_t *cmag, *lastmag, *newmag;
334
 
341
 
335
    cmag = cache->mag_cache[CPU->id].current;
342
    cmag = cache->mag_cache[CPU->id].current;
336
    lastmag = cache->mag_cache[CPU->id].last;
343
    lastmag = cache->mag_cache[CPU->id].last;
337
    if (cmag) { /* First try local CPU magazines */
344
    if (cmag) { /* First try local CPU magazines */
338
        if (cmag->busy)
345
        if (cmag->busy)
339
            return cmag;
346
            return cmag;
340
 
347
 
341
        if (lastmag && lastmag->busy) {
348
        if (lastmag && lastmag->busy) {
342
            cache->mag_cache[CPU->id].current = lastmag;
349
            cache->mag_cache[CPU->id].current = lastmag;
343
            cache->mag_cache[CPU->id].last = cmag;
350
            cache->mag_cache[CPU->id].last = cmag;
344
            return lastmag;
351
            return lastmag;
345
        }
352
        }
346
    }
353
    }
347
    /* Local magazines are empty, import one from magazine list */
354
    /* Local magazines are empty, import one from magazine list */
348
    spinlock_lock(&cache->lock);
355
    spinlock_lock(&cache->maglock);
349
    if (list_empty(&cache->magazines)) {
356
    if (list_empty(&cache->magazines)) {
350
        spinlock_unlock(&cache->lock);
357
        spinlock_unlock(&cache->maglock);
351
        return NULL;
358
        return NULL;
352
    }
359
    }
353
    newmag = list_get_instance(cache->magazines.next,
360
    newmag = list_get_instance(cache->magazines.next,
354
                   slab_magazine_t,
361
                   slab_magazine_t,
355
                   link);
362
                   link);
356
    list_remove(&newmag->link);
363
    list_remove(&newmag->link);
357
    spinlock_unlock(&cache->lock);
364
    spinlock_unlock(&cache->maglock);
358
 
365
 
359
    if (lastmag)
366
    if (lastmag)
360
        slab_free(&mag_cache, lastmag);
367
        slab_free(&mag_cache, lastmag);
361
    cache->mag_cache[CPU->id].last = cmag;
368
    cache->mag_cache[CPU->id].last = cmag;
362
    cache->mag_cache[CPU->id].current = newmag;
369
    cache->mag_cache[CPU->id].current = newmag;
363
    return newmag;
370
    return newmag;
364
}
371
}
365
 
372
 
366
/**
373
/**
367
 * Try to find object in CPU-cache magazines
374
 * Try to find object in CPU-cache magazines
368
 *
375
 *
369
 * @return Pointer to object or NULL if not available
376
 * @return Pointer to object or NULL if not available
370
 */
377
 */
371
static void * magazine_obj_get(slab_cache_t *cache)
378
static void * magazine_obj_get(slab_cache_t *cache)
372
{
379
{
373
    slab_magazine_t *mag;
380
    slab_magazine_t *mag;
374
    void *obj;
381
    void *obj;
375
 
382
 
376
    if (!CPU)
383
    if (!CPU)
377
        return NULL;
384
        return NULL;
378
 
385
 
379
    spinlock_lock(&cache->mag_cache[CPU->id].lock);
386
    spinlock_lock(&cache->mag_cache[CPU->id].lock);
380
 
387
 
381
    mag = get_full_current_mag(cache);
388
    mag = get_full_current_mag(cache);
382
    if (!mag) {
389
    if (!mag) {
383
        spinlock_unlock(&cache->mag_cache[CPU->id].lock);
390
        spinlock_unlock(&cache->mag_cache[CPU->id].lock);
384
        return NULL;
391
        return NULL;
385
    }
392
    }
386
    obj = mag->objs[--mag->busy];
393
    obj = mag->objs[--mag->busy];
387
    spinlock_unlock(&cache->mag_cache[CPU->id].lock);
394
    spinlock_unlock(&cache->mag_cache[CPU->id].lock);
388
    atomic_dec(&cache->cached_objs);
395
    atomic_dec(&cache->cached_objs);
389
   
396
   
390
    return obj;
397
    return obj;
391
}
398
}
392
 
399
 
393
/**
400
/**
394
 * Assure that the current magazine is empty, return pointer to it, or NULL if
401
 * Assure that the current magazine is empty, return pointer to it, or NULL if
395
 * no empty magazine is available and cannot be allocated
402
 * no empty magazine is available and cannot be allocated
396
 *
403
 *
397
 * Assume mag_cache[CPU->id].lock is held
404
 * Assume mag_cache[CPU->id].lock is held
398
 *
405
 *
399
 * We have 2 magazines bound to processor.
406
 * We have 2 magazines bound to processor.
400
 * First try the current.
407
 * First try the current.
401
 *  If full, try the last.
408
 *  If full, try the last.
402
 *   If full, put to magazines list.
409
 *   If full, put to magazines list.
403
 *   allocate new, exchange last & current
410
 *   allocate new, exchange last & current
404
 *
411
 *
405
 */
412
 */
406
static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)
413
static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)
407
{
414
{
408
    slab_magazine_t *cmag,*lastmag,*newmag;
415
    slab_magazine_t *cmag,*lastmag,*newmag;
409
 
416
 
410
    cmag = cache->mag_cache[CPU->id].current;
417
    cmag = cache->mag_cache[CPU->id].current;
411
    lastmag = cache->mag_cache[CPU->id].last;
418
    lastmag = cache->mag_cache[CPU->id].last;
412
 
419
 
413
    if (cmag) {
420
    if (cmag) {
414
        if (cmag->busy < cmag->size)
421
        if (cmag->busy < cmag->size)
415
            return cmag;
422
            return cmag;
416
        if (lastmag && lastmag->busy < lastmag->size) {
423
        if (lastmag && lastmag->busy < lastmag->size) {
417
            cache->mag_cache[CPU->id].last = cmag;
424
            cache->mag_cache[CPU->id].last = cmag;
418
            cache->mag_cache[CPU->id].current = lastmag;
425
            cache->mag_cache[CPU->id].current = lastmag;
419
            return lastmag;
426
            return lastmag;
420
        }
427
        }
421
    }
428
    }
422
    /* current | last are full | nonexistent, allocate new */
429
    /* current | last are full | nonexistent, allocate new */
423
    /* We do not want to sleep just because of caching */
430
    /* We do not want to sleep just because of caching */
424
    /* Especially we do not want reclaiming to start, as
431
    /* Especially we do not want reclaiming to start, as
425
     * this would deadlock */
432
     * this would deadlock */
426
    newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM);
433
    newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM);
427
    if (!newmag)
434
    if (!newmag)
428
        return NULL;
435
        return NULL;
429
    newmag->size = SLAB_MAG_SIZE;
436
    newmag->size = SLAB_MAG_SIZE;
430
    newmag->busy = 0;
437
    newmag->busy = 0;
431
 
438
 
432
    /* Flush last to magazine list */
439
    /* Flush last to magazine list */
433
    if (lastmag) {
440
    if (lastmag) {
434
        spinlock_lock(&cache->lock);
441
        spinlock_lock(&cache->maglock);
435
        list_prepend(&lastmag->link, &cache->magazines);
442
        list_prepend(&lastmag->link, &cache->magazines);
436
        spinlock_unlock(&cache->lock);
443
        spinlock_unlock(&cache->maglock);
437
    }
444
    }
438
    /* Move current as last, save new as current */
445
    /* Move current as last, save new as current */
439
    cache->mag_cache[CPU->id].last = cmag; 
446
    cache->mag_cache[CPU->id].last = cmag; 
440
    cache->mag_cache[CPU->id].current = newmag;
447
    cache->mag_cache[CPU->id].current = newmag;
441
 
448
 
442
    return newmag;
449
    return newmag;
443
}
450
}
444
 
451
 
445
/**
452
/**
446
 * Put object into CPU-cache magazine
453
 * Put object into CPU-cache magazine
447
 *
454
 *
448
 * @return 0 - success, -1 - could not get memory
455
 * @return 0 - success, -1 - could not get memory
449
 */
456
 */
450
static int magazine_obj_put(slab_cache_t *cache, void *obj)
457
static int magazine_obj_put(slab_cache_t *cache, void *obj)
451
{
458
{
452
    slab_magazine_t *mag;
459
    slab_magazine_t *mag;
453
 
460
 
454
    if (!CPU)
461
    if (!CPU)
455
        return -1;
462
        return -1;
456
 
463
 
457
    spinlock_lock(&cache->mag_cache[CPU->id].lock);
464
    spinlock_lock(&cache->mag_cache[CPU->id].lock);
458
 
465
 
459
    mag = make_empty_current_mag(cache);
466
    mag = make_empty_current_mag(cache);
460
    if (!mag) {
467
    if (!mag) {
461
        spinlock_unlock(&cache->mag_cache[CPU->id].lock);
468
        spinlock_unlock(&cache->mag_cache[CPU->id].lock);
462
        return -1;
469
        return -1;
463
    }
470
    }
464
   
471
   
465
    mag->objs[mag->busy++] = obj;
472
    mag->objs[mag->busy++] = obj;
466
 
473
 
467
    spinlock_unlock(&cache->mag_cache[CPU->id].lock);
474
    spinlock_unlock(&cache->mag_cache[CPU->id].lock);
468
    atomic_inc(&cache->cached_objs);
475
    atomic_inc(&cache->cached_objs);
469
    return 0;
476
    return 0;
470
}
477
}
471
 
478
 
472
 
479
 
473
/**************************************/
480
/**************************************/
474
/* SLAB CACHE functions */
481
/* SLAB CACHE functions */
475
 
482
 
476
/** Return number of objects that fit in certain cache size */
483
/** Return number of objects that fit in certain cache size */
477
static int comp_objects(slab_cache_t *cache)
484
static int comp_objects(slab_cache_t *cache)
478
{
485
{
479
    if (cache->flags & SLAB_CACHE_SLINSIDE)
486
    if (cache->flags & SLAB_CACHE_SLINSIDE)
480
        return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size;
487
        return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size;
481
    else
488
    else
482
        return (PAGE_SIZE << cache->order) / cache->size;
489
        return (PAGE_SIZE << cache->order) / cache->size;
483
}
490
}
484
 
491
 
485
/** Return wasted space in slab */
492
/** Return wasted space in slab */
486
static int badness(slab_cache_t *cache)
493
static int badness(slab_cache_t *cache)
487
{
494
{
488
    int objects;
495
    int objects;
489
    int ssize;
496
    int ssize;
490
 
497
 
491
    objects = comp_objects(cache);
498
    objects = comp_objects(cache);
492
    ssize = PAGE_SIZE << cache->order;
499
    ssize = PAGE_SIZE << cache->order;
493
    if (cache->flags & SLAB_CACHE_SLINSIDE)
500
    if (cache->flags & SLAB_CACHE_SLINSIDE)
494
        ssize -= sizeof(slab_t);
501
        ssize -= sizeof(slab_t);
495
    return ssize - objects*cache->size;
502
    return ssize - objects*cache->size;
496
}
503
}
497
 
504
 
498
/** Initialize allocated memory as a slab cache */
505
/** Initialize allocated memory as a slab cache */
499
static void
506
static void
500
_slab_cache_create(slab_cache_t *cache,
507
_slab_cache_create(slab_cache_t *cache,
501
           char *name,
508
           char *name,
502
           size_t size,
509
           size_t size,
503
           size_t align,
510
           size_t align,
504
           int (*constructor)(void *obj, int kmflag),
511
           int (*constructor)(void *obj, int kmflag),
505
           void (*destructor)(void *obj),
512
           void (*destructor)(void *obj),
506
           int flags)
513
           int flags)
507
{
514
{
508
    int i;
515
    int i;
509
    int pages;
516
    int pages;
510
 
517
 
511
    memsetb((__address)cache, sizeof(*cache), 0);
518
    memsetb((__address)cache, sizeof(*cache), 0);
512
    cache->name = name;
519
    cache->name = name;
513
 
520
 
514
    if (align < sizeof(__native))
521
    if (align < sizeof(__native))
515
        align = sizeof(__native);
522
        align = sizeof(__native);
516
    size = ALIGN_UP(size, align);
523
    size = ALIGN_UP(size, align);
517
       
524
       
518
    cache->size = size;
525
    cache->size = size;
519
 
526
 
520
    cache->constructor = constructor;
527
    cache->constructor = constructor;
521
    cache->destructor = destructor;
528
    cache->destructor = destructor;
522
    cache->flags = flags;
529
    cache->flags = flags;
523
 
530
 
524
    list_initialize(&cache->full_slabs);
531
    list_initialize(&cache->full_slabs);
525
    list_initialize(&cache->partial_slabs);
532
    list_initialize(&cache->partial_slabs);
526
    list_initialize(&cache->magazines);
533
    list_initialize(&cache->magazines);
527
    spinlock_initialize(&cache->lock, "cachelock");
534
    spinlock_initialize(&cache->slablock, "slab_lock");
-
 
535
    spinlock_initialize(&cache->maglock, "slab_maglock");
528
    if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) {
536
    if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) {
529
        for (i=0; i < config.cpu_count; i++) {
537
        for (i=0; i < config.cpu_count; i++) {
530
            memsetb((__address)&cache->mag_cache[i],
538
            memsetb((__address)&cache->mag_cache[i],
531
                sizeof(cache->mag_cache[i]), 0);
539
                sizeof(cache->mag_cache[i]), 0);
532
            spinlock_initialize(&cache->mag_cache[i].lock,
540
            spinlock_initialize(&cache->mag_cache[i].lock,
533
                        "cpucachelock");
541
                        "slab_maglock_cpu");
534
        }
542
        }
535
    }
543
    }
536
 
544
 
537
    /* Compute slab sizes, object counts in slabs etc. */
545
    /* Compute slab sizes, object counts in slabs etc. */
538
    if (cache->size < SLAB_INSIDE_SIZE)
546
    if (cache->size < SLAB_INSIDE_SIZE)
539
        cache->flags |= SLAB_CACHE_SLINSIDE;
547
        cache->flags |= SLAB_CACHE_SLINSIDE;
540
 
548
 
541
    /* Minimum slab order */
549
    /* Minimum slab order */
542
    pages = ((cache->size-1) >> PAGE_WIDTH) + 1;
550
    pages = ((cache->size-1) >> PAGE_WIDTH) + 1;
543
    cache->order = fnzb(pages);
551
    cache->order = fnzb(pages);
544
 
552
 
545
    while (badness(cache) > SLAB_MAX_BADNESS(cache)) {
553
    while (badness(cache) > SLAB_MAX_BADNESS(cache)) {
546
        cache->order += 1;
554
        cache->order += 1;
547
    }
555
    }
548
    cache->objects = comp_objects(cache);
556
    cache->objects = comp_objects(cache);
549
    /* If info fits in, put it inside */
557
    /* If info fits in, put it inside */
550
    if (badness(cache) > sizeof(slab_t))
558
    if (badness(cache) > sizeof(slab_t))
551
        cache->flags |= SLAB_CACHE_SLINSIDE;
559
        cache->flags |= SLAB_CACHE_SLINSIDE;
552
 
560
 
553
    spinlock_lock(&slab_cache_lock);
561
    spinlock_lock(&slab_cache_lock);
554
 
562
 
555
    list_append(&cache->link, &slab_cache_list);
563
    list_append(&cache->link, &slab_cache_list);
556
 
564
 
557
    spinlock_unlock(&slab_cache_lock);
565
    spinlock_unlock(&slab_cache_lock);
558
}
566
}
559
 
567
 
560
/** Create slab cache  */
568
/** Create slab cache  */
561
slab_cache_t * slab_cache_create(char *name,
569
slab_cache_t * slab_cache_create(char *name,
562
                 size_t size,
570
                 size_t size,
563
                 size_t align,
571
                 size_t align,
564
                 int (*constructor)(void *obj, int kmflag),
572
                 int (*constructor)(void *obj, int kmflag),
565
                 void (*destructor)(void *obj),
573
                 void (*destructor)(void *obj),
566
                 int flags)
574
                 int flags)
567
{
575
{
568
    slab_cache_t *cache;
576
    slab_cache_t *cache;
569
 
577
 
570
    cache = slab_alloc(&slab_cache_cache, 0);
578
    cache = slab_alloc(&slab_cache_cache, 0);
571
    _slab_cache_create(cache, name, size, align, constructor, destructor,
579
    _slab_cache_create(cache, name, size, align, constructor, destructor,
572
               flags);
580
               flags);
573
    return cache;
581
    return cache;
574
}
582
}
575
 
583
 
576
/**
584
/**
577
 * Reclaim space occupied by objects that are already free
585
 * Reclaim space occupied by objects that are already free
578
 *
586
 *
579
 * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing
587
 * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing
580
 * @return Number of freed pages
588
 * @return Number of freed pages
581
 */
589
 */
582
static count_t _slab_reclaim(slab_cache_t *cache, int flags)
590
static count_t _slab_reclaim(slab_cache_t *cache, int flags)
583
{
591
{
584
    int i;
592
    int i;
585
    slab_magazine_t *mag;
593
    slab_magazine_t *mag;
586
    link_t *cur;
594
    link_t *cur;
587
    count_t frames = 0;
595
    count_t frames = 0;
588
   
596
   
589
    if (cache->flags & SLAB_CACHE_NOMAGAZINE)
597
    if (cache->flags & SLAB_CACHE_NOMAGAZINE)
590
        return 0; /* Nothing to do */
598
        return 0; /* Nothing to do */
591
   
599
   
592
    /* First lock all cpu caches, then the complete cache lock */
600
    /* First lock all cpu caches, then the complete cache lock */
593
    if (flags & SLAB_RECLAIM_ALL) {
601
    if (flags & SLAB_RECLAIM_ALL) {
594
        for (i=0; i < config.cpu_count; i++)
602
        for (i=0; i < config.cpu_count; i++)
595
            spinlock_lock(&cache->mag_cache[i].lock);
603
            spinlock_lock(&cache->mag_cache[i].lock);
596
    }
604
    }
597
    spinlock_lock(&cache->lock);
605
    spinlock_lock(&cache->maglock);
598
   
606
   
599
    if (flags & SLAB_RECLAIM_ALL) {
607
    if (flags & SLAB_RECLAIM_ALL) {
600
        /* Aggressive memfree */
608
        /* Aggressive memfree */
601
        /* Destroy CPU magazines */
609
        /* Destroy CPU magazines */
602
        for (i=0; i<config.cpu_count; i++) {
610
        for (i=0; i<config.cpu_count; i++) {
603
            mag = cache->mag_cache[i].current;
611
            mag = cache->mag_cache[i].current;
604
            if (mag)
612
            if (mag)
605
                frames += magazine_destroy(cache, mag);
613
                frames += magazine_destroy(cache, mag);
606
            cache->mag_cache[i].current = NULL;
614
            cache->mag_cache[i].current = NULL;
607
           
615
           
608
            mag = cache->mag_cache[i].last;
616
            mag = cache->mag_cache[i].last;
609
            if (mag)
617
            if (mag)
610
                frames += magazine_destroy(cache, mag);
618
                frames += magazine_destroy(cache, mag);
611
            cache->mag_cache[i].last = NULL;
619
            cache->mag_cache[i].last = NULL;
612
        }
620
        }
613
    }
621
    }
-
 
622
    /* We can release the cache locks now */
-
 
623
    if (flags & SLAB_RECLAIM_ALL) {
-
 
624
        for (i=0; i < config.cpu_count; i++)
-
 
625
            spinlock_unlock(&cache->mag_cache[i].lock);
-
 
626
    }
614
    /* Destroy full magazines */
627
    /* Destroy full magazines */
615
    cur=cache->magazines.prev;
628
    cur=cache->magazines.prev;
616
 
629
 
617
    while (cur != &cache->magazines) {
630
    while (cur != &cache->magazines) {
618
        mag = list_get_instance(cur, slab_magazine_t, link);
631
        mag = list_get_instance(cur, slab_magazine_t, link);
619
       
632
       
620
        cur = cur->prev;
633
        cur = cur->prev;
621
        list_remove(&mag->link);
634
        list_remove(&mag->link);
622
        frames += magazine_destroy(cache,mag);
635
        frames += magazine_destroy(cache,mag);
623
        /* If we do not do full reclaim, break
636
        /* If we do not do full reclaim, break
624
         * as soon as something is freed */
637
         * as soon as something is freed */
625
        if (!(flags & SLAB_RECLAIM_ALL) && frames)
638
        if (!(flags & SLAB_RECLAIM_ALL) && frames)
626
            break;
639
            break;
627
    }
640
    }
628
   
641
   
629
    spinlock_unlock(&cache->lock);
642
    spinlock_unlock(&cache->maglock);
630
    /* We can release the cache locks now */
-
 
631
    if (flags & SLAB_RECLAIM_ALL) {
-
 
632
        for (i=0; i < config.cpu_count; i++)
-
 
633
            spinlock_unlock(&cache->mag_cache[i].lock);
-
 
634
    }
-
 
635
   
643
   
636
    return frames;
644
    return frames;
637
}
645
}
638
 
646
 
639
/** Check that there are no slabs and remove cache from system  */
647
/** Check that there are no slabs and remove cache from system  */
640
void slab_cache_destroy(slab_cache_t *cache)
648
void slab_cache_destroy(slab_cache_t *cache)
641
{
649
{
642
    /* Do not lock anything, we assume the software is correct and
650
    /* Do not lock anything, we assume the software is correct and
643
     * does not touch the cache when it decides to destroy it */
651
     * does not touch the cache when it decides to destroy it */
644
   
652
   
645
    /* Destroy all magazines */
653
    /* Destroy all magazines */
646
    _slab_reclaim(cache, SLAB_RECLAIM_ALL);
654
    _slab_reclaim(cache, SLAB_RECLAIM_ALL);
647
 
655
 
648
    /* All slabs must be empty */
656
    /* All slabs must be empty */
649
    if (!list_empty(&cache->full_slabs) \
657
    if (!list_empty(&cache->full_slabs) \
650
        || !list_empty(&cache->partial_slabs))
658
        || !list_empty(&cache->partial_slabs))
651
        panic("Destroying cache that is not empty.");
659
        panic("Destroying cache that is not empty.");
652
 
660
 
653
    spinlock_lock(&slab_cache_lock);
661
    spinlock_lock(&slab_cache_lock);
654
    list_remove(&cache->link);
662
    list_remove(&cache->link);
655
    spinlock_unlock(&slab_cache_lock);
663
    spinlock_unlock(&slab_cache_lock);
656
 
664
 
657
    slab_free(&slab_cache_cache, cache);
665
    slab_free(&slab_cache_cache, cache);
658
}
666
}
659
 
667
 
660
/** Allocate new object from cache - if no flags given, always returns
668
/** Allocate new object from cache - if no flags given, always returns
661
    memory */
669
    memory */
662
void * slab_alloc(slab_cache_t *cache, int flags)
670
void * slab_alloc(slab_cache_t *cache, int flags)
663
{
671
{
664
    ipl_t ipl;
672
    ipl_t ipl;
665
    void *result = NULL;
673
    void *result = NULL;
666
   
674
   
667
    /* Disable interrupts to avoid deadlocks with interrupt handlers */
675
    /* Disable interrupts to avoid deadlocks with interrupt handlers */
668
    ipl = interrupts_disable();
676
    ipl = interrupts_disable();
669
 
677
 
670
    if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
678
    if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
671
        result = magazine_obj_get(cache);
679
        result = magazine_obj_get(cache);
672
 
680
 
673
    if (!result) {
681
    if (!result)
674
        spinlock_lock(&cache->lock);
-
 
675
        result = slab_obj_create(cache, flags);
682
        result = slab_obj_create(cache, flags);
676
        spinlock_unlock(&cache->lock);
-
 
677
    }
-
 
678
 
683
 
679
    interrupts_restore(ipl);
684
    interrupts_restore(ipl);
680
 
685
 
681
    if (result)
686
    if (result)
682
        atomic_inc(&cache->allocated_objs);
687
        atomic_inc(&cache->allocated_objs);
683
 
688
 
684
    return result;
689
    return result;
685
}
690
}
686
 
691
 
687
/** Return object to cache, use slab if known  */
692
/** Return object to cache, use slab if known  */
688
static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab)
693
static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab)
689
{
694
{
690
    ipl_t ipl;
695
    ipl_t ipl;
691
 
696
 
692
    ipl = interrupts_disable();
697
    ipl = interrupts_disable();
693
 
698
 
694
    if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \
699
    if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \
695
        || magazine_obj_put(cache, obj)) {
700
        || magazine_obj_put(cache, obj)) {
696
        spinlock_lock(&cache->lock);
-
 
-
 
701
 
697
        slab_obj_destroy(cache, obj, slab);
702
        slab_obj_destroy(cache, obj, slab);
698
        spinlock_unlock(&cache->lock);
-
 
-
 
703
 
699
    }
704
    }
700
    interrupts_restore(ipl);
705
    interrupts_restore(ipl);
701
    atomic_dec(&cache->allocated_objs);
706
    atomic_dec(&cache->allocated_objs);
702
}
707
}
703
 
708
 
704
/** Return slab object to cache */
709
/** Return slab object to cache */
705
void slab_free(slab_cache_t *cache, void *obj)
710
void slab_free(slab_cache_t *cache, void *obj)
706
{
711
{
707
    _slab_free(cache,obj,NULL);
712
    _slab_free(cache,obj,NULL);
708
}
713
}
709
 
714
 
710
/* Go through all caches and reclaim what is possible */
715
/* Go through all caches and reclaim what is possible */
711
count_t slab_reclaim(int flags)
716
count_t slab_reclaim(int flags)
712
{
717
{
713
    slab_cache_t *cache;
718
    slab_cache_t *cache;
714
    link_t *cur;
719
    link_t *cur;
715
    count_t frames = 0;
720
    count_t frames = 0;
716
 
721
 
717
    spinlock_lock(&slab_cache_lock);
722
    spinlock_lock(&slab_cache_lock);
718
 
723
 
-
 
724
    /* TODO: Add assert, that interrupts are disabled, otherwise
-
 
725
     * memory allocation from interrupts can deadlock.
-
 
726
     */
-
 
727
 
719
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
728
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
720
        cache = list_get_instance(cur, slab_cache_t, link);
729
        cache = list_get_instance(cur, slab_cache_t, link);
721
        frames += _slab_reclaim(cache, flags);
730
        frames += _slab_reclaim(cache, flags);
722
    }
731
    }
723
 
732
 
724
    spinlock_unlock(&slab_cache_lock);
733
    spinlock_unlock(&slab_cache_lock);
725
 
734
 
726
    return frames;
735
    return frames;
727
}
736
}
728
 
737
 
729
 
738
 
730
/* Print list of slabs */
739
/* Print list of slabs */
731
void slab_print_list(void)
740
void slab_print_list(void)
732
{
741
{
733
    slab_cache_t *cache;
742
    slab_cache_t *cache;
734
    link_t *cur;
743
    link_t *cur;
735
 
744
 
736
    spinlock_lock(&slab_cache_lock);
745
    spinlock_lock(&slab_cache_lock);
737
    printf("SLAB name\tOsize\tPages\tObj/pg\tSlabs\tCached\tAllocobjs\tCtl\n");
746
    printf("SLAB name\tOsize\tPages\tObj/pg\tSlabs\tCached\tAllocobjs\tCtl\n");
738
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
747
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
739
        cache = list_get_instance(cur, slab_cache_t, link);
748
        cache = list_get_instance(cur, slab_cache_t, link);
740
        printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t\t%s\n", cache->name, cache->size,
749
        printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t\t%s\n", cache->name, cache->size,
741
               (1 << cache->order), cache->objects,
750
               (1 << cache->order), cache->objects,
742
               atomic_get(&cache->allocated_slabs),
751
               atomic_get(&cache->allocated_slabs),
743
               atomic_get(&cache->cached_objs),
752
               atomic_get(&cache->cached_objs),
744
               atomic_get(&cache->allocated_objs),
753
               atomic_get(&cache->allocated_objs),
745
               cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out");
754
               cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out");
746
    }
755
    }
747
    spinlock_unlock(&slab_cache_lock);
756
    spinlock_unlock(&slab_cache_lock);
748
}
757
}
749
 
758
 
750
void slab_cache_init(void)
759
void slab_cache_init(void)
751
{
760
{
752
    int i, size;
761
    int i, size;
753
 
762
 
754
    /* Initialize magazine cache */
763
    /* Initialize magazine cache */
755
    _slab_cache_create(&mag_cache,
764
    _slab_cache_create(&mag_cache,
756
               "slab_magazine",
765
               "slab_magazine",
757
               sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*),
766
               sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*),
758
               sizeof(__address),
767
               sizeof(__address),
759
               NULL, NULL,
768
               NULL, NULL,
760
               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
769
               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
761
    /* Initialize slab_cache cache */
770
    /* Initialize slab_cache cache */
762
    _slab_cache_create(&slab_cache_cache,
771
    _slab_cache_create(&slab_cache_cache,
763
               "slab_cache",
772
               "slab_cache",
764
               sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]),
773
               sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]),
765
               sizeof(__address),
774
               sizeof(__address),
766
               NULL, NULL,
775
               NULL, NULL,
767
               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
776
               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
768
    /* Initialize external slab cache */
777
    /* Initialize external slab cache */
769
    slab_extern_cache = slab_cache_create("slab_extern",
778
    slab_extern_cache = slab_cache_create("slab_extern",
770
                          sizeof(slab_t),
779
                          sizeof(slab_t),
771
                          0, NULL, NULL,
780
                          0, NULL, NULL,
772
                          SLAB_CACHE_SLINSIDE);
781
                          SLAB_CACHE_SLINSIDE);
773
 
782
 
774
    /* Initialize structures for malloc */
783
    /* Initialize structures for malloc */
775
    for (i=0, size=(1<<SLAB_MIN_MALLOC_W);
784
    for (i=0, size=(1<<SLAB_MIN_MALLOC_W);
776
         i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1);
785
         i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1);
777
         i++, size <<= 1) {
786
         i++, size <<= 1) {
778
        malloc_caches[i] = slab_cache_create(malloc_names[i],
787
        malloc_caches[i] = slab_cache_create(malloc_names[i],
779
                             size, 0,
788
                             size, 0,
780
                             NULL,NULL,0);
789
                             NULL,NULL,0);
781
    }
790
    }
782
}
791
}
783
 
792
 
784
/**************************************/
793
/**************************************/
785
/* kalloc/kfree functions             */
794
/* kalloc/kfree functions             */
786
void * kalloc(unsigned int size, int flags)
795
void * kalloc(unsigned int size, int flags)
787
{
796
{
788
    int idx;
797
    int idx;
789
   
798
   
790
    ASSERT( size && size <= (1 << SLAB_MAX_MALLOC_W));
799
    ASSERT( size && size <= (1 << SLAB_MAX_MALLOC_W));
791
   
800
   
792
    if (size < (1 << SLAB_MIN_MALLOC_W))
801
    if (size < (1 << SLAB_MIN_MALLOC_W))
793
        size = (1 << SLAB_MIN_MALLOC_W);
802
        size = (1 << SLAB_MIN_MALLOC_W);
794
 
803
 
795
    idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1;
804
    idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1;
796
 
805
 
797
    return slab_alloc(malloc_caches[idx], flags);
806
    return slab_alloc(malloc_caches[idx], flags);
798
}
807
}
799
 
808
 
800
 
809
 
801
void kfree(void *obj)
810
void kfree(void *obj)
802
{
811
{
803
    slab_t *slab = obj2slab(obj);
812
    slab_t *slab = obj2slab(obj);
804
   
813
   
805
    _slab_free(slab->cache, obj, slab);
814
    _slab_free(slab->cache, obj, slab);
806
}
815
}
807
 
816