lib/pool_alloc.c

   1 #include "rsync.h"
   2
   3 #define POOL_DEF_EXTENT (32 * 1024)
   4
   5 #define POOL_QALIGN_P2  (1<<16)
   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)();      /* function to call if
  13                                                  * malloc fails         */
  14         int                     flags;
  15
  16         /* statistical data */
  17         unsigned long           e_created;      /* extents created      */
  18         unsigned long           e_freed;        /* extents destroyed    */
  19         int64                   n_allocated;    /* calls to alloc       */
  20         int64                   n_freed;        /* calls to free        */
  21         int64                   b_allocated;    /* cum. bytes allocated */
  22         int64                   b_freed;        /* cum. bytes freed     */
  23 };
  24
  25 struct pool_extent
  26 {
  27         void                    *start;         /* starting address     */
  28         size_t                  free;           /* free bytecount       */
  29         size_t                  bound;          /* trapped free bytes   */
  30         struct pool_extent      *next;
  31 };
  32
  33 struct align_test {
  34         uchar foo;
  35         union {
  36             int64 i;
  37             void *p;
  38         } bar;
  39 };
  40
  41 #define MINALIGN        offsetof(struct align_test, bar)
  42
  43 /* Temporarily cast a void* var into a char* var when adding an offset (to
  44  * keep some compilers from complaining about the pointer arithmetic). */
  45 #define PTR_ADD(b,o)    ( (void*) ((char*)(b) + (o)) )
  46
  47 alloc_pool_t
  48 pool_create(size_t size, size_t quantum, void (*bomb)(const char *), int flags)
  49 {
  50         struct alloc_pool *pool;
  51
  52         if (!(pool = new0(struct alloc_pool)))
  53                 return NULL;
  54
  55         if ((MINALIGN & (MINALIGN - 1)) != 0) {
  56                 if (bomb)
  57                         (*bomb)("Compiler error: MINALIGN is not a power of 2\n");
  58                 return NULL;
  59         }
  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 &= ~(POOL_QALIGN | POOL_QALIGN_P2);
  76         else if (flags & POOL_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(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_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 += 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);
 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 (!len)
 189                 len = pool->quantum;
 190         else if (pool->flags & POOL_QALIGN_P2) {
 191                 if (len & (pool->quantum - 1))
 192                         len += pool->quantum - (len & (pool->quantum - 1));
 193         } else if (pool->flags & POOL_QALIGN) {
 194                 if (len % pool->quantum)
 195                         len += pool->quantum - len % pool->quantum;
 196         }
 197
 198         pool->n_freed++;
 199         pool->b_freed += len;
 200
 201         for (prev = NULL, cur = pool->extents; cur; prev = cur, cur = cur->next) {
 202                 if (addr >= cur->start
 203                     && addr < PTR_ADD(cur->start, pool->size))
 204                         break;
 205         }
 206         if (!cur)
 207                 return;
 208
 209         if (!prev) {
 210                 /* The "live" extent is kept ready for more allocations. */
 211                 if (cur->free + cur->bound + len >= pool->size) {
 212                         if (pool->flags & POOL_CLEAR) {
 213                                 memset(PTR_ADD(cur->start, cur->free), 0,
 214                                        pool->size - cur->free);
 215                         }
 216                         cur->free = pool->size;
 217                         cur->bound = 0;
 218                 } else if (addr == PTR_ADD(cur->start, cur->free)) {
 219                         if (pool->flags & POOL_CLEAR)
 220                                 memset(addr, 0, len);
 221                         cur->free += len;
 222                 } else
 223                         cur->bound += len;
 224         } else {
 225                 cur->bound += len;
 226
 227                 if (cur->free + cur->bound >= pool->size) {
 228                         prev->next = cur->next;
 229                         if (pool->flags & POOL_PREPEND)
 230                                 free(cur->start - sizeof (struct pool_extent));
 231                         else {
 232                                 free(cur->start);
 233                                 free(cur);
 234                         }
 235                         pool->e_freed++;
 236                 } else if (prev != pool->extents) {
 237                         /* Move the extent to be the first non-live extent. */
 238                         prev->next = cur->next;
 239                         cur->next = pool->extents->next;
 240                         pool->extents->next = cur;
 241                 }
 242         }
 243 }
 244
 245 /* This allows you to declare that the given address marks the edge of some
 246  * pool memory that is no longer needed.  Any extents that hold only data
 247  * older than the boundary address are freed.  NOTE: You MUST NOT USE BOTH
 248  * pool_free() and pool_free_old() on the same pool!! */
 249 void
 250 pool_free_old(alloc_pool_t p, void *addr)
 251 {
 252         struct alloc_pool *pool = (struct alloc_pool *)p;
 253         struct pool_extent *cur, *prev, *next;
 254
 255         if (!pool || !addr)
 256                 return;
 257
 258         for (prev = NULL, cur = pool->extents; cur; prev = cur, cur = cur->next) {
 259                 if (addr >= cur->start
 260                     && addr < PTR_ADD(cur->start, pool->size))
 261                         break;
 262         }
 263         if (!cur)
 264                 return;
 265
 266         if (addr == PTR_ADD(cur->start, cur->free)) {
 267                 if (prev) {
 268                         prev->next = NULL;
 269                         next = cur;
 270                 } else {
 271                         /* The most recent live extent can just be reset. */
 272                         if (pool->flags & POOL_CLEAR)
 273                                 memset(addr, 0, pool->size - cur->free);
 274                         cur->free = pool->size;
 275                         cur->bound = 0;
 276                         next = cur->next;
 277                         cur->next = NULL;
 278                 }
 279         } else {
 280                 next = cur->next;
 281                 cur->next = NULL;
 282         }
 283
 284         while ((cur = next) != NULL) {
 285                 next = cur->next;
 286                 if (pool->flags & POOL_PREPEND)
 287                         free(cur->start - sizeof (struct pool_extent));
 288                 else {
 289                         free(cur->start);
 290                         free(cur);
 291                 }
 292                 pool->e_freed++;
 293         }
 294 }
 295
 296 /* If the current extent doesn't have "len" free space in it, mark it as full
 297  * so that the next alloc will start a new extent.  If len is (size_t)-1, this
 298  * bump will always occur.  The function returns a boundary address that can
 299  * be used with pool_free_old(), or a NULL if no memory is allocated. */
 300 void *
 301 pool_boundary(alloc_pool_t p, size_t len)
 302 {
 303         struct alloc_pool *pool = (struct alloc_pool *)p;
 304         struct pool_extent *cur;
 305
 306         if (!pool || !pool->extents)
 307                 return NULL;
 308
 309         cur = pool->extents;
 310
 311         if (cur->free < len) {
 312                 cur->bound += cur->free;
 313                 cur->free = 0;
 314         }
 315
 316         return PTR_ADD(cur->start, cur->free);
 317 }
 318
 319 #define FDPRINT(label, value) \
 320         snprintf(buf, sizeof buf, label, value), \
 321         write(fd, buf, strlen(buf))
 322
 323 #define FDEXTSTAT(ext) \
 324         snprintf(buf, sizeof buf, "  %12ld  %5ld\n", \
 325                 (long) ext->free, \
 326                 (long) ext->bound), \
 327         write(fd, buf, strlen(buf))
 328
 329 void
 330 pool_stats(alloc_pool_t p, int fd, int summarize)
 331 {
 332         struct alloc_pool *pool = (struct alloc_pool *) p;
 333         struct pool_extent *cur;
 334         char buf[BUFSIZ];
 335
 336         if (!pool)
 337                 return;
 338
 339         FDPRINT("  Extent size:       %12ld\n", (long)  pool->size);
 340         FDPRINT("  Alloc quantum:     %12ld\n", (long)  pool->quantum);
 341         FDPRINT("  Extents created:   %12ld\n",         pool->e_created);
 342         FDPRINT("  Extents freed:     %12ld\n",         pool->e_freed);
 343         FDPRINT("  Alloc count:       %12.0f\n", (double) pool->n_allocated);
 344         FDPRINT("  Free Count:        %12.0f\n", (double) pool->n_freed);
 345         FDPRINT("  Bytes allocated:   %12.0f\n", (double) pool->b_allocated);
 346         FDPRINT("  Bytes freed:       %12.0f\n", (double) pool->b_freed);
 347
 348         if (summarize)
 349                 return;
 350
 351         if (!pool->extents)
 352                 return;
 353
 354         write(fd, "\n", 1);
 355
 356         for (cur = pool->extents; cur; cur = cur->next)
 357                 FDEXTSTAT(cur);
 358 }