Move modules to ccan/ tools to tools/
authorRusty Russell <rusty@vivaldi>
Mon, 2 Jun 2008 02:39:51 +0000 (12:39 +1000)
committerRusty Russell <rusty@vivaldi>
Mon, 2 Jun 2008 02:39:51 +0000 (12:39 +1000)
Requires minor fixups.  "depends" now prefixes ccan/ (allows for
non-ccan deps later).

144 files changed:
Makefile
README
alignof/_info.c [deleted file]
alignof/alignof.h [deleted file]
alignof/test/run.c [deleted file]
alloc/_info.c [deleted file]
alloc/alloc.c [deleted file]
alloc/alloc.h [deleted file]
alloc/test/run.c [deleted file]
build_assert/_info.c [deleted file]
build_assert/build_assert.h [deleted file]
build_assert/test/compile_fail-expr.c [deleted file]
build_assert/test/compile_fail.c [deleted file]
build_assert/test/compile_ok.c [deleted file]
build_assert/test/run-EXPR_BUILD_ASSERT.c [deleted file]
ccan/alignof/_info.c [new file with mode: 0644]
ccan/alignof/alignof.h [new file with mode: 0644]
ccan/alignof/test/run.c [new file with mode: 0644]
ccan/alloc/_info.c [new file with mode: 0644]
ccan/alloc/alloc.c [new file with mode: 0644]
ccan/alloc/alloc.h [new file with mode: 0644]
ccan/alloc/test/run.c [new file with mode: 0644]
ccan/build_assert/_info.c [new file with mode: 0644]
ccan/build_assert/build_assert.h [new file with mode: 0644]
ccan/build_assert/test/compile_fail-expr.c [new file with mode: 0644]
ccan/build_assert/test/compile_fail.c [new file with mode: 0644]
ccan/build_assert/test/compile_ok.c [new file with mode: 0644]
ccan/build_assert/test/run-EXPR_BUILD_ASSERT.c [new file with mode: 0644]
ccan/check_type/_info.c [new file with mode: 0644]
ccan/check_type/check_type.h [new file with mode: 0644]
ccan/check_type/test/compile_fail-check_type.c [new file with mode: 0644]
ccan/check_type/test/compile_fail-check_type_unsigned.c [new file with mode: 0644]
ccan/check_type/test/compile_fail-check_types_match.c [new file with mode: 0644]
ccan/check_type/test/run.c [new file with mode: 0644]
ccan/container_of/_info.c [new file with mode: 0644]
ccan/container_of/container_of.h [new file with mode: 0644]
ccan/container_of/test/compile_fail-bad-type.c [new file with mode: 0644]
ccan/container_of/test/compile_fail-types.c [new file with mode: 0644]
ccan/container_of/test/compile_fail-var-types.c [new file with mode: 0644]
ccan/container_of/test/run.c [new file with mode: 0644]
ccan/list/_info.c [new file with mode: 0644]
ccan/list/list.c [new file with mode: 0644]
ccan/list/list.h [new file with mode: 0644]
ccan/list/test/run.c [new file with mode: 0644]
ccan/noerr/_info.c [new file with mode: 0644]
ccan/noerr/noerr.c [new file with mode: 0644]
ccan/noerr/noerr.h [new file with mode: 0644]
ccan/noerr/test/run.c [new file with mode: 0644]
ccan/string/_info.c [new file with mode: 0644]
ccan/string/string.h [new file with mode: 0644]
ccan/string/test/run.c [new file with mode: 0644]
ccan/talloc/TODO [new file with mode: 0644]
ccan/talloc/_info.c [new file with mode: 0644]
ccan/talloc/talloc.3.xml [new file with mode: 0644]
ccan/talloc/talloc.c [new file with mode: 0644]
ccan/talloc/talloc.h [new file with mode: 0644]
ccan/talloc/test/run.c [new file with mode: 0644]
ccan/tap/_info.c [new file with mode: 0644]
ccan/tap/tap.3 [new file with mode: 0644]
ccan/tap/tap.c [new file with mode: 0644]
ccan/tap/tap.h [new file with mode: 0644]
ccan/tap/test/run.c [new file with mode: 0644]
ccan/typesafe_cb/_info.c [new file with mode: 0644]
ccan/typesafe_cb/test/compile_fail-cast_if_type.c [new file with mode: 0644]
ccan/typesafe_cb/test/compile_fail-typesafe_cb-int.c [new file with mode: 0644]
ccan/typesafe_cb/test/compile_fail-typesafe_cb.c [new file with mode: 0644]
ccan/typesafe_cb/test/compile_fail-typesafe_cb_postargs.c [new file with mode: 0644]
ccan/typesafe_cb/test/compile_fail-typesafe_cb_preargs.c [new file with mode: 0644]
ccan/typesafe_cb/test/run.c [new file with mode: 0644]
ccan/typesafe_cb/typesafe_cb.h [new file with mode: 0644]
ccan_tools/Makefile [deleted file]
ccan_tools/ccanlint/Makefile [deleted file]
ccan_tools/ccanlint/ccanlint.c [deleted file]
ccan_tools/ccanlint/ccanlint.h [deleted file]
ccan_tools/ccanlint/file_analysis.c [deleted file]
ccan_tools/ccanlint/get_file_lines.c [deleted file]
ccan_tools/ccanlint/get_file_lines.h [deleted file]
ccan_tools/ccanlint/has_main_header.c [deleted file]
ccan_tools/ccanlint/has_tests.c [deleted file]
ccan_tools/ccanlint/idempotent.c [deleted file]
ccan_tools/ccanlint/no_info.c [deleted file]
ccan_tools/ccanlint/trailing_whitespace.c [deleted file]
ccan_tools/doc_extract.c [deleted file]
ccan_tools/namespacize.c [deleted file]
ccan_tools/run_tests.c [deleted file]
ccan_tools/test_all.sh [deleted file]
check_type/_info.c [deleted file]
check_type/check_type.h [deleted file]
check_type/test/compile_fail-check_type.c [deleted file]
check_type/test/compile_fail-check_type_unsigned.c [deleted file]
check_type/test/compile_fail-check_types_match.c [deleted file]
check_type/test/run.c [deleted file]
container_of/_info.c [deleted file]
container_of/container_of.h [deleted file]
container_of/test/compile_fail-bad-type.c [deleted file]
container_of/test/compile_fail-types.c [deleted file]
container_of/test/compile_fail-var-types.c [deleted file]
container_of/test/run.c [deleted file]
list/_info.c [deleted file]
list/list.c [deleted file]
list/list.h [deleted file]
list/test/run.c [deleted file]
noerr/_info.c [deleted file]
noerr/noerr.c [deleted file]
noerr/noerr.h [deleted file]
noerr/test/run.c [deleted file]
string/_info.c [deleted file]
string/string.h [deleted file]
string/test/run.c [deleted file]
talloc/TODO [deleted file]
talloc/_info.c [deleted file]
talloc/talloc.3.xml [deleted file]
talloc/talloc.c [deleted file]
talloc/talloc.h [deleted file]
talloc/test/run.c [deleted file]
tap/_info.c [deleted file]
tap/tap.3 [deleted file]
tap/tap.c [deleted file]
tap/tap.h [deleted file]
tap/test/run.c [deleted file]
tools/Makefile [new file with mode: 0644]
tools/ccanlint/Makefile [new file with mode: 0644]
tools/ccanlint/ccanlint.c [new file with mode: 0644]
tools/ccanlint/ccanlint.h [new file with mode: 0644]
tools/ccanlint/file_analysis.c [new file with mode: 0644]
tools/ccanlint/get_file_lines.c [new file with mode: 0644]
tools/ccanlint/get_file_lines.h [new file with mode: 0644]
tools/ccanlint/has_main_header.c [new file with mode: 0644]
tools/ccanlint/has_tests.c [new file with mode: 0644]
tools/ccanlint/idempotent.c [new file with mode: 0644]
tools/ccanlint/no_info.c [new file with mode: 0644]
tools/ccanlint/trailing_whitespace.c [new file with mode: 0644]
tools/doc_extract.c [new file with mode: 0644]
tools/namespacize.c [new file with mode: 0644]
tools/run_tests.c [new file with mode: 0644]
tools/test_all.sh [new file with mode: 0755]
typesafe_cb/_info.c [deleted file]
typesafe_cb/test/compile_fail-cast_if_type.c [deleted file]
typesafe_cb/test/compile_fail-typesafe_cb-int.c [deleted file]
typesafe_cb/test/compile_fail-typesafe_cb.c [deleted file]
typesafe_cb/test/compile_fail-typesafe_cb_postargs.c [deleted file]
typesafe_cb/test/compile_fail-typesafe_cb_preargs.c [deleted file]
typesafe_cb/test/run.c [deleted file]
typesafe_cb/typesafe_cb.h [deleted file]

index 76b79e3309fba524767f6f646e24089a559bd090..b60874d787d7522c8da54df581946b02d8b6a3d4 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,9 @@
 # Hacky makefile to compile everything and run the tests in some kind of sane order.
 # V=--verbose for verbose tests.
 
-CFLAGS=-O3 -Wall -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Werror -I.
+CFLAGS=-O3 -Wall -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Werror -Iccan -I.
 
-ALL=$(patsubst %/test, %, $(wildcard */test))
+ALL=$(patsubst ccan/%/test, ccan/%, $(wildcard ccan/*/test))
 ALL_DEPENDS=$(patsubst %, %/.depends, $(ALL))
 
 test-all: $(ALL_DEPENDS)
@@ -16,13 +16,13 @@ distclean: clean
 $(ALL_DEPENDS): %/.depends: %/_info
        @$< depends > $@ || ( rm -f $@; exit 1 )
 
-test-%: ccan_tools/run_tests
+test-ccan/%: tools/run_tests
        @echo Testing $*...
-       @if ccan_tools/run_tests $(V) $* | grep ^'not ok'; then exit 1; else exit 0; fi
+       @if tools/run_tests $(V) ccan/$* | grep ^'not ok'; then exit 1; else exit 0; fi
 
-ccanlint: ccan_tools/ccanlint/ccanlint
+ccanlint: tools/ccanlint/ccanlint
 
-clean: ccan_tools-clean
-       rm -f `find . -name '*.o'`
+clean: tools-clean
+       rm -f `find . -name '*.o'` `find . -name '.depends'`
 
-include ccan_tools/Makefile
+include tools/Makefile
diff --git a/README b/README
index 65bb8531e167422b5eae49cb617c902f48753ba0..9019fbb2c803309a164736f1ea079f8fa23abe3b 100644 (file)
--- a/README
+++ b/README
@@ -1,8 +1,8 @@
-ccan_tools:
+tools:
        This is currently a bootstrap junkyard for ccan tools.
 
        It is expected that some of this code, being generally useful, will be
        shuffled out to their own modules over time.
 
-other:
+ccan:
        The beginnings of a ccan repository.
diff --git a/alignof/_info.c b/alignof/_info.c
deleted file mode 100644 (file)
index b5afa02..0000000
+++ /dev/null
@@ -1,45 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include "config.h"
-
-/**
- * alignof - ALIGNOF() macro to determine alignment of a type.
- *
- * Many platforms have requirements that certain types must be aligned
- * to certain address boundaries, such as ints needing to be on 4-byte
- * boundaries.  Attempting to access variables with incorrect
- * alignment may cause performance loss or even program failure (eg. a
- * bus signal).
- *
- * There are times which it's useful to be able to programatically
- * access these requirements, such as for dynamic allocators.
- *
- * Example:
- *     #include <stdio.h>
- *     #include "alignof/alignoff.h"
- *
- *     int main(int argc, char *argv[])
- *     {
- *             char arr[sizeof(int)];
- *
- *             if ((unsigned long)arr % ALIGNOF(int)) {
- *                     printf("arr %p CANNOT hold an int\n", arr);
- *                     exit(1);
- *             } else {
- *                     printf("arr %p CAN hold an int\n", arr);
- *                     exit(0);
- *             }
- *     }
- */
-int main(int argc, char *argv[])
-{
-       if (argc != 2)
-               return 1;
-
-       if (strcmp(argv[1], "depends") == 0) {
-               printf("build_assert\n");
-               return 0;
-       }
-
-       return 1;
-}
diff --git a/alignof/alignof.h b/alignof/alignof.h
deleted file mode 100644 (file)
index d146e4c..0000000
+++ /dev/null
@@ -1,19 +0,0 @@
-#ifndef CCAN_ALIGNOF_H
-#define CCAN_ALIGNOF_H
-#include "config.h"
-
-/**
- * ALIGNOF - get the alignment of a type
- * @t: the type to test
- *
- * This returns a safe alignment for the given type.
- */
-#if HAVE_ALIGNOF
-/* A GCC extension. */
-#define ALIGNOF(t) __alignof__(t)
-#else
-/* Alignment by measuring structure padding. */
-#define ALIGNOF(t) ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
-#endif
-
-#endif /* CCAN_ALIGNOF_H */
diff --git a/alignof/test/run.c b/alignof/test/run.c
deleted file mode 100644 (file)
index f76fb66..0000000
+++ /dev/null
@@ -1,62 +0,0 @@
-#include <stdlib.h>
-#include <stddef.h>
-#include <tap/tap.h>
-#include "alignof/alignof.h"
-
-/* Alignment is remarkably difficult to test.  The rules may be more
- * complex than ALIGNOF() can know: eg. on i386 __alignof__(double) == 8, but
- * __alignof__(struct containing double) == 4.
- *
- * Technically, we can only test that we give *at least* the alignment which
- * naturally occurs, and that accesses work.
- *
- * For the moment, we work around double. */
-struct lots_of_types
-{
-       char c;
-       short s;
-       char c2;
-       int i;
-       char c3;
-       float f;
-       char c4;
-       double d;
-       char c5;
-};
-
-int main(int argc, char *argv[])
-{
-       struct lots_of_types lots_of_types, *lp = malloc(sizeof(*lp));
-       char c;
-       short s;
-       char c2;
-       int i;
-       char c3;
-       float f;
-       char c4;
-       double d;
-
-       /* Make sure we use all the variables. */
-       c = 0;
-       c2 = c3 = c4 = c;
-
-       plan_tests(15);
-       ok1((unsigned long)&c % ALIGNOF(char) == 0);
-       ok1((unsigned long)&s % ALIGNOF(short) == 0);
-       ok1((unsigned long)&i % ALIGNOF(int) == 0);
-       ok1((unsigned long)&f % ALIGNOF(float) == 0);
-       ok1((unsigned long)&d % ALIGNOF(double) == 0);
-
-       ok1((unsigned long)&lots_of_types.c % ALIGNOF(char) == 0);
-       ok1((unsigned long)&lots_of_types.s % ALIGNOF(short) == 0);
-       ok1((unsigned long)&lots_of_types.i % ALIGNOF(int) == 0);
-       ok1((unsigned long)&lots_of_types.f % ALIGNOF(float) == 0);
-       ok1(offsetof(struct lots_of_types, d) % ALIGNOF(double) == 0);
-
-       ok1((unsigned long)&lp->c % ALIGNOF(char) == 0);
-       ok1((unsigned long)&lp->s % ALIGNOF(short) == 0);
-       ok1((unsigned long)&lp->i % ALIGNOF(int) == 0);
-       ok1((unsigned long)&lp->f % ALIGNOF(float) == 0);
-       ok1((unsigned long)&lp->d % ALIGNOF(double) == 0);
-       exit(exit_status());
-}
diff --git a/alloc/_info.c b/alloc/_info.c
deleted file mode 100644 (file)
index 59a6638..0000000
+++ /dev/null
@@ -1,103 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include "config.h"
-
-/**
- * alloc - memory allocator routines
- *
- * The alloc module implements a simple allocator which you can use to
- * dynamically allocate space within a region of memory.  This can be useful
- * for suballocations within a given region, or a memory-mapped file.
- *
- * All metadata is kept within the memory handed to the allocator: you only
- * need hand the pointer and the size of the memory to each call.
- *
- * The region contents is always in offsets, so it can be mapped in different
- * places, but is not endian-safe.
- *
- * Example:
- *     #include <sys/mman.h>
- *     #include <unistd.h>
- *     #include <sys/types.h>
- *     #include <err.h>
- *     #include "alloc/alloc.h"
- *
- *     static void usage(const char *name)
- *     {
- *             errx(1, "Usage: %s --create <mapfile>\n"
- *                  " %s --check <mapfile>\n"
- *                  " %s --alloc <mapfile>\n"
- *                  " %s --free=<offset> <mapfile>\n", name, name, name);
- *     }
- *
- *     // Create a memory mapped file, and allocate from within it
- *     int main(int argc, char *argv[])
- *     {
- *             void *a, *p;
- *             int fd;
- *             enum { CREATE, CHECK, ALLOC, FREE } cmd;
- *
- *             if (argc != 3)
- *                     usage(argv[0]);
- *
- *             if (strcmp(argv[1], "--create") == 0)
- *                     cmd = CREATE;
- *             else if (strcmp(argv[1], "--check") == 0)
- *                     cmd = CHECK;
- *             else if (strcmp(argv[1], "--alloc") == 0)
- *                     cmd = ALLOC;
- *             else if (strncmp(argv[1], "--free=", strlen("--free=")) == 0)
- *                     cmd = FREE;
- *             else
- *                     usage(argv[0]);
- *
- *             if (cmd == CREATE) {
- *                     fd = open(argv[2], O_RDWR|O_CREAT|O_EXCL, 0600);
- *                     if (fd < 0)
- *                             err(1, "Could not create %s", argv[2]);
- *                     if (ftruncate(fd, 1048576) != 0)
- *                             err(1, "Could not set length on %s", argv[2]);
- *             } else {
- *                     fd = open(argv[2], O_RDWR);
- *                     if (fd < 0)
- *                             err(1, "Could not open %s", argv[2]);
- *             }
- *
- *             a = mmap(NULL, 1048576, PROT_READ|PROT_WRITE, MAP_SHARED, fd,0);
- *             if (a == MAP_FAILED)
- *                     err(1, "Could not map %s", argv[2]);
- *
- *             switch (cmd) {
- *             case CREATE:
- *                     alloc_init(a, 1048576);
- *                     break;
- *             case CHECK:
- *                     if (!alloc_check(a, 1048576))
- *                             err(1, "Region is corrupt");
- *                     break;
- *             case ALLOC:
- *                     p = alloc_get(a, 1048576, 1024, 16);
- *                     if (!p)
- *                             errx(1, "Could not allocate");
- *                     printf("%zu\n", (char *)p - (char *)a);
- *                     break;
- *             case FREE:
- *                     p = (char *)a + atol(argv[1] + strlen("--free="));
- *                     alloc_free(a, 1048576, p);
- *                     break;
- *             }
- *             return 0;
- *     }
- */
-int main(int argc, char *argv[])
-{
-       if (argc != 2)
-               return 1;
-
-       if (strcmp(argv[1], "depends") == 0) {
-               printf("build_assert\n");
-               return 0;
-       }
-
-       return 1;
-}
diff --git a/alloc/alloc.c b/alloc/alloc.c
deleted file mode 100644 (file)
index f7a05e2..0000000
+++ /dev/null
@@ -1,1119 +0,0 @@
-#include <unistd.h>
-#include <stdint.h>
-#include <string.h>
-#include <limits.h>
-#include <assert.h>
-#include <stdlib.h>
-#include "alloc.h"
-#include "build_assert/build_assert.h"
-#include "alignof/alignof.h"
-#include "config.h"
-
-/* FIXME: We assume getpagesize() doesnt change.  Remapping file with
- * different pagesize should still work. */
-
-/* FIXME: Doesn't handle non-page-aligned poolsize. */
-
-/* FIXME: Reduce. */
-#define MIN_SIZE (getpagesize() * 2)
-
-/* What's the granularity of sub-page allocs? */
-#define BITMAP_GRANULARITY 4
-
-/* File layout:
- *
- *  file := pagestates pad uniform-cache metadata
- *  pagestates := pages * 2-bits-per-page
- *  pad := pad to next ALIGNOF(metaheader)
- *
- *  metadata := metalen next-ptr metabits
- *  metabits := freeblock | bitblock | uniformblock
- *  freeblock := FREE +
- *  bitblock := BITMAP + 2-bits-per-bit-in-page + pad-to-byte
- *  uniformblock := UNIFORM + 14-bit-byte-len + bits + pad-to-byte
- */
-#define UNIFORM_CACHE_NUM 16
-struct uniform_cache
-{
-       uint16_t size[UNIFORM_CACHE_NUM];
-       /* These could be u32 if we're prepared to limit size. */
-       unsigned long page[UNIFORM_CACHE_NUM];
-};
-
-struct metaheader
-{
-       /* Next meta header, or 0 */
-       unsigned long next;
-       /* Bits start here. */
-};
-
-/* Assumes a is a power of two. */
-static unsigned long align_up(unsigned long x, unsigned long a)
-{
-       return (x + a - 1) & ~(a - 1);
-}
-
-static unsigned long align_down(unsigned long x, unsigned long a)
-{
-       return x & ~(a - 1);
-}
-
-static unsigned long div_up(unsigned long x, unsigned long a)
-{
-       return (x + a - 1) / a;
-}
-
-/* It turns out that we spend a lot of time dealing with bit pairs.
- * These routines manipulate them.
- */
-static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
-{
-       return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
-}
-
-static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
-{
-       bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
-       bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
-}
-
-/* This is used for page states and subpage allocations */
-enum alloc_state
-{
-       FREE,
-       TAKEN,
-       TAKEN_START,
-       SPECIAL,        /* Sub-page allocation for page states. */
-};
-
-/* The types for subpage metadata. */
-enum sub_metadata_type
-{
-       /* FREE is same as alloc state */
-       BITMAP = 1, /* bitmap allocated page */
-       UNIFORM, /* uniform size allocated page */
-};
-
-/* Page states are represented by bitpairs, at the start of the pool. */
-#define BITS_PER_PAGE 2
-
-/* How much metadata info per byte? */
-#define METADATA_PER_BYTE (CHAR_BIT / 2)
-
-static uint8_t *get_page_statebits(const void *pool)
-{
-       return (uint8_t *)pool + sizeof(struct uniform_cache);
-}
-
-static enum alloc_state get_page_state(const void *pool, unsigned long page)
-{
-       return get_bit_pair(get_page_statebits(pool), page);
-}
-
-static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
-{
-       set_bit_pair(get_page_statebits(pool), page, s);
-}
-
-/* The offset of metadata for a subpage allocation is found at the end
- * of the subpage */
-#define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
-
-/* This is the length of metadata in bits.  It consists of two bits
- * for every BITMAP_GRANULARITY of usable bytes in the page, then two
- * bits for the tailer.. */
-#define BITMAP_METABITLEN                                              \
-    ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
-
-/* This is the length in bytes. */
-#define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
-
-static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
-{
-       unsigned int pagestatelen;
-
-       pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
-                                      CHAR_BIT),
-                               ALIGNOF(struct metaheader));
-       return (struct metaheader *)(get_page_statebits(pool) + pagestatelen);
-}
-
-static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
-{
-       if (!mh->next)
-               return NULL;
-
-       return (struct metaheader *)((char *)pool + mh->next);
-}
-
-static unsigned long pool_offset(void *pool, void *p)
-{
-       return (char *)p - (char *)pool;
-}
-
-void alloc_init(void *pool, unsigned long poolsize)
-{
-       /* FIXME: Alignment assumptions about pool. */
-       unsigned long len, i;
-       struct metaheader *mh;
-
-       if (poolsize < MIN_SIZE)
-               return;
-
-       mh = first_mheader(pool, poolsize);
-
-       /* Mark all page states FREE, all uniform caches zero, and all of
-        * metaheader bitmap which takes rest of first page. */
-       len = align_up(pool_offset(pool, mh + 1), getpagesize());
-       BUILD_ASSERT(FREE == 0);
-       memset(pool, 0, len);
-
-       /* Mark the pagestate and metadata page(s) allocated. */
-       set_page_state(pool, 0, TAKEN_START);
-       for (i = 1; i < div_up(len, getpagesize()); i++)
-               set_page_state(pool, i, TAKEN);
-}
-
-/* Two bits per element, representing page states.  Returns 0 on fail.
- * off is used to allocate from subpage bitmaps, which use the first 2
- * bits as the type, so the real bitmap is offset by 1. */
-static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
-                                      unsigned long elems,
-                                      unsigned long want, unsigned long align)
-{
-       long i;
-       unsigned long free;
-
-       free = 0;
-       /* We allocate from far end, to increase ability to expand metadata. */
-       for (i = elems - 1; i >= 0; i--) {
-               switch (get_bit_pair(bits, off+i)) {
-               case FREE:
-                       if (++free >= want) {
-                               unsigned long j;
-
-                               /* They might ask for large alignment. */
-                               if (align && i % align)
-                                       continue;
-
-                               set_bit_pair(bits, off+i, TAKEN_START);
-                               for (j = i+1; j < i + want; j++)
-                                       set_bit_pair(bits, off+j, TAKEN);
-                               return off+i;
-                       }
-                       break;
-               case SPECIAL:
-               case TAKEN_START:
-               case TAKEN:
-                       free = 0;
-                       break;
-               }
-       }
-
-       return 0;
-}
-
-static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
-                                    unsigned long pages, unsigned long align)
-{
-       return alloc_from_bitmap(get_page_statebits(pool),
-                                0, poolsize / getpagesize(), pages,
-                                align / getpagesize());
-}
-
-/* Offset to metadata is at end of page. */
-static unsigned long *metadata_off(void *pool, unsigned long page)
-{
-       return (unsigned long *)
-               ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
-}
-
-static uint8_t *get_page_metadata(void *pool, unsigned long page)
-{
-       return (uint8_t *)pool + *metadata_off(pool, page);
-}
-
-static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
-{
-       *metadata_off(pool, page) = meta - (uint8_t *)pool;
-}
-
-static unsigned long sub_page_alloc(void *pool, unsigned long page,
-                                   unsigned long size, unsigned long align)
-{
-       uint8_t *bits = get_page_metadata(pool, page);
-       unsigned long i;
-       enum sub_metadata_type type;
-
-       type = get_bit_pair(bits, 0);
-
-       /* If this is a uniform page, we can't allocate from it. */
-       if (type == UNIFORM)
-               return 0;
-
-       assert(type == BITMAP);
-
-       /* We use a standart bitmap, but offset because of that BITMAP
-        * header. */
-       i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
-                             div_up(size, BITMAP_GRANULARITY),
-                             align / BITMAP_GRANULARITY);
-
-       /* Can't allocate? */
-       if (i == 0)
-               return 0;
-
-       /* i-1 because of the header. */
-       return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
-}
-
-/* We look at the page states to figure out where the allocation for this
- * metadata ends. */
-static unsigned long get_metalen(void *pool, unsigned long poolsize,
-                                struct metaheader *mh)
-{
-       unsigned long i, first, pages = poolsize / getpagesize();
-
-       first = pool_offset(pool, mh + 1)/getpagesize();
-
-       for (i = first + 1; i < pages && get_page_state(pool,i) == TAKEN; i++);
-
-       return i * getpagesize() - pool_offset(pool, mh + 1);
-}
-
-static unsigned int uniform_metalen(unsigned int usize)
-{
-       unsigned int metalen;
-
-       assert(usize < (1 << 14));
-
-       /* Two bits for the header, 14 bits for size, then one bit for each
-        * element the page can hold.  Round up to number of bytes. */
-       metalen = div_up(2 + 14 + SUBPAGE_METAOFF / usize, CHAR_BIT);
-
-       /* To ensure metaheader is always aligned, round bytes up. */
-       metalen = align_up(metalen, ALIGNOF(struct metaheader));
-
-       return metalen;
-}
-
-static unsigned int decode_usize(uint8_t *meta)
-{
-       return ((unsigned)meta[1] << (CHAR_BIT-2)) | (meta[0] >> 2);
-}
-
-static void encode_usize(uint8_t *meta, unsigned int usize)
-{
-       meta[0] = (UNIFORM | (usize << 2));
-       meta[1] = (usize >> (CHAR_BIT - 2));
-}
-
-static uint8_t *alloc_metaspace(void *pool, unsigned long poolsize,
-                               struct metaheader *mh, unsigned long bytes,
-                               enum sub_metadata_type type)
-{
-       uint8_t *meta = (uint8_t *)(mh + 1);
-       unsigned long free = 0, len, i, metalen;
-
-       metalen = get_metalen(pool, poolsize, mh);
-
-       /* Walk through metadata looking for free. */
-       for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
-               switch (get_bit_pair(meta, i)) {
-               case FREE:
-                       len = 1;
-                       free++;
-                       if (free == bytes * METADATA_PER_BYTE) {
-                               /* Mark this as a bitmap. */
-                               set_bit_pair(meta, i - free + 1, type);
-                               return meta + (i - free + 1)/METADATA_PER_BYTE;
-                       }
-                       break;
-               case BITMAP:
-                       /* Skip over this allocated part. */
-                       len = BITMAP_METALEN * METADATA_PER_BYTE;
-                       free = 0;
-                       break;
-               case UNIFORM:
-                       /* Figure metalen given usize. */
-                       len = decode_usize(meta + i / METADATA_PER_BYTE);
-                       len = uniform_metalen(len) * METADATA_PER_BYTE;
-                       free = 0;
-                       break;
-               default:
-                       assert(0);
-                       return NULL;
-               }
-       }
-       return NULL;
-}
-
-/* We need this many bytes of metadata. */
-static uint8_t *new_metadata(void *pool, unsigned long poolsize,
-                            unsigned long bytes, enum sub_metadata_type type)
-{
-       struct metaheader *mh, *newmh;
-       unsigned long page;
-       uint8_t *meta;
-
-       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh))
-               if ((meta = alloc_metaspace(pool, poolsize, mh, bytes, type)))
-                       return meta;
-
-       /* No room for metadata?  Can we expand an existing one? */
-       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
-               unsigned long nextpage;
-
-               /* We start on this page. */
-               nextpage = pool_offset(pool, (char *)(mh+1))/getpagesize();
-               /* Iterate through any other pages we own. */
-               while (get_page_state(pool, ++nextpage) == TAKEN);
-
-               /* Now, can we grab that page? */
-               if (get_page_state(pool, nextpage) != FREE)
-                       continue;
-
-               /* OK, expand metadata, do it again. */
-               set_page_state(pool, nextpage, TAKEN);
-               BUILD_ASSERT(FREE == 0);
-               memset((char *)pool + nextpage*getpagesize(), 0, getpagesize());
-               return alloc_metaspace(pool, poolsize, mh, bytes, type);
-       }
-
-       /* No metadata left at all? */
-       page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
-       if (!page)
-               return NULL;
-
-       newmh = (struct metaheader *)((char *)pool + page * getpagesize());
-       BUILD_ASSERT(FREE == 0);
-       memset(newmh + 1, 0, getpagesize() - sizeof(*mh));
-
-       /* Sew it into linked list */
-       mh = first_mheader(pool,poolsize);
-       newmh->next = mh->next;
-       mh->next = pool_offset(pool, newmh);
-
-       return alloc_metaspace(pool, poolsize, newmh, bytes, type);
-}
-
-static void alloc_free_pages(void *pool, unsigned long pagenum)
-{
-       assert(get_page_state(pool, pagenum) == TAKEN_START);
-       set_page_state(pool, pagenum, FREE);
-       while (get_page_state(pool, ++pagenum) == TAKEN)
-               set_page_state(pool, pagenum, FREE);
-}
-
-static void maybe_transform_uniform_page(void *pool, unsigned long offset)
-{
-       /* FIXME: If possible and page isn't full, change to a bitmap */
-}
-
-/* Returns 0 or the size of the uniform alloc to use */
-static unsigned long suitable_for_uc(unsigned long size, unsigned long align)
-{
-       unsigned long num_elems, wastage, usize;
-       unsigned long bitmap_cost;
-
-       if (size == 0)
-               size = 1;
-
-       /* Fix up silly alignments. */
-       usize = align_up(size, align);
-
-       /* How many can fit in this page? */
-       num_elems = SUBPAGE_METAOFF / usize;
-
-       /* Can happen with bigger alignments. */
-       if (!num_elems)
-               return 0;
-
-       /* Usize maxes out at 14 bits. */
-       if (usize >= (1 << 14))
-               return 0;
-
-       /* How many bytes would be left at the end? */
-       wastage = SUBPAGE_METAOFF % usize;
-
-       /* If we can get a larger allocation within alignment constraints, we
-        * should do it, otherwise might as well leave wastage at the end. */
-       usize += align_down(wastage / num_elems, align);
-
-       /* Bitmap allocation costs 2 bits per BITMAP_GRANULARITY bytes, plus
-        * however much we waste in rounding up to BITMAP_GRANULARITY. */
-       bitmap_cost = 2 * div_up(size, BITMAP_GRANULARITY)
-               + CHAR_BIT * (align_up(size, BITMAP_GRANULARITY) - size);
-
-       /* Our cost is 1 bit, plus usize overhead */
-       if (bitmap_cost < 1 + (usize - size) * CHAR_BIT)
-               return 0;
-
-       return usize;
-}
-
-static unsigned long uniform_alloc(void *pool, unsigned long poolsize,
-                                  struct uniform_cache *uc,
-                                  unsigned long ucnum)
-{
-       uint8_t *metadata = get_page_metadata(pool, uc->page[ucnum]) + 2;
-       unsigned long i, max;
-
-       /* Simple one-bit-per-object bitmap. */
-       max = SUBPAGE_METAOFF / uc->size[ucnum];
-       for (i = 0; i < max; i++) {
-               if (!(metadata[i / CHAR_BIT] & (1 << (i % CHAR_BIT)))) {
-                       metadata[i / CHAR_BIT] |= (1 << (i % CHAR_BIT));
-                       return uc->page[ucnum] * getpagesize()
-                               + i * uc->size[ucnum];
-               }
-       }
-
-       return 0;
-}
-
-static unsigned long new_uniform_page(void *pool, unsigned long poolsize,
-                                     unsigned long usize)
-{
-       unsigned long page, metalen;
-       uint8_t *metadata;
-
-       page = alloc_get_pages(pool, poolsize, 1, 1);
-       if (page == 0)
-               return 0;
-
-       metalen = uniform_metalen(usize);
-
-       /* Get metadata for page. */
-       metadata = new_metadata(pool, poolsize, metalen, UNIFORM);
-       if (!metadata) {
-               alloc_free_pages(pool, page);
-               return 0;
-       }
-
-       encode_usize(metadata, usize);
-
-       BUILD_ASSERT(FREE == 0);
-       memset(metadata + 2, 0, metalen - 2);
-
-       /* Actually, this is a subpage page now. */
-       set_page_state(pool, page, SPECIAL);
-
-       /* Set metadata pointer for page. */
-       set_page_metadata(pool, page, metadata);
-
-       return page;
-}
-
-static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
-                                   unsigned long size, unsigned long align)
-{
-       unsigned long i, usize;
-       uint8_t *metadata;
-       struct uniform_cache *uc = pool;
-
-       usize = suitable_for_uc(size, align);
-       if (usize) {
-               /* Look for a uniform page. */
-               for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
-                       if (uc->size[i] == usize) {
-                               unsigned long ret;
-                               ret = uniform_alloc(pool, poolsize, uc, i);
-                               if (ret != 0)
-                                       return ret;
-                               /* OK, that one is full, remove from cache. */
-                               uc->size[i] = 0;
-                               break;
-                       }
-               }
-
-               /* OK, try a new uniform page.  Use random discard for now. */
-               i = random() % UNIFORM_CACHE_NUM;
-               maybe_transform_uniform_page(pool, uc->page[i]);
-
-               uc->page[i] = new_uniform_page(pool, poolsize, usize);
-               if (uc->page[i]) {
-                       uc->size[i] = usize;
-                       return uniform_alloc(pool, poolsize, uc, i);
-               }
-               uc->size[i] = 0;
-       }
-
-       /* Look for partial page. */
-       for (i = 0; i < poolsize / getpagesize(); i++) {
-               unsigned long ret;
-               if (get_page_state(pool, i) != SPECIAL)
-                       continue;
-
-               ret = sub_page_alloc(pool, i, size, align);
-               if (ret)
-                       return ret;
-       }
-
-       /* Create new SUBPAGE page. */
-       i = alloc_get_pages(pool, poolsize, 1, 1);
-       if (i == 0)
-               return 0;
-
-       /* Get metadata for page. */
-       metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
-       if (!metadata) {
-               alloc_free_pages(pool, i);
-               return 0;
-       }
-
-       /* Actually, this is a subpage page now. */
-       set_page_state(pool, i, SPECIAL);
-
-       /* Set metadata pointer for page. */
-       set_page_metadata(pool, i, metadata);
-
-       /* Do allocation like normal */
-       return sub_page_alloc(pool, i, size, align);
-}
-
-static bool bitmap_page_is_empty(uint8_t *meta)
-{
-       unsigned int i;
-
-       /* Skip the header (first bit of metadata). */
-       for (i = 1; i < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; i++)
-               if (get_bit_pair(meta, i) != FREE)
-                       return false;
-
-       return true;
-}
-
-static bool uniform_page_is_empty(uint8_t *meta)
-{
-       unsigned int i, metalen;
-
-       metalen = uniform_metalen(decode_usize(meta));
-
-       /* Skip the header (first two bytes of metadata). */
-       for (i = 2; i < metalen + 2; i++) {
-               BUILD_ASSERT(FREE == 0);
-               if (meta[i])
-                       return false;
-       }
-       return true;
-}
-
-static bool special_page_is_empty(void *pool, unsigned long page)
-{
-       uint8_t *meta;
-       enum sub_metadata_type type;
-
-       meta = get_page_metadata(pool, page);
-       type = get_bit_pair(meta, 0);
-
-       switch (type) {
-       case UNIFORM:
-               return uniform_page_is_empty(meta);
-       case BITMAP:
-               return bitmap_page_is_empty(meta);
-       default:
-               assert(0);
-       }
-}
-
-static void clear_special_metadata(void *pool, unsigned long page)
-{
-       uint8_t *meta;
-       enum sub_metadata_type type;
-
-       meta = get_page_metadata(pool, page);
-       type = get_bit_pair(meta, 0);
-
-       switch (type) {
-       case UNIFORM:
-               /* First two bytes are the header, rest is already FREE */
-               BUILD_ASSERT(FREE == 0);
-               memset(meta, 0, 2);
-               break;
-       case BITMAP:
-               /* First two bits is the header. */
-               BUILD_ASSERT(BITMAP_METALEN > 1);
-               meta[0] = 0;
-               break;
-       default:
-               assert(0);
-       }
-}
-
-/* Returns true if we cleaned any pages. */
-static bool clean_empty_subpages(void *pool, unsigned long poolsize)
-{
-       unsigned long i;
-       bool progress = false;
-
-       for (i = 0; i < poolsize/getpagesize(); i++) {
-               if (get_page_state(pool, i) != SPECIAL)
-                       continue;
-
-               if (special_page_is_empty(pool, i)) {
-                       clear_special_metadata(pool, i);
-                       set_page_state(pool, i, FREE);
-                       progress = true;
-               }
-       }
-       return progress;
-}
-
-/* Returns true if we cleaned any pages. */
-static bool clean_metadata(void *pool, unsigned long poolsize)
-{
-       struct metaheader *mh, *prev_mh = NULL;
-       bool progress = false;
-
-       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
-               uint8_t *meta;
-               long i;
-               unsigned long metalen = get_metalen(pool, poolsize, mh);
-
-               meta = (uint8_t *)(mh + 1);
-               BUILD_ASSERT(FREE == 0);
-               for (i = metalen - 1; i > 0; i--)
-                       if (meta[i] != 0)
-                               break;
-
-               /* Completely empty? */
-               if (prev_mh && i == metalen) {
-                       alloc_free_pages(pool,
-                                        pool_offset(pool, mh)/getpagesize());
-                       prev_mh->next = mh->next;
-                       mh = prev_mh;
-                       progress = true;
-               } else {
-                       uint8_t *p;
-
-                       /* Some pages at end are free? */
-                       for (p = (uint8_t *)(mh+1) + metalen - getpagesize();
-                            p > meta + i;
-                            p -= getpagesize()) {
-                               set_page_state(pool,
-                                              pool_offset(pool, p)
-                                              / getpagesize(),
-                                              FREE);
-                               progress = true;
-                       }
-               }
-       }
-
-       return progress;
-}
-
-void *alloc_get(void *pool, unsigned long poolsize,
-               unsigned long size, unsigned long align)
-{
-       bool subpage_clean = false, metadata_clean = false;
-       unsigned long ret;
-
-       if (poolsize < MIN_SIZE)
-               return NULL;
-
-again:
-       /* Sub-page allocations have an overhead of ~12%. */
-       if (size + size/8 >= getpagesize() || align >= getpagesize()) {
-               unsigned long pages = div_up(size, getpagesize());
-
-               ret = alloc_get_pages(pool, poolsize, pages, align)
-                       * getpagesize();
-       } else
-               ret = alloc_sub_page(pool, poolsize, size, align);
-
-       if (ret != 0)
-               return (char *)pool + ret;
-
-       /* Allocation failed: garbage collection. */
-       if (!subpage_clean) {
-               subpage_clean = true;
-               if (clean_empty_subpages(pool, poolsize))
-                       goto again;
-       }
-
-       if (!metadata_clean) {
-               metadata_clean = true;
-               if (clean_metadata(pool, poolsize))
-                       goto again;
-       }
-
-       /* FIXME: Compact metadata? */
-       return NULL;
-}
-
-static void bitmap_free(void *pool, unsigned long pagenum, unsigned long off,
-                       uint8_t *metadata)
-{
-       assert(off % BITMAP_GRANULARITY == 0);
-
-       off /= BITMAP_GRANULARITY;
-
-       /* Offset by one because first bit is used for header. */
-       off++;
-
-       set_bit_pair(metadata, off++, FREE);
-       while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
-              && get_bit_pair(metadata, off) == TAKEN)
-               set_bit_pair(metadata, off++, FREE);
-}
-
-static void uniform_free(void *pool, unsigned long pagenum, unsigned long off,
-                        uint8_t *metadata)
-{
-       unsigned int usize, bit;
-
-       usize = decode_usize(metadata);
-       /* Must have been this size. */
-       assert(off % usize == 0);
-       bit = off / usize;
-
-       /* Skip header. */
-       metadata += 2;
-
-       /* Must have been allocated. */
-       assert(metadata[bit / CHAR_BIT] & (1 << (bit % CHAR_BIT)));
-       metadata[bit / CHAR_BIT] &= ~(1 << (bit % CHAR_BIT));
-}
-
-static void subpage_free(void *pool, unsigned long pagenum, void *free)
-{
-       unsigned long off = (unsigned long)free % getpagesize();
-       uint8_t *metadata = get_page_metadata(pool, pagenum);
-       enum sub_metadata_type type;
-
-       type = get_bit_pair(metadata, 0);
-
-       assert(off < SUBPAGE_METAOFF);
-
-       switch (type) {
-       case BITMAP:
-               bitmap_free(pool, pagenum, off, metadata);
-               break;
-       case UNIFORM:
-               uniform_free(pool, pagenum, off, metadata);
-               break;
-       default:
-               assert(0);
-       }
-}
-
-void alloc_free(void *pool, unsigned long poolsize, void *free)
-{
-       unsigned long pagenum;
-       struct metaheader *mh;
-
-       if (!free)
-               return;
-
-       assert(poolsize >= MIN_SIZE);
-
-       mh = first_mheader(pool, poolsize);
-       assert((char *)free >= (char *)(mh + 1));
-       assert((char *)pool + poolsize > (char *)free);
-
-       pagenum = pool_offset(pool, free) / getpagesize();
-
-       if (get_page_state(pool, pagenum) == SPECIAL)
-               subpage_free(pool, pagenum, free);
-       else {
-               assert((unsigned long)free % getpagesize() == 0);
-               alloc_free_pages(pool, pagenum);
-       }
-}
-
-static bool is_metadata_page(void *pool, unsigned long poolsize,
-                            unsigned long page)
-{
-       struct metaheader *mh;
-
-       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
-               unsigned long start, end;
-
-               start = pool_offset(pool, mh);
-               end = pool_offset(pool, (char *)(mh+1)
-                                 + get_metalen(pool, poolsize, mh));
-               if (page >= start/getpagesize() && page < end/getpagesize())
-                       return true;
-       }
-       return false;
-}
-
-static bool check_bitmap_metadata(void *pool, unsigned long *mhoff)
-{
-       enum alloc_state last_state = FREE;
-       unsigned int i;
-
-       for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
-               enum alloc_state state;
-
-               /* +1 because header is the first byte. */
-               state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
-               switch (state) {
-               case SPECIAL:
-                       return false;
-               case TAKEN:
-                       if (last_state == FREE)
-                               return false;
-                       break;
-               default:
-                       break;
-               }
-               last_state = state;
-       }
-       return true;
-}
-
-static bool check_uniform_metadata(void *pool, unsigned long *mhoff)
-{
-       uint8_t *meta = (uint8_t *)pool + *mhoff;
-       unsigned int i, usize;
-       struct uniform_cache *uc = pool;
-
-       usize = decode_usize(meta);
-       if (usize == 0 || suitable_for_uc(usize, 1) != usize)
-               return false;
-
-       /* If it's in uniform cache, make sure that agrees on size. */
-       for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
-               uint8_t *ucm;
-
-               if (!uc->size[i])
-                       continue;
-
-               ucm = get_page_metadata(pool, uc->page[i]);
-               if (ucm != meta)
-                       continue;
-
-               if (usize != uc->size[i])
-                       return false;
-       }
-       return true;
-}
-
-static bool check_subpage(void *pool, unsigned long poolsize,
-                         unsigned long page)
-{
-       unsigned long *mhoff = metadata_off(pool, page);
-
-       if (*mhoff + sizeof(struct metaheader) > poolsize)
-               return false;
-
-       if (*mhoff % ALIGNOF(struct metaheader) != 0)
-               return false;
-
-       /* It must point to a metadata page. */
-       if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
-               return false;
-
-       /* Header at start of subpage allocation */
-       switch (get_bit_pair((uint8_t *)pool + *mhoff, 0)) {
-       case BITMAP:
-               return check_bitmap_metadata(pool, mhoff);
-       case UNIFORM:
-               return check_uniform_metadata(pool, mhoff);
-       default:
-               return false;
-       }
-
-}
-
-bool alloc_check(void *pool, unsigned long poolsize)
-{
-       unsigned long i;
-       struct metaheader *mh;
-       enum alloc_state last_state = FREE;
-       bool was_metadata = false;
-
-       if (poolsize < MIN_SIZE)
-               return true;
-
-       if (get_page_state(pool, 0) != TAKEN_START)
-               return false;
-
-       /* First check metadata pages. */
-       /* Metadata pages will be marked TAKEN. */
-       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
-               unsigned long start, end;
-
-               start = pool_offset(pool, mh);
-               if (start + sizeof(*mh) > poolsize)
-                       return false;
-
-               end = pool_offset(pool, (char *)(mh+1)
-                                 + get_metalen(pool, poolsize, mh));
-               if (end > poolsize)
-                       return false;
-
-               /* Non-first pages should start on a page boundary. */
-               if (mh != first_mheader(pool, poolsize)
-                   && start % getpagesize() != 0)
-                       return false;
-
-               /* It should end on a page boundary. */
-               if (end % getpagesize() != 0)
-                       return false;
-       }
-
-       for (i = 0; i < poolsize / getpagesize(); i++) {
-               enum alloc_state state = get_page_state(pool, i);
-               bool is_metadata = is_metadata_page(pool, poolsize,i);
-
-               switch (state) {
-               case FREE:
-                       /* metadata pages are never free. */
-                       if (is_metadata)
-                               return false;
-               case TAKEN_START:
-                       break;
-               case TAKEN:
-                       /* This should continue a previous block. */
-                       if (last_state == FREE)
-                               return false;
-                       if (is_metadata != was_metadata)
-                               return false;
-                       break;
-               case SPECIAL:
-                       /* Check metadata pointer etc. */
-                       if (!check_subpage(pool, poolsize, i))
-                               return false;
-               }
-               last_state = state;
-               was_metadata = is_metadata;
-       }
-       return true;
-}
-
-void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
-{
-       struct metaheader *mh;
-       struct uniform_cache *uc = pool;
-       unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
-       long i;
-
-       if (poolsize < MIN_SIZE) {
-               fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
-               return;
-       }
-
-       tot = 0;
-       for (i = 0; i < UNIFORM_CACHE_NUM; i++)
-               tot += (uc->size[i] != 0);
-       fprintf(out, "Uniform cache (%lu entries):\n", tot);
-       for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
-               unsigned int j, total = 0;
-               uint8_t *meta;
-
-               if (!uc->size[i])
-                       continue;
-
-               /* First two bytes are header. */
-               meta = get_page_metadata(pool, uc->page[i]) + 2;
-
-               for (j = 0; j < SUBPAGE_METAOFF / uc->size[i]; j++)
-                       if (meta[j / 8] & (1 << (j % 8)))
-                               total++;
-
-               printf("  %u: %u/%u (%u%% density)\n",
-                      uc->size[j], total, SUBPAGE_METAOFF / uc->size[i],
-                      (total * 100) / (SUBPAGE_METAOFF / uc->size[i]));
-       }
-
-       memset(count, 0, sizeof(count));
-       for (i = 0; i < poolsize / getpagesize(); i++)
-               count[get_page_state(pool, i)]++;
-
-       mh = first_mheader(pool, poolsize);
-       pagebitlen = (uint8_t *)mh - get_page_statebits(pool);
-       fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
-               pagebitlen, count[0], count[1], count[2], count[3]);
-
-       /* One metadata page for every page of page bits. */
-       metadata_pages = div_up(pagebitlen, getpagesize());
-
-       /* Now do each metadata page. */
-       for (; mh; mh = next_mheader(pool,mh)) {
-               unsigned long free = 0, bitmapblocks = 0, uniformblocks = 0,
-                       len = 0, uniformlen = 0, bitmaplen = 0, metalen;
-               uint8_t *meta = (uint8_t *)(mh + 1);
-
-               metalen = get_metalen(pool, poolsize, mh);
-               metadata_pages += (sizeof(*mh) + metalen) / getpagesize();
-
-               for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
-                       switch (get_bit_pair(meta, i)) {
-                       case FREE:
-                               len = 1;
-                               free++;
-                               break;
-                       case BITMAP:
-                               /* Skip over this allocated part. */
-                               len = BITMAP_METALEN * CHAR_BIT;
-                               bitmapblocks++;
-                               bitmaplen += len;
-                               break;
-                       case UNIFORM:
-                               /* Skip over this part. */
-                               len = decode_usize(meta + i/METADATA_PER_BYTE);
-                               len = uniform_metalen(len) * METADATA_PER_BYTE;
-                               uniformblocks++;
-                               uniformlen += len;
-                               break;
-                       default:
-                               assert(0);
-                       }
-               }
-
-               fprintf(out, "Metadata %lu-%lu: %lu free, %lu bitmapblocks, %lu uniformblocks, %lu%% density\n",
-                       pool_offset(pool, mh),
-                       pool_offset(pool, (char *)(mh+1) + metalen),
-                       free, bitmapblocks, uniformblocks,
-                       (bitmaplen + uniformlen) * 100
-                       / (free + bitmaplen + uniformlen));
-       }
-
-       /* Account for total pages allocated. */
-       tot = (count[1] + count[2] - metadata_pages) * getpagesize();
-
-       fprintf(out, "Total metadata bytes = %lu\n",
-               metadata_pages * getpagesize());
-
-       /* Now do every subpage. */
-       for (i = 0; i < poolsize / getpagesize(); i++) {
-               uint8_t *meta;
-               unsigned int j, allocated;
-               enum sub_metadata_type type;
-
-               if (get_page_state(pool, i) != SPECIAL)
-                       continue;
-
-               memset(count, 0, sizeof(count));
-
-               meta = get_page_metadata(pool, i);
-               type = get_bit_pair(meta, 0);
-
-               if (type == BITMAP) {
-                       for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
-                               count[get_page_state(meta, j)]++;
-                       allocated = (count[1] + count[2]) * BITMAP_GRANULARITY;
-                       fprintf(out, "Subpage bitmap ");
-               } else {
-                       unsigned int usize = decode_usize(meta);
-
-                       assert(type == UNIFORM);
-                       fprintf(out, "Subpage uniform (%u) ", usize);
-                       meta += 2;
-                       for (j = 0; j < SUBPAGE_METAOFF / usize; j++)
-                               count[!!(meta[j / 8] & (1 << (j % 8)))]++;
-                       allocated = count[1] * usize;
-               }
-               fprintf(out, "%lu: FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %u%% density\n",
-                       i, count[0], count[1], count[2],
-                       allocated * 100 / getpagesize());
-               tot += allocated;
-       }
-
-       /* This is optimistic, since we overalloc in several cases. */
-       fprintf(out, "Best possible allocation density = %lu%%\n",
-               tot * 100 / poolsize);
-}
diff --git a/alloc/alloc.h b/alloc/alloc.h
deleted file mode 100644 (file)
index 29c29d0..0000000
+++ /dev/null
@@ -1,13 +0,0 @@
-#ifndef ALLOC_H
-#define ALLOC_H
-#include <stdio.h>
-#include <stdbool.h>
-
-void alloc_init(void *pool, unsigned long poolsize);
-void *alloc_get(void *pool, unsigned long poolsize,
-               unsigned long size, unsigned long align);
-void alloc_free(void *pool, unsigned long poolsize, void *free);
-bool alloc_check(void *pool, unsigned long poolsize);
-
-void alloc_visualize(FILE *out, void *pool, unsigned long poolsize);
-#endif /* ALLOC_H */
diff --git a/alloc/test/run.c b/alloc/test/run.c
deleted file mode 100644 (file)
index 8cfe8b4..0000000
+++ /dev/null
@@ -1,195 +0,0 @@
-#include "alloc/alloc.h"
-#include "tap/tap.h"
-#include "alloc/alloc.c"
-#include <stdlib.h>
-
-#define POOL_ORD 16
-#define POOL_SIZE (1 << POOL_ORD)
-
-#define sort(p, num, cmp) \
-       qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
-
-static int addr_cmp(void **a, void **b)
-{
-       return (*a) - (*b);
-}
-
-static bool unique(void *p[], unsigned int num)
-{
-       unsigned int i;
-
-       for (i = 1; i < num; i++)
-               if (p[i] == p[i-1])
-                       return false;
-       return true;
-}      
-
-static bool free_every_second_one(void *mem, unsigned int num, void *p[])
-{
-       unsigned int i;
-
-       /* Free every second one. */
-       for (i = 0; i < num; i += 2) {
-               alloc_free(mem, POOL_SIZE, p[i]);
-               if (!alloc_check(mem, POOL_SIZE))
-                       return false;
-       }
-       for (i = 1; i < num; i += 2) {
-               alloc_free(mem, POOL_SIZE, p[i]);
-               if (!alloc_check(mem, POOL_SIZE))
-                       return false;
-       }
-       return true;
-}
-
-
-int main(int argc, char *argv[])
-{
-       void *mem;
-       unsigned int i, num, max_size;
-       void *p[POOL_SIZE];
-
-       plan_tests(139);
-
-       /* FIXME: Needs to be page aligned for now. */
-       posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE);
-
-       /* Small pool, all allocs fail, even 0-length. */
-       alloc_init(mem, 0);
-       ok1(alloc_check(mem, 0));
-       ok1(alloc_get(mem, 0, 1, 1) == NULL);
-       ok1(alloc_get(mem, 0, 128, 1) == NULL);
-       ok1(alloc_get(mem, 0, 0, 1) == NULL);
-
-       /* Free of NULL should work. */
-       alloc_free(mem, 0, NULL);
-
-       alloc_init(mem, POOL_SIZE);
-       ok1(alloc_check(mem, POOL_SIZE));
-       /* Find largest allocation which works. */
-       for (max_size = POOL_SIZE * 2; max_size; max_size--) {
-               p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
-               if (p[0])
-                       break;
-       }
-       ok1(max_size < POOL_SIZE);
-       ok1(max_size > 0);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Free it, should be able to reallocate it. */
-       alloc_free(mem, POOL_SIZE, p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
-       ok1(p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-       alloc_free(mem, POOL_SIZE, p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Allocate a whole heap. */
-       for (i = 0; i < POOL_SIZE; i++) {
-               p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
-               if (!p[i])
-                       break;
-       }
-
-       /* Uncomment this for a more intuitive view of what the
-        * allocator looks like after all these 1 byte allocs. */
-#if 0
-       alloc_visualize(stderr, mem, POOL_SIZE);
-#endif
-
-       num = i;
-       /* Can't allocate this many. */
-       ok1(num != POOL_SIZE);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Sort them. */
-       sort(p, num, addr_cmp);
-
-       /* Uniqueness check */
-       ok1(unique(p, num));
-
-       ok1(free_every_second_one(mem, num, p));
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Should be able to reallocate max size. */
-       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
-       ok1(p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Re-initializing should be the same as freeing everything */
-       alloc_init(mem, POOL_SIZE);
-       ok1(alloc_check(mem, POOL_SIZE));
-       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
-       ok1(p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-       alloc_free(mem, POOL_SIZE, p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Alignment constraints should be met, as long as powers of two */
-       for (i = 0; i < POOL_ORD-1; i++) {
-               p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
-               ok1(p[i]);
-               ok1(((unsigned long)p[i] % (1 << i)) == 0);
-               ok1(alloc_check(mem, POOL_SIZE));
-       }
-
-       for (i = 0; i < POOL_ORD-1; i++) {
-               alloc_free(mem, POOL_SIZE, p[i]);
-               ok1(alloc_check(mem, POOL_SIZE));
-       }
-
-       /* Alignment constraints for a single-byte allocation. */
-       for (i = 0; i < POOL_ORD; i++) {
-               p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
-               ok1(p[0]);
-               ok1(alloc_check(mem, POOL_SIZE));
-               alloc_free(mem, POOL_SIZE, p[0]);
-               ok1(alloc_check(mem, POOL_SIZE));
-       }
-
-       /* Alignment check for a 0-byte allocation.  Corner case. */
-       p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (POOL_ORD - 1));
-       ok1(alloc_check(mem, POOL_SIZE));
-       alloc_free(mem, POOL_SIZE, p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Force the testing of split metadata. */
-       alloc_init(mem, POOL_SIZE);
-       for (i = 0; i < POOL_SIZE; i++) {
-               p[i] = alloc_get(mem, POOL_SIZE, getpagesize(), getpagesize());
-               if (!p[i])
-                       break;
-       }
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Sort them. */
-       sort(p, i-1, addr_cmp);
-
-       /* Free all but the one next to the metadata. */
-       for (i = 1; p[i]; i++)
-               alloc_free(mem, POOL_SIZE, p[i]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Now do a whole heap of subpage allocs. */
-       for (i = 1; i < POOL_SIZE; i++) {
-               p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
-               if (!p[i])
-                       break;
-       }
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       /* Free up our page next to metadata, and should be able to alloc */
-       alloc_free(mem, POOL_SIZE, p[0]);
-       ok1(alloc_check(mem, POOL_SIZE));
-       p[0] = alloc_get(mem, POOL_SIZE, 1, 1);
-       ok1(p[0]);
-
-       /* Clean up. */
-       for (i = 0; p[i]; i++)
-               alloc_free(mem, POOL_SIZE, p[i]);
-       ok1(alloc_check(mem, POOL_SIZE));
-
-       return exit_status();
-}
diff --git a/build_assert/_info.c b/build_assert/_info.c
deleted file mode 100644 (file)
index 555aae2..0000000
+++ /dev/null
@@ -1,38 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include "config.h"
-
-/**
- * build_assert - routines for build-time assertions
- *
- * This code provides routines which will cause compilation to fail should some
- * assertion be untrue: such failures are preferable to run-time assertions,
- * but much more limited since they can only depends on compile-time constants.
- *
- * These assertions are most useful when two parts of the code must be kept in
- * sync: it is better to avoid such cases if possible, but seconds best is to
- * detect invalid changes at build time.
- *
- * For example, a tricky piece of code might rely on a certain element being at
- * the start of the structure.  To ensure that future changes don't break it,
- * you would catch such changes in your code like so:
- *
- * Example:
- *     char *foo_string(struct foo *foo)
- *     {
- *             // This trick requires that the string be first in the structure
- *             BUILD_ASSERT(offsetof(struct foo, string) == 0);
- *             return (char *)foo;
- *     }
- */
-int main(int argc, char *argv[])
-{
-       if (argc != 2)
-               return 1;
-
-       if (strcmp(argv[1], "depends") == 0)
-               /* Nothing. */
-               return 0;
-
-       return 1;
-}
diff --git a/build_assert/build_assert.h b/build_assert/build_assert.h
deleted file mode 100644 (file)
index 4b0d75e..0000000
+++ /dev/null
@@ -1,37 +0,0 @@
-#ifndef CCAN_BUILD_ASSERT_H
-#define CCAN_BUILD_ASSERT_H
-
-/**
- * BUILD_ASSERT - assert a build-time dependency.
- * @cond: the compile-time condition which must be true.
- *
- * Your compile will fail if the condition isn't true, or can't be evaluated
- * by the compiler.  This can only be used within a function.
- *
- * Example:
- *     char *foo_to_char(struct foo *foo)
- *     {
- *             // This code needs string to be at start of foo.
- *             BUILD_ASSERT(offsetof(struct foo, string) == 0);
- *             return (char *)foo;
- *     }
- */
-#define BUILD_ASSERT(cond) \
-       do { (void) sizeof(char [1 - 2*!(cond)]); } while(0)
-
-/**
- * EXPR_BUILD_ASSERT - assert a build-time dependency, as an expression.
- * @cond: the compile-time condition which must be true.
- *
- * Your compile will fail if the condition isn't true, or can't be evaluated
- * by the compiler.  This can be used in an expression: its value is "0".
- *
- * Example:
- *     #define foo_to_char(foo)                                        \
- *              ((char *)(foo)                                         \
- *               + EXPR_BUILD_ASSERT(offsetof(struct foo, string) == 0))
- */
-#define EXPR_BUILD_ASSERT(cond) \
-       (sizeof(char [1 - 2*!(cond)]) - 1)
-
-#endif /* CCAN_BUILD_ASSERT_H */
diff --git a/build_assert/test/compile_fail-expr.c b/build_assert/test/compile_fail-expr.c
deleted file mode 100644 (file)
index 41cdc0f..0000000
+++ /dev/null
@@ -1,10 +0,0 @@
-#include "build_assert/build_assert.h"
-
-int main(int argc, char *argv[])
-{
-#ifdef FAIL
-       return EXPR_BUILD_ASSERT(1 == 0);
-#else
-       return 0;
-#endif
-}
diff --git a/build_assert/test/compile_fail.c b/build_assert/test/compile_fail.c
deleted file mode 100644 (file)
index a6867db..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-#include "build_assert/build_assert.h"
-
-int main(int argc, char *argv[])
-{
-#ifdef FAIL
-       BUILD_ASSERT(1 == 0);
-#endif
-       return 0;
-}
diff --git a/build_assert/test/compile_ok.c b/build_assert/test/compile_ok.c
deleted file mode 100644 (file)
index bc5541f..0000000
+++ /dev/null
@@ -1,7 +0,0 @@
-#include "build_assert/build_assert.h"
-
-int main(int argc, char *argv[])
-{
-       BUILD_ASSERT(1 == 1);
-       return 0;
-}
diff --git a/build_assert/test/run-EXPR_BUILD_ASSERT.c b/build_assert/test/run-EXPR_BUILD_ASSERT.c
deleted file mode 100644 (file)
index 7fd0c49..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-#include "build_assert/build_assert.h"
-#include "tap/tap.h"
-
-int main(int argc, char *argv[])
-{
-       plan_tests(1);
-       ok1(EXPR_BUILD_ASSERT(1 == 1) == 0);
-       return exit_status();
-}
diff --git a/ccan/alignof/_info.c b/ccan/alignof/_info.c
new file mode 100644 (file)
index 0000000..4cccba3
--- /dev/null
@@ -0,0 +1,45 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * alignof - ALIGNOF() macro to determine alignment of a type.
+ *
+ * Many platforms have requirements that certain types must be aligned
+ * to certain address boundaries, such as ints needing to be on 4-byte
+ * boundaries.  Attempting to access variables with incorrect
+ * alignment may cause performance loss or even program failure (eg. a
+ * bus signal).
+ *
+ * There are times which it's useful to be able to programatically
+ * access these requirements, such as for dynamic allocators.
+ *
+ * Example:
+ *     #include <stdio.h>
+ *     #include "alignof/alignoff.h"
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             char arr[sizeof(int)];
+ *
+ *             if ((unsigned long)arr % ALIGNOF(int)) {
+ *                     printf("arr %p CANNOT hold an int\n", arr);
+ *                     exit(1);
+ *             } else {
+ *                     printf("arr %p CAN hold an int\n", arr);
+ *                     exit(0);
+ *             }
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/build_assert\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/alignof/alignof.h b/ccan/alignof/alignof.h
new file mode 100644 (file)
index 0000000..d146e4c
--- /dev/null
@@ -0,0 +1,19 @@
+#ifndef CCAN_ALIGNOF_H
+#define CCAN_ALIGNOF_H
+#include "config.h"
+
+/**
+ * ALIGNOF - get the alignment of a type
+ * @t: the type to test
+ *
+ * This returns a safe alignment for the given type.
+ */
+#if HAVE_ALIGNOF
+/* A GCC extension. */
+#define ALIGNOF(t) __alignof__(t)
+#else
+/* Alignment by measuring structure padding. */
+#define ALIGNOF(t) ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
+#endif
+
+#endif /* CCAN_ALIGNOF_H */
diff --git a/ccan/alignof/test/run.c b/ccan/alignof/test/run.c
new file mode 100644 (file)
index 0000000..f76fb66
--- /dev/null
@@ -0,0 +1,62 @@
+#include <stdlib.h>
+#include <stddef.h>
+#include <tap/tap.h>
+#include "alignof/alignof.h"
+
+/* Alignment is remarkably difficult to test.  The rules may be more
+ * complex than ALIGNOF() can know: eg. on i386 __alignof__(double) == 8, but
+ * __alignof__(struct containing double) == 4.
+ *
+ * Technically, we can only test that we give *at least* the alignment which
+ * naturally occurs, and that accesses work.
+ *
+ * For the moment, we work around double. */
+struct lots_of_types
+{
+       char c;
+       short s;
+       char c2;
+       int i;
+       char c3;
+       float f;
+       char c4;
+       double d;
+       char c5;
+};
+
+int main(int argc, char *argv[])
+{
+       struct lots_of_types lots_of_types, *lp = malloc(sizeof(*lp));
+       char c;
+       short s;
+       char c2;
+       int i;
+       char c3;
+       float f;
+       char c4;
+       double d;
+
+       /* Make sure we use all the variables. */
+       c = 0;
+       c2 = c3 = c4 = c;
+
+       plan_tests(15);
+       ok1((unsigned long)&c % ALIGNOF(char) == 0);
+       ok1((unsigned long)&s % ALIGNOF(short) == 0);
+       ok1((unsigned long)&i % ALIGNOF(int) == 0);
+       ok1((unsigned long)&f % ALIGNOF(float) == 0);
+       ok1((unsigned long)&d % ALIGNOF(double) == 0);
+
+       ok1((unsigned long)&lots_of_types.c % ALIGNOF(char) == 0);
+       ok1((unsigned long)&lots_of_types.s % ALIGNOF(short) == 0);
+       ok1((unsigned long)&lots_of_types.i % ALIGNOF(int) == 0);
+       ok1((unsigned long)&lots_of_types.f % ALIGNOF(float) == 0);
+       ok1(offsetof(struct lots_of_types, d) % ALIGNOF(double) == 0);
+
+       ok1((unsigned long)&lp->c % ALIGNOF(char) == 0);
+       ok1((unsigned long)&lp->s % ALIGNOF(short) == 0);
+       ok1((unsigned long)&lp->i % ALIGNOF(int) == 0);
+       ok1((unsigned long)&lp->f % ALIGNOF(float) == 0);
+       ok1((unsigned long)&lp->d % ALIGNOF(double) == 0);
+       exit(exit_status());
+}
diff --git a/ccan/alloc/_info.c b/ccan/alloc/_info.c
new file mode 100644 (file)
index 0000000..03e20af
--- /dev/null
@@ -0,0 +1,103 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * alloc - memory allocator routines
+ *
+ * The alloc module implements a simple allocator which you can use to
+ * dynamically allocate space within a region of memory.  This can be useful
+ * for suballocations within a given region, or a memory-mapped file.
+ *
+ * All metadata is kept within the memory handed to the allocator: you only
+ * need hand the pointer and the size of the memory to each call.
+ *
+ * The region contents is always in offsets, so it can be mapped in different
+ * places, but is not endian-safe.
+ *
+ * Example:
+ *     #include <sys/mman.h>
+ *     #include <unistd.h>
+ *     #include <sys/types.h>
+ *     #include <err.h>
+ *     #include "alloc/alloc.h"
+ *
+ *     static void usage(const char *name)
+ *     {
+ *             errx(1, "Usage: %s --create <mapfile>\n"
+ *                  " %s --check <mapfile>\n"
+ *                  " %s --alloc <mapfile>\n"
+ *                  " %s --free=<offset> <mapfile>\n", name, name, name);
+ *     }
+ *
+ *     // Create a memory mapped file, and allocate from within it
+ *     int main(int argc, char *argv[])
+ *     {
+ *             void *a, *p;
+ *             int fd;
+ *             enum { CREATE, CHECK, ALLOC, FREE } cmd;
+ *
+ *             if (argc != 3)
+ *                     usage(argv[0]);
+ *
+ *             if (strcmp(argv[1], "--create") == 0)
+ *                     cmd = CREATE;
+ *             else if (strcmp(argv[1], "--check") == 0)
+ *                     cmd = CHECK;
+ *             else if (strcmp(argv[1], "--alloc") == 0)
+ *                     cmd = ALLOC;
+ *             else if (strncmp(argv[1], "--free=", strlen("--free=")) == 0)
+ *                     cmd = FREE;
+ *             else
+ *                     usage(argv[0]);
+ *
+ *             if (cmd == CREATE) {
+ *                     fd = open(argv[2], O_RDWR|O_CREAT|O_EXCL, 0600);
+ *                     if (fd < 0)
+ *                             err(1, "Could not create %s", argv[2]);
+ *                     if (ftruncate(fd, 1048576) != 0)
+ *                             err(1, "Could not set length on %s", argv[2]);
+ *             } else {
+ *                     fd = open(argv[2], O_RDWR);
+ *                     if (fd < 0)
+ *                             err(1, "Could not open %s", argv[2]);
+ *             }
+ *
+ *             a = mmap(NULL, 1048576, PROT_READ|PROT_WRITE, MAP_SHARED, fd,0);
+ *             if (a == MAP_FAILED)
+ *                     err(1, "Could not map %s", argv[2]);
+ *
+ *             switch (cmd) {
+ *             case CREATE:
+ *                     alloc_init(a, 1048576);
+ *                     break;
+ *             case CHECK:
+ *                     if (!alloc_check(a, 1048576))
+ *                             err(1, "Region is corrupt");
+ *                     break;
+ *             case ALLOC:
+ *                     p = alloc_get(a, 1048576, 1024, 16);
+ *                     if (!p)
+ *                             errx(1, "Could not allocate");
+ *                     printf("%zu\n", (char *)p - (char *)a);
+ *                     break;
+ *             case FREE:
+ *                     p = (char *)a + atol(argv[1] + strlen("--free="));
+ *                     alloc_free(a, 1048576, p);
+ *                     break;
+ *             }
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/build_assert\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/alloc/alloc.c b/ccan/alloc/alloc.c
new file mode 100644 (file)
index 0000000..f7a05e2
--- /dev/null
@@ -0,0 +1,1119 @@
+#include <unistd.h>
+#include <stdint.h>
+#include <string.h>
+#include <limits.h>
+#include <assert.h>
+#include <stdlib.h>
+#include "alloc.h"
+#include "build_assert/build_assert.h"
+#include "alignof/alignof.h"
+#include "config.h"
+
+/* FIXME: We assume getpagesize() doesnt change.  Remapping file with
+ * different pagesize should still work. */
+
+/* FIXME: Doesn't handle non-page-aligned poolsize. */
+
+/* FIXME: Reduce. */
+#define MIN_SIZE (getpagesize() * 2)
+
+/* What's the granularity of sub-page allocs? */
+#define BITMAP_GRANULARITY 4
+
+/* File layout:
+ *
+ *  file := pagestates pad uniform-cache metadata
+ *  pagestates := pages * 2-bits-per-page
+ *  pad := pad to next ALIGNOF(metaheader)
+ *
+ *  metadata := metalen next-ptr metabits
+ *  metabits := freeblock | bitblock | uniformblock
+ *  freeblock := FREE +
+ *  bitblock := BITMAP + 2-bits-per-bit-in-page + pad-to-byte
+ *  uniformblock := UNIFORM + 14-bit-byte-len + bits + pad-to-byte
+ */
+#define UNIFORM_CACHE_NUM 16
+struct uniform_cache
+{
+       uint16_t size[UNIFORM_CACHE_NUM];
+       /* These could be u32 if we're prepared to limit size. */
+       unsigned long page[UNIFORM_CACHE_NUM];
+};
+
+struct metaheader
+{
+       /* Next meta header, or 0 */
+       unsigned long next;
+       /* Bits start here. */
+};
+
+/* Assumes a is a power of two. */
+static unsigned long align_up(unsigned long x, unsigned long a)
+{
+       return (x + a - 1) & ~(a - 1);
+}
+
+static unsigned long align_down(unsigned long x, unsigned long a)
+{
+       return x & ~(a - 1);
+}
+
+static unsigned long div_up(unsigned long x, unsigned long a)
+{
+       return (x + a - 1) / a;
+}
+
+/* It turns out that we spend a lot of time dealing with bit pairs.
+ * These routines manipulate them.
+ */
+static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
+{
+       return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
+}
+
+static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
+{
+       bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
+       bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
+}
+
+/* This is used for page states and subpage allocations */
+enum alloc_state
+{
+       FREE,
+       TAKEN,
+       TAKEN_START,
+       SPECIAL,        /* Sub-page allocation for page states. */
+};
+
+/* The types for subpage metadata. */
+enum sub_metadata_type
+{
+       /* FREE is same as alloc state */
+       BITMAP = 1, /* bitmap allocated page */
+       UNIFORM, /* uniform size allocated page */
+};
+
+/* Page states are represented by bitpairs, at the start of the pool. */
+#define BITS_PER_PAGE 2
+
+/* How much metadata info per byte? */
+#define METADATA_PER_BYTE (CHAR_BIT / 2)
+
+static uint8_t *get_page_statebits(const void *pool)
+{
+       return (uint8_t *)pool + sizeof(struct uniform_cache);
+}
+
+static enum alloc_state get_page_state(const void *pool, unsigned long page)
+{
+       return get_bit_pair(get_page_statebits(pool), page);
+}
+
+static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
+{
+       set_bit_pair(get_page_statebits(pool), page, s);
+}
+
+/* The offset of metadata for a subpage allocation is found at the end
+ * of the subpage */
+#define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
+
+/* This is the length of metadata in bits.  It consists of two bits
+ * for every BITMAP_GRANULARITY of usable bytes in the page, then two
+ * bits for the tailer.. */
+#define BITMAP_METABITLEN                                              \
+    ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
+
+/* This is the length in bytes. */
+#define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
+
+static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
+{
+       unsigned int pagestatelen;
+
+       pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
+                                      CHAR_BIT),
+                               ALIGNOF(struct metaheader));
+       return (struct metaheader *)(get_page_statebits(pool) + pagestatelen);
+}
+
+static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
+{
+       if (!mh->next)
+               return NULL;
+
+       return (struct metaheader *)((char *)pool + mh->next);
+}
+
+static unsigned long pool_offset(void *pool, void *p)
+{
+       return (char *)p - (char *)pool;
+}
+
+void alloc_init(void *pool, unsigned long poolsize)
+{
+       /* FIXME: Alignment assumptions about pool. */
+       unsigned long len, i;
+       struct metaheader *mh;
+
+       if (poolsize < MIN_SIZE)
+               return;
+
+       mh = first_mheader(pool, poolsize);
+
+       /* Mark all page states FREE, all uniform caches zero, and all of
+        * metaheader bitmap which takes rest of first page. */
+       len = align_up(pool_offset(pool, mh + 1), getpagesize());
+       BUILD_ASSERT(FREE == 0);
+       memset(pool, 0, len);
+
+       /* Mark the pagestate and metadata page(s) allocated. */
+       set_page_state(pool, 0, TAKEN_START);
+       for (i = 1; i < div_up(len, getpagesize()); i++)
+               set_page_state(pool, i, TAKEN);
+}
+
+/* Two bits per element, representing page states.  Returns 0 on fail.
+ * off is used to allocate from subpage bitmaps, which use the first 2
+ * bits as the type, so the real bitmap is offset by 1. */
+static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
+                                      unsigned long elems,
+                                      unsigned long want, unsigned long align)
+{
+       long i;
+       unsigned long free;
+
+       free = 0;
+       /* We allocate from far end, to increase ability to expand metadata. */
+       for (i = elems - 1; i >= 0; i--) {
+               switch (get_bit_pair(bits, off+i)) {
+               case FREE:
+                       if (++free >= want) {
+                               unsigned long j;
+
+                               /* They might ask for large alignment. */
+                               if (align && i % align)
+                                       continue;
+
+                               set_bit_pair(bits, off+i, TAKEN_START);
+                               for (j = i+1; j < i + want; j++)
+                                       set_bit_pair(bits, off+j, TAKEN);
+                               return off+i;
+                       }
+                       break;
+               case SPECIAL:
+               case TAKEN_START:
+               case TAKEN:
+                       free = 0;
+                       break;
+               }
+       }
+
+       return 0;
+}
+
+static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
+                                    unsigned long pages, unsigned long align)
+{
+       return alloc_from_bitmap(get_page_statebits(pool),
+                                0, poolsize / getpagesize(), pages,
+                                align / getpagesize());
+}
+
+/* Offset to metadata is at end of page. */
+static unsigned long *metadata_off(void *pool, unsigned long page)
+{
+       return (unsigned long *)
+               ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
+}
+
+static uint8_t *get_page_metadata(void *pool, unsigned long page)
+{
+       return (uint8_t *)pool + *metadata_off(pool, page);
+}
+
+static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
+{
+       *metadata_off(pool, page) = meta - (uint8_t *)pool;
+}
+
+static unsigned long sub_page_alloc(void *pool, unsigned long page,
+                                   unsigned long size, unsigned long align)
+{
+       uint8_t *bits = get_page_metadata(pool, page);
+       unsigned long i;
+       enum sub_metadata_type type;
+
+       type = get_bit_pair(bits, 0);
+
+       /* If this is a uniform page, we can't allocate from it. */
+       if (type == UNIFORM)
+               return 0;
+
+       assert(type == BITMAP);
+
+       /* We use a standart bitmap, but offset because of that BITMAP
+        * header. */
+       i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
+                             div_up(size, BITMAP_GRANULARITY),
+                             align / BITMAP_GRANULARITY);
+
+       /* Can't allocate? */
+       if (i == 0)
+               return 0;
+
+       /* i-1 because of the header. */
+       return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
+}
+
+/* We look at the page states to figure out where the allocation for this
+ * metadata ends. */
+static unsigned long get_metalen(void *pool, unsigned long poolsize,
+                                struct metaheader *mh)
+{
+       unsigned long i, first, pages = poolsize / getpagesize();
+
+       first = pool_offset(pool, mh + 1)/getpagesize();
+
+       for (i = first + 1; i < pages && get_page_state(pool,i) == TAKEN; i++);
+
+       return i * getpagesize() - pool_offset(pool, mh + 1);
+}
+
+static unsigned int uniform_metalen(unsigned int usize)
+{
+       unsigned int metalen;
+
+       assert(usize < (1 << 14));
+
+       /* Two bits for the header, 14 bits for size, then one bit for each
+        * element the page can hold.  Round up to number of bytes. */
+       metalen = div_up(2 + 14 + SUBPAGE_METAOFF / usize, CHAR_BIT);
+
+       /* To ensure metaheader is always aligned, round bytes up. */
+       metalen = align_up(metalen, ALIGNOF(struct metaheader));
+
+       return metalen;
+}
+
+static unsigned int decode_usize(uint8_t *meta)
+{
+       return ((unsigned)meta[1] << (CHAR_BIT-2)) | (meta[0] >> 2);
+}
+
+static void encode_usize(uint8_t *meta, unsigned int usize)
+{
+       meta[0] = (UNIFORM | (usize << 2));
+       meta[1] = (usize >> (CHAR_BIT - 2));
+}
+
+static uint8_t *alloc_metaspace(void *pool, unsigned long poolsize,
+                               struct metaheader *mh, unsigned long bytes,
+                               enum sub_metadata_type type)
+{
+       uint8_t *meta = (uint8_t *)(mh + 1);
+       unsigned long free = 0, len, i, metalen;
+
+       metalen = get_metalen(pool, poolsize, mh);
+
+       /* Walk through metadata looking for free. */
+       for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
+               switch (get_bit_pair(meta, i)) {
+               case FREE:
+                       len = 1;
+                       free++;
+                       if (free == bytes * METADATA_PER_BYTE) {
+                               /* Mark this as a bitmap. */
+                               set_bit_pair(meta, i - free + 1, type);
+                               return meta + (i - free + 1)/METADATA_PER_BYTE;
+                       }
+                       break;
+               case BITMAP:
+                       /* Skip over this allocated part. */
+                       len = BITMAP_METALEN * METADATA_PER_BYTE;
+                       free = 0;
+                       break;
+               case UNIFORM:
+                       /* Figure metalen given usize. */
+                       len = decode_usize(meta + i / METADATA_PER_BYTE);
+                       len = uniform_metalen(len) * METADATA_PER_BYTE;
+                       free = 0;
+                       break;
+               default:
+                       assert(0);
+                       return NULL;
+               }
+       }
+       return NULL;
+}
+
+/* We need this many bytes of metadata. */
+static uint8_t *new_metadata(void *pool, unsigned long poolsize,
+                            unsigned long bytes, enum sub_metadata_type type)
+{
+       struct metaheader *mh, *newmh;
+       unsigned long page;
+       uint8_t *meta;
+
+       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh))
+               if ((meta = alloc_metaspace(pool, poolsize, mh, bytes, type)))
+                       return meta;
+
+       /* No room for metadata?  Can we expand an existing one? */
+       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+               unsigned long nextpage;
+
+               /* We start on this page. */
+               nextpage = pool_offset(pool, (char *)(mh+1))/getpagesize();
+               /* Iterate through any other pages we own. */
+               while (get_page_state(pool, ++nextpage) == TAKEN);
+
+               /* Now, can we grab that page? */
+               if (get_page_state(pool, nextpage) != FREE)
+                       continue;
+
+               /* OK, expand metadata, do it again. */
+               set_page_state(pool, nextpage, TAKEN);
+               BUILD_ASSERT(FREE == 0);
+               memset((char *)pool + nextpage*getpagesize(), 0, getpagesize());
+               return alloc_metaspace(pool, poolsize, mh, bytes, type);
+       }
+
+       /* No metadata left at all? */
+       page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
+       if (!page)
+               return NULL;
+
+       newmh = (struct metaheader *)((char *)pool + page * getpagesize());
+       BUILD_ASSERT(FREE == 0);
+       memset(newmh + 1, 0, getpagesize() - sizeof(*mh));
+
+       /* Sew it into linked list */
+       mh = first_mheader(pool,poolsize);
+       newmh->next = mh->next;
+       mh->next = pool_offset(pool, newmh);
+
+       return alloc_metaspace(pool, poolsize, newmh, bytes, type);
+}
+
+static void alloc_free_pages(void *pool, unsigned long pagenum)
+{
+       assert(get_page_state(pool, pagenum) == TAKEN_START);
+       set_page_state(pool, pagenum, FREE);
+       while (get_page_state(pool, ++pagenum) == TAKEN)
+               set_page_state(pool, pagenum, FREE);
+}
+
+static void maybe_transform_uniform_page(void *pool, unsigned long offset)
+{
+       /* FIXME: If possible and page isn't full, change to a bitmap */
+}
+
+/* Returns 0 or the size of the uniform alloc to use */
+static unsigned long suitable_for_uc(unsigned long size, unsigned long align)
+{
+       unsigned long num_elems, wastage, usize;
+       unsigned long bitmap_cost;
+
+       if (size == 0)
+               size = 1;
+
+       /* Fix up silly alignments. */
+       usize = align_up(size, align);
+
+       /* How many can fit in this page? */
+       num_elems = SUBPAGE_METAOFF / usize;
+
+       /* Can happen with bigger alignments. */
+       if (!num_elems)
+               return 0;
+
+       /* Usize maxes out at 14 bits. */
+       if (usize >= (1 << 14))
+               return 0;
+
+       /* How many bytes would be left at the end? */
+       wastage = SUBPAGE_METAOFF % usize;
+
+       /* If we can get a larger allocation within alignment constraints, we
+        * should do it, otherwise might as well leave wastage at the end. */
+       usize += align_down(wastage / num_elems, align);
+
+       /* Bitmap allocation costs 2 bits per BITMAP_GRANULARITY bytes, plus
+        * however much we waste in rounding up to BITMAP_GRANULARITY. */
+       bitmap_cost = 2 * div_up(size, BITMAP_GRANULARITY)
+               + CHAR_BIT * (align_up(size, BITMAP_GRANULARITY) - size);
+
+       /* Our cost is 1 bit, plus usize overhead */
+       if (bitmap_cost < 1 + (usize - size) * CHAR_BIT)
+               return 0;
+
+       return usize;
+}
+
+static unsigned long uniform_alloc(void *pool, unsigned long poolsize,
+                                  struct uniform_cache *uc,
+                                  unsigned long ucnum)
+{
+       uint8_t *metadata = get_page_metadata(pool, uc->page[ucnum]) + 2;
+       unsigned long i, max;
+
+       /* Simple one-bit-per-object bitmap. */
+       max = SUBPAGE_METAOFF / uc->size[ucnum];
+       for (i = 0; i < max; i++) {
+               if (!(metadata[i / CHAR_BIT] & (1 << (i % CHAR_BIT)))) {
+                       metadata[i / CHAR_BIT] |= (1 << (i % CHAR_BIT));
+                       return uc->page[ucnum] * getpagesize()
+                               + i * uc->size[ucnum];
+               }
+       }
+
+       return 0;
+}
+
+static unsigned long new_uniform_page(void *pool, unsigned long poolsize,
+                                     unsigned long usize)
+{
+       unsigned long page, metalen;
+       uint8_t *metadata;
+
+       page = alloc_get_pages(pool, poolsize, 1, 1);
+       if (page == 0)
+               return 0;
+
+       metalen = uniform_metalen(usize);
+
+       /* Get metadata for page. */
+       metadata = new_metadata(pool, poolsize, metalen, UNIFORM);
+       if (!metadata) {
+               alloc_free_pages(pool, page);
+               return 0;
+       }
+
+       encode_usize(metadata, usize);
+
+       BUILD_ASSERT(FREE == 0);
+       memset(metadata + 2, 0, metalen - 2);
+
+       /* Actually, this is a subpage page now. */
+       set_page_state(pool, page, SPECIAL);
+
+       /* Set metadata pointer for page. */
+       set_page_metadata(pool, page, metadata);
+
+       return page;
+}
+
+static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
+                                   unsigned long size, unsigned long align)
+{
+       unsigned long i, usize;
+       uint8_t *metadata;
+       struct uniform_cache *uc = pool;
+
+       usize = suitable_for_uc(size, align);
+       if (usize) {
+               /* Look for a uniform page. */
+               for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
+                       if (uc->size[i] == usize) {
+                               unsigned long ret;
+                               ret = uniform_alloc(pool, poolsize, uc, i);
+                               if (ret != 0)
+                                       return ret;
+                               /* OK, that one is full, remove from cache. */
+                               uc->size[i] = 0;
+                               break;
+                       }
+               }
+
+               /* OK, try a new uniform page.  Use random discard for now. */
+               i = random() % UNIFORM_CACHE_NUM;
+               maybe_transform_uniform_page(pool, uc->page[i]);
+
+               uc->page[i] = new_uniform_page(pool, poolsize, usize);
+               if (uc->page[i]) {
+                       uc->size[i] = usize;
+                       return uniform_alloc(pool, poolsize, uc, i);
+               }
+               uc->size[i] = 0;
+       }
+
+       /* Look for partial page. */
+       for (i = 0; i < poolsize / getpagesize(); i++) {
+               unsigned long ret;
+               if (get_page_state(pool, i) != SPECIAL)
+                       continue;
+
+               ret = sub_page_alloc(pool, i, size, align);
+               if (ret)
+                       return ret;
+       }
+
+       /* Create new SUBPAGE page. */
+       i = alloc_get_pages(pool, poolsize, 1, 1);
+       if (i == 0)
+               return 0;
+
+       /* Get metadata for page. */
+       metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
+       if (!metadata) {
+               alloc_free_pages(pool, i);
+               return 0;
+       }
+
+       /* Actually, this is a subpage page now. */
+       set_page_state(pool, i, SPECIAL);
+
+       /* Set metadata pointer for page. */
+       set_page_metadata(pool, i, metadata);
+
+       /* Do allocation like normal */
+       return sub_page_alloc(pool, i, size, align);
+}
+
+static bool bitmap_page_is_empty(uint8_t *meta)
+{
+       unsigned int i;
+
+       /* Skip the header (first bit of metadata). */
+       for (i = 1; i < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; i++)
+               if (get_bit_pair(meta, i) != FREE)
+                       return false;
+
+       return true;
+}
+
+static bool uniform_page_is_empty(uint8_t *meta)
+{
+       unsigned int i, metalen;
+
+       metalen = uniform_metalen(decode_usize(meta));
+
+       /* Skip the header (first two bytes of metadata). */
+       for (i = 2; i < metalen + 2; i++) {
+               BUILD_ASSERT(FREE == 0);
+               if (meta[i])
+                       return false;
+       }
+       return true;
+}
+
+static bool special_page_is_empty(void *pool, unsigned long page)
+{
+       uint8_t *meta;
+       enum sub_metadata_type type;
+
+       meta = get_page_metadata(pool, page);
+       type = get_bit_pair(meta, 0);
+
+       switch (type) {
+       case UNIFORM:
+               return uniform_page_is_empty(meta);
+       case BITMAP:
+               return bitmap_page_is_empty(meta);
+       default:
+               assert(0);
+       }
+}
+
+static void clear_special_metadata(void *pool, unsigned long page)
+{
+       uint8_t *meta;
+       enum sub_metadata_type type;
+
+       meta = get_page_metadata(pool, page);
+       type = get_bit_pair(meta, 0);
+
+       switch (type) {
+       case UNIFORM:
+               /* First two bytes are the header, rest is already FREE */
+               BUILD_ASSERT(FREE == 0);
+               memset(meta, 0, 2);
+               break;
+       case BITMAP:
+               /* First two bits is the header. */
+               BUILD_ASSERT(BITMAP_METALEN > 1);
+               meta[0] = 0;
+               break;
+       default:
+               assert(0);
+       }
+}
+
+/* Returns true if we cleaned any pages. */
+static bool clean_empty_subpages(void *pool, unsigned long poolsize)
+{
+       unsigned long i;
+       bool progress = false;
+
+       for (i = 0; i < poolsize/getpagesize(); i++) {
+               if (get_page_state(pool, i) != SPECIAL)
+                       continue;
+
+               if (special_page_is_empty(pool, i)) {
+                       clear_special_metadata(pool, i);
+                       set_page_state(pool, i, FREE);
+                       progress = true;
+               }
+       }
+       return progress;
+}
+
+/* Returns true if we cleaned any pages. */
+static bool clean_metadata(void *pool, unsigned long poolsize)
+{
+       struct metaheader *mh, *prev_mh = NULL;
+       bool progress = false;
+
+       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+               uint8_t *meta;
+               long i;
+               unsigned long metalen = get_metalen(pool, poolsize, mh);
+
+               meta = (uint8_t *)(mh + 1);
+               BUILD_ASSERT(FREE == 0);
+               for (i = metalen - 1; i > 0; i--)
+                       if (meta[i] != 0)
+                               break;
+
+               /* Completely empty? */
+               if (prev_mh && i == metalen) {
+                       alloc_free_pages(pool,
+                                        pool_offset(pool, mh)/getpagesize());
+                       prev_mh->next = mh->next;
+                       mh = prev_mh;
+                       progress = true;
+               } else {
+                       uint8_t *p;
+
+                       /* Some pages at end are free? */
+                       for (p = (uint8_t *)(mh+1) + metalen - getpagesize();
+                            p > meta + i;
+                            p -= getpagesize()) {
+                               set_page_state(pool,
+                                              pool_offset(pool, p)
+                                              / getpagesize(),
+                                              FREE);
+                               progress = true;
+                       }
+               }
+       }
+
+       return progress;
+}
+
+void *alloc_get(void *pool, unsigned long poolsize,
+               unsigned long size, unsigned long align)
+{
+       bool subpage_clean = false, metadata_clean = false;
+       unsigned long ret;
+
+       if (poolsize < MIN_SIZE)
+               return NULL;
+
+again:
+       /* Sub-page allocations have an overhead of ~12%. */
+       if (size + size/8 >= getpagesize() || align >= getpagesize()) {
+               unsigned long pages = div_up(size, getpagesize());
+
+               ret = alloc_get_pages(pool, poolsize, pages, align)
+                       * getpagesize();
+       } else
+               ret = alloc_sub_page(pool, poolsize, size, align);
+
+       if (ret != 0)
+               return (char *)pool + ret;
+
+       /* Allocation failed: garbage collection. */
+       if (!subpage_clean) {
+               subpage_clean = true;
+               if (clean_empty_subpages(pool, poolsize))
+                       goto again;
+       }
+
+       if (!metadata_clean) {
+               metadata_clean = true;
+               if (clean_metadata(pool, poolsize))
+                       goto again;
+       }
+
+       /* FIXME: Compact metadata? */
+       return NULL;
+}
+
+static void bitmap_free(void *pool, unsigned long pagenum, unsigned long off,
+                       uint8_t *metadata)
+{
+       assert(off % BITMAP_GRANULARITY == 0);
+
+       off /= BITMAP_GRANULARITY;
+
+       /* Offset by one because first bit is used for header. */
+       off++;
+
+       set_bit_pair(metadata, off++, FREE);
+       while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
+              && get_bit_pair(metadata, off) == TAKEN)
+               set_bit_pair(metadata, off++, FREE);
+}
+
+static void uniform_free(void *pool, unsigned long pagenum, unsigned long off,
+                        uint8_t *metadata)
+{
+       unsigned int usize, bit;
+
+       usize = decode_usize(metadata);
+       /* Must have been this size. */
+       assert(off % usize == 0);
+       bit = off / usize;
+
+       /* Skip header. */
+       metadata += 2;
+
+       /* Must have been allocated. */
+       assert(metadata[bit / CHAR_BIT] & (1 << (bit % CHAR_BIT)));
+       metadata[bit / CHAR_BIT] &= ~(1 << (bit % CHAR_BIT));
+}
+
+static void subpage_free(void *pool, unsigned long pagenum, void *free)
+{
+       unsigned long off = (unsigned long)free % getpagesize();
+       uint8_t *metadata = get_page_metadata(pool, pagenum);
+       enum sub_metadata_type type;
+
+       type = get_bit_pair(metadata, 0);
+
+       assert(off < SUBPAGE_METAOFF);
+
+       switch (type) {
+       case BITMAP:
+               bitmap_free(pool, pagenum, off, metadata);
+               break;
+       case UNIFORM:
+               uniform_free(pool, pagenum, off, metadata);
+               break;
+       default:
+               assert(0);
+       }
+}
+
+void alloc_free(void *pool, unsigned long poolsize, void *free)
+{
+       unsigned long pagenum;
+       struct metaheader *mh;
+
+       if (!free)
+               return;
+
+       assert(poolsize >= MIN_SIZE);
+
+       mh = first_mheader(pool, poolsize);
+       assert((char *)free >= (char *)(mh + 1));
+       assert((char *)pool + poolsize > (char *)free);
+
+       pagenum = pool_offset(pool, free) / getpagesize();
+
+       if (get_page_state(pool, pagenum) == SPECIAL)
+               subpage_free(pool, pagenum, free);
+       else {
+               assert((unsigned long)free % getpagesize() == 0);
+               alloc_free_pages(pool, pagenum);
+       }
+}
+
+static bool is_metadata_page(void *pool, unsigned long poolsize,
+                            unsigned long page)
+{
+       struct metaheader *mh;
+
+       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+               unsigned long start, end;
+
+               start = pool_offset(pool, mh);
+               end = pool_offset(pool, (char *)(mh+1)
+                                 + get_metalen(pool, poolsize, mh));
+               if (page >= start/getpagesize() && page < end/getpagesize())
+                       return true;
+       }
+       return false;
+}
+
+static bool check_bitmap_metadata(void *pool, unsigned long *mhoff)
+{
+       enum alloc_state last_state = FREE;
+       unsigned int i;
+
+       for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
+               enum alloc_state state;
+
+               /* +1 because header is the first byte. */
+               state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
+               switch (state) {
+               case SPECIAL:
+                       return false;
+               case TAKEN:
+                       if (last_state == FREE)
+                               return false;
+                       break;
+               default:
+                       break;
+               }
+               last_state = state;
+       }
+       return true;
+}
+
+static bool check_uniform_metadata(void *pool, unsigned long *mhoff)
+{
+       uint8_t *meta = (uint8_t *)pool + *mhoff;
+       unsigned int i, usize;
+       struct uniform_cache *uc = pool;
+
+       usize = decode_usize(meta);
+       if (usize == 0 || suitable_for_uc(usize, 1) != usize)
+               return false;
+
+       /* If it's in uniform cache, make sure that agrees on size. */
+       for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
+               uint8_t *ucm;
+
+               if (!uc->size[i])
+                       continue;
+
+               ucm = get_page_metadata(pool, uc->page[i]);
+               if (ucm != meta)
+                       continue;
+
+               if (usize != uc->size[i])
+                       return false;
+       }
+       return true;
+}
+
+static bool check_subpage(void *pool, unsigned long poolsize,
+                         unsigned long page)
+{
+       unsigned long *mhoff = metadata_off(pool, page);
+
+       if (*mhoff + sizeof(struct metaheader) > poolsize)
+               return false;
+
+       if (*mhoff % ALIGNOF(struct metaheader) != 0)
+               return false;
+
+       /* It must point to a metadata page. */
+       if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
+               return false;
+
+       /* Header at start of subpage allocation */
+       switch (get_bit_pair((uint8_t *)pool + *mhoff, 0)) {
+       case BITMAP:
+               return check_bitmap_metadata(pool, mhoff);
+       case UNIFORM:
+               return check_uniform_metadata(pool, mhoff);
+       default:
+               return false;
+       }
+
+}
+
+bool alloc_check(void *pool, unsigned long poolsize)
+{
+       unsigned long i;
+       struct metaheader *mh;
+       enum alloc_state last_state = FREE;
+       bool was_metadata = false;
+
+       if (poolsize < MIN_SIZE)
+               return true;
+
+       if (get_page_state(pool, 0) != TAKEN_START)
+               return false;
+
+       /* First check metadata pages. */
+       /* Metadata pages will be marked TAKEN. */
+       for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+               unsigned long start, end;
+
+               start = pool_offset(pool, mh);
+               if (start + sizeof(*mh) > poolsize)
+                       return false;
+
+               end = pool_offset(pool, (char *)(mh+1)
+                                 + get_metalen(pool, poolsize, mh));
+               if (end > poolsize)
+                       return false;
+
+               /* Non-first pages should start on a page boundary. */
+               if (mh != first_mheader(pool, poolsize)
+                   && start % getpagesize() != 0)
+                       return false;
+
+               /* It should end on a page boundary. */
+               if (end % getpagesize() != 0)
+                       return false;
+       }
+
+       for (i = 0; i < poolsize / getpagesize(); i++) {
+               enum alloc_state state = get_page_state(pool, i);
+               bool is_metadata = is_metadata_page(pool, poolsize,i);
+
+               switch (state) {
+               case FREE:
+                       /* metadata pages are never free. */
+                       if (is_metadata)
+                               return false;
+               case TAKEN_START:
+                       break;
+               case TAKEN:
+                       /* This should continue a previous block. */
+                       if (last_state == FREE)
+                               return false;
+                       if (is_metadata != was_metadata)
+                               return false;
+                       break;
+               case SPECIAL:
+                       /* Check metadata pointer etc. */
+                       if (!check_subpage(pool, poolsize, i))
+                               return false;
+               }
+               last_state = state;
+               was_metadata = is_metadata;
+       }
+       return true;
+}
+
+void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
+{
+       struct metaheader *mh;
+       struct uniform_cache *uc = pool;
+       unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
+       long i;
+
+       if (poolsize < MIN_SIZE) {
+               fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
+               return;
+       }
+
+       tot = 0;
+       for (i = 0; i < UNIFORM_CACHE_NUM; i++)
+               tot += (uc->size[i] != 0);
+       fprintf(out, "Uniform cache (%lu entries):\n", tot);
+       for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
+               unsigned int j, total = 0;
+               uint8_t *meta;
+
+               if (!uc->size[i])
+                       continue;
+
+               /* First two bytes are header. */
+               meta = get_page_metadata(pool, uc->page[i]) + 2;
+
+               for (j = 0; j < SUBPAGE_METAOFF / uc->size[i]; j++)
+                       if (meta[j / 8] & (1 << (j % 8)))
+                               total++;
+
+               printf("  %u: %u/%u (%u%% density)\n",
+                      uc->size[j], total, SUBPAGE_METAOFF / uc->size[i],
+                      (total * 100) / (SUBPAGE_METAOFF / uc->size[i]));
+       }
+
+       memset(count, 0, sizeof(count));
+       for (i = 0; i < poolsize / getpagesize(); i++)
+               count[get_page_state(pool, i)]++;
+
+       mh = first_mheader(pool, poolsize);
+       pagebitlen = (uint8_t *)mh - get_page_statebits(pool);
+       fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
+               pagebitlen, count[0], count[1], count[2], count[3]);
+
+       /* One metadata page for every page of page bits. */
+       metadata_pages = div_up(pagebitlen, getpagesize());
+
+       /* Now do each metadata page. */
+       for (; mh; mh = next_mheader(pool,mh)) {
+               unsigned long free = 0, bitmapblocks = 0, uniformblocks = 0,
+                       len = 0, uniformlen = 0, bitmaplen = 0, metalen;
+               uint8_t *meta = (uint8_t *)(mh + 1);
+
+               metalen = get_metalen(pool, poolsize, mh);
+               metadata_pages += (sizeof(*mh) + metalen) / getpagesize();
+
+               for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
+                       switch (get_bit_pair(meta, i)) {
+                       case FREE:
+                               len = 1;
+                               free++;
+                               break;
+                       case BITMAP:
+                               /* Skip over this allocated part. */
+                               len = BITMAP_METALEN * CHAR_BIT;
+                               bitmapblocks++;
+                               bitmaplen += len;
+                               break;
+                       case UNIFORM:
+                               /* Skip over this part. */
+                               len = decode_usize(meta + i/METADATA_PER_BYTE);
+                               len = uniform_metalen(len) * METADATA_PER_BYTE;
+                               uniformblocks++;
+                               uniformlen += len;
+                               break;
+                       default:
+                               assert(0);
+                       }
+               }
+
+               fprintf(out, "Metadata %lu-%lu: %lu free, %lu bitmapblocks, %lu uniformblocks, %lu%% density\n",
+                       pool_offset(pool, mh),
+                       pool_offset(pool, (char *)(mh+1) + metalen),
+                       free, bitmapblocks, uniformblocks,
+                       (bitmaplen + uniformlen) * 100
+                       / (free + bitmaplen + uniformlen));
+       }
+
+       /* Account for total pages allocated. */
+       tot = (count[1] + count[2] - metadata_pages) * getpagesize();
+
+       fprintf(out, "Total metadata bytes = %lu\n",
+               metadata_pages * getpagesize());
+
+       /* Now do every subpage. */
+       for (i = 0; i < poolsize / getpagesize(); i++) {
+               uint8_t *meta;
+               unsigned int j, allocated;
+               enum sub_metadata_type type;
+
+               if (get_page_state(pool, i) != SPECIAL)
+                       continue;
+
+               memset(count, 0, sizeof(count));
+
+               meta = get_page_metadata(pool, i);
+               type = get_bit_pair(meta, 0);
+
+               if (type == BITMAP) {
+                       for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
+                               count[get_page_state(meta, j)]++;
+                       allocated = (count[1] + count[2]) * BITMAP_GRANULARITY;
+                       fprintf(out, "Subpage bitmap ");
+               } else {
+                       unsigned int usize = decode_usize(meta);
+
+                       assert(type == UNIFORM);
+                       fprintf(out, "Subpage uniform (%u) ", usize);
+                       meta += 2;
+                       for (j = 0; j < SUBPAGE_METAOFF / usize; j++)
+                               count[!!(meta[j / 8] & (1 << (j % 8)))]++;
+                       allocated = count[1] * usize;
+               }
+               fprintf(out, "%lu: FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %u%% density\n",
+                       i, count[0], count[1], count[2],
+                       allocated * 100 / getpagesize());
+               tot += allocated;
+       }
+
+       /* This is optimistic, since we overalloc in several cases. */
+       fprintf(out, "Best possible allocation density = %lu%%\n",
+               tot * 100 / poolsize);
+}
diff --git a/ccan/alloc/alloc.h b/ccan/alloc/alloc.h
new file mode 100644 (file)
index 0000000..29c29d0
--- /dev/null
@@ -0,0 +1,13 @@
+#ifndef ALLOC_H
+#define ALLOC_H
+#include <stdio.h>
+#include <stdbool.h>
+
+void alloc_init(void *pool, unsigned long poolsize);
+void *alloc_get(void *pool, unsigned long poolsize,
+               unsigned long size, unsigned long align);
+void alloc_free(void *pool, unsigned long poolsize, void *free);
+bool alloc_check(void *pool, unsigned long poolsize);
+
+void alloc_visualize(FILE *out, void *pool, unsigned long poolsize);
+#endif /* ALLOC_H */
diff --git a/ccan/alloc/test/run.c b/ccan/alloc/test/run.c
new file mode 100644 (file)
index 0000000..8cfe8b4
--- /dev/null
@@ -0,0 +1,195 @@
+#include "alloc/alloc.h"
+#include "tap/tap.h"
+#include "alloc/alloc.c"
+#include <stdlib.h>
+
+#define POOL_ORD 16
+#define POOL_SIZE (1 << POOL_ORD)
+
+#define sort(p, num, cmp) \
+       qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
+
+static int addr_cmp(void **a, void **b)
+{
+       return (*a) - (*b);
+}
+
+static bool unique(void *p[], unsigned int num)
+{
+       unsigned int i;
+
+       for (i = 1; i < num; i++)
+               if (p[i] == p[i-1])
+                       return false;
+       return true;
+}      
+
+static bool free_every_second_one(void *mem, unsigned int num, void *p[])
+{
+       unsigned int i;
+
+       /* Free every second one. */
+       for (i = 0; i < num; i += 2) {
+               alloc_free(mem, POOL_SIZE, p[i]);
+               if (!alloc_check(mem, POOL_SIZE))
+                       return false;
+       }
+       for (i = 1; i < num; i += 2) {
+               alloc_free(mem, POOL_SIZE, p[i]);
+               if (!alloc_check(mem, POOL_SIZE))
+                       return false;
+       }
+       return true;
+}
+
+
+int main(int argc, char *argv[])
+{
+       void *mem;
+       unsigned int i, num, max_size;
+       void *p[POOL_SIZE];
+
+       plan_tests(139);
+
+       /* FIXME: Needs to be page aligned for now. */
+       posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE);
+
+       /* Small pool, all allocs fail, even 0-length. */
+       alloc_init(mem, 0);
+       ok1(alloc_check(mem, 0));
+       ok1(alloc_get(mem, 0, 1, 1) == NULL);
+       ok1(alloc_get(mem, 0, 128, 1) == NULL);
+       ok1(alloc_get(mem, 0, 0, 1) == NULL);
+
+       /* Free of NULL should work. */
+       alloc_free(mem, 0, NULL);
+
+       alloc_init(mem, POOL_SIZE);
+       ok1(alloc_check(mem, POOL_SIZE));
+       /* Find largest allocation which works. */
+       for (max_size = POOL_SIZE * 2; max_size; max_size--) {
+               p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+               if (p[0])
+                       break;
+       }
+       ok1(max_size < POOL_SIZE);
+       ok1(max_size > 0);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Free it, should be able to reallocate it. */
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+       ok1(p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Allocate a whole heap. */
+       for (i = 0; i < POOL_SIZE; i++) {
+               p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
+               if (!p[i])
+                       break;
+       }
+
+       /* Uncomment this for a more intuitive view of what the
+        * allocator looks like after all these 1 byte allocs. */
+#if 0
+       alloc_visualize(stderr, mem, POOL_SIZE);
+#endif
+
+       num = i;
+       /* Can't allocate this many. */
+       ok1(num != POOL_SIZE);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Sort them. */
+       sort(p, num, addr_cmp);
+
+       /* Uniqueness check */
+       ok1(unique(p, num));
+
+       ok1(free_every_second_one(mem, num, p));
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Should be able to reallocate max size. */
+       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+       ok1(p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Re-initializing should be the same as freeing everything */
+       alloc_init(mem, POOL_SIZE);
+       ok1(alloc_check(mem, POOL_SIZE));
+       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+       ok1(p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Alignment constraints should be met, as long as powers of two */
+       for (i = 0; i < POOL_ORD-1; i++) {
+               p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
+               ok1(p[i]);
+               ok1(((unsigned long)p[i] % (1 << i)) == 0);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+
+       for (i = 0; i < POOL_ORD-1; i++) {
+               alloc_free(mem, POOL_SIZE, p[i]);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+
+       /* Alignment constraints for a single-byte allocation. */
+       for (i = 0; i < POOL_ORD; i++) {
+               p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
+               ok1(p[0]);
+               ok1(alloc_check(mem, POOL_SIZE));
+               alloc_free(mem, POOL_SIZE, p[0]);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+
+       /* Alignment check for a 0-byte allocation.  Corner case. */
+       p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (POOL_ORD - 1));
+       ok1(alloc_check(mem, POOL_SIZE));
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Force the testing of split metadata. */
+       alloc_init(mem, POOL_SIZE);
+       for (i = 0; i < POOL_SIZE; i++) {
+               p[i] = alloc_get(mem, POOL_SIZE, getpagesize(), getpagesize());
+               if (!p[i])
+                       break;
+       }
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Sort them. */
+       sort(p, i-1, addr_cmp);
+
+       /* Free all but the one next to the metadata. */
+       for (i = 1; p[i]; i++)
+               alloc_free(mem, POOL_SIZE, p[i]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Now do a whole heap of subpage allocs. */
+       for (i = 1; i < POOL_SIZE; i++) {
+               p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
+               if (!p[i])
+                       break;
+       }
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Free up our page next to metadata, and should be able to alloc */
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+       p[0] = alloc_get(mem, POOL_SIZE, 1, 1);
+       ok1(p[0]);
+
+       /* Clean up. */
+       for (i = 0; p[i]; i++)
+               alloc_free(mem, POOL_SIZE, p[i]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       return exit_status();
+}
diff --git a/ccan/build_assert/_info.c b/ccan/build_assert/_info.c
new file mode 100644 (file)
index 0000000..555aae2
--- /dev/null
@@ -0,0 +1,38 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * build_assert - routines for build-time assertions
+ *
+ * This code provides routines which will cause compilation to fail should some
+ * assertion be untrue: such failures are preferable to run-time assertions,
+ * but much more limited since they can only depends on compile-time constants.
+ *
+ * These assertions are most useful when two parts of the code must be kept in
+ * sync: it is better to avoid such cases if possible, but seconds best is to
+ * detect invalid changes at build time.
+ *
+ * For example, a tricky piece of code might rely on a certain element being at
+ * the start of the structure.  To ensure that future changes don't break it,
+ * you would catch such changes in your code like so:
+ *
+ * Example:
+ *     char *foo_string(struct foo *foo)
+ *     {
+ *             // This trick requires that the string be first in the structure
+ *             BUILD_ASSERT(offsetof(struct foo, string) == 0);
+ *             return (char *)foo;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0)
+               /* Nothing. */
+               return 0;
+
+       return 1;
+}
diff --git a/ccan/build_assert/build_assert.h b/ccan/build_assert/build_assert.h
new file mode 100644 (file)
index 0000000..4b0d75e
--- /dev/null
@@ -0,0 +1,37 @@
+#ifndef CCAN_BUILD_ASSERT_H
+#define CCAN_BUILD_ASSERT_H
+
+/**
+ * BUILD_ASSERT - assert a build-time dependency.
+ * @cond: the compile-time condition which must be true.
+ *
+ * Your compile will fail if the condition isn't true, or can't be evaluated
+ * by the compiler.  This can only be used within a function.
+ *
+ * Example:
+ *     char *foo_to_char(struct foo *foo)
+ *     {
+ *             // This code needs string to be at start of foo.
+ *             BUILD_ASSERT(offsetof(struct foo, string) == 0);
+ *             return (char *)foo;
+ *     }
+ */
+#define BUILD_ASSERT(cond) \
+       do { (void) sizeof(char [1 - 2*!(cond)]); } while(0)
+
+/**
+ * EXPR_BUILD_ASSERT - assert a build-time dependency, as an expression.
+ * @cond: the compile-time condition which must be true.
+ *
+ * Your compile will fail if the condition isn't true, or can't be evaluated
+ * by the compiler.  This can be used in an expression: its value is "0".
+ *
+ * Example:
+ *     #define foo_to_char(foo)                                        \
+ *              ((char *)(foo)                                         \
+ *               + EXPR_BUILD_ASSERT(offsetof(struct foo, string) == 0))
+ */
+#define EXPR_BUILD_ASSERT(cond) \
+       (sizeof(char [1 - 2*!(cond)]) - 1)
+
+#endif /* CCAN_BUILD_ASSERT_H */
diff --git a/ccan/build_assert/test/compile_fail-expr.c b/ccan/build_assert/test/compile_fail-expr.c
new file mode 100644 (file)
index 0000000..41cdc0f
--- /dev/null
@@ -0,0 +1,10 @@
+#include "build_assert/build_assert.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+       return EXPR_BUILD_ASSERT(1 == 0);
+#else
+       return 0;
+#endif
+}
diff --git a/ccan/build_assert/test/compile_fail.c b/ccan/build_assert/test/compile_fail.c
new file mode 100644 (file)
index 0000000..a6867db
--- /dev/null
@@ -0,0 +1,9 @@
+#include "build_assert/build_assert.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+       BUILD_ASSERT(1 == 0);
+#endif
+       return 0;
+}
diff --git a/ccan/build_assert/test/compile_ok.c b/ccan/build_assert/test/compile_ok.c
new file mode 100644 (file)
index 0000000..bc5541f
--- /dev/null
@@ -0,0 +1,7 @@
+#include "build_assert/build_assert.h"
+
+int main(int argc, char *argv[])
+{
+       BUILD_ASSERT(1 == 1);
+       return 0;
+}
diff --git a/ccan/build_assert/test/run-EXPR_BUILD_ASSERT.c b/ccan/build_assert/test/run-EXPR_BUILD_ASSERT.c
new file mode 100644 (file)
index 0000000..7fd0c49
--- /dev/null
@@ -0,0 +1,9 @@
+#include "build_assert/build_assert.h"
+#include "tap/tap.h"
+
+int main(int argc, char *argv[])
+{
+       plan_tests(1);
+       ok1(EXPR_BUILD_ASSERT(1 == 1) == 0);
+       return exit_status();
+}
diff --git a/ccan/check_type/_info.c b/ccan/check_type/_info.c
new file mode 100644 (file)
index 0000000..176e445
--- /dev/null
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * check_type - routines for compile time type checking
+ *
+ * C has fairly weak typing: ints get automatically converted to longs, signed
+ * to unsigned, etc.  There are some cases where this is best avoided, and
+ * these macros provide methods for evoking warnings (or build errors) when
+ * a precise type isn't used.
+ *
+ * On compilers which don't support typeof() these routines are less effective,
+ * since they have to use sizeof() which can only distiguish between types of
+ * different size.
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+#if !HAVE_TYPEOF
+               printf("ccan/build_assert\n");
+#endif
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/check_type/check_type.h b/ccan/check_type/check_type.h
new file mode 100644 (file)
index 0000000..e05236f
--- /dev/null
@@ -0,0 +1,63 @@
+#ifndef CCAN_CHECK_TYPE_H
+#define CCAN_CHECK_TYPE_H
+#include "config.h"
+
+/**
+ * check_type - issue a warning or build failure if type is not correct.
+ * @expr: the expression whose type we should check (not evaluated).
+ * @type: the exact type we expect the expression to be.
+ *
+ * This macro is usually used within other macros to try to ensure that a macro
+ * argument is of the expected type.  No type promotion of the expression is
+ * done: an unsigned int is not the same as an int!
+ *
+ * check_type() always evaluates to 1.
+ *
+ * If your compiler does not support typeof, then the best we can do is fail
+ * to compile if the sizes of the types are unequal (a less complete check).
+ *
+ * Example:
+ *     // They should always pass a 64-bit value to _set_some_value!
+ *     #define set_some_value(expr)                    \
+ *             _set_some_value((check_type((expr), uint64_t), (expr)))
+ */
+
+/**
+ * check_types_match - issue a warning or build failure if types are not same.
+ * @expr1: the first expression (not evaluated).
+ * @expr2: the second expression (not evaluated).
+ *
+ * This macro is usually used within other macros to try to ensure that
+ * arguments are of identical types.  No type promotion of the expressions is
+ * done: an unsigned int is not the same as an int!
+ *
+ * check_types_match() always evaluates to 1.
+ *
+ * If your compiler does not support typeof, then the best we can do is fail
+ * to compile if the sizes of the types are unequal (a less complete check).
+ *
+ * Example:
+ *     // Do subtraction to get to enclosing type, but make sure that
+ *     // pointer is of correct type for that member. 
+ *     #define container_of(mbr_ptr, encl_type, mbr)                   \
+ *             (check_types_match((mbr_ptr), &((encl_type *)0)->mbr),  \
+ *              ((encl_type *)                                         \
+ *               ((char *)(mbr_ptr) - offsetof(enclosing_type, mbr))))
+ */
+#if HAVE_TYPEOF
+#define check_type(expr, type)                 \
+       ((typeof(expr) *)0 != (type *)0)
+
+#define check_types_match(expr1, expr2)                \
+       ((typeof(expr1) *)0 != (typeof(expr2) *)0)
+#else
+#include "build_assert/build_assert.h"
+/* Without typeof, we can only test the sizes. */
+#define check_type(expr, type)                                 \
+       EXPR_BUILD_ASSERT(sizeof(expr) == sizeof(type))
+
+#define check_types_match(expr1, expr2)                                \
+       EXPR_BUILD_ASSERT(sizeof(expr1) == sizeof(expr2))
+#endif /* HAVE_TYPEOF */
+
+#endif /* CCAN_CHECK_TYPE_H */
diff --git a/ccan/check_type/test/compile_fail-check_type.c b/ccan/check_type/test/compile_fail-check_type.c
new file mode 100644 (file)
index 0000000..d19fe86
--- /dev/null
@@ -0,0 +1,9 @@
+#include "check_type/check_type.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+       check_type(argc, char);
+#endif
+       return 0;
+}
diff --git a/ccan/check_type/test/compile_fail-check_type_unsigned.c b/ccan/check_type/test/compile_fail-check_type_unsigned.c
new file mode 100644 (file)
index 0000000..6b18acb
--- /dev/null
@@ -0,0 +1,14 @@
+#include "check_type/check_type.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+#if HAVE_TYPEOF
+       check_type(argc, unsigned int);
+#else
+       /* This doesn't work without typeof, so just fail */
+#error "Fail without typeof"
+#endif
+#endif
+       return 0;
+}
diff --git a/ccan/check_type/test/compile_fail-check_types_match.c b/ccan/check_type/test/compile_fail-check_types_match.c
new file mode 100644 (file)
index 0000000..bc1f9c3
--- /dev/null
@@ -0,0 +1,10 @@
+#include "check_type/check_type.h"
+
+int main(int argc, char *argv[])
+{
+       unsigned char x = argc;
+#ifdef FAIL
+       check_types_match(argc, x);
+#endif
+       return x;
+}
diff --git a/ccan/check_type/test/run.c b/ccan/check_type/test/run.c
new file mode 100644 (file)
index 0000000..f4b33c1
--- /dev/null
@@ -0,0 +1,22 @@
+#include "check_type/check_type.h"
+#include "tap/tap.h"
+
+int main(int argc, char *argv[])
+{
+       int x = 0, y = 0;
+
+       plan_tests(9);
+
+       ok1(check_type(argc, int) == 0);
+       ok1(check_type(&argc, int *) == 0);
+       ok1(check_types_match(argc, argc) == 0);
+       ok1(check_types_match(argc, x) == 0);
+       ok1(check_types_match(&argc, &x) == 0);
+
+       ok1(check_type(x++, int) == 0);
+       ok(x == 0, "check_type does not evaluate expression");
+       ok1(check_types_match(x++, y++) == 0);
+       ok(x == 0 && y == 0, "check_types_match does not evaluate expressions");
+
+       return exit_status();
+}
diff --git a/ccan/container_of/_info.c b/ccan/container_of/_info.c
new file mode 100644 (file)
index 0000000..96c12d8
--- /dev/null
@@ -0,0 +1,47 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * container_of - routine for upcasting
+ *
+ * It is often convenient to create code where the caller registers a pointer
+ * to a generic structure and a callback.  The callback might know that the
+ * pointer points to within a larger structure, and container_of gives a
+ * convenient and fairly type-safe way of returning to the enclosing structure.
+ *
+ * This idiom is an alternative to providing a void * pointer for every
+ * callback.
+ *
+ * Example:
+ *     struct info
+ *     {
+ *             int my_stuff;
+ *             struct timer timer;
+ *     };
+ *
+ *     static void my_timer_callback(struct timer *timer)
+ *     {
+ *             struct info *info = container_of(timer, struct info, timer);
+ *             printf("my_stuff is %u\n", info->my_stuff);
+ *     }
+ *
+ *     int main()
+ *     {
+ *             struct info info = { .my_stuff = 1 };
+ *
+ *             register_timer(&info.timer);
+ *             ...
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/check_type\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/container_of/container_of.h b/ccan/container_of/container_of.h
new file mode 100644 (file)
index 0000000..1f4b18e
--- /dev/null
@@ -0,0 +1,65 @@
+#ifndef CCAN_CONTAINER_OF_H
+#define CCAN_CONTAINER_OF_H
+#include <stddef.h>
+
+#include "config.h"
+#include "check_type/check_type.h"
+
+/**
+ * container_of - get pointer to enclosing structure
+ * @member_ptr: pointer to the structure member
+ * @containing_type: the type this member is within
+ * @member: the name of this member within the structure.
+ *
+ * Given a pointer to a member of a structure, this macro does pointer
+ * subtraction to return the pointer to the enclosing type.
+ *
+ * Example:
+ *     struct info
+ *     {
+ *             int some_other_field;
+ *             struct foo my_foo;
+ *     };
+ *
+ *     struct info *foo_to_info(struct foo *foop)
+ *     {
+ *             return container_of(foo, struct info, my_foo);
+ *     }
+ */
+#define container_of(member_ptr, containing_type, member)              \
+        ((containing_type *)                                           \
+         ((char *)(member_ptr) - offsetof(containing_type, member))    \
+         - check_types_match(*(member_ptr), ((containing_type *)0)->member))
+
+
+/**
+ * container_of_var - get pointer to enclosing structure using a variable
+ * @member_ptr: pointer to the structure member
+ * @var: a pointer to a structure of same type as this member is within
+ * @member: the name of this member within the structure.
+ *
+ * Given a pointer to a member of a structure, this macro does pointer
+ * subtraction to return the pointer to the enclosing type.
+ *
+ * Example:
+ *     struct info
+ *     {
+ *             int some_other_field;
+ *             struct foo my_foo;
+ *     };
+ *
+ *     struct info *foo_to_info(struct foo *foop)
+ *     {
+ *             struct info *i = container_of_var(foo, i, my_foo);
+ *             return i;
+ *     }
+ */
+#ifdef HAVE_TYPEOF
+#define container_of_var(member_ptr, var, member) \
+       container_of(member_ptr, typeof(*var), member)
+#else
+#define container_of_var(member_ptr, var, member) \
+       ((void *)((char *)(member_ptr) - offsetof(containing_type, member)))
+#endif
+
+#endif /* CCAN_CONTAINER_OF_H */
diff --git a/ccan/container_of/test/compile_fail-bad-type.c b/ccan/container_of/test/compile_fail-bad-type.c
new file mode 100644 (file)
index 0000000..01dfd45
--- /dev/null
@@ -0,0 +1,22 @@
+#include "container_of/container_of.h"
+#include <stdlib.h>
+
+struct foo {
+       int a;
+       char b;
+};
+
+int main(int argc, char *argv[])
+{
+       struct foo foo = { .a = 1, .b = 2 };
+       int *intp = &foo.a;
+       char *p;
+
+#ifdef FAIL
+       /* p is a char *, but this gives a struct foo * */
+       p = container_of(intp, struct foo, a);
+#else
+       p = (char *)intp;
+#endif
+       return p == NULL;
+}
diff --git a/ccan/container_of/test/compile_fail-types.c b/ccan/container_of/test/compile_fail-types.c
new file mode 100644 (file)
index 0000000..69f02da
--- /dev/null
@@ -0,0 +1,21 @@
+#include "container_of/container_of.h"
+#include <stdlib.h>
+
+struct foo {
+       int a;
+       char b;
+};
+
+int main(int argc, char *argv[])
+{
+       struct foo foo = { .a = 1, .b = 2 }, *foop;
+       int *intp = &foo.a;
+
+#ifdef FAIL
+       /* b is a char, but intp is an int * */
+       foop = container_of(intp, struct foo, b);
+#else
+       foop = NULL;
+#endif
+       return intp == NULL;
+}
diff --git a/ccan/container_of/test/compile_fail-var-types.c b/ccan/container_of/test/compile_fail-var-types.c
new file mode 100644 (file)
index 0000000..5c77679
--- /dev/null
@@ -0,0 +1,21 @@
+#include "container_of/container_of.h"
+#include <stdlib.h>
+
+struct foo {
+       int a;
+       char b;
+};
+
+int main(int argc, char *argv[])
+{
+       struct foo foo = { .a = 1, .b = 2 }, *foop;
+       int *intp = &foo.a;
+
+#ifdef FAIL
+       /* b is a char, but intp is an int * */
+       foop = container_of_var(intp, foop, b);
+#else
+       foop = NULL;
+#endif
+       return intp == NULL;
+}
diff --git a/ccan/container_of/test/run.c b/ccan/container_of/test/run.c
new file mode 100644 (file)
index 0000000..dd57204
--- /dev/null
@@ -0,0 +1,21 @@
+#include "container_of/container_of.h"
+#include "tap/tap.h"
+
+struct foo {
+       int a;
+       char b;
+};
+
+int main(int argc, char *argv[])
+{
+       struct foo foo = { .a = 1, .b = 2 };
+       int *intp = &foo.a;
+       char *charp = &foo.b;
+
+       plan_tests(4);
+       ok1(container_of(intp, struct foo, a) == &foo);
+       ok1(container_of(charp, struct foo, b) == &foo);
+       ok1(container_of_var(intp, &foo, a) == &foo);
+       ok1(container_of_var(charp, &foo, b) == &foo);
+       return exit_status();
+}
diff --git a/ccan/list/_info.c b/ccan/list/_info.c
new file mode 100644 (file)
index 0000000..dc3c3e6
--- /dev/null
@@ -0,0 +1,63 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * list - double linked list routines
+ *
+ * The list header contains routines for manipulating double linked lists.
+ * It defines two types: struct list_head used for anchoring lists, and
+ * struct list_node which is usually embedded in the structure which is placed
+ * in the list.
+ *
+ * Example:
+ *     #include <err.h>
+ *     #include "list/list.h"
+ *
+ *     struct parent {
+ *             const char *name;
+ *             struct list_head children;
+ *             unsigned int num_children;
+ *     };
+ *
+ *     struct child {
+ *             const char *name;
+ *             struct list_node list;
+ *     };
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             struct parent p;
+ *             struct child *c;
+ *             unsigned int i;
+ *
+ *             if (argc < 2)
+ *                     errx(1, "Usage: %s parent children...", argv[0]);
+ *
+ *             p.name = argv[1];
+ *             for (i = 2; i < argc, i++) {
+ *                     c = malloc(sizeof(*c));
+ *                     c->name = argv[i];
+ *                     list_add(&p.children, &c->list);
+ *                     p.num_children++;
+ *             }
+ *
+ *             printf("%s has %u children:", p.name, p.num_children);
+ *             list_for_each(&p.children, c, list)
+ *                     printf("%s ", c->name);
+ *             printf("\n");
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/container_of\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/list/list.c b/ccan/list/list.c
new file mode 100644 (file)
index 0000000..b72f8f6
--- /dev/null
@@ -0,0 +1,33 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "list/list.h"
+
+struct list_head *list_check(struct list_head *h, const char *abortstr)
+{
+       struct list_node *n, *p;
+       int count = 0;
+
+       if (h->n.next == &h->n) {
+               if (h->n.prev != &h->n) {
+                       if (!abortstr)
+                               return NULL;
+                       fprintf(stderr, "%s: prev corrupt in empty %p\n",
+                               abortstr, h);
+                       abort();
+               }
+               return h;
+       }
+
+       for (p = &h->n, n = h->n.next; n != &h->n; p = n, n = n->next) {
+               count++;
+               if (n->prev != p) {
+                       if (!abortstr)
+                               return NULL;
+                       fprintf(stderr,
+                               "%s: prev corrupt in node %p (%u) of %p\n",
+                               abortstr, n, count, h);
+                       abort();
+               }
+       }
+       return h;
+}
diff --git a/ccan/list/list.h b/ccan/list/list.h
new file mode 100644 (file)
index 0000000..c664d83
--- /dev/null
@@ -0,0 +1,253 @@
+#ifndef CCAN_LIST_H
+#define CCAN_LIST_H
+#include <stdbool.h>
+#include "container_of/container_of.h"
+
+/**
+ * struct list_node - an entry in a doubly-linked list
+ * @next: next entry (self if empty)
+ * @prev: previous entry (self if empty)
+ *
+ * This is used as an entry in a linked list.
+ * Example:
+ *     struct child {
+ *             const char *name;
+ *             // Linked list of all us children.
+ *             struct list_node list;
+ *     };
+ */
+struct list_node
+{
+       struct list_node *next, *prev;
+};
+
+/**
+ * struct list_head - the head of a doubly-linked list
+ * @h: the list_head (containing next and prev pointers)
+ *
+ * This is used as the head of a linked list.
+ * Example:
+ *     struct parent {
+ *             const char *name;
+ *             struct list_head children;
+ *             unsigned int num_children;
+ *     };
+ */
+struct list_head
+{
+       struct list_node n;
+};
+
+/**
+ * list_check - check a list for consistency
+ * @h: the list_head
+ * @abortstr: the location to print on aborting, or NULL.
+ *
+ * Because list_nodes have redundant information, consistency checking between
+ * the back and forward links can be done.  This is useful as a debugging check.
+ * If @abortstr is non-NULL, that will be printed in a diagnostic if the list
+ * is inconsistent, and the function will abort.
+ *
+ * Returns the list head if the list is consistent, NULL if not (it
+ * can never return NULL if @abortstr is set).
+ *
+ * Example:
+ *     static void dump_parent(struct parent *p)
+ *     {
+ *             struct child *c;
+ *
+ *             printf("%s (%u children):\n", p->name, parent->num_children);
+ *             list_check(&p->children, "bad child list");
+ *             list_for_each(&p->children, c, list)
+ *                     printf(" -> %s\n", c->name);
+ *     }
+ */
+struct list_head *list_check(struct list_head *h, const char *abortstr);
+
+#ifdef CCAN_LIST_DEBUG
+#define debug_list(h) list_check((h), __func__)
+#else
+#define debug_list(h) (h)
+#endif
+
+/**
+ * list_head_init - initialize a list_head
+ * @h: the list_head to set to the empty list
+ *
+ * Example:
+ *     list_head_init(&parent->children);
+ *     parent->num_children = 0;
+ */
+static inline void list_head_init(struct list_head *h)
+{
+       h->n.next = h->n.prev = &h->n;
+}
+
+/**
+ * LIST_HEAD - define and initalized empty list_head
+ * @name: the name of the list.
+ *
+ * The LIST_HEAD macro defines a list_head and initializes it to an empty
+ * list.  It can be prepended by "static" to define a static list_head.
+ *
+ * Example:
+ *     // Header:
+ *     extern struct list_head my_list;
+ *
+ *     // C file:
+ *     LIST_HEAD(my_list);
+ */
+#define LIST_HEAD(name) \
+       struct list_head name = { { &name.n, &name.n } }
+
+/**
+ * list_add - add an entry at the start of a linked list.
+ * @h: the list_head to add the node to
+ * @n: the list_node to add to the list.
+ *
+ * The list_node does not need to be initialized; it will be overwritten.
+ * Example:
+ *     list_add(&parent->children, &child->list);
+ *     parent->num_children++;
+ */
+static inline void list_add(struct list_head *h, struct list_node *n)
+{
+       n->next = h->n.next;
+       n->prev = &h->n;
+       h->n.next->prev = n;
+       h->n.next = n;
+       (void)debug_list(h);
+}
+
+/**
+ * list_add_tail - add an entry at the end of a linked list.
+ * @h: the list_head to add the node to
+ * @n: the list_node to add to the list.
+ *
+ * The list_node does not need to be initialized; it will be overwritten.
+ * Example:
+ *     list_add_tail(&parent->children, &child->list);
+ *     parent->num_children++;
+ */
+static inline void list_add_tail(struct list_head *h, struct list_node *n)
+{
+       n->next = &h->n;
+       n->prev = h->n.prev;
+       h->n.prev->next = n;
+       h->n.prev = n;
+       (void)debug_list(h);
+}
+
+/**
+ * list_del - delete an entry from a linked list.
+ * @n: the list_node to delete from the list.
+ *
+ * Example:
+ *     list_del(&child->list);
+ *     parent->num_children--;
+ */
+static inline void list_del(struct list_node *n)
+{
+       n->next->prev = n->prev;
+       n->prev->next = n->next;
+       (void)debug_list(n->next);
+#ifdef CCAN_LIST_DEBUG
+       /* Catch use-after-del. */
+       n->next = n->prev = NULL;
+#endif
+}
+
+/**
+ * list_empty - is a list empty?
+ * @h: the list_head
+ *
+ * If the list is empty, returns true.
+ *
+ * Example:
+ *     assert(list_empty(&parent->children) == (parent->num_children == 0));
+ */
+static inline bool list_empty(struct list_head *h)
+{
+       (void)debug_list(h);
+       return h->n.next == &h->n;
+}
+
+/**
+ * list_entry - convert a list_node back into the structure containing it.
+ * @n: the list_node
+ * @type: the type of the entry
+ * @member: the list_node member of the type
+ *
+ * Example:
+ *     struct child *c;
+ *     // First list entry is children.next; convert back to child.
+ *     c = list_entry(parent->children.next, struct child, list);
+ */
+#define list_entry(n, type, member) container_of(n, type, member)
+
+/**
+ * list_top - get the first entry in a list
+ * @h: the list_head
+ * @type: the type of the entry
+ * @member: the list_node member of the type
+ *
+ * If the list is empty, returns NULL.
+ *
+ * Example:
+ *     struct child *first;
+ *     first = list_top(&parent->children, struct child, list);
+ */
+#define list_top(h, type, member) \
+       list_entry(_list_top(h), type, member)  
+
+static inline struct list_node *_list_top(struct list_head *h)
+{
+       (void)debug_list(h);
+       if (list_empty(h))
+               return NULL;
+       return h->n.next;
+}
+
+/**
+ * list_for_each - iterate through a list.
+ * @h: the list_head
+ * @i: the structure containing the list_node
+ * @member: the list_node member of the structure
+ *
+ * This is a convenient wrapper to iterate @i over the entire list.  It's
+ * a for loop, so you can break and continue as normal.
+ *
+ * Example:
+ *     struct child *c;
+ *     list_for_each(&parent->children, c, list)
+ *             printf("Name: %s\n", c->name);
+ */
+#define list_for_each(h, i, member)                                    \
+       for (i = container_of_var(debug_list(h)->n.next, i, member);    \
+            &i->member != &(h)->n;                                     \
+            i = container_of_var(i->member.next, i, member))
+
+/**
+ * list_for_each_safe - iterate through a list, maybe during deletion
+ * @h: the list_head
+ * @i: the structure containing the list_node
+ * @nxt: the structure containing the list_node
+ * @member: the list_node member of the structure
+ *
+ * This is a convenient wrapper to iterate @i over the entire list.  It's
+ * a for loop, so you can break and continue as normal.  The extra variable
+ * @nxt is used to hold the next element, so you can delete @i from the list.
+ *
+ * Example:
+ *     struct child *c, *n;
+ *     list_for_each_safe(&parent->children, c, n, list) {
+ *             list_del(&c->list);
+ *             parent->num_children--;
+ *     }
+ */
+#define list_for_each_safe(h, i, nxt, member)                          \
+       for (i = container_of_var(debug_list(h)->n.next, i, member),    \
+               nxt = container_of_var(i->member.next, i, member);      \
+            &i->member != &(h)->n;                                     \
+            i = nxt, nxt = container_of_var(i->member.next, i, member))
+#endif /* CCAN_LIST_H */
diff --git a/ccan/list/test/run.c b/ccan/list/test/run.c
new file mode 100644 (file)
index 0000000..66b9630
--- /dev/null
@@ -0,0 +1,118 @@
+#include "list/list.h"
+#include "tap/tap.h"
+#include "list/list.c"
+
+struct parent {
+       const char *name;
+       struct list_head children;
+       unsigned int num_children;
+};
+
+struct child {
+       const char *name;
+       struct list_node list;
+};
+
+static LIST_HEAD(static_list);
+
+int main(int argc, char *argv[])
+{
+       struct parent parent;
+       struct child c1, c2, c3, *c, *n;
+       unsigned int i;
+
+       plan_tests(41);
+       /* Test LIST_HEAD, list_empty and check_list */
+       ok1(list_empty(&static_list));
+       ok1(list_check(&static_list, NULL));
+
+       parent.num_children = 0;
+       list_head_init(&parent.children);
+       /* Test list_head_init */
+       ok1(list_empty(&parent.children));
+       ok1(list_check(&parent.children, NULL));
+
+       c2.name = "c2";
+       list_add(&parent.children, &c2.list);
+       /* Test list_add and !list_empty. */
+       ok1(!list_empty(&parent.children));
+       ok1(c2.list.next == &parent.children.n);
+       ok1(c2.list.prev == &parent.children.n);
+       ok1(parent.children.n.next == &c2.list);
+       ok1(parent.children.n.prev == &c2.list);
+       /* Test list_check */
+       ok1(list_check(&parent.children, NULL));
+
+       c1.name = "c1";
+       list_add(&parent.children, &c1.list);
+       /* Test list_add and !list_empty. */
+       ok1(!list_empty(&parent.children));
+       ok1(c2.list.next == &parent.children.n);
+       ok1(c2.list.prev == &c1.list);
+       ok1(parent.children.n.next == &c1.list);
+       ok1(parent.children.n.prev == &c2.list);
+       ok1(c1.list.next == &c2.list);
+       ok1(c1.list.prev == &parent.children.n);
+       /* Test list_check */
+       ok1(list_check(&parent.children, NULL));
+
+       c3.name = "c3";
+       list_add_tail(&parent.children, &c3.list);
+       /* Test list_add_tail and !list_empty. */
+       ok1(!list_empty(&parent.children));
+       ok1(parent.children.n.next == &c1.list);
+       ok1(parent.children.n.prev == &c3.list);
+       ok1(c1.list.next == &c2.list);
+       ok1(c1.list.prev == &parent.children.n);
+       ok1(c2.list.next == &c3.list);
+       ok1(c2.list.prev == &c1.list);
+       ok1(c3.list.next == &parent.children.n);
+       ok1(c3.list.prev == &c2.list);
+       /* Test list_check */
+       ok1(list_check(&parent.children, NULL));
+
+       /* Test list_top */
+       ok1(list_top(&parent.children, struct child, list) == &c1);
+
+       /* Test list_for_each. */
+       i = 0;
+       list_for_each(&parent.children, c, list) {
+               switch (i++) {
+               case 0:
+                       ok1(c == &c1);
+                       break;
+               case 1:
+                       ok1(c == &c2);
+                       break;
+               case 2:
+                       ok1(c == &c3);
+                       break;
+               }
+               if (i > 2)
+                       break;
+       }
+       ok1(i == 3);
+
+       /* Test list_for_each_safe and list_del. */
+       i = 0;
+       list_for_each_safe(&parent.children, c, n, list) {
+               switch (i++) {
+               case 0:
+                       ok1(c == &c1);
+                       break;
+               case 1:
+                       ok1(c == &c2);
+                       break;
+               case 2:
+                       ok1(c == &c3);
+                       break;
+               }
+               list_del(&c->list);
+               ok1(list_check(&parent.children, NULL));
+               if (i > 2)
+                       break;
+       }
+       ok1(i == 3);
+       ok1(list_empty(&parent.children));
+       return exit_status();
+}
diff --git a/ccan/noerr/_info.c b/ccan/noerr/_info.c
new file mode 100644 (file)
index 0000000..96fbbcd
--- /dev/null
@@ -0,0 +1,54 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * noerr - routines for cleaning up without blatting errno
+ *
+ * It is a good idea to follow the standard C convention of setting errno in
+ * your own helper functions.  Unfortunately, care must be taken in the error
+ * paths as most standard functions can (and do) overwrite errno, even if they
+ * succeed.
+ *
+ * Example:
+ *     #include <sys/types.h>
+ *     #include <sys/stat.h>
+ *     #include <fcntl.h>
+ *
+ *     bool write_string_to_file(const char *file, const char *string)
+ *     {
+ *             int ret, fd = open(file, O_WRONLY|O_CREAT|O_EXCL, 0600);
+ *             if (fd < 0)
+ *                     return false;
+ *             ret = write(fd, string, strlen(string));
+ *             if (ret < 0) {
+ *                     // Preserve errno from write above.
+ *                     close_noerr(fd);
+ *                     unlink_noerr(file);
+ *                     return false;
+ *             }
+ *             if (close(fd) != 0) {
+ *                     // Again, preserve errno.
+ *                     unlink_noerr(file);
+ *                     return false;
+ *             }
+ *             // A short write means out of space.
+ *             if (ret < strlen(string)) {
+ *                     unlink(file);
+ *                     errno = ENOSPC;
+ *                     return false;
+ *             }
+ *             return true;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0)
+               /* Nothing. */
+               return 0;
+
+       return 1;
+}
diff --git a/ccan/noerr/noerr.c b/ccan/noerr/noerr.c
new file mode 100644 (file)
index 0000000..d6df81f
--- /dev/null
@@ -0,0 +1,29 @@
+#include "noerr.h"
+#include <unistd.h>
+#include <errno.h>
+
+int close_noerr(int fd)
+{
+       int saved_errno = errno, ret;
+
+       if (close(fd) != 0)
+               ret = errno;
+       else
+               ret = 0;
+
+       errno = saved_errno;
+       return ret;
+}
+
+int unlink_noerr(const char *pathname)
+{
+       int saved_errno = errno, ret;
+
+       if (unlink(pathname) != 0)
+               ret = errno;
+       else
+               ret = 0;
+
+       errno = saved_errno;
+       return ret;
+}
diff --git a/ccan/noerr/noerr.h b/ccan/noerr/noerr.h
new file mode 100644 (file)
index 0000000..559ba61
--- /dev/null
@@ -0,0 +1,22 @@
+#ifndef NOERR_H
+#define NOERR_H
+
+/**
+ * close_noerr - close without stomping errno.
+ * @fd: the file descriptor to close.
+ *
+ * errno is saved and restored across the call to close: if an error occurs,
+ * the resulting (non-zero) errno is returned.
+ */
+int close_noerr(int fd);
+
+/**
+ * unlink_noerr - unlink a file without stomping errno.
+ * @pathname: the path to unlink.
+ *
+ * errno is saved and restored across the call to unlink: if an error occurs,
+ * the resulting (non-zero) errno is returned.
+ */
+int unlink_noerr(const char *pathname);
+
+#endif /* NOERR_H */
diff --git a/ccan/noerr/test/run.c b/ccan/noerr/test/run.c
new file mode 100644 (file)
index 0000000..6d3c683
--- /dev/null
@@ -0,0 +1,48 @@
+#include "noerr/noerr.h"
+#include "tap/tap.h"
+#include "noerr/noerr.c"
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <assert.h>
+
+int main(int argc, char *argv[])
+{
+       /* tempnam(3) is generally a bad idea, but OK here. */
+       char *name = tempnam(NULL, "noerr");
+       int fd;
+
+       plan_tests(12);
+       /* Should fail to unlink. */
+       ok1(unlink(name) != 0);
+       ok1(errno == ENOENT);
+
+       /* This one should not set errno. */
+       errno = 100;
+       ok1(unlink_noerr(name) == ENOENT);
+       ok1(errno == 100);
+
+       /* Should fail to close. */
+       ok1(close(-1) != 0);
+       ok1(errno == EBADF);
+
+       /* This one should not set errno. */
+       errno = 100;
+       ok1(close_noerr(-1) == EBADF);
+       ok1(errno == 100);
+
+       /* Test successful close/unlink doesn't hit errno either. */
+       fd = open(name, O_WRONLY|O_CREAT|O_EXCL, 0600);
+       assert(fd >= 0);
+
+       errno = 100;
+       ok1(close_noerr(fd) == 0);
+       ok1(errno == 100);
+
+       errno = 100;
+       ok1(unlink_noerr(name) == 0);
+       ok1(errno == 100);
+
+       return exit_status();
+}
diff --git a/ccan/string/_info.c b/ccan/string/_info.c
new file mode 100644 (file)
index 0000000..9cb691c
--- /dev/null
@@ -0,0 +1,35 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * string - string helper routines
+ *
+ * This is a grab bag of modules for string comparisons, designed to enhance
+ * the standard string.h.
+ *
+ * Example:
+ *     #include "string/string.h"
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             if (argv[1] && streq(argv[1], "--verbose"))
+ *                     printf("verbose set\n");
+ *             if (argv[1] && strstarts(argv[1], "--"))
+ *                     printf("Some option set\n");
+ *             if (argv[1] && strends(argv[1], "cow-powers"))
+ *                     printf("Magic option set\n");
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0)
+               /* Nothing. */
+               return 0;
+
+       return 1;
+}
diff --git a/ccan/string/string.h b/ccan/string/string.h
new file mode 100644 (file)
index 0000000..f4997c6
--- /dev/null
@@ -0,0 +1,46 @@
+#ifndef CCAN_STRING_H
+#define CCAN_STRING_H
+#include <string.h>
+#include <stdbool.h>
+
+/**
+ * streq - Are two strings equal?
+ * @a: first string
+ * @b: first string
+ *
+ * This macro is arguably more readable than "!strcmp(a, b)".
+ *
+ * Example:
+ *     if (streq(str, ""))
+ *             printf("String is empty!\n");
+ */
+#define streq(a,b) (strcmp((a),(b)) == 0)
+
+/**
+ * strstarts - Does this string start with this prefix?
+ * @str: string to test
+ * @prefix: prefix to look for at start of str
+ *
+ * Example:
+ *     if (strstarts(str, "foo"))
+ *             printf("String %s begins with 'foo'!\n", str);
+ */
+#define strstarts(str,prefix) (strncmp((str),(prefix),strlen(prefix)) == 0)
+
+/**
+ * strends - Does this string end with this postfix?
+ * @str: string to test
+ * @postfix: postfix to look for at end of str
+ *
+ * Example:
+ *     if (strends(str, "foo"))
+ *             printf("String %s end with 'foo'!\n", str);
+ */
+static inline bool strends(const char *str, const char *postfix)
+{
+       if (strlen(str) < strlen(postfix))
+               return false;
+
+       return streq(str + strlen(str) - strlen(postfix), postfix);
+}
+#endif /* CCAN_STRING_H */
diff --git a/ccan/string/test/run.c b/ccan/string/test/run.c
new file mode 100644 (file)
index 0000000..fded0e4
--- /dev/null
@@ -0,0 +1,77 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "string/string.h"
+#include "tap/tap.h"
+
+/* FIXME: ccanize */
+#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
+
+static char *substrings[] = { "far", "bar", "baz", "b", "ba", "z", "ar" };
+
+static char *strdup_rev(const char *s)
+{
+       char *ret = strdup(s);
+       unsigned int i;
+
+       for (i = 0; i < strlen(s); i++)
+               ret[i] = s[strlen(s) - i - 1];
+       return ret;
+}
+
+int main(int argc, char *argv[])
+{
+       unsigned int i, j, n;
+       char *strings[ARRAY_SIZE(substrings) * ARRAY_SIZE(substrings)];
+
+       n = 0;
+       for (i = 0; i < ARRAY_SIZE(substrings); i++) {
+               for (j = 0; j < ARRAY_SIZE(substrings); j++) {
+                       strings[n] = malloc(strlen(substrings[i])
+                                           + strlen(substrings[j]) + 1);
+                       sprintf(strings[n++], "%s%s",
+                               substrings[i], substrings[j]);
+               }
+       }
+
+       plan_tests(n * n * 5);
+       for (i = 0; i < n; i++) {
+               for (j = 0; j < n; j++) {
+                       unsigned int k, identical = 0;
+                       char *reva, *revb;
+
+                       /* Find first difference. */
+                       for (k = 0; strings[i][k]==strings[j][k]; k++) {
+                               if (k == strlen(strings[i])) {
+                                       identical = 1;
+                                       break;
+                               }
+                       }
+
+                       if (identical) 
+                               ok1(streq(strings[i], strings[j]));
+                       else
+                               ok1(!streq(strings[i], strings[j]));
+
+                       /* Postfix test should be equivalent to prefix
+                        * test on reversed string. */
+                       reva = strdup_rev(strings[i]);
+                       revb = strdup_rev(strings[j]);
+
+                       if (!strings[i][k]) {
+                               ok1(strstarts(strings[j], strings[i]));
+                               ok1(strends(revb, reva));
+                       } else {
+                               ok1(!strstarts(strings[j], strings[i]));
+                               ok1(!strends(revb, reva));
+                       }
+                       if (!strings[j][k]) {
+                               ok1(strstarts(strings[i], strings[j]));
+                               ok1(strends(reva, revb));
+                       } else {
+                               ok1(!strstarts(strings[i], strings[j]));
+                               ok1(!strends(reva, revb));
+                       }
+               }
+       }
+       return exit_status();
+}                              
diff --git a/ccan/talloc/TODO b/ccan/talloc/TODO
new file mode 100644 (file)
index 0000000..0671a6d
--- /dev/null
@@ -0,0 +1,2 @@
+- Remove talloc.h cruft
+- Restore errno around (successful) talloc_free.
diff --git a/ccan/talloc/_info.c b/ccan/talloc/_info.c
new file mode 100644 (file)
index 0000000..bc48736
--- /dev/null
@@ -0,0 +1,103 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * talloc - tree allocator routines
+ *
+ * Talloc is a hierarchical memory pool system with destructors: you keep your
+ * objects in heirarchies reflecting their lifetime.  Every pointer returned
+ * from talloc() is itself a valid talloc context, from which other talloc()s
+ * can be attached.  This means you can do this:
+ *
+ *  struct foo *X = talloc(mem_ctx, struct foo);
+ *  X->name = talloc_strdup(X, "foo");
+ *
+ * and the pointer X->name would be a "child" of the talloc context "X" which
+ * is itself a child of mem_ctx.  So if you do talloc_free(mem_ctx) then it is
+ * all destroyed, whereas if you do talloc_free(X) then just X and X->name are
+ * destroyed, and if you do talloc_free(X->name) then just the name element of
+ * X is destroyed.
+ *
+ * If you think about this, then what this effectively gives you is an n-ary
+ * tree, where you can free any part of the tree with talloc_free().
+ *
+ * Talloc has been measured with a time overhead of around 4% over glibc
+ * malloc, and 48/80 bytes per allocation (32/64 bit).
+ *
+ * This version is based on svn://svnanon.samba.org/samba/branches/SAMBA_4_0/source/lib/talloc revision 23158.
+ *
+ * Example:
+ *     #include <stdio.h>
+ *     #include <stdarg.h>
+ *     #include <err.h>
+ *     #include "talloc/talloc.h"
+ *
+ *     // A structure containing a popened comman.
+ *     struct command
+ *     {
+ *             FILE *f;
+ *             const char *command;
+ *     };
+ *
+ *     // When struct command is freed, we also want to pclose pipe.
+ *     static int close_cmd(struct command *cmd)
+ *     {
+ *             pclose(cmd->f);
+ *             // 0 means "we succeeded, continue freeing"
+ *             return 0;
+ *     }
+ *
+ *     // This function opens a writable pipe to the given command.
+ *     struct command *open_output_cmd(const void *ctx, char *fmt, ...)
+ *     {
+ *             va_list ap;
+ *             struct command *cmd = talloc(ctx, struct command);
+ *
+ *             if (!cmd)
+ *                     return NULL;
+ *
+ *             va_start(ap, fmt);
+ *             cmd->command = talloc_vasprintf(cmd, fmt, ap);
+ *             va_end(ap);
+ *             if (!cmd->command) {
+ *                     talloc_free(cmd);
+ *                     return NULL;
+ *             }
+ *
+ *             cmd->f = popen(cmd->command, "w");
+ *             if (!cmd->f) {
+ *                     talloc_free(cmd);
+ *                     return NULL;
+ *             }
+ *             talloc_set_destructor(cmd, close_cmd);
+ *             return cmd;
+ *     }
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             struct command *cmd;
+ *
+ *             if (argc != 2)
+ *                     errx(1, "Usage: %s <command>\n");
+ *
+ *             cmd = open_output_cmd(NULL, "%s hello", argv[1]);
+ *             if (!cmd)
+ *                     err(1, "Running '%s hello'", argv[1]);
+ *             fprintf(cmd->f, "This is a test\n");
+ *             talloc_free(cmd);
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/typesafe_cb\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/talloc/talloc.3.xml b/ccan/talloc/talloc.3.xml
new file mode 100644 (file)
index 0000000..83ca67a
--- /dev/null
@@ -0,0 +1,739 @@
+<?xml version="1.0"?>
+<!DOCTYPE refentry PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN" "http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd">
+<refentry>
+  <refmeta>
+    <refentrytitle>talloc</refentrytitle>
+    <manvolnum>3</manvolnum>
+  </refmeta>
+  <refnamediv>
+    <refname>talloc</refname>
+<refpurpose>hierarchical reference counted memory pool system with destructors</refpurpose>
+  </refnamediv>
+  <refsynopsisdiv>
+<synopsis>#include &lt;talloc/talloc.h&gt;</synopsis>
+  </refsynopsisdiv>
+  <refsect1><title>DESCRIPTION</title>
+    <para>
+      If you are used to talloc from Samba3 then please read this
+      carefully, as talloc has changed a lot.
+    </para>
+    <para>
+      The new talloc is a hierarchical, reference counted memory pool
+      system with destructors. Quite a mouthful really, but not too bad
+      once you get used to it.
+    </para>
+    <para>
+      Perhaps the biggest change from Samba3 is that there is no
+      distinction between a "talloc context" and a "talloc pointer".  Any
+      pointer returned from talloc() is itself a valid talloc context. 
+      This means you can do this:
+    </para>
+    <programlisting>
+    struct foo *X = talloc(mem_ctx, struct foo);
+    X->name = talloc_strdup(X, "foo");
+    </programlisting>
+    <para>
+      and the pointer <literal role="code">X-&gt;name</literal>
+      would be a "child" of the talloc context <literal
+      role="code">X</literal> which is itself a child of
+      <literal role="code">mem_ctx</literal>.  So if you do
+      <literal role="code">talloc_free(mem_ctx)</literal> then
+      it is all destroyed, whereas if you do <literal
+      role="code">talloc_free(X)</literal> then just <literal
+      role="code">X</literal> and <literal
+      role="code">X-&gt;name</literal> are destroyed, and if
+      you do <literal
+      role="code">talloc_free(X-&gt;name)</literal> then just
+      the name element of <literal role="code">X</literal> is
+      destroyed.
+    </para>
+    <para>
+      If you think about this, then what this effectively gives you is an
+      n-ary tree, where you can free any part of the tree with
+      talloc_free().
+    </para>
+    <para>
+      If you find this confusing, then I suggest you run the <literal
+      role="code">testsuite</literal> program to watch talloc
+      in action.  You may also like to add your own tests to <literal
+      role="code">testsuite.c</literal> to clarify how some
+      particular situation is handled.
+    </para>
+  </refsect1>
+  <refsect1><title>TALLOC API</title>
+    <para>
+      The following is a complete guide to the talloc API. Read it all at
+      least twice.
+    </para>
+    <refsect2><title>(type *)talloc(const void *ctx, type);</title>
+        <para>
+         The talloc() macro is the core of the talloc library.  It takes a
+         memory <emphasis role="italic">ctx</emphasis> and a <emphasis
+         role="italic">type</emphasis>, and returns a pointer to a new
+         area of memory of the given <emphasis
+         role="italic">type</emphasis>.
+        </para>
+        <para>
+         The returned pointer is itself a talloc context, so you can use
+         it as the <emphasis role="italic">ctx</emphasis> argument to more
+         calls to talloc() if you wish.
+        </para>
+        <para>
+         The returned pointer is a "child" of the supplied context.  This
+         means that if you talloc_free() the <emphasis
+         role="italic">ctx</emphasis> then the new child disappears as
+         well.  Alternatively you can free just the child.
+        </para>
+        <para>
+         The <emphasis role="italic">ctx</emphasis> argument to talloc()
+         can be NULL, in which case a new top level context is created.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_size(const void *ctx, size_t size);</title>
+        <para>
+         The function talloc_size() should be used when you don't have a
+         convenient type to pass to talloc().  Unlike talloc(), it is not
+         type safe (as it returns a void *), so you are on your own for
+         type checking.
+        </para>
+    </refsect2>
+    <refsect2><title>(typeof(ptr)) talloc_ptrtype(const void *ctx, ptr);</title>
+        <para>
+         The talloc_ptrtype() macro should be used when you have a pointer and
+         want to allocate memory to point at with this pointer. When compiling
+         with gcc >= 3 it is typesafe. Note this is a wrapper of talloc_size()
+         and talloc_get_name() will return the current location in the source file.
+         and not the type.
+        </para>
+    </refsect2>
+    <refsect2><title>int talloc_free(void *ptr);</title>
+        <para>
+         The talloc_free() function frees a piece of talloc memory, and
+         all its children.  You can call talloc_free() on any pointer
+         returned by talloc().
+        </para>
+        <para>
+         The return value of talloc_free() indicates success or failure,
+         with 0 returned for success and -1 for failure.  The only
+         possible failure condition is if <emphasis
+         role="italic">ptr</emphasis> had a destructor attached to it and
+         the destructor returned -1.  See <link
+         linkend="talloc_set_destructor"><quote>talloc_set_destructor()</quote></link>
+         for details on destructors.
+        </para>
+        <para>
+         If this pointer has an additional parent when talloc_free() is
+         called then the memory is not actually released, but instead the
+         most recently established parent is destroyed.  See <link
+         linkend="talloc_reference"><quote>talloc_reference()</quote></link>
+         for details on establishing additional parents.
+        </para>
+        <para>
+         For more control on which parent is removed, see <link
+         linkend="talloc_unlink"><quote>talloc_unlink()</quote></link>.
+        </para>
+        <para>
+         talloc_free() operates recursively on its children.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_reference"><title>void *talloc_reference(const void *ctx, const void *ptr);</title>
+        <para>
+         The talloc_reference() function makes <emphasis
+         role="italic">ctx</emphasis> an additional parent of <emphasis
+         role="italic">ptr</emphasis>.
+        </para>
+        <para>
+         The return value of talloc_reference() is always the original
+         pointer <emphasis role="italic">ptr</emphasis>, unless talloc ran
+         out of memory in creating the reference in which case it will
+         return NULL (each additional reference consumes around 48 bytes
+         of memory on intel x86 platforms).
+        </para>
+        <para>
+         If <emphasis role="italic">ptr</emphasis> is NULL, then the
+         function is a no-op, and simply returns NULL.
+        </para>
+        <para>
+         After creating a reference you can free it in one of the
+         following ways:
+        </para>
+      <para>
+        <itemizedlist>
+          <listitem>
+            <para>
+             you can talloc_free() any parent of the original pointer. 
+             That will reduce the number of parents of this pointer by 1,
+             and will cause this pointer to be freed if it runs out of
+             parents.
+            </para>
+          </listitem>
+          <listitem>
+            <para>
+             you can talloc_free() the pointer itself.  That will destroy
+             the most recently established parent to the pointer and leave
+             the pointer as a child of its current parent.
+            </para>
+          </listitem>
+        </itemizedlist>
+      </para>
+      <para>
+       For more control on which parent to remove, see <link
+       linkend="talloc_unlink"><quote>talloc_unlink()</quote></link>.
+      </para>
+    </refsect2>
+    <refsect2 id="talloc_unlink"><title>int talloc_unlink(const void *ctx, const void *ptr);</title>
+        <para>
+         The talloc_unlink() function removes a specific parent from
+         <emphasis role="italic">ptr</emphasis>. The <emphasis
+         role="italic">ctx</emphasis> passed must either be a context used
+         in talloc_reference() with this pointer, or must be a direct
+         parent of ptr.
+        </para>
+        <para>
+         Note that if the parent has already been removed using
+         talloc_free() then this function will fail and will return -1. 
+         Likewise, if <emphasis role="italic">ptr</emphasis> is NULL, then
+         the function will make no modifications and return -1.
+        </para>
+        <para>
+         Usually you can just use talloc_free() instead of
+         talloc_unlink(), but sometimes it is useful to have the
+         additional control on which parent is removed.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_set_destructor"><title>void talloc_set_destructor(const void *ptr, int (*destructor)(void *));</title>
+        <para>
+         The function talloc_set_destructor() sets the <emphasis
+         role="italic">destructor</emphasis> for the pointer <emphasis
+         role="italic">ptr</emphasis>.  A <emphasis
+         role="italic">destructor</emphasis> is a function that is called
+         when the memory used by a pointer is about to be released.  The
+         destructor receives <emphasis role="italic">ptr</emphasis> as an
+         argument, and should return 0 for success and -1 for failure.
+        </para>
+        <para>
+         The <emphasis role="italic">destructor</emphasis> can do anything
+         it wants to, including freeing other pieces of memory.  A common
+         use for destructors is to clean up operating system resources
+         (such as open file descriptors) contained in the structure the
+         destructor is placed on.
+        </para>
+        <para>
+         You can only place one destructor on a pointer.  If you need more
+         than one destructor then you can create a zero-length child of
+         the pointer and place an additional destructor on that.
+        </para>
+        <para>
+         To remove a destructor call talloc_set_destructor() with NULL for
+         the destructor.
+        </para>
+        <para>
+         If your destructor attempts to talloc_free() the pointer that it
+         is the destructor for then talloc_free() will return -1 and the
+         free will be ignored.  This would be a pointless operation
+         anyway, as the destructor is only called when the memory is just
+         about to go away.
+        </para>
+    </refsect2>
+    <refsect2><title>int talloc_increase_ref_count(const void *<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         The talloc_increase_ref_count(<emphasis
+         role="italic">ptr</emphasis>) function is exactly equivalent to:
+        </para>
+        <programlisting>talloc_reference(NULL, ptr);</programlisting>
+        <para>
+         You can use either syntax, depending on which you think is
+         clearer in your code.
+        </para>
+        <para>
+         It returns 0 on success and -1 on failure.
+        </para>
+    </refsect2>
+    <refsect2><title>size_t talloc_reference_count(const void *<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         Return the number of references to the pointer.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_set_name"><title>void talloc_set_name(const void *ptr, const char *fmt, ...);</title>
+        <para>
+         Each talloc pointer has a "name".  The name is used principally
+         for debugging purposes, although it is also possible to set and
+         get the name on a pointer in as a way of "marking" pointers in
+         your code.
+        </para>
+        <para>
+         The main use for names on pointer is for "talloc reports".  See
+         <link
+         linkend="talloc_report"><quote>talloc_report_depth_cb()</quote></link>,
+         <link
+         linkend="talloc_report"><quote>talloc_report_depth_file()</quote></link>,
+         <link
+         linkend="talloc_report"><quote>talloc_report()</quote></link>
+         <link
+         linkend="talloc_report"><quote>talloc_report()</quote></link>
+         and <link
+         linkend="talloc_report_full"><quote>talloc_report_full()</quote></link>
+         for details.  Also see <link
+         linkend="talloc_enable_leak_report"><quote>talloc_enable_leak_report()</quote></link>
+         and <link
+         linkend="talloc_enable_leak_report_full"><quote>talloc_enable_leak_report_full()</quote></link>.
+        </para>
+        <para>
+         The talloc_set_name() function allocates memory as a child of the
+         pointer.  It is logically equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, talloc_asprintf(ptr, fmt, ...));</programlisting>
+        <para>
+         Note that multiple calls to talloc_set_name() will allocate more
+         memory without releasing the name.  All of the memory is released
+         when the ptr is freed using talloc_free().
+        </para>
+    </refsect2>
+    <refsect2><title>void talloc_set_name_const(const void *<emphasis role="italic">ptr</emphasis>, const char *<emphasis role="italic">name</emphasis>);</title>
+        <para>
+         The function talloc_set_name_const() is just like
+         talloc_set_name(), but it takes a string constant, and is much
+         faster.  It is extensively used by the "auto naming" macros, such
+         as talloc_p().
+        </para>
+        <para>
+         This function does not allocate any memory.  It just copies the
+         supplied pointer into the internal representation of the talloc
+         ptr. This means you must not pass a <emphasis
+         role="italic">name</emphasis> pointer to memory that will
+         disappear before <emphasis role="italic">ptr</emphasis> is freed
+         with talloc_free().
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_named(const void *<emphasis role="italic">ctx</emphasis>, size_t <emphasis role="italic">size</emphasis>, const char *<emphasis role="italic">fmt</emphasis>, ...);</title>
+        <para>
+         The talloc_named() function creates a named talloc pointer.  It
+         is equivalent to:
+        </para>
+        <programlisting>ptr = talloc_size(ctx, size);
+talloc_set_name(ptr, fmt, ....);</programlisting>
+    </refsect2>
+    <refsect2><title>void *talloc_named_const(const void *<emphasis role="italic">ctx</emphasis>, size_t <emphasis role="italic">size</emphasis>, const char *<emphasis role="italic">name</emphasis>);</title>
+        <para>
+         This is equivalent to:
+        </para>
+        <programlisting>ptr = talloc_size(ctx, size);
+talloc_set_name_const(ptr, name);</programlisting>
+    </refsect2>
+    <refsect2><title>const char *talloc_get_name(const void *<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         This returns the current name for the given talloc pointer,
+         <emphasis role="italic">ptr</emphasis>. See <link
+         linkend="talloc_set_name"><quote>talloc_set_name()</quote></link>
+         for details.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_init(const char *<emphasis role="italic">fmt</emphasis>, ...);</title>
+        <para>
+         This function creates a zero length named talloc context as a top
+         level context.  It is equivalent to:
+        </para>
+        <programlisting>talloc_named(NULL, 0, fmt, ...);</programlisting>
+    </refsect2>
+    <refsect2><title>void *talloc_new(void *<emphasis role="italic">ctx</emphasis>);</title>
+        <para>
+         This is a utility macro that creates a new memory context hanging
+         off an exiting context, automatically naming it "talloc_new:
+         __location__" where __location__ is the source line it is called
+         from.  It is particularly useful for creating a new temporary
+         working context.
+        </para>
+    </refsect2>
+    <refsect2><title>(<emphasis role="italic">type</emphasis> *)talloc_realloc(const void *<emphasis role="italic">ctx</emphasis>, void *<emphasis role="italic">ptr</emphasis>, <emphasis role="italic">type</emphasis>, <emphasis role="italic">count</emphasis>);</title>
+        <para>
+         The talloc_realloc() macro changes the size of a talloc pointer. 
+         It has the following equivalences:
+        </para>
+        <programlisting>talloc_realloc(ctx, NULL, type, 1) ==> talloc(ctx, type);
+talloc_realloc(ctx, ptr, type, 0)  ==> talloc_free(ptr);</programlisting>
+        <para>
+         The <emphasis role="italic">ctx</emphasis> argument is only used
+         if <emphasis role="italic">ptr</emphasis> is not NULL, otherwise
+         it is ignored.
+        </para>
+        <para>
+         talloc_realloc() returns the new pointer, or NULL on failure. 
+         The call will fail either due to a lack of memory, or because the
+         pointer has more than one parent (see <link
+         linkend="talloc_reference"><quote>talloc_reference()</quote></link>).
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_realloc_size(const void *ctx, void *ptr, size_t size);</title>
+        <para>
+         the talloc_realloc_size() function is useful when the type is not
+         known so the type-safe talloc_realloc() cannot be used.
+        </para>
+    </refsect2>
+    <refsect2><title>TYPE *talloc_steal(const void *<emphasis role="italic">new_ctx</emphasis>, const TYPE *<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         The talloc_steal() function changes the parent context of a
+         talloc pointer.  It is typically used when the context that the
+         pointer is currently a child of is going to be freed and you wish
+         to keep the memory for a longer time.
+        </para>
+        <para>
+         The talloc_steal() function returns the pointer that you pass it.
+          It does not have any failure modes.
+        </para>
+        <para>
+         NOTE: It is possible to produce loops in the parent/child
+         relationship if you are not careful with talloc_steal().  No
+         guarantees are provided as to your sanity or the safety of your
+         data if you do this.
+        </para>
+    </refsect2>
+    <refsect2><title>TYPE *talloc_move(const void *<emphasis role="italic">new_ctx</emphasis>, TYPE **<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         The talloc_move() function is a wrapper around
+         talloc_steal() which zeros the source pointer after the
+         move. This avoids a potential source of bugs where a
+         programmer leaves a pointer in two structures, and uses the
+         pointer from the old structure after it has been moved to a
+         new one.
+        </para>
+    </refsect2>
+    <refsect2><title>size_t talloc_total_size(const void *<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         The talloc_total_size() function returns the total size in bytes
+         used by this pointer and all child pointers.  Mostly useful for
+         debugging.
+        </para>
+        <para>
+         Passing NULL is allowed, but it will only give a meaningful
+         result if talloc_enable_leak_report() or
+         talloc_enable_leak_report_full() has been called.
+        </para>
+    </refsect2>
+    <refsect2><title>size_t talloc_total_blocks(const void *<emphasis role="italic">ptr</emphasis>);</title>
+        <para>
+         The talloc_total_blocks() function returns the total memory block
+         count used by this pointer and all child pointers.  Mostly useful
+         for debugging.
+        </para>
+        <para>
+         Passing NULL is allowed, but it will only give a meaningful
+         result if talloc_enable_leak_report() or
+         talloc_enable_leak_report_full() has been called.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_report"><title>void talloc_report(const void *ptr, FILE *f);</title>
+        <para>
+         The talloc_report() function prints a summary report of all
+         memory used by <emphasis role="italic">ptr</emphasis>.  One line
+         of report is printed for each immediate child of ptr, showing the
+         total memory and number of blocks used by that child.
+        </para>
+        <para>
+         You can pass NULL for the pointer, in which case a report is
+         printed for the top level memory context, but only if
+         talloc_enable_leak_report() or talloc_enable_leak_report_full()
+         has been called.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_report_full"><title>void talloc_report_full(const void *<emphasis role="italic">ptr</emphasis>, FILE *<emphasis role="italic">f</emphasis>);</title>
+        <para>
+         This provides a more detailed report than talloc_report().  It
+         will recursively print the entire tree of memory referenced by
+         the pointer. References in the tree are shown by giving the name
+         of the pointer that is referenced.
+        </para>
+        <para>
+         You can pass NULL for the pointer, in which case a report is
+         printed for the top level memory context, but only if
+         talloc_enable_leak_report() or talloc_enable_leak_report_full()
+         has been called.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_report_depth_cb">
+     <funcsynopsis><funcprototype>
+      <funcdef>void <function>talloc_report_depth_cb</function></funcdef>
+      <paramdef><parameter>const void *ptr</parameter></paramdef>
+      <paramdef><parameter>int depth</parameter></paramdef>
+      <paramdef><parameter>int max_depth</parameter></paramdef>
+      <paramdef><parameter>void (*callback)(const void *ptr, int depth, int max_depth, int is_ref, void *priv)</parameter></paramdef>
+      <paramdef><parameter>void *priv</parameter></paramdef>
+     </funcprototype></funcsynopsis>
+        <para>
+         This provides a more flexible reports than talloc_report(). It
+         will recursively call the callback for the entire tree of memory
+         referenced by the pointer. References in the tree are passed with
+         <emphasis role="italic">is_ref = 1</emphasis> and the pointer that is referenced.
+        </para>
+        <para>
+         You can pass NULL for the pointer, in which case a report is
+         printed for the top level memory context, but only if
+         talloc_enable_leak_report() or talloc_enable_leak_report_full()
+         has been called.
+        </para>
+        <para>
+         The recursion is stopped when depth >= max_depth.
+         max_depth = -1 means only stop at leaf nodes.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_report_depth_file">
+     <funcsynopsis><funcprototype>
+      <funcdef>void <function>talloc_report_depth_file</function></funcdef>
+      <paramdef><parameter>const void *ptr</parameter></paramdef>
+      <paramdef><parameter>int depth</parameter></paramdef>
+      <paramdef><parameter>int max_depth</parameter></paramdef>
+      <paramdef><parameter>FILE *f</parameter></paramdef>
+     </funcprototype></funcsynopsis>
+        <para>
+         This provides a more flexible reports than talloc_report(). It
+         will let you specify the depth and max_depth.
+        </para>
+    </refsect2>
+    <refsect2 id="talloc_enable_leak_report"><title>void talloc_enable_leak_report(void);</title>
+        <para>
+         This enables calling of talloc_report(NULL, stderr) when the
+         program exits.  In Samba4 this is enabled by using the
+         --leak-report command line option.
+        </para>
+        <para>
+         For it to be useful, this function must be called before any
+         other talloc function as it establishes a "null context" that
+         acts as the top of the tree.  If you don't call this function
+         first then passing NULL to talloc_report() or
+         talloc_report_full() won't give you the full tree printout.
+        </para>
+        <para>
+         Here is a typical talloc report:
+        </para>
+        <screen format="linespecific">talloc report on 'null_context' (total 267 bytes in 15 blocks)
+libcli/auth/spnego_parse.c:55  contains   31 bytes in   2 blocks
+libcli/auth/spnego_parse.c:55  contains   31 bytes in   2 blocks
+iconv(UTF8,CP850)              contains   42 bytes in   2 blocks
+libcli/auth/spnego_parse.c:55  contains   31 bytes in   2 blocks
+iconv(CP850,UTF8)              contains   42 bytes in   2 blocks
+iconv(UTF8,UTF-16LE)           contains   45 bytes in   2 blocks
+iconv(UTF-16LE,UTF8)           contains   45 bytes in   2 blocks
+      </screen>
+    </refsect2>
+    <refsect2 id="talloc_enable_leak_report_full"><title>void talloc_enable_leak_report_full(void);</title>
+        <para>
+         This enables calling of talloc_report_full(NULL, stderr) when the
+         program exits.  In Samba4 this is enabled by using the
+         --leak-report-full command line option.
+        </para>
+        <para>
+         For it to be useful, this function must be called before any
+         other talloc function as it establishes a "null context" that
+         acts as the top of the tree.  If you don't call this function
+         first then passing NULL to talloc_report() or
+         talloc_report_full() won't give you the full tree printout.
+        </para>
+        <para>
+         Here is a typical full report:
+        </para>
+        <screen format="linespecific">full talloc report on 'root' (total 18 bytes in 8 blocks)
+p1               contains     18 bytes in   7 blocks (ref 0)
+    r1               contains     13 bytes in   2 blocks (ref 0)
+        reference to: p2
+    p2               contains      1 bytes in   1 blocks (ref 1)
+    x3               contains      1 bytes in   1 blocks (ref 0)
+    x2               contains      1 bytes in   1 blocks (ref 0)
+    x1               contains      1 bytes in   1 blocks (ref 0)
+      </screen>
+    </refsect2>
+    <refsect2><title>(<emphasis role="italic">type</emphasis> *)talloc_zero(const void *<emphasis role="italic">ctx</emphasis>, <emphasis role="italic">type</emphasis>);</title>
+        <para>
+         The talloc_zero() macro is equivalent to:
+        </para>
+        <programlisting>ptr = talloc(ctx, type);
+if (ptr) memset(ptr, 0, sizeof(type));</programlisting>
+    </refsect2>
+    <refsect2><title>void *talloc_zero_size(const void *<emphasis role="italic">ctx</emphasis>, size_t <emphasis role="italic">size</emphasis>)</title>
+        <para>
+         The talloc_zero_size() function is useful when you don't have a
+         known type.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_memdup(const void *<emphasis role="italic">ctx</emphasis>, const void *<emphasis role="italic">p</emphasis>, size_t size);</title>
+        <para>
+         The talloc_memdup() function is equivalent to:
+        </para>
+        <programlisting>ptr = talloc_size(ctx, size);
+if (ptr) memcpy(ptr, p, size);</programlisting>
+    </refsect2>
+    <refsect2><title>char *talloc_strdup(const void *<emphasis role="italic">ctx</emphasis>, const char *<emphasis role="italic">p</emphasis>);</title>
+        <para>
+         The talloc_strdup() function is equivalent to:
+        </para>
+        <programlisting>ptr = talloc_size(ctx, strlen(p)+1);
+if (ptr) memcpy(ptr, p, strlen(p)+1);</programlisting>
+        <para>
+         This function sets the name of the new pointer to the passed
+         string. This is equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, ptr)</programlisting>
+    </refsect2>
+    <refsect2><title>char *talloc_strndup(const void *<emphasis role="italic">t</emphasis>, const char *<emphasis role="italic">p</emphasis>, size_t <emphasis role="italic">n</emphasis>);</title>
+        <para>
+         The talloc_strndup() function is the talloc equivalent of the C
+         library function strndup(3).
+        </para>
+        <para>
+         This function sets the name of the new pointer to the passed
+         string. This is equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, ptr)</programlisting>
+    </refsect2>
+    <refsect2><title>char *talloc_append_string(const void *<emphasis role="italic">t</emphasis>, char *<emphasis role="italic">orig</emphasis>, const char *<emphasis role="italic">append</emphasis>);</title>
+        <para>
+         The talloc_append_string() function appends the given formatted
+         string to the given string.
+        </para>
+        <para>
+         This function sets the name of the new pointer to the new
+         string. This is equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, ptr)</programlisting>
+    </refsect2>
+    <refsect2><title>char *talloc_vasprintf(const void *<emphasis role="italic">t</emphasis>, const char *<emphasis role="italic">fmt</emphasis>, va_list <emphasis role="italic">ap</emphasis>);</title>
+        <para>
+         The talloc_vasprintf() function is the talloc equivalent of the C
+         library function vasprintf(3).
+        </para>
+        <para>
+         This function sets the name of the new pointer to the new
+         string. This is equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, ptr)</programlisting>
+    </refsect2>
+    <refsect2><title>char *talloc_asprintf(const void *<emphasis role="italic">t</emphasis>, const char *<emphasis role="italic">fmt</emphasis>, ...);</title>
+        <para>
+         The talloc_asprintf() function is the talloc equivalent of the C
+         library function asprintf(3).
+        </para>
+        <para>
+         This function sets the name of the new pointer to the passed
+         string. This is equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, ptr)</programlisting>
+    </refsect2>
+    <refsect2><title>char *talloc_asprintf_append(char *s, const char *fmt, ...);</title>
+        <para>
+         The talloc_asprintf_append() function appends the given formatted
+         string to the given string.
+        </para>
+        <para>
+         This function sets the name of the new pointer to the new
+         string. This is equivalent to:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, ptr)</programlisting>
+    </refsect2>
+    <refsect2><title>(type *)talloc_array(const void *ctx, type, uint_t count);</title>
+        <para>
+         The talloc_array() macro is equivalent to:
+        </para>
+        <programlisting>(type *)talloc_size(ctx, sizeof(type) * count);</programlisting>
+        <para>
+         except that it provides integer overflow protection for the
+         multiply, returning NULL if the multiply overflows.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_array_size(const void *ctx, size_t size, uint_t count);</title>
+        <para>
+         The talloc_array_size() function is useful when the type is not
+         known. It operates in the same way as talloc_array(), but takes a
+         size instead of a type.
+        </para>
+    </refsect2>
+    <refsect2><title>(typeof(ptr)) talloc_array_ptrtype(const void *ctx, ptr, uint_t count);</title>
+        <para>
+         The talloc_ptrtype() macro should be used when you have a pointer to an array
+         and want to allocate memory of an array to point at with this pointer. When compiling
+         with gcc >= 3 it is typesafe. Note this is a wrapper of talloc_array_size()
+         and talloc_get_name() will return the current location in the source file.
+         and not the type.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_realloc_fn(const void *ctx, void *ptr, size_t size)</title>
+        <para>
+         This is a non-macro version of talloc_realloc(), which is useful
+         as libraries sometimes want a realloc function pointer.  A
+         realloc(3) implementation encapsulates the functionality of
+         malloc(3), free(3) and realloc(3) in one call, which is why it is
+         useful to be able to pass around a single function pointer.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_autofree_context(void);</title>
+        <para>
+         This is a handy utility function that returns a talloc context
+         which will be automatically freed on program exit.  This can be
+         used to reduce the noise in memory leak reports.
+        </para>
+    </refsect2>
+    <refsect2><title>void *talloc_check_name(const void *ptr, const char *name);</title>
+        <para>
+         This function checks if a pointer has the specified <emphasis
+         role="italic">name</emphasis>.  If it does then the pointer is
+         returned.  It it doesn't then NULL is returned.
+        </para>
+    </refsect2>
+    <refsect2><title>(type *)talloc_get_type(const void *ptr, type);</title>
+        <para>
+         This macro allows you to do type checking on talloc pointers.  It
+         is particularly useful for void* private pointers.  It is
+         equivalent to this:
+        </para>
+        <programlisting>(type *)talloc_check_name(ptr, #type)</programlisting>
+    </refsect2>
+    <refsect2><title>talloc_set_type(const void *ptr, type);</title>
+        <para>
+         This macro allows you to force the name of a pointer to be a
+         particular <emphasis>type</emphasis>.  This can be
+         used in conjunction with talloc_get_type() to do type checking on
+         void* pointers.
+        </para>
+        <para>
+         It is equivalent to this:
+        </para>
+        <programlisting>talloc_set_name_const(ptr, #type)</programlisting>
+    </refsect2>
+  </refsect1>
+  <refsect1><title>PERFORMANCE</title>
+    <para>
+      All the additional features of talloc(3) over malloc(3) do come at a
+      price.  We have a simple performance test in Samba4 that measures
+      talloc() versus malloc() performance, and it seems that talloc() is
+      about 10% slower than malloc() on my x86 Debian Linux box.  For
+      Samba, the great reduction in code complexity that we get by using
+      talloc makes this worthwhile, especially as the total overhead of
+      talloc/malloc in Samba is already quite small.
+    </para>
+  </refsect1>
+  <refsect1><title>SEE ALSO</title>
+    <para>
+      malloc(3), strndup(3), vasprintf(3), asprintf(3), 
+      <ulink url="http://talloc.samba.org/"/>
+    </para>
+  </refsect1>
+  <refsect1><title>COPYRIGHT/LICENSE</title>
+    <para>
+      Copyright (C) Andrew Tridgell 2004
+    </para>
+    <para>
+      This program is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published by
+      the Free Software Foundation; either version 2 of the License, or (at
+      your option) any later version.
+    </para>
+    <para>
+      This program is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+    </para>
+    <para>
+      You should have received a copy of the GNU General Public License
+      along with this program; if not, write to the Free Software
+      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+    </para>
+  </refsect1>
+</refentry>
diff --git a/ccan/talloc/talloc.c b/ccan/talloc/talloc.c
new file mode 100644 (file)
index 0000000..d624b91
--- /dev/null
@@ -0,0 +1,1403 @@
+/* 
+   Samba Unix SMB/CIFS implementation.
+
+   Samba trivial allocation library - new interface
+
+   NOTE: Please read talloc_guide.txt for full documentation
+
+   Copyright (C) Andrew Tridgell 2004
+   Copyright (C) Stefan Metzmacher 2006
+   
+     ** NOTE! The following LGPL license applies to the talloc
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+  inspired by http://swapped.cc/halloc/
+*/
+
+#include "talloc.h"
+#include <string.h>
+#include <stdint.h>
+#include <errno.h>
+
+/* use this to force every realloc to change the pointer, to stress test
+   code that might not cope */
+#define ALWAYS_REALLOC 0
+
+
+#define MAX_TALLOC_SIZE 0x10000000
+#define TALLOC_MAGIC 0xe814ec70
+#define TALLOC_FLAG_FREE 0x01
+#define TALLOC_FLAG_LOOP 0x02
+#define TALLOC_MAGIC_REFERENCE ((const char *)1)
+
+/* by default we abort when given a bad pointer (such as when talloc_free() is called 
+   on a pointer that came from malloc() */
+#ifndef TALLOC_ABORT
+#define TALLOC_ABORT(reason) abort()
+#endif
+
+#ifndef discard_const_p
+#if defined(INTPTR_MIN)
+# define discard_const_p(type, ptr) ((type *)((intptr_t)(ptr)))
+#else
+# define discard_const_p(type, ptr) ((type *)(ptr))
+#endif
+#endif
+
+/* these macros gain us a few percent of speed on gcc */
+#if HAVE_BUILTIN_EXPECT
+/* the strange !! is to ensure that __builtin_expect() takes either 0 or 1
+   as its first argument */
+#define likely(x)   __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+#else
+#define likely(x) x
+#define unlikely(x) x
+#endif
+
+/* this null_context is only used if talloc_enable_leak_report() or
+   talloc_enable_leak_report_full() is called, otherwise it remains
+   NULL
+*/
+static void *null_context;
+static void *autofree_context;
+
+struct talloc_reference_handle {
+       struct talloc_reference_handle *next, *prev;
+       void *ptr;
+};
+
+typedef int (*talloc_destructor_t)(void *);
+
+struct talloc_chunk {
+       struct talloc_chunk *next, *prev;
+       struct talloc_chunk *parent, *child;
+       struct talloc_reference_handle *refs;
+       talloc_destructor_t destructor;
+       const char *name;
+       size_t size;
+       unsigned flags;
+};
+
+/* 16 byte alignment seems to keep everyone happy */
+#define TC_HDR_SIZE ((sizeof(struct talloc_chunk)+15)&~15)
+#define TC_PTR_FROM_CHUNK(tc) ((void *)(TC_HDR_SIZE + (char*)tc))
+
+/* panic if we get a bad magic value */
+static inline struct talloc_chunk *talloc_chunk_from_ptr(const void *ptr)
+{
+       const char *pp = (const char *)ptr;
+       struct talloc_chunk *tc = discard_const_p(struct talloc_chunk, pp - TC_HDR_SIZE);
+       if (unlikely((tc->flags & (TALLOC_FLAG_FREE | ~0xF)) != TALLOC_MAGIC)) { 
+               if (tc->flags & TALLOC_FLAG_FREE) {
+                       TALLOC_ABORT("Bad talloc magic value - double free"); 
+               } else {
+                       TALLOC_ABORT("Bad talloc magic value - unknown value"); 
+               }
+       }
+       return tc;
+}
+
+/* hook into the front of the list */
+#define _TLIST_ADD(list, p) \
+do { \
+        if (!(list)) { \
+               (list) = (p); \
+               (p)->next = (p)->prev = NULL; \
+       } else { \
+               (list)->prev = (p); \
+               (p)->next = (list); \
+               (p)->prev = NULL; \
+               (list) = (p); \
+       }\
+} while (0)
+
+/* remove an element from a list - element doesn't have to be in list. */
+#define _TLIST_REMOVE(list, p) \
+do { \
+       if ((p) == (list)) { \
+               (list) = (p)->next; \
+               if (list) (list)->prev = NULL; \
+       } else { \
+               if ((p)->prev) (p)->prev->next = (p)->next; \
+               if ((p)->next) (p)->next->prev = (p)->prev; \
+       } \
+       if ((p) && ((p) != (list))) (p)->next = (p)->prev = NULL; \
+} while (0)
+
+
+/*
+  return the parent chunk of a pointer
+*/
+static inline struct talloc_chunk *talloc_parent_chunk(const void *ptr)
+{
+       struct talloc_chunk *tc;
+
+       if (unlikely(ptr == NULL)) {
+               return NULL;
+       }
+
+       tc = talloc_chunk_from_ptr(ptr);
+       while (tc->prev) tc=tc->prev;
+
+       return tc->parent;
+}
+
+void *talloc_parent(const void *ptr)
+{
+       struct talloc_chunk *tc = talloc_parent_chunk(ptr);
+       return tc? TC_PTR_FROM_CHUNK(tc) : NULL;
+}
+
+/*
+  find parents name
+*/
+const char *talloc_parent_name(const void *ptr)
+{
+       struct talloc_chunk *tc = talloc_parent_chunk(ptr);
+       return tc? tc->name : NULL;
+}
+
+/* 
+   Allocate a bit of memory as a child of an existing pointer
+*/
+static inline void *__talloc(const void *context, size_t size)
+{
+       struct talloc_chunk *tc;
+
+       if (unlikely(context == NULL)) {
+               context = null_context;
+       }
+
+       if (unlikely(size >= MAX_TALLOC_SIZE)) {
+               return NULL;
+       }
+
+       tc = (struct talloc_chunk *)malloc(TC_HDR_SIZE+size);
+       if (unlikely(tc == NULL)) return NULL;
+
+       tc->size = size;
+       tc->flags = TALLOC_MAGIC;
+       tc->destructor = NULL;
+       tc->child = NULL;
+       tc->name = NULL;
+       tc->refs = NULL;
+
+       if (likely(context)) {
+               struct talloc_chunk *parent = talloc_chunk_from_ptr(context);
+
+               if (parent->child) {
+                       parent->child->parent = NULL;
+                       tc->next = parent->child;
+                       tc->next->prev = tc;
+               } else {
+                       tc->next = NULL;
+               }
+               tc->parent = parent;
+               tc->prev = NULL;
+               parent->child = tc;
+       } else {
+               tc->next = tc->prev = tc->parent = NULL;
+       }
+
+       return TC_PTR_FROM_CHUNK(tc);
+}
+
+/*
+  setup a destructor to be called on free of a pointer
+  the destructor should return 0 on success, or -1 on failure.
+  if the destructor fails then the free is failed, and the memory can
+  be continued to be used
+*/
+void _talloc_set_destructor(const void *ptr, int (*destructor)(void *))
+{
+       struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
+       tc->destructor = destructor;
+}
+
+/*
+  increase the reference count on a piece of memory. 
+*/
+int talloc_increase_ref_count(const void *ptr)
+{
+       if (unlikely(!talloc_reference(null_context, ptr))) {
+               return -1;
+       }
+       return 0;
+}
+
+/*
+  helper for talloc_reference()
+
+  this is referenced by a function pointer and should not be inline
+*/
+static int talloc_reference_destructor(struct talloc_reference_handle *handle)
+{
+       struct talloc_chunk *ptr_tc = talloc_chunk_from_ptr(handle->ptr);
+       _TLIST_REMOVE(ptr_tc->refs, handle);
+       return 0;
+}
+
+/*
+   more efficient way to add a name to a pointer - the name must point to a 
+   true string constant
+*/
+static inline void _talloc_set_name_const(const void *ptr, const char *name)
+{
+       struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
+       tc->name = name;
+}
+
+/*
+  internal talloc_named_const()
+*/
+static inline void *_talloc_named_const(const void *context, size_t size, const char *name)
+{
+       void *ptr;
+
+       ptr = __talloc(context, size);
+       if (unlikely(ptr == NULL)) {
+               return NULL;
+       }
+
+       _talloc_set_name_const(ptr, name);
+
+       return ptr;
+}
+
+/*
+  make a secondary reference to a pointer, hanging off the given context.
+  the pointer remains valid until both the original caller and this given
+  context are freed.
+  
+  the major use for this is when two different structures need to reference the 
+  same underlying data, and you want to be able to free the two instances separately,
+  and in either order
+*/
+void *_talloc_reference(const void *context, const void *ptr)
+{
+       struct talloc_chunk *tc;
+       struct talloc_reference_handle *handle;
+       if (unlikely(ptr == NULL)) return NULL;
+
+       tc = talloc_chunk_from_ptr(ptr);
+       handle = (struct talloc_reference_handle *)_talloc_named_const(context,
+                                                  sizeof(struct talloc_reference_handle),
+                                                  TALLOC_MAGIC_REFERENCE);
+       if (unlikely(handle == NULL)) return NULL;
+
+       /* note that we hang the destructor off the handle, not the
+          main context as that allows the caller to still setup their
+          own destructor on the context if they want to */
+       talloc_set_destructor(handle, talloc_reference_destructor);
+       handle->ptr = discard_const_p(void, ptr);
+       _TLIST_ADD(tc->refs, handle);
+       return handle->ptr;
+}
+
+
+/* 
+   internal talloc_free call
+*/
+static inline int _talloc_free(void *ptr)
+{
+       struct talloc_chunk *tc;
+
+       if (unlikely(ptr == NULL)) {
+               return -1;
+       }
+
+       tc = talloc_chunk_from_ptr(ptr);
+
+       if (unlikely(tc->refs)) {
+               int is_child;
+               /* check this is a reference from a child or grantchild
+                * back to it's parent or grantparent
+                *
+                * in that case we need to remove the reference and
+                * call another instance of talloc_free() on the current
+                * pointer.
+                */
+               is_child = talloc_is_parent(tc->refs, ptr);
+               _talloc_free(tc->refs);
+               if (is_child) {
+                       return _talloc_free(ptr);
+               }
+               return -1;
+       }
+
+       if (unlikely(tc->flags & TALLOC_FLAG_LOOP)) {
+               /* we have a free loop - stop looping */
+               return 0;
+       }
+
+       if (unlikely(tc->destructor)) {
+               talloc_destructor_t d = tc->destructor;
+               if (d == (talloc_destructor_t)-1) {
+                       return -1;
+               }
+               tc->destructor = (talloc_destructor_t)-1;
+               if (d(ptr) == -1) {
+                       tc->destructor = d;
+                       return -1;
+               }
+               tc->destructor = NULL;
+       }
+
+       if (tc->parent) {
+               _TLIST_REMOVE(tc->parent->child, tc);
+               if (tc->parent->child) {
+                       tc->parent->child->parent = tc->parent;
+               }
+       } else {
+               if (tc->prev) tc->prev->next = tc->next;
+               if (tc->next) tc->next->prev = tc->prev;
+       }
+
+       tc->flags |= TALLOC_FLAG_LOOP;
+
+       while (tc->child) {
+               /* we need to work out who will own an abandoned child
+                  if it cannot be freed. In priority order, the first
+                  choice is owner of any remaining reference to this
+                  pointer, the second choice is our parent, and the
+                  final choice is the null context. */
+               void *child = TC_PTR_FROM_CHUNK(tc->child);
+               const void *new_parent = null_context;
+               if (unlikely(tc->child->refs)) {
+                       struct talloc_chunk *p = talloc_parent_chunk(tc->child->refs);
+                       if (p) new_parent = TC_PTR_FROM_CHUNK(p);
+               }
+               if (unlikely(_talloc_free(child) == -1)) {
+                       if (new_parent == null_context) {
+                               struct talloc_chunk *p = talloc_parent_chunk(ptr);
+                               if (p) new_parent = TC_PTR_FROM_CHUNK(p);
+                       }
+                       talloc_steal(new_parent, child);
+               }
+       }
+
+       tc->flags |= TALLOC_FLAG_FREE;
+       free(tc);
+       return 0;
+}
+
+/* 
+   move a lump of memory from one talloc context to another return the
+   ptr on success, or NULL if it could not be transferred.
+   passing NULL as ptr will always return NULL with no side effects.
+*/
+void *_talloc_steal(const void *new_ctx, const void *ptr)
+{
+       struct talloc_chunk *tc, *new_tc;
+
+       if (unlikely(!ptr)) {
+               return NULL;
+       }
+
+       if (unlikely(new_ctx == NULL)) {
+               new_ctx = null_context;
+       }
+
+       tc = talloc_chunk_from_ptr(ptr);
+
+       if (unlikely(new_ctx == NULL)) {
+               if (tc->parent) {
+                       _TLIST_REMOVE(tc->parent->child, tc);
+                       if (tc->parent->child) {
+                               tc->parent->child->parent = tc->parent;
+                       }
+               } else {
+                       if (tc->prev) tc->prev->next = tc->next;
+                       if (tc->next) tc->next->prev = tc->prev;
+               }
+               
+               tc->parent = tc->next = tc->prev = NULL;
+               return discard_const_p(void, ptr);
+       }
+
+       new_tc = talloc_chunk_from_ptr(new_ctx);
+
+       if (unlikely(tc == new_tc || tc->parent == new_tc)) {
+               return discard_const_p(void, ptr);
+       }
+
+       if (tc->parent) {
+               _TLIST_REMOVE(tc->parent->child, tc);
+               if (tc->parent->child) {
+                       tc->parent->child->parent = tc->parent;
+               }
+       } else {
+               if (tc->prev) tc->prev->next = tc->next;
+               if (tc->next) tc->next->prev = tc->prev;
+       }
+
+       tc->parent = new_tc;
+       if (new_tc->child) new_tc->child->parent = NULL;
+       _TLIST_ADD(new_tc->child, tc);
+
+       return discard_const_p(void, ptr);
+}
+
+
+
+/*
+  remove a secondary reference to a pointer. This undo's what
+  talloc_reference() has done. The context and pointer arguments
+  must match those given to a talloc_reference()
+*/
+static inline int talloc_unreference(const void *context, const void *ptr)
+{
+       struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
+       struct talloc_reference_handle *h;
+
+       if (unlikely(context == NULL)) {
+               context = null_context;
+       }
+
+       for (h=tc->refs;h;h=h->next) {
+               struct talloc_chunk *p = talloc_parent_chunk(h);
+               if (p == NULL) {
+                       if (context == NULL) break;
+               } else if (TC_PTR_FROM_CHUNK(p) == context) {
+                       break;
+               }
+       }
+       if (h == NULL) {
+               return -1;
+       }
+
+       return _talloc_free(h);
+}
+
+/*
+  remove a specific parent context from a pointer. This is a more
+  controlled varient of talloc_free()
+*/
+int talloc_unlink(const void *context, void *ptr)
+{
+       struct talloc_chunk *tc_p, *new_p;
+       void *new_parent;
+
+       if (ptr == NULL) {
+               return -1;
+       }
+
+       if (context == NULL) {
+               context = null_context;
+       }
+
+       if (talloc_unreference(context, ptr) == 0) {
+               return 0;
+       }
+
+       if (context == NULL) {
+               if (talloc_parent_chunk(ptr) != NULL) {
+                       return -1;
+               }
+       } else {
+               if (talloc_chunk_from_ptr(context) != talloc_parent_chunk(ptr)) {
+                       return -1;
+               }
+       }
+       
+       tc_p = talloc_chunk_from_ptr(ptr);
+
+       if (tc_p->refs == NULL) {
+               return _talloc_free(ptr);
+       }
+
+       new_p = talloc_parent_chunk(tc_p->refs);
+       if (new_p) {
+               new_parent = TC_PTR_FROM_CHUNK(new_p);
+       } else {
+               new_parent = NULL;
+       }
+
+       if (talloc_unreference(new_parent, ptr) != 0) {
+               return -1;
+       }
+
+       talloc_steal(new_parent, ptr);
+
+       return 0;
+}
+
+/*
+  add a name to an existing pointer - va_list version
+*/
+static inline const char *talloc_set_name_v(const void *ptr, const char *fmt, va_list ap) PRINTF_ATTRIBUTE(2,0);
+
+static inline const char *talloc_set_name_v(const void *ptr, const char *fmt, va_list ap)
+{
+       struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
+       tc->name = talloc_vasprintf(ptr, fmt, ap);
+       if (likely(tc->name)) {
+               _talloc_set_name_const(tc->name, ".name");
+       }
+       return tc->name;
+}
+
+/*
+  add a name to an existing pointer
+*/
+const char *talloc_set_name(const void *ptr, const char *fmt, ...)
+{
+       const char *name;
+       va_list ap;
+       va_start(ap, fmt);
+       name = talloc_set_name_v(ptr, fmt, ap);
+       va_end(ap);
+       return name;
+}
+
+
+/*
+  create a named talloc pointer. Any talloc pointer can be named, and
+  talloc_named() operates just like talloc() except that it allows you
+  to name the pointer.
+*/
+void *talloc_named(const void *context, size_t size, const char *fmt, ...)
+{
+       va_list ap;
+       void *ptr;
+       const char *name;
+
+       ptr = __talloc(context, size);
+       if (unlikely(ptr == NULL)) return NULL;
+
+       va_start(ap, fmt);
+       name = talloc_set_name_v(ptr, fmt, ap);
+       va_end(ap);
+
+       if (unlikely(name == NULL)) {
+               _talloc_free(ptr);
+               return NULL;
+       }
+
+       return ptr;
+}
+
+/*
+  return the name of a talloc ptr, or "UNNAMED"
+*/
+const char *talloc_get_name(const void *ptr)
+{
+       struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
+       if (unlikely(tc->name == TALLOC_MAGIC_REFERENCE)) {
+               return ".reference";
+       }
+       if (likely(tc->name)) {
+               return tc->name;
+       }
+       return "UNNAMED";
+}
+
+
+/*
+  check if a pointer has the given name. If it does, return the pointer,
+  otherwise return NULL
+*/
+void *talloc_check_name(const void *ptr, const char *name)
+{
+       const char *pname;
+       if (unlikely(ptr == NULL)) return NULL;
+       pname = talloc_get_name(ptr);
+       if (likely(pname == name || strcmp(pname, name) == 0)) {
+               return discard_const_p(void, ptr);
+       }
+       return NULL;
+}
+
+
+/*
+  this is for compatibility with older versions of talloc
+*/
+void *talloc_init(const char *fmt, ...)
+{
+       va_list ap;
+       void *ptr;
+       const char *name;
+
+       /*
+        * samba3 expects talloc_report_depth_cb(NULL, ...)
+        * reports all talloc'ed memory, so we need to enable
+        * null_tracking
+        */
+       talloc_enable_null_tracking();
+
+       ptr = __talloc(NULL, 0);
+       if (unlikely(ptr == NULL)) return NULL;
+
+       va_start(ap, fmt);
+       name = talloc_set_name_v(ptr, fmt, ap);
+       va_end(ap);
+
+       if (unlikely(name == NULL)) {
+               _talloc_free(ptr);
+               return NULL;
+       }
+
+       return ptr;
+}
+
+/*
+  this is a replacement for the Samba3 talloc_destroy_pool functionality. It
+  should probably not be used in new code. It's in here to keep the talloc
+  code consistent across Samba 3 and 4.
+*/
+void talloc_free_children(void *ptr)
+{
+       struct talloc_chunk *tc;
+
+       if (unlikely(ptr == NULL)) {
+               return;
+       }
+
+       tc = talloc_chunk_from_ptr(ptr);
+
+       while (tc->child) {
+               /* we need to work out who will own an abandoned child
+                  if it cannot be freed. In priority order, the first
+                  choice is owner of any remaining reference to this
+                  pointer, the second choice is our parent, and the
+                  final choice is the null context. */
+               void *child = TC_PTR_FROM_CHUNK(tc->child);
+               const void *new_parent = null_context;
+               if (unlikely(tc->child->refs)) {
+                       struct talloc_chunk *p = talloc_parent_chunk(tc->child->refs);
+                       if (p) new_parent = TC_PTR_FROM_CHUNK(p);
+               }
+               if (unlikely(_talloc_free(child) == -1)) {
+                       if (new_parent == null_context) {
+                               struct talloc_chunk *p = talloc_parent_chunk(ptr);
+                               if (p) new_parent = TC_PTR_FROM_CHUNK(p);
+                       }
+                       talloc_steal(new_parent, child);
+               }
+       }
+}
+
+/* 
+   Allocate a bit of memory as a child of an existing pointer
+*/
+void *_talloc(const void *context, size_t size)
+{
+       return __talloc(context, size);
+}
+
+/*
+  externally callable talloc_set_name_const()
+*/
+void talloc_set_name_const(const void *ptr, const char *name)
+{
+       _talloc_set_name_const(ptr, name);
+}
+
+/*
+  create a named talloc pointer. Any talloc pointer can be named, and
+  talloc_named() operates just like talloc() except that it allows you
+  to name the pointer.
+*/
+void *talloc_named_const(const void *context, size_t size, const char *name)
+{
+       return _talloc_named_const(context, size, name);
+}
+
+/* 
+   free a talloc pointer. This also frees all child pointers of this 
+   pointer recursively
+
+   return 0 if the memory is actually freed, otherwise -1. The memory
+   will not be freed if the ref_count is > 1 or the destructor (if
+   any) returns non-zero
+*/
+int talloc_free(void *ptr)
+{
+       int saved_errno = errno, ret;
+       ret = _talloc_free(ptr);
+       if (ret == 0)
+               errno = saved_errno;
+       return ret;
+}
+
+
+
+/*
+  A talloc version of realloc. The context argument is only used if
+  ptr is NULL
+*/
+void *_talloc_realloc(const void *context, void *ptr, size_t size, const char *name)
+{
+       struct talloc_chunk *tc;
+       void *new_ptr;
+
+       /* size zero is equivalent to free() */
+       if (unlikely(size == 0)) {
+               _talloc_free(ptr);
+               return NULL;
+       }
+
+       if (unlikely(size >= MAX_TALLOC_SIZE)) {
+               return NULL;
+       }
+
+       /* realloc(NULL) is equivalent to malloc() */
+       if (ptr == NULL) {
+               return _talloc_named_const(context, size, name);
+       }
+
+       tc = talloc_chunk_from_ptr(ptr);
+
+       /* don't allow realloc on referenced pointers */
+       if (unlikely(tc->refs)) {
+               return NULL;
+       }
+
+       /* by resetting magic we catch users of the old memory */
+       tc->flags |= TALLOC_FLAG_FREE;
+
+#if ALWAYS_REALLOC
+       new_ptr = malloc(size + TC_HDR_SIZE);
+       if (new_ptr) {
+               memcpy(new_ptr, tc, tc->size + TC_HDR_SIZE);
+               free(tc);
+       }
+#else
+       new_ptr = realloc(tc, size + TC_HDR_SIZE);
+#endif
+       if (unlikely(!new_ptr)) {       
+               tc->flags &= ~TALLOC_FLAG_FREE; 
+               return NULL; 
+       }
+
+       tc = (struct talloc_chunk *)new_ptr;
+       tc->flags &= ~TALLOC_FLAG_FREE; 
+       if (tc->parent) {
+               tc->parent->child = tc;
+       }
+       if (tc->child) {
+               tc->child->parent = tc;
+       }
+
+       if (tc->prev) {
+               tc->prev->next = tc;
+       }
+       if (tc->next) {
+               tc->next->prev = tc;
+       }
+
+       tc->size = size;
+       _talloc_set_name_const(TC_PTR_FROM_CHUNK(tc), name);
+
+       return TC_PTR_FROM_CHUNK(tc);
+}
+
+/*
+  a wrapper around talloc_steal() for situations where you are moving a pointer
+  between two structures, and want the old pointer to be set to NULL
+*/
+void *_talloc_move(const void *new_ctx, const void *_pptr)
+{
+       const void **pptr = discard_const_p(const void *,_pptr);
+       void *ret = _talloc_steal(new_ctx, *pptr);
+       (*pptr) = NULL;
+       return ret;
+}
+
+/*
+  return the total size of a talloc pool (subtree)
+*/
+size_t talloc_total_size(const void *ptr)
+{
+       size_t total = 0;
+       struct talloc_chunk *c, *tc;
+
+       if (ptr == NULL) {
+               ptr = null_context;
+       }
+       if (ptr == NULL) {
+               return 0;
+       }
+
+       tc = talloc_chunk_from_ptr(ptr);
+
+       if (tc->flags & TALLOC_FLAG_LOOP) {
+               return 0;
+       }
+
+       tc->flags |= TALLOC_FLAG_LOOP;
+
+       total = tc->size;
+       for (c=tc->child;c;c=c->next) {
+               total += talloc_total_size(TC_PTR_FROM_CHUNK(c));
+       }
+
+       tc->flags &= ~TALLOC_FLAG_LOOP;
+
+       return total;
+}
+
+/*
+  return the total number of blocks in a talloc pool (subtree)
+*/
+size_t talloc_total_blocks(const void *ptr)
+{
+       size_t total = 0;
+       struct talloc_chunk *c, *tc = talloc_chunk_from_ptr(ptr);
+
+       if (tc->flags & TALLOC_FLAG_LOOP) {
+               return 0;
+       }
+
+       tc->flags |= TALLOC_FLAG_LOOP;
+
+       total++;
+       for (c=tc->child;c;c=c->next) {
+               total += talloc_total_blocks(TC_PTR_FROM_CHUNK(c));
+       }
+
+       tc->flags &= ~TALLOC_FLAG_LOOP;
+
+       return total;
+}
+
+/*
+  return the number of external references to a pointer
+*/
+size_t talloc_reference_count(const void *ptr)
+{
+       struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
+       struct talloc_reference_handle *h;
+       size_t ret = 0;
+
+       for (h=tc->refs;h;h=h->next) {
+               ret++;
+       }
+       return ret;
+}
+
+/*
+  report on memory usage by all children of a pointer, giving a full tree view
+*/
+void talloc_report_depth_cb(const void *ptr, int depth, int max_depth,
+                           void (*callback)(const void *ptr,
+                                            int depth, int max_depth,
+                                            int is_ref,
+                                            void *private_data),
+                           void *private_data)
+{
+       struct talloc_chunk *c, *tc;
+
+       if (ptr == NULL) {
+               ptr = null_context;
+       }
+       if (ptr == NULL) return;
+
+       tc = talloc_chunk_from_ptr(ptr);
+
+       if (tc->flags & TALLOC_FLAG_LOOP) {
+               return;
+       }
+
+       callback(ptr, depth, max_depth, 0, private_data);
+
+       if (max_depth >= 0 && depth >= max_depth) {
+               return;
+       }
+
+       tc->flags |= TALLOC_FLAG_LOOP;
+       for (c=tc->child;c;c=c->next) {
+               if (c->name == TALLOC_MAGIC_REFERENCE) {
+                       struct talloc_reference_handle *h = (struct talloc_reference_handle *)TC_PTR_FROM_CHUNK(c);
+                       callback(h->ptr, depth + 1, max_depth, 1, private_data);
+               } else {
+                       talloc_report_depth_cb(TC_PTR_FROM_CHUNK(c), depth + 1, max_depth, callback, private_data);
+               }
+       }
+       tc->flags &= ~TALLOC_FLAG_LOOP;
+}
+
+static void talloc_report_depth_FILE_helper(const void *ptr, int depth, int max_depth, int is_ref, void *_f)
+{
+       const char *name = talloc_get_name(ptr);
+       FILE *f = (FILE *)_f;
+
+       if (is_ref) {
+               fprintf(f, "%*sreference to: %s\n", depth*4, "", name);
+               return;
+       }
+
+       if (depth == 0) {
+               fprintf(f,"%stalloc report on '%s' (total %6lu bytes in %3lu blocks)\n", 
+                       (max_depth < 0 ? "full " :""), name,
+                       (unsigned long)talloc_total_size(ptr),
+                       (unsigned long)talloc_total_blocks(ptr));
+               return;
+       }
+
+       fprintf(f, "%*s%-30s contains %6lu bytes in %3lu blocks (ref %d) %p\n", 
+               depth*4, "",
+               name,
+               (unsigned long)talloc_total_size(ptr),
+               (unsigned long)talloc_total_blocks(ptr),
+               (int)talloc_reference_count(ptr), ptr);
+
+#if 0
+       fprintf(f, "content: ");
+       if (talloc_total_size(ptr)) {
+               int tot = talloc_total_size(ptr);
+               int i;
+
+               for (i = 0; i < tot; i++) {
+                       if ((((char *)ptr)[i] > 31) && (((char *)ptr)[i] < 126)) {
+                               fprintf(f, "%c", ((char *)ptr)[i]);
+                       } else {
+                               fprintf(f, "~%02x", ((char *)ptr)[i]);
+                       }
+               }
+       }
+       fprintf(f, "\n");
+#endif
+}
+
+/*
+  report on memory usage by all children of a pointer, giving a full tree view
+*/
+void talloc_report_depth_file(const void *ptr, int depth, int max_depth, FILE *f)
+{
+       talloc_report_depth_cb(ptr, depth, max_depth, talloc_report_depth_FILE_helper, f);
+       fflush(f);
+}
+
+/*
+  report on memory usage by all children of a pointer, giving a full tree view
+*/
+void talloc_report_full(const void *ptr, FILE *f)
+{
+       talloc_report_depth_file(ptr, 0, -1, f);
+}
+
+/*
+  report on memory usage by all children of a pointer
+*/
+void talloc_report(const void *ptr, FILE *f)
+{
+       talloc_report_depth_file(ptr, 0, 1, f);
+}
+
+/*
+  report on any memory hanging off the null context
+*/
+static void talloc_report_null(void)
+{
+       if (talloc_total_size(null_context) != 0) {
+               talloc_report(null_context, stderr);
+       }
+}
+
+/*
+  report on any memory hanging off the null context
+*/
+static void talloc_report_null_full(void)
+{
+       if (talloc_total_size(null_context) != 0) {
+               talloc_report_full(null_context, stderr);
+       }
+}
+
+/*
+  enable tracking of the NULL context
+*/
+void talloc_enable_null_tracking(void)
+{
+       if (null_context == NULL) {
+               null_context = _talloc_named_const(NULL, 0, "null_context");
+       }
+}
+
+/*
+  disable tracking of the NULL context
+*/
+void talloc_disable_null_tracking(void)
+{
+       _talloc_free(null_context);
+       null_context = NULL;
+}
+
+/*
+  enable leak reporting on exit
+*/
+void talloc_enable_leak_report(void)
+{
+       talloc_enable_null_tracking();
+       atexit(talloc_report_null);
+}
+
+/*
+  enable full leak reporting on exit
+*/
+void talloc_enable_leak_report_full(void)
+{
+       talloc_enable_null_tracking();
+       atexit(talloc_report_null_full);
+}
+
+/* 
+   talloc and zero memory. 
+*/
+void *_talloc_zero(const void *ctx, size_t size, const char *name)
+{
+       void *p = _talloc_named_const(ctx, size, name);
+
+       if (p) {
+               memset(p, '\0', size);
+       }
+
+       return p;
+}
+
+/*
+  memdup with a talloc. 
+*/
+void *_talloc_memdup(const void *t, const void *p, size_t size, const char *name)
+{
+       void *newp = _talloc_named_const(t, size, name);
+
+       if (likely(newp)) {
+               memcpy(newp, p, size);
+       }
+
+       return newp;
+}
+
+/*
+  strdup with a talloc 
+*/
+char *talloc_strdup(const void *t, const char *p)
+{
+       char *ret;
+       if (!p) {
+               return NULL;
+       }
+       ret = (char *)talloc_memdup(t, p, strlen(p) + 1);
+       if (likely(ret)) {
+               _talloc_set_name_const(ret, ret);
+       }
+       return ret;
+}
+
+/*
+ append to a talloced string 
+*/
+char *talloc_append_string(char *orig, const char *append)
+{
+       char *ret;
+       size_t olen = strlen(orig);
+       size_t alenz;
+
+       if (!append)
+               return orig;
+
+       alenz = strlen(append) + 1;
+
+       ret = talloc_realloc(NULL, orig, char, olen + alenz);
+       if (!ret)
+               return NULL;
+
+       /* append the string with the trailing \0 */
+       memcpy(&ret[olen], append, alenz);
+
+       _talloc_set_name_const(ret, ret);
+
+       return ret;
+}
+
+/*
+  strndup with a talloc 
+*/
+char *talloc_strndup(const void *t, const char *p, size_t n)
+{
+       size_t len;
+       char *ret;
+
+       for (len=0; len<n && p[len]; len++) ;
+
+       ret = (char *)__talloc(t, len + 1);
+       if (!ret) { return NULL; }
+       memcpy(ret, p, len);
+       ret[len] = 0;
+       _talloc_set_name_const(ret, ret);
+       return ret;
+}
+
+char *talloc_vasprintf(const void *t, const char *fmt, va_list ap)
+{      
+       int len;
+       char *ret;
+       va_list ap2;
+       char c;
+       
+       /* this call looks strange, but it makes it work on older solaris boxes */
+       va_copy(ap2, ap);
+       len = vsnprintf(&c, 1, fmt, ap2);
+       va_end(ap2);
+       if (len < 0) {
+               return NULL;
+       }
+
+       ret = (char *)__talloc(t, len+1);
+       if (ret) {
+               va_copy(ap2, ap);
+               vsnprintf(ret, len+1, fmt, ap2);
+               va_end(ap2);
+               _talloc_set_name_const(ret, ret);
+       }
+
+       return ret;
+}
+
+
+/*
+  Perform string formatting, and return a pointer to newly allocated
+  memory holding the result, inside a memory pool.
+ */
+char *talloc_asprintf(const void *t, const char *fmt, ...)
+{
+       va_list ap;
+       char *ret;
+
+       va_start(ap, fmt);
+       ret = talloc_vasprintf(t, fmt, ap);
+       va_end(ap);
+       return ret;
+}
+
+
+/**
+ * Realloc @p s to append the formatted result of @p fmt and @p ap,
+ * and return @p s, which may have moved.  Good for gradually
+ * accumulating output into a string buffer.
+ **/
+char *talloc_vasprintf_append(char *s, const char *fmt, va_list ap)
+{      
+       struct talloc_chunk *tc;
+       int len, s_len;
+       va_list ap2;
+       char c;
+
+       if (s == NULL) {
+               return talloc_vasprintf(NULL, fmt, ap);
+       }
+
+       tc = talloc_chunk_from_ptr(s);
+
+       s_len = tc->size - 1;
+
+       va_copy(ap2, ap);
+       len = vsnprintf(&c, 1, fmt, ap2);
+       va_end(ap2);
+
+       if (len <= 0) {
+               /* Either the vsnprintf failed or the format resulted in
+                * no characters being formatted. In the former case, we
+                * ought to return NULL, in the latter we ought to return
+                * the original string. Most current callers of this 
+                * function expect it to never return NULL.
+                */
+               return s;
+       }
+
+       s = talloc_realloc(NULL, s, char, s_len + len+1);
+       if (!s) return NULL;
+
+       va_copy(ap2, ap);
+       vsnprintf(s+s_len, len+1, fmt, ap2);
+       va_end(ap2);
+       _talloc_set_name_const(s, s);
+
+       return s;
+}
+
+/*
+  Realloc @p s to append the formatted result of @p fmt and return @p
+  s, which may have moved.  Good for gradually accumulating output
+  into a string buffer.
+ */
+char *talloc_asprintf_append(char *s, const char *fmt, ...)
+{
+       va_list ap;
+
+       va_start(ap, fmt);
+       s = talloc_vasprintf_append(s, fmt, ap);
+       va_end(ap);
+       return s;
+}
+
+/*
+  alloc an array, checking for integer overflow in the array size
+*/
+void *_talloc_array(const void *ctx, size_t el_size, unsigned count, const char *name)
+{
+       if (count >= MAX_TALLOC_SIZE/el_size) {
+               return NULL;
+       }
+       return _talloc_named_const(ctx, el_size * count, name);
+}
+
+/*
+  alloc an zero array, checking for integer overflow in the array size
+*/
+void *_talloc_zero_array(const void *ctx, size_t el_size, unsigned count, const char *name)
+{
+       if (count >= MAX_TALLOC_SIZE/el_size) {
+               return NULL;
+       }
+       return _talloc_zero(ctx, el_size * count, name);
+}
+
+/*
+  realloc an array, checking for integer overflow in the array size
+*/
+void *_talloc_realloc_array(const void *ctx, void *ptr, size_t el_size, unsigned count, const char *name)
+{
+       if (count >= MAX_TALLOC_SIZE/el_size) {
+               return NULL;
+       }
+       return _talloc_realloc(ctx, ptr, el_size * count, name);
+}
+
+/*
+  a function version of talloc_realloc(), so it can be passed as a function pointer
+  to libraries that want a realloc function (a realloc function encapsulates
+  all the basic capabilities of an allocation library, which is why this is useful)
+*/
+void *talloc_realloc_fn(const void *context, void *ptr, size_t size)
+{
+       return _talloc_realloc(context, ptr, size, NULL);
+}
+
+
+static int talloc_autofree_destructor(void *ptr)
+{
+       autofree_context = NULL;
+       return 0;
+}
+
+static void talloc_autofree(void)
+{
+       _talloc_free(autofree_context);
+}
+
+/*
+  return a context which will be auto-freed on exit
+  this is useful for reducing the noise in leak reports
+*/
+void *talloc_autofree_context(void)
+{
+       if (autofree_context == NULL) {
+               autofree_context = _talloc_named_const(NULL, 0, "autofree_context");
+               talloc_set_destructor(autofree_context, talloc_autofree_destructor);
+               atexit(talloc_autofree);
+       }
+       return autofree_context;
+}
+
+size_t talloc_get_size(const void *context)
+{
+       struct talloc_chunk *tc;
+
+       if (context == NULL)
+               return 0;
+
+       tc = talloc_chunk_from_ptr(context);
+
+       return tc->size;
+}
+
+/*
+  find a parent of this context that has the given name, if any
+*/
+void *talloc_find_parent_byname(const void *context, const char *name)
+{
+       struct talloc_chunk *tc;
+
+       if (context == NULL) {
+               return NULL;
+       }
+
+       tc = talloc_chunk_from_ptr(context);
+       while (tc) {
+               if (tc->name && strcmp(tc->name, name) == 0) {
+                       return TC_PTR_FROM_CHUNK(tc);
+               }
+               while (tc && tc->prev) tc = tc->prev;
+               if (tc) {
+                       tc = tc->parent;
+               }
+       }
+       return NULL;
+}
+
+/*
+  show the parentage of a context
+*/
+void talloc_show_parents(const void *context, FILE *file)
+{
+       struct talloc_chunk *tc;
+
+       if (context == NULL) {
+               fprintf(file, "talloc no parents for NULL\n");
+               return;
+       }
+
+       tc = talloc_chunk_from_ptr(context);
+       fprintf(file, "talloc parents of '%s'\n", talloc_get_name(context));
+       while (tc) {
+               fprintf(file, "\t'%s'\n", talloc_get_name(TC_PTR_FROM_CHUNK(tc)));
+               while (tc && tc->prev) tc = tc->prev;
+               if (tc) {
+                       tc = tc->parent;
+               }
+       }
+       fflush(file);
+}
+
+/*
+  return 1 if ptr is a parent of context
+*/
+int talloc_is_parent(const void *context, const void *ptr)
+{
+       struct talloc_chunk *tc;
+
+       if (context == NULL) {
+               return 0;
+       }
+
+       tc = talloc_chunk_from_ptr(context);
+       while (tc) {
+               if (TC_PTR_FROM_CHUNK(tc) == ptr) return 1;
+               while (tc && tc->prev) tc = tc->prev;
+               if (tc) {
+                       tc = tc->parent;
+               }
+       }
+       return 0;
+}
diff --git a/ccan/talloc/talloc.h b/ccan/talloc/talloc.h
new file mode 100644 (file)
index 0000000..7da8d97
--- /dev/null
@@ -0,0 +1,951 @@
+#ifndef CCAN_TALLOC_H
+#define CCAN_TALLOC_H
+/* 
+   Copyright (C) Andrew Tridgell 2004-2005
+   Copyright (C) Stefan Metzmacher 2006
+   
+     ** NOTE! The following LGPL license applies to the talloc
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include "config.h"
+#include "ccan/typesafe_cb/typesafe_cb.h"
+
+/*
+  this uses a little trick to allow __LINE__ to be stringified
+*/
+#ifndef __location__
+#define __TALLOC_STRING_LINE1__(s)    #s
+#define __TALLOC_STRING_LINE2__(s)   __TALLOC_STRING_LINE1__(s)
+#define __TALLOC_STRING_LINE3__  __TALLOC_STRING_LINE2__(__LINE__)
+#define __location__ __FILE__ ":" __TALLOC_STRING_LINE3__
+#endif
+
+#if HAVE_ATTRIBUTE_PRINTF
+/** Use gcc attribute to check printf fns.  a1 is the 1-based index of
+ * the parameter containing the format, and a2 the index of the first
+ * argument. Note that some gcc 2.x versions don't handle this
+ * properly **/
+#define PRINTF_ATTRIBUTE(a1, a2) __attribute__ ((format (__printf__, a1, a2)))
+#else
+#define PRINTF_ATTRIBUTE(a1, a2)
+#endif
+
+/* try to make talloc_set_destructor() and talloc_steal() type safe,
+   if we have a recent gcc */
+#if HAVE_TYPEOF
+#define _TALLOC_TYPEOF(ptr) __typeof__(ptr)
+#else
+#define _TALLOC_TYPEOF(ptr) void *
+#endif
+
+#define talloc_move(ctx, ptr) (_TALLOC_TYPEOF(*(ptr)))_talloc_move((ctx),(void *)(ptr))
+
+/**
+ * talloc - allocate dynamic memory for a type
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @type: the type to be allocated.
+ *
+ * The talloc() macro is the core of the talloc library. It takes a memory
+ * context and a type, and returns a pointer to a new area of memory of the
+ * given type.
+ *
+ * The returned pointer is itself a talloc context, so you can use it as the
+ * context argument to more calls to talloc if you wish.
+ *
+ * The returned pointer is a "child" of @ctx. This means that if you
+ * talloc_free() @ctx then the new child disappears as well.  Alternatively you
+ * can free just the child.
+ *
+ * @ctx can be NULL, in which case a new top level context is created.
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(a, unsigned int);
+ *
+ * See Also:
+ *     talloc_zero, talloc_array, talloc_steal, talloc_free.
+ */
+#define talloc(ctx, type) (type *)talloc_named_const(ctx, sizeof(type), #type)
+
+/**
+ * talloc_free - free talloc'ed memory and its children
+ * @ptr: the talloced pointer to free
+ *
+ * The talloc_free() function frees a piece of talloc memory, and all its
+ * children. You can call talloc_free() on any pointer returned by talloc().
+ *
+ * The return value of talloc_free() indicates success or failure, with 0
+ * returned for success and -1 for failure. The only possible failure condition
+ * is if the pointer had a destructor attached to it and the destructor
+ * returned -1. See talloc_set_destructor() for details on destructors.
+ * errno will be preserved unless the talloc_free fails.
+ *
+ * If this pointer has an additional parent when talloc_free() is called then
+ * the memory is not actually released, but instead the most recently
+ * established parent is destroyed. See talloc_reference() for details on
+ * establishing additional parents.
+ *
+ * For more control on which parent is removed, see talloc_unlink().
+ *
+ * talloc_free() operates recursively on its children.
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(a, unsigned int);
+ *     // Frees a and b
+ *     talloc_free(a);
+ *
+ * See Also:
+ *     talloc_set_destructor, talloc_unlink
+ */
+int talloc_free(void *ptr);
+
+/**
+ * talloc_set_destructor: set a destructor for when this pointer is freed
+ * @ptr: the talloc pointer to set the destructor on
+ * @destructor: the function to be called
+ *
+ * The function talloc_set_destructor() sets the "destructor" for the pointer
+ * @ptr.  A destructor is a function that is called when the memory used by a
+ * pointer is about to be released.  The destructor receives the pointer as an
+ * argument, and should return 0 for success and -1 for failure.
+ *
+ * The destructor can do anything it wants to, including freeing other pieces
+ * of memory. A common use for destructors is to clean up operating system
+ * resources (such as open file descriptors) contained in the structure the
+ * destructor is placed on.
+ *
+ * You can only place one destructor on a pointer. If you need more than one
+ * destructor then you can create a zero-length child of the pointer and place
+ * an additional destructor on that.
+ *
+ * To remove a destructor call talloc_set_destructor() with NULL for the
+ * destructor.
+ *
+ * If your destructor attempts to talloc_free() the pointer that it is the
+ * destructor for then talloc_free() will return -1 and the free will be
+ * ignored. This would be a pointless operation anyway, as the destructor is
+ * only called when the memory is just about to go away.
+ *
+ * Example:
+ * static int destroy_fd(int *fd)
+ * {
+ *     close(*fd);
+ *     return 0;
+ * }
+ *
+ * int *open_file(const char *filename)
+ * {
+ *     int *fd = talloc(NULL, int);
+ *     *fd = open(filename, O_RDONLY);
+ *     if (*fd < 0) {
+ *             talloc_free(fd);
+ *             return NULL;
+ *     }
+ *     // Whenever they free this, we close the file.
+ *     talloc_set_destructor(fd, destroy_fd);
+ *     return fd;
+ * }
+ *
+ * See Also:
+ *     talloc, talloc_free
+ */
+#define talloc_set_destructor(ptr, function)                                 \
+       _talloc_set_destructor((ptr), typesafe_cb(int, (function), (ptr)))
+
+/**
+ * talloc_zero - allocate zeroed dynamic memory for a type
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @type: the type to be allocated.
+ *
+ * The talloc_zero() macro is equivalent to:
+ *
+ *  ptr = talloc(ctx, type);
+ *  if (ptr) memset(ptr, 0, sizeof(type));
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc_zero(NULL, unsigned int);
+ *     b = talloc_zero(a, unsigned int);
+ *
+ * See Also:
+ *     talloc, talloc_zero_size, talloc_zero_array
+ */
+#define talloc_zero(ctx, type) (type *)_talloc_zero(ctx, sizeof(type), #type)
+
+/**
+ * talloc_array - allocate dynamic memory for an array of a given type
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @type: the type to be allocated.
+ * @count: the number of elements to be allocated.
+ *
+ * The talloc_array() macro is a safe way of allocating an array.  It is
+ * equivalent to:
+ *
+ *  (type *)talloc_size(ctx, sizeof(type) * count);
+ *
+ * except that it provides integer overflow protection for the multiply,
+ * returning NULL if the multiply overflows.
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc_zero(NULL, unsigned int);
+ *     b = talloc_array(a, unsigned int, 100);
+ *
+ * See Also:
+ *     talloc, talloc_zero_array
+ */
+#define talloc_array(ctx, type, count) (type *)_talloc_array(ctx, sizeof(type), count, #type)
+
+/**
+ * talloc_size - allocate a particular size of memory
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @size: the number of bytes to allocate
+ *
+ * The function talloc_size() should be used when you don't have a convenient
+ * type to pass to talloc(). Unlike talloc(), it is not type safe (as it
+ * returns a void *), so you are on your own for type checking.
+ *
+ * Best to use talloc() or talloc_array() instead.
+ *
+ * Example:
+ *     void *mem = talloc_size(NULL, 100);
+ *
+ * See Also:
+ *     talloc, talloc_array, talloc_zero_size
+ */
+#define talloc_size(ctx, size) talloc_named_const(ctx, size, __location__)
+
+#ifdef HAVE_TYPEOF
+/**
+ * talloc_steal - change/set the parent context of a talloc pointer
+ * @ctx: the new parent
+ * @ptr: the talloc pointer to reparent
+ *
+ * The talloc_steal() function changes the parent context of a talloc
+ * pointer. It is typically used when the context that the pointer is currently
+ * a child of is going to be freed and you wish to keep the memory for a longer
+ * time.
+ *
+ * The talloc_steal() function returns the pointer that you pass it. It does
+ * not have any failure modes.
+ *
+ * NOTE: It is possible to produce loops in the parent/child relationship if
+ * you are not careful with talloc_steal(). No guarantees are provided as to
+ * your sanity or the safety of your data if you do this.
+ *
+ * talloc_steal (new_ctx, NULL) will return NULL with no sideeffects.
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(NULL, unsigned int);
+ *     // Reparent b to a as if we'd done 'b = talloc(a, unsigned int)'.
+ *     talloc_steal(a, b);
+ *
+ * See Also:
+ *     talloc_reference
+ */
+#define talloc_steal(ctx, ptr) ({ _TALLOC_TYPEOF(ptr) _talloc_steal_ret = (_TALLOC_TYPEOF(ptr))_talloc_steal((ctx),(ptr)); _talloc_steal_ret; }) /* this extremely strange macro is to avoid some braindamaged warning stupidity in gcc 4.1.x */
+#else
+#define talloc_steal(ctx, ptr) (_TALLOC_TYPEOF(ptr))_talloc_steal((ctx),(ptr))
+#endif /* HAVE_TYPEOF */
+
+/**
+ * talloc_report_full - report all the memory used by a pointer and children.
+ * @ptr: the context to report on
+ * @f: the file to report to
+ *
+ * Recursively print the entire tree of memory referenced by the
+ * pointer. References in the tree are shown by giving the name of the pointer
+ * that is referenced.
+ *
+ * You can pass NULL for the pointer, in which case a report is printed for the
+ * top level memory context, but only if talloc_enable_null_tracking() has been
+ * called.
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(a, unsigned int);
+ *     fprintf(stderr, "Dumping memory tree for a:\n");
+ *     talloc_report_full(a, stderr);
+ *
+ * See Also:
+ *     talloc_report
+ */
+void talloc_report_full(const void *ptr, FILE *f);
+
+/**
+ * talloc_reference - add an additional parent to a context
+ * @ctx: the additional parent
+ * @ptr: the talloc pointer
+ *
+ * The talloc_reference() function makes @ctx an additional parent of @ptr.
+ *
+ * The return value of talloc_reference() is always the original pointer @ptr,
+ * unless talloc ran out of memory in creating the reference in which case it
+ * will return NULL (each additional reference consumes around 48 bytes of
+ * memory on intel x86 platforms).
+ *
+ * If @ptr is NULL, then the function is a no-op, and simply returns NULL.
+ *
+ * After creating a reference you can free it in one of the following ways:
+ *
+ *  - you can talloc_free() any parent of the original pointer. That will
+ *    reduce the number of parents of this pointer by 1, and will cause this
+ *    pointer to be freed if it runs out of parents.
+ *
+ *  - you can talloc_free() the pointer itself. That will destroy the most
+ *    recently established parent to the pointer and leave the pointer as a
+ *    child of its current parent.
+ *
+ * For more control on which parent to remove, see talloc_unlink().
+ * Example:
+ *     unsigned int *a, *b, *c;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(NULL, unsigned int);
+ *     c = talloc(a, unsigned int);
+ *     // b also serves as a parent of c.
+ *     talloc_reference(b, c);
+ */
+#define talloc_reference(ctx, ptr) (_TALLOC_TYPEOF(ptr))_talloc_reference((ctx),(ptr))
+
+/**
+ * talloc_unlink: remove a specific parent from a talloc pointer.
+ * @context: the parent to remove
+ * @ptr: the talloc pointer
+ *
+ * The talloc_unlink() function removes a specific parent from @ptr. The
+ * context passed must either be a context used in talloc_reference() with this
+ * pointer, or must be a direct parent of @ptr.
+ *
+ * Note that if the parent has already been removed using talloc_free() then
+ * this function will fail and will return -1.  Likewise, if @ptr is NULL,
+ * then the function will make no modifications and return -1.
+ *
+ * Usually you can just use talloc_free() instead of talloc_unlink(), but
+ * sometimes it is useful to have the additional control on which parent is
+ * removed.
+ * Example:
+ *     unsigned int *a, *b, *c;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(NULL, unsigned int);
+ *     c = talloc(a, unsigned int);
+ *     // b also serves as a parent of c.
+ *     talloc_reference(b, c);
+ *     talloc_unlink(b, c);
+ */
+int talloc_unlink(const void *context, void *ptr);
+
+/**
+ * talloc_report - print a summary of memory used by a pointer
+ *
+ * The talloc_report() function prints a summary report of all memory
+ * used by @ptr.  One line of report is printed for each immediate child of
+ * @ptr, showing the total memory and number of blocks used by that child.
+ *
+ * You can pass NULL for the pointer, in which case a report is printed for the
+ * top level memory context, but only if talloc_enable_null_tracking() has been
+ * called.
+ *
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(a, unsigned int);
+ *     fprintf(stderr, "Summary of memory tree for a:\n");
+ *     talloc_report(a, stderr);
+ *
+ * See Also:
+ *     talloc_report_full
+ */
+void talloc_report(const void *ptr, FILE *f);
+
+/**
+ * talloc_ptrtype - allocate a size of memory suitable for this pointer
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @ptr: the pointer whose type we are to allocate
+ *
+ * The talloc_ptrtype() macro should be used when you have a pointer and
+ * want to allocate memory to point at with this pointer. When compiling
+ * with gcc >= 3 it is typesafe. Note this is a wrapper of talloc_size()
+ * and talloc_get_name() will return the current location in the source file.
+ * and not the type.
+ *
+ * Example:
+ *     unsigned int *a = talloc_ptrtype(NULL, a);
+ */
+#define talloc_ptrtype(ctx, ptr) (_TALLOC_TYPEOF(ptr))talloc_size(ctx, sizeof(*(ptr)))
+
+/**
+ * talloc_free_children - free talloc'ed memory's children only
+ * @ptr: the talloced pointer whose children we want to free
+ *
+ * talloc_free_children() walks along the list of all children of a talloc
+ * context @ptr and talloc_free()s only the children, not the context itself.
+ * Example:
+ *     unsigned int *a, *b;
+ *     a = talloc(NULL, unsigned int);
+ *     b = talloc(a, unsigned int);
+ *     // Frees b
+ *     talloc_free_children(a);
+ */
+void talloc_free_children(void *ptr);
+
+/**
+ * talloc_new - create a new context
+ * @ctx: the context to use as a parent.
+ *
+ * This is a utility macro that creates a new memory context hanging off an
+ * exiting context, automatically naming it "talloc_new: __location__" where
+ * __location__ is the source line it is called from. It is particularly useful
+ * for creating a new temporary working context.
+ */
+#define talloc_new(ctx) talloc_named_const(ctx, 0, "talloc_new: " __location__)
+
+/**
+ * talloc_zero_size -  allocate a particular size of zeroed memory
+ *
+ * The talloc_zero_size() function is useful when you don't have a known type.
+ */
+#define talloc_zero_size(ctx, size) _talloc_zero(ctx, size, __location__)
+
+/**
+ * talloc_zero_array -  allocate an array of zeroed types
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @type: the type to be allocated.
+ * @count: the number of elements to be allocated.
+ *
+ * Just like talloc_array, but zeroes the memory.
+ */
+#define talloc_zero_array(ctx, type, count) (type *)_talloc_zero_array(ctx, sizeof(type), count, #type)
+
+/**
+ * talloc_zero_array - allocate an array of zeroed types
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @type: the type to be allocated.
+ * @count: the number of elements to be allocated.
+ *
+ * Just like talloc_array, but zeroes the memory.
+ */
+#define talloc_array_size(ctx, size, count) _talloc_array(ctx, size, count, __location__)
+
+/**
+ * talloc_array_ptrtype - allocate an array of memory suitable for this pointer
+ * @ctx: context to be parent of this allocation, or NULL.
+ * @ptr: the pointer whose type we are to allocate
+ * @count: the number of elements for the array
+ *
+ * Like talloc_ptrtype(), except it allocates an array.
+ */
+#define talloc_array_ptrtype(ctx, ptr, count) (_TALLOC_TYPEOF(ptr))talloc_array_size(ctx, sizeof(*(ptr)), count)
+
+/**
+ * talloc_realloc - resize a talloc array
+ * @ctx: the parent to assign (if p is NULL)
+ * @p: the memory to reallocate
+ * @type: the type of the object to allocate
+ * @count: the number of objects to reallocate
+ *
+ * The talloc_realloc() macro changes the size of a talloc pointer. The "count"
+ * argument is the number of elements of type "type" that you want the
+ * resulting pointer to hold.
+ *
+ * talloc_realloc() has the following equivalences:
+ *
+ *  talloc_realloc(context, NULL, type, 1) ==> talloc(context, type);
+ *  talloc_realloc(context, NULL, type, N) ==> talloc_array(context, type, N);
+ *  talloc_realloc(context, ptr, type, 0)  ==> talloc_free(ptr);
+ *
+ * The "context" argument is only used if "ptr" is NULL, otherwise it is
+ * ignored.
+ *
+ * talloc_realloc() returns the new pointer, or NULL on failure. The call will
+ * fail either due to a lack of memory, or because the pointer has more than
+ * one parent (see talloc_reference()).
+ */
+#define talloc_realloc(ctx, p, type, count) (type *)_talloc_realloc_array(ctx, p, sizeof(type), count, #type)
+
+/**
+ * talloc_realloc_size - resize talloc memory
+ * @ctx: the parent to assign (if p is NULL)
+ * @ptr: the memory to reallocate
+ * @size: the new size of memory.
+ *
+ * The talloc_realloc_size() function is useful when the type is not known so
+ * the typesafe talloc_realloc() cannot be used.
+ */
+#define talloc_realloc_size(ctx, ptr, size) _talloc_realloc(ctx, ptr, size, __location__)
+
+/**
+ * talloc_strdup - duplicate a string
+ * @ctx: the talloc context for the new string
+ * @p: the string to copy
+ *
+ * The talloc_strdup() function is equivalent to:
+ *
+ *  ptr = talloc_size(ctx, strlen(p)+1);
+ *  if (ptr) memcpy(ptr, p, strlen(p)+1);
+ *
+ * This functions sets the name of the new pointer to the passed string. This
+ * is equivalent to:
+ *
+ *  talloc_set_name_const(ptr, ptr)
+ */
+char *talloc_strdup(const void *t, const char *p);
+
+/**
+ * talloc_strndup - duplicate a limited length of a string
+ * @ctx: the talloc context for the new string
+ * @p: the string to copy
+ * @n: the maximum length of the returned string.
+ *
+ * The talloc_strndup() function is the talloc equivalent of the C library
+ * function strndup(): the result will be truncated to @n characters before
+ * the nul terminator.
+ *
+ * This functions sets the name of the new pointer to the passed string. This
+ * is equivalent to:
+ *
+ *   talloc_set_name_const(ptr, ptr)
+ */
+char *talloc_strndup(const void *t, const char *p, size_t n);
+
+/**
+ * talloc_memdup - duplicate some talloc memory
+ *
+ * The talloc_memdup() function is equivalent to:
+ *
+ *  ptr = talloc_size(ctx, size);
+ *  if (ptr) memcpy(ptr, p, size);
+ */
+#define talloc_memdup(t, p, size) _talloc_memdup(t, p, size, __location__)
+
+/**
+ * talloc_asprintf - sprintf into a talloc buffer.
+ * @t: The context to allocate the buffer from
+ * @fmt: printf-style format for the buffer.
+ *
+ * The talloc_asprintf() function is the talloc equivalent of the C library
+ * function asprintf().
+ *
+ * This functions sets the name of the new pointer to the new string. This is
+ * equivalent to:
+ *
+ *   talloc_set_name_const(ptr, ptr)
+ */
+char *talloc_asprintf(const void *t, const char *fmt, ...) PRINTF_ATTRIBUTE(2,3);
+
+/**
+ * talloc_append_string - concatenate onto a tallocated string 
+ * @orig: the tallocated string to append to
+ * @append: the string to add, or NULL to add nothing.
+ *
+ * The talloc_append_string() function appends the given formatted string to
+ * the given string.
+ *
+ * This function sets the name of the new pointer to the new string. This is
+ * equivalent to:
+ *
+ *    talloc_set_name_const(ptr, ptr)
+ */
+char *talloc_append_string(char *orig, const char *append);
+
+/**
+ * talloc_asprintf_append - sprintf onto the end of a talloc buffer.
+ * @s: The tallocated string buffer
+ * @fmt: printf-style format to append to the buffer.
+ *
+ * The talloc_asprintf_append() function appends the given formatted string to
+ * the given string.
+ *
+ * This functions sets the name of the new pointer to the new string. This is
+ * equivalent to:
+ *   talloc_set_name_const(ptr, ptr)
+ */
+char *talloc_asprintf_append(char *s, const char *fmt, ...) PRINTF_ATTRIBUTE(2,3);
+
+/**
+ * talloc_vasprintf - vsprintf into a talloc buffer.
+ * @t: The context to allocate the buffer from
+ * @fmt: printf-style format for the buffer
+ * @ap: va_list arguments
+ *
+ * The talloc_vasprintf() function is the talloc equivalent of the C library
+ * function vasprintf()
+ *
+ * This functions sets the name of the new pointer to the new string. This is
+ * equivalent to:
+ *
+ *   talloc_set_name_const(ptr, ptr)
+ */
+char *talloc_vasprintf(const void *t, const char *fmt, va_list ap) PRINTF_ATTRIBUTE(2,0);
+
+/**
+ * talloc_vasprintf_append - sprintf onto the end of a talloc buffer.
+ * @t: The context to allocate the buffer from
+ * @fmt: printf-style format for the buffer
+ * @ap: va_list arguments
+ *
+ * The talloc_vasprintf_append() function is equivalent to
+ * talloc_asprintf_append(), except it takes a va_list.
+ */
+char *talloc_vasprintf_append(char *s, const char *fmt, va_list ap) PRINTF_ATTRIBUTE(2,0);
+
+/**
+ * talloc_set_type - force the name of a pointer to a particular type
+ * @ptr: the talloc pointer
+ * @type: the type whose name to set the ptr name to.
+ *
+ * This macro allows you to force the name of a pointer to be a particular
+ * type. This can be used in conjunction with talloc_get_type() to do type
+ * checking on void* pointers.
+ *
+ * It is equivalent to this:
+ *   talloc_set_name_const(ptr, #type)
+ */
+#define talloc_set_type(ptr, type) talloc_set_name_const(ptr, #type)
+
+/**
+ * talloc_get_type - convert a talloced pointer with typechecking
+ * @ptr: the talloc pointer
+ * @type: the type which we expect the talloced pointer to be.
+ *
+ * This macro allows you to do type checking on talloc pointers. It is
+ * particularly useful for void* private pointers. It is equivalent to this:
+ *
+ *   (type *)talloc_check_name(ptr, #type)
+ */
+#define talloc_get_type(ptr, type) (type *)talloc_check_name(ptr, #type)
+
+/**
+ * talloc_find_parent_byname - find a talloc parent by type
+ * @ptr: the talloc pointer
+ * @type: the type we're looking for
+ *
+ * Find a parent memory context of the current context that has the given
+ * name. This can be very useful in complex programs where it may be difficult
+ * to pass all information down to the level you need, but you know the
+ * structure you want is a parent of another context.
+ */
+#define talloc_find_parent_bytype(ptr, type) (type *)talloc_find_parent_byname(ptr, #type)
+
+/**
+ * talloc_increase_ref_count - hold a reference to a talloc pointer
+ * @ptr: the talloc pointer
+ *
+ * The talloc_increase_ref_count(ptr) function is exactly equivalent to:
+ *
+ *  talloc_reference(NULL, ptr);
+ *
+ * You can use either syntax, depending on which you think is clearer in your
+ * code.
+ *
+ * It returns 0 on success and -1 on failure.
+ */
+int talloc_increase_ref_count(const void *ptr);
+
+/**
+ * talloc_set_name - set the name for a talloc pointer
+ * @ptr: the talloc pointer
+ * @fmt: the printf-style format string for the name
+ *
+ * Each talloc pointer has a "name". The name is used principally for debugging
+ * purposes, although it is also possible to set and get the name on a pointer
+ * in as a way of "marking" pointers in your code.
+ *
+ * The main use for names on pointer is for "talloc reports". See
+ * talloc_report() and talloc_report_full() for details. Also see
+ * talloc_enable_leak_report() and talloc_enable_leak_report_full().
+ *
+ * The talloc_set_name() function allocates memory as a child of the
+ * pointer. It is logically equivalent to:
+ *   talloc_set_name_const(ptr, talloc_asprintf(ptr, fmt, ...));
+ *
+ * Note that multiple calls to talloc_set_name() will allocate more memory
+ * without releasing the name. All of the memory is released when the ptr is
+ * freed using talloc_free().
+ */
+const char *talloc_set_name(const void *ptr, const char *fmt, ...) PRINTF_ATTRIBUTE(2,3);
+
+/**
+ * talloc_set_name_const - set a talloc pointer name to a string constant
+ * @ptr: the talloc pointer to name
+ * @name: the strucng constant.
+ *
+ * The function talloc_set_name_const() is just like talloc_set_name(), but it
+ * takes a string constant, and is much faster. It is extensively used by the
+ * "auto naming" macros, such as talloc().
+ *
+ * This function does not allocate any memory. It just copies the supplied
+ * pointer into the internal representation of the talloc ptr. This means you
+ * must not pass a name pointer to memory that will disappear before the ptr is
+ * freed with talloc_free().
+ */
+void talloc_set_name_const(const void *ptr, const char *name);
+
+/**
+ * talloc_named - create a specifically-named talloc pointer
+ * @context: the parent context for the allocation
+ * @size: the size to allocate
+ * @fmt: the printf-style format for the name
+ *
+ * The talloc_named() function creates a named talloc pointer. It is equivalent
+ * to:
+ *
+ *   ptr = talloc_size(context, size);
+ *   talloc_set_name(ptr, fmt, ....);
+ */
+void *talloc_named(const void *context, size_t size, 
+                  const char *fmt, ...) PRINTF_ATTRIBUTE(3,4);
+
+/**
+ * talloc_named_const - create a specifically-named talloc pointer
+ * @context: the parent context for the allocation
+ * @size: the size to allocate
+ * @name: the string constant to use as the name
+ *
+ * This is equivalent to:
+ *
+ *   ptr = talloc_size(context, size);
+ *   talloc_set_name_const(ptr, name);
+ */
+void *talloc_named_const(const void *context, size_t size, const char *name);
+
+/**
+ * talloc_get_name - get the name of a talloc pointer
+ * @ptr: the talloc pointer
+ *
+ * This returns the current name for the given talloc pointer. See
+ * talloc_set_name() for details.
+ */
+const char *talloc_get_name(const void *ptr);
+
+/**
+ * talloc_check_name - check if a pointer has the specified name
+ * @ptr: the talloc pointer
+ * @name: the name to compare with the pointer's name
+ *
+ * This function checks if a pointer has the specified name. If it does then
+ * the pointer is returned. It it doesn't then NULL is returned.
+ */
+void *talloc_check_name(const void *ptr, const char *name);
+
+/**
+ * talloc_init - create a top-level context of particular name
+ * @fmt: the printf-style format of the name
+ *
+ * This function creates a zero length named talloc context as a top level
+ * context. It is equivalent to:
+ *
+ *   talloc_named(NULL, 0, fmt, ...);
+ */
+void *talloc_init(const char *fmt, ...) PRINTF_ATTRIBUTE(1,2);
+
+/**
+ * talloc_total_size - get the bytes used by the pointer and its children
+ * @ptr: the talloc pointer
+ *
+ * The talloc_total_size() function returns the total size in bytes used by
+ * this pointer and all child pointers. Mostly useful for debugging.
+ *
+ * Passing NULL is allowed, but it will only give a meaningful result if
+ * talloc_enable_leak_report() or talloc_enable_leak_report_full() has been
+ * called.
+ */
+size_t talloc_total_size(const void *ptr);
+
+/**
+ * talloc_total_blocks - get the number of allocations for the pointer
+ * @ptr: the talloc pointer
+ *
+ * The talloc_total_blocks() function returns the total allocations used by
+ * this pointer and all child pointers. Mostly useful for debugging. For
+ * example, a pointer with no children will return "1".
+ *
+ * Passing NULL is allowed, but it will only give a meaningful result if
+ * talloc_enable_leak_report() or talloc_enable_leak_report_full() has been
+ * called.
+ */
+size_t talloc_total_blocks(const void *ptr);
+
+/**
+ * talloc_report_depth_cb - walk the entire talloc tree under a talloc pointer
+ * @ptr: the talloc pointer to recurse under
+ * @depth: the current depth of traversal
+ * @max_depth: maximum depth to traverse, or -1 for no maximum
+ * @callback: the function to call on each pointer
+ * @private_data: pointer to hand to @callback.
+ *
+ * This provides a more flexible reports than talloc_report(). It will
+ * recursively call the callback for the entire tree of memory referenced by
+ * the pointer. References in the tree are passed with is_ref = 1 and the
+ * pointer that is referenced.
+ *
+ * You can pass NULL for the pointer, in which case a report is printed for the
+ * top level memory context, but only if talloc_enable_leak_report() or
+ * talloc_enable_leak_report_full() has been called.
+ *
+ * The recursion is stopped when depth >= max_depth.  max_depth = -1 means only
+ * stop at leaf nodes.
+ */
+void talloc_report_depth_cb(const void *ptr, int depth, int max_depth,
+                           void (*callback)(const void *ptr,
+                                            int depth, int max_depth,
+                                            int is_ref,
+                                            void *private_data),
+                           void *private_data);
+
+/**
+ * talloc_report_depth_file - report talloc usage to a maximum depth
+ * @ptr: the talloc pointer to recurse under
+ * @depth: the current depth of traversal
+ * @max_depth: maximum depth to traverse, or -1 for no maximum
+ * @f: the file to report to
+ *
+ * This provides a more flexible reports than talloc_report(). It will let you
+ * specify the depth and max_depth.
+ */
+void talloc_report_depth_file(const void *ptr, int depth, int max_depth, FILE *f);
+
+/**
+ * talloc_enable_null_tracking - enable tracking of top-level tallocs
+ *
+ * This enables tracking of the NULL memory context without enabling leak
+ * reporting on exit. Useful for when you want to do your own leak reporting
+ * call via talloc_report_null_full();
+ */
+void talloc_enable_null_tracking(void);
+
+/**
+ * talloc_disable_null_tracking - enable tracking of top-level tallocs
+ *
+ * This disables tracking of the NULL memory context.
+ */
+void talloc_disable_null_tracking(void);
+
+/**
+ * talloc_enable_leak_report - call talloc_report on program exit
+ *
+ * This enables calling of talloc_report(NULL, stderr) when the program
+ * exits. In Samba4 this is enabled by using the --leak-report command line
+ * option.
+ *
+ * For it to be useful, this function must be called before any other talloc
+ * function as it establishes a "null context" that acts as the top of the
+ * tree. If you don't call this function first then passing NULL to
+ * talloc_report() or talloc_report_full() won't give you the full tree
+ * printout.
+ *
+ * Here is a typical talloc report:
+ *
+ * talloc report on 'null_context' (total 267 bytes in 15 blocks)
+ *         libcli/auth/spnego_parse.c:55  contains     31 bytes in   2 blocks
+ *         libcli/auth/spnego_parse.c:55  contains     31 bytes in   2 blocks
+ *         iconv(UTF8,CP850)              contains     42 bytes in   2 blocks
+ *         libcli/auth/spnego_parse.c:55  contains     31 bytes in   2 blocks
+ *         iconv(CP850,UTF8)              contains     42 bytes in   2 blocks
+ *         iconv(UTF8,UTF-16LE)           contains     45 bytes in   2 blocks
+ *         iconv(UTF-16LE,UTF8)           contains     45 bytes in   2 blocks
+ */
+void talloc_enable_leak_report(void);
+
+/**
+ * talloc_enable_leak_report - call talloc_report_full on program exit
+ *
+ * This enables calling of talloc_report_full(NULL, stderr) when the program
+ * exits. In Samba4 this is enabled by using the --leak-report-full command
+ * line option.
+ *
+ * For it to be useful, this function must be called before any other talloc
+ * function as it establishes a "null context" that acts as the top of the
+ * tree. If you don't call this function first then passing NULL to
+ * talloc_report() or talloc_report_full() won't give you the full tree
+ * printout.
+ *
+ * Here is a typical full report:
+ *
+ * full talloc report on 'root' (total 18 bytes in 8 blocks)
+ *    p1                        contains     18 bytes in   7 blocks (ref 0)
+ *         r1                        contains     13 bytes in   2 blocks (ref 0)
+ *             reference to: p2
+ *         p2                        contains      1 bytes in   1 blocks (ref 1)
+ *         x3                        contains      1 bytes in   1 blocks (ref 0)
+ *         x2                        contains      1 bytes in   1 blocks (ref 0)
+ *         x1                        contains      1 bytes in   1 blocks (ref 0)
+ */
+void talloc_enable_leak_report_full(void);
+
+/**
+ * talloc_autofree_context - a context which will be freed at exit
+ *
+ * This is a handy utility function that returns a talloc context which will be
+ * automatically freed on program exit. This can be used to reduce the noise in
+ * memory leak reports.
+ */
+void *talloc_autofree_context(void);
+
+/**
+ * talloc_get_size - get the size of an allocation
+ * @ctx: the talloc pointer whose allocation to measure.
+ *
+ * This function lets you know the amount of memory alloced so far by this
+ * context. It does NOT account for subcontext memory.  This can be used to
+ * calculate the size of an array.
+ */
+size_t talloc_get_size(const void *ctx);
+
+/**
+ * talloc_find_parent_byname - find a parent of this context with this name
+ * @ctx: the context whose ancestors to search
+ * @name: the name to look for
+ *
+ * Find a parent memory context of @ctx that has the given name. This can be
+ * very useful in complex programs where it may be difficult to pass all
+ * information down to the level you need, but you know the structure you want
+ * is a parent of another context.
+ */
+void *talloc_find_parent_byname(const void *ctx, const char *name);
+
+/* The following definitions come from talloc.c  */
+void *_talloc(const void *context, size_t size);
+void _talloc_set_destructor(const void *ptr, int (*destructor)(void *));
+size_t talloc_reference_count(const void *ptr);
+void *_talloc_reference(const void *context, const void *ptr);
+
+void *_talloc_realloc(const void *context, void *ptr, size_t size, const char *name);
+void *talloc_parent(const void *ptr);
+const char *talloc_parent_name(const void *ptr);
+void *_talloc_steal(const void *new_ctx, const void *ptr);
+void *_talloc_move(const void *new_ctx, const void *pptr);
+void *_talloc_zero(const void *ctx, size_t size, const char *name);
+void *_talloc_memdup(const void *t, const void *p, size_t size, const char *name);
+void *_talloc_array(const void *ctx, size_t el_size, unsigned count, const char *name);
+void *_talloc_zero_array(const void *ctx, size_t el_size, unsigned count, const char *name);
+void *_talloc_realloc_array(const void *ctx, void *ptr, size_t el_size, unsigned count, const char *name);
+void *talloc_realloc_fn(const void *context, void *ptr, size_t size);
+void talloc_show_parents(const void *context, FILE *file);
+int talloc_is_parent(const void *context, const void *ptr);
+
+#endif /* CCAN_TALLOC_H */
diff --git a/ccan/talloc/test/run.c b/ccan/talloc/test/run.c
new file mode 100644 (file)
index 0000000..7369186
--- /dev/null
@@ -0,0 +1,871 @@
+/* 
+   Unix SMB/CIFS implementation.
+
+   local testing of talloc routines.
+
+   Copyright (C) Andrew Tridgell 2004
+   Converted to ccan tests by Rusty Russell 2008
+   
+     ** NOTE! The following LGPL license applies to the talloc
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+#include "talloc/talloc.c"
+#include <stdbool.h>
+#include "tap/tap.h"
+
+#define torture_assert(test, expr, str)                                        \
+       ok(expr, "failure: %s [\n%s: Expression %s failed: %s\n]\n",    \
+          test, __location__, #expr, str)
+
+#define torture_assert_str_equal(test, arg1, arg2, desc)       \
+       ok(strcmp(arg1, arg2) == 0,                             \
+          "failure: %s [\n%s: Expected %s, got %s: %s\n]\n",   \
+          test, __location__, arg1, arg2, desc)
+
+#define CHECK_SIZE(test, ptr, tsize)                                   \
+       ok(talloc_total_size(ptr) == (tsize),                           \
+          "failed: %s [\nwrong '%s' tree size: got %u  expected %u\n]\n", \
+          test, #ptr,                                                  \
+          (unsigned)talloc_total_size(ptr),                            \
+          (unsigned)tsize)
+
+#define CHECK_BLOCKS(test, ptr, tblocks)                               \
+       ok(talloc_total_blocks(ptr) == (tblocks),                       \
+          "failed: %s [\nwrong '%s' tree blocks: got %u  expected %u\n]\n", \
+          test, #ptr,                                                  \
+          (unsigned)talloc_total_blocks(ptr),                          \
+          (unsigned)tblocks)
+
+#define CHECK_PARENT(test, ptr, parent)                                        \
+       ok(talloc_parent(ptr) == (parent),                              \
+          "failed: %s [\n'%s' has wrong parent: got %p  expected %p\n]\n", \
+          test, #ptr,                                                  \
+          talloc_parent(ptr),                                          \
+          (parent))
+
+/*
+  test references 
+*/
+static bool test_ref1(void)
+{
+       void *root, *p1, *p2, *ref, *r1;
+
+       root = talloc_named_const(NULL, 0, "root");
+       p1 = talloc_named_const(root, 1, "p1");
+       p2 = talloc_named_const(p1, 1, "p2");
+       talloc_named_const(p1, 1, "x1");
+       talloc_named_const(p1, 2, "x2");
+       talloc_named_const(p1, 3, "x3");
+
+       r1 = talloc_named_const(root, 1, "r1"); 
+       ref = talloc_reference(r1, p2);
+
+       CHECK_BLOCKS("ref1", p1, 5);
+       CHECK_BLOCKS("ref1", p2, 1);
+       CHECK_BLOCKS("ref1", r1, 2);
+
+       talloc_free(p2);
+
+       CHECK_BLOCKS("ref1", p1, 5);
+       CHECK_BLOCKS("ref1", p2, 1);
+       CHECK_BLOCKS("ref1", r1, 1);
+
+       talloc_free(p1);
+
+       CHECK_BLOCKS("ref1", r1, 1);
+
+       talloc_free(r1);
+
+       if (talloc_reference(root, NULL)) {
+               return false;
+       }
+
+       CHECK_BLOCKS("ref1", root, 1);
+
+       CHECK_SIZE("ref1", root, 0);
+
+       talloc_free(root);
+       return true;
+}
+
+/*
+  test references 
+*/
+static bool test_ref2(void)
+{
+       void *root, *p1, *p2, *ref, *r1;
+
+       root = talloc_named_const(NULL, 0, "root");
+       p1 = talloc_named_const(root, 1, "p1");
+       talloc_named_const(p1, 1, "x1");
+       talloc_named_const(p1, 1, "x2");
+       talloc_named_const(p1, 1, "x3");
+       p2 = talloc_named_const(p1, 1, "p2");
+
+       r1 = talloc_named_const(root, 1, "r1"); 
+       ref = talloc_reference(r1, p2);
+
+       CHECK_BLOCKS("ref2", p1, 5);
+       CHECK_BLOCKS("ref2", p2, 1);
+       CHECK_BLOCKS("ref2", r1, 2);
+
+       talloc_free(ref);
+
+       CHECK_BLOCKS("ref2", p1, 5);
+       CHECK_BLOCKS("ref2", p2, 1);
+       CHECK_BLOCKS("ref2", r1, 1);
+
+       talloc_free(p2);
+
+       CHECK_BLOCKS("ref2", p1, 4);
+       CHECK_BLOCKS("ref2", r1, 1);
+
+       talloc_free(p1);
+
+       CHECK_BLOCKS("ref2", r1, 1);
+
+       talloc_free(r1);
+
+       CHECK_SIZE("ref2", root, 0);
+
+       talloc_free(root);
+       return true;
+}
+
+/*
+  test references 
+*/
+static bool test_ref3(void)
+{
+       void *root, *p1, *p2, *ref, *r1;
+
+       root = talloc_named_const(NULL, 0, "root");
+       p1 = talloc_named_const(root, 1, "p1");
+       p2 = talloc_named_const(root, 1, "p2");
+       r1 = talloc_named_const(p1, 1, "r1");
+       ref = talloc_reference(p2, r1);
+
+       CHECK_BLOCKS("ref3", p1, 2);
+       CHECK_BLOCKS("ref3", p2, 2);
+       CHECK_BLOCKS("ref3", r1, 1);
+
+       talloc_free(p1);
+
+       CHECK_BLOCKS("ref3", p2, 2);
+       CHECK_BLOCKS("ref3", r1, 1);
+
+       talloc_free(p2);
+
+       CHECK_SIZE("ref3", root, 0);
+
+       talloc_free(root);
+
+       return true;
+}
+
+/*
+  test references 
+*/
+static bool test_ref4(void)
+{
+       void *root, *p1, *p2, *ref, *r1;
+
+       root = talloc_named_const(NULL, 0, "root");
+       p1 = talloc_named_const(root, 1, "p1");
+       talloc_named_const(p1, 1, "x1");
+       talloc_named_const(p1, 1, "x2");
+       talloc_named_const(p1, 1, "x3");
+       p2 = talloc_named_const(p1, 1, "p2");
+
+       r1 = talloc_named_const(root, 1, "r1"); 
+       ref = talloc_reference(r1, p2);
+
+       CHECK_BLOCKS("ref4", p1, 5);
+       CHECK_BLOCKS("ref4", p2, 1);
+       CHECK_BLOCKS("ref4", r1, 2);
+
+       talloc_free(r1);
+
+       CHECK_BLOCKS("ref4", p1, 5);
+       CHECK_BLOCKS("ref4", p2, 1);
+
+       talloc_free(p2);
+
+       CHECK_BLOCKS("ref4", p1, 4);
+
+       talloc_free(p1);
+
+       CHECK_SIZE("ref4", root, 0);
+
+       talloc_free(root);
+
+       return true;
+}
+
+
+/*
+  test references 
+*/
+static bool test_unlink1(void)
+{
+       void *root, *p1, *p2, *ref, *r1;
+
+       root = talloc_named_const(NULL, 0, "root");
+       p1 = talloc_named_const(root, 1, "p1");
+       talloc_named_const(p1, 1, "x1");
+       talloc_named_const(p1, 1, "x2");
+       talloc_named_const(p1, 1, "x3");
+       p2 = talloc_named_const(p1, 1, "p2");
+
+       r1 = talloc_named_const(p1, 1, "r1");   
+       ref = talloc_reference(r1, p2);
+
+       CHECK_BLOCKS("unlink", p1, 7);
+       CHECK_BLOCKS("unlink", p2, 1);
+       CHECK_BLOCKS("unlink", r1, 2);
+
+       talloc_unlink(r1, p2);
+
+       CHECK_BLOCKS("unlink", p1, 6);
+       CHECK_BLOCKS("unlink", p2, 1);
+       CHECK_BLOCKS("unlink", r1, 1);
+
+       talloc_free(p1);
+
+       CHECK_SIZE("unlink", root, 0);
+
+       talloc_free(root);
+
+       return true;
+}
+
+static int fail_destructor(void *ptr)
+{
+       return -1;
+}
+
+/*
+  miscellaneous tests to try to get a higher test coverage percentage
+*/
+static bool test_misc(void)
+{
+       void *root, *p1;
+       char *p2;
+       double *d;
+       const char *name;
+
+       root = talloc_new(NULL);
+
+       p1 = talloc_size(root, 0x7fffffff);
+       torture_assert("misc", !p1, "failed: large talloc allowed\n");
+
+       p1 = talloc_strdup(root, "foo");
+       talloc_increase_ref_count(p1);
+       talloc_increase_ref_count(p1);
+       talloc_increase_ref_count(p1);
+       CHECK_BLOCKS("misc", p1, 1);
+       CHECK_BLOCKS("misc", root, 2);
+       talloc_free(p1);
+       CHECK_BLOCKS("misc", p1, 1);
+       CHECK_BLOCKS("misc", root, 2);
+       talloc_unlink(NULL, p1);
+       CHECK_BLOCKS("misc", p1, 1);
+       CHECK_BLOCKS("misc", root, 2);
+       p2 = talloc_strdup(p1, "foo");
+       torture_assert("misc", talloc_unlink(root, p2) == -1,
+                                  "failed: talloc_unlink() of non-reference context should return -1\n");
+       torture_assert("misc", talloc_unlink(p1, p2) == 0,
+               "failed: talloc_unlink() of parent should succeed\n");
+       talloc_free(p1);
+       CHECK_BLOCKS("misc", p1, 1);
+       CHECK_BLOCKS("misc", root, 2);
+
+       name = talloc_set_name(p1, "my name is %s", "foo");
+       torture_assert_str_equal("misc", talloc_get_name(p1), "my name is foo",
+               "failed: wrong name after talloc_set_name(my name is foo)");
+       CHECK_BLOCKS("misc", p1, 2);
+       CHECK_BLOCKS("misc", root, 3);
+
+       talloc_set_name_const(p1, NULL);
+       torture_assert_str_equal ("misc", talloc_get_name(p1), "UNNAMED",
+               "failed: wrong name after talloc_set_name(NULL)");
+       CHECK_BLOCKS("misc", p1, 2);
+       CHECK_BLOCKS("misc", root, 3);
+
+       torture_assert("misc", talloc_free(NULL) == -1, 
+                                  "talloc_free(NULL) should give -1\n");
+
+       talloc_set_destructor(p1, fail_destructor);
+       torture_assert("misc", talloc_free(p1) == -1, 
+               "Failed destructor should cause talloc_free to fail\n");
+       talloc_set_destructor(p1, NULL);
+
+
+       p2 = (char *)talloc_zero_size(p1, 20);
+       torture_assert("misc", p2[19] == 0, "Failed to give zero memory\n");
+       talloc_free(p2);
+
+       torture_assert("misc", talloc_strdup(root, NULL) == NULL,
+               "failed: strdup on NULL should give NULL\n");
+
+       p2 = talloc_strndup(p1, "foo", 2);
+       torture_assert("misc", strcmp("fo", p2) == 0, 
+                                  "strndup doesn't work\n");
+       p2 = talloc_asprintf_append(p2, "o%c", 'd');
+       torture_assert("misc", strcmp("food", p2) == 0, 
+                                  "talloc_asprintf_append doesn't work\n");
+       CHECK_BLOCKS("misc", p2, 1);
+       CHECK_BLOCKS("misc", p1, 3);
+
+       p2 = talloc_asprintf_append(NULL, "hello %s", "world");
+       torture_assert("misc", strcmp("hello world", p2) == 0,
+               "talloc_asprintf_append doesn't work\n");
+       CHECK_BLOCKS("misc", p2, 1);
+       CHECK_BLOCKS("misc", p1, 3);
+       talloc_free(p2);
+
+       d = talloc_array(p1, double, 0x20000000);
+       torture_assert("misc", !d, "failed: integer overflow not detected\n");
+
+       d = talloc_realloc(p1, d, double, 0x20000000);
+       torture_assert("misc", !d, "failed: integer overflow not detected\n");
+
+       talloc_free(p1);
+       CHECK_BLOCKS("misc", root, 1);
+
+       p1 = talloc_named(root, 100, "%d bytes", 100);
+       CHECK_BLOCKS("misc", p1, 2);
+       CHECK_BLOCKS("misc", root, 3);
+       talloc_unlink(root, p1);
+
+       p1 = talloc_init("%d bytes", 200);
+       p2 = talloc_asprintf(p1, "my test '%s'", "string");
+       torture_assert_str_equal("misc", p2, "my test 'string'",
+               "failed: talloc_asprintf(\"my test '%%s'\", \"string\") gave: \"%s\"");
+       CHECK_BLOCKS("misc", p1, 3);
+       CHECK_SIZE("misc", p2, 17);
+       CHECK_BLOCKS("misc", root, 1);
+       talloc_unlink(NULL, p1);
+
+       p1 = talloc_named_const(root, 10, "p1");
+       p2 = (char *)talloc_named_const(root, 20, "p2");
+       (void)talloc_reference(p1, p2);
+       talloc_unlink(root, p2);
+       CHECK_BLOCKS("misc", p2, 1);
+       CHECK_BLOCKS("misc", p1, 2);
+       CHECK_BLOCKS("misc", root, 3);
+       talloc_unlink(p1, p2);
+       talloc_unlink(root, p1);
+
+       p1 = talloc_named_const(root, 10, "p1");
+       p2 = (char *)talloc_named_const(root, 20, "p2");
+       (void)talloc_reference(NULL, p2);
+       talloc_unlink(root, p2);
+       CHECK_BLOCKS("misc", p2, 1);
+       CHECK_BLOCKS("misc", p1, 1);
+       CHECK_BLOCKS("misc", root, 2);
+       talloc_unlink(NULL, p2);
+       talloc_unlink(root, p1);
+
+       /* Test that talloc_unlink is a no-op */
+
+       torture_assert("misc", talloc_unlink(root, NULL) == -1,
+               "failed: talloc_unlink(root, NULL) == -1\n");
+
+       CHECK_SIZE("misc", root, 0);
+
+       talloc_free(root);
+
+       CHECK_SIZE("misc", NULL, 0);
+
+       talloc_enable_leak_report();
+       talloc_enable_leak_report_full();
+
+       return true;
+}
+
+
+/*
+  test realloc
+*/
+static bool test_realloc(void)
+{
+       void *root, *p1, *p2;
+
+       root = talloc_new(NULL);
+
+       p1 = talloc_size(root, 10);
+       CHECK_SIZE("realloc", p1, 10);
+
+       p1 = talloc_realloc_size(NULL, p1, 20);
+       CHECK_SIZE("realloc", p1, 20);
+
+       talloc_new(p1);
+
+       p2 = talloc_realloc_size(p1, NULL, 30);
+
+       talloc_new(p1);
+
+       p2 = talloc_realloc_size(p1, p2, 40);
+
+       CHECK_SIZE("realloc", p2, 40);
+       CHECK_SIZE("realloc", root, 60);
+       CHECK_BLOCKS("realloc", p1, 4);
+
+       p1 = talloc_realloc_size(NULL, p1,&nb