/src/kamailio/src/core/mem/tlsf_malloc_bits.h
Line | Count | Source (jump to first uncovered line) |
1 | | #ifndef INCLUDED_tlsfbits |
2 | | #define INCLUDED_tlsfbits |
3 | | |
4 | | #if defined(__cplusplus) |
5 | | #define tlsf_decl inline |
6 | | #else |
7 | | #define tlsf_decl static |
8 | | #endif |
9 | | |
10 | | /* |
11 | | ** Architecture-specific bit manipulation routines. |
12 | | ** |
13 | | ** TLSF achieves O(1) cost for malloc and free operations by limiting |
14 | | ** the search for a free block to a free list of guaranteed size |
15 | | ** adequate to fulfill the request, combined with efficient free list |
16 | | ** queries using bitmasks and architecture-specific bit-manipulation |
17 | | ** routines. |
18 | | ** |
19 | | ** Most modern processors provide instructions to count leading zeroes |
20 | | ** in a word, find the lowest and highest set bit, etc. These |
21 | | ** specific implementations will be used when available, falling back |
22 | | ** to a reasonably efficient generic implementation. |
23 | | ** |
24 | | ** NOTE: TLSF spec relies on ffs/fls returning value 0..31. |
25 | | ** ffs/fls return 1-32 by default, returning 0 for error. |
26 | | */ |
27 | | |
28 | | /* |
29 | | ** Detect whether or not we are building for a 32- or 64-bit (LP/LLP) |
30 | | ** architecture. There is no reliable portable method at compile-time. |
31 | | */ |
32 | | #if defined(__alpha__) || defined(__ia64__) || defined(__x86_64__) \ |
33 | | || defined(_WIN64) || defined(__LP64__) || defined(__LLP64__) |
34 | | #define TLSF_64BIT |
35 | | #endif |
36 | | |
37 | | /* |
38 | | ** gcc 3.4 and above have builtin support, specialized for architecture. |
39 | | ** Some compilers masquerade as gcc; patchlevel test filters them out. |
40 | | ** |
41 | | ** Note: clang is compatible with GCC builtins and will also define those macros |
42 | | */ |
43 | | #if defined(__GNUC__) \ |
44 | | && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) \ |
45 | | && defined(__GNUC_PATCHLEVEL__) |
46 | | |
47 | | tlsf_decl int tlsf_ffs(unsigned int word) |
48 | 0 | { |
49 | 0 | return __builtin_ffs(word) - 1; |
50 | 0 | } |
51 | | |
52 | | tlsf_decl int tlsf_fls(unsigned int word) |
53 | 0 | { |
54 | 0 | const int bit = word ? 32 - __builtin_clz(word) : 0; |
55 | 0 | return bit - 1; |
56 | 0 | } |
57 | | |
58 | | #if defined(TLSF_64BIT) |
59 | | tlsf_decl int tlsf_fls_sizet(size_t size) |
60 | 0 | { |
61 | 0 | const int bit = size ? 64 - __builtin_clzl(size) : 0; |
62 | 0 | return bit - 1; |
63 | 0 | } |
64 | | #endif |
65 | | #else |
66 | | /* Fall back to generic implementation. */ |
67 | | |
68 | | tlsf_decl int tlsf_fls_generic(unsigned int word) |
69 | | { |
70 | | int bit = 32; |
71 | | |
72 | | if(!word) |
73 | | bit -= 1; |
74 | | if(!(word & 0xffff0000)) { |
75 | | word <<= 16; |
76 | | bit -= 16; |
77 | | } |
78 | | if(!(word & 0xff000000)) { |
79 | | word <<= 8; |
80 | | bit -= 8; |
81 | | } |
82 | | if(!(word & 0xf0000000)) { |
83 | | word <<= 4; |
84 | | bit -= 4; |
85 | | } |
86 | | if(!(word & 0xc0000000)) { |
87 | | word <<= 2; |
88 | | bit -= 2; |
89 | | } |
90 | | if(!(word & 0x80000000)) { |
91 | | word <<= 1; |
92 | | bit -= 1; |
93 | | } |
94 | | |
95 | | return bit; |
96 | | } |
97 | | |
98 | | /* Implement ffs in terms of fls. */ |
99 | | tlsf_decl int tlsf_ffs(unsigned int word) |
100 | | { |
101 | | return tlsf_fls_generic(word & (~word + 1)) - 1; |
102 | | } |
103 | | |
104 | | tlsf_decl int tlsf_fls(unsigned int word) |
105 | | { |
106 | | return tlsf_fls_generic(word) - 1; |
107 | | } |
108 | | |
109 | | #if defined(TLSF_64BIT) |
110 | | tlsf_decl int tlsf_fls_sizet(size_t size) |
111 | | { |
112 | | int high = (int)(size >> 32); |
113 | | int bits = 0; |
114 | | if(high) { |
115 | | bits = 32 + tlsf_fls(high); |
116 | | } else { |
117 | | bits = tlsf_fls((int)size & 0xffffffff); |
118 | | } |
119 | | return bits; |
120 | | } |
121 | | #endif /* defined (TLSF_64BIT) */ |
122 | | |
123 | | #endif /* GNUC */ |
124 | | |
125 | | |
126 | | #if !defined(TLSF_64BIT) |
127 | | #define tlsf_fls_sizet tlsf_fls |
128 | | #endif |
129 | | |
130 | | #undef tlsf_decl |
131 | | |
132 | | #endif |