4502b9389fd1f811ef21f63b41435f4b1c65f49d
[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         /* len covers all page states, plus the metaheader. */
147         len = (char *)(mh + 1) - (char *)pool;
148         /* Mark all page states FREE */
149         BUILD_ASSERT(FREE == 0);
150         memset(pool, 0, len);
151
152         /* metaheader len takes us up to next page boundary. */
153         mh->metalen = align_up(len, getpagesize()) - len;
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 -1 on fail. */
162 static long alloc_from_bitmap(uint8_t *bits, unsigned long elems,
163                               unsigned long want, unsigned long align)
164 {
165         long i;
166         unsigned long free;
167
168         free = 0;
169         /* We allocate from far end, to increase ability to expand metadata. */
170         for (i = elems - 1; i >= 0; i--) {
171                 switch (get_bit_pair(bits, i)) {
172                 case FREE:
173                         if (++free >= want) {
174                                 unsigned long j;
175
176                                 /* They might ask for large alignment. */
177                                 if (align && i % align)
178                                         continue;
179
180                                 for (j = i+1; j < i + want; j++)
181                                         set_bit_pair(bits, j, TAKEN);
182                                 set_bit_pair(bits, i, TAKEN_START);
183                                 return i;
184                         }
185                         break;
186                 case SPECIAL:
187                 case TAKEN_START:
188                 case TAKEN:
189                         free = 0;
190                         break;
191                 }
192         }
193
194         return -1;
195 }
196
197 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
198                                      unsigned long pages, unsigned long align)
199 {
200         long i;
201         unsigned long free;
202
203         free = 0;
204         /* We allocate from far end, to increase ability to expand metadata. */
205         for (i = poolsize / getpagesize() - 1; i >= 0; i--) {
206                 switch (get_page_state(pool, i)) {
207                 case FREE:
208                         if (++free >= pages) {
209                                 unsigned long j, addr;
210
211                                 addr = (unsigned long)pool + i * getpagesize();
212
213                                 /* They might ask for multi-page alignment. */
214                                 if (addr % align)
215                                         continue;
216
217                                 for (j = i+1; j < i + pages; j++)
218                                         set_page_state(pool, j, TAKEN);
219                                 set_page_state(pool, i, TAKEN_START);
220                                 return i;
221                         }
222                         break;
223                 case SPECIAL:
224                 case TAKEN_START:
225                 case TAKEN:
226                         free = 0;
227                         break;
228                 }
229         }
230
231         return 0;
232 }
233
234 /* Offset to metadata is at end of page. */
235 static unsigned long *metadata_off(void *pool, unsigned long page)
236 {
237         return (unsigned long *)
238                 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
239 }
240
241 static uint8_t *get_page_metadata(void *pool, unsigned long page)
242 {
243         return (uint8_t *)pool + *metadata_off(pool, page);
244 }
245
246 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
247 {
248         *metadata_off(pool, page) = meta - (uint8_t *)pool;
249 }
250
251 static unsigned long sub_page_alloc(void *pool, unsigned long page,
252                                     unsigned long size, unsigned long align)
253 {
254         uint8_t *bits = get_page_metadata(pool, page);
255         long i;
256
257         /* TAKEN at end means a bitwise alloc. */
258         assert(get_bit_pair(bits, getpagesize()/BITMAP_GRANULARITY-1) == TAKEN);
259
260         /* Our bits are the same as the page bits. */
261         i = alloc_from_bitmap(bits, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
262                               div_up(size, BITMAP_GRANULARITY),
263                               align / BITMAP_GRANULARITY);
264
265         /* Can't allocate? */
266         if (i < 0)
267                 return 0;
268
269         return page*getpagesize() + i*BITMAP_GRANULARITY;
270 }
271
272 static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes)
273 {
274         uint8_t *meta = (uint8_t *)(mh + 1);
275         unsigned long free = 0, len;
276         long i;
277
278         /* TAKEN tags end a subpage alloc. */
279         for (i = mh->metalen * CHAR_BIT / BITS_PER_PAGE - 1; i >= 0; i -= len) {
280                 switch (get_bit_pair(meta, i)) {
281                 case FREE:
282                         len = 1;
283                         free++;
284                         if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
285                                 /* TAKEN marks end of metablock. */
286                                 set_page_state(meta, i + free - 1, TAKEN);
287                                 return meta + i / (CHAR_BIT / BITS_PER_PAGE);
288                         }
289                         break;
290                 case BITMAP:
291                         /* Skip over this allocated part. */
292                         len = BITMAP_METALEN * CHAR_BIT / BITS_PER_PAGE;
293                         free = 0;
294                         break;
295                 default:
296                         assert(0);
297                         return NULL;
298                 }
299         }
300         return NULL;
301 }
302
303 /* We need this many bytes of metadata. */
304 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
305                              unsigned long bytes)
306 {
307         struct metaheader *mh, *newmh;
308         unsigned long page;
309
310         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
311                 uint8_t *meta = alloc_metaspace(mh, bytes);
312
313                 if (meta)
314                         return meta;
315         }
316
317         /* No room for metadata?  Can we expand an existing one? */
318         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
319                 /* It should end on a page boundary. */
320                 unsigned long nextpage;
321
322                 nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
323                 assert(nextpage % getpagesize() == 0);
324
325                 /* Now, can we grab that page? */
326                 if (get_page_state(pool, nextpage / getpagesize()) != FREE)
327                         continue;
328
329                 /* OK, expand metadata, do it again. */
330                 set_page_state(pool, nextpage / getpagesize(), TAKEN);
331                 BUILD_ASSERT(FREE == 0);
332                 memset((char *)pool + nextpage, 0, getpagesize());
333                 mh->metalen += getpagesize();
334                 return alloc_metaspace(mh, bytes);
335         }
336
337         /* No metadata left at all? */
338         page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
339         if (!page)
340                 return NULL;
341
342         newmh = (struct metaheader *)((char *)pool + page * getpagesize());
343         newmh->metalen = getpagesize() - sizeof(*mh);
344         BUILD_ASSERT(FREE == 0);
345         memset(newmh + 1, 0, newmh->metalen);
346
347         /* Sew it into linked list */
348         mh = first_mheader(pool,poolsize);
349         newmh->next = mh->next;
350         mh->next = pool_offset(pool, newmh);
351
352         return alloc_metaspace(newmh, bytes);
353 }
354
355 static void alloc_free_pages(void *pool, unsigned long pagenum)
356 {
357         assert(get_page_state(pool, pagenum) == TAKEN_START);
358         set_page_state(pool, pagenum, FREE);
359         while (get_page_state(pool, ++pagenum) == TAKEN)
360                 set_page_state(pool, pagenum, FREE);
361 }
362
363 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
364                                     unsigned long size, unsigned long align)
365 {
366         unsigned long i;
367         uint8_t *metadata;
368
369         /* Look for partial page. */
370         for (i = 0; i < poolsize / getpagesize(); i++) {
371                 unsigned long ret;
372                 if (get_page_state(pool, i) != SPECIAL)
373                         continue;
374
375                 ret = sub_page_alloc(pool, i, size, align);
376                 if (ret)
377                         return ret;
378         }
379
380         /* Create new SUBPAGE page. */
381         i = alloc_get_pages(pool, poolsize, 1, 1);
382         if (i == 0)
383                 return 0;
384
385         /* Get metadata for page. */
386         metadata = new_metadata(pool, poolsize, BITMAP_METALEN);
387         if (!metadata) {
388                 alloc_free_pages(pool, i);
389                 return 0;
390         }
391
392         /* Actually, this is a subpage page now. */
393         set_page_state(pool, i, SPECIAL);
394
395         /* Set metadata pointer for page. */
396         set_page_metadata(pool, i, metadata);
397
398         /* Do allocation like normal */
399         return sub_page_alloc(pool, i, size, align);
400 }
401
402 /* Returns true if we cleaned any pages. */
403 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
404 {
405         unsigned long i;
406         bool progress = false;
407
408         for (i = 0; i < poolsize/getpagesize(); i++) {
409                 uint8_t *meta;
410                 unsigned int j;
411                 if (get_page_state(pool, i) != SPECIAL)
412                         continue;
413
414                 meta = get_page_metadata(pool, i);
415                 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
416                         if (get_page_state(meta, j) != FREE)
417                                 break;
418
419                 /* So, is this page totally empty? */
420                 if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY) {
421                         set_page_state(pool, i, FREE);
422                         progress = true;
423                 }
424         }
425         return progress;
426 }
427
428 /* Returns true if we cleaned any pages. */
429 static bool clean_metadata(void *pool, unsigned long poolsize)
430 {
431         struct metaheader *mh, *prev_mh = NULL;
432         bool progress = false;
433
434         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
435                 uint8_t *meta;
436                 long i;
437
438                 meta = (uint8_t *)(mh + 1);
439                 BUILD_ASSERT(FREE == 0);
440                 for (i = mh->metalen - 1; i > 0; i--)
441                         if (meta[i] != 0)
442                                 break;
443
444                 /* Completely empty? */
445                 if (prev_mh && i == mh->metalen) {
446                         alloc_free_pages(pool,
447                                          pool_offset(pool, mh)/getpagesize());
448                         prev_mh->next = mh->next;
449                         mh = prev_mh;
450                         progress = true;
451                 } else {
452                         uint8_t *p;
453
454                         /* Some pages at end are free? */
455                         for (p = (uint8_t *)(mh+1)+mh->metalen - getpagesize();
456                              p > meta + i;
457                              p -= getpagesize()) {
458                                 set_page_state(pool,
459                                                pool_offset(pool, p)
460                                                / getpagesize(),
461                                                FREE);
462                                 progress = true;
463                         }
464                 }
465         }
466
467         return progress;
468 }
469
470 void *alloc_get(void *pool, unsigned long poolsize,
471                 unsigned long size, unsigned long align)
472 {
473         bool subpage_clean = false, metadata_clean = false;
474         unsigned long ret;
475
476         if (poolsize < MIN_SIZE)
477                 return NULL;
478
479 again:
480         /* Sub-page allocations have an overhead of ~12%. */
481         if (size + size/8 >= getpagesize() || align >= getpagesize()) {
482                 unsigned long pages = div_up(size, getpagesize());
483
484                 ret = alloc_get_pages(pool, poolsize, pages, align)
485                         * getpagesize();
486         } else
487                 ret = alloc_sub_page(pool, poolsize, size, align);
488
489         if (ret != 0)
490                 return (char *)pool + ret;
491
492         /* Allocation failed: garbage collection. */
493         if (!subpage_clean) {
494                 subpage_clean = true;
495                 if (clean_empty_subpages(pool, poolsize))
496                         goto again;
497         }
498
499         if (!metadata_clean) {
500                 metadata_clean = true;
501                 if (clean_metadata(pool, poolsize))
502                         goto again;
503         }
504
505         /* FIXME: Compact metadata? */
506         return NULL;
507 }
508
509 static void subpage_free(void *pool, unsigned long pagenum, void *free)
510 {
511         unsigned long off = (unsigned long)free % getpagesize();
512         uint8_t *metadata;
513
514         assert(off < SUBPAGE_METAOFF);
515         assert(off % BITMAP_GRANULARITY == 0);
516
517         metadata = get_page_metadata(pool, pagenum);
518
519         off /= BITMAP_GRANULARITY;
520
521         set_page_state(metadata, off++, FREE);
522         while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
523                && get_page_state(metadata, off) == TAKEN)
524                 set_page_state(metadata, off++, FREE);
525 }
526
527 void alloc_free(void *pool, unsigned long poolsize, void *free)
528 {
529         unsigned long pagenum;
530         struct metaheader *mh;
531
532         if (!free)
533                 return;
534
535         assert(poolsize >= MIN_SIZE);
536
537         mh = first_mheader(pool, poolsize);
538         assert((char *)free >= (char *)(mh + 1) + mh->metalen);
539         assert((char *)pool + poolsize > (char *)free);
540
541         pagenum = pool_offset(pool, free) / getpagesize();
542
543         if (get_page_state(pool, pagenum) == SPECIAL)
544                 subpage_free(pool, pagenum, free);
545         else {
546                 assert((unsigned long)free % getpagesize() == 0);
547                 alloc_free_pages(pool, pagenum);
548         }
549 }
550
551 static bool is_metadata_page(void *pool, unsigned long poolsize,
552                              unsigned long page)
553 {
554         struct metaheader *mh;
555
556         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
557                 unsigned long start, end;
558
559                 start = pool_offset(pool, mh);
560                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
561                 if (page >= start/getpagesize() && page < end/getpagesize())
562                         return true;
563         }
564         return false;
565 }
566
567 static bool check_subpage(void *pool, unsigned long poolsize,
568                           unsigned long page)
569 {
570         unsigned long *mhoff = metadata_off(pool, page);
571         unsigned int i;
572         enum alloc_state last_state = FREE;
573
574         if (*mhoff + sizeof(struct metaheader) > poolsize)
575                 return false;
576
577         if (*mhoff % ALIGNOF(struct metaheader) != 0)
578                 return false;
579
580         /* It must point to a metadata page. */
581         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
582                 return false;
583
584         /* Marker at end of subpage allocation is "taken" */
585         if (get_bit_pair((uint8_t *)pool + *mhoff,
586                          getpagesize()/BITMAP_GRANULARITY - 1) != TAKEN)
587                 return false;
588
589         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
590                 enum alloc_state state;
591
592                 state = get_bit_pair((uint8_t *)pool + *mhoff, i);
593                 switch (state) {
594                 case SPECIAL:
595                         return false;
596                 case TAKEN:
597                         if (last_state == FREE)
598                                 return false;
599                         break;
600                 default:
601                         break;
602                 }
603                 last_state = state;
604         }
605         return true;
606 }
607
608 bool alloc_check(void *pool, unsigned long poolsize)
609 {
610         unsigned long i;
611         struct metaheader *mh;
612         enum alloc_state last_state = FREE;
613         bool was_metadata = false;
614
615         if (poolsize < MIN_SIZE)
616                 return true;
617
618         if (get_page_state(pool, 0) != TAKEN_START)
619                 return false;
620
621         /* First check metadata pages. */
622         /* Metadata pages will be marked TAKEN. */
623         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
624                 unsigned long start, end;
625
626                 start = pool_offset(pool, mh);
627                 if (start + sizeof(*mh) > poolsize)
628                         return false;
629
630                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
631                 if (end > poolsize)
632                         return false;
633
634                 /* Non-first pages should start on a page boundary. */
635                 if (mh != first_mheader(pool, poolsize)
636                     && start % getpagesize() != 0)
637                         return false;
638
639                 /* It should end on a page boundary. */
640                 if (end % getpagesize() != 0)
641                         return false;
642         }
643
644         for (i = 0; i < poolsize / getpagesize(); i++) {
645                 enum alloc_state state = get_page_state(pool, i);
646                 bool is_metadata = is_metadata_page(pool, poolsize,i);
647
648                 switch (state) {
649                 case FREE:
650                         /* metadata pages are never free. */
651                         if (is_metadata)
652                                 return false;
653                 case TAKEN_START:
654                         break;
655                 case TAKEN:
656                         /* This should continue a previous block. */
657                         if (last_state == FREE)
658                                 return false;
659                         if (is_metadata != was_metadata)
660                                 return false;
661                         break;
662                 case SPECIAL:
663                         /* Check metadata pointer etc. */
664                         if (!check_subpage(pool, poolsize, i))
665                                 return false;
666                 }
667                 last_state = state;
668                 was_metadata = is_metadata;
669         }
670         return true;
671 }
672
673 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
674 {
675         struct metaheader *mh;
676         unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
677         long i;
678
679         if (poolsize < MIN_SIZE) {
680                 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
681                 return;
682         }
683
684         memset(count, 0, sizeof(count));
685         for (i = 0; i < poolsize / getpagesize(); i++)
686                 count[get_page_state(pool, i)]++;
687
688         mh = first_mheader(pool, poolsize);
689         pagebitlen = (char *)mh - (char *)pool;
690         fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
691                 pagebitlen, count[0], count[1], count[2], count[3]);
692
693         /* One metadata page for every page of page bits. */
694         metadata_pages = div_up(pagebitlen, getpagesize());
695
696         /* Now do each metadata page. */
697         for (; mh; mh = next_mheader(pool,mh)) {
698                 unsigned long free = 0, subpageblocks = 0, len = 0;
699                 uint8_t *meta = (uint8_t *)(mh + 1);
700
701                 metadata_pages += (sizeof(*mh) + mh->metalen) / getpagesize();
702
703                 /* TAKEN tags end a subpage alloc. */
704                 for (i = mh->metalen * CHAR_BIT/BITS_PER_PAGE - 1;
705                      i >= 0;
706                      i -= len) {
707                         switch (get_page_state(meta, i)) {
708                         case FREE:
709                                 len = 1;
710                                 free++;
711                                 break;
712                         case TAKEN:
713                                 /* Skip over this allocated part. */
714                                 len = BITMAP_METALEN * CHAR_BIT;
715                                 subpageblocks++;
716                                 break;
717                         default:
718                                 assert(0);
719                         }
720                 }
721
722                 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
723                         pool_offset(pool, mh),
724                         pool_offset(pool, (char *)(mh+1) + mh->metalen),
725                         free, subpageblocks,
726                         subpageblocks * BITMAP_METALEN * 100
727                         / (free + subpageblocks * BITMAP_METALEN));
728         }
729
730         /* Account for total pages allocated. */
731         tot = (count[1] + count[2] - metadata_pages) * getpagesize();
732
733         fprintf(out, "Total metadata bytes = %lu\n",
734                 metadata_pages * getpagesize());
735
736         /* Now do every subpage. */
737         for (i = 0; i < poolsize / getpagesize(); i++) {
738                 uint8_t *meta;
739                 unsigned int j;
740                 if (get_page_state(pool, i) != SPECIAL)
741                         continue;
742
743                 memset(count, 0, sizeof(count));
744                 meta = get_page_metadata(pool, i);
745                 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
746                         count[get_page_state(meta, j)]++;
747
748                 fprintf(out, "Subpage %lu: "
749                         "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
750                         i, count[0], count[1], count[2],
751                         ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
752                         / getpagesize());
753                 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
754         }
755
756         /* This is optimistic, since we overalloc in several cases. */
757         fprintf(out, "Best possible allocation density = %lu%%\n",
758                 tot * 100 / poolsize);
759 }