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 *pool_alloc(alloc_pool_t p, size_t len, char *bomb)
  89 {
  90         struct alloc_pool *pool = (struct alloc_pool *) p;
  91         if (!pool)
  92                 return NULL;
  93
  94         if (!len)
  95                 len = pool->quantum;
  96         else if (pool->quantum > 1 && len % pool->quantum)
  97                 len += pool->quantum - len % pool->quantum;
  98
  99         if (len > pool->size)
 100                 goto bomb;
 101
 102         if (!pool->live || len > pool->live->free)
 103         {
 104                 void    *start;
 105                 size_t  free;
 106                 size_t  bound;
 107                 size_t  sqew;
 108                 size_t  asize;
 109
 110                 if (pool->live)
 111                 {
 112                         pool->live->next = pool->free;
 113                         pool->free = pool->live;
 114                 }
 115
 116                 free = pool->size;
 117                 bound = 0;
 118
 119                 asize = pool->size;
 120                 if (pool->flags & POOL_APPEND)
 121                         asize += sizeof (struct pool_extent);
 122
 123                 if (!(start = (void *) malloc(asize)))
 124                         goto bomb;
 125
 126                 if (pool->flags & POOL_CLEAR)
 127                         memset(start, 0, pool->size);
 128
 129                 if (pool->flags & POOL_APPEND)
 130                 {
 131                         pool->live = start + free;
 132                 }
 133                 else if (!(pool->live = (struct pool_extent *) malloc(sizeof (struct pool_extent))))
 134                 {
 135                         goto bomb;
 136                 }
 137                 if (pool->flags & POOL_QALIGN && pool->quantum > 1
 138                     && (sqew = (size_t)(start + free) % pool->quantum))
 139                 {
 140                         bound  += sqew;
 141                         free -= sqew;
 142                 }
 143                 pool->live->start = start;
 144                 pool->live->free = free;
 145                 pool->live->bound = bound;
 146                 pool->live->next = NULL;
 147
 148                 pool->e_created++;
 149         }
 150
 151         pool->n_allocated++;
 152         pool->b_allocated += len;
 153
 154         pool->live->free -= len;
 155
 156         return pool->live->start + pool->live->free;
 157
 158 bomb:
 159         if (pool->bomb)
 160                 (*pool->bomb)(bomb);
 161         return NULL;
 162 }
 163
 164 void
 165 pool_free(alloc_pool_t p, size_t len, void *addr)
 166 {
 167         struct alloc_pool *pool = (struct alloc_pool *) p;
 168         struct pool_extent      *cur;
 169         struct pool_extent      *prev;
 170
 171         if (!pool)
 172                 return;
 173
 174         if (!len)
 175                 len = pool->quantum;
 176         else if (pool->quantum > 1 && len % pool->quantum)
 177                 len += pool->quantum - len % pool->quantum;
 178
 179         if (!addr && pool->live)
 180         {
 181                 pool->live->next = pool->free;
 182                 pool->free = pool->live;
 183                 pool->live = NULL;
 184                 return;
 185         }
 186         pool->n_freed++;
 187         pool->b_freed += len;
 188
 189         cur = pool->live;
 190         if (cur
 191             && addr >= cur->start
 192             && addr < cur->start + pool->size)
 193         {
 194                 if (addr == cur->start + cur->free)
 195                 {
 196                         if (pool->flags & POOL_CLEAR)
 197                                 memset(addr, 0, len);
 198                         pool->b_freed += len;
 199                 } else {
 200                         cur->bound += len;
 201                 }
 202                 if (cur->free + cur->bound >= pool->size)
 203                 {
 204                         size_t sqew;
 205
 206                         cur->free = pool->size;
 207                         cur->bound = 0;
 208                         if (pool->flags & POOL_QALIGN && pool->quantum > 1
 209                             && (sqew = (size_t)(cur->start + cur->free) % pool->quantum))
 210                         {
 211                                 cur->bound += sqew;
 212                                 cur->free -= sqew;
 213                         }
 214                 }
 215                 return;
 216         }
 217         for (prev = NULL, cur = pool->free; cur; prev = cur, cur = cur->next)
 218         {
 219                 if (addr >= cur->start
 220                     && addr < cur->start + pool->size)
 221                         break;
 222         }
 223         if (!cur)
 224                 return;
 225
 226         if (prev)
 227         {
 228                 prev->next = cur->next;
 229                 cur->next = pool->free;
 230                 pool->free = cur;
 231         }
 232         cur->bound += len;
 233
 234         if (cur->free + cur->bound >= pool->size)
 235         {
 236                 pool->free = cur->next;
 237
 238                 free(cur->start);
 239                 if (!(pool->flags & POOL_APPEND))
 240                         free(cur);
 241                 pool->e_freed++;
 242         }
 243         return;
 244 }
 245
 246 #define FDPRINT(label, value) \
 247         snprintf(buf, BUFSIZ, label, value), \
 248         write(fd, buf, strlen(buf));
 249
 250 #define FDEXTSTAT(ext) \
 251         snprintf(buf, BUFSIZ, "  %12ld  %5ld\n", \
 252                 (long) ext->free, \
 253                 (long) ext->bound), \
 254         write(fd, buf, strlen(buf))
 255
 256 void
 257 pool_stats(alloc_pool_t p, int fd, int summarize)
 258 {
 259         struct alloc_pool *pool = (struct alloc_pool *) p;
 260         struct pool_extent      *cur;
 261         char buf[BUFSIZ];
 262
 263         if (!pool)
 264                 return;
 265
 266         FDPRINT("  Extent size:       %12ld\n", (long)  pool->size);
 267         FDPRINT("  Alloc quantum:     %12ld\n", (long)  pool->quantum);
 268         FDPRINT("  Extents created:   %12ld\n",         pool->e_created);
 269         FDPRINT("  Extents freed:     %12ld\n",         pool->e_freed);
 270         FDPRINT("  Alloc count:       %12.0f\n", (double) pool->n_allocated);
 271         FDPRINT("  Free Count:        %12.0f\n", (double) pool->n_freed);
 272         FDPRINT("  Alloc bytes:       %12.0f\n", (double) pool->b_allocated);
 273         FDPRINT("  Free bytes:        %12.0f\n", (double) pool->b_freed);
 274
 275         if (summarize)
 276                 return;
 277
 278         if (!pool->live && !pool->free)
 279                 return;
 280
 281         write(fd, "\n", 1);
 282
 283         if (pool->live)
 284         {
 285                 FDEXTSTAT(pool->live);
 286         }
 287         strcpy(buf, "   FREE    BOUND\n");
 288         write(fd, buf, strlen(buf));
 289
 290         cur = pool->free;
 291         while (cur)
 292         {
 293                 FDEXTSTAT(cur);
 294                 cur = cur->next;
 295         }
 296 }
 297