X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Falloc%2Falloc.c;h=8e0b72aa0432227990f7b053f6620020fd53dcac;hp=3f1cc75008c907e843c2b0d69f06cded79021b02;hb=3d9899b97bff2a3ec5abe57f06c2a9355a18e6b5;hpb=99d6764c1ea1e763b6c9d09038fba7fa8ec61d16 diff --git a/ccan/alloc/alloc.c b/ccan/alloc/alloc.c index 3f1cc750..8e0b72aa 100644 --- a/ccan/alloc/alloc.c +++ b/ccan/alloc/alloc.c @@ -5,8 +5,11 @@ #include #include #include "alloc.h" +#include "bitops.h" +#include "tiny.h" #include #include +#include #include #include "config.h" @@ -31,24 +34,17 @@ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ -#if 0 /* Until we have the tiny allocator working, go down to 1 MB */ - /* We divide the pool into this many large pages (nearest power of 2) */ -#define MAX_PAGES (1024UL) +#define MAX_LARGE_PAGES (256UL) /* 32 small pages == 1 large page. */ #define BITS_FROM_SMALL_TO_LARGE_PAGE 5 -#else - -#define MAX_PAGES (128UL) -#define BITS_FROM_SMALL_TO_LARGE_PAGE 4 - -#endif +#define MAX_SMALL_PAGES (MAX_LARGE_PAGES << BITS_FROM_SMALL_TO_LARGE_PAGE) -/* Smallest pool size for this scheme: 512-byte small pages. That's - * 3/5% overhead for 32/64 bit. */ -#define MIN_USEFUL_SIZE (MAX_PAGES << (9 + 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 @@ -64,171 +60,39 @@ #define BITS_PER_LONG (sizeof(long) * CHAR_BIT) struct bucket_state { - unsigned long elements_per_page; + u32 elements_per_page; u16 page_list; u16 full_list; }; struct header { /* Bitmap of which pages are large. */ - unsigned long pagesize[MAX_PAGES / BITS_PER_LONG]; + 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; - u32 elements_used; - /* FIXME: Pack this in somewhere... */ - u8 bucket; + /* 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. */ }; -/* 2 bit for every byte to allocate. */ -static void tiny_alloc_init(void *pool, unsigned long poolsize) -{ -/* FIXME */ -} - -static void *tiny_alloc_get(void *pool, unsigned long poolsize, - unsigned long size, unsigned long align) -{ -/* FIXME */ - return NULL; -} - -static void tiny_alloc_free(void *pool, unsigned long poolsize, void *free) -{ -/* FIXME */ -} - -static unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, - void *p) -{ -/* FIXME */ - return 0; -} - -static bool tiny_alloc_check(void *pool, unsigned long poolsize) -{ -/* FIXME */ - return true; -} - -static unsigned int fls(unsigned long val) -{ -#if HAVE_BUILTIN_CLZL - /* This is significantly faster! */ - return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0; -#else - unsigned int r = 32; - - if (!val) - return 0; - if (!(val & 0xffff0000u)) { - val <<= 16; - r -= 16; - } - if (!(val & 0xff000000u)) { - val <<= 8; - r -= 8; - } - if (!(val & 0xf0000000u)) { - val <<= 4; - r -= 4; - } - if (!(val & 0xc0000000u)) { - val <<= 2; - r -= 2; - } - if (!(val & 0x80000000u)) { - val <<= 1; - r -= 1; - } - return r; -#endif -} - -/* FIXME: Move to bitops. */ -static unsigned int ffsl(unsigned long val) -{ -#if HAVE_BUILTIN_FFSL - /* This is significantly faster! */ - return __builtin_ffsl(val); -#else - unsigned int r = 1; - - if (!val) - return 0; - if (sizeof(long) == sizeof(u64)) { - if (!(val & 0xffffffff)) { - /* Workaround gcc warning on 32-bit: - error: right shift count >= width of type */ - u64 tmp = val; - tmp >>= 32; - val = tmp; - r += 32; - } - } - if (!(val & 0xffff)) { - val >>= 16; - r += 16; - } - if (!(val & 0xff)) { - val >>= 8; - r += 8; - } - if (!(val & 0xf)) { - val >>= 4; - r += 4; - } - if (!(val & 3)) { - val >>= 2; - r += 2; - } - if (!(val & 1)) { - val >>= 1; - r += 1; - } - return r; -#endif -} - -static unsigned int popcount(unsigned long val) -{ -#if HAVE_BUILTIN_POPCOUNTL - return __builtin_popcountl(val); -#else - if (sizeof(long) == sizeof(u64)) { - u64 v = val; - v = (v & 0x5555555555555555ULL) - + ((v >> 1) & 0x5555555555555555ULL); - v = (v & 0x3333333333333333ULL) - + ((v >> 1) & 0x3333333333333333ULL); - v = (v & 0x0F0F0F0F0F0F0F0FULL) - + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL); - v = (v & 0x00FF00FF00FF00FFULL) - + ((v >> 1) & 0x00FF00FF00FF00FFULL); - v = (v & 0x0000FFFF0000FFFFULL) - + ((v >> 1) & 0x0000FFFF0000FFFFULL); - v = (v & 0x00000000FFFFFFFFULL) - + ((v >> 1) & 0x00000000FFFFFFFFULL); - return v; - } - val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL); - val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL); - val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL); - val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL); - val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL); - return val; -#endif -} - /* * Every 4 buckets, the size doubles. * Between buckets, sizes increase linearly. @@ -267,14 +131,9 @@ static unsigned int size_to_bucket(unsigned long size) + ((overshoot * INTER_BUCKET_SPACE + (1 << base)-1) >> base); } -static unsigned int large_page_bits(unsigned long poolsize) -{ - return fls(poolsize / MAX_PAGES / 2); -} - -static unsigned long align_up(unsigned long x, unsigned long align) +static unsigned int small_page_bits(unsigned long poolsize) { - return (x + align - 1) & ~(align - 1); + return fls(poolsize / MAX_SMALL_PAGES / 2); } static struct page_header *from_pgnum(struct header *head, @@ -356,6 +215,36 @@ static u16 pop_from_list(struct header *head, 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) @@ -470,10 +359,10 @@ void alloc_init(void *pool, unsigned long poolsize) } /* We rely on page numbers fitting in 16 bit. */ - BUILD_ASSERT((MAX_PAGES << BITS_FROM_SMALL_TO_LARGE_PAGE) < 65536); + BUILD_ASSERT(MAX_SMALL_PAGES < 65536); - lp_bits = large_page_bits(poolsize); - sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE; + sp_bits = small_page_bits(poolsize); + lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE; num_buckets = max_bucket(lp_bits); @@ -500,7 +389,7 @@ void alloc_init(void *pool, unsigned long poolsize) /* FIXME: small pages for last bit? */ /* Split first page into small pages. */ - assert(header_size << (1UL << lp_bits)); + assert(header_size < (1UL << lp_bits)); clear_bit(head->pagesize, 0); /* Skip over page(s) used by header, add rest to free list */ @@ -550,16 +439,11 @@ static bool all_empty(struct header *head, return true; } -static u16 get_large_page(struct header *head, unsigned long poolsize, - unsigned int sp_bits) +static void recombine_small_pages(struct header *head, unsigned long poolsize, + unsigned int sp_bits) { - unsigned int lp_bits, i, page; - - lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE; - - page = pop_from_list(head, &head->large_free_list, sp_bits); - if (likely(page)) - return page; + 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; @@ -576,7 +460,21 @@ static u16 get_large_page(struct header *head, unsigned long poolsize, 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 lp_bits, page; + + lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_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); } @@ -611,6 +509,189 @@ static u16 get_small_page(struct header *head, unsigned long poolsize, 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 void *unlikely_func 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 + (1 << 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 += (1 << 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 + (1 << 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 void unlikely_func 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 += 1 << 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 += 1 << 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 unsigned long unlikely_func 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) { @@ -630,13 +711,13 @@ void *alloc_get(void *pool, unsigned long poolsize, size = 1; bucket = size_to_bucket(size); - if (bucket >= max_bucket(large_page_bits(poolsize))) { - /* FIXME: huge alloc. */ - return NULL; + 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]; - sp_bits = large_page_bits(poolsize) - BITS_FROM_SMALL_TO_LARGE_PAGE; if (!bs->page_list) { struct page_header *ph; @@ -688,7 +769,7 @@ void alloc_free(void *pool, unsigned long poolsize, void *free) } /* Get page header. */ - sp_bits = large_page_bits(poolsize) - BITS_FROM_SMALL_TO_LARGE_PAGE; + sp_bits = small_page_bits(poolsize); pgnum = offset >> sp_bits; /* Big page? Round down further. */ @@ -700,6 +781,11 @@ void alloc_free(void *pool, unsigned long poolsize, void *free) /* 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, @@ -736,7 +822,7 @@ unsigned long alloc_size(void *pool, unsigned long poolsize, void *p) return tiny_alloc_size(pool, poolsize, p); /* Get page header. */ - sp_bits = large_page_bits(poolsize) - BITS_FROM_SMALL_TO_LARGE_PAGE; + sp_bits = small_page_bits(poolsize); pgnum = offset >> sp_bits; /* Big page? Round down further. */ @@ -745,6 +831,9 @@ unsigned long alloc_size(void *pool, unsigned long poolsize, void *p) /* 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); } @@ -795,8 +884,8 @@ static bool check_bucket(struct header *head, struct page_header *ph; unsigned long taken, i, prev, pagesize, sp_bits, lp_bits; - lp_bits = large_page_bits(poolsize); - sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE; + sp_bits = small_page_bits(poolsize); + lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE; lp_bucket = large_page_bucket(bindex, sp_bits); @@ -892,14 +981,14 @@ 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; - unsigned long pages[(MAX_PAGES << BITS_FROM_SMALL_TO_LARGE_PAGE) - / BITS_PER_LONG] = { 0 }; + 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); - lp_bits = large_page_bits(poolsize); - sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE; + sp_bits = small_page_bits(poolsize); + lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE; num_buckets = max_bucket(lp_bits); @@ -960,6 +1049,46 @@ bool alloc_check(void *pool, unsigned long poolsize) 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 += (1 << 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)) @@ -1049,10 +1178,6 @@ static unsigned long visualize_bucket(FILE *out, struct header *head, return overhead; } -static void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize) -{ -} - void alloc_visualize(FILE *out, void *pool, unsigned long poolsize) { struct header *head = pool; @@ -1067,8 +1192,8 @@ void alloc_visualize(FILE *out, void *pool, unsigned long poolsize) return; } - lp_bits = large_page_bits(poolsize); - sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE; + 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); @@ -1090,7 +1215,7 @@ void alloc_visualize(FILE *out, void *pool, unsigned long poolsize) count, i, count ? 100.0 * count / i : 0.0); /* Total small pages. */ - i = (poolsize >> lp_bits) - i; + 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",