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