# 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)
$(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
-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.
+++ /dev/null
-#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;
-}
+++ /dev/null
-#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 */
+++ /dev/null
-#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());
-}
+++ /dev/null
-#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;
-}
+++ /dev/null
-#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);
-}
+++ /dev/null
-#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 */
+++ /dev/null
-#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();
-}
+++ /dev/null
-#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;
-}
+++ /dev/null
-#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 */
+++ /dev/null
-#include "build_assert/build_assert.h"
-
-int main(int argc, char *argv[])
-{
-#ifdef FAIL
- return EXPR_BUILD_ASSERT(1 == 0);
-#else
- return 0;
-#endif
-}
+++ /dev/null
-#include "build_assert/build_assert.h"
-
-int main(int argc, char *argv[])
-{
-#ifdef FAIL
- BUILD_ASSERT(1 == 0);
-#endif
- return 0;
-}
+++ /dev/null
-#include "build_assert/build_assert.h"
-
-int main(int argc, char *argv[])
-{
- BUILD_ASSERT(1 == 1);
- return 0;
-}
+++ /dev/null
-#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();
-}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#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());
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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);
+}
--- /dev/null
+#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 */
--- /dev/null
+#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();
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#include "build_assert/build_assert.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+ return EXPR_BUILD_ASSERT(1 == 0);
+#else
+ return 0;
+#endif
+}
--- /dev/null
+#include "build_assert/build_assert.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+ BUILD_ASSERT(1 == 0);
+#endif
+ return 0;
+}
--- /dev/null
+#include "build_assert/build_assert.h"
+
+int main(int argc, char *argv[])
+{
+ BUILD_ASSERT(1 == 1);
+ return 0;
+}
--- /dev/null
+#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();
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#include "check_type/check_type.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+ check_type(argc, char);
+#endif
+ return 0;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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();
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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();
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#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();
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#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();
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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 */
--- /dev/null
+#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();
+}
--- /dev/null
+- Remove talloc.h cruft
+- Restore errno around (successful) talloc_free.
--- /dev/null
+#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;
+}
--- /dev/null
+<?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 <talloc/talloc.h></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->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->name</literal> are destroyed, and if
+ you do <literal
+ role="code">talloc_free(X->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>
--- /dev/null
+/*
+ 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;
+}
--- /dev/null
+#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 */
--- /dev/null
+/*
+ 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
projects / ccan / commitdiff