summaryrefslogtreecommitdiff
path: root/firmware/test/memory/memory-slab.c
diff options
context:
space:
mode:
Diffstat (limited to 'firmware/test/memory/memory-slab.c')
-rw-r--r--firmware/test/memory/memory-slab.c463
1 files changed, 0 insertions, 463 deletions
diff --git a/firmware/test/memory/memory-slab.c b/firmware/test/memory/memory-slab.c
deleted file mode 100644
index 289818b24a..0000000000
--- a/firmware/test/memory/memory-slab.c
+++ /dev/null
@@ -1,463 +0,0 @@
1/***************************************************************************
2 * __________ __ ___.
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
7 * \/ \/ \/ \/ \/
8 * $Id:
9 *
10 * Copyright (C) 2002 by Alan Korr
11 *
12 * All files in this archive are subject to the GNU General Public License.
13 * See the file COPYING in the source tree root for full license agreement.
14 *
15 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
16 * KIND, either express or implied.
17 *
18 ****************************************************************************/
19#if 0
20
21#include <memory.h>
22
23static struct memory_cache *free_block_cache[MEMORY_PAGE_MINIMAL_SIZE - ];
24static struct memory_cache *cache_list;
25
26static inline int get_order (unsigned size)
27 {
28 int order = 0;
29 size = (size + sizeof(struct memory_free_block) - 1) & - sizeof(struct memory_free_block);
30 while (size > 0)
31 {
32 ++order; size <<= 1;
33 }
34 return order;
35 }
36
37static inline struct memory_slab *get_slab (struct memory_cache *cache,void *address)
38 {
39#ifdef TEST
40 return (struct memory_slab *)((((unsigned)address + cache->page_size) & -cache->page_size) - sizeof (struct memory_slab));
41#else
42 return (struct memory_slab *)((free_page + (((unsigned)address - free_page + cache->page_size) & -cache->page_size) - sizeof (struct memory_slab)));
43#endif
44 }
45
46static struct memory_cache *splay_cache (struct memory_cache *root,unsigned int left)
47 {
48 struct memory_cache *down;
49 struct memory_cache *less;
50 struct memory_cache *more;
51 struct memory_cache head;
52 head.less =
53 head.more = 0;
54 less =
55 more = &head;
56 while (1)
57 {
58 if (left < root->left)
59 {
60 if ((down = root->less))
61 {
62 if (left < down->left)
63 {
64 root->less = down->more;
65 down->more = root;
66 root = down;
67 if (!root->less)
68 break;
69 }
70 more->less = root;
71 more = root;
72 root = root->less;
73 continue;
74 }
75 break;
76 }
77 if (root->left < left)
78 {
79 if ((down = root->more))
80 {
81 if (root->left < left)
82 {
83 root->more = down->less;
84 down->less = root;
85 root = down;
86 if (!root->more)
87 break;
88 }
89 less->more = root;
90 less = root;
91 root = root->more;
92 continue;
93 }
94 }
95 break;
96 }
97 less->more = root->less;
98 more->less = root->more;
99 root->less = head.more;
100 root->more = head.less;
101 return root;
102 }
103
104static inline struct memory_cache *insert_cache (struct memory_cache *root,struct memory_cache *node)
105 {
106 node->less =
107 node->more =
108 node->same = 0;
109 if (root)
110 {
111 if (node->left == ((root = splay_cache (root,node))->left))
112 {
113 node->less = root.less;
114 node->more = root.more;
115 node->same = root;
116 root->less = node;
117 }
118 else if (node < root)
119 {
120 node->less = root->less;
121 node->more = root;
122 root->less = 0;
123 }
124 else
125 {
126 node->less = root;
127 node->more = root->more;
128 node->more = 0;
129 }
130 }
131 return node;
132 }
133
134static inline struct memory_cache *remove_cache (struct memory_cache *root,struct memory_cache *node)
135 {
136 if (root)
137 {
138 root = splay_cache (root,node);
139 if (root != node)
140 {
141 node->less->same = node->same;
142 if (node->same)
143 node->same->less = node->less;
144 return root;
145 }
146 if (root->less)
147 {
148 node = splay_page (root->less,node);
149 node->more = root->more;
150 }
151 else
152 node = root->more;
153 }
154 return root;
155 }
156
157static inline struct memory_cache *move_cache (struct memory_cache *root,struct memory_cache *node,int delta)
158 {
159 if ((root = remove_cache (root,node)))
160 {
161 node->left += delta;
162 root = insert_cache (root,node);
163 }
164 return root;
165 }
166
167static inline struct memory_slab *push_slab (struct memory_cache *head,struct memory_cache *node)
168 {
169 node->less = head;
170 if (head)
171 {
172 node->more = head->more;
173 head->more = node;
174 }
175 else
176 node->more = 0;
177 return node;
178 }
179
180static inline struct memory_slab *pop_slab (struct memory_cache *head,struct memory_cache *node)
181 {
182 if (head)
183 head->more = node->more;
184 return node->more;
185 }
186
187static inline struct memory_slab *move_slab (struct memory_slab **from,struct memory_slab **to)
188 {
189 struct memory_slab *head = *from;
190 *from = (*from)->more;
191 if (*from)
192 (*from)->less = head->less;
193 head->less = 0;
194 head->more = (*to);
195 if (*to)
196 (*to)->prev = head;
197 *to = head;
198 return head;
199 }
200
201
202/*****************************************************************************/
203/* PUBLIC FUNCTIONS */
204/*****************************************************************************/
205
206///////////////////////////////////////////////////////////////////////////////
207// MEMORY CACHE :
208/////////////////
209//
210// - memory_grow_cache : allocate a new slab for a cache
211// - memory_shrink_cache : release free slabs from a cache
212// - memory_create_cache : create a new cache of size-fixed blocks
213// - memory_destroy_cache : destroy the cache and release all the slabs
214// - memory_cache_allocate : allocate a block from the cache
215// - memory_cache_release : release a block in the cache
216//
217
218struct memory_slab *memory_grow_cache (struct memory_cache *cache)
219 {
220 struct memory_slab *slab;
221 unsigned int page;
222 if (cache)
223 {
224 page = (unsigned int)memory_allocate_page (cache->page_order);
225 if (page)
226 {
227 struct memory_free_block *block,**link;
228 slab = (struct memory_slab *)(page + cache->page_size - sizeof (struct memory_slab));
229 slab->free = 0;
230 slab->left = 0;
231 link = &slab->free;
232 for ((unsigned int)block = page;
233 (unsigned int)block + cache->size < (unsigned int)slab;
234 (unsigned int)block += cache->size)
235 {
236 *link = block;
237 link = &block->link;
238 ++slab->free;
239 }
240 *link = 0;
241 cache->blocks_per_slab = slab->free;
242 cache->reap = push_slab (cache->reap,slab);
243 cache_list = move_cache (cache_list,cache,+1);
244 return slab;
245 }
246 }
247 return MEMORY_RETURN_FAILURE;
248 }
249
250static int memory_shrink_cache (struct memory_cache *cache,int all,int move)
251 {
252 struct memory_slab *slab;
253 unsigned int slabs = 0;
254 if (cache)
255 {
256 while ((slab = cache->reap))
257 {
258 ++slabs;
259 cache->reap = pop_slab (cache->reap,slab);
260 memory_release_page ((void *)slab);
261 if (all)
262 continue;
263 if (move)
264 cache_list = move_cache (cache_list,cache,-slabs);
265 return MEMORY_RETURN_SUCCESS;
266 }
267 }
268 return MEMORY_RETURN_FAILURE;
269 }
270
271int memory_shrink_cache (struct memory_cache *cache,int all)
272 {
273 return shrink_cache (cache,all,1 /* move cache in cache_list */);
274 }
275
276struct memory_cache *memory_create_cache (unsigned int size,int align,int flags)
277 {
278 struct memory_cache *cache;
279 unsigned int waste = 0,blocks_per_page;
280 int page_order;
281 unsigned int page_size;
282 unsigned int original_size = size;
283
284 // Align size on 'align' bytes ('align' should equal 1<<n)
285 // if 'align' is inferior to 4, 32-bit word alignment is done by default.
286 size = (align > 4) ? ((size + align - 1) & -align) : ((size + sizeof (int) - 1) & -sizeof (int));
287 if (!(cache = memory_cache_allocate (&cache_cache))
288 return MEMORY_RETURN_FAILURE;
289
290 cache->flags =
291 cache->left = 0;
292
293 cache->used =
294 cache->free =
295 cache->reap = 0;
296
297 cache->original_size = original_size;
298 cache->size = size;
299
300 page_size = 0;
301 page_order = MEMORY_PAGE_MINIMAL_SIZE;;
302
303 // Trying to determine what is the best number of pages per slab
304 for (;; ++order,(page_size <<= 1))
305 {
306 if (page_order >= MEMORY_MAXIMUM_PAGE_ORDER_PER_SLAB)
307 {
308 memory_cache_release (&cache_cache,cache);
309 return MEMORY_RETURN_FAILURE;
310 }
311
312 waste = page_size;
313 waste -= sizeof (struct memory_slab);
314
315 blocks_per_slab = waste / size;
316 waste -= block_per_slab * size;
317
318 if (blocks_per_slab < MEMORY_MINIMUM_BLOCKS_PER_SLAB)
319 {
320 ++page_order; page_size <<= 1;
321 continue;
322 }
323
324 // below 3% of lost space is correct
325 if ((waste << 16) / page_size) < 1967)
326 break;
327 ++page_order; page_size <<= 1;
328 }
329
330 cache->page_size = page_size;
331 cache->page_order = page_order;
332
333 cache_list = insert_cache (cache_list,cache);
334
335 return cache;
336 }
337
338int memory_destroy_cache (struct memory_cache *cache)
339 {
340 if (cache)
341 {
342 cache_list = remove_cache (cache_list,cache);
343 if (shrink_cache (cache,1 /* release all free slabs */,0 /* don't move in cache_list */))
344 return memory_cache_release (&cache_cache,cache);
345 }
346 return MEMORY_RETURN_FAILURE;
347 }
348
349void *memory_cache_allocate (struct memory_cache *cache)
350 {
351 if (cache)
352 {
353 do
354 {
355 struct memory_slab *slab;
356 if ((slab = cache->free))
357 {
358 if (slab->left > 0)
359 {
360ok: struct memory_free_block *block = slab->free;
361 slab->free = block->link;
362 if (--slab->left == 0)
363 move_slab (&cache->free,&cache->used);
364 return block;
365 }
366 }
367 if (cache->reap)
368 {
369 slab = move_slab (&cache->reap,&cache->free);
370 cache_list = move_cache (cache_list,cache,-1);
371 goto ok;
372 }
373 }
374 while (grow_cache (cache));
375 }
376 return MEMORY_RETURN_FAILURE;
377 }
378
379int memory_cache_release (struct memory_cache *cache,void *address)
380 {
381 struct memory_slab *slab = get_slab (cache,address);
382 slab->free = (struct memory_free_block *)address;
383 if (slab->left++ == 0)
384 move_slab (&cache->used,&cache->free);
385 else if (slab->left == cache->elements_per_slab)
386 {
387 move_slab (&cache->free,&cache->reap);
388 cache_list = move_cache (cache_list,cache,+1);
389 }
390 return MEMORY_RETURN_SUCCESS;
391 }
392
393
394///////////////////////////////////////////////////////////////////////////////
395// MEMORY BLOCK :
396/////////////////
397//
398// - memory_allocate_small_block : allocate a small block (no page)
399// - memory_release_small_block : release a small block (no page)
400// - memory_allocate_block : allocate a block (or a page)
401// - memory_release_block : release a block (or a page)
402//
403
404static inline void *allocate_small_block (int order)
405 {
406 struct memory_cache *cache = free_block_cache[order];
407 do
408 {
409 if (cache)
410 return memory_cache_allocate (cache);
411 }
412 while ((free_block_cache[order] = cache = memory_create_cache (size,0,0)));
413 return MEMORY_RETURN_FAILURE;
414 }
415
416void *memory_allocate_small_block (int order)
417 {
418 if (order < MEMORY_PAGE_MINIMAL_ORDER)
419 return allocate_small_block (order)
420 return MEMORY_RETURN_FAILURE;
421 }
422
423static inline int release_small_block (int order,void *address)
424 {
425 struct memory_cache *cache = free_block_cache[order];
426 if (cache)
427 return memory_cache_release (cache,address);
428 return MEMORY_RETURN_FAILURE;
429 }
430
431int memory_release_small_block (int order,void *address)
432 {
433 if (order < MEMORY_PAGE_MINIMAL_ORDER)
434 return memory_release_small_block (order,address);
435 return memory_release_page (address);
436 }
437
438void *memory_allocate_block (unsigned int size)
439 {
440 size += sizeof (int *);
441 int order = get_order (size);
442 if (size < MEMORY_PAGE_MINIMAL_SIZE)
443 {
444 int *block = (int *)allocate_block (order);
445 *block = order;
446 return block;
447 }
448 if (size < MEMORY_PAGE_MAXIMAL_SIZE)
449 return memory_allocate_page (order);
450 return MEMORY_RETURN_FAILURE;
451 }
452
453int memory_release_block (void *address)
454 {
455 int order = *((int *)address);
456 if (order < MEMORY_PAGE_MINIMAL_ORDER)
457 return release_block (order);
458 if (order < MEMORY_PAGE_MAXIMAL_ORDER)
459 return memory_release_page (address);
460 return MEMORY_RETURN_FAILURE;
461 }
462
463#endif \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-24 23:15:03 +0000