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