src/pool.c

   1 #include "pool.h"
   2 #ifndef GIT_WIN32
   3 #include <unistd.h>
   4 #endif
   5
   6 struct git_pool_page {
   7         git_pool_page *next;
   8         uint32_t size;
   9         uint32_t avail;
  10         char data[GIT_FLEX_ARRAY];
  11 };
  12
  13 struct pool_freelist {
  14         struct pool_freelist *next;
  15 };
  16
  17 #define GIT_POOL_MIN_USABLE     4
  18 #define GIT_POOL_MIN_PAGESZ     2 * sizeof(void*)
  19
  20 static void *pool_alloc_page(git_pool *pool, uint32_t size);
  21 static void pool_insert_page(git_pool *pool, git_pool_page *page);
  22
  23 int git_pool_init(
  24         git_pool *pool, uint32_t item_size, uint32_t items_per_page)
  25 {
  26         assert(pool);
  27
  28         if (!item_size)
  29                 item_size = 1;
  30         /* round up item_size for decent object alignment */
  31         if (item_size > 4)
  32                 item_size = (item_size + 7) & ~7;
  33         else if (item_size == 3)
  34                 item_size = 4;
  35
  36         if (!items_per_page)
  37                 items_per_page = git_pool__suggest_items_per_page(item_size);
  38         if (item_size * items_per_page < GIT_POOL_MIN_PAGESZ)
  39                 items_per_page = (GIT_POOL_MIN_PAGESZ + item_size - 1) / item_size;
  40
  41         memset(pool, 0, sizeof(git_pool));
  42         pool->item_size = item_size;
  43         pool->page_size = item_size * items_per_page;
  44
  45         return 0;
  46 }
  47
  48 void git_pool_clear(git_pool *pool)
  49 {
  50         git_pool_page *scan, *next;
  51
  52         for (scan = pool->open; scan != NULL; scan = next) {
  53                 next = scan->next;
  54                 git__free(scan);
  55         }
  56         pool->open = NULL;
  57
  58         for (scan = pool->full; scan != NULL; scan = next) {
  59                 next = scan->next;
  60                 git__free(scan);
  61         }
  62         pool->full = NULL;
  63
  64         pool->free_list = NULL;
  65
  66         pool->items = 0;
  67
  68         pool->has_string_alloc     = 0;
  69         pool->has_multi_item_alloc = 0;
  70         pool->has_large_page_alloc = 0;
  71 }
  72
  73 void git_pool_swap(git_pool *a, git_pool *b)
  74 {
  75         git_pool temp;
  76
  77         if (a == b)
  78                 return;
  79
  80         memcpy(&temp, a, sizeof(temp));
  81         memcpy(a, b, sizeof(temp));
  82         memcpy(b, &temp, sizeof(temp));
  83 }
  84
  85 static void pool_insert_page(git_pool *pool, git_pool_page *page)
  86 {
  87         git_pool_page *scan;
  88
  89         /* If there are no open pages or this page has the most open space,
  90          * insert it at the beginning of the list.  This is the common case.
  91          */
  92         if (pool->open == NULL || pool->open->avail < page->avail) {
  93                 page->next = pool->open;
  94                 pool->open = page;
  95                 return;
  96         }
  97
  98         /* Otherwise insert into sorted position. */
  99         for (scan = pool->open;
 100                  scan->next && scan->next->avail > page->avail;
 101                  scan = scan->next);
 102         page->next = scan->next;
 103         scan->next = page;
 104 }
 105
 106 static void *pool_alloc_page(git_pool *pool, uint32_t size)
 107 {
 108         git_pool_page *page;
 109         uint32_t alloc_size;
 110
 111         if (size <= pool->page_size)
 112                 alloc_size = pool->page_size;
 113         else {
 114                 alloc_size = size;
 115                 pool->has_large_page_alloc = 1;
 116         }
 117
 118         page = git__calloc(1, alloc_size + sizeof(git_pool_page));
 119         if (!page)
 120                 return NULL;
 121
 122         page->size  = alloc_size;
 123         page->avail = alloc_size - size;
 124
 125         if (page->avail > 0)
 126                 pool_insert_page(pool, page);
 127         else {
 128                 page->next = pool->full;
 129                 pool->full = page;
 130         }
 131
 132         pool->items++;
 133
 134         return page->data;
 135 }
 136
 137 GIT_INLINE(void) pool_remove_page(
 138         git_pool *pool, git_pool_page *page, git_pool_page *prev)
 139 {
 140         if (prev == NULL)
 141                 pool->open = page->next;
 142         else
 143                 prev->next = page->next;
 144 }
 145
 146 void *git_pool_malloc(git_pool *pool, uint32_t items)
 147 {
 148         git_pool_page *scan = pool->open, *prev;
 149         uint32_t size = items * pool->item_size;
 150         void *ptr = NULL;
 151
 152         pool->has_string_alloc = 0;
 153         if (items > 1)
 154                 pool->has_multi_item_alloc = 1;
 155         else if (pool->free_list != NULL) {
 156                 ptr = pool->free_list;
 157                 pool->free_list = ((struct pool_freelist *)pool->free_list)->next;
 158                 return ptr;
 159         }
 160
 161         /* just add a block if there is no open one to accomodate this */
 162         if (size >= pool->page_size || !scan || scan->avail < size)
 163                 return pool_alloc_page(pool, size);
 164
 165         pool->items++;
 166
 167         /* find smallest block in free list with space */
 168         for (scan = pool->open, prev = NULL;
 169                  scan->next && scan->next->avail >= size;
 170                  prev = scan, scan = scan->next);
 171
 172         /* allocate space from the block */
 173         ptr = &scan->data[scan->size - scan->avail];
 174         scan->avail -= size;
 175
 176         /* move to full list if there is almost no space left */
 177         if (scan->avail < pool->item_size || scan->avail < GIT_POOL_MIN_USABLE) {
 178                 pool_remove_page(pool, scan, prev);
 179                 scan->next = pool->full;
 180                 pool->full = scan;
 181         }
 182         /* reorder list if block is now smaller than the one after it */
 183         else if (scan->next != NULL && scan->next->avail > scan->avail) {
 184                 pool_remove_page(pool, scan, prev);
 185                 pool_insert_page(pool, scan);
 186         }
 187
 188         return ptr;
 189 }
 190
 191 char *git_pool_strndup(git_pool *pool, const char *str, size_t n)
 192 {
 193         void *ptr = NULL;
 194
 195         assert(pool && str && pool->item_size == sizeof(char));
 196
 197         if (n + 1 == 0) {
 198                 giterr_set_oom();
 199                 return NULL;
 200         }
 201
 202         if ((ptr = git_pool_malloc(pool, (uint32_t)(n + 1))) != NULL) {
 203                 memcpy(ptr, str, n);
 204                 *(((char *)ptr) + n) = '\0';
 205         }
 206         pool->has_string_alloc = 1;
 207
 208         return ptr;
 209 }
 210
 211 char *git_pool_strdup(git_pool *pool, const char *str)
 212 {
 213         assert(pool && str && pool->item_size == sizeof(char));
 214
 215         return git_pool_strndup(pool, str, strlen(str));
 216 }
 217
 218 char *git_pool_strdup_safe(git_pool *pool, const char *str)
 219 {
 220         return str ? git_pool_strdup(pool, str) : NULL;
 221 }
 222
 223 char *git_pool_strcat(git_pool *pool, const char *a, const char *b)
 224 {
 225         void *ptr;
 226         size_t len_a, len_b;
 227
 228         assert(pool && a && b && pool->item_size == sizeof(char));
 229
 230         len_a = a ? strlen(a) : 0;
 231         len_b = b ? strlen(b) : 0;
 232
 233         if ((ptr = git_pool_malloc(pool, (uint32_t)(len_a + len_b + 1))) != NULL) {
 234                 if (len_a)
 235                         memcpy(ptr, a, len_a);
 236                 if (len_b)
 237                         memcpy(((char *)ptr) + len_a, b, len_b);
 238                 *(((char *)ptr) + len_a + len_b) = '\0';
 239         }
 240         pool->has_string_alloc = 1;
 241
 242         return ptr;
 243 }
 244
 245 void git_pool_free(git_pool *pool, void *ptr)
 246 {
 247         struct pool_freelist *item = ptr;
 248
 249         assert(pool && pool->item_size >= sizeof(void*));
 250
 251         if (item) {
 252                 item->next = pool->free_list;
 253                 pool->free_list = item;
 254         }
 255 }
 256
 257 void git_pool_free_array(git_pool *pool, size_t count, void **ptrs)
 258 {
 259         struct pool_freelist **items = (struct pool_freelist **)ptrs;
 260         size_t i;
 261
 262         assert(pool && ptrs && pool->item_size >= sizeof(void*));
 263
 264         if (!count)
 265                 return;
 266
 267         for (i = count - 1; i > 0; --i)
 268                 items[i]->next = items[i - 1];
 269
 270         items[i]->next  = pool->free_list;
 271         pool->free_list = items[count - 1];
 272 }
 273
 274 uint32_t git_pool__open_pages(git_pool *pool)
 275 {
 276         uint32_t ct = 0;
 277         git_pool_page *scan;
 278         for (scan = pool->open; scan != NULL; scan = scan->next) ct++;
 279         return ct;
 280 }
 281
 282 uint32_t git_pool__full_pages(git_pool *pool)
 283 {
 284         uint32_t ct = 0;
 285         git_pool_page *scan;
 286         for (scan = pool->full; scan != NULL; scan = scan->next) ct++;
 287         return ct;
 288 }
 289
 290 bool git_pool__ptr_in_pool(git_pool *pool, void *ptr)
 291 {
 292         git_pool_page *scan;
 293         for (scan = pool->open; scan != NULL; scan = scan->next)
 294                 if ((void *)scan->data <= ptr &&
 295                         (void *)(((char *)scan->data) + scan->size) > ptr)
 296                         return true;
 297         for (scan = pool->full; scan != NULL; scan = scan->next)
 298                 if ((void *)scan->data <= ptr &&
 299                         (void *)(((char *)scan->data) + scan->size) > ptr)
 300                         return true;
 301         return false;
 302 }
 303
 304 uint32_t git_pool__system_page_size(void)
 305 {
 306         static uint32_t size = 0;
 307
 308         if (!size) {
 309 #ifdef GIT_WIN32
 310                 SYSTEM_INFO info;
 311                 GetSystemInfo(&info);
 312                 size = (uint32_t)info.dwPageSize;
 313 #elif defined(__amigaos4__)
 314                 size = (uint32_t)4096; /* 4K as there is no global value we can query */
 315 #else
 316                 size = (uint32_t)sysconf(_SC_PAGE_SIZE);
 317 #endif
 318
 319                 size -= 2 * sizeof(void *); /* allow space for malloc overhead */
 320         }
 321
 322         return size;
 323 }
 324
 325 uint32_t git_pool__suggest_items_per_page(uint32_t item_size)
 326 {
 327         uint32_t page_bytes =
 328                 git_pool__system_page_size() - sizeof(git_pool_page);
 329         return page_bytes / item_size;
 330 }
 331