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

   1 #include <xtypes/xheap.h>
   2 #include <xtypes/domain.h>
   3 //#include "xheap.h"
   4 //#include "domain.h"
   5 //#include <stdio.h>
   6
   7 //aligned alloc bytes with header size
   8 static inline uint64_t __get_alloc_bytes(struct xheap *xheap, uint64_t bytes)
   9 {
  10         return __align(bytes + sizeof(struct xheap_header), xheap->alignment_unit);
  11 }
  12
  13 static inline struct xheap_header* __get_header(void *ptr)
  14 {
  15         return (struct xheap_header *) (ptr - sizeof(struct xheap_header));
  16 }
  17
  18 static inline int __get_index(struct xheap *heap, uint64_t bytes)
  19 {
  20         bytes = __get_alloc_bytes(heap, bytes) - sizeof(struct xheap_header);
  21         return (sizeof(bytes)*8 - __builtin_clzl(bytes -1));
  22 }
  23
  24 uint64_t xheap_get_chunk_size(void *ptr)
  25 {
  26         struct xheap_header *h = __get_header(ptr);
  27         return h->size;
  28 }
  29
  30 /* return a pointer to a memory of size
  31  * __align(bytes, xheap->alignment_unit) - sizeof(xheap_header)
  32  */
  33 void* xheap_allocate(struct xheap *heap, uint64_t bytes)
  34 {
  35         struct xheap_header *h;
  36         int r = __get_index(heap, bytes);
  37         void *mem = XPTR(&heap->mem), *addr = NULL;
  38         xptr *free_list = (xptr *) mem;
  39         xptr head, next;
  40
  41         xlock_acquire(&heap->lock, 1);
  42
  43         head = free_list[r];
  44         //printf("(r: %d) list[%x]: %lu\n", r, &free_list[r], list);
  45         if (!head)
  46                 goto alloc;
  47         next = *(xptr *)(((unsigned long) mem) + head);
  48         free_list[r] = next;
  49 //      printf("popped %llu out of list. list is now %llu\n", head, next);
  50         addr = (void *) (((unsigned long)mem) + head);
  51         goto out;
  52
  53 alloc:
  54         bytes = __get_alloc_bytes(heap, bytes);
  55 //      printf("before heap->cur: %llu\n", heap->cur);
  56 //      printf("bytes: %llu\n", bytes);
  57         if (heap->cur + bytes > heap->size)
  58                 goto out;
  59         addr = (void *) (((unsigned long) mem) + heap->cur + sizeof(struct xheap_header));
  60 //      printf("after heap->cur: %llu\n", heap->cur);
  61         h = (struct xheap_header *) (((unsigned long) mem) + heap->cur);
  62         h->size = bytes - sizeof(struct xheap_header);
  63         XPTRSET(&h->heap, heap);
  64         heap->cur += bytes;
  65
  66 out:
  67         xlock_release(&heap->lock);
  68 //      printf("alloced: %lx (size: %llu) (xptr: %llu)\n", addr, __get_header(addr)->size,
  69 //                      addr-mem);
  70         return addr;
  71 }
  72
  73 void __add_in_free_list(struct xheap *heap, xptr* list, void *ptr)
  74 {
  75         void *mem = XPTR(&heap->mem);
  76         xptr abs_ptr = (xptr) ((unsigned long)ptr - (unsigned long) mem);
  77         xptr cur, *node = (xptr *) ptr;
  78
  79         xlock_acquire(&heap->lock, 2);
  80
  81         cur = *(volatile xptr *)list;
  82         *node = cur;
  83         *list = abs_ptr;
  84         //printf("cur: %llu, next: %llu\n", cur, abs_ptr);
  85         //printf("next points to %llu\n", *(xptr *) ptr);
  86
  87         xlock_release(&heap->lock);
  88 }
  89
  90 void xheap_free(void *ptr)
  91 {
  92         struct xheap_header *h = __get_header(ptr);
  93         struct xheap *heap = XPTR(&h->heap);
  94         void *mem = XPTR(&heap->mem);
  95         uint64_t size = xheap_get_chunk_size(ptr);
  96         xptr *free_list = (xptr *) mem;
  97         int r = __get_index(heap, size);
  98         //printf("size: %llu, r: %d\n", size, r);
  99         __add_in_free_list(heap, &free_list[r], ptr);
 100 //      printf("freed %lx (size: %llu)\n", ptr, __get_header(ptr)->size);
 101         return;
 102 }
 103
 104 int xheap_init(struct xheap *heap, uint64_t size, uint32_t alignment_unit, void *mem)
 105 {
 106         //int r = (sizeof(size)*8 - __builtin_clzl(size));
 107         int r, i;
 108         void *al_mem = (void *) __align((unsigned long)mem, alignment_unit);
 109         uint64_t diff = (uint64_t) ((unsigned long)al_mem - (unsigned long)mem);
 110         uint64_t heap_page = 1 << alignment_unit;
 111         xptr * free_list;
 112
 113         heap->cur = diff;
 114         heap->size = size;
 115         heap->alignment_unit = alignment_unit;
 116         XPTRSET(&heap->mem, mem);
 117
 118         r = __get_index(heap, size);
 119
 120         /* minimum alignment unit required */
 121         if (heap_page < sizeof(struct xheap_header))
 122                 return -1;
 123         //if (heap_page < sizeof(xptr *) * r)
 124         //      return -1;
 125
 126         /* make sure unused space in heap start can hold a header*/
 127         if (heap->cur < sizeof(struct xheap_header)) {
 128                 heap->cur += heap_page;
 129         }
 130         heap->cur -= sizeof(struct xheap_header);
 131
 132         /* make sure there is enough unused space in heap start to be
 133          * used as an indexing array
 134          */
 135         while (heap->cur < sizeof(xptr *) * r)
 136                         heap->cur += heap_page;
 137
 138         /* clean up index array */
 139         free_list = (xptr *) mem;
 140         for (i = 0; i < r; i++) {
 141                 free_list[i] = 0;
 142         }
 143
 144         /* make sure there is at least one "heap_page" to allocate */
 145         if (heap->cur >= size - heap_page)
 146                 return -1;
 147         xlock_release(&heap->lock);
 148
 149         return 0;
 150 }