Rev 780 | Rev 782 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 780 | Rev 781 | ||
---|---|---|---|
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, |
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 |
89 | * we could then try_spinlock over all partial slabs and thus improve |
90 | * scalability even on slab level |
90 | * scalability even on slab level |
91 | */ |
91 | */ |
92 | 92 | ||
93 | 93 | ||
94 | #include <synch/spinlock.h> |
94 | #include <synch/spinlock.h> |
95 | #include <mm/slab.h> |
95 | #include <mm/slab.h> |
96 | #include <list.h> |
96 | #include <list.h> |
97 | #include <memstr.h> |
97 | #include <memstr.h> |
98 | #include <align.h> |
98 | #include <align.h> |
99 | #include <mm/heap.h> |
99 | #include <mm/heap.h> |
100 | #include <mm/frame.h> |
100 | #include <mm/frame.h> |
101 | #include <config.h> |
101 | #include <config.h> |
102 | #include <print.h> |
102 | #include <print.h> |
103 | #include <arch.h> |
103 | #include <arch.h> |
104 | #include <panic.h> |
104 | #include <panic.h> |
105 | #include <debug.h> |
105 | #include <debug.h> |
106 | #include <bitops.h> |
106 | #include <bitops.h> |
107 | 107 | ||
108 | SPINLOCK_INITIALIZE(slab_cache_lock); |
108 | SPINLOCK_INITIALIZE(slab_cache_lock); |
109 | static LIST_INITIALIZE(slab_cache_list); |
109 | static LIST_INITIALIZE(slab_cache_list); |
110 | 110 | ||
111 | /** Magazine cache */ |
111 | /** Magazine cache */ |
112 | static slab_cache_t mag_cache; |
112 | static slab_cache_t mag_cache; |
113 | /** Cache for cache descriptors */ |
113 | /** Cache for cache descriptors */ |
114 | static slab_cache_t slab_cache_cache; |
114 | static slab_cache_t slab_cache_cache; |
115 | 115 | ||
116 | /** Cache for external slab descriptors |
116 | /** Cache for external slab descriptors |
117 | * 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 |
118 | * - using SLAB for internal SLAB structures will not deadlock, |
118 | * - using SLAB for internal SLAB structures will not deadlock, |
119 | * as all slab structures are 'small' - control structures of |
119 | * as all slab structures are 'small' - control structures of |
120 | * their caches do not require further allocation |
120 | * their caches do not require further allocation |
121 | */ |
121 | */ |
122 | static slab_cache_t *slab_extern_cache; |
122 | static slab_cache_t *slab_extern_cache; |
123 | /** Caches for malloc */ |
123 | /** Caches for malloc */ |
124 | 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]; |
125 | char *malloc_names[] = { |
125 | char *malloc_names[] = { |
126 | "malloc-8","malloc-16","malloc-32","malloc-64","malloc-128", |
126 | "malloc-8","malloc-16","malloc-32","malloc-64","malloc-128", |
127 | "malloc-256","malloc-512","malloc-1K","malloc-2K", |
127 | "malloc-256","malloc-512","malloc-1K","malloc-2K", |
128 | "malloc-4K","malloc-8K","malloc-16K","malloc-32K", |
128 | "malloc-4K","malloc-8K","malloc-16K","malloc-32K", |
129 | "malloc-64K","malloc-128K" |
129 | "malloc-64K","malloc-128K" |
130 | }; |
130 | }; |
131 | 131 | ||
132 | /** Slab descriptor */ |
132 | /** Slab descriptor */ |
133 | typedef struct { |
133 | typedef struct { |
134 | slab_cache_t *cache; /**< Pointer to parent cache */ |
134 | slab_cache_t *cache; /**< Pointer to parent cache */ |
135 | link_t link; /* List of full/partial slabs */ |
135 | link_t link; /* List of full/partial slabs */ |
136 | void *start; /**< Start address of first available item */ |
136 | void *start; /**< Start address of first available item */ |
137 | count_t available; /**< Count of available items in this slab */ |
137 | count_t available; /**< Count of available items in this slab */ |
138 | index_t nextavail; /**< The index of next available item */ |
138 | index_t nextavail; /**< The index of next available item */ |
139 | }slab_t; |
139 | }slab_t; |
140 | 140 | ||
141 | /**************************************/ |
141 | /**************************************/ |
142 | /* SLAB allocation functions */ |
142 | /* SLAB allocation functions */ |
143 | 143 | ||
144 | /** |
144 | /** |
145 | * Allocate frames for slab space and initialize |
145 | * Allocate frames for slab space and initialize |
146 | * |
146 | * |
147 | */ |
147 | */ |
148 | 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) |
149 | { |
149 | { |
150 | void *data; |
150 | void *data; |
151 | slab_t *slab; |
151 | slab_t *slab; |
152 | size_t fsize; |
152 | size_t fsize; |
153 | int i; |
153 | int i; |
154 | zone_t *zone = NULL; |
154 | zone_t *zone = NULL; |
155 | int status; |
155 | int status; |
156 | frame_t *frame; |
156 | frame_t *frame; |
157 | 157 | ||
158 | data = (void *)frame_alloc(FRAME_KA | flags, cache->order, &status, &zone); |
158 | data = (void *)frame_alloc(FRAME_KA | flags, cache->order, &status, &zone); |
159 | if (status != FRAME_OK) { |
159 | if (status != FRAME_OK) { |
160 | return NULL; |
160 | return NULL; |
161 | } |
161 | } |
162 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { |
162 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { |
163 | slab = slab_alloc(slab_extern_cache, flags); |
163 | slab = slab_alloc(slab_extern_cache, flags); |
164 | if (!slab) { |
164 | if (!slab) { |
165 | frame_free((__address)data); |
165 | frame_free((__address)data); |
166 | return NULL; |
166 | return NULL; |
167 | } |
167 | } |
168 | } else { |
168 | } else { |
169 | fsize = (PAGE_SIZE << cache->order); |
169 | fsize = (PAGE_SIZE << cache->order); |
170 | slab = data + fsize - sizeof(*slab); |
170 | slab = data + fsize - sizeof(*slab); |
171 | } |
171 | } |
172 | 172 | ||
173 | /* Fill in slab structures */ |
173 | /* Fill in slab structures */ |
174 | /* TODO: some better way of accessing the frame */ |
174 | /* TODO: some better way of accessing the frame */ |
175 | for (i=0; i < (1 << cache->order); i++) { |
175 | for (i=0; i < (1 << cache->order); i++) { |
176 | frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE))); |
176 | frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE))); |
177 | frame->parent = slab; |
177 | frame->parent = slab; |
178 | } |
178 | } |
179 | 179 | ||
180 | slab->start = data; |
180 | slab->start = data; |
181 | slab->available = cache->objects; |
181 | slab->available = cache->objects; |
182 | slab->nextavail = 0; |
182 | slab->nextavail = 0; |
183 | slab->cache = cache; |
183 | slab->cache = cache; |
184 | 184 | ||
185 | for (i=0; i<cache->objects;i++) |
185 | for (i=0; i<cache->objects;i++) |
186 | *((int *) (slab->start + i*cache->size)) = i+1; |
186 | *((int *) (slab->start + i*cache->size)) = i+1; |
187 | 187 | ||
188 | atomic_inc(&cache->allocated_slabs); |
188 | atomic_inc(&cache->allocated_slabs); |
189 | return slab; |
189 | return slab; |
190 | } |
190 | } |
191 | 191 | ||
192 | /** |
192 | /** |
193 | * Deallocate space associated with SLAB |
193 | * Deallocate space associated with SLAB |
194 | * |
194 | * |
195 | * @return number of freed frames |
195 | * @return number of freed frames |
196 | */ |
196 | */ |
197 | 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) |
198 | { |
198 | { |
199 | frame_free((__address)slab->start); |
199 | frame_free((__address)slab->start); |
200 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) |
200 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) |
201 | slab_free(slab_extern_cache, slab); |
201 | slab_free(slab_extern_cache, slab); |
202 | 202 | ||
203 | atomic_dec(&cache->allocated_slabs); |
203 | atomic_dec(&cache->allocated_slabs); |
204 | 204 | ||
205 | return 1 << cache->order; |
205 | return 1 << cache->order; |
206 | } |
206 | } |
207 | 207 | ||
208 | /** Map object to slab structure */ |
208 | /** Map object to slab structure */ |
209 | static slab_t * obj2slab(void *obj) |
209 | static slab_t * obj2slab(void *obj) |
210 | { |
210 | { |
211 | frame_t *frame; |
211 | frame_t *frame; |
212 | 212 | ||
213 | frame = frame_addr2frame((__address)obj); |
213 | frame = frame_addr2frame((__address)obj); |
214 | return (slab_t *)frame->parent; |
214 | return (slab_t *)frame->parent; |
215 | } |
215 | } |
216 | 216 | ||
217 | /**************************************/ |
217 | /**************************************/ |
218 | /* SLAB functions */ |
218 | /* SLAB functions */ |
219 | 219 | ||
220 | 220 | ||
221 | /** |
221 | /** |
222 | * Return object to slab and call a destructor |
222 | * Return object to slab and call a destructor |
223 | * |
223 | * |
224 | * @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 |
225 | * |
225 | * |
226 | * @return Number of freed pages |
226 | * @return Number of freed pages |
227 | */ |
227 | */ |
228 | 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, |
229 | slab_t *slab) |
229 | slab_t *slab) |
230 | { |
230 | { |
231 | count_t frames = 0; |
231 | count_t frames = 0; |
232 | 232 | ||
233 | if (!slab) |
233 | if (!slab) |
234 | slab = obj2slab(obj); |
234 | slab = obj2slab(obj); |
235 | 235 | ||
236 | ASSERT(slab->cache == cache); |
236 | ASSERT(slab->cache == cache); |
237 | ASSERT(slab->available < cache->objects); |
237 | ASSERT(slab->available < cache->objects); |
238 | 238 | ||
239 | spinlock_lock(&cache->slablock); |
239 | spinlock_lock(&cache->slablock); |
240 | 240 | ||
241 | *((int *)obj) = slab->nextavail; |
241 | *((int *)obj) = slab->nextavail; |
242 | slab->nextavail = (obj - slab->start)/cache->size; |
242 | slab->nextavail = (obj - slab->start)/cache->size; |
243 | slab->available++; |
243 | slab->available++; |
244 | 244 | ||
245 | /* Move it to correct list */ |
245 | /* Move it to correct list */ |
246 | if (slab->available == cache->objects) { |
246 | if (slab->available == cache->objects) { |
247 | /* Free associated memory */ |
247 | /* Free associated memory */ |
248 | list_remove(&slab->link); |
248 | list_remove(&slab->link); |
249 | /* This should not produce deadlock, as |
249 | /* This should not produce deadlock, as |
250 | * magazine is always allocated with NO reclaim, |
250 | * magazine is always allocated with NO reclaim, |
251 | * keep all locks */ |
251 | * keep all locks */ |
252 | frames = slab_space_free(cache, slab); |
252 | frames = slab_space_free(cache, slab); |
253 | } else if (slab->available == 1) { |
253 | } else if (slab->available == 1) { |
254 | /* It was in full, move to partial */ |
254 | /* It was in full, move to partial */ |
255 | list_remove(&slab->link); |
255 | list_remove(&slab->link); |
256 | list_prepend(&slab->link, &cache->partial_slabs); |
256 | list_prepend(&slab->link, &cache->partial_slabs); |
257 | } |
257 | } |
258 | 258 | ||
259 | spinlock_unlock(&cache->slablock); |
259 | spinlock_unlock(&cache->slablock); |
260 | 260 | ||
261 | return frames; |
261 | return frames; |
262 | } |
262 | } |
263 | 263 | ||
264 | /** |
264 | /** |
265 | * Take new object from slab or create new if needed |
265 | * Take new object from slab or create new if needed |
266 | * |
266 | * |
267 | * @return Object address or null |
267 | * @return Object address or null |
268 | */ |
268 | */ |
269 | static void * slab_obj_create(slab_cache_t *cache, int flags) |
269 | static void * slab_obj_create(slab_cache_t *cache, int flags) |
270 | { |
270 | { |
271 | slab_t *slab; |
271 | slab_t *slab; |
272 | void *obj; |
272 | void *obj; |
273 | 273 | ||
274 | spinlock_lock(&cache->slablock); |
274 | spinlock_lock(&cache->slablock); |
275 | 275 | ||
276 | if (list_empty(&cache->partial_slabs)) { |
276 | if (list_empty(&cache->partial_slabs)) { |
277 | /* Allow recursion and reclaiming |
277 | /* Allow recursion and reclaiming |
278 | * - this should work, as the SLAB control structures |
278 | * - this should work, as the SLAB control structures |
279 | * are small and do not need to allocte with anything |
279 | * are small and do not need to allocte with anything |
280 | * other ten frame_alloc when they are allocating, |
280 | * other ten frame_alloc when they are allocating, |
281 | * 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 |
282 | */ |
282 | */ |
283 | spinlock_unlock(&cache->slablock); |
283 | spinlock_unlock(&cache->slablock); |
284 | slab = slab_space_alloc(cache, flags); |
284 | slab = slab_space_alloc(cache, flags); |
285 | if (!slab) |
285 | if (!slab) |
286 | return NULL; |
286 | return NULL; |
287 | spinlock_lock(&cache->slablock); |
287 | spinlock_lock(&cache->slablock); |
288 | } else { |
288 | } else { |
289 | slab = list_get_instance(cache->partial_slabs.next, |
289 | slab = list_get_instance(cache->partial_slabs.next, |
290 | slab_t, |
290 | slab_t, |
291 | link); |
291 | link); |
292 | list_remove(&slab->link); |
292 | list_remove(&slab->link); |
293 | } |
293 | } |
294 | obj = slab->start + slab->nextavail * cache->size; |
294 | obj = slab->start + slab->nextavail * cache->size; |
295 | slab->nextavail = *((int *)obj); |
295 | slab->nextavail = *((int *)obj); |
296 | slab->available--; |
296 | slab->available--; |
297 | if (! slab->available) |
297 | if (! slab->available) |
298 | list_prepend(&slab->link, &cache->full_slabs); |
298 | list_prepend(&slab->link, &cache->full_slabs); |
299 | else |
299 | else |
300 | list_prepend(&slab->link, &cache->partial_slabs); |
300 | list_prepend(&slab->link, &cache->partial_slabs); |
301 | 301 | ||
302 | spinlock_unlock(&cache->slablock); |
302 | spinlock_unlock(&cache->slablock); |
303 | return obj; |
303 | return obj; |
304 | } |
304 | } |
305 | 305 | ||
306 | /**************************************/ |
306 | /**************************************/ |
307 | /* CPU-Cache slab functions */ |
307 | /* CPU-Cache slab functions */ |
308 | 308 | ||
309 | /** |
309 | /** |
- | 310 | * Finds a full magazine in cache, takes it from list |
|
- | 311 | * and returns it |
|
- | 312 | * |
|
- | 313 | * @param first If true, return first, else last mag |
|
- | 314 | */ |
|
- | 315 | static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache, |
|
- | 316 | int first) |
|
- | 317 | { |
|
- | 318 | slab_magazine_t *mag = NULL; |
|
- | 319 | link_t *cur; |
|
- | 320 | ||
- | 321 | spinlock_lock(&cache->maglock); |
|
- | 322 | if (!list_empty(&cache->magazines)) { |
|
- | 323 | if (first) |
|
- | 324 | cur = cache->magazines.next; |
|
- | 325 | else |
|
- | 326 | cur = cache->magazines.prev; |
|
- | 327 | mag = list_get_instance(cur, slab_magazine_t, link); |
|
- | 328 | list_remove(&mag->link); |
|
- | 329 | atomic_dec(&cache->magazine_counter); |
|
- | 330 | } |
|
- | 331 | spinlock_unlock(&cache->maglock); |
|
- | 332 | return mag; |
|
- | 333 | } |
|
- | 334 | ||
- | 335 | /** Prepend magazine to magazine list in cache */ |
|
- | 336 | static void put_mag_to_cache(slab_cache_t *cache, slab_magazine_t *mag) |
|
- | 337 | { |
|
- | 338 | spinlock_lock(&cache->maglock); |
|
- | 339 | ||
- | 340 | list_prepend(&mag->link, &cache->magazines); |
|
- | 341 | atomic_inc(&cache->magazine_counter); |
|
- | 342 | ||
- | 343 | spinlock_unlock(&cache->maglock); |
|
- | 344 | } |
|
- | 345 | ||
- | 346 | /** |
|
310 | * Free all objects in magazine and free memory associated with magazine |
347 | * Free all objects in magazine and free memory associated with magazine |
311 | * |
348 | * |
312 | * @return Number of freed pages |
349 | * @return Number of freed pages |
313 | */ |
350 | */ |
314 | static count_t magazine_destroy(slab_cache_t *cache, |
351 | static count_t magazine_destroy(slab_cache_t *cache, |
315 | slab_magazine_t *mag) |
352 | slab_magazine_t *mag) |
316 | { |
353 | { |
317 | int i; |
354 | int i; |
318 | count_t frames = 0; |
355 | count_t frames = 0; |
319 | 356 | ||
320 | for (i=0;i < mag->busy; i++) { |
357 | for (i=0;i < mag->busy; i++) { |
321 | frames += slab_obj_destroy(cache, mag->objs[i], NULL); |
358 | frames += slab_obj_destroy(cache, mag->objs[i], NULL); |
322 | atomic_dec(&cache->cached_objs); |
359 | atomic_dec(&cache->cached_objs); |
323 | } |
360 | } |
324 | 361 | ||
325 | slab_free(&mag_cache, mag); |
362 | slab_free(&mag_cache, mag); |
326 | 363 | ||
327 | return frames; |
364 | return frames; |
328 | } |
365 | } |
329 | 366 | ||
330 | /** |
367 | /** |
331 | * Find full magazine, set it as current and return it |
368 | * Find full magazine, set it as current and return it |
332 | * |
369 | * |
333 | * Assume cpu_magazine lock is held |
370 | * Assume cpu_magazine lock is held |
334 | */ |
371 | */ |
335 | static slab_magazine_t * get_full_current_mag(slab_cache_t *cache) |
372 | static slab_magazine_t * get_full_current_mag(slab_cache_t *cache) |
336 | { |
373 | { |
337 | slab_magazine_t *cmag, *lastmag, *newmag; |
374 | slab_magazine_t *cmag, *lastmag, *newmag; |
338 | 375 | ||
339 | cmag = cache->mag_cache[CPU->id].current; |
376 | cmag = cache->mag_cache[CPU->id].current; |
340 | lastmag = cache->mag_cache[CPU->id].last; |
377 | lastmag = cache->mag_cache[CPU->id].last; |
341 | if (cmag) { /* First try local CPU magazines */ |
378 | if (cmag) { /* First try local CPU magazines */ |
342 | if (cmag->busy) |
379 | if (cmag->busy) |
343 | return cmag; |
380 | return cmag; |
344 | 381 | ||
345 | if (lastmag && lastmag->busy) { |
382 | if (lastmag && lastmag->busy) { |
346 | cache->mag_cache[CPU->id].current = lastmag; |
383 | cache->mag_cache[CPU->id].current = lastmag; |
347 | cache->mag_cache[CPU->id].last = cmag; |
384 | cache->mag_cache[CPU->id].last = cmag; |
348 | return lastmag; |
385 | return lastmag; |
349 | } |
386 | } |
350 | } |
387 | } |
351 | /* Local magazines are empty, import one from magazine list */ |
388 | /* Local magazines are empty, import one from magazine list */ |
352 | spinlock_lock(&cache->maglock); |
389 | newmag = get_mag_from_cache(cache, 1); |
353 | if (list_empty(&cache->magazines)) { |
390 | if (!newmag) |
354 | spinlock_unlock(&cache->maglock); |
- | |
355 | return NULL; |
391 | return NULL; |
356 | } |
- | |
357 | newmag = list_get_instance(cache->magazines.next, |
- | |
358 | slab_magazine_t, |
- | |
359 | link); |
- | |
360 | list_remove(&newmag->link); |
- | |
361 | spinlock_unlock(&cache->maglock); |
- | |
362 | 392 | ||
363 | if (lastmag) |
393 | if (lastmag) |
364 | slab_free(&mag_cache, lastmag); |
394 | magazine_destroy(cache, lastmag); |
- | 395 | ||
365 | cache->mag_cache[CPU->id].last = cmag; |
396 | cache->mag_cache[CPU->id].last = cmag; |
366 | cache->mag_cache[CPU->id].current = newmag; |
397 | cache->mag_cache[CPU->id].current = newmag; |
367 | return newmag; |
398 | return newmag; |
368 | } |
399 | } |
369 | 400 | ||
370 | /** |
401 | /** |
371 | * Try to find object in CPU-cache magazines |
402 | * Try to find object in CPU-cache magazines |
372 | * |
403 | * |
373 | * @return Pointer to object or NULL if not available |
404 | * @return Pointer to object or NULL if not available |
374 | */ |
405 | */ |
375 | static void * magazine_obj_get(slab_cache_t *cache) |
406 | static void * magazine_obj_get(slab_cache_t *cache) |
376 | { |
407 | { |
377 | slab_magazine_t *mag; |
408 | slab_magazine_t *mag; |
378 | void *obj; |
409 | void *obj; |
379 | 410 | ||
380 | if (!CPU) |
411 | if (!CPU) |
381 | return NULL; |
412 | return NULL; |
382 | 413 | ||
383 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
414 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
384 | 415 | ||
385 | mag = get_full_current_mag(cache); |
416 | mag = get_full_current_mag(cache); |
386 | if (!mag) { |
417 | if (!mag) { |
387 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
418 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
388 | return NULL; |
419 | return NULL; |
389 | } |
420 | } |
390 | obj = mag->objs[--mag->busy]; |
421 | obj = mag->objs[--mag->busy]; |
391 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
422 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
392 | atomic_dec(&cache->cached_objs); |
423 | atomic_dec(&cache->cached_objs); |
393 | 424 | ||
394 | return obj; |
425 | return obj; |
395 | } |
426 | } |
396 | 427 | ||
397 | /** |
428 | /** |
398 | * Assure that the current magazine is empty, return pointer to it, or NULL if |
429 | * Assure that the current magazine is empty, return pointer to it, or NULL if |
399 | * no empty magazine is available and cannot be allocated |
430 | * no empty magazine is available and cannot be allocated |
400 | * |
431 | * |
401 | * Assume mag_cache[CPU->id].lock is held |
432 | * Assume mag_cache[CPU->id].lock is held |
402 | * |
433 | * |
403 | * We have 2 magazines bound to processor. |
434 | * We have 2 magazines bound to processor. |
404 | * First try the current. |
435 | * First try the current. |
405 | * If full, try the last. |
436 | * If full, try the last. |
406 | * If full, put to magazines list. |
437 | * If full, put to magazines list. |
407 | * allocate new, exchange last & current |
438 | * allocate new, exchange last & current |
408 | * |
439 | * |
409 | */ |
440 | */ |
410 | static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache) |
441 | static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache) |
411 | { |
442 | { |
412 | slab_magazine_t *cmag,*lastmag,*newmag; |
443 | slab_magazine_t *cmag,*lastmag,*newmag; |
413 | 444 | ||
414 | cmag = cache->mag_cache[CPU->id].current; |
445 | cmag = cache->mag_cache[CPU->id].current; |
415 | lastmag = cache->mag_cache[CPU->id].last; |
446 | lastmag = cache->mag_cache[CPU->id].last; |
416 | 447 | ||
417 | if (cmag) { |
448 | if (cmag) { |
418 | if (cmag->busy < cmag->size) |
449 | if (cmag->busy < cmag->size) |
419 | return cmag; |
450 | return cmag; |
420 | if (lastmag && lastmag->busy < lastmag->size) { |
451 | if (lastmag && lastmag->busy < lastmag->size) { |
421 | cache->mag_cache[CPU->id].last = cmag; |
452 | cache->mag_cache[CPU->id].last = cmag; |
422 | cache->mag_cache[CPU->id].current = lastmag; |
453 | cache->mag_cache[CPU->id].current = lastmag; |
423 | return lastmag; |
454 | return lastmag; |
424 | } |
455 | } |
425 | } |
456 | } |
426 | /* current | last are full | nonexistent, allocate new */ |
457 | /* current | last are full | nonexistent, allocate new */ |
427 | /* We do not want to sleep just because of caching */ |
458 | /* We do not want to sleep just because of caching */ |
428 | /* Especially we do not want reclaiming to start, as |
459 | /* Especially we do not want reclaiming to start, as |
429 | * this would deadlock */ |
460 | * this would deadlock */ |
430 | newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM); |
461 | newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM); |
431 | if (!newmag) |
462 | if (!newmag) |
432 | return NULL; |
463 | return NULL; |
433 | newmag->size = SLAB_MAG_SIZE; |
464 | newmag->size = SLAB_MAG_SIZE; |
434 | newmag->busy = 0; |
465 | newmag->busy = 0; |
435 | 466 | ||
436 | /* Flush last to magazine list */ |
467 | /* Flush last to magazine list */ |
437 | if (lastmag) { |
468 | if (lastmag) |
438 | spinlock_lock(&cache->maglock); |
469 | put_mag_to_cache(cache, lastmag); |
439 | list_prepend(&lastmag->link, &cache->magazines); |
- | |
440 | spinlock_unlock(&cache->maglock); |
- | |
441 | } |
470 | |
442 | /* Move current as last, save new as current */ |
471 | /* Move current as last, save new as current */ |
443 | cache->mag_cache[CPU->id].last = cmag; |
472 | cache->mag_cache[CPU->id].last = cmag; |
444 | cache->mag_cache[CPU->id].current = newmag; |
473 | cache->mag_cache[CPU->id].current = newmag; |
445 | 474 | ||
446 | return newmag; |
475 | return newmag; |
447 | } |
476 | } |
448 | 477 | ||
449 | /** |
478 | /** |
450 | * Put object into CPU-cache magazine |
479 | * Put object into CPU-cache magazine |
451 | * |
480 | * |
452 | * @return 0 - success, -1 - could not get memory |
481 | * @return 0 - success, -1 - could not get memory |
453 | */ |
482 | */ |
454 | static int magazine_obj_put(slab_cache_t *cache, void *obj) |
483 | static int magazine_obj_put(slab_cache_t *cache, void *obj) |
455 | { |
484 | { |
456 | slab_magazine_t *mag; |
485 | slab_magazine_t *mag; |
457 | 486 | ||
458 | if (!CPU) |
487 | if (!CPU) |
459 | return -1; |
488 | return -1; |
460 | 489 | ||
461 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
490 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
462 | 491 | ||
463 | mag = make_empty_current_mag(cache); |
492 | mag = make_empty_current_mag(cache); |
464 | if (!mag) { |
493 | if (!mag) { |
465 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
494 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
466 | return -1; |
495 | return -1; |
467 | } |
496 | } |
468 | 497 | ||
469 | mag->objs[mag->busy++] = obj; |
498 | mag->objs[mag->busy++] = obj; |
470 | 499 | ||
471 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
500 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
472 | atomic_inc(&cache->cached_objs); |
501 | atomic_inc(&cache->cached_objs); |
473 | return 0; |
502 | return 0; |
474 | } |
503 | } |
475 | 504 | ||
476 | 505 | ||
477 | /**************************************/ |
506 | /**************************************/ |
478 | /* SLAB CACHE functions */ |
507 | /* SLAB CACHE functions */ |
479 | 508 | ||
480 | /** Return number of objects that fit in certain cache size */ |
509 | /** Return number of objects that fit in certain cache size */ |
481 | static int comp_objects(slab_cache_t *cache) |
510 | static int comp_objects(slab_cache_t *cache) |
482 | { |
511 | { |
483 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
512 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
484 | return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size; |
513 | return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size; |
485 | else |
514 | else |
486 | return (PAGE_SIZE << cache->order) / cache->size; |
515 | return (PAGE_SIZE << cache->order) / cache->size; |
487 | } |
516 | } |
488 | 517 | ||
489 | /** Return wasted space in slab */ |
518 | /** Return wasted space in slab */ |
490 | static int badness(slab_cache_t *cache) |
519 | static int badness(slab_cache_t *cache) |
491 | { |
520 | { |
492 | int objects; |
521 | int objects; |
493 | int ssize; |
522 | int ssize; |
494 | 523 | ||
495 | objects = comp_objects(cache); |
524 | objects = comp_objects(cache); |
496 | ssize = PAGE_SIZE << cache->order; |
525 | ssize = PAGE_SIZE << cache->order; |
497 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
526 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
498 | ssize -= sizeof(slab_t); |
527 | ssize -= sizeof(slab_t); |
499 | return ssize - objects*cache->size; |
528 | return ssize - objects*cache->size; |
500 | } |
529 | } |
501 | 530 | ||
502 | /** Initialize allocated memory as a slab cache */ |
531 | /** Initialize allocated memory as a slab cache */ |
503 | static void |
532 | static void |
504 | _slab_cache_create(slab_cache_t *cache, |
533 | _slab_cache_create(slab_cache_t *cache, |
505 | char *name, |
534 | char *name, |
506 | size_t size, |
535 | size_t size, |
507 | size_t align, |
536 | size_t align, |
508 | int (*constructor)(void *obj, int kmflag), |
537 | int (*constructor)(void *obj, int kmflag), |
509 | void (*destructor)(void *obj), |
538 | void (*destructor)(void *obj), |
510 | int flags) |
539 | int flags) |
511 | { |
540 | { |
512 | int i; |
541 | int i; |
513 | int pages; |
542 | int pages; |
514 | 543 | ||
515 | memsetb((__address)cache, sizeof(*cache), 0); |
544 | memsetb((__address)cache, sizeof(*cache), 0); |
516 | cache->name = name; |
545 | cache->name = name; |
517 | 546 | ||
518 | if (align < sizeof(__native)) |
547 | if (align < sizeof(__native)) |
519 | align = sizeof(__native); |
548 | align = sizeof(__native); |
520 | size = ALIGN_UP(size, align); |
549 | size = ALIGN_UP(size, align); |
521 | 550 | ||
522 | cache->size = size; |
551 | cache->size = size; |
523 | 552 | ||
524 | cache->constructor = constructor; |
553 | cache->constructor = constructor; |
525 | cache->destructor = destructor; |
554 | cache->destructor = destructor; |
526 | cache->flags = flags; |
555 | cache->flags = flags; |
527 | 556 | ||
528 | list_initialize(&cache->full_slabs); |
557 | list_initialize(&cache->full_slabs); |
529 | list_initialize(&cache->partial_slabs); |
558 | list_initialize(&cache->partial_slabs); |
530 | list_initialize(&cache->magazines); |
559 | list_initialize(&cache->magazines); |
531 | spinlock_initialize(&cache->slablock, "slab_lock"); |
560 | spinlock_initialize(&cache->slablock, "slab_lock"); |
532 | spinlock_initialize(&cache->maglock, "slab_maglock"); |
561 | spinlock_initialize(&cache->maglock, "slab_maglock"); |
533 | if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) { |
562 | if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) { |
534 | for (i=0; i < config.cpu_count; i++) { |
563 | for (i=0; i < config.cpu_count; i++) { |
535 | memsetb((__address)&cache->mag_cache[i], |
564 | memsetb((__address)&cache->mag_cache[i], |
536 | sizeof(cache->mag_cache[i]), 0); |
565 | sizeof(cache->mag_cache[i]), 0); |
537 | spinlock_initialize(&cache->mag_cache[i].lock, |
566 | spinlock_initialize(&cache->mag_cache[i].lock, |
538 | "slab_maglock_cpu"); |
567 | "slab_maglock_cpu"); |
539 | } |
568 | } |
540 | } |
569 | } |
541 | 570 | ||
542 | /* Compute slab sizes, object counts in slabs etc. */ |
571 | /* Compute slab sizes, object counts in slabs etc. */ |
543 | if (cache->size < SLAB_INSIDE_SIZE) |
572 | if (cache->size < SLAB_INSIDE_SIZE) |
544 | cache->flags |= SLAB_CACHE_SLINSIDE; |
573 | cache->flags |= SLAB_CACHE_SLINSIDE; |
545 | 574 | ||
546 | /* Minimum slab order */ |
575 | /* Minimum slab order */ |
547 | pages = ((cache->size-1) >> PAGE_WIDTH) + 1; |
576 | pages = ((cache->size-1) >> PAGE_WIDTH) + 1; |
548 | cache->order = fnzb(pages); |
577 | cache->order = fnzb(pages); |
549 | 578 | ||
550 | while (badness(cache) > SLAB_MAX_BADNESS(cache)) { |
579 | while (badness(cache) > SLAB_MAX_BADNESS(cache)) { |
551 | cache->order += 1; |
580 | cache->order += 1; |
552 | } |
581 | } |
553 | cache->objects = comp_objects(cache); |
582 | cache->objects = comp_objects(cache); |
554 | /* If info fits in, put it inside */ |
583 | /* If info fits in, put it inside */ |
555 | if (badness(cache) > sizeof(slab_t)) |
584 | if (badness(cache) > sizeof(slab_t)) |
556 | cache->flags |= SLAB_CACHE_SLINSIDE; |
585 | cache->flags |= SLAB_CACHE_SLINSIDE; |
557 | 586 | ||
558 | spinlock_lock(&slab_cache_lock); |
587 | spinlock_lock(&slab_cache_lock); |
559 | 588 | ||
560 | list_append(&cache->link, &slab_cache_list); |
589 | list_append(&cache->link, &slab_cache_list); |
561 | 590 | ||
562 | spinlock_unlock(&slab_cache_lock); |
591 | spinlock_unlock(&slab_cache_lock); |
563 | } |
592 | } |
564 | 593 | ||
565 | /** Create slab cache */ |
594 | /** Create slab cache */ |
566 | slab_cache_t * slab_cache_create(char *name, |
595 | slab_cache_t * slab_cache_create(char *name, |
567 | size_t size, |
596 | size_t size, |
568 | size_t align, |
597 | size_t align, |
569 | int (*constructor)(void *obj, int kmflag), |
598 | int (*constructor)(void *obj, int kmflag), |
570 | void (*destructor)(void *obj), |
599 | void (*destructor)(void *obj), |
571 | int flags) |
600 | int flags) |
572 | { |
601 | { |
573 | slab_cache_t *cache; |
602 | slab_cache_t *cache; |
574 | 603 | ||
575 | cache = slab_alloc(&slab_cache_cache, 0); |
604 | cache = slab_alloc(&slab_cache_cache, 0); |
576 | _slab_cache_create(cache, name, size, align, constructor, destructor, |
605 | _slab_cache_create(cache, name, size, align, constructor, destructor, |
577 | flags); |
606 | flags); |
578 | return cache; |
607 | return cache; |
579 | } |
608 | } |
580 | 609 | ||
581 | /** |
610 | /** |
582 | * Reclaim space occupied by objects that are already free |
611 | * Reclaim space occupied by objects that are already free |
583 | * |
612 | * |
584 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing |
613 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing |
585 | * @return Number of freed pages |
614 | * @return Number of freed pages |
586 | */ |
615 | */ |
587 | static count_t _slab_reclaim(slab_cache_t *cache, int flags) |
616 | static count_t _slab_reclaim(slab_cache_t *cache, int flags) |
588 | { |
617 | { |
589 | int i; |
618 | int i; |
590 | slab_magazine_t *mag; |
619 | slab_magazine_t *mag; |
591 | link_t *cur; |
- | |
592 | count_t frames = 0; |
620 | count_t frames = 0; |
- | 621 | int magcount; |
|
593 | 622 | ||
594 | if (cache->flags & SLAB_CACHE_NOMAGAZINE) |
623 | if (cache->flags & SLAB_CACHE_NOMAGAZINE) |
595 | return 0; /* Nothing to do */ |
624 | return 0; /* Nothing to do */ |
596 | 625 | ||
597 | /* First lock all cpu caches, then the complete cache lock */ |
626 | /* We count up to original magazine count to avoid |
598 | if (flags & SLAB_RECLAIM_ALL) { |
627 | * endless loop |
- | 628 | */ |
|
599 | for (i=0; i < config.cpu_count; i++) |
629 | magcount = atomic_get(&cache->magazine_counter); |
- | 630 | while (magcount-- && (mag=get_mag_from_cache(cache,0))) { |
|
600 | spinlock_lock(&cache->mag_cache[i].lock); |
631 | frames += magazine_destroy(cache,mag); |
- | 632 | if (!(flags & SLAB_RECLAIM_ALL) && frames) |
|
- | 633 | break; |
|
601 | } |
634 | } |
602 | spinlock_lock(&cache->maglock); |
- | |
603 | 635 | ||
604 | if (flags & SLAB_RECLAIM_ALL) { |
636 | if (flags & SLAB_RECLAIM_ALL) { |
605 | /* Aggressive memfree */ |
637 | /* Free cpu-bound magazines */ |
606 | /* Destroy CPU magazines */ |
638 | /* Destroy CPU magazines */ |
607 | for (i=0; i<config.cpu_count; i++) { |
639 | for (i=0; i<config.cpu_count; i++) { |
- | 640 | spinlock_lock(&cache->mag_cache[i].lock); |
|
- | 641 | ||
608 | mag = cache->mag_cache[i].current; |
642 | mag = cache->mag_cache[i].current; |
609 | if (mag) |
643 | if (mag) |
610 | frames += magazine_destroy(cache, mag); |
644 | frames += magazine_destroy(cache, mag); |
611 | cache->mag_cache[i].current = NULL; |
645 | cache->mag_cache[i].current = NULL; |
612 | 646 | ||
613 | mag = cache->mag_cache[i].last; |
647 | mag = cache->mag_cache[i].last; |
614 | if (mag) |
648 | if (mag) |
615 | frames += magazine_destroy(cache, mag); |
649 | frames += magazine_destroy(cache, mag); |
616 | cache->mag_cache[i].last = NULL; |
650 | cache->mag_cache[i].last = NULL; |
617 | } |
- | |
618 | } |
651 | |
619 | /* We can release the cache locks now */ |
- | |
620 | if (flags & SLAB_RECLAIM_ALL) { |
- | |
621 | for (i=0; i < config.cpu_count; i++) |
- | |
622 | spinlock_unlock(&cache->mag_cache[i].lock); |
652 | spinlock_unlock(&cache->mag_cache[i].lock); |
- | 653 | } |
|
623 | } |
654 | } |
624 | /* Destroy full magazines */ |
- | |
625 | cur=cache->magazines.prev; |
- | |
626 | 655 | ||
627 | while (cur != &cache->magazines) { |
- | |
628 | mag = list_get_instance(cur, slab_magazine_t, link); |
- | |
629 | - | ||
630 | cur = cur->prev; |
- | |
631 | list_remove(&mag->link); |
- | |
632 | frames += magazine_destroy(cache,mag); |
- | |
633 | /* If we do not do full reclaim, break |
- | |
634 | * as soon as something is freed */ |
- | |
635 | if (!(flags & SLAB_RECLAIM_ALL) && frames) |
- | |
636 | break; |
- | |
637 | } |
- | |
638 | - | ||
639 | spinlock_unlock(&cache->maglock); |
- | |
640 | - | ||
641 | return frames; |
656 | return frames; |
642 | } |
657 | } |
643 | 658 | ||
644 | /** Check that there are no slabs and remove cache from system */ |
659 | /** Check that there are no slabs and remove cache from system */ |
645 | void slab_cache_destroy(slab_cache_t *cache) |
660 | void slab_cache_destroy(slab_cache_t *cache) |
646 | { |
661 | { |
- | 662 | ipl_t ipl; |
|
- | 663 | ||
- | 664 | /* First remove cache from link, so that we don't need |
|
- | 665 | * to disable interrupts later |
|
- | 666 | */ |
|
- | 667 | ||
- | 668 | ipl = interrupts_disable(); |
|
- | 669 | spinlock_lock(&slab_cache_lock); |
|
- | 670 | ||
- | 671 | list_remove(&cache->link); |
|
- | 672 | ||
- | 673 | spinlock_unlock(&slab_cache_lock); |
|
- | 674 | interrupts_restore(ipl); |
|
- | 675 | ||
647 | /* Do not lock anything, we assume the software is correct and |
676 | /* Do not lock anything, we assume the software is correct and |
648 | * does not touch the cache when it decides to destroy it */ |
677 | * does not touch the cache when it decides to destroy it */ |
649 | 678 | ||
650 | /* Destroy all magazines */ |
679 | /* Destroy all magazines */ |
651 | _slab_reclaim(cache, SLAB_RECLAIM_ALL); |
680 | _slab_reclaim(cache, SLAB_RECLAIM_ALL); |
652 | 681 | ||
653 | /* All slabs must be empty */ |
682 | /* All slabs must be empty */ |
654 | if (!list_empty(&cache->full_slabs) \ |
683 | if (!list_empty(&cache->full_slabs) \ |
655 | || !list_empty(&cache->partial_slabs)) |
684 | || !list_empty(&cache->partial_slabs)) |
656 | panic("Destroying cache that is not empty."); |
685 | panic("Destroying cache that is not empty."); |
657 | 686 | ||
658 | spinlock_lock(&slab_cache_lock); |
- | |
659 | list_remove(&cache->link); |
- | |
660 | spinlock_unlock(&slab_cache_lock); |
- | |
661 | - | ||
662 | slab_free(&slab_cache_cache, cache); |
687 | slab_free(&slab_cache_cache, cache); |
663 | } |
688 | } |
664 | 689 | ||
665 | /** Allocate new object from cache - if no flags given, always returns |
690 | /** Allocate new object from cache - if no flags given, always returns |
666 | memory */ |
691 | memory */ |
667 | void * slab_alloc(slab_cache_t *cache, int flags) |
692 | void * slab_alloc(slab_cache_t *cache, int flags) |
668 | { |
693 | { |
669 | ipl_t ipl; |
694 | ipl_t ipl; |
670 | void *result = NULL; |
695 | void *result = NULL; |
671 | 696 | ||
672 | /* Disable interrupts to avoid deadlocks with interrupt handlers */ |
697 | /* Disable interrupts to avoid deadlocks with interrupt handlers */ |
673 | ipl = interrupts_disable(); |
698 | ipl = interrupts_disable(); |
674 | 699 | ||
675 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) |
700 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) |
676 | result = magazine_obj_get(cache); |
701 | result = magazine_obj_get(cache); |
677 | - | ||
678 | if (!result) |
702 | if (!result) |
679 | result = slab_obj_create(cache, flags); |
703 | result = slab_obj_create(cache, flags); |
680 | 704 | ||
681 | interrupts_restore(ipl); |
705 | interrupts_restore(ipl); |
682 | 706 | ||
683 | if (result) |
707 | if (result) |
684 | atomic_inc(&cache->allocated_objs); |
708 | atomic_inc(&cache->allocated_objs); |
685 | 709 | ||
686 | return result; |
710 | return result; |
687 | } |
711 | } |
688 | 712 | ||
689 | /** Return object to cache, use slab if known */ |
713 | /** Return object to cache, use slab if known */ |
690 | static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab) |
714 | static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab) |
691 | { |
715 | { |
692 | ipl_t ipl; |
716 | ipl_t ipl; |
693 | 717 | ||
694 | ipl = interrupts_disable(); |
718 | ipl = interrupts_disable(); |
695 | 719 | ||
696 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \ |
720 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \ |
697 | || magazine_obj_put(cache, obj)) { |
721 | || magazine_obj_put(cache, obj)) { |
698 | 722 | ||
699 | slab_obj_destroy(cache, obj, slab); |
723 | slab_obj_destroy(cache, obj, slab); |
700 | 724 | ||
701 | } |
725 | } |
702 | interrupts_restore(ipl); |
726 | interrupts_restore(ipl); |
703 | atomic_dec(&cache->allocated_objs); |
727 | atomic_dec(&cache->allocated_objs); |
704 | } |
728 | } |
705 | 729 | ||
706 | /** Return slab object to cache */ |
730 | /** Return slab object to cache */ |
707 | void slab_free(slab_cache_t *cache, void *obj) |
731 | void slab_free(slab_cache_t *cache, void *obj) |
708 | { |
732 | { |
709 | _slab_free(cache,obj,NULL); |
733 | _slab_free(cache,obj,NULL); |
710 | } |
734 | } |
711 | 735 | ||
712 | /* Go through all caches and reclaim what is possible */ |
736 | /* Go through all caches and reclaim what is possible */ |
713 | count_t slab_reclaim(int flags) |
737 | count_t slab_reclaim(int flags) |
714 | { |
738 | { |
715 | slab_cache_t *cache; |
739 | slab_cache_t *cache; |
716 | link_t *cur; |
740 | link_t *cur; |
717 | count_t frames = 0; |
741 | count_t frames = 0; |
718 | 742 | ||
719 | spinlock_lock(&slab_cache_lock); |
743 | spinlock_lock(&slab_cache_lock); |
720 | 744 | ||
721 | /* TODO: Add assert, that interrupts are disabled, otherwise |
745 | /* TODO: Add assert, that interrupts are disabled, otherwise |
722 | * memory allocation from interrupts can deadlock. |
746 | * memory allocation from interrupts can deadlock. |
- | 747 | * - cache_destroy can call this with interrupts enabled :-/ |
|
723 | */ |
748 | */ |
724 | 749 | ||
725 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
750 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
726 | cache = list_get_instance(cur, slab_cache_t, link); |
751 | cache = list_get_instance(cur, slab_cache_t, link); |
727 | frames += _slab_reclaim(cache, flags); |
752 | frames += _slab_reclaim(cache, flags); |
728 | } |
753 | } |
729 | 754 | ||
730 | spinlock_unlock(&slab_cache_lock); |
755 | spinlock_unlock(&slab_cache_lock); |
731 | 756 | ||
732 | return frames; |
757 | return frames; |
733 | } |
758 | } |
734 | 759 | ||
735 | 760 | ||
736 | /* Print list of slabs */ |
761 | /* Print list of slabs */ |
737 | void slab_print_list(void) |
762 | void slab_print_list(void) |
738 | { |
763 | { |
739 | slab_cache_t *cache; |
764 | slab_cache_t *cache; |
740 | link_t *cur; |
765 | link_t *cur; |
741 | 766 | ||
742 | spinlock_lock(&slab_cache_lock); |
767 | spinlock_lock(&slab_cache_lock); |
743 | printf("SLAB name\tOsize\tPages\tObj/pg\tSlabs\tCached\tAllocobjs\tCtl\n"); |
768 | printf("SLAB name\tOsize\tPages\tObj/pg\tSlabs\tCached\tAllocobjs\tCtl\n"); |
744 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
769 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
745 | cache = list_get_instance(cur, slab_cache_t, link); |
770 | cache = list_get_instance(cur, slab_cache_t, link); |
746 | printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t\t%s\n", cache->name, cache->size, |
771 | printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t\t%s\n", cache->name, cache->size, |
747 | (1 << cache->order), cache->objects, |
772 | (1 << cache->order), cache->objects, |
748 | atomic_get(&cache->allocated_slabs), |
773 | atomic_get(&cache->allocated_slabs), |
749 | atomic_get(&cache->cached_objs), |
774 | atomic_get(&cache->cached_objs), |
750 | atomic_get(&cache->allocated_objs), |
775 | atomic_get(&cache->allocated_objs), |
751 | cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out"); |
776 | cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out"); |
752 | } |
777 | } |
753 | spinlock_unlock(&slab_cache_lock); |
778 | spinlock_unlock(&slab_cache_lock); |
754 | } |
779 | } |
755 | 780 | ||
756 | #ifdef CONFIG_DEBUG |
781 | #ifdef CONFIG_DEBUG |
757 | static int _slab_initialized = 0; |
782 | static int _slab_initialized = 0; |
758 | #endif |
783 | #endif |
759 | 784 | ||
760 | void slab_cache_init(void) |
785 | void slab_cache_init(void) |
761 | { |
786 | { |
762 | int i, size; |
787 | int i, size; |
763 | 788 | ||
764 | /* Initialize magazine cache */ |
789 | /* Initialize magazine cache */ |
765 | _slab_cache_create(&mag_cache, |
790 | _slab_cache_create(&mag_cache, |
766 | "slab_magazine", |
791 | "slab_magazine", |
767 | sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*), |
792 | sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*), |
768 | sizeof(__address), |
793 | sizeof(__address), |
769 | NULL, NULL, |
794 | NULL, NULL, |
770 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
795 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
771 | /* Initialize slab_cache cache */ |
796 | /* Initialize slab_cache cache */ |
772 | _slab_cache_create(&slab_cache_cache, |
797 | _slab_cache_create(&slab_cache_cache, |
773 | "slab_cache", |
798 | "slab_cache", |
774 | sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]), |
799 | sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]), |
775 | sizeof(__address), |
800 | sizeof(__address), |
776 | NULL, NULL, |
801 | NULL, NULL, |
777 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
802 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
778 | /* Initialize external slab cache */ |
803 | /* Initialize external slab cache */ |
779 | slab_extern_cache = slab_cache_create("slab_extern", |
804 | slab_extern_cache = slab_cache_create("slab_extern", |
780 | sizeof(slab_t), |
805 | sizeof(slab_t), |
781 | 0, NULL, NULL, |
806 | 0, NULL, NULL, |
782 | SLAB_CACHE_SLINSIDE); |
807 | SLAB_CACHE_SLINSIDE); |
783 | 808 | ||
784 | /* Initialize structures for malloc */ |
809 | /* Initialize structures for malloc */ |
785 | for (i=0, size=(1<<SLAB_MIN_MALLOC_W); |
810 | for (i=0, size=(1<<SLAB_MIN_MALLOC_W); |
786 | i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1); |
811 | i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1); |
787 | i++, size <<= 1) { |
812 | i++, size <<= 1) { |
788 | malloc_caches[i] = slab_cache_create(malloc_names[i], |
813 | malloc_caches[i] = slab_cache_create(malloc_names[i], |
789 | size, 0, |
814 | size, 0, |
790 | NULL,NULL,0); |
815 | NULL,NULL,0); |
791 | } |
816 | } |
792 | #ifdef CONFIG_DEBUG |
817 | #ifdef CONFIG_DEBUG |
793 | _slab_initialized = 1; |
818 | _slab_initialized = 1; |
794 | #endif |
819 | #endif |
795 | } |
820 | } |
796 | 821 | ||
797 | /**************************************/ |
822 | /**************************************/ |
798 | /* kalloc/kfree functions */ |
823 | /* kalloc/kfree functions */ |
799 | void * kalloc(unsigned int size, int flags) |
824 | void * kalloc(unsigned int size, int flags) |
800 | { |
825 | { |
801 | int idx; |
826 | int idx; |
802 | 827 | ||
803 | ASSERT(_slab_initialized); |
828 | ASSERT(_slab_initialized); |
804 | ASSERT( size && size <= (1 << SLAB_MAX_MALLOC_W)); |
829 | ASSERT( size && size <= (1 << SLAB_MAX_MALLOC_W)); |
805 | 830 | ||
806 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
831 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
807 | size = (1 << SLAB_MIN_MALLOC_W); |
832 | size = (1 << SLAB_MIN_MALLOC_W); |
808 | 833 | ||
809 | idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1; |
834 | idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1; |
810 | 835 | ||
811 | return slab_alloc(malloc_caches[idx], flags); |
836 | return slab_alloc(malloc_caches[idx], flags); |
812 | } |
837 | } |
813 | 838 | ||
814 | 839 | ||
815 | void kfree(void *obj) |
840 | void kfree(void *obj) |
816 | { |
841 | { |
817 | slab_t *slab = obj2slab(obj); |
842 | slab_t *slab; |
818 | 843 | ||
- | 844 | if (!obj) return; |
|
- | 845 | ||
- | 846 | slab = obj2slab(obj); |
|
819 | _slab_free(slab->cache, obj, slab); |
847 | _slab_free(slab->cache, obj, slab); |
820 | } |
848 | } |
821 | 849 |