Rev 2123 | Rev 2745 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2123 | Rev 2124 | ||
---|---|---|---|
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 | /** @addtogroup genericmm |
29 | /** @addtogroup genericmm |
30 | * @{ |
30 | * @{ |
31 | */ |
31 | */ |
32 | 32 | ||
33 | /** |
33 | /** |
34 | * @file |
34 | * @file |
35 | * @brief Slab allocator. |
35 | * @brief Slab allocator. |
36 | * |
36 | * |
37 | * The slab allocator is closely modelled after OpenSolaris slab allocator. |
37 | * The slab allocator is closely modelled after OpenSolaris slab allocator. |
38 | * @see http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/ |
38 | * @see http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/ |
39 | * |
39 | * |
40 | * with the following exceptions: |
40 | * with the following exceptions: |
41 | * @li empty slabs are deallocated immediately |
41 | * @li empty slabs are deallocated immediately |
42 | * (in Linux they are kept in linked list, in Solaris ???) |
42 | * (in Linux they are kept in linked list, in Solaris ???) |
43 | * @li empty magazines are deallocated when not needed |
43 | * @li empty magazines are deallocated when not needed |
44 | * (in Solaris they are held in linked list in slab cache) |
44 | * (in Solaris they are held in linked list in slab cache) |
45 | * |
45 | * |
46 | * Following features are not currently supported but would be easy to do: |
46 | * Following features are not currently supported but would be easy to do: |
47 | * @li cache coloring |
47 | * @li cache coloring |
48 | * @li dynamic magazine growing (different magazine sizes are already |
48 | * @li dynamic magazine growing (different magazine sizes are already |
49 | * supported, but we would need to adjust allocation strategy) |
49 | * supported, but we would need to adjust allocation strategy) |
50 | * |
50 | * |
51 | * The slab allocator supports per-CPU caches ('magazines') to facilitate |
51 | * The slab allocator supports per-CPU caches ('magazines') to facilitate |
52 | * good SMP scaling. |
52 | * good SMP scaling. |
53 | * |
53 | * |
54 | * When a new object is being allocated, it is first checked, if it is |
54 | * When a new object is being allocated, it is first checked, if it is |
55 | * available in a CPU-bound magazine. If it is not found there, it is |
55 | * available in a CPU-bound magazine. If it is not found there, it is |
56 | * allocated from a CPU-shared slab - if a partially full one is found, |
56 | * allocated from a CPU-shared slab - if a partially full one is found, |
57 | * it is used, otherwise a new one is allocated. |
57 | * it is used, otherwise a new one is allocated. |
58 | * |
58 | * |
59 | * When an object is being deallocated, it is put to a CPU-bound magazine. |
59 | * When an object is being deallocated, it is put to a CPU-bound magazine. |
60 | * If there is no such magazine, a new one is allocated (if this fails, |
60 | * If there is no such magazine, a new one is allocated (if this fails, |
61 | * the object is deallocated into slab). If the magazine is full, it is |
61 | * the object is deallocated into slab). If the magazine is full, it is |
62 | * put into cpu-shared list of magazines and a new one is allocated. |
62 | * put into cpu-shared list of magazines and a new one is allocated. |
63 | * |
63 | * |
64 | * The CPU-bound magazine is actually a pair of magazines in order to avoid |
64 | * The CPU-bound magazine is actually a pair of magazines in order to avoid |
65 | * thrashing when somebody is allocating/deallocating 1 item at the magazine |
65 | * thrashing when somebody is allocating/deallocating 1 item at the magazine |
66 | * size boundary. LIFO order is enforced, which should avoid fragmentation |
66 | * size boundary. LIFO order is enforced, which should avoid fragmentation |
67 | * as much as possible. |
67 | * as much as possible. |
68 | * |
68 | * |
69 | * Every cache contains list of full slabs and list of partially full slabs. |
69 | * Every cache contains list of full slabs and list of partially full slabs. |
70 | * Empty slabs are immediately freed (thrashing will be avoided because |
70 | * Empty slabs are immediately freed (thrashing will be avoided because |
71 | * of magazines). |
71 | * of magazines). |
72 | * |
72 | * |
73 | * The slab information structure is kept inside the data area, if possible. |
73 | * The slab information structure is kept inside the data area, if possible. |
74 | * The cache can be marked that it should not use magazines. This is used |
74 | * The cache can be marked that it should not use magazines. This is used |
75 | * only for slab related caches to avoid deadlocks and infinite recursion |
75 | * only for slab related caches to avoid deadlocks and infinite recursion |
76 | * (the slab allocator uses itself for allocating all it's control structures). |
76 | * (the slab allocator uses itself for allocating all it's control structures). |
77 | * |
77 | * |
78 | * The slab allocator allocates a lot of space and does not free it. When |
78 | * The slab allocator allocates a lot of space and does not free it. When |
79 | * the frame allocator fails to allocate a frame, it calls slab_reclaim(). |
79 | * the frame allocator fails to allocate a frame, it calls slab_reclaim(). |
80 | * It tries 'light reclaim' first, then brutal reclaim. The light reclaim |
80 | * It tries 'light reclaim' first, then brutal reclaim. The light reclaim |
81 | * releases slabs from cpu-shared magazine-list, until at least 1 slab |
81 | * releases slabs from cpu-shared magazine-list, until at least 1 slab |
82 | * is deallocated in each cache (this algorithm should probably change). |
82 | * is deallocated in each cache (this algorithm should probably change). |
83 | * The brutal reclaim removes all cached objects, even from CPU-bound |
83 | * The brutal reclaim removes all cached objects, even from CPU-bound |
84 | * magazines. |
84 | * magazines. |
85 | * |
85 | * |
86 | * @todo |
86 | * @todo |
87 | * For better CPU-scaling the magazine allocation strategy should |
87 | * For better CPU-scaling the magazine allocation strategy should |
88 | * be extended. Currently, if the cache does not have magazine, it asks |
88 | * be extended. Currently, if the cache does not have magazine, it asks |
89 | * for non-cpu cached magazine cache to provide one. It might be feasible |
89 | * for non-cpu cached magazine cache to provide one. It might be feasible |
90 | * to add cpu-cached magazine cache (which would allocate it's magazines |
90 | * to add cpu-cached magazine cache (which would allocate it's magazines |
91 | * from non-cpu-cached mag. cache). This would provide a nice per-cpu |
91 | * from non-cpu-cached mag. cache). This would provide a nice per-cpu |
92 | * buffer. The other possibility is to use the per-cache |
92 | * buffer. The other possibility is to use the per-cache |
93 | * 'empty-magazine-list', which decreases competing for 1 per-system |
93 | * 'empty-magazine-list', which decreases competing for 1 per-system |
94 | * magazine cache. |
94 | * magazine cache. |
95 | * |
95 | * |
96 | * @todo |
96 | * @todo |
97 | * it might be good to add granularity of locks even to slab level, |
97 | * it might be good to add granularity of locks even to slab level, |
98 | * we could then try_spinlock over all partial slabs and thus improve |
98 | * we could then try_spinlock over all partial slabs and thus improve |
99 | * scalability even on slab level |
99 | * scalability even on slab level |
100 | */ |
100 | */ |
101 | 101 | ||
102 | #include <synch/spinlock.h> |
102 | #include <synch/spinlock.h> |
103 | #include <mm/slab.h> |
103 | #include <mm/slab.h> |
104 | #include <adt/list.h> |
104 | #include <adt/list.h> |
105 | #include <memstr.h> |
105 | #include <memstr.h> |
106 | #include <align.h> |
106 | #include <align.h> |
107 | #include <mm/frame.h> |
107 | #include <mm/frame.h> |
108 | #include <config.h> |
108 | #include <config.h> |
109 | #include <print.h> |
109 | #include <print.h> |
110 | #include <arch.h> |
110 | #include <arch.h> |
111 | #include <panic.h> |
111 | #include <panic.h> |
112 | #include <debug.h> |
112 | #include <debug.h> |
113 | #include <bitops.h> |
113 | #include <bitops.h> |
- | 114 | #include <macros.h> |
|
114 | 115 | ||
115 | SPINLOCK_INITIALIZE(slab_cache_lock); |
116 | SPINLOCK_INITIALIZE(slab_cache_lock); |
116 | static LIST_INITIALIZE(slab_cache_list); |
117 | static LIST_INITIALIZE(slab_cache_list); |
117 | 118 | ||
118 | /** Magazine cache */ |
119 | /** Magazine cache */ |
119 | static slab_cache_t mag_cache; |
120 | static slab_cache_t mag_cache; |
120 | /** Cache for cache descriptors */ |
121 | /** Cache for cache descriptors */ |
121 | static slab_cache_t slab_cache_cache; |
122 | static slab_cache_t slab_cache_cache; |
122 | /** Cache for external slab descriptors |
123 | /** Cache for external slab descriptors |
123 | * This time we want per-cpu cache, so do not make it static |
124 | * This time we want per-cpu cache, so do not make it static |
124 | * - using slab for internal slab structures will not deadlock, |
125 | * - using slab for internal slab structures will not deadlock, |
125 | * as all slab structures are 'small' - control structures of |
126 | * as all slab structures are 'small' - control structures of |
126 | * their caches do not require further allocation |
127 | * their caches do not require further allocation |
127 | */ |
128 | */ |
128 | static slab_cache_t *slab_extern_cache; |
129 | static slab_cache_t *slab_extern_cache; |
129 | /** Caches for malloc */ |
130 | /** Caches for malloc */ |
130 | static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1]; |
131 | static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W - SLAB_MIN_MALLOC_W + 1]; |
131 | char *malloc_names[] = { |
132 | char *malloc_names[] = { |
- | 133 | "malloc-16", |
|
- | 134 | "malloc-32", |
|
- | 135 | "malloc-64", |
|
132 | "malloc-16","malloc-32","malloc-64","malloc-128", |
136 | "malloc-128", |
133 | "malloc-256","malloc-512","malloc-1K","malloc-2K", |
137 | "malloc-256", |
- | 138 | "malloc-512", |
|
- | 139 | "malloc-1K", |
|
- | 140 | "malloc-2K", |
|
- | 141 | "malloc-4K", |
|
- | 142 | "malloc-8K", |
|
- | 143 | "malloc-16K", |
|
134 | "malloc-4K","malloc-8K","malloc-16K","malloc-32K", |
144 | "malloc-32K", |
- | 145 | "malloc-64K", |
|
135 | "malloc-64K","malloc-128K","malloc-256K" |
146 | "malloc-128K", |
- | 147 | "malloc-256K" |
|
136 | }; |
148 | }; |
137 | 149 | ||
138 | /** Slab descriptor */ |
150 | /** Slab descriptor */ |
139 | typedef struct { |
151 | typedef struct { |
140 | slab_cache_t *cache; /**< Pointer to parent cache. */ |
152 | slab_cache_t *cache; /**< Pointer to parent cache. */ |
141 | link_t link; /**< List of full/partial slabs. */ |
153 | link_t link; /**< List of full/partial slabs. */ |
142 | void *start; /**< Start address of first available item. */ |
154 | void *start; /**< Start address of first available item. */ |
143 | count_t available; /**< Count of available items in this slab. */ |
155 | count_t available; /**< Count of available items in this slab. */ |
144 | index_t nextavail; /**< The index of next available item. */ |
156 | index_t nextavail; /**< The index of next available item. */ |
145 | }slab_t; |
157 | } slab_t; |
146 | 158 | ||
147 | #ifdef CONFIG_DEBUG |
159 | #ifdef CONFIG_DEBUG |
148 | static int _slab_initialized = 0; |
160 | static int _slab_initialized = 0; |
149 | #endif |
161 | #endif |
150 | 162 | ||
151 | /**************************************/ |
163 | /**************************************/ |
152 | /* Slab allocation functions */ |
164 | /* Slab allocation functions */ |
153 | 165 | ||
154 | /** |
166 | /** |
155 | * Allocate frames for slab space and initialize |
167 | * Allocate frames for slab space and initialize |
156 | * |
168 | * |
157 | */ |
169 | */ |
158 | static slab_t * slab_space_alloc(slab_cache_t *cache, int flags) |
170 | static slab_t * slab_space_alloc(slab_cache_t *cache, int flags) |
159 | { |
171 | { |
160 | void *data; |
172 | void *data; |
161 | slab_t *slab; |
173 | slab_t *slab; |
162 | size_t fsize; |
174 | size_t fsize; |
163 | int i; |
175 | int i; |
164 | unsigned int zone = 0; |
176 | unsigned int zone = 0; |
165 | 177 | ||
166 | data = frame_alloc_generic(cache->order, FRAME_KA | flags, &zone); |
178 | data = frame_alloc_generic(cache->order, FRAME_KA | flags, &zone); |
167 | if (!data) { |
179 | if (!data) { |
168 | return NULL; |
180 | return NULL; |
169 | } |
181 | } |
170 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { |
182 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { |
171 | slab = slab_alloc(slab_extern_cache, flags); |
183 | slab = slab_alloc(slab_extern_cache, flags); |
172 | if (!slab) { |
184 | if (!slab) { |
173 | frame_free(KA2PA(data)); |
185 | frame_free(KA2PA(data)); |
174 | return NULL; |
186 | return NULL; |
175 | } |
187 | } |
176 | } else { |
188 | } else { |
177 | fsize = (PAGE_SIZE << cache->order); |
189 | fsize = (PAGE_SIZE << cache->order); |
178 | slab = data + fsize - sizeof(*slab); |
190 | slab = data + fsize - sizeof(*slab); |
179 | } |
191 | } |
180 | 192 | ||
181 | /* Fill in slab structures */ |
193 | /* Fill in slab structures */ |
182 | for (i=0; i < (1 << cache->order); i++) |
194 | for (i=0; i < (1 << cache->order); i++) |
183 | frame_set_parent(ADDR2PFN(KA2PA(data))+i, slab, zone); |
195 | frame_set_parent(ADDR2PFN(KA2PA(data))+i, slab, zone); |
184 | 196 | ||
185 | slab->start = data; |
197 | slab->start = data; |
186 | slab->available = cache->objects; |
198 | slab->available = cache->objects; |
187 | slab->nextavail = 0; |
199 | slab->nextavail = 0; |
188 | slab->cache = cache; |
200 | slab->cache = cache; |
189 | 201 | ||
190 | for (i=0; i<cache->objects;i++) |
202 | for (i=0; i<cache->objects;i++) |
191 | *((int *) (slab->start + i*cache->size)) = i+1; |
203 | *((int *) (slab->start + i*cache->size)) = i+1; |
192 | 204 | ||
193 | atomic_inc(&cache->allocated_slabs); |
205 | atomic_inc(&cache->allocated_slabs); |
194 | return slab; |
206 | return slab; |
195 | } |
207 | } |
196 | 208 | ||
197 | /** |
209 | /** |
198 | * Deallocate space associated with slab |
210 | * Deallocate space associated with slab |
199 | * |
211 | * |
200 | * @return number of freed frames |
212 | * @return number of freed frames |
201 | */ |
213 | */ |
202 | static count_t slab_space_free(slab_cache_t *cache, slab_t *slab) |
214 | static count_t slab_space_free(slab_cache_t *cache, slab_t *slab) |
203 | { |
215 | { |
204 | frame_free(KA2PA(slab->start)); |
216 | frame_free(KA2PA(slab->start)); |
205 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) |
217 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) |
206 | slab_free(slab_extern_cache, slab); |
218 | slab_free(slab_extern_cache, slab); |
207 | 219 | ||
208 | atomic_dec(&cache->allocated_slabs); |
220 | atomic_dec(&cache->allocated_slabs); |
209 | 221 | ||
210 | return 1 << cache->order; |
222 | return 1 << cache->order; |
211 | } |
223 | } |
212 | 224 | ||
213 | /** Map object to slab structure */ |
225 | /** Map object to slab structure */ |
214 | static slab_t * obj2slab(void *obj) |
226 | static slab_t * obj2slab(void *obj) |
215 | { |
227 | { |
216 | return (slab_t *)frame_get_parent(ADDR2PFN(KA2PA(obj)), 0); |
228 | return (slab_t *) frame_get_parent(ADDR2PFN(KA2PA(obj)), 0); |
217 | } |
229 | } |
218 | 230 | ||
219 | /**************************************/ |
231 | /**************************************/ |
220 | /* Slab functions */ |
232 | /* Slab functions */ |
221 | 233 | ||
222 | 234 | ||
223 | /** |
235 | /** |
224 | * Return object to slab and call a destructor |
236 | * Return object to slab and call a destructor |
225 | * |
237 | * |
226 | * @param slab If the caller knows directly slab of the object, otherwise NULL |
238 | * @param slab If the caller knows directly slab of the object, otherwise NULL |
227 | * |
239 | * |
228 | * @return Number of freed pages |
240 | * @return Number of freed pages |
229 | */ |
241 | */ |
230 | static count_t slab_obj_destroy(slab_cache_t *cache, void *obj, |
242 | static count_t slab_obj_destroy(slab_cache_t *cache, void *obj, |
231 | slab_t *slab) |
243 | slab_t *slab) |
232 | { |
244 | { |
233 | int freed = 0; |
245 | int freed = 0; |
234 | 246 | ||
235 | if (!slab) |
247 | if (!slab) |
236 | slab = obj2slab(obj); |
248 | slab = obj2slab(obj); |
237 | 249 | ||
238 | ASSERT(slab->cache == cache); |
250 | ASSERT(slab->cache == cache); |
239 | 251 | ||
240 | if (cache->destructor) |
252 | if (cache->destructor) |
241 | freed = cache->destructor(obj); |
253 | freed = cache->destructor(obj); |
242 | 254 | ||
243 | spinlock_lock(&cache->slablock); |
255 | spinlock_lock(&cache->slablock); |
244 | ASSERT(slab->available < cache->objects); |
256 | ASSERT(slab->available < cache->objects); |
245 | 257 | ||
246 | *((int *)obj) = slab->nextavail; |
258 | *((int *)obj) = slab->nextavail; |
247 | slab->nextavail = (obj - slab->start)/cache->size; |
259 | slab->nextavail = (obj - slab->start)/cache->size; |
248 | slab->available++; |
260 | slab->available++; |
249 | 261 | ||
250 | /* Move it to correct list */ |
262 | /* Move it to correct list */ |
251 | if (slab->available == cache->objects) { |
263 | if (slab->available == cache->objects) { |
252 | /* Free associated memory */ |
264 | /* Free associated memory */ |
253 | list_remove(&slab->link); |
265 | list_remove(&slab->link); |
254 | spinlock_unlock(&cache->slablock); |
266 | spinlock_unlock(&cache->slablock); |
255 | 267 | ||
256 | return freed + slab_space_free(cache, slab); |
268 | return freed + slab_space_free(cache, slab); |
257 | 269 | ||
258 | } else if (slab->available == 1) { |
270 | } else if (slab->available == 1) { |
259 | /* It was in full, move to partial */ |
271 | /* It was in full, move to partial */ |
260 | list_remove(&slab->link); |
272 | list_remove(&slab->link); |
261 | list_prepend(&slab->link, &cache->partial_slabs); |
273 | list_prepend(&slab->link, &cache->partial_slabs); |
262 | } |
274 | } |
263 | spinlock_unlock(&cache->slablock); |
275 | spinlock_unlock(&cache->slablock); |
264 | return freed; |
276 | return freed; |
265 | } |
277 | } |
266 | 278 | ||
267 | /** |
279 | /** |
268 | * Take new object from slab or create new if needed |
280 | * Take new object from slab or create new if needed |
269 | * |
281 | * |
270 | * @return Object address or null |
282 | * @return Object address or null |
271 | */ |
283 | */ |
272 | static void * slab_obj_create(slab_cache_t *cache, int flags) |
284 | static void * slab_obj_create(slab_cache_t *cache, int flags) |
273 | { |
285 | { |
274 | slab_t *slab; |
286 | slab_t *slab; |
275 | void *obj; |
287 | void *obj; |
276 | 288 | ||
277 | spinlock_lock(&cache->slablock); |
289 | spinlock_lock(&cache->slablock); |
278 | 290 | ||
279 | if (list_empty(&cache->partial_slabs)) { |
291 | if (list_empty(&cache->partial_slabs)) { |
280 | /* Allow recursion and reclaiming |
292 | /* Allow recursion and reclaiming |
281 | * - this should work, as the slab control structures |
293 | * - this should work, as the slab control structures |
282 | * are small and do not need to allocate with anything |
294 | * are small and do not need to allocate with anything |
283 | * other than frame_alloc when they are allocating, |
295 | * other than frame_alloc when they are allocating, |
284 | * that's why we should get recursion at most 1-level deep |
296 | * that's why we should get recursion at most 1-level deep |
285 | */ |
297 | */ |
286 | spinlock_unlock(&cache->slablock); |
298 | spinlock_unlock(&cache->slablock); |
287 | slab = slab_space_alloc(cache, flags); |
299 | slab = slab_space_alloc(cache, flags); |
288 | if (!slab) |
300 | if (!slab) |
289 | return NULL; |
301 | return NULL; |
290 | spinlock_lock(&cache->slablock); |
302 | spinlock_lock(&cache->slablock); |
291 | } else { |
303 | } else { |
292 | slab = list_get_instance(cache->partial_slabs.next, slab_t, link); |
304 | slab = list_get_instance(cache->partial_slabs.next, slab_t, link); |
293 | list_remove(&slab->link); |
305 | list_remove(&slab->link); |
294 | } |
306 | } |
295 | obj = slab->start + slab->nextavail * cache->size; |
307 | obj = slab->start + slab->nextavail * cache->size; |
296 | slab->nextavail = *((int *)obj); |
308 | slab->nextavail = *((int *)obj); |
297 | slab->available--; |
309 | slab->available--; |
298 | 310 | ||
299 | if (!slab->available) |
311 | if (!slab->available) |
300 | list_prepend(&slab->link, &cache->full_slabs); |
312 | list_prepend(&slab->link, &cache->full_slabs); |
301 | else |
313 | else |
302 | list_prepend(&slab->link, &cache->partial_slabs); |
314 | list_prepend(&slab->link, &cache->partial_slabs); |
303 | 315 | ||
304 | spinlock_unlock(&cache->slablock); |
316 | spinlock_unlock(&cache->slablock); |
305 | 317 | ||
306 | if (cache->constructor && cache->constructor(obj, flags)) { |
318 | if (cache->constructor && cache->constructor(obj, flags)) { |
307 | /* Bad, bad, construction failed */ |
319 | /* Bad, bad, construction failed */ |
308 | slab_obj_destroy(cache, obj, slab); |
320 | slab_obj_destroy(cache, obj, slab); |
309 | return NULL; |
321 | return NULL; |
310 | } |
322 | } |
311 | return obj; |
323 | return obj; |
312 | } |
324 | } |
313 | 325 | ||
314 | /**************************************/ |
326 | /**************************************/ |
315 | /* CPU-Cache slab functions */ |
327 | /* CPU-Cache slab functions */ |
316 | 328 | ||
317 | /** |
329 | /** |
318 | * Finds a full magazine in cache, takes it from list |
330 | * Finds a full magazine in cache, takes it from list |
319 | * and returns it |
331 | * and returns it |
320 | * |
332 | * |
321 | * @param first If true, return first, else last mag |
333 | * @param first If true, return first, else last mag |
322 | */ |
334 | */ |
323 | static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache, |
335 | static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache, |
324 | int first) |
336 | int first) |
325 | { |
337 | { |
326 | slab_magazine_t *mag = NULL; |
338 | slab_magazine_t *mag = NULL; |
327 | link_t *cur; |
339 | link_t *cur; |
328 | 340 | ||
329 | spinlock_lock(&cache->maglock); |
341 | spinlock_lock(&cache->maglock); |
330 | if (!list_empty(&cache->magazines)) { |
342 | if (!list_empty(&cache->magazines)) { |
331 | if (first) |
343 | if (first) |
332 | cur = cache->magazines.next; |
344 | cur = cache->magazines.next; |
333 | else |
345 | else |
334 | cur = cache->magazines.prev; |
346 | cur = cache->magazines.prev; |
335 | mag = list_get_instance(cur, slab_magazine_t, link); |
347 | mag = list_get_instance(cur, slab_magazine_t, link); |
336 | list_remove(&mag->link); |
348 | list_remove(&mag->link); |
337 | atomic_dec(&cache->magazine_counter); |
349 | atomic_dec(&cache->magazine_counter); |
338 | } |
350 | } |
339 | spinlock_unlock(&cache->maglock); |
351 | spinlock_unlock(&cache->maglock); |
340 | return mag; |
352 | return mag; |
341 | } |
353 | } |
342 | 354 | ||
343 | /** Prepend magazine to magazine list in cache */ |
355 | /** Prepend magazine to magazine list in cache */ |
344 | static void put_mag_to_cache(slab_cache_t *cache, slab_magazine_t *mag) |
356 | static void put_mag_to_cache(slab_cache_t *cache, slab_magazine_t *mag) |
345 | { |
357 | { |
346 | spinlock_lock(&cache->maglock); |
358 | spinlock_lock(&cache->maglock); |
347 | 359 | ||
348 | list_prepend(&mag->link, &cache->magazines); |
360 | list_prepend(&mag->link, &cache->magazines); |
349 | atomic_inc(&cache->magazine_counter); |
361 | atomic_inc(&cache->magazine_counter); |
350 | 362 | ||
351 | spinlock_unlock(&cache->maglock); |
363 | spinlock_unlock(&cache->maglock); |
352 | } |
364 | } |
353 | 365 | ||
354 | /** |
366 | /** |
355 | * Free all objects in magazine and free memory associated with magazine |
367 | * Free all objects in magazine and free memory associated with magazine |
356 | * |
368 | * |
357 | * @return Number of freed pages |
369 | * @return Number of freed pages |
358 | */ |
370 | */ |
359 | static count_t magazine_destroy(slab_cache_t *cache, |
371 | static count_t magazine_destroy(slab_cache_t *cache, |
360 | slab_magazine_t *mag) |
372 | slab_magazine_t *mag) |
361 | { |
373 | { |
362 | int i; |
374 | int i; |
363 | count_t frames = 0; |
375 | count_t frames = 0; |
364 | 376 | ||
365 | for (i=0;i < mag->busy; i++) { |
377 | for (i=0;i < mag->busy; i++) { |
366 | frames += slab_obj_destroy(cache, mag->objs[i], NULL); |
378 | frames += slab_obj_destroy(cache, mag->objs[i], NULL); |
367 | atomic_dec(&cache->cached_objs); |
379 | atomic_dec(&cache->cached_objs); |
368 | } |
380 | } |
369 | 381 | ||
370 | slab_free(&mag_cache, mag); |
382 | slab_free(&mag_cache, mag); |
371 | 383 | ||
372 | return frames; |
384 | return frames; |
373 | } |
385 | } |
374 | 386 | ||
375 | /** |
387 | /** |
376 | * Find full magazine, set it as current and return it |
388 | * Find full magazine, set it as current and return it |
377 | * |
389 | * |
378 | * Assume cpu_magazine lock is held |
390 | * Assume cpu_magazine lock is held |
379 | */ |
391 | */ |
380 | static slab_magazine_t * get_full_current_mag(slab_cache_t *cache) |
392 | static slab_magazine_t * get_full_current_mag(slab_cache_t *cache) |
381 | { |
393 | { |
382 | slab_magazine_t *cmag, *lastmag, *newmag; |
394 | slab_magazine_t *cmag, *lastmag, *newmag; |
383 | 395 | ||
384 | cmag = cache->mag_cache[CPU->id].current; |
396 | cmag = cache->mag_cache[CPU->id].current; |
385 | lastmag = cache->mag_cache[CPU->id].last; |
397 | lastmag = cache->mag_cache[CPU->id].last; |
386 | if (cmag) { /* First try local CPU magazines */ |
398 | if (cmag) { /* First try local CPU magazines */ |
387 | if (cmag->busy) |
399 | if (cmag->busy) |
388 | return cmag; |
400 | return cmag; |
389 | 401 | ||
390 | if (lastmag && lastmag->busy) { |
402 | if (lastmag && lastmag->busy) { |
391 | cache->mag_cache[CPU->id].current = lastmag; |
403 | cache->mag_cache[CPU->id].current = lastmag; |
392 | cache->mag_cache[CPU->id].last = cmag; |
404 | cache->mag_cache[CPU->id].last = cmag; |
393 | return lastmag; |
405 | return lastmag; |
394 | } |
406 | } |
395 | } |
407 | } |
396 | /* Local magazines are empty, import one from magazine list */ |
408 | /* Local magazines are empty, import one from magazine list */ |
397 | newmag = get_mag_from_cache(cache, 1); |
409 | newmag = get_mag_from_cache(cache, 1); |
398 | if (!newmag) |
410 | if (!newmag) |
399 | return NULL; |
411 | return NULL; |
400 | 412 | ||
401 | if (lastmag) |
413 | if (lastmag) |
402 | magazine_destroy(cache, lastmag); |
414 | magazine_destroy(cache, lastmag); |
403 | 415 | ||
404 | cache->mag_cache[CPU->id].last = cmag; |
416 | cache->mag_cache[CPU->id].last = cmag; |
405 | cache->mag_cache[CPU->id].current = newmag; |
417 | cache->mag_cache[CPU->id].current = newmag; |
406 | return newmag; |
418 | return newmag; |
407 | } |
419 | } |
408 | 420 | ||
409 | /** |
421 | /** |
410 | * Try to find object in CPU-cache magazines |
422 | * Try to find object in CPU-cache magazines |
411 | * |
423 | * |
412 | * @return Pointer to object or NULL if not available |
424 | * @return Pointer to object or NULL if not available |
413 | */ |
425 | */ |
414 | static void * magazine_obj_get(slab_cache_t *cache) |
426 | static void * magazine_obj_get(slab_cache_t *cache) |
415 | { |
427 | { |
416 | slab_magazine_t *mag; |
428 | slab_magazine_t *mag; |
417 | void *obj; |
429 | void *obj; |
418 | 430 | ||
419 | if (!CPU) |
431 | if (!CPU) |
420 | return NULL; |
432 | return NULL; |
421 | 433 | ||
422 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
434 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
423 | 435 | ||
424 | mag = get_full_current_mag(cache); |
436 | mag = get_full_current_mag(cache); |
425 | if (!mag) { |
437 | if (!mag) { |
426 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
438 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
427 | return NULL; |
439 | return NULL; |
428 | } |
440 | } |
429 | obj = mag->objs[--mag->busy]; |
441 | obj = mag->objs[--mag->busy]; |
430 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
442 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
431 | atomic_dec(&cache->cached_objs); |
443 | atomic_dec(&cache->cached_objs); |
432 | 444 | ||
433 | return obj; |
445 | return obj; |
434 | } |
446 | } |
435 | 447 | ||
436 | /** |
448 | /** |
437 | * Assure that the current magazine is empty, return pointer to it, or NULL if |
449 | * Assure that the current magazine is empty, return pointer to it, or NULL if |
438 | * no empty magazine is available and cannot be allocated |
450 | * no empty magazine is available and cannot be allocated |
439 | * |
451 | * |
440 | * Assume mag_cache[CPU->id].lock is held |
452 | * Assume mag_cache[CPU->id].lock is held |
441 | * |
453 | * |
442 | * We have 2 magazines bound to processor. |
454 | * We have 2 magazines bound to processor. |
443 | * First try the current. |
455 | * First try the current. |
444 | * If full, try the last. |
456 | * If full, try the last. |
445 | * If full, put to magazines list. |
457 | * If full, put to magazines list. |
446 | * allocate new, exchange last & current |
458 | * allocate new, exchange last & current |
447 | * |
459 | * |
448 | */ |
460 | */ |
449 | static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache) |
461 | static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache) |
450 | { |
462 | { |
451 | slab_magazine_t *cmag,*lastmag,*newmag; |
463 | slab_magazine_t *cmag,*lastmag,*newmag; |
452 | 464 | ||
453 | cmag = cache->mag_cache[CPU->id].current; |
465 | cmag = cache->mag_cache[CPU->id].current; |
454 | lastmag = cache->mag_cache[CPU->id].last; |
466 | lastmag = cache->mag_cache[CPU->id].last; |
455 | 467 | ||
456 | if (cmag) { |
468 | if (cmag) { |
457 | if (cmag->busy < cmag->size) |
469 | if (cmag->busy < cmag->size) |
458 | return cmag; |
470 | return cmag; |
459 | if (lastmag && lastmag->busy < lastmag->size) { |
471 | if (lastmag && lastmag->busy < lastmag->size) { |
460 | cache->mag_cache[CPU->id].last = cmag; |
472 | cache->mag_cache[CPU->id].last = cmag; |
461 | cache->mag_cache[CPU->id].current = lastmag; |
473 | cache->mag_cache[CPU->id].current = lastmag; |
462 | return lastmag; |
474 | return lastmag; |
463 | } |
475 | } |
464 | } |
476 | } |
465 | /* current | last are full | nonexistent, allocate new */ |
477 | /* current | last are full | nonexistent, allocate new */ |
466 | /* We do not want to sleep just because of caching */ |
478 | /* We do not want to sleep just because of caching */ |
467 | /* Especially we do not want reclaiming to start, as |
479 | /* Especially we do not want reclaiming to start, as |
468 | * this would deadlock */ |
480 | * this would deadlock */ |
469 | newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM); |
481 | newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM); |
470 | if (!newmag) |
482 | if (!newmag) |
471 | return NULL; |
483 | return NULL; |
472 | newmag->size = SLAB_MAG_SIZE; |
484 | newmag->size = SLAB_MAG_SIZE; |
473 | newmag->busy = 0; |
485 | newmag->busy = 0; |
474 | 486 | ||
475 | /* Flush last to magazine list */ |
487 | /* Flush last to magazine list */ |
476 | if (lastmag) |
488 | if (lastmag) |
477 | put_mag_to_cache(cache, lastmag); |
489 | put_mag_to_cache(cache, lastmag); |
478 | 490 | ||
479 | /* Move current as last, save new as current */ |
491 | /* Move current as last, save new as current */ |
480 | cache->mag_cache[CPU->id].last = cmag; |
492 | cache->mag_cache[CPU->id].last = cmag; |
481 | cache->mag_cache[CPU->id].current = newmag; |
493 | cache->mag_cache[CPU->id].current = newmag; |
482 | 494 | ||
483 | return newmag; |
495 | return newmag; |
484 | } |
496 | } |
485 | 497 | ||
486 | /** |
498 | /** |
487 | * Put object into CPU-cache magazine |
499 | * Put object into CPU-cache magazine |
488 | * |
500 | * |
489 | * @return 0 - success, -1 - could not get memory |
501 | * @return 0 - success, -1 - could not get memory |
490 | */ |
502 | */ |
491 | static int magazine_obj_put(slab_cache_t *cache, void *obj) |
503 | static int magazine_obj_put(slab_cache_t *cache, void *obj) |
492 | { |
504 | { |
493 | slab_magazine_t *mag; |
505 | slab_magazine_t *mag; |
494 | 506 | ||
495 | if (!CPU) |
507 | if (!CPU) |
496 | return -1; |
508 | return -1; |
497 | 509 | ||
498 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
510 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
499 | 511 | ||
500 | mag = make_empty_current_mag(cache); |
512 | mag = make_empty_current_mag(cache); |
501 | if (!mag) { |
513 | if (!mag) { |
502 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
514 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
503 | return -1; |
515 | return -1; |
504 | } |
516 | } |
505 | 517 | ||
506 | mag->objs[mag->busy++] = obj; |
518 | mag->objs[mag->busy++] = obj; |
507 | 519 | ||
508 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
520 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
509 | atomic_inc(&cache->cached_objs); |
521 | atomic_inc(&cache->cached_objs); |
510 | return 0; |
522 | return 0; |
511 | } |
523 | } |
512 | 524 | ||
513 | 525 | ||
514 | /**************************************/ |
526 | /**************************************/ |
515 | /* Slab cache functions */ |
527 | /* Slab cache functions */ |
516 | 528 | ||
517 | /** Return number of objects that fit in certain cache size */ |
529 | /** Return number of objects that fit in certain cache size */ |
518 | static int comp_objects(slab_cache_t *cache) |
530 | static int comp_objects(slab_cache_t *cache) |
519 | { |
531 | { |
520 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
532 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
521 | return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size; |
533 | return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size; |
522 | else |
534 | else |
523 | return (PAGE_SIZE << cache->order) / cache->size; |
535 | return (PAGE_SIZE << cache->order) / cache->size; |
524 | } |
536 | } |
525 | 537 | ||
526 | /** Return wasted space in slab */ |
538 | /** Return wasted space in slab */ |
527 | static int badness(slab_cache_t *cache) |
539 | static int badness(slab_cache_t *cache) |
528 | { |
540 | { |
529 | int objects; |
541 | int objects; |
530 | int ssize; |
542 | int ssize; |
531 | 543 | ||
532 | objects = comp_objects(cache); |
544 | objects = comp_objects(cache); |
533 | ssize = PAGE_SIZE << cache->order; |
545 | ssize = PAGE_SIZE << cache->order; |
534 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
546 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
535 | ssize -= sizeof(slab_t); |
547 | ssize -= sizeof(slab_t); |
536 | return ssize - objects*cache->size; |
548 | return ssize - objects*cache->size; |
537 | } |
549 | } |
538 | 550 | ||
539 | /** |
551 | /** |
540 | * Initialize mag_cache structure in slab cache |
552 | * Initialize mag_cache structure in slab cache |
541 | */ |
553 | */ |
542 | static void make_magcache(slab_cache_t *cache) |
554 | static void make_magcache(slab_cache_t *cache) |
543 | { |
555 | { |
544 | int i; |
556 | int i; |
545 | 557 | ||
546 | ASSERT(_slab_initialized >= 2); |
558 | ASSERT(_slab_initialized >= 2); |
547 | 559 | ||
548 | cache->mag_cache = malloc(sizeof(slab_mag_cache_t)*config.cpu_count,0); |
560 | cache->mag_cache = malloc(sizeof(slab_mag_cache_t)*config.cpu_count,0); |
549 | for (i=0; i < config.cpu_count; i++) { |
561 | for (i=0; i < config.cpu_count; i++) { |
550 | memsetb((uintptr_t)&cache->mag_cache[i], |
562 | memsetb((uintptr_t)&cache->mag_cache[i], |
551 | sizeof(cache->mag_cache[i]), 0); |
563 | sizeof(cache->mag_cache[i]), 0); |
552 | spinlock_initialize(&cache->mag_cache[i].lock, |
564 | spinlock_initialize(&cache->mag_cache[i].lock, |
553 | "slab_maglock_cpu"); |
565 | "slab_maglock_cpu"); |
554 | } |
566 | } |
555 | } |
567 | } |
556 | 568 | ||
557 | /** Initialize allocated memory as a slab cache */ |
569 | /** Initialize allocated memory as a slab cache */ |
558 | static void |
570 | static void |
559 | _slab_cache_create(slab_cache_t *cache, |
571 | _slab_cache_create(slab_cache_t *cache, |
560 | char *name, |
572 | char *name, |
561 | size_t size, |
573 | size_t size, |
562 | size_t align, |
574 | size_t align, |
563 | int (*constructor)(void *obj, int kmflag), |
575 | int (*constructor)(void *obj, int kmflag), |
564 | int (*destructor)(void *obj), |
576 | int (*destructor)(void *obj), |
565 | int flags) |
577 | int flags) |
566 | { |
578 | { |
567 | int pages; |
579 | int pages; |
568 | ipl_t ipl; |
580 | ipl_t ipl; |
569 | 581 | ||
570 | memsetb((uintptr_t)cache, sizeof(*cache), 0); |
582 | memsetb((uintptr_t)cache, sizeof(*cache), 0); |
571 | cache->name = name; |
583 | cache->name = name; |
572 | 584 | ||
573 | if (align < sizeof(unative_t)) |
585 | if (align < sizeof(unative_t)) |
574 | align = sizeof(unative_t); |
586 | align = sizeof(unative_t); |
575 | size = ALIGN_UP(size, align); |
587 | size = ALIGN_UP(size, align); |
576 | 588 | ||
577 | cache->size = size; |
589 | cache->size = size; |
578 | 590 | ||
579 | cache->constructor = constructor; |
591 | cache->constructor = constructor; |
580 | cache->destructor = destructor; |
592 | cache->destructor = destructor; |
581 | cache->flags = flags; |
593 | cache->flags = flags; |
582 | 594 | ||
583 | list_initialize(&cache->full_slabs); |
595 | list_initialize(&cache->full_slabs); |
584 | list_initialize(&cache->partial_slabs); |
596 | list_initialize(&cache->partial_slabs); |
585 | list_initialize(&cache->magazines); |
597 | list_initialize(&cache->magazines); |
586 | spinlock_initialize(&cache->slablock, "slab_lock"); |
598 | spinlock_initialize(&cache->slablock, "slab_lock"); |
587 | spinlock_initialize(&cache->maglock, "slab_maglock"); |
599 | spinlock_initialize(&cache->maglock, "slab_maglock"); |
588 | if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) |
600 | if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) |
589 | make_magcache(cache); |
601 | make_magcache(cache); |
590 | 602 | ||
591 | /* Compute slab sizes, object counts in slabs etc. */ |
603 | /* Compute slab sizes, object counts in slabs etc. */ |
592 | if (cache->size < SLAB_INSIDE_SIZE) |
604 | if (cache->size < SLAB_INSIDE_SIZE) |
593 | cache->flags |= SLAB_CACHE_SLINSIDE; |
605 | cache->flags |= SLAB_CACHE_SLINSIDE; |
594 | 606 | ||
595 | /* Minimum slab order */ |
607 | /* Minimum slab order */ |
596 | pages = SIZE2FRAMES(cache->size); |
608 | pages = SIZE2FRAMES(cache->size); |
597 | /* We need the 2^order >= pages */ |
609 | /* We need the 2^order >= pages */ |
598 | if (pages == 1) |
610 | if (pages == 1) |
599 | cache->order = 0; |
611 | cache->order = 0; |
600 | else |
612 | else |
601 | cache->order = fnzb(pages-1)+1; |
613 | cache->order = fnzb(pages-1)+1; |
602 | 614 | ||
603 | while (badness(cache) > SLAB_MAX_BADNESS(cache)) { |
615 | while (badness(cache) > SLAB_MAX_BADNESS(cache)) { |
604 | cache->order += 1; |
616 | cache->order += 1; |
605 | } |
617 | } |
606 | cache->objects = comp_objects(cache); |
618 | cache->objects = comp_objects(cache); |
607 | /* If info fits in, put it inside */ |
619 | /* If info fits in, put it inside */ |
608 | if (badness(cache) > sizeof(slab_t)) |
620 | if (badness(cache) > sizeof(slab_t)) |
609 | cache->flags |= SLAB_CACHE_SLINSIDE; |
621 | cache->flags |= SLAB_CACHE_SLINSIDE; |
610 | 622 | ||
611 | /* Add cache to cache list */ |
623 | /* Add cache to cache list */ |
612 | ipl = interrupts_disable(); |
624 | ipl = interrupts_disable(); |
613 | spinlock_lock(&slab_cache_lock); |
625 | spinlock_lock(&slab_cache_lock); |
614 | 626 | ||
615 | list_append(&cache->link, &slab_cache_list); |
627 | list_append(&cache->link, &slab_cache_list); |
616 | 628 | ||
617 | spinlock_unlock(&slab_cache_lock); |
629 | spinlock_unlock(&slab_cache_lock); |
618 | interrupts_restore(ipl); |
630 | interrupts_restore(ipl); |
619 | } |
631 | } |
620 | 632 | ||
621 | /** Create slab cache */ |
633 | /** Create slab cache */ |
622 | slab_cache_t * slab_cache_create(char *name, |
634 | slab_cache_t * slab_cache_create(char *name, |
623 | size_t size, |
635 | size_t size, |
624 | size_t align, |
636 | size_t align, |
625 | int (*constructor)(void *obj, int kmflag), |
637 | int (*constructor)(void *obj, int kmflag), |
626 | int (*destructor)(void *obj), |
638 | int (*destructor)(void *obj), |
627 | int flags) |
639 | int flags) |
628 | { |
640 | { |
629 | slab_cache_t *cache; |
641 | slab_cache_t *cache; |
630 | 642 | ||
631 | cache = slab_alloc(&slab_cache_cache, 0); |
643 | cache = slab_alloc(&slab_cache_cache, 0); |
632 | _slab_cache_create(cache, name, size, align, constructor, destructor, |
644 | _slab_cache_create(cache, name, size, align, constructor, destructor, |
633 | flags); |
645 | flags); |
634 | return cache; |
646 | return cache; |
635 | } |
647 | } |
636 | 648 | ||
637 | /** |
649 | /** |
638 | * Reclaim space occupied by objects that are already free |
650 | * Reclaim space occupied by objects that are already free |
639 | * |
651 | * |
640 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing |
652 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing |
641 | * @return Number of freed pages |
653 | * @return Number of freed pages |
642 | */ |
654 | */ |
643 | static count_t _slab_reclaim(slab_cache_t *cache, int flags) |
655 | static count_t _slab_reclaim(slab_cache_t *cache, int flags) |
644 | { |
656 | { |
645 | int i; |
657 | int i; |
646 | slab_magazine_t *mag; |
658 | slab_magazine_t *mag; |
647 | count_t frames = 0; |
659 | count_t frames = 0; |
648 | int magcount; |
660 | int magcount; |
649 | 661 | ||
650 | if (cache->flags & SLAB_CACHE_NOMAGAZINE) |
662 | if (cache->flags & SLAB_CACHE_NOMAGAZINE) |
651 | return 0; /* Nothing to do */ |
663 | return 0; /* Nothing to do */ |
652 | 664 | ||
653 | /* We count up to original magazine count to avoid |
665 | /* We count up to original magazine count to avoid |
654 | * endless loop |
666 | * endless loop |
655 | */ |
667 | */ |
656 | magcount = atomic_get(&cache->magazine_counter); |
668 | magcount = atomic_get(&cache->magazine_counter); |
657 | while (magcount-- && (mag=get_mag_from_cache(cache,0))) { |
669 | while (magcount-- && (mag=get_mag_from_cache(cache,0))) { |
658 | frames += magazine_destroy(cache,mag); |
670 | frames += magazine_destroy(cache,mag); |
659 | if (!(flags & SLAB_RECLAIM_ALL) && frames) |
671 | if (!(flags & SLAB_RECLAIM_ALL) && frames) |
660 | break; |
672 | break; |
661 | } |
673 | } |
662 | 674 | ||
663 | if (flags & SLAB_RECLAIM_ALL) { |
675 | if (flags & SLAB_RECLAIM_ALL) { |
664 | /* Free cpu-bound magazines */ |
676 | /* Free cpu-bound magazines */ |
665 | /* Destroy CPU magazines */ |
677 | /* Destroy CPU magazines */ |
666 | for (i=0; i<config.cpu_count; i++) { |
678 | for (i=0; i<config.cpu_count; i++) { |
667 | spinlock_lock(&cache->mag_cache[i].lock); |
679 | spinlock_lock(&cache->mag_cache[i].lock); |
668 | 680 | ||
669 | mag = cache->mag_cache[i].current; |
681 | mag = cache->mag_cache[i].current; |
670 | if (mag) |
682 | if (mag) |
671 | frames += magazine_destroy(cache, mag); |
683 | frames += magazine_destroy(cache, mag); |
672 | cache->mag_cache[i].current = NULL; |
684 | cache->mag_cache[i].current = NULL; |
673 | 685 | ||
674 | mag = cache->mag_cache[i].last; |
686 | mag = cache->mag_cache[i].last; |
675 | if (mag) |
687 | if (mag) |
676 | frames += magazine_destroy(cache, mag); |
688 | frames += magazine_destroy(cache, mag); |
677 | cache->mag_cache[i].last = NULL; |
689 | cache->mag_cache[i].last = NULL; |
678 | 690 | ||
679 | spinlock_unlock(&cache->mag_cache[i].lock); |
691 | spinlock_unlock(&cache->mag_cache[i].lock); |
680 | } |
692 | } |
681 | } |
693 | } |
682 | 694 | ||
683 | return frames; |
695 | return frames; |
684 | } |
696 | } |
685 | 697 | ||
686 | /** Check that there are no slabs and remove cache from system */ |
698 | /** Check that there are no slabs and remove cache from system */ |
687 | void slab_cache_destroy(slab_cache_t *cache) |
699 | void slab_cache_destroy(slab_cache_t *cache) |
688 | { |
700 | { |
689 | ipl_t ipl; |
701 | ipl_t ipl; |
690 | 702 | ||
691 | /* First remove cache from link, so that we don't need |
703 | /* First remove cache from link, so that we don't need |
692 | * to disable interrupts later |
704 | * to disable interrupts later |
693 | */ |
705 | */ |
694 | 706 | ||
695 | ipl = interrupts_disable(); |
707 | ipl = interrupts_disable(); |
696 | spinlock_lock(&slab_cache_lock); |
708 | spinlock_lock(&slab_cache_lock); |
697 | 709 | ||
698 | list_remove(&cache->link); |
710 | list_remove(&cache->link); |
699 | 711 | ||
700 | spinlock_unlock(&slab_cache_lock); |
712 | spinlock_unlock(&slab_cache_lock); |
701 | interrupts_restore(ipl); |
713 | interrupts_restore(ipl); |
702 | 714 | ||
703 | /* Do not lock anything, we assume the software is correct and |
715 | /* Do not lock anything, we assume the software is correct and |
704 | * does not touch the cache when it decides to destroy it */ |
716 | * does not touch the cache when it decides to destroy it */ |
705 | 717 | ||
706 | /* Destroy all magazines */ |
718 | /* Destroy all magazines */ |
707 | _slab_reclaim(cache, SLAB_RECLAIM_ALL); |
719 | _slab_reclaim(cache, SLAB_RECLAIM_ALL); |
708 | 720 | ||
709 | /* All slabs must be empty */ |
721 | /* All slabs must be empty */ |
710 | if (!list_empty(&cache->full_slabs) \ |
722 | if (!list_empty(&cache->full_slabs) \ |
711 | || !list_empty(&cache->partial_slabs)) |
723 | || !list_empty(&cache->partial_slabs)) |
712 | panic("Destroying cache that is not empty."); |
724 | panic("Destroying cache that is not empty."); |
713 | 725 | ||
714 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) |
726 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) |
715 | free(cache->mag_cache); |
727 | free(cache->mag_cache); |
716 | slab_free(&slab_cache_cache, cache); |
728 | slab_free(&slab_cache_cache, cache); |
717 | } |
729 | } |
718 | 730 | ||
719 | /** Allocate new object from cache - if no flags given, always returns |
731 | /** Allocate new object from cache - if no flags given, always returns |
720 | memory */ |
732 | memory */ |
721 | void * slab_alloc(slab_cache_t *cache, int flags) |
733 | void * slab_alloc(slab_cache_t *cache, int flags) |
722 | { |
734 | { |
723 | ipl_t ipl; |
735 | ipl_t ipl; |
724 | void *result = NULL; |
736 | void *result = NULL; |
725 | 737 | ||
726 | /* Disable interrupts to avoid deadlocks with interrupt handlers */ |
738 | /* Disable interrupts to avoid deadlocks with interrupt handlers */ |
727 | ipl = interrupts_disable(); |
739 | ipl = interrupts_disable(); |
728 | 740 | ||
729 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) { |
741 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) { |
730 | result = magazine_obj_get(cache); |
742 | result = magazine_obj_get(cache); |
731 | } |
743 | } |
732 | if (!result) |
744 | if (!result) |
733 | result = slab_obj_create(cache, flags); |
745 | result = slab_obj_create(cache, flags); |
734 | 746 | ||
735 | interrupts_restore(ipl); |
747 | interrupts_restore(ipl); |
736 | 748 | ||
737 | if (result) |
749 | if (result) |
738 | atomic_inc(&cache->allocated_objs); |
750 | atomic_inc(&cache->allocated_objs); |
739 | 751 | ||
740 | return result; |
752 | return result; |
741 | } |
753 | } |
742 | 754 | ||
743 | /** Return object to cache, use slab if known */ |
755 | /** Return object to cache, use slab if known */ |
744 | static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab) |
756 | static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab) |
745 | { |
757 | { |
746 | ipl_t ipl; |
758 | ipl_t ipl; |
747 | 759 | ||
748 | ipl = interrupts_disable(); |
760 | ipl = interrupts_disable(); |
749 | 761 | ||
750 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \ |
762 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \ |
751 | || magazine_obj_put(cache, obj)) { |
763 | || magazine_obj_put(cache, obj)) { |
752 | 764 | ||
753 | slab_obj_destroy(cache, obj, slab); |
765 | slab_obj_destroy(cache, obj, slab); |
754 | 766 | ||
755 | } |
767 | } |
756 | interrupts_restore(ipl); |
768 | interrupts_restore(ipl); |
757 | atomic_dec(&cache->allocated_objs); |
769 | atomic_dec(&cache->allocated_objs); |
758 | } |
770 | } |
759 | 771 | ||
760 | /** Return slab object to cache */ |
772 | /** Return slab object to cache */ |
761 | void slab_free(slab_cache_t *cache, void *obj) |
773 | void slab_free(slab_cache_t *cache, void *obj) |
762 | { |
774 | { |
763 | _slab_free(cache,obj,NULL); |
775 | _slab_free(cache, obj, NULL); |
764 | } |
776 | } |
765 | 777 | ||
766 | /* Go through all caches and reclaim what is possible */ |
778 | /* Go through all caches and reclaim what is possible */ |
767 | count_t slab_reclaim(int flags) |
779 | count_t slab_reclaim(int flags) |
768 | { |
780 | { |
769 | slab_cache_t *cache; |
781 | slab_cache_t *cache; |
770 | link_t *cur; |
782 | link_t *cur; |
771 | count_t frames = 0; |
783 | count_t frames = 0; |
772 | 784 | ||
773 | spinlock_lock(&slab_cache_lock); |
785 | spinlock_lock(&slab_cache_lock); |
774 | 786 | ||
775 | /* TODO: Add assert, that interrupts are disabled, otherwise |
787 | /* TODO: Add assert, that interrupts are disabled, otherwise |
776 | * memory allocation from interrupts can deadlock. |
788 | * memory allocation from interrupts can deadlock. |
777 | */ |
789 | */ |
778 | 790 | ||
779 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
791 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
780 | cache = list_get_instance(cur, slab_cache_t, link); |
792 | cache = list_get_instance(cur, slab_cache_t, link); |
781 | frames += _slab_reclaim(cache, flags); |
793 | frames += _slab_reclaim(cache, flags); |
782 | } |
794 | } |
783 | 795 | ||
784 | spinlock_unlock(&slab_cache_lock); |
796 | spinlock_unlock(&slab_cache_lock); |
785 | 797 | ||
786 | return frames; |
798 | return frames; |
787 | } |
799 | } |
788 | 800 | ||
789 | 801 | ||
790 | /* Print list of slabs */ |
802 | /* Print list of slabs */ |
791 | void slab_print_list(void) |
803 | void slab_print_list(void) |
792 | { |
804 | { |
793 | slab_cache_t *cache; |
805 | slab_cache_t *cache; |
794 | link_t *cur; |
806 | link_t *cur; |
795 | ipl_t ipl; |
807 | ipl_t ipl; |
796 | 808 | ||
797 | ipl = interrupts_disable(); |
809 | ipl = interrupts_disable(); |
798 | spinlock_lock(&slab_cache_lock); |
810 | spinlock_lock(&slab_cache_lock); |
799 | printf("slab name size pages obj/pg slabs cached allocated ctl\n"); |
811 | printf("slab name size pages obj/pg slabs cached allocated ctl\n"); |
800 | printf("---------------- -------- ------ ------ ------ ------ --------- ---\n"); |
812 | printf("---------------- -------- ------ ------ ------ ------ --------- ---\n"); |
801 | 813 | ||
802 | for (cur = slab_cache_list.next; cur != &slab_cache_list; cur = cur->next) { |
814 | for (cur = slab_cache_list.next; cur != &slab_cache_list; cur = cur->next) { |
803 | cache = list_get_instance(cur, slab_cache_t, link); |
815 | cache = list_get_instance(cur, slab_cache_t, link); |
804 | 816 | ||
805 | 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"); |
817 | 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"); |
806 | } |
818 | } |
807 | spinlock_unlock(&slab_cache_lock); |
819 | spinlock_unlock(&slab_cache_lock); |
808 | interrupts_restore(ipl); |
820 | interrupts_restore(ipl); |
809 | } |
821 | } |
810 | 822 | ||
811 | void slab_cache_init(void) |
823 | void slab_cache_init(void) |
812 | { |
824 | { |
813 | int i, size; |
825 | int i, size; |
814 | 826 | ||
815 | /* Initialize magazine cache */ |
827 | /* Initialize magazine cache */ |
816 | _slab_cache_create(&mag_cache, |
828 | _slab_cache_create(&mag_cache, |
817 | "slab_magazine", |
829 | "slab_magazine", |
818 | sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*), |
830 | sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*), |
819 | sizeof(uintptr_t), |
831 | sizeof(uintptr_t), |
820 | NULL, NULL, |
832 | NULL, NULL, |
821 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
833 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
822 | /* Initialize slab_cache cache */ |
834 | /* Initialize slab_cache cache */ |
823 | _slab_cache_create(&slab_cache_cache, |
835 | _slab_cache_create(&slab_cache_cache, |
824 | "slab_cache", |
836 | "slab_cache", |
825 | sizeof(slab_cache_cache), |
837 | sizeof(slab_cache_cache), |
826 | sizeof(uintptr_t), |
838 | sizeof(uintptr_t), |
827 | NULL, NULL, |
839 | NULL, NULL, |
828 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
840 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
829 | /* Initialize external slab cache */ |
841 | /* Initialize external slab cache */ |
830 | slab_extern_cache = slab_cache_create("slab_extern", |
842 | slab_extern_cache = slab_cache_create("slab_extern", |
831 | sizeof(slab_t), |
843 | sizeof(slab_t), |
832 | 0, NULL, NULL, |
844 | 0, NULL, NULL, |
833 | SLAB_CACHE_SLINSIDE | SLAB_CACHE_MAGDEFERRED); |
845 | SLAB_CACHE_SLINSIDE | SLAB_CACHE_MAGDEFERRED); |
834 | 846 | ||
835 | /* Initialize structures for malloc */ |
847 | /* Initialize structures for malloc */ |
836 | for (i=0, size=(1<<SLAB_MIN_MALLOC_W); |
848 | for (i=0, size=(1<<SLAB_MIN_MALLOC_W); |
837 | i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1); |
849 | i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1); |
838 | i++, size <<= 1) { |
850 | i++, size <<= 1) { |
839 | malloc_caches[i] = slab_cache_create(malloc_names[i], |
851 | malloc_caches[i] = slab_cache_create(malloc_names[i], |
840 | size, 0, |
852 | size, 0, |
841 | NULL,NULL, SLAB_CACHE_MAGDEFERRED); |
853 | NULL,NULL, SLAB_CACHE_MAGDEFERRED); |
842 | } |
854 | } |
843 | #ifdef CONFIG_DEBUG |
855 | #ifdef CONFIG_DEBUG |
844 | _slab_initialized = 1; |
856 | _slab_initialized = 1; |
845 | #endif |
857 | #endif |
846 | } |
858 | } |
847 | 859 | ||
848 | /** Enable cpu_cache |
860 | /** Enable cpu_cache |
849 | * |
861 | * |
850 | * Kernel calls this function, when it knows the real number of |
862 | * Kernel calls this function, when it knows the real number of |
851 | * processors. |
863 | * processors. |
852 | * Allocate slab for cpucache and enable it on all existing |
864 | * Allocate slab for cpucache and enable it on all existing |
853 | * slabs that are SLAB_CACHE_MAGDEFERRED |
865 | * slabs that are SLAB_CACHE_MAGDEFERRED |
854 | */ |
866 | */ |
855 | void slab_enable_cpucache(void) |
867 | void slab_enable_cpucache(void) |
856 | { |
868 | { |
857 | link_t *cur; |
869 | link_t *cur; |
858 | slab_cache_t *s; |
870 | slab_cache_t *s; |
859 | 871 | ||
860 | #ifdef CONFIG_DEBUG |
872 | #ifdef CONFIG_DEBUG |
861 | _slab_initialized = 2; |
873 | _slab_initialized = 2; |
862 | #endif |
874 | #endif |
863 | 875 | ||
864 | spinlock_lock(&slab_cache_lock); |
876 | spinlock_lock(&slab_cache_lock); |
865 | 877 | ||
866 | for (cur=slab_cache_list.next; cur != &slab_cache_list;cur=cur->next){ |
878 | for (cur=slab_cache_list.next; cur != &slab_cache_list;cur=cur->next){ |
867 | s = list_get_instance(cur, slab_cache_t, link); |
879 | s = list_get_instance(cur, slab_cache_t, link); |
868 | if ((s->flags & SLAB_CACHE_MAGDEFERRED) != SLAB_CACHE_MAGDEFERRED) |
880 | if ((s->flags & SLAB_CACHE_MAGDEFERRED) != SLAB_CACHE_MAGDEFERRED) |
869 | continue; |
881 | continue; |
870 | make_magcache(s); |
882 | make_magcache(s); |
871 | s->flags &= ~SLAB_CACHE_MAGDEFERRED; |
883 | s->flags &= ~SLAB_CACHE_MAGDEFERRED; |
872 | } |
884 | } |
873 | 885 | ||
874 | spinlock_unlock(&slab_cache_lock); |
886 | spinlock_unlock(&slab_cache_lock); |
875 | } |
887 | } |
876 | 888 | ||
877 | /**************************************/ |
889 | /**************************************/ |
878 | /* kalloc/kfree functions */ |
890 | /* kalloc/kfree functions */ |
879 | void * malloc(unsigned int size, int flags) |
891 | void * malloc(unsigned int size, int flags) |
880 | { |
892 | { |
881 | int idx; |
- | |
882 | - | ||
883 | ASSERT(_slab_initialized); |
893 | ASSERT(_slab_initialized); |
884 | ASSERT(size && size <= (1 << SLAB_MAX_MALLOC_W)); |
894 | ASSERT(size && size <= (1 << SLAB_MAX_MALLOC_W)); |
885 | 895 | ||
886 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
896 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
887 | size = (1 << SLAB_MIN_MALLOC_W); |
897 | size = (1 << SLAB_MIN_MALLOC_W); |
888 | 898 | ||
889 | idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1; |
899 | int idx = fnzb(size - 1) - SLAB_MIN_MALLOC_W + 1; |
890 | 900 | ||
891 | return slab_alloc(malloc_caches[idx], flags); |
901 | return slab_alloc(malloc_caches[idx], flags); |
892 | } |
902 | } |
893 | 903 | ||
894 | void free(void *obj) |
904 | void * realloc(void *ptr, unsigned int size, int flags) |
895 | { |
905 | { |
- | 906 | ASSERT(_slab_initialized); |
|
- | 907 | ASSERT(size <= (1 << SLAB_MAX_MALLOC_W)); |
|
- | 908 | ||
- | 909 | void *new_ptr; |
|
- | 910 | ||
- | 911 | if (size > 0) { |
|
- | 912 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
|
- | 913 | size = (1 << SLAB_MIN_MALLOC_W); |
|
- | 914 | int idx = fnzb(size - 1) - SLAB_MIN_MALLOC_W + 1; |
|
- | 915 | ||
- | 916 | new_ptr = slab_alloc(malloc_caches[idx], flags); |
|
- | 917 | } else |
|
896 | slab_t *slab; |
918 | new_ptr = NULL; |
- | 919 | ||
- | 920 | if ((new_ptr != NULL) && (ptr != NULL)) { |
|
- | 921 | slab_t *slab = obj2slab(ptr); |
|
- | 922 | memcpy(new_ptr, ptr, min(size, slab->cache->size)); |
|
- | 923 | } |
|
- | 924 | ||
- | 925 | if (ptr != NULL) |
|
- | 926 | free(ptr); |
|
- | 927 | ||
- | 928 | return new_ptr; |
|
- | 929 | } |
|
897 | 930 | ||
- | 931 | void free(void *ptr) |
|
- | 932 | { |
|
898 | if (!obj) |
933 | if (!ptr) |
899 | return; |
934 | return; |
900 | 935 | ||
901 | slab = obj2slab(obj); |
936 | slab_t *slab = obj2slab(ptr); |
902 | _slab_free(slab->cache, obj, slab); |
937 | _slab_free(slab->cache, ptr, slab); |
903 | } |
938 | } |
904 | 939 | ||
905 | /** @} |
940 | /** @} |
906 | */ |
941 | */ |
907 | 942 |