ccan/ccan/alloc/alloc.c

/* Licensed under LGPLv2.1+ - see LICENSE file for details */
#include <unistd.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <stdlib.h>
#include "alloc.h"
#include "bitops.h"
#include "tiny.h"
#include <ccan/build_assert/build_assert.h>
#include <ccan/likely/likely.h>
#include <ccan/alignof/alignof.h>
#include <ccan/short_types/short_types.h>
#include <ccan/compiler/compiler.h>
#include "config.h"

/*
   Inspired by (and parts taken from) Andrew Tridgell's alloc_mmap:
   http://samba.org/~tridge/junkcode/alloc_mmap/

   Copyright (C) Andrew Tridgell 2007
   
   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
 */

/* We divide the pool into this many large pages (nearest power of 2) */
#define MAX_LARGE_PAGES (256UL)

/* 32 small pages == 1 large page. */
#define BITS_FROM_SMALL_TO_LARGE_PAGE 5

#define MAX_SMALL_PAGES (MAX_LARGE_PAGES << BITS_FROM_SMALL_TO_LARGE_PAGE)

/* Smallest pool size for this scheme: 128-byte small pages.  That's
 * 9/13% overhead for 32/64 bit. */
#define MIN_USEFUL_SIZE (MAX_SMALL_PAGES * 128)

/* Every 4 buckets, we jump up a power of 2. ...8 10 12 14 16 20 24 28 32... */
#define INTER_BUCKET_SPACE 4

#define SMALL_PAGES_PER_LARGE_PAGE (1 << BITS_FROM_SMALL_TO_LARGE_PAGE)

/* FIXME: Figure this out properly. */
#define MAX_SIZE (1 << 30)

/* How few object to fit in a page before using a larger one? (8) */
#define MAX_PAGE_OBJECT_ORDER	3

#define BITS_PER_LONG (sizeof(long) * CHAR_BIT)

struct bucket_state {
	u32 elements_per_page;
	u16 page_list;
	u16 full_list;
};

struct header {
	/* Bitmap of which pages are large. */
	unsigned long pagesize[MAX_LARGE_PAGES / BITS_PER_LONG];

	/* List of unused small/large pages. */
	u16 small_free_list;
	u16 large_free_list;

	/* List of huge allocs. */
	unsigned long huge;

	/* This is less defined: we have two buckets for each power of 2 */
	struct bucket_state bs[1];
};

struct huge_alloc {
	unsigned long next, prev;
	unsigned long off, len;
};

struct page_header {
	u16 next, prev;
	/* FIXME: We can just count all-0 and all-1 used[] elements. */
	unsigned elements_used : 25;
	unsigned bucket : 7;
	unsigned long used[1]; /* One bit per element. */
};

/*
 * Every 4 buckets, the size doubles.
 * Between buckets, sizes increase linearly.
 *
 * eg. bucket 40 = 2^10			= 1024
 *     bucket 41 = 2^10 + 2^10*4	= 1024 + 256
 *     bucket 42 = 2^10 + 2^10*4	= 1024 + 512
 *     bucket 43 = 2^10 + 2^10*4	= 1024 + 768
 *     bucket 45 = 2^11			= 2048
 *
 * Care is taken to handle low numbered buckets, at cost of overflow.
 */
static unsigned long bucket_to_size(unsigned int bucket)
{
	unsigned long base = 1UL << (bucket / INTER_BUCKET_SPACE);
	return base + ((bucket % INTER_BUCKET_SPACE)
		       << (bucket / INTER_BUCKET_SPACE))
		/ INTER_BUCKET_SPACE;
}

/*
 * Say size is 10.
 *   fls(size/2) == 3.  1 << 3 == 8, so we're 2 too large, out of a possible
 * 8 too large.  That's 1/4 of the way to the next power of 2 == 1 bucket.
 *
 * We make sure we round up.  Note that this fails on 32 bit at size
 * 1879048193 (around bucket 120).
 */
static unsigned int size_to_bucket(unsigned long size)
{
	unsigned int base = afls(size/2);
	unsigned long overshoot;

	overshoot = size - (1UL << base);
	return base * INTER_BUCKET_SPACE
		+ ((overshoot * INTER_BUCKET_SPACE + (1UL << base)-1) >> base);
}

static unsigned int small_page_bits(unsigned long poolsize)
{
	return afls(poolsize / MAX_SMALL_PAGES - 1);
}

static struct page_header *from_pgnum(struct header *head,
				      unsigned long pgnum,
				      unsigned sp_bits)
{
	return (struct page_header *)((char *)head + (pgnum << sp_bits));
}

static u16 to_pgnum(struct header *head, void *p, unsigned sp_bits)
{
	return ((char *)p - (char *)head) >> sp_bits;
}

static size_t used_size(unsigned int num_elements)
{
	return align_up(num_elements, BITS_PER_LONG) / CHAR_BIT;
}

/*
 * We always align the first entry to the lower power of 2.
 * eg. the 12-byte bucket gets 8-byte aligned.  The 4096-byte bucket
 * gets 4096-byte aligned.
 */
static unsigned long page_header_size(unsigned int align_bits,
				      unsigned long num_elements)
{
	unsigned long size;

	size = sizeof(struct page_header)
		- sizeof(((struct page_header *)0)->used)
		+ used_size(num_elements);
	return align_up(size, 1UL << align_bits);
}

static void add_to_list(struct header *head,
			u16 *list, struct page_header *ph, unsigned sp_bits)
{
	unsigned long h = *list, offset = to_pgnum(head, ph, sp_bits);

	ph->next = h;
	if (h) {
		struct page_header *prev = from_pgnum(head, h, sp_bits);
		assert(prev->prev == 0);
		prev->prev = offset;
	}
	*list = offset;
	ph->prev = 0;
}

static void del_from_list(struct header *head,
			  u16 *list, struct page_header *ph, unsigned sp_bits)
{
	/* Front of list? */
	if (ph->prev == 0) {
		*list = ph->next;
	} else {
		struct page_header *prev = from_pgnum(head, ph->prev, sp_bits);
		prev->next = ph->next;
	}
	if (ph->next != 0) {
		struct page_header *next = from_pgnum(head, ph->next, sp_bits);
		next->prev = ph->prev;
	}
}

static u16 pop_from_list(struct header *head,
				   u16 *list,
				   unsigned int sp_bits)
{
	u16 h = *list;
	struct page_header *ph = from_pgnum(head, h, sp_bits);

	if (likely(h)) {
		*list = ph->next;
		if (*list)
			from_pgnum(head, *list, sp_bits)->prev = 0;
	}
	return h;
}

static void add_to_huge_list(struct header *head, struct huge_alloc *ha)
{
	unsigned long h = head->huge;
	unsigned long offset = (char *)ha - (char *)head;

	ha->next = h;
	if (h) {
		struct huge_alloc *prev = (void *)((char *)head + h);
		assert(prev->prev == 0);
		prev->prev = offset;
	}
	head->huge = offset;
	ha->prev = 0;
}

static void del_from_huge(struct header *head, struct huge_alloc *ha)
{
	/* Front of list? */
	if (ha->prev == 0) {
		head->huge = ha->next;
	} else {
		struct huge_alloc *prev = (void *)((char *)head + ha->prev);
		prev->next = ha->next;
	}
	if (ha->next != 0) {
		struct huge_alloc *next = (void *)((char *)head + ha->next);
		next->prev = ha->prev;
	}
}

static void add_small_page_to_freelist(struct header *head,
				       struct page_header *ph,
				       unsigned int sp_bits)
{
	add_to_list(head, &head->small_free_list, ph, sp_bits);
}

static void add_large_page_to_freelist(struct header *head,
				       struct page_header *ph,
				       unsigned int sp_bits)
{
	add_to_list(head, &head->large_free_list, ph, sp_bits);
}

static void add_to_bucket_list(struct header *head,
			       struct bucket_state *bs,
			       struct page_header *ph,
			       unsigned int sp_bits)
{
	add_to_list(head, &bs->page_list, ph, sp_bits);
}

static void del_from_bucket_list(struct header *head,
				 struct bucket_state *bs,
				 struct page_header *ph,
				 unsigned int sp_bits)
{
	del_from_list(head, &bs->page_list, ph, sp_bits);
}

static void del_from_bucket_full_list(struct header *head,
				      struct bucket_state *bs,
				      struct page_header *ph,
				      unsigned int sp_bits)
{
	del_from_list(head, &bs->full_list, ph, sp_bits);
}

static void add_to_bucket_full_list(struct header *head,
				    struct bucket_state *bs,
				    struct page_header *ph,
				    unsigned int sp_bits)
{
	add_to_list(head, &bs->full_list, ph, sp_bits);
}

static void clear_bit(unsigned long bitmap[], unsigned int off)
{
	bitmap[off / BITS_PER_LONG] &= ~(1UL << (off % BITS_PER_LONG));
}

static bool test_bit(const unsigned long bitmap[], unsigned int off)
{
	return bitmap[off / BITS_PER_LONG] & (1UL << (off % BITS_PER_LONG));
}

static void set_bit(unsigned long bitmap[], unsigned int off)
{
	bitmap[off / BITS_PER_LONG] |= (1UL << (off % BITS_PER_LONG));
}

/* There must be a bit to be found. */
static unsigned int find_free_bit(const unsigned long bitmap[])
{
	unsigned int i;

	for (i = 0; bitmap[i] == -1UL; i++);
	return (i*BITS_PER_LONG) + affsl(~bitmap[i]) - 1;
}

/* How many elements can we fit in a page? */
static unsigned long elements_per_page(unsigned long align_bits,
				       unsigned long esize,
				       unsigned long psize)
{
	unsigned long num, overhead;

	/* First approximation: no extra room for bitmap. */
	overhead = align_up(sizeof(struct page_header), 1UL << align_bits);
	num = (psize - overhead) / esize;

	while (page_header_size(align_bits, num) + esize * num > psize)
		num--;
	return num;
}

static bool large_page_bucket(unsigned int bucket, unsigned int sp_bits)
{
	unsigned long max_smallsize;

	/* Note: this doesn't take into account page header. */
	max_smallsize = (1UL << sp_bits) >> MAX_PAGE_OBJECT_ORDER;

	return bucket_to_size(bucket) > max_smallsize;
}

static unsigned int max_bucket(unsigned int lp_bits)
{
	return (lp_bits - MAX_PAGE_OBJECT_ORDER) * INTER_BUCKET_SPACE;
}

void alloc_init(void *pool, unsigned long poolsize)
{
	struct header *head = pool;
	struct page_header *ph;
	unsigned int lp_bits, sp_bits, num_buckets;
	unsigned long header_size, i;

	if (poolsize < MIN_USEFUL_SIZE) {
		tiny_alloc_init(pool, poolsize);
		return;
	}

	/* We rely on page numbers fitting in 16 bit. */
	BUILD_ASSERT(MAX_SMALL_PAGES < 65536);
	
	sp_bits = small_page_bits(poolsize);
	lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;

	num_buckets = max_bucket(lp_bits);

	head = pool;
	header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);

	memset(head, 0, header_size);
	for (i = 0; i < num_buckets; i++) {
		unsigned long pagesize;

		if (large_page_bucket(i, sp_bits))
			pagesize = 1UL << lp_bits;
		else
			pagesize = 1UL << sp_bits;

		head->bs[i].elements_per_page
			= elements_per_page(i / INTER_BUCKET_SPACE,
					    bucket_to_size(i),
					    pagesize);
	}

	/* They start as all large pages. */
	memset(head->pagesize, 0xFF, sizeof(head->pagesize));
	/* FIXME: small pages for last bit? */

	/* Split first page into small pages. */
	assert(header_size < (1UL << lp_bits));
	clear_bit(head->pagesize, 0);

	/* Skip over page(s) used by header, add rest to free list */
	for (i = align_up(header_size, (1UL << sp_bits)) >> sp_bits;
	     i < SMALL_PAGES_PER_LARGE_PAGE;
	     i++) {
		ph = from_pgnum(head, i, sp_bits);
		ph->elements_used = 0;
		add_small_page_to_freelist(head, ph, sp_bits);
	}

	/* Add the rest of the pages as large pages. */
	i = SMALL_PAGES_PER_LARGE_PAGE;
	while ((i << sp_bits) + (1UL << lp_bits) <= poolsize) {
		assert(i < MAX_SMALL_PAGES);
		ph = from_pgnum(head, i, sp_bits);
		ph->elements_used = 0;
		add_large_page_to_freelist(head, ph, sp_bits);
		i += SMALL_PAGES_PER_LARGE_PAGE;
	}
}

/* A large page worth of small pages are free: delete them from free list. */
static void del_large_from_small_free_list(struct header *head,
					   struct page_header *ph,
					   unsigned int sp_bits)
{
	unsigned long i;

	for (i = 0; i < SMALL_PAGES_PER_LARGE_PAGE; i++) {
		del_from_list(head, &head->small_free_list,
			      (struct page_header *)((char *)ph
						     + (i << sp_bits)),
			      sp_bits);
	}
}

static bool all_empty(struct header *head,
		      unsigned long pgnum,
		      unsigned sp_bits)
{
	unsigned long i;

	for (i = 0; i < SMALL_PAGES_PER_LARGE_PAGE; i++) {
		struct page_header *ph = from_pgnum(head, pgnum + i, sp_bits);
		if (ph->elements_used)
			return false;
	}
	return true;
}

static void recombine_small_pages(struct header *head, unsigned long poolsize,
				  unsigned int sp_bits)
{
	unsigned long i;
	unsigned int lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;

	/* Look for small pages to coalesce, after first large page. */
	for (i = SMALL_PAGES_PER_LARGE_PAGE;
	     i < (poolsize >> lp_bits) << BITS_FROM_SMALL_TO_LARGE_PAGE;
	     i += SMALL_PAGES_PER_LARGE_PAGE) {
		/* Already a large page? */
		if (test_bit(head->pagesize, i / SMALL_PAGES_PER_LARGE_PAGE))
			continue;
		if (all_empty(head, i, sp_bits)) {
			struct page_header *ph = from_pgnum(head, i, sp_bits);
			set_bit(head->pagesize,
				i / SMALL_PAGES_PER_LARGE_PAGE);
			del_large_from_small_free_list(head, ph, sp_bits);
			add_large_page_to_freelist(head, ph, sp_bits);
		}
	}
}

static u16 get_large_page(struct header *head, unsigned long poolsize,
			  unsigned int sp_bits)
{
	unsigned int page;

	page = pop_from_list(head, &head->large_free_list, sp_bits);
	if (likely(page))
		return page;

	recombine_small_pages(head, poolsize, sp_bits);

	return pop_from_list(head, &head->large_free_list, sp_bits);
}

/* Returns small page. */
static unsigned long break_up_large_page(struct header *head,
					 unsigned int sp_bits,
					 u16 lpage)
{
	unsigned int i;

	clear_bit(head->pagesize, lpage >> BITS_FROM_SMALL_TO_LARGE_PAGE);

	for (i = 1; i < SMALL_PAGES_PER_LARGE_PAGE; i++) {
		struct page_header *ph = from_pgnum(head, lpage + i, sp_bits);
		/* Initialize this: huge_alloc reads it. */
		ph->elements_used = 0;
		add_small_page_to_freelist(head, ph, sp_bits);
	}

	return lpage;
}

static u16 get_small_page(struct header *head, unsigned long poolsize,
			  unsigned int sp_bits)
{
	u16 ret;

	ret = pop_from_list(head, &head->small_free_list, sp_bits);
	if (likely(ret))
		return ret;
	ret = get_large_page(head, poolsize, sp_bits);
	if (likely(ret))
		ret = break_up_large_page(head, sp_bits, ret);
	return ret;
}

static bool huge_allocated(struct header *head, unsigned long offset)
{
	unsigned long i;
	struct huge_alloc *ha;

	for (i = head->huge; i; i = ha->next) {
		ha = (void *)((char *)head + i);
		if (ha->off <= offset && ha->off + ha->len > offset)
			return true;
	}
	return false;
}

/* They want something really big.  Aim for contiguous pages (slow). */
static COLD void *huge_alloc(void *pool, unsigned long poolsize,
			     unsigned long size, unsigned long align)
{
	struct header *head = pool;
	struct huge_alloc *ha;
	unsigned long i, sp_bits, lp_bits, num, header_size;

	sp_bits = small_page_bits(poolsize);
	lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;

	/* Allocate tracking structure optimistically. */
	ha = alloc_get(pool, poolsize, sizeof(*ha), ALIGNOF(*ha));
	if (!ha)
		return NULL;

	/* First search for contiguous small pages... */
	header_size = sizeof(*head) + sizeof(head->bs) * (max_bucket(lp_bits)-1);

	num = 0;
	for (i = (header_size + (1UL << sp_bits) - 1) >> sp_bits;
	     i << sp_bits < poolsize;
	     i++) {
		struct page_header *pg;
		unsigned long off = (i << sp_bits);

		/* Skip over large pages. */
		if (test_bit(head->pagesize, i >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
			i += (1UL << BITS_FROM_SMALL_TO_LARGE_PAGE)-1;
			continue;
		}

		/* Does this page meet alignment requirements? */
		if (!num && off % align != 0)
			continue;

		/* FIXME: This makes us O(n^2). */
		if (huge_allocated(head, off)) {
			num = 0;
			continue;
		}

		pg = (struct page_header *)((char *)head + off);
		if (pg->elements_used) {
			num = 0;
			continue;
		}

		num++;
		if (num << sp_bits >= size) {
			unsigned long pgnum;

			/* Remove from free list. */
			for (pgnum = i; pgnum > i - num; pgnum--) {
				pg = from_pgnum(head, pgnum, sp_bits);
				del_from_list(head,
					      &head->small_free_list,
					      pg, sp_bits);
			}
			ha->off = (i - num + 1) << sp_bits;
			ha->len = num << sp_bits;
			goto done;
		}
	}

	/* Now search for large pages... */
	recombine_small_pages(head, poolsize, sp_bits);

	num = 0;
	for (i = (header_size + (1UL << lp_bits) - 1) >> lp_bits;
	     (i << lp_bits) < poolsize; i++) {
		struct page_header *pg;
		unsigned long off = (i << lp_bits);

		/* Ignore small pages. */
		if (!test_bit(head->pagesize, i))
			continue;

		/* Does this page meet alignment requirements? */
		if (!num && off % align != 0)
			continue;

		/* FIXME: This makes us O(n^2). */
		if (huge_allocated(head, off)) {
			num = 0;
			continue;
		}

		pg = (struct page_header *)((char *)head + off);
		if (pg->elements_used) {
			num = 0;
			continue;
		}

		num++;
		if (num << lp_bits >= size) {
			unsigned long pgnum;

			/* Remove from free list. */
			for (pgnum = i; pgnum > i - num; pgnum--) {
				pg = from_pgnum(head, pgnum, lp_bits);
				del_from_list(head,
					      &head->large_free_list,
					      pg, sp_bits);
			}
			ha->off = (i - num + 1) << lp_bits;
			ha->len = num << lp_bits;
			goto done;
		}
	}

	/* Unable to satisfy: free huge alloc structure. */
	alloc_free(pool, poolsize, ha);
	return NULL;

done:
	add_to_huge_list(pool, ha);
	return (char *)pool + ha->off;
}

static COLD void
huge_free(struct header *head, unsigned long poolsize, void *free)
{
	unsigned long i, off, pgnum, free_off = (char *)free - (char *)head;
	unsigned int sp_bits, lp_bits;
	struct huge_alloc *ha;

	for (i = head->huge; i; i = ha->next) {
		ha = (void *)((char *)head + i);
		if (free_off == ha->off)
			break;
	}
	assert(i);

	/* Free up all the pages, delete and free ha */
	sp_bits = small_page_bits(poolsize);
	lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;
	pgnum = free_off >> sp_bits;

	if (test_bit(head->pagesize, pgnum >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
		for (off = ha->off;
		     off < ha->off + ha->len;
		     off += 1UL << lp_bits) {
			add_large_page_to_freelist(head,
						   (void *)((char *)head + off),
						   sp_bits);
		}
	} else {
		for (off = ha->off;
		     off < ha->off + ha->len;
		     off += 1UL << sp_bits) {
			add_small_page_to_freelist(head,
						   (void *)((char *)head + off),
						   sp_bits);
		}
	}
	del_from_huge(head, ha);
	alloc_free(head, poolsize, ha);
}

static COLD unsigned long huge_size(struct header *head, void *p)
{
	unsigned long i, off = (char *)p - (char *)head;
	struct huge_alloc *ha;

	for (i = head->huge; i; i = ha->next) {
		ha = (void *)((char *)head + i);
		if (off == ha->off) {
			return ha->len;
		}
	}
	abort();
}

void *alloc_get(void *pool, unsigned long poolsize,
		unsigned long size, unsigned long align)
{
	struct header *head = pool;
	unsigned int bucket;
	unsigned long i;
	struct bucket_state *bs;
	struct page_header *ph;
	unsigned int sp_bits;

	if (poolsize < MIN_USEFUL_SIZE) {
		return tiny_alloc_get(pool, poolsize, size, align);
	}

	size = align_up(size, align);
	if (unlikely(!size))
		size = 1;
	bucket = size_to_bucket(size);

	sp_bits = small_page_bits(poolsize);

	if (bucket >= max_bucket(sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE)) {
		return huge_alloc(pool, poolsize, size, align);
	}

	bs = &head->bs[bucket];

	if (!bs->page_list) {
		struct page_header *ph;

		if (large_page_bucket(bucket, sp_bits))
			bs->page_list = get_large_page(head, poolsize,
						       sp_bits);
		else
			bs->page_list = get_small_page(head, poolsize,
						       sp_bits);
		/* FIXME: Try large-aligned alloc?  Header stuffing? */
		if (unlikely(!bs->page_list))
			return NULL;
		ph = from_pgnum(head, bs->page_list, sp_bits);
		ph->bucket = bucket;
		ph->elements_used = 0;
		ph->next = 0;
		memset(ph->used, 0, used_size(bs->elements_per_page));
	}

	ph = from_pgnum(head, bs->page_list, sp_bits);

	i = find_free_bit(ph->used);
	set_bit(ph->used, i);
	ph->elements_used++;

	/* check if this page is now full */
	if (unlikely(ph->elements_used == bs->elements_per_page)) {
		del_from_bucket_list(head, bs, ph, sp_bits);
		add_to_bucket_full_list(head, bs, ph, sp_bits);
	}

	return (char *)ph + page_header_size(ph->bucket / INTER_BUCKET_SPACE,
					     bs->elements_per_page)
	       + i * bucket_to_size(bucket);
}

void alloc_free(void *pool, unsigned long poolsize, void *free)
{
	struct header *head = pool;
	struct bucket_state *bs;
	unsigned int sp_bits;
	unsigned long i, pgnum, pgoffset, offset = (char *)free - (char *)pool;
	bool smallpage;
	struct page_header *ph;

	if (poolsize < MIN_USEFUL_SIZE) {
		tiny_alloc_free(pool, poolsize, free);
		return;
	}
	
	/* Get page header. */
	sp_bits = small_page_bits(poolsize);
	pgnum = offset >> sp_bits;

	/* Big page? Round down further. */
	if (test_bit(head->pagesize, pgnum >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
		smallpage = false;
		pgnum &= ~(SMALL_PAGES_PER_LARGE_PAGE - 1);
	} else
		smallpage = true;

	/* Step back to page header. */
	ph = from_pgnum(head, pgnum, sp_bits);
	if ((void *)ph == free) {
		huge_free(head, poolsize, free);
		return;
	}

	bs = &head->bs[ph->bucket];
	pgoffset = offset - (pgnum << sp_bits)
		- page_header_size(ph->bucket / INTER_BUCKET_SPACE,
				   bs->elements_per_page);

	if (unlikely(ph->elements_used == bs->elements_per_page)) {
		del_from_bucket_full_list(head, bs, ph, sp_bits);
		add_to_bucket_list(head, bs, ph, sp_bits);
	}

	/* Which element are we? */
	i = pgoffset / bucket_to_size(ph->bucket);
	clear_bit(ph->used, i);
	ph->elements_used--;

	if (unlikely(ph->elements_used == 0)) {
		bs = &head->bs[ph->bucket];
		del_from_bucket_list(head, bs, ph, sp_bits);
		if (smallpage)
			add_small_page_to_freelist(head, ph, sp_bits);
		else
			add_large_page_to_freelist(head, ph, sp_bits);
	}
}

unsigned long alloc_size(void *pool, unsigned long poolsize, void *p)
{
	struct header *head = pool;
	unsigned int pgnum, sp_bits;
	unsigned long offset = (char *)p - (char *)pool;
	struct page_header *ph;

	if (poolsize < MIN_USEFUL_SIZE)
		return tiny_alloc_size(pool, poolsize, p);

	/* Get page header. */
	sp_bits = small_page_bits(poolsize);
	pgnum = offset >> sp_bits;

	/* Big page? Round down further. */
	if (test_bit(head->pagesize, pgnum >> BITS_FROM_SMALL_TO_LARGE_PAGE))
		pgnum &= ~(SMALL_PAGES_PER_LARGE_PAGE - 1);

	/* Step back to page header. */
	ph = from_pgnum(head, pgnum, sp_bits);
	if ((void *)ph == p)
		return huge_size(head, p);

	return bucket_to_size(ph->bucket);
}

/* Useful for gdb breakpoints. */
static bool check_fail(void)
{
	return false;
}

static unsigned long count_bits(const unsigned long bitmap[],
				unsigned long limit)
{
	unsigned long i, count = 0;

	while (limit >= BITS_PER_LONG) {
		count += popcount(bitmap[0]);
		bitmap++;
		limit -= BITS_PER_LONG;
	}

	for (i = 0; i < limit; i++)
		if (test_bit(bitmap, i))
			count++;
	return count;
}

static bool out_of_bounds(unsigned long pgnum,
			  unsigned int sp_bits,
			  unsigned long pagesize,
			  unsigned long poolsize)
{
	if (((pgnum << sp_bits) >> sp_bits) != pgnum)
		return true;

	if ((pgnum << sp_bits) > poolsize)
		return true;

	return ((pgnum << sp_bits) + pagesize > poolsize);
}

static bool check_bucket(struct header *head,
			 unsigned long poolsize,
			 unsigned long pages[],
			 struct bucket_state *bs,
			 unsigned int bindex)
{
	bool lp_bucket;
	struct page_header *ph;
	unsigned long taken, i, prev, pagesize, sp_bits, lp_bits;

	sp_bits = small_page_bits(poolsize);
	lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;

	lp_bucket = large_page_bucket(bindex, sp_bits);

	pagesize = 1UL << (lp_bucket ? lp_bits : sp_bits);

	/* This many elements fit? */
	taken = page_header_size(bindex / INTER_BUCKET_SPACE,
				 bs->elements_per_page);
	taken += bucket_to_size(bindex) * bs->elements_per_page;
	if (taken > pagesize)
		return check_fail();

	/* One more wouldn't fit? */
	taken = page_header_size(bindex / INTER_BUCKET_SPACE,
				 bs->elements_per_page + 1);
	taken += bucket_to_size(bindex) * (bs->elements_per_page + 1);
	if (taken <= pagesize)
		return check_fail();

	/* Walk used list. */
	prev = 0;
	for (i = bs->page_list; i; i = ph->next) {
		/* Bad pointer? */
		if (out_of_bounds(i, sp_bits, pagesize, poolsize))
			return check_fail();
		/* Wrong size page? */
		if (!!test_bit(head->pagesize, i >> BITS_FROM_SMALL_TO_LARGE_PAGE)
		    != lp_bucket)
			return check_fail();
		/* Large page not on boundary? */
		if (lp_bucket && (i % SMALL_PAGES_PER_LARGE_PAGE) != 0)
			return check_fail();
		ph = from_pgnum(head, i, sp_bits);
		/* Linked list corrupt? */
		if (ph->prev != prev)
			return check_fail();
		/* Already seen this page? */
		if (test_bit(pages, i))
			return check_fail();
		set_bit(pages, i);
		/* Empty or full? */
		if (ph->elements_used == 0)
			return check_fail();
		if (ph->elements_used >= bs->elements_per_page)
			return check_fail();
		/* Used bits don't agree? */
		if (ph->elements_used != count_bits(ph->used,
						    bs->elements_per_page))
			return check_fail();
		/* Wrong bucket? */
		if (ph->bucket != bindex)
			return check_fail();
		prev = i;
	}

	/* Walk full list. */
	prev = 0;
	for (i = bs->full_list; i; i = ph->next) {
		/* Bad pointer? */
		if (out_of_bounds(i, sp_bits, pagesize, poolsize))
			return check_fail();
		/* Wrong size page? */
		if (!!test_bit(head->pagesize, i >> BITS_FROM_SMALL_TO_LARGE_PAGE)
		    != lp_bucket)
		/* Large page not on boundary? */
		if (lp_bucket && (i % SMALL_PAGES_PER_LARGE_PAGE) != 0)
			return check_fail();
		ph = from_pgnum(head, i, sp_bits);
		/* Linked list corrupt? */
		if (ph->prev != prev)
			return check_fail();
		/* Already seen this page? */
		if (test_bit(pages, i))
			return check_fail();
		set_bit(pages, i);
		/* Not full? */
		if (ph->elements_used != bs->elements_per_page)
			return check_fail();
		/* Used bits don't agree? */
		if (ph->elements_used != count_bits(ph->used,
						    bs->elements_per_page))
			return check_fail();
		/* Wrong bucket? */
		if (ph->bucket != bindex)
			return check_fail();
		prev = i;
	}
	return true;
}

bool alloc_check(void *pool, unsigned long poolsize)
{
	struct header *head = pool;
	unsigned long prev, i, lp_bits, sp_bits, header_size, num_buckets;
	struct page_header *ph;
	struct huge_alloc *ha;
	unsigned long pages[MAX_SMALL_PAGES / BITS_PER_LONG] = { 0 };

	if (poolsize < MIN_USEFUL_SIZE)
		return tiny_alloc_check(pool, poolsize);

	sp_bits = small_page_bits(poolsize);
	lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;

	num_buckets = max_bucket(lp_bits);

	header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);

	/* First, set all bits taken by header. */
	for (i = 0; i < header_size; i += (1UL << sp_bits))
		set_bit(pages, i >> sp_bits);

	/* Check small page free list. */
	prev = 0;
	for (i = head->small_free_list; i; i = ph->next) {
		/* Bad pointer? */
		if (out_of_bounds(i, sp_bits, 1UL << sp_bits, poolsize))
			return check_fail();
		/* Large page? */
		if (test_bit(head->pagesize, i >> BITS_FROM_SMALL_TO_LARGE_PAGE))
			return check_fail();
		ph = from_pgnum(head, i, sp_bits);
		/* Linked list corrupt? */
		if (ph->prev != prev)
			return check_fail();
		/* Already seen this page? */
		if (test_bit(pages, i))
			return check_fail();
		set_bit(pages, i);
		prev = i;
	}

	/* Check large page free list. */
	prev = 0;
	for (i = head->large_free_list; i; i = ph->next) {
		/* Bad pointer? */
		if (out_of_bounds(i, sp_bits, 1UL << lp_bits, poolsize))
			return check_fail();
		/* Not large page? */
		if (!test_bit(head->pagesize, i >> BITS_FROM_SMALL_TO_LARGE_PAGE))
			return check_fail();
		/* Not page boundary? */
		if ((i % SMALL_PAGES_PER_LARGE_PAGE) != 0)
			return check_fail();
		ph = from_pgnum(head, i, sp_bits);
		/* Linked list corrupt? */
		if (ph->prev != prev)
			return check_fail();
		/* Already seen this page? */
		if (test_bit(pages, i))
			return check_fail();
		set_bit(pages, i);
		prev = i;
	}

	/* Check the buckets. */
	for (i = 0; i < max_bucket(lp_bits); i++) {
		struct bucket_state *bs = &head->bs[i];

		if (!check_bucket(head, poolsize, pages, bs, i))
			return false;
	}

	/* Check the huge alloc list. */
	prev = 0;
	for (i = head->huge; i; i = ha->next) {
		unsigned long pgbits, j;

		/* Bad pointer? */
		if (i >= poolsize || i + sizeof(*ha) > poolsize)
			return check_fail();
		ha = (void *)((char *)head + i);

		/* Check contents of ha. */
		if (ha->off > poolsize || ha->off + ha->len > poolsize)
			return check_fail();

		/* Large or small page? */
		pgbits = test_bit(head->pagesize, ha->off >> lp_bits)
			? lp_bits : sp_bits;

		/* Not page boundary? */
		if ((ha->off % (1UL << pgbits)) != 0)
			return check_fail();

		/* Not page length? */
		if ((ha->len % (1UL << pgbits)) != 0)
			return check_fail();

		/* Linked list corrupt? */
		if (ha->prev != prev)
			return check_fail();

		for (j = ha->off; j < ha->off + ha->len; j += (1UL<<sp_bits)) {
			/* Already seen this page? */
			if (test_bit(pages, j >> sp_bits))
				return check_fail();
			set_bit(pages, j >> sp_bits);
		}

		prev = i;
	}
		
	/* Make sure every page accounted for. */
	for (i = 0; i < poolsize >> sp_bits; i++) {
		if (!test_bit(pages, i))
			return check_fail();
		if (test_bit(head->pagesize,
			     i >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
			/* Large page, skip rest. */
			i += SMALL_PAGES_PER_LARGE_PAGE - 1;
		}
	}

	return true;
}

static unsigned long print_overhead(FILE *out, const char *desc,
				    unsigned long bytes,
				    unsigned long poolsize)
{
	fprintf(out, "Overhead (%s): %lu bytes (%.3g%%)\n",
		desc, bytes, 100.0 * bytes / poolsize);
	return bytes;
}

static unsigned long count_list(struct header *head,
				u16 pgnum,
				unsigned int sp_bits,
				unsigned long *total_elems)
{
	struct page_header *p;
	unsigned long ret = 0;

	while (pgnum) {
		p = from_pgnum(head, pgnum, sp_bits);
		if (total_elems)
			(*total_elems) += p->elements_used;
		ret++;
		pgnum = p->next;
	}
	return ret;
}

static unsigned long visualize_bucket(FILE *out, struct header *head,
				      unsigned int bucket,
				      unsigned long poolsize,
				      unsigned int sp_bits)
{
	unsigned long num_full, num_partial, num_pages, page_size,
		elems, hdr_min, hdr_size, elems_per_page, overhead = 0;

	elems_per_page = head->bs[bucket].elements_per_page;

	/* If we used byte-based bitmaps, we could get pg hdr to: */
	hdr_min = sizeof(struct page_header)
		- sizeof(((struct page_header *)0)->used)
		+ align_up(elems_per_page, CHAR_BIT) / CHAR_BIT;
	hdr_size = page_header_size(bucket / INTER_BUCKET_SPACE,
				    elems_per_page);

	elems = 0;
	num_full = count_list(head, head->bs[bucket].full_list, sp_bits,
			      &elems);
	num_partial = count_list(head, head->bs[bucket].page_list, sp_bits,
				 &elems);
	num_pages = num_full + num_partial;
	if (!num_pages)
		return 0;

	fprintf(out, "Bucket %u (%lu bytes):"
		" %lu full, %lu partial = %lu elements\n",
		bucket, bucket_to_size(bucket), num_full, num_partial, elems);
	/* Strict requirement of page header size. */
	overhead += print_overhead(out, "page headers",
				   hdr_min * num_pages, poolsize);
	/* Gap between minimal page header and actual start. */
	overhead += print_overhead(out, "page post-header alignments",
				   (hdr_size - hdr_min) * num_pages, poolsize);
	/* Between last element and end of page. */
	page_size = (1UL << sp_bits);
	if (large_page_bucket(bucket, sp_bits))
		page_size <<= BITS_FROM_SMALL_TO_LARGE_PAGE;

	overhead += print_overhead(out, "page tails",
				   (page_size - (hdr_size
						 + (elems_per_page
						    * bucket_to_size(bucket))))
				   * num_pages, poolsize);
	return overhead;
}

void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
{
	struct header *head = pool;
	unsigned long i, lp_bits, sp_bits, header_size, num_buckets, count,
		overhead = 0;

	fprintf(out, "Pool %p size %lu: (%s allocator)\n", pool, poolsize,
		poolsize < MIN_USEFUL_SIZE ? "tiny" : "standard");

	if (poolsize < MIN_USEFUL_SIZE) {
		tiny_alloc_visualize(out, pool, poolsize);
		return;
	}
	
	sp_bits = small_page_bits(poolsize);
	lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;

	num_buckets = max_bucket(lp_bits);
	header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);

	fprintf(out, "Large page size %lu, small page size %lu.\n",
		1UL << lp_bits, 1UL << sp_bits);
	overhead += print_overhead(out, "unused pool tail",
				   poolsize % (1UL << lp_bits), poolsize);
	fprintf(out, "Main header %lu bytes (%lu small pages).\n",
		header_size, align_up(header_size, 1UL << sp_bits) >> sp_bits);
	overhead += print_overhead(out, "partial header page",
				   align_up(header_size, 1UL << sp_bits)
				   - header_size, poolsize);
	/* Total large pages. */
	i = count_bits(head->pagesize, poolsize >> lp_bits);
	/* Used pages. */
	count = i - count_list(head, head->large_free_list, sp_bits, NULL);
	fprintf(out, "%lu/%lu large pages used (%.3g%%)\n",
		count, i, count ? 100.0 * count / i : 0.0);

	/* Total small pages. */
	i = ((poolsize >> lp_bits) - i) << BITS_FROM_SMALL_TO_LARGE_PAGE;
	/* Used pages */
	count = i - count_list(head, head->small_free_list, sp_bits, NULL);
	fprintf(out, "%lu/%lu small pages used (%.3g%%)\n",
		count, i, count ? 100.0 * count / i : 0.0);

	/* Summary of each bucket. */
	fprintf(out, "%lu buckets:\n", num_buckets);
	for (i = 0; i < num_buckets; i++)
		overhead += visualize_bucket(out, head, i, poolsize, sp_bits);

	print_overhead(out, "total", overhead, poolsize);
}