Added allocation pool code.

diff --git a/lib/pool_alloc.3 b/lib/pool_alloc.3
new file mode 100644 (file)
index 0000000..b9d338b
--- /dev/null
+++ b/lib/pool_alloc.3
@@ -0,0 +1,199 @@
+.ds d \-\^\-
+.ds o \fR[\fP
+.ds c \fR]\fP
+.ds | \fR|\fP
+.de D
+\\.B \*d\\$1
+..
+.de DI
+\\.BI \*d\\$1 \\$2
+..
+.de DR
+\\.BR \*d\\$1 \\$2
+..
+.de Di
+\\.BI \*d\\$1 " \\$2"
+..
+.de Db
+\\.B \*d\\$1 " \\$2"
+..
+.de Df
+\\.B \*d\*ono\*c\\$1
+..
+.de See
+See \fB\\$1\fP for details.
+..
+.de SeeIn
+See \fB\\$1\fP in \fB\\$2\fP for details.
+..
+.TH POOL_ALLOC 3
+.SH NAME
+pool_alloc, pool_free, pool_talloc, pool_tfree, pool_create, pool_destroy
+\- Allocate and free memory in managed allocation pools.
+.SH SYNOPSIS
+.B #include "pool_alloc.h"
+
+\fBstruct alloc_pool *pool_create(size_t \fIsize\fB, size_t \fIquantum\fB, void (*\fIbomb\fB)(char *), int \fIflags\fB);
+
+\fBvoid pool_destroy(struct alloc_pool *\fIpool\fB);
+
+\fBvoid *pool_alloc(struct alloc_pool *\fIpool\fB, size_t \fIsize\fB, char *\fImsg\fB);
+
+\fBvoid pool_free(struct alloc_pool *\fIpool\fB, sise_t \fIsize\fB, void *\fIaddr\fB);
+
+\fBvoid *pool_talloc(struct alloc_pool *\fIpool\fB, \fItype\fB), int \fIcount\fB, char *\fImsg\fB);
+
+\fBvoid pool_tfree(struct alloc_pool *\fIpool\fB, \fItype\fB, int \fIcount\fB, void *\fIaddr\fB);
+.SH DESCRIPTION
+.P
+The pool allocation routines use
+.B malloc()
+for underlying memory management.
+What allocation pools do is cause
+memory within a given pool to be in large contigious blocks
+(called extents) that when freed will be reusable.  Unlike
+.B malloc()
+the allocations are not managed individually.
+Instead each extent tracks the total free memory within the
+extent.  Each extent can either be used to allocate memory
+or to manage the freeing of memory within that extent.
+When an extent has less free memory than a given
+allocation request or when the first request to free
+memory within that extent is received the extent ceases to
+be used for allocation.
+.P
+This form of memory management is suited to large numbers of small
+related allocations that are held for a while
+and then freed as a group.
+Because the
+underlying allocations are done in large contigious extents
+when an extent is freed it releases a large enough
+contigious block of memory to be useful to subsequent
+.B malloc()
+and
+.B pool_alloc()
+calls even if allocations from other pools or from
+.B malloc()
+are made between allocations from a given pool.
+.P
+.B pool_create()
+Creates an allocation pool for subsequent calls to the pool
+allocation functions.
+When an extent is created for allocations it will be
+.I size 
+bytes.
+Allocations from the pool have their sizes rounded up to a
+multiple of
+.I quantum
+bytes in length.
+Specifying
+.B 0
+for
+.I quantum
+Will produce a quantum that should meet maximal allignment
+on most platforms.
+If the
+.B POOL_QALIGN
+.I flag
+is set allocations will be aligned to addresses that are a
+multiple of
+.IR quantum .
+If the
+.B POOL_CLEAR
+.I flag
+is set all allocations from the pool will be zero filled.
+.P
+.B pool_destroy()
+destroys an allocation pool and frees all memory allocated
+in that pool.
+.P
+.B pool_alloc()
+allocates
+.I size
+bytes from the specified
+.IR pool .
+If
+.I size
+is
+.B 0
+.I quantum
+bytes will be freed.
+If the requested memory cannot be allocated
+.B pool_alloc()
+will call
+.I bomb()
+function, if defined, with
+.I msg
+as it's sole argument and
+.B NULL
+will be returned.
+.P
+.B pool_free()
+frees
+.I size
+bytes pointed to by
+.I addr
+previously allocated in the specified
+.IR pool .
+The memory freed within an extent will not be reusable until
+all of the memory in that extent has been freed but 
+depending on the order in which the
+allocations are freed some extents may be released for reuse
+while others are still in use.
+If
+.I size
+is
+.B 0
+.I quantum
+bytes will be freed.
+If
+.I addr
+is
+.B 0
+no memory will be freed but subsequent allocations will come
+from a new extent.
+.P
+.B pool_talloc()
+is a macro that take a
+.I type
+and
+.I count
+instead of
+.I size
+and will cast the return value to the correct type.
+.P
+.B pool_tfree
+is a macro to free memory previously allocated in the
+specified
+.IR pool .
+.SH RETURN VALUE
+.B pool_create()
+returns a pointer to
+.BR "struct alloc_pool" .
+.P
+.B pool_alloc()
+and
+.B pool_talloc()
+return pointers to the allocated memory,
+or NULL if the request fails.
+For each extent so long as no allocations are smaller than varaible
+allignment requirements this pointer will be suitably
+alligned for any kind of variable.
+The return type of
+.B pool_alloc()
+will normally require casting to the desired type but
+.B pool_talloc()
+will returns a pointer of the requested
+.IR type .
+.P
+.BR pool_free() ,
+.B pool_tfree()
+and
+.B pool_destroy()
+return no value.
+.SH SEE ALSO
+.nf
+malloc(3)
+.SH AUTHOR
+pool_alloc was created by J.W. Schultz of Pegasystems Technologies.
+.SH BUGS AND ISSUES

diff --git a/lib/pool_alloc.c b/lib/pool_alloc.c
new file mode 100644 (file)
index 0000000..acb356a
--- /dev/null
+++ b/lib/pool_alloc.c
@@ -0,0 +1,297 @@
+#include "rsync.h"
+
+#define POOL_DEF_EXTENT        (32 * 1024)
+
+struct alloc_pool
+{
+       size_t                  size;           /* extent size          */
+       size_t                  quantum;        /* allocation quantum   */
+       struct pool_extent      *live;          /* current extent for
+                                                * allocations          */
+       struct pool_extent      *free;          /* unfreed extent list  */
+       void                    (*bomb)();
+                                               /* function to call if
+                                                * malloc fails         */
+       int                     flags;
+
+       /* statistical data */
+       unsigned long           e_created;      /* extents created      */
+       unsigned long           e_freed;        /* extents detroyed     */
+       uint64                  n_allocated;    /* calls to alloc       */
+       uint64                  n_freed;        /* calls to free        */
+       uint64                  b_allocated;    /* cum. bytes allocated */
+       uint64                  b_freed;        /* cum. bytes freed     */
+};
+
+struct pool_extent
+{
+       void                    *start;         /* starting address     */
+       size_t                  free;           /* free bytecount       */
+       size_t                  bound;          /* bytes bound by padding,
+                                                * overhead and freed   */
+       struct pool_extent      *next;
+};
+
+#define MINALIGN       (sizeof (void *))
+
+alloc_pool_t
+pool_create(size_t size, size_t quantum,
+    void (*bomb)(char *), int flags)
+{
+       struct alloc_pool       *pool;
+
+       if (!(pool = (struct alloc_pool*) malloc(sizeof (struct alloc_pool))))
+               return pool;
+       memset(pool, 0, sizeof (struct alloc_pool));
+
+       pool->size = size       /* round extent size to min alignment reqs */
+           ? (size + MINALIGN - 1) & ~(MINALIGN - 1)
+           : POOL_DEF_EXTENT;
+       if (pool->flags & POOL_INTERN)
+       {
+               pool->size -= sizeof (struct pool_extent);
+               flags |= POOL_APPEND;
+       }
+       pool->quantum = quantum ? quantum : MINALIGN;
+       pool->bomb = bomb;
+       pool->flags = flags;
+
+       return pool;
+}
+
+void
+pool_destroy(alloc_pool_t p)
+{
+       struct alloc_pool *pool = (struct alloc_pool *) p;
+       struct pool_extent      *cur, *next;
+
+       if (!pool)
+               return;
+
+       if (pool->live)
+       {
+               cur = pool->live;
+               free(cur->start);
+               if (!(pool->flags & POOL_APPEND))
+                       free(cur);
+       }
+       for (cur = pool->free; cur; cur = next)
+       {
+               next = cur->next;
+               free(cur->start);
+               if (!(pool->flags & POOL_APPEND))
+                       free(cur);
+       }
+       free(pool);
+}
+
+void *pool_alloc(alloc_pool_t p, size_t len, char *bomb)
+{
+       struct alloc_pool *pool = (struct alloc_pool *) p;
+       if (!pool)
+               return NULL;
+
+       if (!len)
+               len = pool->quantum;
+       else if (pool->quantum > 1 && len % pool->quantum)
+               len += pool->quantum - len % pool->quantum;
+
+       if (len > pool->size)
+               goto bomb;
+
+       if (!pool->live || len > pool->live->free)
+       {
+               void    *start;
+               size_t  free;
+               size_t  bound;
+               size_t  sqew;
+               size_t  asize;
+
+               if (pool->live)
+               {
+                       pool->live->next = pool->free;
+                       pool->free = pool->live;
+               }
+
+               free = pool->size;
+               bound = 0;
+
+               asize = pool->size;
+               if (pool->flags & POOL_APPEND)
+                       asize += sizeof (struct pool_extent);
+
+               if (!(start = (void *) malloc(asize)))
+                       goto bomb;
+
+               if (pool->flags & POOL_CLEAR)
+                       memset(start, 0, pool->size);
+
+               if (pool->flags & POOL_APPEND)
+               {
+                       pool->live = start + free;
+               }
+               else if (!(pool->live = (struct pool_extent *) malloc(sizeof (struct pool_extent))))
+               {
+                       goto bomb;
+               }
+               if (pool->flags & POOL_QALIGN && pool->quantum > 1
+                   && (sqew = (size_t)(start + free) % pool->quantum))
+               {
+                       bound  += sqew;
+                       free -= sqew;
+               }
+               pool->live->start = start;
+               pool->live->free = free;
+               pool->live->bound = bound;
+               pool->live->next = NULL;
+
+               pool->e_created++;
+       }
+
+       pool->n_allocated++;
+       pool->b_allocated += len;
+
+       pool->live->free -= len;
+
+       return pool->live->start + pool->live->free;
+
+bomb:
+       if (pool->bomb)
+               (*pool->bomb)(bomb);
+       return NULL;
+}
+
+void
+pool_free(alloc_pool_t p, size_t len, void *addr)
+{
+       struct alloc_pool *pool = (struct alloc_pool *) p;
+       struct pool_extent      *cur;
+       struct pool_extent      *prev;
+
+       if (!pool)
+               return;
+
+       if (!len)
+               len = pool->quantum;
+       else if (pool->quantum > 1 && len % pool->quantum)
+               len += pool->quantum - len % pool->quantum;
+
+       if (!addr && pool->live)
+       {
+               pool->live->next = pool->free;
+               pool->free = pool->live;
+               pool->live = NULL;
+               return;
+       }
+       pool->n_freed++;
+       pool->b_freed += len;
+
+       cur = pool->live;
+       if (cur
+           && addr >= cur->start
+           && addr < cur->start + pool->size)
+       {
+               if (addr == cur->start + cur->free)
+               {
+                       if (pool->flags & POOL_CLEAR)
+                               memset(addr, 0, len);
+                       pool->b_freed += len;
+               } else {
+                       cur->bound += len;
+               }
+               if (cur->free + cur->bound >= pool->size)
+               {
+                       size_t sqew;
+
+                       cur->free = pool->size;
+                       cur->bound = 0;
+                       if (pool->flags & POOL_QALIGN && pool->quantum > 1
+                           && (sqew = (size_t)(cur->start + cur->free) % pool->quantum))
+                       {
+                               cur->bound += sqew;
+                               cur->free -= sqew;
+                       }
+               }
+               return;
+       }
+       for (prev = NULL, cur = pool->free; cur; prev = cur, cur = cur->next)
+       {
+               if (addr >= cur->start
+                   && addr < cur->start + pool->size)
+                       break;
+       }
+       if (!cur)
+               return;
+
+       if (prev)
+       {
+               prev->next = cur->next;
+               cur->next = pool->free;
+               pool->free = cur;
+       }
+       cur->bound += len;
+
+       if (cur->free + cur->bound >= pool->size)
+       {
+               pool->free = cur->next;
+
+               free(cur->start);
+               if (!(pool->flags & POOL_APPEND))
+                       free(cur);
+               pool->e_freed++;
+       }
+       return;
+}
+
+#define FDPRINT(label, value) \
+       snprintf(buf, BUFSIZ, label, value), \
+       write(fd, buf, strlen(buf));
+
+#define FDEXTSTAT(ext) \
+       snprintf(buf, BUFSIZ, "  %12ld  %5ld\n", \
+               (long) ext->free, \
+               (long) ext->bound), \
+       write(fd, buf, strlen(buf))
+
+void
+pool_stats(alloc_pool_t p, int fd, int summarize)
+{
+       struct alloc_pool *pool = (struct alloc_pool *) p;
+       struct pool_extent      *cur;
+       char buf[BUFSIZ];
+
+       if (!pool)
+               return;
+
+       FDPRINT("  Extent size:       %12ld\n", (long)  pool->size);
+       FDPRINT("  Alloc quantum:     %12ld\n", (long)  pool->quantum);
+       FDPRINT("  Extents created:   %12ld\n",         pool->e_created);
+       FDPRINT("  Extents freed:     %12ld\n",         pool->e_freed);
+       FDPRINT("  Alloc count:       %12.0f\n", (double) pool->n_allocated);
+       FDPRINT("  Free Count:        %12.0f\n", (double) pool->n_freed);
+       FDPRINT("  Alloc bytes:       %12.0f\n", (double) pool->b_allocated);
+       FDPRINT("  Free bytes:        %12.0f\n", (double) pool->b_freed);
+
+       if (summarize)
+               return;
+
+       if (!pool->live && !pool->free)
+               return;
+
+       write(fd, "\n", 1);
+
+       if (pool->live)
+       {
+               FDEXTSTAT(pool->live);
+       }
+       strcpy(buf, "   FREE    BOUND\n");
+       write(fd, buf, strlen(buf));
+
+       cur = pool->free;
+       while (cur)
+       {
+               FDEXTSTAT(cur);
+               cur = cur->next;
+       }
+}
+

diff --git a/lib/pool_alloc.h b/lib/pool_alloc.h
new file mode 100644 (file)
index 0000000..a4ab761
--- /dev/null
+++ b/lib/pool_alloc.h
@@ -0,0 +1,20 @@
+#include <stddef.h>
+
+#define POOL_CLEAR     (1<<0)          /* zero fill allocations        */
+#define POOL_QALIGN    (1<<1)          /* align data to quanta         */
+#define POOL_INTERN    (1<<2)          /* Allocate extent structures   */
+#define POOL_APPEND    (1<<3)          /*   or appended to extent data */
+
+typedef void *alloc_pool_t;
+
+alloc_pool_t pool_create(size_t size, size_t quantum, void (*bomb)(char *), int flags);
+void pool_destroy(alloc_pool_t pool);
+void *pool_alloc(alloc_pool_t pool, size_t size, char *bomb);
+void pool_free(alloc_pool_t pool, size_t size, void *addr);
+
+#define pool_talloc(pool, type, count, bomb) \
+       ((type *)pool_alloc(pool, sizeof(type) * count, bomb))
+
+#define pool_tfree(pool, type, count, addr) \
+       (pool_free(pool, sizeof(type) * count, addr))
+