More cleanups where get_bit_pair should be used instead of
[ccan] / alloc / alloc.c
1 #include <unistd.h>
2 #include <stdint.h>
3 #include <string.h>
4 #include <limits.h>
5 #include <assert.h>
6 #include "alloc.h"
7 #include "build_assert/build_assert.h"
8 #include "config.h"
9
10 #if HAVE_ALIGNOF
11 #define ALIGNOF(t) __alignof__(t)
12 #else
13 /* Alignment by measuring structure padding. */
14 #define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
15 #endif
16
17 /* FIXME: Doesn't handle non-page-aligned poolsize. */
18
19 /* FIXME: Reduce. */
20 #define MIN_SIZE (getpagesize() * 2)
21
22 /* What's the granularity of sub-page allocs? */
23 #define BITMAP_GRANULARITY 4
24
25 /* File layout:
26  *
27  *  file := pagestates pad metadata
28  *  pagestates := pages * 2-bits-per-page
29  *  pad := pad to next ALIGNOF(metadata)
30  *
31  *  metadata := metalen next-ptr metabits
32  *  metabits := freeblock | bitblock
33  *  freeblock := 0+
34  *  bitblock := 2-bits-per-bit-in-page 1
35  */
36 struct metaheader
37 {
38         /* Length (after this header).  (FIXME: implied by page bits!). */
39         unsigned long metalen;
40         /* Next meta header, or 0 */
41         unsigned long next;
42         /* Bits start here. */
43 };
44
45 /* Assumes a is a power of two. */
46 static unsigned long align_up(unsigned long x, unsigned long a)
47 {
48         return (x + a - 1) & ~(a - 1);
49 }
50
51 static unsigned long div_up(unsigned long x, unsigned long a)
52 {
53         return (x + a - 1) / a;
54 }
55
56 /* It turns out that we spend a lot of time dealing with bit pairs.
57  * These routines manipulate them.
58  */
59 static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
60 {
61         return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
62 }
63
64 static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
65 {
66         bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
67         bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
68 }
69
70 /* This is used for page states and subpage allocations */
71 enum alloc_state
72 {
73         FREE,
74         TAKEN,
75         TAKEN_START,
76         SPECIAL,        /* Sub-page allocation for page states. */
77 };
78
79 /* The types for subpage metadata. */
80 enum sub_metadata_type
81 {
82         /* FREE is same as alloc state */
83         BITMAP = 1,
84 };
85
86 /* Page states are represented by bitpairs, at the start of the pool. */
87 #define BITS_PER_PAGE 2
88
89 static enum alloc_state get_page_state(const void *pool, unsigned long page)
90 {
91         return get_bit_pair(pool, page);
92 }
93
94 static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
95 {
96         set_bit_pair(pool, page, s);
97 }
98
99 /* The offset of metadata for a subpage allocation is found at the end
100  * of the subpage */
101 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
102
103 /* This is the length of metadata in bits.  It consists of two bits
104  * for every BITMAP_GRANULARITY of usable bytes in the page, then two
105  * bits for the tailer.. */
106 #define BITMAP_METABITLEN                                               \
107     ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
108
109 /* This is the length in bytes. */
110 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
111
112 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
113 {
114         unsigned int pagestatelen;
115
116         pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
117                                        CHAR_BIT),
118                                 ALIGNOF(struct metaheader));
119         return (struct metaheader *)((char *)pool + pagestatelen);
120 }
121
122 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
123 {
124         if (!mh->next)
125                 return NULL;
126
127         return (struct metaheader *)((char *)pool + mh->next);
128 }
129
130 static unsigned long pool_offset(void *pool, void *p)
131 {
132         return (char *)p - (char *)pool;
133 }
134
135 void alloc_init(void *pool, unsigned long poolsize)
136 {
137         /* FIXME: Alignment assumptions about pool. */
138         unsigned long len, i;
139         struct metaheader *mh;
140
141         if (poolsize < MIN_SIZE)
142                 return;
143
144         mh = first_mheader(pool, poolsize);
145
146         /* Mark all page states FREE, and all of metaheader bitmap which takes
147          * rest of first page. */
148         len = align_up(pool_offset(pool, mh + 1), getpagesize());
149         BUILD_ASSERT(FREE == 0);
150         memset(pool, 0, len);
151
152         /* Set up metalen */
153         mh->metalen = len - pool_offset(pool, mh + 1);
154
155         /* Mark the pagestate and metadata page(s) allocated. */
156         set_page_state(pool, 0, TAKEN_START);
157         for (i = 1; i < div_up(len, getpagesize()); i++)
158                 set_page_state(pool, i, TAKEN);
159 }
160
161 /* Two bits per element, representing page states.  Returns 0 on fail.
162  * off is used to allocate from subpage bitmaps, which use the first 2
163  * bits as the type, so the real bitmap is offset by 1. */
164 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
165                                        unsigned long elems,
166                                        unsigned long want, unsigned long align)
167 {
168         long i;
169         unsigned long free;
170
171         free = 0;
172         /* We allocate from far end, to increase ability to expand metadata. */
173         for (i = elems - 1; i >= 0; i--) {
174                 switch (get_bit_pair(bits, off+i)) {
175                 case FREE:
176                         if (++free >= want) {
177                                 unsigned long j;
178
179                                 /* They might ask for large alignment. */
180                                 if (align && i % align)
181                                         continue;
182
183                                 set_bit_pair(bits, off+i, TAKEN_START);
184                                 for (j = i+1; j < i + want; j++)
185                                         set_bit_pair(bits, off+j, TAKEN);
186                                 return off+i;
187                         }
188                         break;
189                 case SPECIAL:
190                 case TAKEN_START:
191                 case TAKEN:
192                         free = 0;
193                         break;
194                 }
195         }
196
197         return 0;
198 }
199
200 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
201                                      unsigned long pages, unsigned long align)
202 {
203         return alloc_from_bitmap(pool, 0, poolsize / getpagesize(), pages,
204                                  align / getpagesize());
205 }
206
207 /* Offset to metadata is at end of page. */
208 static unsigned long *metadata_off(void *pool, unsigned long page)
209 {
210         return (unsigned long *)
211                 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
212 }
213
214 static uint8_t *get_page_metadata(void *pool, unsigned long page)
215 {
216         return (uint8_t *)pool + *metadata_off(pool, page);
217 }
218
219 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
220 {
221         *metadata_off(pool, page) = meta - (uint8_t *)pool;
222 }
223
224 static unsigned long sub_page_alloc(void *pool, unsigned long page,
225                                     unsigned long size, unsigned long align)
226 {
227         uint8_t *bits = get_page_metadata(pool, page);
228         unsigned long i;
229
230         /* TAKEN at start means a bitwise alloc. */
231         assert(get_bit_pair(bits, 0) == BITMAP);
232
233         /* We use a standart bitmap, but offset because of that BITMAP
234          * header. */
235         i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
236                               div_up(size, BITMAP_GRANULARITY),
237                               align / BITMAP_GRANULARITY);
238
239         /* Can't allocate? */
240         if (i == 0)
241                 return 0;
242
243         /* i-1 because of the header. */
244         return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
245 }
246
247 static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes,
248                                 enum sub_metadata_type type)
249 {
250         uint8_t *meta = (uint8_t *)(mh + 1);
251         unsigned long free = 0, len;
252         unsigned long i;
253
254         /* TAKEN tags end a subpage alloc. */
255         for (i = 0; i < mh->metalen * CHAR_BIT / BITS_PER_PAGE; i += len) {
256                 switch (get_bit_pair(meta, i)) {
257                 case FREE:
258                         len = 1;
259                         free++;
260                         if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
261                                 /* Mark this as a bitmap. */
262                                 set_bit_pair(meta, i - free + 1, type);
263                                 return meta + (i - free + 1)
264                                         / (CHAR_BIT / BITS_PER_PAGE);
265                         }
266                         break;
267                 case BITMAP:
268                         /* Skip over this allocated part. */
269                         len = BITMAP_METALEN * CHAR_BIT / BITS_PER_PAGE;
270                         free = 0;
271                         break;
272                 default:
273                         assert(0);
274                         return NULL;
275                 }
276         }
277         return NULL;
278 }
279
280 /* We need this many bytes of metadata. */
281 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
282                              unsigned long bytes, enum sub_metadata_type type)
283 {
284         struct metaheader *mh, *newmh;
285         unsigned long page;
286
287         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
288                 uint8_t *meta = alloc_metaspace(mh, bytes, type);
289
290                 if (meta)
291                         return meta;
292         }
293
294         /* No room for metadata?  Can we expand an existing one? */
295         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
296                 /* It should end on a page boundary. */
297                 unsigned long nextpage;
298
299                 nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
300                 assert(nextpage % getpagesize() == 0);
301
302                 /* Now, can we grab that page? */
303                 if (get_page_state(pool, nextpage / getpagesize()) != FREE)
304                         continue;
305
306                 /* OK, expand metadata, do it again. */
307                 set_page_state(pool, nextpage / getpagesize(), TAKEN);
308                 BUILD_ASSERT(FREE == 0);
309                 memset((char *)pool + nextpage, 0, getpagesize());
310                 mh->metalen += getpagesize();
311                 return alloc_metaspace(mh, bytes, type);
312         }
313
314         /* No metadata left at all? */
315         page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
316         if (!page)
317                 return NULL;
318
319         newmh = (struct metaheader *)((char *)pool + page * getpagesize());
320         newmh->metalen = getpagesize() - sizeof(*mh);
321         BUILD_ASSERT(FREE == 0);
322         memset(newmh + 1, 0, newmh->metalen);
323
324         /* Sew it into linked list */
325         mh = first_mheader(pool,poolsize);
326         newmh->next = mh->next;
327         mh->next = pool_offset(pool, newmh);
328
329         return alloc_metaspace(newmh, bytes, type);
330 }
331
332 static void alloc_free_pages(void *pool, unsigned long pagenum)
333 {
334         assert(get_page_state(pool, pagenum) == TAKEN_START);
335         set_page_state(pool, pagenum, FREE);
336         while (get_page_state(pool, ++pagenum) == TAKEN)
337                 set_page_state(pool, pagenum, FREE);
338 }
339
340 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
341                                     unsigned long size, unsigned long align)
342 {
343         unsigned long i;
344         uint8_t *metadata;
345
346         /* Look for partial page. */
347         for (i = 0; i < poolsize / getpagesize(); i++) {
348                 unsigned long ret;
349                 if (get_page_state(pool, i) != SPECIAL)
350                         continue;
351
352                 ret = sub_page_alloc(pool, i, size, align);
353                 if (ret)
354                         return ret;
355         }
356
357         /* Create new SUBPAGE page. */
358         i = alloc_get_pages(pool, poolsize, 1, 1);
359         if (i == 0)
360                 return 0;
361
362         /* Get metadata for page. */
363         metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
364         if (!metadata) {
365                 alloc_free_pages(pool, i);
366                 return 0;
367         }
368
369         /* Actually, this is a subpage page now. */
370         set_page_state(pool, i, SPECIAL);
371
372         /* Set metadata pointer for page. */
373         set_page_metadata(pool, i, metadata);
374
375         /* Do allocation like normal */
376         return sub_page_alloc(pool, i, size, align);
377 }
378
379 /* Returns true if we cleaned any pages. */
380 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
381 {
382         unsigned long i;
383         bool progress = false;
384
385         for (i = 0; i < poolsize/getpagesize(); i++) {
386                 uint8_t *meta;
387                 unsigned int j;
388                 if (get_page_state(pool, i) != SPECIAL)
389                         continue;
390
391                 meta = get_page_metadata(pool, i);
392                 /* Skip the header (first bit of metadata). */
393                 for (j = 1; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; j++)
394                         if (get_bit_pair(meta, j) != FREE)
395                                 break;
396
397                 /* So, is this page totally empty? */
398                 if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY+1) {
399                         set_page_state(pool, i, FREE);
400                         progress = true;
401                 }
402         }
403         return progress;
404 }
405
406 /* Returns true if we cleaned any pages. */
407 static bool clean_metadata(void *pool, unsigned long poolsize)
408 {
409         struct metaheader *mh, *prev_mh = NULL;
410         bool progress = false;
411
412         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
413                 uint8_t *meta;
414                 long i;
415
416                 meta = (uint8_t *)(mh + 1);
417                 BUILD_ASSERT(FREE == 0);
418                 for (i = mh->metalen - 1; i > 0; i--)
419                         if (meta[i] != 0)
420                                 break;
421
422                 /* Completely empty? */
423                 if (prev_mh && i == mh->metalen) {
424                         alloc_free_pages(pool,
425                                          pool_offset(pool, mh)/getpagesize());
426                         prev_mh->next = mh->next;
427                         mh = prev_mh;
428                         progress = true;
429                 } else {
430                         uint8_t *p;
431
432                         /* Some pages at end are free? */
433                         for (p = (uint8_t *)(mh+1)+mh->metalen - getpagesize();
434                              p > meta + i;
435                              p -= getpagesize()) {
436                                 set_page_state(pool,
437                                                pool_offset(pool, p)
438                                                / getpagesize(),
439                                                FREE);
440                                 progress = true;
441                         }
442                 }
443         }
444
445         return progress;
446 }
447
448 void *alloc_get(void *pool, unsigned long poolsize,
449                 unsigned long size, unsigned long align)
450 {
451         bool subpage_clean = false, metadata_clean = false;
452         unsigned long ret;
453
454         if (poolsize < MIN_SIZE)
455                 return NULL;
456
457 again:
458         /* Sub-page allocations have an overhead of ~12%. */
459         if (size + size/8 >= getpagesize() || align >= getpagesize()) {
460                 unsigned long pages = div_up(size, getpagesize());
461
462                 ret = alloc_get_pages(pool, poolsize, pages, align)
463                         * getpagesize();
464         } else
465                 ret = alloc_sub_page(pool, poolsize, size, align);
466
467         if (ret != 0)
468                 return (char *)pool + ret;
469
470         /* Allocation failed: garbage collection. */
471         if (!subpage_clean) {
472                 subpage_clean = true;
473                 if (clean_empty_subpages(pool, poolsize))
474                         goto again;
475         }
476
477         if (!metadata_clean) {
478                 metadata_clean = true;
479                 if (clean_metadata(pool, poolsize))
480                         goto again;
481         }
482
483         /* FIXME: Compact metadata? */
484         return NULL;
485 }
486
487 static void subpage_free(void *pool, unsigned long pagenum, void *free)
488 {
489         unsigned long off = (unsigned long)free % getpagesize();
490         uint8_t *metadata;
491
492         assert(off < SUBPAGE_METAOFF);
493         assert(off % BITMAP_GRANULARITY == 0);
494
495         metadata = get_page_metadata(pool, pagenum);
496
497         off /= BITMAP_GRANULARITY;
498
499         /* Offset by one because first bit is used for header. */
500         off++;
501
502         set_bit_pair(metadata, off++, FREE);
503         while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
504                && get_bit_pair(metadata, off) == TAKEN)
505                 set_bit_pair(metadata, off++, FREE);
506 }
507
508 void alloc_free(void *pool, unsigned long poolsize, void *free)
509 {
510         unsigned long pagenum;
511         struct metaheader *mh;
512
513         if (!free)
514                 return;
515
516         assert(poolsize >= MIN_SIZE);
517
518         mh = first_mheader(pool, poolsize);
519         assert((char *)free >= (char *)(mh + 1) + mh->metalen);
520         assert((char *)pool + poolsize > (char *)free);
521
522         pagenum = pool_offset(pool, free) / getpagesize();
523
524         if (get_page_state(pool, pagenum) == SPECIAL)
525                 subpage_free(pool, pagenum, free);
526         else {
527                 assert((unsigned long)free % getpagesize() == 0);
528                 alloc_free_pages(pool, pagenum);
529         }
530 }
531
532 static bool is_metadata_page(void *pool, unsigned long poolsize,
533                              unsigned long page)
534 {
535         struct metaheader *mh;
536
537         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
538                 unsigned long start, end;
539
540                 start = pool_offset(pool, mh);
541                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
542                 if (page >= start/getpagesize() && page < end/getpagesize())
543                         return true;
544         }
545         return false;
546 }
547
548 static bool check_subpage(void *pool, unsigned long poolsize,
549                           unsigned long page)
550 {
551         unsigned long *mhoff = metadata_off(pool, page);
552         unsigned int i;
553         enum alloc_state last_state = FREE;
554
555         if (*mhoff + sizeof(struct metaheader) > poolsize)
556                 return false;
557
558         if (*mhoff % ALIGNOF(struct metaheader) != 0)
559                 return false;
560
561         /* It must point to a metadata page. */
562         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
563                 return false;
564
565         /* Header at start of subpage allocation */
566         if (get_bit_pair((uint8_t *)pool + *mhoff, 0) != BITMAP)
567                 return false;
568
569         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
570                 enum alloc_state state;
571
572                 /* +1 because header is the first byte. */
573                 state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
574                 switch (state) {
575                 case SPECIAL:
576                         return false;
577                 case TAKEN:
578                         if (last_state == FREE)
579                                 return false;
580                         break;
581                 default:
582                         break;
583                 }
584                 last_state = state;
585         }
586         return true;
587 }
588
589 bool alloc_check(void *pool, unsigned long poolsize)
590 {
591         unsigned long i;
592         struct metaheader *mh;
593         enum alloc_state last_state = FREE;
594         bool was_metadata = false;
595
596         if (poolsize < MIN_SIZE)
597                 return true;
598
599         if (get_page_state(pool, 0) != TAKEN_START)
600                 return false;
601
602         /* First check metadata pages. */
603         /* Metadata pages will be marked TAKEN. */
604         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
605                 unsigned long start, end;
606
607                 start = pool_offset(pool, mh);
608                 if (start + sizeof(*mh) > poolsize)
609                         return false;
610
611                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
612                 if (end > poolsize)
613                         return false;
614
615                 /* Non-first pages should start on a page boundary. */
616                 if (mh != first_mheader(pool, poolsize)
617                     && start % getpagesize() != 0)
618                         return false;
619
620                 /* It should end on a page boundary. */
621                 if (end % getpagesize() != 0)
622                         return false;
623         }
624
625         for (i = 0; i < poolsize / getpagesize(); i++) {
626                 enum alloc_state state = get_page_state(pool, i);
627                 bool is_metadata = is_metadata_page(pool, poolsize,i);
628
629                 switch (state) {
630                 case FREE:
631                         /* metadata pages are never free. */
632                         if (is_metadata)
633                                 return false;
634                 case TAKEN_START:
635                         break;
636                 case TAKEN:
637                         /* This should continue a previous block. */
638                         if (last_state == FREE)
639                                 return false;
640                         if (is_metadata != was_metadata)
641                                 return false;
642                         break;
643                 case SPECIAL:
644                         /* Check metadata pointer etc. */
645                         if (!check_subpage(pool, poolsize, i))
646                                 return false;
647                 }
648                 last_state = state;
649                 was_metadata = is_metadata;
650         }
651         return true;
652 }
653
654 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
655 {
656         struct metaheader *mh;
657         unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
658         long i;
659
660         if (poolsize < MIN_SIZE) {
661                 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
662                 return;
663         }
664
665         memset(count, 0, sizeof(count));
666         for (i = 0; i < poolsize / getpagesize(); i++)
667                 count[get_page_state(pool, i)]++;
668
669         mh = first_mheader(pool, poolsize);
670         pagebitlen = (char *)mh - (char *)pool;
671         fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
672                 pagebitlen, count[0], count[1], count[2], count[3]);
673
674         /* One metadata page for every page of page bits. */
675         metadata_pages = div_up(pagebitlen, getpagesize());
676
677         /* Now do each metadata page. */
678         for (; mh; mh = next_mheader(pool,mh)) {
679                 unsigned long free = 0, subpageblocks = 0, len = 0;
680                 uint8_t *meta = (uint8_t *)(mh + 1);
681
682                 metadata_pages += (sizeof(*mh) + mh->metalen) / getpagesize();
683
684                 for (i = 0;
685                      i < mh->metalen * CHAR_BIT / BITS_PER_PAGE;
686                      i += len) {
687                         switch (get_page_state(meta, i)) {
688                         case FREE:
689                                 len = 1;
690                                 free++;
691                                 break;
692                         case BITMAP:
693                                 /* Skip over this allocated part. */
694                                 len = BITMAP_METALEN * CHAR_BIT;
695                                 subpageblocks++;
696                                 break;
697                         default:
698                                 assert(0);
699                         }
700                 }
701
702                 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
703                         pool_offset(pool, mh),
704                         pool_offset(pool, (char *)(mh+1) + mh->metalen),
705                         free, subpageblocks,
706                         subpageblocks * BITMAP_METALEN * 100
707                         / (free + subpageblocks * BITMAP_METALEN));
708         }
709
710         /* Account for total pages allocated. */
711         tot = (count[1] + count[2] - metadata_pages) * getpagesize();
712
713         fprintf(out, "Total metadata bytes = %lu\n",
714                 metadata_pages * getpagesize());
715
716         /* Now do every subpage. */
717         for (i = 0; i < poolsize / getpagesize(); i++) {
718                 uint8_t *meta;
719                 unsigned int j;
720                 if (get_page_state(pool, i) != SPECIAL)
721                         continue;
722
723                 memset(count, 0, sizeof(count));
724                 meta = get_page_metadata(pool, i);
725                 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
726                         count[get_page_state(meta, j)]++;
727
728                 fprintf(out, "Subpage %lu: "
729                         "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
730                         i, count[0], count[1], count[2],
731                         ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
732                         / getpagesize());
733                 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
734         }
735
736         /* This is optimistic, since we overalloc in several cases. */
737         fprintf(out, "Best possible allocation density = %lu%%\n",
738                 tot * 100 / poolsize);
739 }