lib/librte_eal/common/malloc_elem.c

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