code.grnet.gr Git - archipelago/blob - xseg/xtypes/xheap.c

   1 #include <xtypes/xheap.h>
   2 #include <xtypes/domain.h>
   3
   4 // small allocations are considered those  < 1 << (alignment_unit + SMALL_LIMIT)
   5 #define SMALL_LIMIT 5
   6 // medium allocations are considered those < 1 << (alignment_unit + MEDIUM_LIMIT)
   7 #define MEDIUM_LIMIT 10
   8
   9 //This (the -3) ensures that the space that is allocated
  10 //beyond the requested bytes is less than 12.5 % of requested space
  11 #define MEDIUM_AL_UNIT (SMALL_LIMIT - 3)
  12 #define LARGE_AL_UNIT (MEDIUM_LIMIT - 3)
  13
  14 /*
  15  * Heap allocation sizes:
  16  * 0 - SMALL_LIMIT -> bytes round up to (1 << alignment_unit)
  17  * SMALL_LIMIT - MEDIUM_LIMIT -> bytes round up to (1 << (alignment_unit+ MEDIUM_AL_UNIT))
  18  * MEDIUM_LIMIT - ... -> bytes round up to ( 1 << (alignment_unit + LARGE_AL_UNIT) )
  19  */
  20
  21 //aligned alloc bytes with header size
  22 static inline uint64_t __get_alloc_bytes(struct xheap *xheap, uint64_t bytes)
  23 {
  24         if (bytes < 1<<(xheap->alignment_unit + SMALL_LIMIT))
  25                 return __align(bytes + sizeof(struct xheap_header),
  26                                 xheap->alignment_unit);
  27         else if (bytes < 1<<(xheap->alignment_unit + MEDIUM_LIMIT))
  28                 return __align(bytes + sizeof(struct xheap_header),
  29                                 xheap->alignment_unit + MEDIUM_AL_UNIT);
  30         else
  31                 return __align(bytes + sizeof(struct xheap_header),
  32                                 xheap->alignment_unit + LARGE_AL_UNIT);
  33 }
  34
  35 static inline struct xheap_header* __get_header(void *ptr)
  36 {
  37         return (struct xheap_header *) ((unsigned long)ptr - sizeof(struct xheap_header));
  38 }
  39
  40 static inline int __get_index(struct xheap *heap, uint64_t bytes)
  41 {
  42         int r;
  43         uint32_t alignment_unit = heap->alignment_unit;
  44         bytes = __get_alloc_bytes(heap, bytes) - sizeof(struct xheap_header);
  45
  46         if (bytes < (1<<(alignment_unit + SMALL_LIMIT)))
  47                 r = bytes >> alignment_unit;
  48         else if (bytes < (1 << (alignment_unit + MEDIUM_LIMIT))) {
  49                 r = (1 << SMALL_LIMIT);
  50                 //r -= (1 << (alignment_unit+SMALL_LIMIT)) / (1 << (alignment_unit + MEDIUM_AL_UNIT));
  51                 r -= (1 << (SMALL_LIMIT - MEDIUM_AL_UNIT));
  52                 //XSEGLOG("%u, %u, r %d\n",((1<<alignment_unit) * 32), (1 << (alignment_unit +2)), r);
  53                 r += (bytes >> (alignment_unit + MEDIUM_AL_UNIT));
  54         }
  55         else {
  56                 r = (1 << SMALL_LIMIT) + (1 << MEDIUM_LIMIT);
  57                 r -= 1 << (SMALL_LIMIT - MEDIUM_AL_UNIT);
  58                 r -= 1 << (MEDIUM_LIMIT - (LARGE_AL_UNIT - MEDIUM_AL_UNIT));
  59                 r += bytes >> (alignment_unit + LARGE_AL_UNIT);
  60         }
  61         return r;
  62 }
  63
  64 uint64_t xheap_get_chunk_size(void *ptr)
  65 {
  66         struct xheap_header *h = __get_header(ptr);
  67         return h->size;
  68 }
  69
  70 void* xheap_allocate(struct xheap *heap, uint64_t bytes)
  71 {
  72         struct xheap_header *h;
  73         int r = __get_index(heap, bytes);
  74         void *mem = XPTR(&heap->mem), *addr = NULL;
  75         xptr *free_list = (xptr *) mem;
  76         xptr head, next;
  77         uint64_t req_bytes = bytes;
  78
  79         xlock_acquire(&heap->lock, 1);
  80
  81         head = free_list[r];
  82         //printf("(r: %d) list[%x]: %lu\n", r, &free_list[r], list);
  83         if (!head)
  84                 goto alloc;
  85         if (head > heap->cur) {
  86                 XSEGLOG("invalid xptr %llu found in chunk lists\n", head);
  87                 goto out;
  88         }
  89         next = *(xptr *)(((unsigned long) mem) + head);
  90         free_list[r] = next;
  91 //      XSEGLOG("alloced %llu bytes from list %d\n", bytes, r);
  92 //      printf("popped %llu out of list. list is now %llu\n", head, next);
  93         addr = (void *) (((unsigned long)mem) + head);
  94         goto out;
  95
  96 alloc:
  97         bytes = __get_alloc_bytes(heap, bytes);
  98 //      printf("before heap->cur: %llu\n", heap->cur);
  99 //      printf("bytes: %llu\n", bytes);
 100         if (heap->cur + bytes > heap->size)
 101                 goto out;
 102         addr = (void *) (((unsigned long) mem) + heap->cur + sizeof(struct xheap_header));
 103 //      printf("after heap->cur: %llu\n", heap->cur);
 104         h = (struct xheap_header *) (((unsigned long) mem) + heap->cur);
 105         h->size = bytes - sizeof(struct xheap_header);
 106         XPTRSET(&h->heap, heap);
 107         heap->cur += bytes;
 108
 109 out:
 110         xlock_release(&heap->lock);
 111 //      printf("alloced: %lx (size: %llu) (xptr: %llu)\n", addr, __get_header(addr)->size,
 112 //                      addr-mem);
 113         if (addr && xheap_get_chunk_size(addr) < req_bytes){
 114                 XSEGLOG("requested %llu bytes but heap returned %llu",
 115                                 req_bytes, xheap_get_chunk_size(addr));
 116                 addr = NULL;
 117         }
 118         if (addr && xheap_get_chunk_size(addr) != (__get_alloc_bytes(heap, req_bytes) -
 119                                         sizeof(struct xheap_header))) {
 120                 XSEGLOG("allocated chunk size %llu, but it should be %llu (req_bytes %llu)",
 121                         xheap_get_chunk_size(addr), __get_alloc_bytes(heap, req_bytes), req_bytes);
 122                 addr = NULL;
 123         }
 124         return addr;
 125 }
 126
 127 static inline void __add_in_free_list(struct xheap *heap, xptr* list, void *ptr)
 128 {
 129         void *mem = XPTR(&heap->mem);
 130         xptr abs_ptr = (xptr) ((unsigned long)ptr - (unsigned long) mem);
 131         xptr cur, *node = (xptr *) ptr;
 132
 133         xlock_acquire(&heap->lock, 2);
 134
 135         cur = *(volatile xptr *)list;
 136         *node = cur;
 137         *list = abs_ptr;
 138         //printf("cur: %llu, next: %llu\n", cur, abs_ptr);
 139         //printf("next points to %llu\n", *(xptr *) ptr);
 140
 141         xlock_release(&heap->lock);
 142 }
 143
 144 void xheap_free(void *ptr)
 145 {
 146         struct xheap_header *h = __get_header(ptr);
 147         struct xheap *heap = XPTR(&h->heap);
 148         void *mem = XPTR(&heap->mem);
 149         uint64_t size = xheap_get_chunk_size(ptr);
 150         xptr *free_list = (xptr *) mem;
 151         int r = __get_index(heap, size);
 152         //printf("size: %llu, r: %d\n", size, r);
 153         __add_in_free_list(heap, &free_list[r], ptr);
 154 //      printf("freed %lx (size: %llu)\n", ptr, __get_header(ptr)->size);
 155 //      XSEGLOG("freed %llu bytes to list %d\n", size, r);
 156         return;
 157 }
 158
 159 int xheap_init(struct xheap *heap, uint64_t size, uint32_t alignment_unit, void *mem)
 160 {
 161         //int r = (sizeof(size)*8 - __builtin_clzl(size));
 162         int r, i;
 163         void *al_mem = (void *) __align((unsigned long)mem, alignment_unit);
 164         uint64_t diff = (uint64_t) ((unsigned long)al_mem - (unsigned long)mem);
 165         uint64_t heap_page = 1 << alignment_unit;
 166         xptr * free_list;
 167
 168         heap->cur = diff;
 169         heap->size = size;
 170         heap->alignment_unit = alignment_unit;
 171         XPTRSET(&heap->mem, mem);
 172
 173         r = __get_index(heap, size);
 174
 175         /* minimum alignment unit required */
 176         if (heap_page < sizeof(struct xheap_header))
 177                 return -1;
 178         //if (heap_page < sizeof(xptr *) * r)
 179         //      return -1;
 180
 181         /* make sure unused space in heap start can hold a header*/
 182         if (heap->cur < sizeof(struct xheap_header)) {
 183                 heap->cur += heap_page;
 184         }
 185         heap->cur -= sizeof(struct xheap_header);
 186
 187         /* make sure there is enough unused space in heap start to be
 188          * used as an indexing array
 189          */
 190         while (heap->cur < sizeof(xptr *) * r)
 191                         heap->cur += heap_page;
 192
 193         /* clean up index array */
 194         free_list = (xptr *) mem;
 195         for (i = 0; i < r; i++) {
 196                 free_list[i] = 0;
 197         }
 198
 199         /* make sure there is at least one "heap_page" to allocate */
 200         if (heap->cur >= size - heap_page)
 201                 return -1;
 202         xlock_release(&heap->lock);
 203
 204         return 0;
 205 }