lib/pool_alloc.c

   1 #include "rsync.h"
   2
   3 #define POOL_DEF_EXTENT (32 * 1024)
   4
   5 #define POOL_QALIGN_P2          (1<<16)         /* power-of-2 qalign    */
   6
   7 struct alloc_pool
   8 {
   9         size_t                  size;           /* extent size          */
  10         size_t                  quantum;        /* allocation quantum   */
  11         struct pool_extent      *extents;       /* top extent is "live" */
  12         void                    (*bomb)();      /* called if malloc fails */
  13         int                     flags;
  14
  15         /* statistical data */
  16         unsigned long           e_created;      /* extents created      */
  17         unsigned long           e_freed;        /* extents destroyed    */
  18         int64                   n_allocated;    /* calls to alloc       */
  19         int64                   n_freed;        /* calls to free        */
  20         int64                   b_allocated;    /* cum. bytes allocated */
  21         int64                   b_freed;        /* cum. bytes freed     */
  22 };
  23
  24 struct pool_extent
  25 {
  26         struct pool_extent      *next;
  27         void                    *start;         /* starting address     */
  28         size_t                  free;           /* free bytecount       */
  29         size_t                  bound;          /* trapped free bytes   */
  30 };
  31
  32 struct align_test {
  33         uchar foo;
  34         union {
  35             int64 i;
  36             void *p;
  37         } bar;
  38 };
  39
  40 #define MINALIGN        offsetof(struct align_test, bar)
  41
  42 /* Temporarily cast a void* var into a char* var when adding an offset (to
  43  * keep some compilers from complaining about the pointer arithmetic). */
  44 #define PTR_ADD(b,o)    ( (void*) ((char*)(b) + (o)) )
  45
  46 alloc_pool_t
  47 pool_create(size_t size, size_t quantum, void (*bomb)(const char*, const char*, int), int flags)
  48 {
  49         struct alloc_pool *pool;
  50
  51         if ((MINALIGN & (MINALIGN - 1)) != (0)) {
  52                 if (bomb)
  53                         (*bomb)("Compiler error: MINALIGN is not a power of 2", __FILE__, __LINE__);
  54                 return NULL;
  55         }
  56
  57         if (!(pool = new0(struct alloc_pool)))
  58                 return NULL;
  59
  60         if (!size)
  61                 size = POOL_DEF_EXTENT;
  62         if (!quantum)
  63                 quantum = MINALIGN;
  64
  65         if (flags & POOL_INTERN) {
  66                 if (size <= sizeof (struct pool_extent))
  67                         size = quantum;
  68                 else
  69                         size -= sizeof (struct pool_extent);
  70                 flags |= POOL_PREPEND;
  71         }
  72
  73         if (quantum <= 1)
  74                 flags = (flags | POOL_NO_QALIGN) & ~POOL_QALIGN_P2;
  75         else if (!(flags & POOL_NO_QALIGN)) {
  76                 if (size % quantum)
  77                         size += quantum - size % quantum;
  78                 /* If quantum is a power of 2, we'll avoid using modulus. */
  79                 if (!(quantum & (quantum - 1)))
  80                         flags |= POOL_QALIGN_P2;
  81         }
  82
  83         pool->size = size;
  84         pool->quantum = quantum;
  85         pool->bomb = bomb;
  86         pool->flags = flags;
  87
  88         return pool;
  89 }
  90
  91 void
  92 pool_destroy(alloc_pool_t p)
  93 {
  94         struct alloc_pool *pool = (struct alloc_pool *) p;
  95         struct pool_extent *cur, *next;
  96
  97         if (!pool)
  98                 return;
  99
 100         for (cur = pool->extents; cur; cur = next) {
 101                 next = cur->next;
 102                 if (pool->flags & POOL_PREPEND)
 103                         free(PTR_ADD(cur->start, -sizeof (struct pool_extent)));
 104                 else {
 105                         free(cur->start);
 106                         free(cur);
 107                 }
 108         }
 109
 110         free(pool);
 111 }
 112
 113 void *
 114 pool_alloc(alloc_pool_t p, size_t len, const char *bomb_msg)
 115 {
 116         struct alloc_pool *pool = (struct alloc_pool *) p;
 117         if (!pool)
 118                 return NULL;
 119
 120         if (!len)
 121                 len = pool->quantum;
 122         else if (pool->flags & POOL_QALIGN_P2) {
 123                 if (len & (pool->quantum - 1))
 124                         len += pool->quantum - (len & (pool->quantum - 1));
 125         } else if (!(pool->flags & POOL_NO_QALIGN)) {
 126                 if (len % pool->quantum)
 127                         len += pool->quantum - len % pool->quantum;
 128         }
 129
 130         if (len > pool->size)
 131                 goto bomb_out;
 132
 133         if (!pool->extents || len > pool->extents->free) {
 134                 void *start;
 135                 size_t asize;
 136                 struct pool_extent *ext;
 137
 138                 asize = pool->size;
 139                 if (pool->flags & POOL_PREPEND)
 140                         asize += sizeof (struct pool_extent);
 141
 142                 if (!(start = new_array(char, asize)))
 143                         goto bomb_out;
 144
 145                 if (pool->flags & POOL_CLEAR)
 146                         memset(start, 0, asize);
 147
 148                 if (pool->flags & POOL_PREPEND) {
 149                         ext = start;
 150                         start = PTR_ADD(start, sizeof (struct pool_extent));
 151                 } else if (!(ext = new(struct pool_extent)))
 152                         goto bomb_out;
 153                 ext->start = start;
 154                 ext->free = pool->size;
 155                 ext->bound = 0;
 156                 ext->next = pool->extents;
 157                 pool->extents = ext;
 158
 159                 pool->e_created++;
 160         }
 161
 162         pool->n_allocated++;
 163         pool->b_allocated += len;
 164
 165         pool->extents->free -= len;
 166
 167         return PTR_ADD(pool->extents->start, pool->extents->free);
 168
 169   bomb_out:
 170         if (pool->bomb)
 171                 (*pool->bomb)(bomb_msg, __FILE__, __LINE__);
 172         return NULL;
 173 }
 174
 175 /* This function allows you to declare memory in the pool that you are done
 176  * using.  If you free all the memory in a pool's extent, that extent will
 177  * be freed. */
 178 void
 179 pool_free(alloc_pool_t p, size_t len, void *addr)
 180 {
 181         struct alloc_pool *pool = (struct alloc_pool *)p;
 182         struct pool_extent *cur, *prev;
 183
 184         if (!pool)
 185                 return;
 186
 187         if (!addr) {
 188                 /* A NULL addr starts a fresh extent for new allocations. */
 189                 if ((cur = pool->extents) != NULL && cur->free != pool->size) {
 190                         cur->bound += cur->free;
 191                         cur->free = 0;
 192                 }
 193                 return;
 194         }
 195
 196         if (!len)
 197                 len = pool->quantum;
 198         else if (pool->flags & POOL_QALIGN_P2) {
 199                 if (len & (pool->quantum - 1))
 200                         len += pool->quantum - (len & (pool->quantum - 1));
 201         } else if (!(pool->flags & POOL_NO_QALIGN)) {
 202                 if (len % pool->quantum)
 203                         len += pool->quantum - len % pool->quantum;
 204         }
 205
 206         pool->n_freed++;
 207         pool->b_freed += len;
 208
 209         for (prev = NULL, cur = pool->extents; cur; prev = cur, cur = cur->next) {
 210                 if (addr >= cur->start
 211                     && addr < PTR_ADD(cur->start, pool->size))
 212                         break;
 213         }
 214         if (!cur)
 215                 return;
 216
 217         if (!prev) {
 218                 /* The "live" extent is kept ready for more allocations. */
 219                 if (cur->free + cur->bound + len >= pool->size) {
 220                         if (pool->flags & POOL_CLEAR) {
 221                                 memset(PTR_ADD(cur->start, cur->free), 0,
 222                                        pool->size - cur->free);
 223                         }
 224                         cur->free = pool->size;
 225                         cur->bound = 0;
 226                 } else if (addr == PTR_ADD(cur->start, cur->free)) {
 227                         if (pool->flags & POOL_CLEAR)
 228                                 memset(addr, 0, len);
 229                         cur->free += len;
 230                 } else
 231                         cur->bound += len;
 232         } else {
 233                 cur->bound += len;
 234
 235                 if (cur->free + cur->bound >= pool->size) {
 236                         prev->next = cur->next;
 237                         if (pool->flags & POOL_PREPEND)
 238                                 free(PTR_ADD(cur->start, -sizeof (struct pool_extent)));
 239                         else {
 240                                 free(cur->start);
 241                                 free(cur);
 242                         }
 243                         pool->e_freed++;
 244                 } else if (prev != pool->extents) {
 245                         /* Move the extent to be the first non-live extent. */
 246                         prev->next = cur->next;
 247                         cur->next = pool->extents->next;
 248                         pool->extents->next = cur;
 249                 }
 250         }
 251 }
 252
 253 /* This allows you to declare that the given address marks the edge of some
 254  * pool memory that is no longer needed.  Any extents that hold only data
 255  * older than the boundary address are freed.  NOTE: You MUST NOT USE BOTH
 256  * pool_free() and pool_free_old() on the same pool!! */
 257 void
 258 pool_free_old(alloc_pool_t p, void *addr)
 259 {
 260         struct alloc_pool *pool = (struct alloc_pool *)p;
 261         struct pool_extent *cur, *prev, *next;
 262
 263         if (!pool || !addr)
 264                 return;
 265
 266         for (prev = NULL, cur = pool->extents; cur; prev = cur, cur = cur->next) {
 267                 if (addr >= cur->start
 268                     && addr < PTR_ADD(cur->start, pool->size))
 269                         break;
 270         }
 271         if (!cur)
 272                 return;
 273
 274         if (addr == PTR_ADD(cur->start, cur->free)) {
 275                 if (prev) {
 276                         prev->next = NULL;
 277                         next = cur;
 278                 } else {
 279                         /* The most recent live extent can just be reset. */
 280                         if (pool->flags & POOL_CLEAR)
 281                                 memset(addr, 0, pool->size - cur->free);
 282                         cur->free = pool->size;
 283                         cur->bound = 0;
 284                         next = cur->next;
 285                         cur->next = NULL;
 286                 }
 287         } else {
 288                 next = cur->next;
 289                 cur->next = NULL;
 290         }
 291
 292         while ((cur = next) != NULL) {
 293                 next = cur->next;
 294                 if (pool->flags & POOL_PREPEND)
 295                         free(PTR_ADD(cur->start, -sizeof (struct pool_extent)));
 296                 else {
 297                         free(cur->start);
 298                         free(cur);
 299                 }
 300                 pool->e_freed++;
 301         }
 302 }
 303
 304 /* If the current extent doesn't have "len" free space in it, mark it as full
 305  * so that the next alloc will start a new extent.  If len is (size_t)-1, this
 306  * bump will always occur.  The function returns a boundary address that can
 307  * be used with pool_free_old(), or a NULL if no memory is allocated. */
 308 void *
 309 pool_boundary(alloc_pool_t p, size_t len)
 310 {
 311         struct alloc_pool *pool = (struct alloc_pool *)p;
 312         struct pool_extent *cur;
 313
 314         if (!pool || !pool->extents)
 315                 return NULL;
 316
 317         cur = pool->extents;
 318
 319         if (cur->free < len) {
 320                 cur->bound += cur->free;
 321                 cur->free = 0;
 322         }
 323
 324         return PTR_ADD(cur->start, cur->free);
 325 }
 326
 327 #define FDPRINT(label, value) \
 328         do { \
 329                 int len = snprintf(buf, sizeof buf, label, value); \
 330                 if (write(fd, buf, len) != len) \
 331                         ret = -1; \
 332         } while (0)
 333
 334 #define FDEXTSTAT(ext) \
 335         do { \
 336                 int len = snprintf(buf, sizeof buf, "  %12ld  %5ld\n", \
 337                                    (long)ext->free, (long)ext->bound); \
 338                 if (write(fd, buf, len) != len) \
 339                         ret = -1; \
 340         } while (0)
 341
 342 int
 343 pool_stats(alloc_pool_t p, int fd, int summarize)
 344 {
 345         struct alloc_pool *pool = (struct alloc_pool *) p;
 346         struct pool_extent *cur;
 347         char buf[BUFSIZ];
 348         int ret = 0;
 349
 350         if (!pool)
 351                 return ret;
 352
 353         FDPRINT("  Extent size:       %12ld\n", (long)  pool->size);
 354         FDPRINT("  Alloc quantum:     %12ld\n", (long)  pool->quantum);
 355         FDPRINT("  Extents created:   %12ld\n",         pool->e_created);
 356         FDPRINT("  Extents freed:     %12ld\n",         pool->e_freed);
 357         FDPRINT("  Alloc count:       %12.0f\n", (double) pool->n_allocated);
 358         FDPRINT("  Free Count:        %12.0f\n", (double) pool->n_freed);
 359         FDPRINT("  Bytes allocated:   %12.0f\n", (double) pool->b_allocated);
 360         FDPRINT("  Bytes freed:       %12.0f\n", (double) pool->b_freed);
 361
 362         if (summarize)
 363                 return ret;
 364
 365         if (!pool->extents)
 366                 return ret;
 367
 368         if (write(fd, "\n", 1) != 1)
 369                 ret = -1;
 370
 371         for (cur = pool->extents; cur; cur = cur->next)
 372                 FDEXTSTAT(cur);
 373
 374         return ret;
 375 }