1 /******************************************************************************* 2 * Copyright (C) 2018 Cadence Design Systems, Inc. 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to use this Software with Cadence processor cores only and 7 * not with any other processors and platforms, subject to 8 * the following conditions: 9 * 10 * The above copyright notice and this permission notice shall be included 11 * in all copies or substantial portions of the Software. 12 * 13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 14 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 15 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 16 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 17 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 18 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 19 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 20 21 ******************************************************************************/ 22 23 /******************************************************************************* 24 * xf-mem.c 25 * 26 * Dynamic memory allocator implementation (based on rb-tree index) 27 * 28 ******************************************************************************/ 29 30 #define MODULE_TAG MM 31 32 /******************************************************************************* 33 * Includes 34 ******************************************************************************/ 35 36 #include "xf.h" 37 38 /******************************************************************************* 39 * Tracing configuration 40 ******************************************************************************/ 41 42 TRACE_TAG(INIT, 1); 43 44 /******************************************************************************* 45 * Internal helpers 46 ******************************************************************************/ 47 48 /* ...initialize block */ 49 static inline xf_mm_block_t * xf_mm_block_init(void *addr, u32 size) 50 { 51 xf_mm_block_t *b = (xf_mm_block_t *)addr; 52 53 /* ...use 31 available bits of node color to keep aligned size */ 54 return b->l_node.color = size, b; 55 } 56 57 /* ...check if the length of the block is less than given */ 58 static inline int xf_mm_block_length_less(xf_mm_block_t *b, u32 size) 59 { 60 /* ...we don't really care about LSB of color */ 61 return (b->l_node.color < size); 62 } 63 64 /* ...return exact block length */ 65 static inline u32 xf_mm_block_length(xf_mm_block_t *b) 66 { 67 /* ...wipe out least-significant bit from node color */ 68 return (b->l_node.color & ~1); 69 } 70 71 /* ...increase block length */ 72 static inline u32 xf_mm_block_length_add(xf_mm_block_t *b, u32 size) 73 { 74 /* ...return exact block length after increase */ 75 return ((b->l_node.color += size) & ~1); 76 } 77 78 /* ...decrease block length */ 79 static inline u32 xf_mm_block_length_sub(xf_mm_block_t *b, u32 size) 80 { 81 /* ...return exact block length after decrease */ 82 return ((b->l_node.color -= size) & ~1); 83 } 84 85 /******************************************************************************* 86 * Internal functions 87 ******************************************************************************/ 88 89 /* ...find best-match node given requested size */ 90 static inline xf_mm_block_t * xf_mm_find_by_size(xf_mm_pool_t *pool, u32 size) 91 { 92 rb_tree_t *tree = &pool->l_map; 93 rb_idx_t p_idx, t_idx; 94 95 /* ...find first block having length greater than requested */ 96 for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = rb_right(tree, p_idx)) 97 { 98 xf_mm_block_t *b = container_of(p_idx, xf_mm_block_t, l_node); 99 100 /* ...break upon finding first matching candidate */ 101 if (!xf_mm_block_length_less(b, size)) 102 break; 103 } 104 105 /* ...bail out if haven't found a block with sufficient size */ 106 if (p_idx == rb_null(tree)) 107 return NULL; 108 109 /* ...try to find better match in left subtree */ 110 for (t_idx = rb_left(tree, p_idx); t_idx != rb_null(tree); ) 111 { 112 xf_mm_block_t *b = container_of(t_idx, xf_mm_block_t, l_node); 113 114 /* ...check the size of the block */ 115 if (!xf_mm_block_length_less(b, size)) 116 { 117 /* ...update best match */ 118 p_idx = t_idx; 119 120 /* ...and check if we have anything better in left sbtree */ 121 t_idx = rb_left(tree, t_idx); 122 } 123 else 124 { 125 /* ...move towards higher block sizes in that subtree */ 126 t_idx = rb_right(tree, t_idx); 127 } 128 } 129 130 /* ...p_idx is our best choice */ 131 return container_of(p_idx, xf_mm_block_t, l_node); 132 } 133 134 /* ...find the neighbours of the block basing on its address */ 135 static void xf_mm_find_by_addr(xf_mm_pool_t *pool, void *addr, xf_mm_block_t **n) 136 { 137 rb_tree_t *tree = &pool->a_map; 138 rb_idx_t p_idx, l_idx, r_idx; 139 140 /* ...it is not possible to have exact match in this map */ 141 for (p_idx = rb_root(tree), l_idx = r_idx = NULL; p_idx != rb_null(tree); ) 142 { 143 /* ...only "is less than" comparison is valid (as "a_node" pointer is biased) */ 144 if ((u32)p_idx < (u32)addr) 145 { 146 /* ...update lower neighbour */ 147 l_idx = p_idx; 148 149 /* ...and move towards higher addresses */ 150 p_idx = rb_right(tree, p_idx); 151 } 152 else 153 { 154 /* ...update higher neighbour */ 155 r_idx = p_idx; 156 157 /* ...and move towards lower addresses */ 158 p_idx = rb_left(tree, p_idx); 159 } 160 } 161 162 /* ...translate nodes into blocks */ 163 n[0] = (l_idx ? container_of(l_idx, xf_mm_block_t, a_node) : NULL); 164 n[1] = (r_idx ? container_of(r_idx, xf_mm_block_t, a_node) : NULL); 165 } 166 167 /* ...insert the block into L-map */ 168 static void xf_mm_insert_size(xf_mm_pool_t *pool, xf_mm_block_t *b, u32 size) 169 { 170 rb_tree_t *tree = &pool->l_map; 171 rb_idx_t p_idx, t_idx; 172 173 /* ...find the parent node for the next block */ 174 for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = t_idx) 175 { 176 /* ...check for the size */ 177 if (xf_mm_block_length_less(container_of(p_idx, xf_mm_block_t, l_node), size)) 178 { 179 /* ...move towards higher addresses */ 180 if ((t_idx = rb_right(tree, p_idx)) == rb_null(tree)) 181 { 182 /* ...node becomes a right child of parent p */ 183 rb_set_right(tree, p_idx, &b->l_node); 184 break; 185 } 186 } 187 else 188 { 189 /* ...move towards lower addresses (ok if exact size match is found) */ 190 if ((t_idx = rb_left(tree, p_idx)) == rb_null(tree)) 191 { 192 /* ...node becomes a left child of parent p */ 193 rb_set_left(tree, p_idx, &b->l_node); 194 break; 195 } 196 } 197 } 198 199 /* ...insert node into tree */ 200 rb_insert(tree, &b->l_node, p_idx); 201 } 202 203 /* ...insert the block into A-map */ 204 static void xf_mm_insert_addr(xf_mm_pool_t *pool, xf_mm_block_t *b) 205 { 206 rb_tree_t *tree = &pool->a_map; 207 rb_idx_t p_idx, t_idx; 208 209 /* ...find the parent node for the next block */ 210 for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = t_idx) 211 { 212 /* ...check for the address (only "is less than" comparison is valid) */ 213 if ((u32)p_idx < (u32)b) 214 { 215 /* ...move towards higher addresses */ 216 if ((t_idx = rb_right(tree, p_idx)) == rb_null(tree)) 217 { 218 /* ...node becomes a right child of parent p */ 219 rb_set_right(tree, p_idx, &b->a_node); 220 break; 221 } 222 } 223 else 224 { 225 /* ...move towards lower addresses (by design there cannot be exact match) */ 226 if ((t_idx = rb_left(tree, p_idx)) == rb_null(tree)) 227 { 228 /* ...node becomes a left child of parent p */ 229 rb_set_left(tree, p_idx, &b->a_node); 230 break; 231 } 232 } 233 } 234 235 /* ...insert node into tree */ 236 rb_insert(tree, &b->a_node, p_idx); 237 } 238 239 /******************************************************************************* 240 * Entry points 241 ******************************************************************************/ 242 243 /* ...block allocation */ 244 void * xf_mm_alloc(xf_mm_pool_t *pool, u32 size) 245 { 246 xf_mm_block_t *b; 247 248 /* ...find best-fit free block */ 249 XF_CHK_ERR(b = xf_mm_find_by_size(pool, size), NULL); 250 251 /* ...remove the block from the L-map */ 252 rb_delete(&pool->l_map, &b->l_node); 253 254 /* ...check if the size is exactly the same as requested */ 255 if ((size = xf_mm_block_length_sub(b, size)) == 0) 256 { 257 /* ...the block needs to be removed from the A-map as well */ 258 rb_delete(&pool->a_map, &b->a_node); 259 260 /* ...entire block goes to user */ 261 return (void *) b; 262 } 263 else 264 { 265 /* ...insert the block into L-map */ 266 xf_mm_insert_size(pool, b, size); 267 268 /* ...A-map remains intact; tail of the block goes to user */ 269 return (void *) b + size; 270 } 271 } 272 273 /* ...block deallocation */ 274 void xf_mm_free(xf_mm_pool_t *pool, void *addr, u32 size) 275 { 276 xf_mm_block_t *b = xf_mm_block_init(addr, size); 277 xf_mm_block_t *n[2]; 278 279 /* ...find block neighbours in A-map */ 280 xf_mm_find_by_addr(pool, addr, n); 281 282 /* ...check if we can merge block to left neighbour */ 283 if (n[0]) 284 { 285 if ((void *)n[0] + xf_mm_block_length(n[0]) == addr) 286 { 287 /* ...merge free block with left neighbour; delete it from L-map */ 288 rb_delete(&pool->l_map, &n[0]->l_node); 289 290 /* ...adjust block length (block remains in A-map) */ 291 addr = (void *)(b = n[0]), size = xf_mm_block_length_add(b, size); 292 } 293 else 294 { 295 /* ...mark there is no left-merge */ 296 n[0] = NULL; 297 } 298 } 299 300 /* ...check if we can merge block to right neighbour */ 301 if (n[1]) 302 { 303 if ((void *)n[1] == addr + size) 304 { 305 /* ...merge free block with right neighbour; delete it from L-map */ 306 rb_delete(&pool->l_map, &n[1]->l_node); 307 308 /* ...adjust block length */ 309 size = xf_mm_block_length_add(b, xf_mm_block_length(n[1])); 310 311 /* ...check if left merge took place as well */ 312 if (n[0]) 313 { 314 /* ...left neighbour covers now all three blocks; drop record from A-map */ 315 rb_delete(&pool->a_map, &n[1]->a_node); 316 } 317 else 318 { 319 /* ...fixup tree pointers (equivalent to remove/reinsert the same key) */ 320 rb_replace(&pool->a_map, &n[1]->a_node, &b->a_node); 321 } 322 } 323 else 324 { 325 n[1] = NULL; 326 } 327 } 328 329 /* ...if any merge has occured, A-map is updated */ 330 if (n[0] == NULL && n[1] == NULL) 331 { 332 /* ...add new block into A-map */ 333 xf_mm_insert_addr(pool, b); 334 } 335 336 /* ...add (new or adjusted) block into L-map */ 337 xf_mm_insert_size(pool, b, size); 338 } 339 340 /* ...initialize memory allocator */ 341 int xf_mm_init(xf_mm_pool_t *pool, void *addr, u32 size) 342 { 343 /* ...check pool alignment validity */ 344 XF_CHK_ERR(((u32)addr & (sizeof(xf_mm_block_t) - 1)) == 0, -EINVAL); 345 346 /* ...check pool size validity */ 347 XF_CHK_ERR(((size) & (sizeof(xf_mm_block_t) - 1)) == 0, -EINVAL); 348 349 /* ...set pool parameters (need that stuff at all? - tbd) */ 350 pool->addr = addr, pool->size = size; 351 352 /* ...initialize rb-trees */ 353 rb_init(&pool->l_map), rb_init(&pool->a_map); 354 355 /* ..."free" the entire block */ 356 xf_mm_free(pool, addr, size); 357 358 TRACE(INIT, _b("memory allocator initialized: [%p..%p)"), addr, addr + size); 359 360 return 0; 361 } 362
