Outline ![]()
Files ![]()
loading...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
/*
* SPDX-FileCopyrightText: 2024 Matthew Conte
*
* SPDX-License-Identifier: BSD-3-Clause
*/
#pragma once
#include "tlsf_block_functions.h"
#if defined(__cplusplus)
extern "C" {
#define tlsf_decl static inline
#else
#define tlsf_decl static inline __attribute__((always_inline))
#endif
enum tlsf_config
{
/* All allocation sizes and addresses are aligned to 4 bytes. */
ALIGN_SIZE_LOG2 = 2,
ALIGN_SIZE = (1 << ALIGN_SIZE_LOG2),
};
/* The TLSF control structure. */
typedef struct control_t
{
/* Empty lists point at this block to indicate they are free. */
block_header_t block_null;
/* Local parameter for the pool. Given the maximum
* value of each field, all the following parameters
* can fit on 4 bytes when using bitfields
*/
unsigned int fl_index_count : 5; // 5 cumulated bits
unsigned int fl_index_shift : 3; // 8 cumulated bits
unsigned int fl_index_max : 6; // 14 cumulated bits
unsigned int sl_index_count : 6; // 20 cumulated bits
/* log2 of number of linear subdivisions of block sizes. Larger
** values require more memory in the control structure. Values of
** 4 or 5 are typical.
*/
unsigned int sl_index_count_log2 : 3; // 23 cumulated bits
unsigned int small_block_size : 8; // 31 cumulated bits
/* size of the metadata ( size of control block,
* sl_bitmap and blocks )
*/
size_t size;
/* Bitmaps for free lists. */
unsigned int fl_bitmap;
unsigned int *sl_bitmap;
/* Head of free lists. */
block_header_t** blocks;
} control_t;
/*
** Architecture-specific bit manipulation routines.
**
** TLSF achieves O(1) cost for malloc and free operations by limiting
** the search for a free block to a free list of guaranteed size
** adequate to fulfill the request, combined with efficient free list
** queries using bitmasks and architecture-specific bit-manipulation
** routines.
**
** Most modern processors provide instructions to count leading zeroes
** in a word, find the lowest and highest set bit, etc. These
** specific implementations will be used when available, falling back
** to a reasonably efficient generic implementation.
**
** NOTE: TLSF spec relies on ffs/fls returning value 0..31.
** ffs/fls return 1-32 by default, returning 0 for error.
*/
/*
** Detect whether or not we are building for a 32- or 64-bit (LP/LLP)
** architecture. There is no reliable portable method at compile-time.
*/
#if defined (__alpha__) || defined (__ia64__) || defined (__x86_64__) \
|| defined (_WIN64) || defined (__LP64__) || defined (__LLP64__)
#define TLSF_64BIT
#endif
/*
** gcc 3.4 and above have builtin support, specialized for architecture.
** Some compilers masquerade as gcc; patchlevel test filters them out.
*/
#if defined (__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) \
&& defined (__GNUC_PATCHLEVEL__)
#if defined (__SNC__)
/* SNC for Playstation 3. */
tlsf_decl int tlsf_ffs(unsigned int word)
{
const unsigned int reverse = word & (~word + 1);
const int bit = 32 - __builtin_clz(reverse);
return bit - 1;
}
#else
tlsf_decl int tlsf_ffs(unsigned int word)
{
return __builtin_ffs(word) - 1;
}
#endif
tlsf_decl int tlsf_fls(unsigned int word)
{
const int bit = word ? 32 - __builtin_clz(word) : 0;
return bit - 1;
}
#elif defined (_MSC_VER) && (_MSC_VER >= 1400) && (defined (_M_IX86) || defined (_M_X64))
/* Microsoft Visual C++ support on x86/X64 architectures. */
#include <intrin.h>
#pragma intrinsic(_BitScanReverse)
#pragma intrinsic(_BitScanForward)
tlsf_decl int tlsf_fls(unsigned int word)
{
unsigned long index;
return _BitScanReverse(&index, word) ? index : -1;
}
tlsf_decl int tlsf_ffs(unsigned int word)
{
unsigned long index;
return _BitScanForward(&index, word) ? index : -1;
}
#elif defined (_MSC_VER) && defined (_M_PPC)
/* Microsoft Visual C++ support on PowerPC architectures. */
#include <ppcintrinsics.h>
tlsf_decl int tlsf_fls(unsigned int word)
{
const int bit = 32 - _CountLeadingZeros(word);
return bit - 1;
}
tlsf_decl int tlsf_ffs(unsigned int word)
{
const unsigned int reverse = word & (~word + 1);
const int bit = 32 - _CountLeadingZeros(reverse);
return bit - 1;
}
#elif defined (__ARMCC_VERSION)
/* RealView Compilation Tools for ARM */
tlsf_decl int tlsf_ffs(unsigned int word)
{
const unsigned int reverse = word & (~word + 1);
const int bit = 32 - __clz(reverse);
return bit - 1;
}
tlsf_decl int tlsf_fls(unsigned int word)
{
const int bit = word ? 32 - __clz(word) : 0;
return bit - 1;
}
#elif defined (__ghs__)
/* Green Hills support for PowerPC */
#include <ppc_ghs.h>
tlsf_decl int tlsf_ffs(unsigned int word)
{
const unsigned int reverse = word & (~word + 1);
const int bit = 32 - __CLZ32(reverse);
return bit - 1;
}
tlsf_decl int tlsf_fls(unsigned int word)
{
const int bit = word ? 32 - __CLZ32(word) : 0;
return bit - 1;
}
#else
/* Fall back to generic implementation. */
tlsf_decl int tlsf_fls_generic(unsigned int word)
{
int bit = 32;
if (!word) bit -= 1;
if (!(word & 0xffff0000)) { word <<= 16; bit -= 16; }
if (!(word & 0xff000000)) { word <<= 8; bit -= 8; }
if (!(word & 0xf0000000)) { word <<= 4; bit -= 4; }
if (!(word & 0xc0000000)) { word <<= 2; bit -= 2; }
if (!(word & 0x80000000)) { word <<= 1; bit -= 1; }
return bit;
}
/* Implement ffs in terms of fls. */
tlsf_decl int tlsf_ffs(unsigned int word)
{
return tlsf_fls_generic(word & (~word + 1)) - 1;
}
tlsf_decl int tlsf_fls(unsigned int word)
{
return tlsf_fls_generic(word) - 1;
}
#endif
/* Possibly 64-bit version of tlsf_fls. */
#if defined (TLSF_64BIT)
tlsf_decl int tlsf_fls_sizet(size_t size)
{
int high = (int)(size >> 32);
int bits = 0;
if (high)
{
bits = 32 + tlsf_fls(high);
}
else
{
bits = tlsf_fls((int)size & 0xffffffff);
}
return bits;
}
#else
#define tlsf_fls_sizet tlsf_fls
#endif
tlsf_decl size_t align_up(size_t x, size_t align)
{
tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two");
return (x + (align - 1)) & ~(align - 1);
}
tlsf_decl size_t align_down(size_t x, size_t align)
{
tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two");
return x - (x & (align - 1));
}
tlsf_decl void* align_ptr(const void* ptr, size_t align)
{
const tlsfptr_t aligned =
(tlsf_cast(tlsfptr_t, ptr) + (align - 1)) & ~(align - 1);
tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two");
return tlsf_cast(void*, aligned);
}
tlsf_decl size_t tlsf_align_size(void)
{
return ALIGN_SIZE;
}
tlsf_decl size_t tlsf_block_size_min(void)
{
return block_size_min;
}
tlsf_decl size_t tlsf_block_size_max(control_t *control)
{
if (control == NULL)
{
return 0;
}
return tlsf_cast(size_t, 1) << control->fl_index_max;
}
/*
** Adjust an allocation size to be aligned to word size, and no smaller
** than internal minimum.
*/
tlsf_decl size_t adjust_request_size(control_t *control, size_t size, size_t align)
{
size_t adjust = 0;
if (size)
{
const size_t aligned = align_up(size, align);
/* aligned sized must not exceed block_size_max or we'll go out of bounds on sl_bitmap */
if (aligned < tlsf_block_size_max(control))
{
adjust = tlsf_max(aligned, block_size_min);
}
}
return adjust;
}
/*
** TLSF utility functions. In most cases, these are direct translations of
** the documentation found in the white paper.
*/
tlsf_decl void mapping_insert(control_t* control, size_t size, int* fli, int* sli)
{
int fl, sl;
if (size < control->small_block_size)
{
/* Store small blocks in first list. */
fl = 0;
sl = tlsf_cast(int, size) / (control->small_block_size / control->sl_index_count);
}
else
{
fl = tlsf_fls_sizet(size);
sl = tlsf_cast(int, size >> (fl - control->sl_index_count_log2)) ^ (1 << control->sl_index_count_log2);
fl -= (control->fl_index_shift - 1);
}
*fli = fl;
*sli = sl;
}
/* This version rounds up to the next block size (for allocations) */
tlsf_decl void mapping_search(control_t* control, size_t* size, int* fli, int* sli)
{
if (*size >= control->small_block_size)
{
const size_t round = (1 << (tlsf_fls_sizet(*size) - control->sl_index_count_log2));
*size = align_up(*size, round);
}
mapping_insert(control, *size, fli, sli);
}
tlsf_decl block_header_t* search_suitable_block(control_t* control, int* fli, int* sli)
{
int fl = *fli;
int sl = *sli;
/*
** First, search for a block in the list associated with the given
** fl/sl index.
*/
unsigned int sl_map = control->sl_bitmap[fl] & (~0U << sl);
if (!sl_map)
{
/* No block exists. Search in the next largest first-level list. */
const unsigned int fl_map = control->fl_bitmap & (~0U << (fl + 1));
if (!fl_map)
{
/* No free blocks available, memory has been exhausted. */
return 0;
}
fl = tlsf_ffs(fl_map);
*fli = fl;
sl_map = control->sl_bitmap[fl];
}
tlsf_assert(sl_map && "internal error - second level bitmap is null");
sl = tlsf_ffs(sl_map);
*sli = sl;
/* Return the first block in the free list. */
return control->blocks[fl * control->sl_index_count + sl];
}
/* Remove a free block from the free list.*/
tlsf_decl void remove_free_block(control_t* control, block_header_t* block, int fl, int sl)
{
block_header_t* prev = block->prev_free;
block_header_t* next = block->next_free;
tlsf_assert(prev && "prev_free field can not be null");
tlsf_assert(next && "next_free field can not be null");
next->prev_free = prev;
prev->next_free = next;
/* If this block is the head of the free list, set new head. */
if (control->blocks[fl * control->sl_index_count + sl] == block)
{
control->blocks[fl * control->sl_index_count + sl] = next;
/* If the new head is null, clear the bitmap. */
if (next == &control->block_null)
{
control->sl_bitmap[fl] &= ~(1U << sl);
/* If the second bitmap is now empty, clear the fl bitmap. */
if (!control->sl_bitmap[fl])
{
control->fl_bitmap &= ~(1U << fl);
}
}
}
}
/* Insert a free block into the free block list. */
tlsf_decl void insert_free_block(control_t* control, block_header_t* block, int fl, int sl)
{
block_header_t* current = control->blocks[fl * control->sl_index_count + sl];
tlsf_assert(current && "free list cannot have a null entry");
tlsf_assert(block && "cannot insert a null entry into the free list");
block->next_free = current;
block->prev_free = &control->block_null;
current->prev_free = block;
tlsf_assert(block_to_ptr(block) == align_ptr(block_to_ptr(block), ALIGN_SIZE)
&& "block not aligned properly");
/*
** Insert the new block at the head of the list, and mark the first-
** and second-level bitmaps appropriately.
*/
control->blocks[fl * control->sl_index_count + sl] = block;
control->fl_bitmap |= (1U << fl);
control->sl_bitmap[fl] |= (1U << sl);
}
/* Remove a given block from the free list. */
tlsf_decl void block_remove(control_t* control, block_header_t* block)
{
int fl, sl;
mapping_insert(control, block_size(block), &fl, &sl);
remove_free_block(control, block, fl, sl);
}
/* Insert a given block into the free list. */
tlsf_decl void block_insert(control_t* control, block_header_t* block)
{
int fl, sl;
mapping_insert(control, block_size(block), &fl, &sl);
insert_free_block(control, block, fl, sl);
}
tlsf_decl int block_can_split(block_header_t* block, size_t size)
{
return block_size(block) >= sizeof(block_header_t) + size;
}
/* Split a block into two, the second of which is free. */
tlsf_decl block_header_t* block_split(block_header_t* block, size_t size)
{
/* Calculate the amount of space left in the remaining block.
* REMINDER: remaining pointer's first field is `prev_phys_block` but this field is part of the
* previous physical block. */
block_header_t* remaining =
offset_to_block(block_to_ptr(block), size - block_header_overhead);
/* `size` passed as an argument is the first block's new size, thus, the remaining block's size
* is `block_size(block) - size`. However, the block's data must be precedeed by the data size.
* This field is NOT part of the size, so it has to be substracted from the calculation. */
const size_t remain_size = block_size(block) - (size + block_header_overhead);
tlsf_assert(block_to_ptr(remaining) == align_ptr(block_to_ptr(remaining), ALIGN_SIZE)
&& "remaining block not aligned properly");
tlsf_assert(block_size(block) == remain_size + size + block_header_overhead);
block_set_size(remaining, remain_size);
tlsf_assert(block_size(remaining) >= block_size_min && "block split with invalid size");
block_set_size(block, size);
block_mark_as_free(remaining);
/**
* Here is the final outcome of this function:
*
* block remaining (block_ptr + size - BHO)
* + +
* | |
* v v
* +----------------------------------------------------------------------+
* |0000| |xxxxxxxxxxxxxxxxxxxxxx|xxxx| |###########################|
* |0000| |xxxxxxxxxxxxxxxxxxxxxx|xxxx| |###########################|
* |0000| |xxxxxxxxxxxxxxxxxxxxxx|xxxx| |###########################|
* |0000| |xxxxxxxxxxxxxxxxxxxxxx|xxxx| |###########################|
* +----------------------------------------------------------------------+
* | | | |
* + +<------------------------->+ +<------------------------->
* BHO `size` (argument) bytes BHO `remain_size` bytes
*
* Where BHO = block_header_overhead,
* 0: part of the memory owned by a `block`'s previous neighbour,
* x: part of the memory owned by `block`.
* #: part of the memory owned by `remaining`.
*/
return remaining;
}
/*!
* @brief Weak function filling the given memory with a given fill pattern.
*
* @param start: pointer to the start of the memory region to fill
* @param size: size of the memory region to fill
* @param is_free: Indicate if the pattern to use the fill the region should be
* an after free or after allocation pattern.
*/
__attribute__((weak)) void block_absorb_post_hook(void *start, size_t size, bool is_free);
/* Absorb a free block's storage into an adjacent previous free block. */
tlsf_decl block_header_t* block_absorb(block_header_t* prev, block_header_t* block)
{
tlsf_assert(!block_is_last(prev) && "previous block can't be last");
/* Note: Leaves flags untouched. */
prev->size += block_size(block) + block_header_overhead;
block_link_next(prev);
if (block_absorb_post_hook != NULL)
{
block_absorb_post_hook(block, sizeof(block_header_t), POISONING_AFTER_FREE);
}
return prev;
}
/* Merge a just-freed block with an adjacent previous free block. */
tlsf_decl block_header_t* block_merge_prev(control_t* control, block_header_t* block)
{
if (block_is_prev_free(block))
{
block_header_t* prev = block_prev(block);
tlsf_assert(prev && "prev physical block can't be null");
tlsf_assert(block_is_free(prev) && "prev block is not free though marked as such");
block_remove(control, prev);
block = block_absorb(prev, block);
}
return block;
}
/* Merge a just-freed block with an adjacent free block. */
tlsf_decl block_header_t* block_merge_next(control_t* control, block_header_t* block)
{
block_header_t* next = block_next(block);
tlsf_assert(next && "next physical block can't be null");
if (block_is_free(next))
{
tlsf_assert(!block_is_last(block) && "previous block can't be last");
block_remove(control, next);
block = block_absorb(block, next);
}
return block;
}
/* Trim any trailing block space off the end of a block, return to pool. */
tlsf_decl void block_trim_free(control_t* control, block_header_t* block, size_t size)
{
tlsf_assert(block_is_free(block) && "block must be free");
if (block_can_split(block, size))
{
block_header_t* remaining_block = block_split(block, size);
block_link_next(block);
block_set_prev_free(remaining_block);
block_insert(control, remaining_block);
}
}
/* Trim any trailing block space off the end of a used block, return to pool. */
tlsf_decl void block_trim_used(control_t* control, block_header_t* block, size_t size)
{
tlsf_assert(!block_is_free(block) && "block must be used");
if (block_can_split(block, size))
{
/* If the next block is free, we must coalesce. */
block_header_t* remaining_block = block_split(block, size);
block_set_prev_used(remaining_block);
remaining_block = block_merge_next(control, remaining_block);
block_insert(control, remaining_block);
}
}
tlsf_decl block_header_t* block_trim_free_leading(control_t* control, block_header_t* block, size_t size)
{
block_header_t* remaining_block = block;
if (block_can_split(block, size))
{
/* We want to split `block` in two: the first block will be freed and the
* second block will be returned. */
remaining_block = block_split(block, size - block_header_overhead);
/* `remaining_block` is the second block, mark its predecessor (first
* block) as free. */
block_set_prev_free(remaining_block);
block_link_next(block);
/* Put back the first block into the free memory list. */
block_insert(control, block);
}
return remaining_block;
}
tlsf_decl block_header_t* block_locate_free(control_t* control, size_t* size)
{
int fl = 0, sl = 0;
block_header_t* block = 0;
if (*size)
{
mapping_search(control, size, &fl, &sl);
/*
** mapping_search can futz with the size, so for excessively large sizes it can sometimes wind up
** with indices that are off the end of the block array.
** So, we protect against that here, since this is the only callsite of mapping_search.
** Note that we don't need to check sl, since it comes from a modulo operation that guarantees it's always in range.
*/
if (fl < control->fl_index_count)
{
block = search_suitable_block(control, &fl, &sl);
}
}
if (block)
{
tlsf_assert(block_size(block) >= *size);
remove_free_block(control, block, fl, sl);
}
return block;
}
tlsf_decl void* block_prepare_used(control_t* control, block_header_t* block, size_t size)
{
void* p = 0;
if (block)
{
tlsf_assert(size && "size must be non-zero");
block_trim_free(control, block, size);
block_mark_as_used(block);
p = block_to_ptr(block);
}
return p;
}
#undef tlsf_decl
#if defined(__cplusplus)
};
#endif
Details ![]()
Show: from Types: Columns: ![]( "Show Project Names")
![]( "Show Locations")
![]( "Show Referring Symbols")
![]( "Show Scope")
This file uses the notable symbols shown below. Click anywhere in the file to view more details.