source: azure_iot_hub_f767zi/trunk/asp_baseplatform/syssvc/tlsf.c@ 457

Last change on this file since 457 was 457, checked in by coas-nagasima, 4 years ago

ファイルを追加
  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-csrc;charset=UTF-8
File size: 29.9 KB
Line 
1/*
2 * Two Levels Segregate Fit memory allocator (TLSF)
3 * Version 2.4.6
4 *
5 * Written by Miguel Masmano Tello <mimastel@doctor.upv.es>
6 *
7 * Thanks to Ismael Ripoll for his suggestions and reviews
8 *
9 * Copyright (C) 2008, 2007, 2006, 2005, 2004
10 *
11 * This code is released using a dual license strategy: GPL/LGPL
12 * You can choose the licence that better fits your requirements.
13 *
14 * Released under the terms of the GNU General Public License Version 2.0
15 * Released under the terms of the GNU Lesser General Public License Version 2.1
16 *
17 */
18
19/*
20 * Code contributions:
21 *
22 * (Jul 28 2007) Herman ten Brugge <hermantenbrugge@home.nl>:
23 *
24 * - Add 64 bit support. It now runs on x86_64 and solaris64.
25 * - I also tested this on vxworks/32and solaris/32 and i386/32 processors.
26 * - Remove assembly code. I could not measure any performance difference
27 * on my core2 processor. This also makes the code more portable.
28 * - Moved defines/typedefs from tlsf.h to tlsf.c
29 * - Changed MIN_BLOCK_SIZE to sizeof (free_ptr_t) and BHDR_OVERHEAD to
30 * (sizeof (bhdr_t) - MIN_BLOCK_SIZE). This does not change the fact
31 * that the minumum size is still sizeof
32 * (bhdr_t).
33 * - Changed all C++ comment style to C style. (// -> /.* ... *./)
34 * - Used ls_bit instead of ffs and ms_bit instead of fls. I did this to
35 * avoid confusion with the standard ffs function which returns
36 * different values.
37 * - Created set_bit/clear_bit fuctions because they are not present
38 * on x86_64.
39 * - Added locking support + extra file target.h to show how to use it.
40 * - Added get_used_size function (REMOVED in 2.4)
41 * - Added rtl_realloc and rtl_calloc function
42 * - Implemented realloc clever support.
43 * - Added some test code in the example directory.
44 * - Bug fixed (discovered by the rockbox project: www.rockbox.org).
45 *
46 * (Oct 23 2006) Adam Scislowicz:
47 *
48 * - Support for ARMv5 implemented
49 *
50 */
51
52/*#define USE_SBRK (0) */
53/*#define USE_MMAP (0) */
54
55#ifndef USE_PRINTF
56#define USE_PRINTF (1)
57#endif
58
59#include <string.h>
60
61#ifndef TLSF_USE_LOCKS
62#define TLSF_USE_LOCKS (0)
63#endif
64
65#ifndef TLSF_STATISTIC
66#define TLSF_STATISTIC (0)
67#endif
68
69#ifndef USE_MMAP
70#define USE_MMAP (0)
71#endif
72
73#ifndef USE_SBRK
74#define USE_SBRK (0)
75#endif
76
77
78#if TLSF_USE_LOCKS
79#include "kernel.h"
80#include "kernel_cfg.h"
81#define TLSF_MLOCK_T ID
82#define TLSF_CREATE_LOCK(lock) (*lock = TLSF_SEM)
83#define TLSF_DESTROY_LOCK(lock) ini_sem(*lock)
84#define TLSF_ACQUIRE_LOCK(lock) wai_sem(*lock)
85#define TLSF_RELEASE_LOCK(lock) sig_sem(*lock)
86#else
87#define TLSF_CREATE_LOCK(_unused_) do{}while(0)
88#define TLSF_DESTROY_LOCK(_unused_) do{}while(0)
89#define TLSF_ACQUIRE_LOCK(_unused_) do{}while(0)
90#define TLSF_RELEASE_LOCK(_unused_) do{}while(0)
91#endif
92
93#if TLSF_STATISTIC
94#define TLSF_ADD_SIZE(tlsf, b) do { \
95 tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
96 if (tlsf->used_size > tlsf->max_size) \
97 tlsf->max_size = tlsf->used_size; \
98 } while(0)
99
100#define TLSF_REMOVE_SIZE(tlsf, b) do { \
101 tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
102 } while(0)
103#else
104#define TLSF_ADD_SIZE(tlsf, b) do{}while(0)
105#define TLSF_REMOVE_SIZE(tlsf, b) do{}while(0)
106#endif
107
108#if USE_MMAP || USE_SBRK
109#include <unistd.h>
110#endif
111
112#if USE_MMAP
113#include <sys/mman.h>
114#endif
115
116#include "tlsf.h"
117
118#if !defined(__GNUC__)
119#ifndef __inline__
120#define __inline__
121#endif
122#endif
123
124/* The debug functions only can be used when _DEBUG_TLSF_ is set. */
125#ifndef _DEBUG_TLSF_
126#define _DEBUG_TLSF_ (0)
127#endif
128
129/*************************************************************************/
130/* Definition of the structures used by TLSF */
131
132
133/* Some IMPORTANT TLSF parameters */
134/* Unlike the preview TLSF versions, now they are statics */
135#define BLOCK_ALIGN (sizeof(void *) * 2)
136
137#define MAX_FLI (30)
138#define MAX_LOG2_SLI (5)
139#define MAX_SLI (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */
140
141#define FLI_OFFSET (6) /* tlsf structure just will manage blocks bigger */
142/* than 128 bytes */
143#define SMALL_BLOCK (128)
144#define REAL_FLI (MAX_FLI - FLI_OFFSET)
145#define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
146#define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
147#define TLSF_SIGNATURE (0x2A59FA59)
148
149#define PTR_MASK (sizeof(void *) - 1)
150#define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK)
151
152#define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
153#define MEM_ALIGN ((BLOCK_ALIGN) - 1)
154#define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
155#define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
156#define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x))
157
158#define BLOCK_STATE (0x1)
159#define PREV_STATE (0x2)
160
161/* bit 0 of the block size */
162#define FREE_BLOCK (0x1)
163#define USED_BLOCK (0x0)
164
165/* bit 1 of the block size */
166#define PREV_FREE (0x2)
167#define PREV_USED (0x0)
168
169
170#define DEFAULT_AREA_SIZE (1024*10)
171
172#ifdef USE_MMAP
173#define PAGE_SIZE (getpagesize())
174#endif
175
176#ifdef USE_PRINTF
177#include <stdio.h>
178#include <t_stddef.h>
179#include <t_syslog.h>
180#define PRINT_MSG(fmt, args...) syslog(LOG_ERROR, fmt, ## args)
181#define ERROR_MSG(fmt, args...) syslog(LOG_ERROR, fmt, ## args)
182#else
183# if !defined(PRINT_MSG)
184# define PRINT_MSG(fmt, args...)
185# endif
186# if !defined(ERROR_MSG)
187# define ERROR_MSG(fmt, args...)
188# endif
189#endif
190
191typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */
192typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */
193
194typedef struct free_ptr_struct {
195 struct bhdr_struct *prev;
196 struct bhdr_struct *next;
197} free_ptr_t;
198
199typedef struct bhdr_struct {
200 /* This pointer is just valid if the first bit of size is set */
201 struct bhdr_struct *prev_hdr;
202 /* The size is stored in bytes */
203 size_t size; /* bit 0 indicates whether the block is used and */
204 /* bit 1 allows to know whether the previous block is free */
205 union {
206 struct free_ptr_struct free_ptr;
207 u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */
208 } ptr;
209} bhdr_t;
210
211/* This structure is embedded at the beginning of each area, giving us
212 * enough information to cope with a set of areas */
213
214typedef struct area_info_struct {
215 bhdr_t *end;
216 struct area_info_struct *next;
217} area_info_t;
218
219typedef struct TLSF_struct {
220 /* the TLSF's structure signature */
221 u32_t tlsf_signature;
222
223#if TLSF_USE_LOCKS
224 TLSF_MLOCK_T lock;
225#endif
226
227#if TLSF_STATISTIC
228 /* These can not be calculated outside tlsf because we
229 * do not know the sizes when freeing/reallocing memory. */
230 size_t used_size;
231 size_t max_size;
232#endif
233
234 /* A linked list holding all the existing areas */
235 area_info_t *area_head;
236
237 /* the first-level bitmap */
238 /* This array should have a size of REAL_FLI bits */
239 u32_t fl_bitmap;
240
241 /* the second-level bitmap */
242 u32_t sl_bitmap[REAL_FLI];
243
244 bhdr_t *matrix[REAL_FLI][MAX_SLI];
245} tlsf_t;
246
247
248/******************************************************************/
249/************** Helping functions **************************/
250/******************************************************************/
251static __inline__ void set_bit(int nr, u32_t * addr);
252static __inline__ void clear_bit(int nr, u32_t * addr);
253static __inline__ int ls_bit(int x);
254static __inline__ int ms_bit(int x);
255static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
256static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
257static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
258static __inline__ bhdr_t *process_area(void *area, size_t size);
259#if USE_SBRK || USE_MMAP
260static __inline__ void *get_new_area(size_t * size);
261#endif
262
263static const int table[] = {
264 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
265 4, 4,
266 4, 4, 4, 4, 4, 4, 4,
267 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
268 5,
269 5, 5, 5, 5, 5, 5, 5,
270 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
271 6,
272 6, 6, 6, 6, 6, 6, 6,
273 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
274 6,
275 6, 6, 6, 6, 6, 6, 6,
276 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
277 7,
278 7, 7, 7, 7, 7, 7, 7,
279 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
280 7,
281 7, 7, 7, 7, 7, 7, 7,
282 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
283 7,
284 7, 7, 7, 7, 7, 7, 7,
285 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
286 7,
287 7, 7, 7, 7, 7, 7, 7
288};
289
290static __inline__ int ls_bit(int i)
291{
292 unsigned int a;
293 unsigned int x = i & -i;
294
295 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
296 return table[x >> a] + a;
297}
298
299static __inline__ int ms_bit(int i)
300{
301 unsigned int a;
302 unsigned int x = (unsigned int) i;
303
304 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
305 return table[x >> a] + a;
306}
307
308static __inline__ void set_bit(int nr, u32_t * addr)
309{
310 addr[nr >> 5] |= 1 << (nr & 0x1f);
311}
312
313static __inline__ void clear_bit(int nr, u32_t * addr)
314{
315 addr[nr >> 5] &= ~(1 << (nr & 0x1f));
316}
317
318static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
319{
320 int _t;
321
322 if (*_r < SMALL_BLOCK) {
323 *_fl = 0;
324 *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
325 } else {
326 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
327 *_r = *_r + _t;
328 *_fl = ms_bit(*_r);
329 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
330 *_fl -= FLI_OFFSET;
331 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
332 *_fl = *_sl = 0;
333 */
334 *_r &= ~_t;
335 }
336}
337
338static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
339{
340 if (_r < SMALL_BLOCK) {
341 *_fl = 0;
342 *_sl = _r / (SMALL_BLOCK / MAX_SLI);
343 } else {
344 *_fl = ms_bit(_r);
345 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
346 *_fl -= FLI_OFFSET;
347 }
348}
349
350
351static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
352{
353 u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
354 bhdr_t *_b = NULL;
355
356 if (_tmp) {
357 *_sl = ls_bit(_tmp);
358 _b = _tlsf->matrix[*_fl][*_sl];
359 } else {
360 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
361 if (*_fl > 0) { /* likely */
362 *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
363 _b = _tlsf->matrix[*_fl][*_sl];
364 }
365 }
366 return _b;
367}
368
369
370#define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
371 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
372 if (_tlsf -> matrix[_fl][_sl]) \
373 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
374 else { \
375 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
376 if (!_tlsf -> sl_bitmap [_fl]) \
377 clear_bit (_fl, &_tlsf -> fl_bitmap); \
378 } \
379 _b -> ptr.free_ptr.prev = NULL; \
380 _b -> ptr.free_ptr.next = NULL; \
381 }while(0)
382
383
384#define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
385 if (_b -> ptr.free_ptr.next) \
386 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
387 if (_b -> ptr.free_ptr.prev) \
388 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
389 if (_tlsf -> matrix [_fl][_sl] == _b) { \
390 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
391 if (!_tlsf -> matrix [_fl][_sl]) { \
392 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
393 if (!_tlsf -> sl_bitmap [_fl]) \
394 clear_bit (_fl, &_tlsf -> fl_bitmap); \
395 } \
396 } \
397 _b -> ptr.free_ptr.prev = NULL; \
398 _b -> ptr.free_ptr.next = NULL; \
399 } while(0)
400
401#define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
402 _b -> ptr.free_ptr.prev = NULL; \
403 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
404 if (_tlsf -> matrix [_fl][_sl]) \
405 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
406 _tlsf -> matrix [_fl][_sl] = _b; \
407 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
408 set_bit (_fl, &_tlsf -> fl_bitmap); \
409 } while(0)
410
411#if USE_SBRK || USE_MMAP
412static __inline__ void *get_new_area(size_t * size)
413{
414 void *area;
415
416#if USE_SBRK
417 area = (void *)sbrk(0);
418 if (((void *)sbrk(*size)) != ((void *) -1))
419 return area;
420#endif
421
422#ifndef MAP_ANONYMOUS
423/* https://dev.openwrt.org/ticket/322 */
424# define MAP_ANONYMOUS MAP_ANON
425#endif
426
427
428#if USE_MMAP
429 *size = ROUNDUP(*size, PAGE_SIZE);
430 if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED)
431 return area;
432#endif
433 return ((void *) ~0);
434}
435#endif
436
437static __inline__ bhdr_t *process_area(void *area, size_t size)
438{
439 bhdr_t *b, *lb, *ib;
440 area_info_t *ai;
441
442 ib = (bhdr_t *) area;
443 ib->size =
444 (sizeof(area_info_t) <
445 MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
446 b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
447 b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
448 b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
449 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
450 lb->prev_hdr = b;
451 lb->size = 0 | USED_BLOCK | PREV_FREE;
452 ai = (area_info_t *) ib->ptr.buffer;
453 ai->next = 0;
454 ai->end = lb;
455 return ib;
456}
457
458/******************************************************************/
459/******************** Begin of the allocator code *****************/
460/******************************************************************/
461
462static char *mp = NULL; /* Default memory pool. */
463
464/******************************************************************/
465size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
466{
467/******************************************************************/
468 tlsf_t *tlsf;
469 bhdr_t *b, *ib;
470
471 if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
472 ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
473 return -1;
474 }
475
476 if (((unsigned long) mem_pool & PTR_MASK)) {
477 ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
478 return -1;
479 }
480 tlsf = (tlsf_t *) mem_pool;
481 /* Check if already initialised */
482 if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
483 mp = mem_pool;
484 b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
485 return b->size & BLOCK_SIZE;
486 }
487
488 mp = mem_pool;
489
490 /* Zeroing the memory pool */
491 memset(mem_pool, 0, sizeof(tlsf_t));
492
493 tlsf->tlsf_signature = TLSF_SIGNATURE;
494
495 TLSF_CREATE_LOCK(&tlsf->lock);
496
497 ib = process_area(GET_NEXT_BLOCK
498 (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
499 b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
500 free_ex(b->ptr.buffer, tlsf);
501 tlsf->area_head = (area_info_t *) ib->ptr.buffer;
502
503#if TLSF_STATISTIC
504 tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
505 tlsf->max_size = tlsf->used_size;
506#endif
507
508 return (b->size & BLOCK_SIZE);
509}
510
511/******************************************************************/
512size_t add_new_area(void *area, size_t area_size, void *mem_pool)
513{
514/******************************************************************/
515 tlsf_t *tlsf = (tlsf_t *) mem_pool;
516 area_info_t *ptr, *ptr_prev, *ai;
517 bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b;
518
519 memset(area, 0, area_size);
520 ptr = tlsf->area_head;
521 ptr_prev = 0;
522
523 ib0 = process_area(area, area_size);
524 b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE);
525 lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE);
526
527 /* Before inserting the new area, we have to merge this area with the
528 already existing ones */
529
530 while (ptr) {
531 ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
532 b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
533 lb1 = ptr->end;
534
535 /* Merging the new area with the next physically contigous one */
536 if ((unsigned long) ib1 == (unsigned long) lb0 + BHDR_OVERHEAD) {
537 if (tlsf->area_head == ptr) {
538 tlsf->area_head = ptr->next;
539 ptr = ptr->next;
540 } else {
541 ptr_prev->next = ptr->next;
542 ptr = ptr->next;
543 }
544
545 b0->size =
546 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
547 (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
548
549 b1->prev_hdr = b0;
550 lb0 = lb1;
551
552 continue;
553 }
554
555 /* Merging the new area with the previous physically contigous
556 one */
557 if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
558 if (tlsf->area_head == ptr) {
559 tlsf->area_head = ptr->next;
560 ptr = ptr->next;
561 } else {
562 ptr_prev->next = ptr->next;
563 ptr = ptr->next;
564 }
565
566 lb1->size =
567 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
568 (ib0->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | (lb1->size & PREV_STATE);
569 next_b = GET_NEXT_BLOCK(lb1->ptr.buffer, lb1->size & BLOCK_SIZE);
570 next_b->prev_hdr = lb1;
571 b0 = lb1;
572 ib0 = ib1;
573
574 continue;
575 }
576 ptr_prev = ptr;
577 ptr = ptr->next;
578 }
579
580 /* Inserting the area in the list of linked areas */
581 ai = (area_info_t *) ib0->ptr.buffer;
582 ai->next = tlsf->area_head;
583 ai->end = lb0;
584 tlsf->area_head = ai;
585 free_ex(b0->ptr.buffer, mem_pool);
586 return (b0->size & BLOCK_SIZE);
587}
588
589
590/******************************************************************/
591size_t get_used_size(void *mem_pool)
592{
593/******************************************************************/
594#if TLSF_STATISTIC
595 return ((tlsf_t *) mem_pool)->used_size;
596#else
597 return 0;
598#endif
599}
600
601/******************************************************************/
602size_t get_max_size(void *mem_pool)
603{
604/******************************************************************/
605#if TLSF_STATISTIC
606 return ((tlsf_t *) mem_pool)->max_size;
607#else
608 return 0;
609#endif
610}
611
612/******************************************************************/
613void destroy_memory_pool(void *mem_pool)
614{
615/******************************************************************/
616 tlsf_t *tlsf = (tlsf_t *) mem_pool;
617
618 tlsf->tlsf_signature = 0;
619
620 TLSF_DESTROY_LOCK(&tlsf->lock);
621
622}
623
624
625/******************************************************************/
626void *tlsf_malloc(size_t size)
627{
628/******************************************************************/
629 void *ret;
630
631#if USE_MMAP || USE_SBRK
632 if (!mp) {
633 size_t area_size;
634 void *area;
635
636 area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */
637 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
638 area = get_new_area(&area_size);
639 if (area == ((void *) ~0))
640 return NULL; /* Not enough system memory */
641 init_memory_pool(area_size, area);
642 }
643#endif
644
645 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
646
647 ret = malloc_ex(size, mp);
648
649 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
650
651 return ret;
652}
653
654/******************************************************************/
655void tlsf_free(void *ptr)
656{
657/******************************************************************/
658
659 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
660
661 free_ex(ptr, mp);
662
663 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
664
665}
666
667/******************************************************************/
668void *tlsf_realloc(void *ptr, size_t size)
669{
670/******************************************************************/
671 void *ret;
672
673#if USE_MMAP || USE_SBRK
674 if (!mp) {
675 return tlsf_malloc(size);
676 }
677#endif
678
679 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
680
681 ret = realloc_ex(ptr, size, mp);
682
683 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
684
685 return ret;
686}
687
688/******************************************************************/
689void *tlsf_calloc(size_t nelem, size_t elem_size)
690{
691/******************************************************************/
692 void *ret;
693
694 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
695
696 ret = calloc_ex(nelem, elem_size, mp);
697
698 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
699
700 return ret;
701}
702
703/******************************************************************/
704void *malloc_ex(size_t size, void *mem_pool)
705{
706/******************************************************************/
707 tlsf_t *tlsf = (tlsf_t *) mem_pool;
708 bhdr_t *b, *b2, *next_b;
709 int fl, sl;
710 size_t tmp_size;
711
712 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
713
714 /* Rounding up the requested size and calculating fl and sl */
715 MAPPING_SEARCH(&size, &fl, &sl);
716
717 /* Searching a free block, recall that this function changes the values of fl and sl,
718 so they are not longer valid when the function fails */
719 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
720#if USE_MMAP || USE_SBRK
721 if (!b) {
722 size_t area_size;
723 void *area;
724 /* Growing the pool size when needed */
725 area_size = size + BHDR_OVERHEAD * 8; /* size plus enough room for the requered headers. */
726 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
727 area = get_new_area(&area_size); /* Call sbrk or mmap */
728 if (area == ((void *) ~0))
729 return NULL; /* Not enough system memory */
730 add_new_area(area, area_size, mem_pool);
731 /* Rounding up the requested size and calculating fl and sl */
732 MAPPING_SEARCH(&size, &fl, &sl);
733 /* Searching a free block */
734 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
735 }
736#endif
737 if (!b)
738 return NULL; /* Not found */
739
740 EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
741
742 /*-- found: */
743 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
744 /* Should the block be split? */
745 tmp_size = (b->size & BLOCK_SIZE) - size;
746 if (tmp_size >= sizeof(bhdr_t)) {
747 tmp_size -= BHDR_OVERHEAD;
748 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
749 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
750 next_b->prev_hdr = b2;
751 MAPPING_INSERT(tmp_size, &fl, &sl);
752 INSERT_BLOCK(b2, tlsf, fl, sl);
753
754 b->size = size | (b->size & PREV_STATE);
755 } else {
756 next_b->size &= (~PREV_FREE);
757 b->size &= (~FREE_BLOCK); /* Now it's used */
758 }
759
760 TLSF_ADD_SIZE(tlsf, b);
761
762 return (void *) b->ptr.buffer;
763}
764
765/******************************************************************/
766void free_ex(void *ptr, void *mem_pool)
767{
768/******************************************************************/
769 tlsf_t *tlsf = (tlsf_t *) mem_pool;
770 bhdr_t *b, *tmp_b;
771 int fl = 0, sl = 0;
772
773 if (!ptr) {
774 return;
775 }
776 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
777 b->size |= FREE_BLOCK;
778
779 TLSF_REMOVE_SIZE(tlsf, b);
780
781 b->ptr.free_ptr.prev = NULL;
782 b->ptr.free_ptr.next = NULL;
783 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
784 if (tmp_b->size & FREE_BLOCK) {
785 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
786 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
787 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
788 }
789 if (b->size & PREV_FREE) {
790 tmp_b = b->prev_hdr;
791 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
792 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
793 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
794 b = tmp_b;
795 }
796 MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
797 INSERT_BLOCK(b, tlsf, fl, sl);
798
799 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
800 tmp_b->size |= PREV_FREE;
801 tmp_b->prev_hdr = b;
802}
803
804/******************************************************************/
805void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
806{
807/******************************************************************/
808 tlsf_t *tlsf = (tlsf_t *) mem_pool;
809 void *ptr_aux;
810 unsigned int cpsize;
811 bhdr_t *b, *tmp_b, *next_b;
812 int fl, sl;
813 size_t tmp_size;
814
815 if (!ptr) {
816 if (new_size)
817 return (void *) malloc_ex(new_size, mem_pool);
818 if (!new_size)
819 return NULL;
820 } else if (!new_size) {
821 free_ex(ptr, mem_pool);
822 return NULL;
823 }
824
825 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
826 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
827 new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
828 tmp_size = (b->size & BLOCK_SIZE);
829 if (new_size <= tmp_size) {
830 TLSF_REMOVE_SIZE(tlsf, b);
831 if (next_b->size & FREE_BLOCK) {
832 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
833 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
834 tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
835 next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
836 /* We allways reenter this free block because tmp_size will
837 be greater then sizeof (bhdr_t) */
838 }
839 tmp_size -= new_size;
840 if (tmp_size >= sizeof(bhdr_t)) {
841 tmp_size -= BHDR_OVERHEAD;
842 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
843 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
844 next_b->prev_hdr = tmp_b;
845 next_b->size |= PREV_FREE;
846 MAPPING_INSERT(tmp_size, &fl, &sl);
847 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
848 b->size = new_size | (b->size & PREV_STATE);
849 }
850 TLSF_ADD_SIZE(tlsf, b);
851 return (void *) b->ptr.buffer;
852 }
853 if ((next_b->size & FREE_BLOCK)) {
854 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
855 TLSF_REMOVE_SIZE(tlsf, b);
856 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
857 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
858 b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
859 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
860 next_b->prev_hdr = b;
861 next_b->size &= ~PREV_FREE;
862 tmp_size = (b->size & BLOCK_SIZE) - new_size;
863 if (tmp_size >= sizeof(bhdr_t)) {
864 tmp_size -= BHDR_OVERHEAD;
865 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
866 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
867 next_b->prev_hdr = tmp_b;
868 next_b->size |= PREV_FREE;
869 MAPPING_INSERT(tmp_size, &fl, &sl);
870 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
871 b->size = new_size | (b->size & PREV_STATE);
872 }
873 TLSF_ADD_SIZE(tlsf, b);
874 return (void *) b->ptr.buffer;
875 }
876 }
877
878 if (!(ptr_aux = malloc_ex(new_size, mem_pool))){
879 return NULL;
880 }
881
882 cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
883
884 memcpy(ptr_aux, ptr, cpsize);
885
886 free_ex(ptr, mem_pool);
887 return ptr_aux;
888}
889
890
891/******************************************************************/
892void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
893{
894/******************************************************************/
895 void *ptr;
896
897 if (nelem <= 0 || elem_size <= 0)
898 return NULL;
899
900 if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
901 return NULL;
902 memset(ptr, 0, nelem * elem_size);
903
904 return ptr;
905}
906
907
908
909#if _DEBUG_TLSF_
910
911/*************** DEBUG FUNCTIONS **************/
912
913/* The following functions have been designed to ease the debugging of */
914/* the TLSF structure. For non-developing purposes, it may be they */
915/* haven't too much worth. To enable them, _DEBUG_TLSF_ must be set. */
916
917extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
918extern void print_block(bhdr_t * b);
919extern void print_tlsf(tlsf_t * tlsf);
920void print_all_blocks(tlsf_t * tlsf);
921
922void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
923{
924
925 unsigned long begin = (unsigned long) mem_ptr;
926 unsigned long end = (unsigned long) mem_ptr + size;
927 int column = 0;
928
929 begin >>= 2;
930 begin <<= 2;
931
932 end >>= 2;
933 end++;
934 end <<= 2;
935
936 PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
937
938 column = 0;
939 PRINT_MSG("0x%lx ", begin);
940
941 while (begin < end) {
942 if (((unsigned char *) begin)[0] == 0)
943 PRINT_MSG("00");
944 else
945 PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
946 if (((unsigned char *) begin)[1] == 0)
947 PRINT_MSG("00 ");
948 else
949 PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
950 begin += 2;
951 column++;
952 if (column == 8) {
953 PRINT_MSG("\n0x%lx ", begin);
954 column = 0;
955 }
956
957 }
958 PRINT_MSG("\n\n");
959}
960
961void print_block(bhdr_t * b)
962{
963 if (!b)
964 return;
965 PRINT_MSG(">> [%p] (", b);
966 if ((b->size & BLOCK_SIZE))
967 PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
968 else
969 PRINT_MSG("sentinel, ");
970 if ((b->size & BLOCK_STATE) == FREE_BLOCK)
971 PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next);
972 else
973 PRINT_MSG("used, ");
974 if ((b->size & PREV_STATE) == PREV_FREE)
975 PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
976 else
977 PRINT_MSG("prev used)\n");
978}
979
980void print_tlsf(tlsf_t * tlsf)
981{
982 bhdr_t *next;
983 int i, j;
984
985 PRINT_MSG("\nTLSF at %p\n", tlsf);
986
987 PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
988
989 for (i = 0; i < REAL_FLI; i++) {
990 if (tlsf->sl_bitmap[i])
991 PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]);
992 for (j = 0; j < MAX_SLI; j++) {
993 next = tlsf->matrix[i][j];
994 if (next)
995 PRINT_MSG("-> [%d][%d]\n", i, j);
996 while (next) {
997 print_block(next);
998 next = next->ptr.free_ptr.next;
999 }
1000 }
1001 }
1002}
1003
1004void print_all_blocks(tlsf_t * tlsf)
1005{
1006 area_info_t *ai;
1007 bhdr_t *next;
1008 PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
1009 ai = tlsf->area_head;
1010 while (ai) {
1011 next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
1012 while (next) {
1013 print_block(next);
1014 if ((next->size & BLOCK_SIZE))
1015 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
1016 else
1017 next = NULL;
1018 }
1019 ai = ai->next;
1020 }
1021}
1022
1023#endif
Note: See TracBrowser for help on using the repository browser.