8 #include <ccan/build_assert/build_assert.h>
9 #include <ccan/likely/likely.h>
10 #include <ccan/short_types/short_types.h>
14 Inspired by (and parts taken from) Andrew Tridgell's alloc_mmap:
15 http://samba.org/~tridge/junkcode/alloc_mmap/
17 Copyright (C) Andrew Tridgell 2007
19 This library is free software; you can redistribute it and/or
20 modify it under the terms of the GNU Lesser General Public
21 License as published by the Free Software Foundation; either
22 version 2 of the License, or (at your option) any later version.
24 This library is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 Lesser General Public License for more details.
29 You should have received a copy of the GNU Lesser General Public
30 License along with this library; if not, write to the Free Software
31 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
34 #if 0 /* Until we have the tiny allocator working, go down to 1 MB */
36 /* We divide the pool into this many large pages (nearest power of 2) */
37 #define MAX_PAGES (1024UL)
39 /* 32 small pages == 1 large page. */
40 #define BITS_FROM_SMALL_TO_LARGE_PAGE 5
44 #define MAX_PAGES (128UL)
45 #define BITS_FROM_SMALL_TO_LARGE_PAGE 4
49 /* Smallest pool size for this scheme: 512-byte small pages. That's
50 * 4/8% overhead for 32/64 bit. */
51 #define MIN_USEFUL_SIZE (MAX_PAGES << (9 + BITS_FROM_SMALL_TO_LARGE_PAGE))
53 /* Every 4 buckets, we jump up a power of 2. ...8 10 12 14 16 20 24 28 32... */
54 #define INTER_BUCKET_SPACE 4
56 /* FIXME: Figure this out properly. */
57 #define MAX_SIZE (1 << 30)
59 /* How few object to fit in a page before using a larger one? (8) */
60 #define MAX_PAGE_OBJECT_ORDER 3
62 #define BITS_PER_LONG (sizeof(long) * CHAR_BIT)
65 unsigned long elements_per_page;
66 unsigned long page_list;
67 unsigned long full_list;
71 /* 1024 bit bitmap of which pages are large. */
72 unsigned long pagesize[MAX_PAGES / BITS_PER_LONG];
74 /* List of unused small/large pages. */
75 unsigned long small_free_list;
76 unsigned long large_free_list;
78 /* This is less defined: we have two buckets for each power of 2 */
79 struct bucket_state bs[1];
83 unsigned long next, prev;
85 /* FIXME: Pack this in somewhere... */
87 unsigned long used[1]; /* One bit per element. */
90 /* 2 bit for every byte to allocate. */
91 static void tiny_alloc_init(void *pool, unsigned long poolsize)
96 static void *tiny_alloc_get(void *pool, unsigned long poolsize,
97 unsigned long size, unsigned long align)
103 static void tiny_alloc_free(void *pool, unsigned long poolsize, void *free)
108 static unsigned long tiny_alloc_size(void *pool, unsigned long poolsize,
115 static bool tiny_alloc_check(void *pool, unsigned long poolsize)
121 static unsigned int fls(unsigned long val)
123 #if HAVE_BUILTIN_CLZL
124 /* This is significantly faster! */
125 return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0;
131 if (!(val & 0xffff0000u)) {
135 if (!(val & 0xff000000u)) {
139 if (!(val & 0xf0000000u)) {
143 if (!(val & 0xc0000000u)) {
147 if (!(val & 0x80000000u)) {
155 /* FIXME: Move to bitops. */
156 static unsigned int ffsl(unsigned long val)
158 #if HAVE_BUILTIN_FFSL
159 /* This is significantly faster! */
160 return __builtin_ffsl(val);
166 if (sizeof(long) == sizeof(u64)) {
167 if (!(val & 0xffffffff)) {
168 /* Workaround gcc warning on 32-bit:
169 error: right shift count >= width of type */
176 if (!(val & 0xffff)) {
200 static unsigned int popcount(unsigned long val)
202 #if HAVE_BUILTIN_POPCOUNTL
203 return __builtin_popcountl(val);
205 if (sizeof(long) == sizeof(u64)) {
207 v = (v & 0x5555555555555555ULL)
208 + ((v >> 1) & 0x5555555555555555ULL);
209 v = (v & 0x3333333333333333ULL)
210 + ((v >> 1) & 0x3333333333333333ULL);
211 v = (v & 0x0F0F0F0F0F0F0F0FULL)
212 + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
213 v = (v & 0x00FF00FF00FF00FFULL)
214 + ((v >> 1) & 0x00FF00FF00FF00FFULL);
215 v = (v & 0x0000FFFF0000FFFFULL)
216 + ((v >> 1) & 0x0000FFFF0000FFFFULL);
217 v = (v & 0x00000000FFFFFFFFULL)
218 + ((v >> 1) & 0x00000000FFFFFFFFULL);
221 val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
222 val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
223 val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
224 val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
225 val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
231 * Every 4 buckets, the size doubles.
232 * Between buckets, sizes increase linearly.
234 * eg. bucket 40 = 2^10 = 1024
235 * bucket 41 = 2^10 + 2^10*4 = 1024 + 256
236 * bucket 42 = 2^10 + 2^10*4 = 1024 + 512
237 * bucket 43 = 2^10 + 2^10*4 = 1024 + 768
238 * bucket 45 = 2^11 = 2048
240 * Care is taken to handle low numbered buckets, at cost of overflow.
242 static unsigned long bucket_to_size(unsigned int bucket)
244 unsigned long base = 1 << (bucket / INTER_BUCKET_SPACE);
245 return base + ((bucket % INTER_BUCKET_SPACE)
246 << (bucket / INTER_BUCKET_SPACE))
247 / INTER_BUCKET_SPACE;
252 * fls(size/2) == 3. 1 << 3 == 8, so we're 2 too large, out of a possible
253 * 8 too large. That's 1/4 of the way to the next power of 2 == 1 bucket.
255 * We make sure we round up. Note that this fails on 32 bit at size
256 * 1879048193 (around bucket 120).
258 static unsigned int size_to_bucket(unsigned long size)
260 unsigned int base = fls(size/2);
261 unsigned long overshoot;
263 overshoot = size - (1 << base);
264 return base * INTER_BUCKET_SPACE
265 + ((overshoot * INTER_BUCKET_SPACE + (1 << base)-1) >> base);
268 static unsigned int large_page_bits(unsigned long poolsize)
270 return fls(poolsize / MAX_PAGES / 2);
273 static unsigned long align_up(unsigned long x, unsigned long align)
275 return (x + align - 1) & ~(align - 1);
278 static void *from_off(struct header *head, unsigned long off)
280 return (char *)head + off;
283 static unsigned long to_off(struct header *head, void *p)
285 return (char *)p - (char *)head;
288 static size_t used_size(unsigned int num_elements)
290 return (num_elements + BITS_PER_LONG-1) / BITS_PER_LONG;
294 * We always align the first entry to the lower power of 2.
295 * eg. the 12-byte bucket gets 8-byte aligned. The 4096-byte bucket
296 * gets 4096-byte aligned.
298 static unsigned long page_header_size(unsigned int align_bits,
299 unsigned long num_elements)
303 size = sizeof(struct page_header)
304 - sizeof(((struct page_header *)0)->used)
305 + used_size(num_elements);
306 return align_up(size, 1 << align_bits);
309 static void add_to_list(struct header *head,
310 unsigned long *list, struct page_header *ph)
312 unsigned long h = *list, offset = to_off(head, ph);
316 struct page_header *prev = from_off(head, h);
317 assert(prev->prev == 0);
324 static void del_from_list(struct header *head,
325 unsigned long *list, struct page_header *ph)
331 struct page_header *prev = from_off(head, ph->prev);
332 prev->next = ph->next;
335 struct page_header *next = from_off(head, ph->next);
336 next->prev = ph->prev;
340 static unsigned long pop_from_list(struct header *head,
343 unsigned long h = *list;
344 struct page_header *ph = from_off(head, h);
349 struct page_header *next = from_off(head, *list);
356 static void add_small_page_to_freelist(struct header *head,
357 struct page_header *ph)
359 add_to_list(head, &head->small_free_list, ph);
362 static void add_large_page_to_freelist(struct header *head,
363 struct page_header *ph)
365 add_to_list(head, &head->large_free_list, ph);
368 static void add_to_bucket_list(struct header *head,
369 struct bucket_state *bs,
370 struct page_header *ph)
372 add_to_list(head, &bs->page_list, ph);
375 static void del_from_bucket_list(struct header *head,
376 struct bucket_state *bs,
377 struct page_header *ph)
379 del_from_list(head, &bs->page_list, ph);
382 static void del_from_bucket_full_list(struct header *head,
383 struct bucket_state *bs,
384 struct page_header *ph)
386 del_from_list(head, &bs->full_list, ph);
389 static void add_to_bucket_full_list(struct header *head,
390 struct bucket_state *bs,
391 struct page_header *ph)
393 add_to_list(head, &bs->full_list, ph);
396 static void clear_bit(unsigned long bitmap[], unsigned int off)
398 bitmap[off / BITS_PER_LONG] &= ~(1 << (off % BITS_PER_LONG));
401 static bool test_bit(const unsigned long bitmap[], unsigned int off)
403 return bitmap[off / BITS_PER_LONG] & (1 << (off % BITS_PER_LONG));
406 static void set_bit(unsigned long bitmap[], unsigned int off)
408 bitmap[off / BITS_PER_LONG] |= (1 << (off % BITS_PER_LONG));
411 /* There must be a bit to be found. */
412 static unsigned int find_free_bit(const unsigned long bitmap[])
416 for (i = 0; bitmap[i] == -1UL; i++);
417 return (i*BITS_PER_LONG) + ffsl(~bitmap[i]) - 1;
420 /* How many elements can we fit in a page? */
421 static unsigned long elements_per_page(unsigned long align_bits,
425 unsigned long num, overhead;
427 /* First approximation: no extra room for bitmap. */
428 overhead = align_up(sizeof(struct page_header), 1 << align_bits);
429 num = (psize - overhead) / esize;
431 while (page_header_size(align_bits, num) + esize * num > psize)
436 static bool large_page_bucket(unsigned int bucket, unsigned long poolsize)
438 unsigned int sp_bits;
439 unsigned long max_smallsize;
441 sp_bits = large_page_bits(poolsize) - BITS_FROM_SMALL_TO_LARGE_PAGE;
442 /* Note: this doesn't take into account page header. */
443 max_smallsize = (1UL << sp_bits) >> MAX_PAGE_OBJECT_ORDER;
445 return bucket_to_size(bucket) > max_smallsize;
448 static unsigned int max_bucket(unsigned int lp_bits)
450 return (lp_bits - MAX_PAGE_OBJECT_ORDER) * INTER_BUCKET_SPACE;
453 void alloc_init(void *pool, unsigned long poolsize)
455 struct header *head = pool;
456 struct page_header *ph;
457 unsigned int lp_bits, sp_bits, num_buckets;
458 unsigned long header_size, i;
460 if (poolsize < MIN_USEFUL_SIZE) {
461 tiny_alloc_init(pool, poolsize);
465 lp_bits = large_page_bits(poolsize);
466 sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
468 num_buckets = max_bucket(lp_bits);
471 header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);
473 memset(head, 0, header_size);
474 for (i = 0; i < num_buckets; i++) {
475 unsigned long pagesize;
477 if (large_page_bucket(i, poolsize))
478 pagesize = 1UL << lp_bits;
480 pagesize = 1UL << sp_bits;
482 head->bs[i].elements_per_page
483 = elements_per_page(i / INTER_BUCKET_SPACE,
488 /* They start as all large pages. */
489 memset(head->pagesize, 0xFF, sizeof(head->pagesize));
490 /* FIXME: small pages for last bit? */
492 /* Split first page into small pages. */
493 assert(header_size << (1UL << lp_bits));
494 clear_bit(head->pagesize, 0);
496 /* Skip over page(s) used by header, add rest to free list */
497 for (i = align_up(header_size, (1 << sp_bits)) >> sp_bits;
498 i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE);
500 ph = from_off(head, i<<sp_bits);
501 ph->elements_used = 0;
502 add_small_page_to_freelist(head, ph);
505 /* Add the rest of the pages as large pages. */
507 while (i + (1 << lp_bits) <= poolsize) {
508 ph = from_off(head, i);
509 ph->elements_used = 0;
510 add_large_page_to_freelist(head, ph);
515 /* A large page worth of small pages are free: delete them from free list. */
516 static void del_large_from_small_free_list(struct header *head,
517 struct page_header *ph,
518 unsigned int sp_bits)
522 for (i = 0; i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE); i++) {
523 del_from_list(head, &head->small_free_list,
524 (void *)ph + (i << sp_bits));
528 static bool all_empty(struct header *head, unsigned long off, unsigned sp_bits)
532 for (i = 0; i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE); i++) {
533 struct page_header *ph = from_off(head, off + (i << sp_bits));
534 if (ph->elements_used)
540 static unsigned long get_large_page(struct header *head,
541 unsigned long poolsize)
543 unsigned long lp_bits, sp_bits, i, page;
545 page = pop_from_list(head, &head->large_free_list);
549 /* Look for small pages to coalesce, after first large page. */
550 lp_bits = large_page_bits(poolsize);
551 sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
553 for (i = (1 << lp_bits); i < poolsize; i += (1 << lp_bits)) {
554 /* Already a large page? */
555 if (test_bit(head->pagesize, i >> lp_bits))
557 if (all_empty(head, i, sp_bits)) {
558 struct page_header *ph = from_off(head, i);
559 set_bit(head->pagesize, i >> lp_bits);
560 del_large_from_small_free_list(head, ph, sp_bits);
561 add_large_page_to_freelist(head, ph);
565 return pop_from_list(head, &head->large_free_list);
568 /* Returns small page. */
569 static unsigned long break_up_large_page(struct header *head,
573 unsigned long lp_bits, sp_bits, i;
575 lp_bits = large_page_bits(psize);
576 sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
577 clear_bit(head->pagesize, lpage >> lp_bits);
579 for (i = 1; i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE); i++)
580 add_small_page_to_freelist(head,
582 lpage + (i<<sp_bits)));
587 static unsigned long get_small_page(struct header *head,
588 unsigned long poolsize)
592 ret = pop_from_list(head, &head->small_free_list);
595 ret = get_large_page(head, poolsize);
597 ret = break_up_large_page(head, poolsize, ret);
601 void *alloc_get(void *pool, unsigned long poolsize,
602 unsigned long size, unsigned long align)
604 struct header *head = pool;
607 struct bucket_state *bs;
608 struct page_header *ph;
610 if (poolsize < MIN_USEFUL_SIZE) {
611 return tiny_alloc_get(pool, poolsize, size, align);
614 size = align_up(size, align);
617 bucket = size_to_bucket(size);
619 if (bucket >= max_bucket(large_page_bits(poolsize))) {
620 /* FIXME: huge alloc. */
624 bs = &head->bs[bucket];
626 if (!bs->page_list) {
627 struct page_header *ph;
629 if (large_page_bucket(bucket, poolsize))
630 bs->page_list = get_large_page(head, poolsize);
632 bs->page_list = get_small_page(head, poolsize);
633 /* FIXME: Try large-aligned alloc? Header stuffing? */
634 if (unlikely(!bs->page_list))
636 ph = from_off(head, bs->page_list);
638 ph->elements_used = 0;
640 memset(ph->used, 0, used_size(bs->elements_per_page));
643 ph = from_off(head, bs->page_list);
645 i = find_free_bit(ph->used);
646 set_bit(ph->used, i);
649 /* check if this page is now full */
650 if (unlikely(ph->elements_used == bs->elements_per_page)) {
651 del_from_bucket_list(head, bs, ph);
652 add_to_bucket_full_list(head, bs, ph);
655 return (char *)ph + page_header_size(ph->bucket / INTER_BUCKET_SPACE,
656 bs->elements_per_page)
657 + i * bucket_to_size(bucket);
660 void alloc_free(void *pool, unsigned long poolsize, void *free)
662 struct header *head = pool;
663 struct bucket_state *bs;
664 unsigned int pagebits;
665 unsigned long i, pgoffset, offset = (char *)free - (char *)pool;
667 struct page_header *ph;
669 if (poolsize < MIN_USEFUL_SIZE) {
670 return tiny_alloc_free(pool, poolsize, free);
673 /* Get page header. */
674 pagebits = large_page_bits(poolsize);
675 if (!test_bit(head->pagesize, offset >> pagebits)) {
677 pagebits -= BITS_FROM_SMALL_TO_LARGE_PAGE;
681 /* Step back to page header. */
682 ph = from_off(head, offset & ~((1UL << pagebits) - 1));
683 bs = &head->bs[ph->bucket];
684 pgoffset = (offset & ((1UL << pagebits) - 1))
685 - page_header_size(ph->bucket / INTER_BUCKET_SPACE,
686 bs->elements_per_page);
688 if (unlikely(ph->elements_used == bs->elements_per_page)) {
689 del_from_bucket_full_list(head, bs, ph);
690 add_to_bucket_list(head, bs, ph);
693 /* Which element are we? */
694 i = pgoffset / bucket_to_size(ph->bucket);
695 clear_bit(ph->used, i);
698 if (unlikely(ph->elements_used == 0)) {
699 bs = &head->bs[ph->bucket];
700 del_from_bucket_list(head, bs, ph);
702 add_small_page_to_freelist(head, ph);
704 add_large_page_to_freelist(head, ph);
708 unsigned long alloc_size(void *pool, unsigned long poolsize, void *p)
710 struct header *head = pool;
711 unsigned int pagebits;
712 unsigned long offset = (char *)p - (char *)pool;
713 struct page_header *ph;
715 if (poolsize < MIN_USEFUL_SIZE)
716 return tiny_alloc_size(pool, poolsize, p);
718 /* Get page header. */
719 pagebits = large_page_bits(poolsize);
720 if (!test_bit(head->pagesize, offset >> pagebits))
721 pagebits -= BITS_FROM_SMALL_TO_LARGE_PAGE;
723 /* Step back to page header. */
724 ph = from_off(head, offset & ~((1UL << pagebits) - 1));
725 return bucket_to_size(ph->bucket);
728 /* Useful for gdb breakpoints. */
729 static bool check_fail(void)
734 static unsigned long count_bits(const unsigned long bitmap[],
737 unsigned long i, count = 0;
739 while (limit >= BITS_PER_LONG) {
740 count += popcount(bitmap[0]);
742 limit -= BITS_PER_LONG;
745 for (i = 0; i < limit; i++)
746 if (test_bit(bitmap, i))
751 static bool out_of_bounds(unsigned long off,
752 unsigned long pagesize,
753 unsigned long poolsize)
755 return (off > poolsize || off + pagesize > poolsize);
758 static bool check_bucket(struct header *head,
759 unsigned long poolsize,
760 unsigned long pages[],
761 struct bucket_state *bs,
764 bool lp_bucket = large_page_bucket(bindex, poolsize);
765 struct page_header *ph;
766 unsigned long taken, i, prev, pagesize, sp_bits, lp_bits;
768 lp_bits = large_page_bits(poolsize);
769 sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
771 pagesize = 1UL << (lp_bucket ? lp_bits : sp_bits);
773 /* This many elements fit? */
774 taken = page_header_size(bindex / INTER_BUCKET_SPACE,
775 bs->elements_per_page);
776 taken += bucket_to_size(bindex) * bs->elements_per_page;
777 if (taken > pagesize)
780 /* One more wouldn't fit? */
781 taken = page_header_size(bindex / INTER_BUCKET_SPACE,
782 bs->elements_per_page + 1);
783 taken += bucket_to_size(bindex) * (bs->elements_per_page + 1);
784 if (taken <= pagesize)
787 /* Walk used list. */
789 for (i = bs->page_list; i; i = ph->next) {
791 if (out_of_bounds(i, pagesize, poolsize))
793 /* Wrong size page? */
794 if (!!test_bit(head->pagesize, i >> lp_bits) != lp_bucket)
796 /* Not page boundary? */
799 ph = from_off(head, i);
800 /* Linked list corrupt? */
801 if (ph->prev != prev)
803 /* Already seen this page? */
804 if (test_bit(pages, i >> sp_bits))
806 set_bit(pages, i >> sp_bits);
808 if (ph->elements_used == 0)
810 if (ph->elements_used >= bs->elements_per_page)
812 /* Used bits don't agree? */
813 if (ph->elements_used != count_bits(ph->used,
814 bs->elements_per_page))
817 if (ph->bucket != bindex)
822 /* Walk full list. */
824 for (i = bs->full_list; i; i = ph->next) {
826 if (out_of_bounds(i, pagesize, poolsize))
828 /* Wrong size page? */
829 if (!!test_bit(head->pagesize, i >> lp_bits) != lp_bucket)
831 /* Not page boundary? */
834 ph = from_off(head, i);
835 /* Linked list corrupt? */
836 if (ph->prev != prev)
838 /* Already seen this page? */
839 if (test_bit(pages, i >> sp_bits))
841 set_bit(pages, i >> sp_bits);
843 if (ph->elements_used != bs->elements_per_page)
845 /* Used bits don't agree? */
846 if (ph->elements_used != count_bits(ph->used,
847 bs->elements_per_page))
850 if (ph->bucket != bindex)
857 bool alloc_check(void *pool, unsigned long poolsize)
859 struct header *head = pool;
860 unsigned long prev, i, lp_bits, sp_bits, header_size, num_buckets;
861 struct page_header *ph;
862 unsigned long pages[(MAX_PAGES << BITS_FROM_SMALL_TO_LARGE_PAGE)
863 / BITS_PER_LONG] = { 0 };
865 if (poolsize < MIN_USEFUL_SIZE)
866 return tiny_alloc_check(pool, poolsize);
868 lp_bits = large_page_bits(poolsize);
869 sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
871 num_buckets = max_bucket(lp_bits);
873 header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);
875 /* First, set all bits taken by header. */
876 for (i = 0; i < header_size; i += (1UL << sp_bits))
877 set_bit(pages, i >> sp_bits);
879 /* Check small page free list. */
881 for (i = head->small_free_list; i; i = ph->next) {
883 if (out_of_bounds(i, 1 << sp_bits, poolsize))
886 if (test_bit(head->pagesize, i >> lp_bits))
888 /* Not page boundary? */
889 if (i % (1 << sp_bits))
891 ph = from_off(head, i);
892 /* Linked list corrupt? */
893 if (ph->prev != prev)
895 /* Already seen this page? */
896 if (test_bit(pages, i >> sp_bits))
898 set_bit(pages, i >> sp_bits);
902 /* Check large page free list. */
904 for (i = head->large_free_list; i; i = ph->next) {
906 if (out_of_bounds(i, 1 << lp_bits, poolsize))
908 /* Not large page? */
909 if (!test_bit(head->pagesize, i >> lp_bits))
911 /* Not page boundary? */
912 if (i % (1 << lp_bits))
914 ph = from_off(head, i);
915 /* Linked list corrupt? */
916 if (ph->prev != prev)
918 /* Already seen this page? */
919 if (test_bit(pages, i >> sp_bits))
921 set_bit(pages, i >> sp_bits);
925 /* Check the buckets. */
926 for (i = 0; i < max_bucket(lp_bits); i++) {
927 struct bucket_state *bs = &head->bs[i];
929 if (!check_bucket(head, poolsize, pages, bs, i))
933 /* Make sure every page accounted for. */
934 for (i = 0; i < poolsize >> sp_bits; i++) {
935 if (!test_bit(pages, i))
937 if (test_bit(head->pagesize,
938 i >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
939 /* Large page, skip rest. */
940 i += (1 << BITS_FROM_SMALL_TO_LARGE_PAGE) - 1;