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