lib/pool_alloc.c

   1 #include "rsync.h"
   2
   3 #define POOL_DEF_EXTENT (32 * 1024)
   4
   5 struct alloc_pool
   6 {
   7         size_t                  size;           /* extent size          */
   8         size_t                  quantum;        /* allocation quantum   */
   9         struct pool_extent      *live;          /* current extent for
  10                                                  * allocations          */
  11         struct pool_extent      *free;          /* unfreed extent list  */
  12         void                    (*bomb)();
  13                                                 /* function to call if
  14                                                  * malloc fails         */
  15         int                     flags;
  16
  17         /* statistical data */
  18         unsigned long           e_created;      /* extents created      */
  19         unsigned long           e_freed;        /* extents detroyed     */
  20         uint64                  n_allocated;    /* calls to alloc       */
  21         uint64                  n_freed;        /* calls to free        */
  22         uint64                  b_allocated;    /* cum. bytes allocated */
  23         uint64                  b_freed;        /* cum. bytes freed     */
  24 };
  25
  26 struct pool_extent
  27 {
  28         void                    *start;         /* starting address     */
  29         size_t                  free;           /* free bytecount       */
  30         size_t                  bound;          /* bytes bound by padding,
  31                                                  * overhead and freed   */
  32         struct pool_extent      *next;
  33 };
  34
  35 #define MINALIGN        (sizeof (void *))
  36
  37 alloc_pool_t
  38 pool_create(size_t size, size_t quantum,
  39     void (*bomb)(char *), int flags)
  40 {
  41         struct alloc_pool       *pool;
  42
  43         if (!(pool = (struct alloc_pool*) malloc(sizeof (struct alloc_pool))))
  44                 return pool;
  45         memset(pool, 0, sizeof (struct alloc_pool));
  46
  47         pool->size = size       /* round extent size to min alignment reqs */
  48             ? (size + MINALIGN - 1) & ~(MINALIGN - 1)
  49             : POOL_DEF_EXTENT;
  50         if (pool->flags & POOL_INTERN)
  51         {
  52                 pool->size -= sizeof (struct pool_extent);
  53                 flags |= POOL_APPEND;
  54         }
  55         pool->quantum = quantum ? quantum : MINALIGN;
  56         pool->bomb = bomb;
  57         pool->flags = flags;
  58
  59         return pool;
  60 }
  61
  62 void
  63 pool_destroy(alloc_pool_t p)
  64 {
  65         struct alloc_pool *pool = (struct alloc_pool *) p;
  66         struct pool_extent      *cur, *next;
  67
  68         if (!pool)
  69                 return;
  70
  71         if (pool->live)
  72         {
  73                 cur = pool->live;
  74                 free(cur->start);
  75                 if (!(pool->flags & POOL_APPEND))
  76                         free(cur);
  77         }
  78         for (cur = pool->free; cur; cur = next)
  79         {
  80                 next = cur->next;
  81                 free(cur->start);
  82                 if (!(pool->flags & POOL_APPEND))
  83                         free(cur);
  84         }
  85         free(pool);
  86 }
  87
  88 void *
  89 pool_alloc(alloc_pool_t p, size_t len, char *bomb)
  90 {
  91         struct alloc_pool *pool = (struct alloc_pool *) p;
  92         if (!pool)
  93                 return NULL;
  94
  95         if (!len)
  96                 len = pool->quantum;
  97         else if (pool->quantum > 1 && len % pool->quantum)
  98                 len += pool->quantum - len % pool->quantum;
  99
 100         if (len > pool->size)
 101                 goto bomb;
 102
 103         if (!pool->live || len > pool->live->free)
 104         {
 105                 void    *start;
 106                 size_t  free;
 107                 size_t  bound;
 108                 size_t  sqew;
 109                 size_t  asize;
 110
 111                 if (pool->live)
 112                 {
 113                         pool->live->next = pool->free;
 114                         pool->free = pool->live;
 115                 }
 116
 117                 free = pool->size;
 118                 bound = 0;
 119
 120                 asize = pool->size;
 121                 if (pool->flags & POOL_APPEND)
 122                         asize += sizeof (struct pool_extent);
 123
 124                 if (!(start = (void *) malloc(asize)))
 125                         goto bomb;
 126
 127                 if (pool->flags & POOL_CLEAR)
 128                         memset(start, 0, pool->size);
 129
 130                 if (pool->flags & POOL_APPEND)
 131                 {
 132                         pool->live = start + free;
 133                 }
 134                 else if (!(pool->live = (struct pool_extent *) malloc(sizeof (struct pool_extent))))
 135                 {
 136                         goto bomb;
 137                 }
 138                 if (pool->flags & POOL_QALIGN && pool->quantum > 1
 139                     && (sqew = (size_t)(start + free) % pool->quantum))
 140                 {
 141                         bound  += sqew;
 142                         free -= sqew;
 143                 }
 144                 pool->live->start = start;
 145                 pool->live->free = free;
 146                 pool->live->bound = bound;
 147                 pool->live->next = NULL;
 148
 149                 pool->e_created++;
 150         }
 151
 152         pool->n_allocated++;
 153         pool->b_allocated += len;
 154
 155         pool->live->free -= len;
 156
 157         return pool->live->start + pool->live->free;
 158
 159 bomb:
 160         if (pool->bomb)
 161                 (*pool->bomb)(bomb);
 162         return NULL;
 163 }
 164
 165 void
 166 pool_free(alloc_pool_t p, size_t len, void *addr)
 167 {
 168         struct alloc_pool *pool = (struct alloc_pool *) p;
 169         struct pool_extent      *cur;
 170         struct pool_extent      *prev;
 171
 172         if (!pool)
 173                 return;
 174
 175         if (!len)
 176                 len = pool->quantum;
 177         else if (pool->quantum > 1 && len % pool->quantum)
 178                 len += pool->quantum - len % pool->quantum;
 179
 180         if (!addr && pool->live)
 181         {
 182                 pool->live->next = pool->free;
 183                 pool->free = pool->live;
 184                 pool->live = NULL;
 185                 return;
 186         }
 187         pool->n_freed++;
 188         pool->b_freed += len;
 189
 190         cur = pool->live;
 191         if (cur
 192             && addr >= cur->start
 193             && addr < cur->start + pool->size)
 194         {
 195                 if (addr == cur->start + cur->free)
 196                 {
 197                         if (pool->flags & POOL_CLEAR)
 198                                 memset(addr, 0, len);
 199                         pool->b_freed += len;
 200                 } else {
 201                         cur->bound += len;
 202                 }
 203                 if (cur->free + cur->bound >= pool->size)
 204                 {
 205                         size_t sqew;
 206
 207                         cur->free = pool->size;
 208                         cur->bound = 0;
 209                         if (pool->flags & POOL_QALIGN && pool->quantum > 1
 210                             && (sqew = (size_t)(cur->start + cur->free) % pool->quantum))
 211                         {
 212                                 cur->bound += sqew;
 213                                 cur->free -= sqew;
 214                         }
 215                 }
 216                 return;
 217         }
 218         for (prev = NULL, cur = pool->free; cur; prev = cur, cur = cur->next)
 219         {
 220                 if (addr >= cur->start
 221                     && addr < cur->start + pool->size)
 222                         break;
 223         }
 224         if (!cur)
 225                 return;
 226
 227         if (prev)
 228         {
 229                 prev->next = cur->next;
 230                 cur->next = pool->free;
 231                 pool->free = cur;
 232         }
 233         cur->bound += len;
 234
 235         if (cur->free + cur->bound >= pool->size)
 236         {
 237                 pool->free = cur->next;
 238
 239                 free(cur->start);
 240                 if (!(pool->flags & POOL_APPEND))
 241                         free(cur);
 242                 pool->e_freed++;
 243         }
 244         return;
 245 }
 246
 247 #define FDPRINT(label, value) \
 248         snprintf(buf, BUFSIZ, label, value), \
 249         write(fd, buf, strlen(buf));
 250
 251 #define FDEXTSTAT(ext) \
 252         snprintf(buf, BUFSIZ, "  %12ld  %5ld\n", \
 253                 (long) ext->free, \
 254                 (long) ext->bound), \
 255         write(fd, buf, strlen(buf))
 256
 257 void
 258 pool_stats(alloc_pool_t p, int fd, int summarize)
 259 {
 260         struct alloc_pool *pool = (struct alloc_pool *) p;
 261         struct pool_extent      *cur;
 262         char buf[BUFSIZ];
 263
 264         if (!pool)
 265                 return;
 266
 267         FDPRINT("  Extent size:       %12ld\n", (long)  pool->size);
 268         FDPRINT("  Alloc quantum:     %12ld\n", (long)  pool->quantum);
 269         FDPRINT("  Extents created:   %12ld\n",         pool->e_created);
 270         FDPRINT("  Extents freed:     %12ld\n",         pool->e_freed);
 271         FDPRINT("  Alloc count:       %12.0f\n", (double) pool->n_allocated);
 272         FDPRINT("  Free Count:        %12.0f\n", (double) pool->n_freed);
 273         FDPRINT("  Alloc bytes:       %12.0f\n", (double) pool->b_allocated);
 274         FDPRINT("  Free bytes:        %12.0f\n", (double) pool->b_freed);
 275
 276         if (summarize)
 277                 return;
 278
 279         if (!pool->live && !pool->free)
 280                 return;
 281
 282         write(fd, "\n", 1);
 283
 284         if (pool->live)
 285         {
 286                 FDEXTSTAT(pool->live);
 287         }
 288         strcpy(buf, "   FREE    BOUND\n");
 289         write(fd, buf, strlen(buf));
 290
 291         for (cur = pool->free; cur; cur = cur->next)
 292         {
 293                 FDEXTSTAT(cur);
 294         }
 295 }