lib/librte_eal/common/malloc_elem.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2014 Intel Corporation
   3  */
   4 #include <stdint.h>
   5 #include <stddef.h>
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include <sys/queue.h>
   9
  10 #include <rte_memory.h>
  11 #include <rte_eal.h>
  12 #include <rte_launch.h>
  13 #include <rte_per_lcore.h>
  14 #include <rte_lcore.h>
  15 #include <rte_debug.h>
  16 #include <rte_common.h>
  17 #include <rte_spinlock.h>
  18
  19 #include "malloc_elem.h"
  20 #include "malloc_heap.h"
  21
  22 #define MIN_DATA_SIZE (RTE_CACHE_LINE_SIZE)
  23
  24 /*
  25  * Initialize a general malloc_elem header structure
  26  */
  27 void
  28 malloc_elem_init(struct malloc_elem *elem,
  29                 struct malloc_heap *heap, const struct rte_memseg *ms, size_t size)
  30 {
  31         elem->heap = heap;
  32         elem->ms = ms;
  33         elem->prev = NULL;
  34         elem->next = NULL;
  35         memset(&elem->free_list, 0, sizeof(elem->free_list));
  36         elem->state = ELEM_FREE;
  37         elem->size = size;
  38         elem->pad = 0;
  39         set_header(elem);
  40         set_trailer(elem);
  41 }
  42
  43 void
  44 malloc_elem_insert(struct malloc_elem *elem)
  45 {
  46         struct malloc_elem *prev_elem, *next_elem;
  47         struct malloc_heap *heap = elem->heap;
  48
  49         if (heap->first == NULL && heap->last == NULL) {
  50                 /* if empty heap */
  51                 heap->first = elem;
  52                 heap->last = elem;
  53                 prev_elem = NULL;
  54                 next_elem = NULL;
  55         } else if (elem < heap->first) {
  56                 /* if lower than start */
  57                 prev_elem = NULL;
  58                 next_elem = heap->first;
  59                 heap->first = elem;
  60         } else if (elem > heap->last) {
  61                 /* if higher than end */
  62                 prev_elem = heap->last;
  63                 next_elem = NULL;
  64                 heap->last = elem;
  65         } else {
  66                 /* the new memory is somewhere inbetween start and end */
  67                 uint64_t dist_from_start, dist_from_end;
  68
  69                 dist_from_end = RTE_PTR_DIFF(heap->last, elem);
  70                 dist_from_start = RTE_PTR_DIFF(elem, heap->first);
  71
  72                 /* check which is closer, and find closest list entries */
  73                 if (dist_from_start < dist_from_end) {
  74                         prev_elem = heap->first;
  75                         while (prev_elem->next < elem)
  76                                 prev_elem = prev_elem->next;
  77                         next_elem = prev_elem->next;
  78                 } else {
  79                         next_elem = heap->last;
  80                         while (next_elem->prev > elem)
  81                                 next_elem = next_elem->prev;
  82                         prev_elem = next_elem->prev;
  83                 }
  84         }
  85
  86         /* insert new element */
  87         elem->prev = prev_elem;
  88         elem->next = next_elem;
  89         if (prev_elem)
  90                 prev_elem->next = elem;
  91         if (next_elem)
  92                 next_elem->prev = elem;
  93 }
  94
  95 /*
  96  * calculate the starting point of where data of the requested size
  97  * and alignment would fit in the current element. If the data doesn't
  98  * fit, return NULL.
  99  */
 100 static void *
 101 elem_start_pt(struct malloc_elem *elem, size_t size, unsigned align,
 102                 size_t bound)
 103 {
 104         const size_t bmask = ~(bound - 1);
 105         uintptr_t end_pt = (uintptr_t)elem +
 106                         elem->size - MALLOC_ELEM_TRAILER_LEN;
 107         uintptr_t new_data_start = RTE_ALIGN_FLOOR((end_pt - size), align);
 108         uintptr_t new_elem_start;
 109
 110         /* check boundary */
 111         if ((new_data_start & bmask) != ((end_pt - 1) & bmask)) {
 112                 end_pt = RTE_ALIGN_FLOOR(end_pt, bound);
 113                 new_data_start = RTE_ALIGN_FLOOR((end_pt - size), align);
 114                 end_pt = new_data_start + size;
 115                 if (((end_pt - 1) & bmask) != (new_data_start & bmask))
 116                         return NULL;
 117         }
 118
 119         new_elem_start = new_data_start - MALLOC_ELEM_HEADER_LEN;
 120
 121         /* if the new start point is before the exist start, it won't fit */
 122         return (new_elem_start < (uintptr_t)elem) ? NULL : (void *)new_elem_start;
 123 }
 124
 125 /*
 126  * use elem_start_pt to determine if we get meet the size and
 127  * alignment request from the current element
 128  */
 129 int
 130 malloc_elem_can_hold(struct malloc_elem *elem, size_t size,     unsigned align,
 131                 size_t bound)
 132 {
 133         return elem_start_pt(elem, size, align, bound) != NULL;
 134 }
 135
 136 /*
 137  * split an existing element into two smaller elements at the given
 138  * split_pt parameter.
 139  */
 140 static void
 141 split_elem(struct malloc_elem *elem, struct malloc_elem *split_pt)
 142 {
 143         struct malloc_elem *next_elem = elem->next;
 144         const size_t old_elem_size = (uintptr_t)split_pt - (uintptr_t)elem;
 145         const size_t new_elem_size = elem->size - old_elem_size;
 146
 147         malloc_elem_init(split_pt, elem->heap, elem->ms, new_elem_size);
 148         split_pt->prev = elem;
 149         split_pt->next = next_elem;
 150         if (next_elem)
 151                 next_elem->prev = split_pt;
 152         else
 153                 elem->heap->last = split_pt;
 154         elem->next = split_pt;
 155         elem->size = old_elem_size;
 156         set_trailer(elem);
 157 }
 158
 159 /*
 160  * our malloc heap is a doubly linked list, so doubly remove our element.
 161  */
 162 static void __rte_unused
 163 remove_elem(struct malloc_elem *elem)
 164 {
 165         struct malloc_elem *next, *prev;
 166         next = elem->next;
 167         prev = elem->prev;
 168
 169         if (next)
 170                 next->prev = prev;
 171         else
 172                 elem->heap->last = prev;
 173         if (prev)
 174                 prev->next = next;
 175         else
 176                 elem->heap->first = next;
 177
 178         elem->prev = NULL;
 179         elem->next = NULL;
 180 }
 181
 182 static int
 183 next_elem_is_adjacent(struct malloc_elem *elem)
 184 {
 185         return elem->next == RTE_PTR_ADD(elem, elem->size);
 186 }
 187
 188 static int
 189 prev_elem_is_adjacent(struct malloc_elem *elem)
 190 {
 191         return elem == RTE_PTR_ADD(elem->prev, elem->prev->size);
 192 }
 193
 194 /*
 195  * Given an element size, compute its freelist index.
 196  * We free an element into the freelist containing similarly-sized elements.
 197  * We try to allocate elements starting with the freelist containing
 198  * similarly-sized elements, and if necessary, we search freelists
 199  * containing larger elements.
 200  *
 201  * Example element size ranges for a heap with five free lists:
 202  *   heap->free_head[0] - (0   , 2^8]
 203  *   heap->free_head[1] - (2^8 , 2^10]
 204  *   heap->free_head[2] - (2^10 ,2^12]
 205  *   heap->free_head[3] - (2^12, 2^14]
 206  *   heap->free_head[4] - (2^14, MAX_SIZE]
 207  */
 208 size_t
 209 malloc_elem_free_list_index(size_t size)
 210 {
 211 #define MALLOC_MINSIZE_LOG2   8
 212 #define MALLOC_LOG2_INCREMENT 2
 213
 214         size_t log2;
 215         size_t index;
 216
 217         if (size <= (1UL << MALLOC_MINSIZE_LOG2))
 218                 return 0;
 219
 220         /* Find next power of 2 >= size. */
 221         log2 = sizeof(size) * 8 - __builtin_clzl(size-1);
 222
 223         /* Compute freelist index, based on log2(size). */
 224         index = (log2 - MALLOC_MINSIZE_LOG2 + MALLOC_LOG2_INCREMENT - 1) /
 225                 MALLOC_LOG2_INCREMENT;
 226
 227         return index <= RTE_HEAP_NUM_FREELISTS-1?
 228                 index: RTE_HEAP_NUM_FREELISTS-1;
 229 }
 230
 231 /*
 232  * Add the specified element to its heap's free list.
 233  */
 234 void
 235 malloc_elem_free_list_insert(struct malloc_elem *elem)
 236 {
 237         size_t idx;
 238
 239         idx = malloc_elem_free_list_index(elem->size - MALLOC_ELEM_HEADER_LEN);
 240         elem->state = ELEM_FREE;
 241         LIST_INSERT_HEAD(&elem->heap->free_head[idx], elem, free_list);
 242 }
 243
 244 /*
 245  * Remove the specified element from its heap's free list.
 246  */
 247 static void
 248 elem_free_list_remove(struct malloc_elem *elem)
 249 {
 250         LIST_REMOVE(elem, free_list);
 251 }
 252
 253 /*
 254  * reserve a block of data in an existing malloc_elem. If the malloc_elem
 255  * is much larger than the data block requested, we split the element in two.
 256  * This function is only called from malloc_heap_alloc so parameter checking
 257  * is not done here, as it's done there previously.
 258  */
 259 struct malloc_elem *
 260 malloc_elem_alloc(struct malloc_elem *elem, size_t size, unsigned align,
 261                 size_t bound)
 262 {
 263         struct malloc_elem *new_elem = elem_start_pt(elem, size, align, bound);
 264         const size_t old_elem_size = (uintptr_t)new_elem - (uintptr_t)elem;
 265         const size_t trailer_size = elem->size - old_elem_size - size -
 266                 MALLOC_ELEM_OVERHEAD;
 267
 268         elem_free_list_remove(elem);
 269
 270         if (trailer_size > MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE) {
 271                 /* split it, too much free space after elem */
 272                 struct malloc_elem *new_free_elem =
 273                                 RTE_PTR_ADD(new_elem, size + MALLOC_ELEM_OVERHEAD);
 274
 275                 split_elem(elem, new_free_elem);
 276                 malloc_elem_free_list_insert(new_free_elem);
 277
 278                 if (elem == elem->heap->last)
 279                         elem->heap->last = new_free_elem;
 280         }
 281
 282         if (old_elem_size < MALLOC_ELEM_OVERHEAD + MIN_DATA_SIZE) {
 283                 /* don't split it, pad the element instead */
 284                 elem->state = ELEM_BUSY;
 285                 elem->pad = old_elem_size;
 286
 287                 /* put a dummy header in padding, to point to real element header */
 288                 if (elem->pad > 0) { /* pad will be at least 64-bytes, as everything
 289                                      * is cache-line aligned */
 290                         new_elem->pad = elem->pad;
 291                         new_elem->state = ELEM_PAD;
 292                         new_elem->size = elem->size - elem->pad;
 293                         set_header(new_elem);
 294                 }
 295
 296                 return new_elem;
 297         }
 298
 299         /* we are going to split the element in two. The original element
 300          * remains free, and the new element is the one allocated.
 301          * Re-insert original element, in case its new size makes it
 302          * belong on a different list.
 303          */
 304         split_elem(elem, new_elem);
 305         new_elem->state = ELEM_BUSY;
 306         malloc_elem_free_list_insert(elem);
 307
 308         return new_elem;
 309 }
 310
 311 /*
 312  * join two struct malloc_elem together. elem1 and elem2 must
 313  * be contiguous in memory.
 314  */
 315 static inline void
 316 join_elem(struct malloc_elem *elem1, struct malloc_elem *elem2)
 317 {
 318         struct malloc_elem *next = elem2->next;
 319         elem1->size += elem2->size;
 320         if (next)
 321                 next->prev = elem1;
 322         else
 323                 elem1->heap->last = elem1;
 324         elem1->next = next;
 325 }
 326
 327 static struct malloc_elem *
 328 elem_join_adjacent_free(struct malloc_elem *elem)
 329 {
 330         /*
 331          * check if next element exists, is adjacent and is free, if so join
 332          * with it, need to remove from free list.
 333          */
 334         if (elem->next != NULL && elem->next->state == ELEM_FREE &&
 335                         next_elem_is_adjacent(elem)) {
 336                 void *erase;
 337
 338                 /* we will want to erase the trailer and header */
 339                 erase = RTE_PTR_SUB(elem->next, MALLOC_ELEM_TRAILER_LEN);
 340
 341                 /* remove from free list, join to this one */
 342                 elem_free_list_remove(elem->next);
 343                 join_elem(elem, elem->next);
 344
 345                 /* erase header and trailer */
 346                 memset(erase, 0, MALLOC_ELEM_OVERHEAD);
 347         }
 348
 349         /*
 350          * check if prev element exists, is adjacent and is free, if so join
 351          * with it, need to remove from free list.
 352          */
 353         if (elem->prev != NULL && elem->prev->state == ELEM_FREE &&
 354                         prev_elem_is_adjacent(elem)) {
 355                 struct malloc_elem *new_elem;
 356                 void *erase;
 357
 358                 /* we will want to erase trailer and header */
 359                 erase = RTE_PTR_SUB(elem, MALLOC_ELEM_TRAILER_LEN);
 360
 361                 /* remove from free list, join to this one */
 362                 elem_free_list_remove(elem->prev);
 363
 364                 new_elem = elem->prev;
 365                 join_elem(new_elem, elem);
 366
 367                 /* erase header and trailer */
 368                 memset(erase, 0, MALLOC_ELEM_OVERHEAD);
 369
 370                 elem = new_elem;
 371         }
 372
 373         return elem;
 374 }
 375
 376 /*
 377  * free a malloc_elem block by adding it to the free list. If the
 378  * blocks either immediately before or immediately after newly freed block
 379  * are also free, the blocks are merged together.
 380  */
 381 int
 382 malloc_elem_free(struct malloc_elem *elem)
 383 {
 384         void *ptr;
 385         size_t data_len;
 386
 387         ptr = RTE_PTR_ADD(elem, sizeof(*elem));
 388         data_len = elem->size - MALLOC_ELEM_OVERHEAD;
 389
 390         elem = elem_join_adjacent_free(elem);
 391
 392         malloc_elem_free_list_insert(elem);
 393
 394         /* decrease heap's count of allocated elements */
 395         elem->heap->alloc_count--;
 396
 397         memset(ptr, 0, data_len);
 398
 399         return 0;
 400 }
 401
 402 /*
 403  * attempt to resize a malloc_elem by expanding into any free space
 404  * immediately after it in memory.
 405  */
 406 int
 407 malloc_elem_resize(struct malloc_elem *elem, size_t size)
 408 {
 409         const size_t new_size = size + elem->pad + MALLOC_ELEM_OVERHEAD;
 410
 411         /* if we request a smaller size, then always return ok */
 412         if (elem->size >= new_size)
 413                 return 0;
 414
 415         /* check if there is a next element, it's free and adjacent */
 416         if (!elem->next || elem->next->state != ELEM_FREE ||
 417                         !next_elem_is_adjacent(elem))
 418                 return -1;
 419         if (elem->size + elem->next->size < new_size)
 420                 return -1;
 421
 422         /* we now know the element fits, so remove from free list,
 423          * join the two
 424          */
 425         elem_free_list_remove(elem->next);
 426         join_elem(elem, elem->next);
 427
 428         if (elem->size - new_size >= MIN_DATA_SIZE + MALLOC_ELEM_OVERHEAD) {
 429                 /* now we have a big block together. Lets cut it down a bit, by splitting */
 430                 struct malloc_elem *split_pt = RTE_PTR_ADD(elem, new_size);
 431                 split_pt = RTE_PTR_ALIGN_CEIL(split_pt, RTE_CACHE_LINE_SIZE);
 432                 split_elem(elem, split_pt);
 433                 malloc_elem_free_list_insert(split_pt);
 434         }
 435         return 0;
 436 }