1 | Two Level Segregated Fit memory allocator implementation.
|
---|
2 | Written by Matthew Conte (matt@baisoku.org).
|
---|
3 | Public Domain, no restrictions.
|
---|
4 |
|
---|
5 | http://tlsf.baisoku.org
|
---|
6 |
|
---|
7 | Features
|
---|
8 | --------
|
---|
9 | * O(1) cost for malloc, free, realloc, memalign
|
---|
10 | * Extremely low overhead per allocation (4 bytes)
|
---|
11 | * Low overhead per TLSF management of pools (~3kB)
|
---|
12 | * Low fragmentation
|
---|
13 | * Compiles to only a few kB of code and data
|
---|
14 | * Support for adding and removing memory pool regions on the fly
|
---|
15 |
|
---|
16 | Caveats
|
---|
17 | -------
|
---|
18 | * Currently, assumes architecture can make 4-byte aligned accesses
|
---|
19 | * Not designed to be thread safe; the user must provide this
|
---|
20 |
|
---|
21 | Notes
|
---|
22 | -----
|
---|
23 | This code was based on the TLSF 1.4 spec and documentation found at:
|
---|
24 |
|
---|
25 | http://rtportal.upv.es/rtmalloc/allocators/tlsf/index.shtml
|
---|
26 |
|
---|
27 | It also leverages the TLSF 2.0 improvement to shrink the per-block overhead
|
---|
28 | from 8 to 4 bytes.
|
---|
29 |
|
---|
30 | Known Issues
|
---|
31 | ------------
|
---|
32 | * Due to the internal block structure size and the implementation
|
---|
33 | details of tlsf_memalign, there is worst-case behavior when requesting
|
---|
34 | small (<16 byte) blocks aligned to 8-byte boundaries. Overuse of memalign
|
---|
35 | will generally increase fragmentation, but this particular case will leave
|
---|
36 | lots of unusable "holes" in the pool. The solution would be to internally
|
---|
37 | align all blocks to 8 bytes, but this will require significantl changes
|
---|
38 | to the implementation. Contact me if you are interested.
|
---|
39 |
|
---|
40 | History
|
---|
41 | -------
|
---|
42 | 2014/02/08 - v3.0
|
---|
43 | * This version is based on improvements from 3DInteractive GmbH
|
---|
44 | * Interface changed to allow more than one memory pool
|
---|
45 | * Separated pool handling from control structure (adding, removing, debugging)
|
---|
46 | * Control structure and pools can still be constructed in the same memory block
|
---|
47 | * Memory blocks for control structure and pools are checked for alignment
|
---|
48 | * Added functions to retrieve control structure size, alignment size, min and
|
---|
49 | max block size, overhead of pool structure, and overhead of a single allocation
|
---|
50 | * Minimal Pool size is tlsf_block_size_min() + tlsf_pool_overhead()
|
---|
51 | * Pool must be empty when it is removed, in order to allow O(1) removal
|
---|
52 |
|
---|
53 | 2011/10/20 - v2.0
|
---|
54 | * 64-bit support
|
---|
55 | * More compiler intrinsics for ffs/fls
|
---|
56 | * ffs/fls verification during TLSF creation in debug builds
|
---|
57 |
|
---|
58 | 2008/04/04 - v1.9
|
---|
59 | * Add tlsf_heap_check, a heap integrity check
|
---|
60 | * Support a predefined tlsf_assert macro
|
---|
61 | * Fix realloc case where block should shrink; if adjacent block is
|
---|
62 | in use, execution would go down the slow path
|
---|
63 |
|
---|
64 | 2007/02/08 - v1.8
|
---|
65 | * Fix for unnecessary reallocation in tlsf_realloc
|
---|
66 |
|
---|
67 | 2007/02/03 - v1.7
|
---|
68 | * tlsf_heap_walk takes a callback
|
---|
69 | * tlsf_realloc now returns NULL on failure
|
---|
70 | * tlsf_memalign optimization for 4-byte alignment
|
---|
71 | * Usage of size_t where appropriate
|
---|
72 |
|
---|
73 | 2006/11/21 - v1.6
|
---|
74 | * ffs/fls broken out into tlsfbits.h
|
---|
75 | * tlsf_overhead queries per-pool overhead
|
---|
76 |
|
---|
77 | 2006/11/07 - v1.5
|
---|
78 | * Smart realloc implementation
|
---|
79 | * Smart memalign implementation
|
---|
80 |
|
---|
81 | 2006/10/11 - v1.4
|
---|
82 | * Add some ffs/fls implementations
|
---|
83 | * Minor code footprint reduction
|
---|
84 |
|
---|
85 | 2006/09/14 - v1.3
|
---|
86 | * Profiling indicates heavy use of blocks of
|
---|
87 | size 1-128, so implement small block handling
|
---|
88 | * Reduce pool overhead by about 1kb
|
---|
89 | * Reduce minimum block size from 32 to 12 bytes
|
---|
90 | * Realloc bug fix
|
---|
91 |
|
---|
92 | 2006/09/09 - v1.2
|
---|
93 | * Add tlsf_block_size
|
---|
94 | * Static assertion mechanism for invariants
|
---|
95 | * Minor bugfixes
|
---|
96 |
|
---|
97 | 2006/09/01 - v1.1
|
---|
98 | * Add tlsf_realloc
|
---|
99 | * Add tlsf_walk_heap
|
---|
100 |
|
---|
101 | 2006/08/25 - v1.0
|
---|
102 | * First release
|
---|