Move modules to ccan/ tools to tools/
[ccan] / 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 <stdlib.h>
7 #include "alloc.h"
8 #include "build_assert/build_assert.h"
9 #include "alignof/alignof.h"
10 #include "config.h"
11
12 /* FIXME: We assume getpagesize() doesnt change.  Remapping file with
13  * different pagesize should still work. */
14
15 /* FIXME: Doesn't handle non-page-aligned poolsize. */
16
17 /* FIXME: Reduce. */
18 #define MIN_SIZE (getpagesize() * 2)
19
20 /* What's the granularity of sub-page allocs? */
21 #define BITMAP_GRANULARITY 4
22
23 /* File layout:
24  *
25  *  file := pagestates pad uniform-cache metadata
26  *  pagestates := pages * 2-bits-per-page
27  *  pad := pad to next ALIGNOF(metaheader)
28  *
29  *  metadata := metalen next-ptr metabits
30  *  metabits := freeblock | bitblock | uniformblock
31  *  freeblock := FREE +
32  *  bitblock := BITMAP + 2-bits-per-bit-in-page + pad-to-byte
33  *  uniformblock := UNIFORM + 14-bit-byte-len + bits + pad-to-byte
34  */
35 #define UNIFORM_CACHE_NUM 16
36 struct uniform_cache
37 {
38         uint16_t size[UNIFORM_CACHE_NUM];
39         /* These could be u32 if we're prepared to limit size. */
40         unsigned long page[UNIFORM_CACHE_NUM];
41 };
42
43 struct metaheader
44 {
45         /* Next meta header, or 0 */
46         unsigned long next;
47         /* Bits start here. */
48 };
49
50 /* Assumes a is a power of two. */
51 static unsigned long align_up(unsigned long x, unsigned long a)
52 {
53         return (x + a - 1) & ~(a - 1);
54 }
55
56 static unsigned long align_down(unsigned long x, unsigned long a)
57 {
58         return x & ~(a - 1);
59 }
60
61 static unsigned long div_up(unsigned long x, unsigned long a)
62 {
63         return (x + a - 1) / a;
64 }
65
66 /* It turns out that we spend a lot of time dealing with bit pairs.
67  * These routines manipulate them.
68  */
69 static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
70 {
71         return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
72 }
73
74 static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
75 {
76         bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
77         bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
78 }
79
80 /* This is used for page states and subpage allocations */
81 enum alloc_state
82 {
83         FREE,
84         TAKEN,
85         TAKEN_START,
86         SPECIAL,        /* Sub-page allocation for page states. */
87 };
88
89 /* The types for subpage metadata. */
90 enum sub_metadata_type
91 {
92         /* FREE is same as alloc state */
93         BITMAP = 1, /* bitmap allocated page */
94         UNIFORM, /* uniform size allocated page */
95 };
96
97 /* Page states are represented by bitpairs, at the start of the pool. */
98 #define BITS_PER_PAGE 2
99
100 /* How much metadata info per byte? */
101 #define METADATA_PER_BYTE (CHAR_BIT / 2)
102
103 static uint8_t *get_page_statebits(const void *pool)
104 {
105         return (uint8_t *)pool + sizeof(struct uniform_cache);
106 }
107
108 static enum alloc_state get_page_state(const void *pool, unsigned long page)
109 {
110         return get_bit_pair(get_page_statebits(pool), page);
111 }
112
113 static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
114 {
115         set_bit_pair(get_page_statebits(pool), page, s);
116 }
117
118 /* The offset of metadata for a subpage allocation is found at the end
119  * of the subpage */
120 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
121
122 /* This is the length of metadata in bits.  It consists of two bits
123  * for every BITMAP_GRANULARITY of usable bytes in the page, then two
124  * bits for the tailer.. */
125 #define BITMAP_METABITLEN                                               \
126     ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
127
128 /* This is the length in bytes. */
129 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
130
131 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
132 {
133         unsigned int pagestatelen;
134
135         pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
136                                        CHAR_BIT),
137                                 ALIGNOF(struct metaheader));
138         return (struct metaheader *)(get_page_statebits(pool) + pagestatelen);
139 }
140
141 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
142 {
143         if (!mh->next)
144                 return NULL;
145
146         return (struct metaheader *)((char *)pool + mh->next);
147 }
148
149 static unsigned long pool_offset(void *pool, void *p)
150 {
151         return (char *)p - (char *)pool;
152 }
153
154 void alloc_init(void *pool, unsigned long poolsize)
155 {
156         /* FIXME: Alignment assumptions about pool. */
157         unsigned long len, i;
158         struct metaheader *mh;
159
160         if (poolsize < MIN_SIZE)
161                 return;
162
163         mh = first_mheader(pool, poolsize);
164
165         /* Mark all page states FREE, all uniform caches zero, and all of
166          * metaheader bitmap which takes rest of first page. */
167         len = align_up(pool_offset(pool, mh + 1), getpagesize());
168         BUILD_ASSERT(FREE == 0);
169         memset(pool, 0, len);
170
171         /* Mark the pagestate and metadata page(s) allocated. */
172         set_page_state(pool, 0, TAKEN_START);
173         for (i = 1; i < div_up(len, getpagesize()); i++)
174                 set_page_state(pool, i, TAKEN);
175 }
176
177 /* Two bits per element, representing page states.  Returns 0 on fail.
178  * off is used to allocate from subpage bitmaps, which use the first 2
179  * bits as the type, so the real bitmap is offset by 1. */
180 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
181                                        unsigned long elems,
182                                        unsigned long want, unsigned long align)
183 {
184         long i;
185         unsigned long free;
186
187         free = 0;
188         /* We allocate from far end, to increase ability to expand metadata. */
189         for (i = elems - 1; i >= 0; i--) {
190                 switch (get_bit_pair(bits, off+i)) {
191                 case FREE:
192                         if (++free >= want) {
193                                 unsigned long j;
194
195                                 /* They might ask for large alignment. */
196                                 if (align && i % align)
197                                         continue;
198
199                                 set_bit_pair(bits, off+i, TAKEN_START);
200                                 for (j = i+1; j < i + want; j++)
201                                         set_bit_pair(bits, off+j, TAKEN);
202                                 return off+i;
203                         }
204                         break;
205                 case SPECIAL:
206                 case TAKEN_START:
207                 case TAKEN:
208                         free = 0;
209                         break;
210                 }
211         }
212
213         return 0;
214 }
215
216 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
217                                      unsigned long pages, unsigned long align)
218 {
219         return alloc_from_bitmap(get_page_statebits(pool),
220                                  0, poolsize / getpagesize(), pages,
221                                  align / getpagesize());
222 }
223
224 /* Offset to metadata is at end of page. */
225 static unsigned long *metadata_off(void *pool, unsigned long page)
226 {
227         return (unsigned long *)
228                 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
229 }
230
231 static uint8_t *get_page_metadata(void *pool, unsigned long page)
232 {
233         return (uint8_t *)pool + *metadata_off(pool, page);
234 }
235
236 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
237 {
238         *metadata_off(pool, page) = meta - (uint8_t *)pool;
239 }
240
241 static unsigned long sub_page_alloc(void *pool, unsigned long page,
242                                     unsigned long size, unsigned long align)
243 {
244         uint8_t *bits = get_page_metadata(pool, page);
245         unsigned long i;
246         enum sub_metadata_type type;
247
248         type = get_bit_pair(bits, 0);
249
250         /* If this is a uniform page, we can't allocate from it. */
251         if (type == UNIFORM)
252                 return 0;
253
254         assert(type == BITMAP);
255
256         /* We use a standart bitmap, but offset because of that BITMAP
257          * header. */
258         i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
259                               div_up(size, BITMAP_GRANULARITY),
260                               align / BITMAP_GRANULARITY);
261
262         /* Can't allocate? */
263         if (i == 0)
264                 return 0;
265
266         /* i-1 because of the header. */
267         return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
268 }
269
270 /* We look at the page states to figure out where the allocation for this
271  * metadata ends. */
272 static unsigned long get_metalen(void *pool, unsigned long poolsize,
273                                  struct metaheader *mh)
274 {
275         unsigned long i, first, pages = poolsize / getpagesize();
276
277         first = pool_offset(pool, mh + 1)/getpagesize();
278
279         for (i = first + 1; i < pages && get_page_state(pool,i) == TAKEN; i++);
280
281         return i * getpagesize() - pool_offset(pool, mh + 1);
282 }
283
284 static unsigned int uniform_metalen(unsigned int usize)
285 {
286         unsigned int metalen;
287
288         assert(usize < (1 << 14));
289
290         /* Two bits for the header, 14 bits for size, then one bit for each
291          * element the page can hold.  Round up to number of bytes. */
292         metalen = div_up(2 + 14 + SUBPAGE_METAOFF / usize, CHAR_BIT);
293
294         /* To ensure metaheader is always aligned, round bytes up. */
295         metalen = align_up(metalen, ALIGNOF(struct metaheader));
296
297         return metalen;
298 }
299
300 static unsigned int decode_usize(uint8_t *meta)
301 {
302         return ((unsigned)meta[1] << (CHAR_BIT-2)) | (meta[0] >> 2);
303 }
304
305 static void encode_usize(uint8_t *meta, unsigned int usize)
306 {
307         meta[0] = (UNIFORM | (usize << 2));
308         meta[1] = (usize >> (CHAR_BIT - 2));
309 }
310
311 static uint8_t *alloc_metaspace(void *pool, unsigned long poolsize,
312                                 struct metaheader *mh, unsigned long bytes,
313                                 enum sub_metadata_type type)
314 {
315         uint8_t *meta = (uint8_t *)(mh + 1);
316         unsigned long free = 0, len, i, metalen;
317
318         metalen = get_metalen(pool, poolsize, mh);
319
320         /* Walk through metadata looking for free. */
321         for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
322                 switch (get_bit_pair(meta, i)) {
323                 case FREE:
324                         len = 1;
325                         free++;
326                         if (free == bytes * METADATA_PER_BYTE) {
327                                 /* Mark this as a bitmap. */
328                                 set_bit_pair(meta, i - free + 1, type);
329                                 return meta + (i - free + 1)/METADATA_PER_BYTE;
330                         }
331                         break;
332                 case BITMAP:
333                         /* Skip over this allocated part. */
334                         len = BITMAP_METALEN * METADATA_PER_BYTE;
335                         free = 0;
336                         break;
337                 case UNIFORM:
338                         /* Figure metalen given usize. */
339                         len = decode_usize(meta + i / METADATA_PER_BYTE);
340                         len = uniform_metalen(len) * METADATA_PER_BYTE;
341                         free = 0;
342                         break;
343                 default:
344                         assert(0);
345                         return NULL;
346                 }
347         }
348         return NULL;
349 }
350
351 /* We need this many bytes of metadata. */
352 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
353                              unsigned long bytes, enum sub_metadata_type type)
354 {
355         struct metaheader *mh, *newmh;
356         unsigned long page;
357         uint8_t *meta;
358
359         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh))
360                 if ((meta = alloc_metaspace(pool, poolsize, mh, bytes, type)))
361                         return meta;
362
363         /* No room for metadata?  Can we expand an existing one? */
364         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
365                 unsigned long nextpage;
366
367                 /* We start on this page. */
368                 nextpage = pool_offset(pool, (char *)(mh+1))/getpagesize();
369                 /* Iterate through any other pages we own. */
370                 while (get_page_state(pool, ++nextpage) == TAKEN);
371
372                 /* Now, can we grab that page? */
373                 if (get_page_state(pool, nextpage) != FREE)
374                         continue;
375
376                 /* OK, expand metadata, do it again. */
377                 set_page_state(pool, nextpage, TAKEN);
378                 BUILD_ASSERT(FREE == 0);
379                 memset((char *)pool + nextpage*getpagesize(), 0, getpagesize());
380                 return alloc_metaspace(pool, poolsize, mh, bytes, type);
381         }
382
383         /* No metadata left at all? */
384         page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
385         if (!page)
386                 return NULL;
387
388         newmh = (struct metaheader *)((char *)pool + page * getpagesize());
389         BUILD_ASSERT(FREE == 0);
390         memset(newmh + 1, 0, getpagesize() - sizeof(*mh));
391
392         /* Sew it into linked list */
393         mh = first_mheader(pool,poolsize);
394         newmh->next = mh->next;
395         mh->next = pool_offset(pool, newmh);
396
397         return alloc_metaspace(pool, poolsize, newmh, bytes, type);
398 }
399
400 static void alloc_free_pages(void *pool, unsigned long pagenum)
401 {
402         assert(get_page_state(pool, pagenum) == TAKEN_START);
403         set_page_state(pool, pagenum, FREE);
404         while (get_page_state(pool, ++pagenum) == TAKEN)
405                 set_page_state(pool, pagenum, FREE);
406 }
407
408 static void maybe_transform_uniform_page(void *pool, unsigned long offset)
409 {
410         /* FIXME: If possible and page isn't full, change to a bitmap */
411 }
412
413 /* Returns 0 or the size of the uniform alloc to use */
414 static unsigned long suitable_for_uc(unsigned long size, unsigned long align)
415 {
416         unsigned long num_elems, wastage, usize;
417         unsigned long bitmap_cost;
418
419         if (size == 0)
420                 size = 1;
421
422         /* Fix up silly alignments. */
423         usize = align_up(size, align);
424
425         /* How many can fit in this page? */
426         num_elems = SUBPAGE_METAOFF / usize;
427
428         /* Can happen with bigger alignments. */
429         if (!num_elems)
430                 return 0;
431
432         /* Usize maxes out at 14 bits. */
433         if (usize >= (1 << 14))
434                 return 0;
435
436         /* How many bytes would be left at the end? */
437         wastage = SUBPAGE_METAOFF % usize;
438
439         /* If we can get a larger allocation within alignment constraints, we
440          * should do it, otherwise might as well leave wastage at the end. */
441         usize += align_down(wastage / num_elems, align);
442
443         /* Bitmap allocation costs 2 bits per BITMAP_GRANULARITY bytes, plus
444          * however much we waste in rounding up to BITMAP_GRANULARITY. */
445         bitmap_cost = 2 * div_up(size, BITMAP_GRANULARITY)
446                 + CHAR_BIT * (align_up(size, BITMAP_GRANULARITY) - size);
447
448         /* Our cost is 1 bit, plus usize overhead */
449         if (bitmap_cost < 1 + (usize - size) * CHAR_BIT)
450                 return 0;
451
452         return usize;
453 }
454
455 static unsigned long uniform_alloc(void *pool, unsigned long poolsize,
456                                    struct uniform_cache *uc,
457                                    unsigned long ucnum)
458 {
459         uint8_t *metadata = get_page_metadata(pool, uc->page[ucnum]) + 2;
460         unsigned long i, max;
461
462         /* Simple one-bit-per-object bitmap. */
463         max = SUBPAGE_METAOFF / uc->size[ucnum];
464         for (i = 0; i < max; i++) {
465                 if (!(metadata[i / CHAR_BIT] & (1 << (i % CHAR_BIT)))) {
466                         metadata[i / CHAR_BIT] |= (1 << (i % CHAR_BIT));
467                         return uc->page[ucnum] * getpagesize()
468                                 + i * uc->size[ucnum];
469                 }
470         }
471
472         return 0;
473 }
474
475 static unsigned long new_uniform_page(void *pool, unsigned long poolsize,
476                                       unsigned long usize)
477 {
478         unsigned long page, metalen;
479         uint8_t *metadata;
480
481         page = alloc_get_pages(pool, poolsize, 1, 1);
482         if (page == 0)
483                 return 0;
484
485         metalen = uniform_metalen(usize);
486
487         /* Get metadata for page. */
488         metadata = new_metadata(pool, poolsize, metalen, UNIFORM);
489         if (!metadata) {
490                 alloc_free_pages(pool, page);
491                 return 0;
492         }
493
494         encode_usize(metadata, usize);
495
496         BUILD_ASSERT(FREE == 0);
497         memset(metadata + 2, 0, metalen - 2);
498
499         /* Actually, this is a subpage page now. */
500         set_page_state(pool, page, SPECIAL);
501
502         /* Set metadata pointer for page. */
503         set_page_metadata(pool, page, metadata);
504
505         return page;
506 }
507
508 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
509                                     unsigned long size, unsigned long align)
510 {
511         unsigned long i, usize;
512         uint8_t *metadata;
513         struct uniform_cache *uc = pool;
514
515         usize = suitable_for_uc(size, align);
516         if (usize) {
517                 /* Look for a uniform page. */
518                 for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
519                         if (uc->size[i] == usize) {
520                                 unsigned long ret;
521                                 ret = uniform_alloc(pool, poolsize, uc, i);
522                                 if (ret != 0)
523                                         return ret;
524                                 /* OK, that one is full, remove from cache. */
525                                 uc->size[i] = 0;
526                                 break;
527                         }
528                 }
529
530                 /* OK, try a new uniform page.  Use random discard for now. */
531                 i = random() % UNIFORM_CACHE_NUM;
532                 maybe_transform_uniform_page(pool, uc->page[i]);
533
534                 uc->page[i] = new_uniform_page(pool, poolsize, usize);
535                 if (uc->page[i]) {
536                         uc->size[i] = usize;
537                         return uniform_alloc(pool, poolsize, uc, i);
538                 }
539                 uc->size[i] = 0;
540         }
541
542         /* Look for partial page. */
543         for (i = 0; i < poolsize / getpagesize(); i++) {
544                 unsigned long ret;
545                 if (get_page_state(pool, i) != SPECIAL)
546                         continue;
547
548                 ret = sub_page_alloc(pool, i, size, align);
549                 if (ret)
550                         return ret;
551         }
552
553         /* Create new SUBPAGE page. */
554         i = alloc_get_pages(pool, poolsize, 1, 1);
555         if (i == 0)
556                 return 0;
557
558         /* Get metadata for page. */
559         metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
560         if (!metadata) {
561                 alloc_free_pages(pool, i);
562                 return 0;
563         }
564
565         /* Actually, this is a subpage page now. */
566         set_page_state(pool, i, SPECIAL);
567
568         /* Set metadata pointer for page. */
569         set_page_metadata(pool, i, metadata);
570
571         /* Do allocation like normal */
572         return sub_page_alloc(pool, i, size, align);
573 }
574
575 static bool bitmap_page_is_empty(uint8_t *meta)
576 {
577         unsigned int i;
578
579         /* Skip the header (first bit of metadata). */
580         for (i = 1; i < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; i++)
581                 if (get_bit_pair(meta, i) != FREE)
582                         return false;
583
584         return true;
585 }
586
587 static bool uniform_page_is_empty(uint8_t *meta)
588 {
589         unsigned int i, metalen;
590
591         metalen = uniform_metalen(decode_usize(meta));
592
593         /* Skip the header (first two bytes of metadata). */
594         for (i = 2; i < metalen + 2; i++) {
595                 BUILD_ASSERT(FREE == 0);
596                 if (meta[i])
597                         return false;
598         }
599         return true;
600 }
601
602 static bool special_page_is_empty(void *pool, unsigned long page)
603 {
604         uint8_t *meta;
605         enum sub_metadata_type type;
606
607         meta = get_page_metadata(pool, page);
608         type = get_bit_pair(meta, 0);
609
610         switch (type) {
611         case UNIFORM:
612                 return uniform_page_is_empty(meta);
613         case BITMAP:
614                 return bitmap_page_is_empty(meta);
615         default:
616                 assert(0);
617         }
618 }
619
620 static void clear_special_metadata(void *pool, unsigned long page)
621 {
622         uint8_t *meta;
623         enum sub_metadata_type type;
624
625         meta = get_page_metadata(pool, page);
626         type = get_bit_pair(meta, 0);
627
628         switch (type) {
629         case UNIFORM:
630                 /* First two bytes are the header, rest is already FREE */
631                 BUILD_ASSERT(FREE == 0);
632                 memset(meta, 0, 2);
633                 break;
634         case BITMAP:
635                 /* First two bits is the header. */
636                 BUILD_ASSERT(BITMAP_METALEN > 1);
637                 meta[0] = 0;
638                 break;
639         default:
640                 assert(0);
641         }
642 }
643
644 /* Returns true if we cleaned any pages. */
645 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
646 {
647         unsigned long i;
648         bool progress = false;
649
650         for (i = 0; i < poolsize/getpagesize(); i++) {
651                 if (get_page_state(pool, i) != SPECIAL)
652                         continue;
653
654                 if (special_page_is_empty(pool, i)) {
655                         clear_special_metadata(pool, i);
656                         set_page_state(pool, i, FREE);
657                         progress = true;
658                 }
659         }
660         return progress;
661 }
662
663 /* Returns true if we cleaned any pages. */
664 static bool clean_metadata(void *pool, unsigned long poolsize)
665 {
666         struct metaheader *mh, *prev_mh = NULL;
667         bool progress = false;
668
669         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
670                 uint8_t *meta;
671                 long i;
672                 unsigned long metalen = get_metalen(pool, poolsize, mh);
673
674                 meta = (uint8_t *)(mh + 1);
675                 BUILD_ASSERT(FREE == 0);
676                 for (i = metalen - 1; i > 0; i--)
677                         if (meta[i] != 0)
678                                 break;
679
680                 /* Completely empty? */
681                 if (prev_mh && i == metalen) {
682                         alloc_free_pages(pool,
683                                          pool_offset(pool, mh)/getpagesize());
684                         prev_mh->next = mh->next;
685                         mh = prev_mh;
686                         progress = true;
687                 } else {
688                         uint8_t *p;
689
690                         /* Some pages at end are free? */
691                         for (p = (uint8_t *)(mh+1) + metalen - getpagesize();
692                              p > meta + i;
693                              p -= getpagesize()) {
694                                 set_page_state(pool,
695                                                pool_offset(pool, p)
696                                                / getpagesize(),
697                                                FREE);
698                                 progress = true;
699                         }
700                 }
701         }
702
703         return progress;
704 }
705
706 void *alloc_get(void *pool, unsigned long poolsize,
707                 unsigned long size, unsigned long align)
708 {
709         bool subpage_clean = false, metadata_clean = false;
710         unsigned long ret;
711
712         if (poolsize < MIN_SIZE)
713                 return NULL;
714
715 again:
716         /* Sub-page allocations have an overhead of ~12%. */
717         if (size + size/8 >= getpagesize() || align >= getpagesize()) {
718                 unsigned long pages = div_up(size, getpagesize());
719
720                 ret = alloc_get_pages(pool, poolsize, pages, align)
721                         * getpagesize();
722         } else
723                 ret = alloc_sub_page(pool, poolsize, size, align);
724
725         if (ret != 0)
726                 return (char *)pool + ret;
727
728         /* Allocation failed: garbage collection. */
729         if (!subpage_clean) {
730                 subpage_clean = true;
731                 if (clean_empty_subpages(pool, poolsize))
732                         goto again;
733         }
734
735         if (!metadata_clean) {
736                 metadata_clean = true;
737                 if (clean_metadata(pool, poolsize))
738                         goto again;
739         }
740
741         /* FIXME: Compact metadata? */
742         return NULL;
743 }
744
745 static void bitmap_free(void *pool, unsigned long pagenum, unsigned long off,
746                         uint8_t *metadata)
747 {
748         assert(off % BITMAP_GRANULARITY == 0);
749
750         off /= BITMAP_GRANULARITY;
751
752         /* Offset by one because first bit is used for header. */
753         off++;
754
755         set_bit_pair(metadata, off++, FREE);
756         while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
757                && get_bit_pair(metadata, off) == TAKEN)
758                 set_bit_pair(metadata, off++, FREE);
759 }
760
761 static void uniform_free(void *pool, unsigned long pagenum, unsigned long off,
762                          uint8_t *metadata)
763 {
764         unsigned int usize, bit;
765
766         usize = decode_usize(metadata);
767         /* Must have been this size. */
768         assert(off % usize == 0);
769         bit = off / usize;
770
771         /* Skip header. */
772         metadata += 2;
773
774         /* Must have been allocated. */
775         assert(metadata[bit / CHAR_BIT] & (1 << (bit % CHAR_BIT)));
776         metadata[bit / CHAR_BIT] &= ~(1 << (bit % CHAR_BIT));
777 }
778
779 static void subpage_free(void *pool, unsigned long pagenum, void *free)
780 {
781         unsigned long off = (unsigned long)free % getpagesize();
782         uint8_t *metadata = get_page_metadata(pool, pagenum);
783         enum sub_metadata_type type;
784
785         type = get_bit_pair(metadata, 0);
786
787         assert(off < SUBPAGE_METAOFF);
788
789         switch (type) {
790         case BITMAP:
791                 bitmap_free(pool, pagenum, off, metadata);
792                 break;
793         case UNIFORM:
794                 uniform_free(pool, pagenum, off, metadata);
795                 break;
796         default:
797                 assert(0);
798         }
799 }
800
801 void alloc_free(void *pool, unsigned long poolsize, void *free)
802 {
803         unsigned long pagenum;
804         struct metaheader *mh;
805
806         if (!free)
807                 return;
808
809         assert(poolsize >= MIN_SIZE);
810
811         mh = first_mheader(pool, poolsize);
812         assert((char *)free >= (char *)(mh + 1));
813         assert((char *)pool + poolsize > (char *)free);
814
815         pagenum = pool_offset(pool, free) / getpagesize();
816
817         if (get_page_state(pool, pagenum) == SPECIAL)
818                 subpage_free(pool, pagenum, free);
819         else {
820                 assert((unsigned long)free % getpagesize() == 0);
821                 alloc_free_pages(pool, pagenum);
822         }
823 }
824
825 static bool is_metadata_page(void *pool, unsigned long poolsize,
826                              unsigned long page)
827 {
828         struct metaheader *mh;
829
830         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
831                 unsigned long start, end;
832
833                 start = pool_offset(pool, mh);
834                 end = pool_offset(pool, (char *)(mh+1)
835                                   + get_metalen(pool, poolsize, mh));
836                 if (page >= start/getpagesize() && page < end/getpagesize())
837                         return true;
838         }
839         return false;
840 }
841
842 static bool check_bitmap_metadata(void *pool, unsigned long *mhoff)
843 {
844         enum alloc_state last_state = FREE;
845         unsigned int i;
846
847         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
848                 enum alloc_state state;
849
850                 /* +1 because header is the first byte. */
851                 state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
852                 switch (state) {
853                 case SPECIAL:
854                         return false;
855                 case TAKEN:
856                         if (last_state == FREE)
857                                 return false;
858                         break;
859                 default:
860                         break;
861                 }
862                 last_state = state;
863         }
864         return true;
865 }
866
867 static bool check_uniform_metadata(void *pool, unsigned long *mhoff)
868 {
869         uint8_t *meta = (uint8_t *)pool + *mhoff;
870         unsigned int i, usize;
871         struct uniform_cache *uc = pool;
872
873         usize = decode_usize(meta);
874         if (usize == 0 || suitable_for_uc(usize, 1) != usize)
875                 return false;
876
877         /* If it's in uniform cache, make sure that agrees on size. */
878         for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
879                 uint8_t *ucm;
880
881                 if (!uc->size[i])
882                         continue;
883
884                 ucm = get_page_metadata(pool, uc->page[i]);
885                 if (ucm != meta)
886                         continue;
887
888                 if (usize != uc->size[i])
889                         return false;
890         }
891         return true;
892 }
893
894 static bool check_subpage(void *pool, unsigned long poolsize,
895                           unsigned long page)
896 {
897         unsigned long *mhoff = metadata_off(pool, page);
898
899         if (*mhoff + sizeof(struct metaheader) > poolsize)
900                 return false;
901
902         if (*mhoff % ALIGNOF(struct metaheader) != 0)
903                 return false;
904
905         /* It must point to a metadata page. */
906         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
907                 return false;
908
909         /* Header at start of subpage allocation */
910         switch (get_bit_pair((uint8_t *)pool + *mhoff, 0)) {
911         case BITMAP:
912                 return check_bitmap_metadata(pool, mhoff);
913         case UNIFORM:
914                 return check_uniform_metadata(pool, mhoff);
915         default:
916                 return false;
917         }
918
919 }
920
921 bool alloc_check(void *pool, unsigned long poolsize)
922 {
923         unsigned long i;
924         struct metaheader *mh;
925         enum alloc_state last_state = FREE;
926         bool was_metadata = false;
927
928         if (poolsize < MIN_SIZE)
929                 return true;
930
931         if (get_page_state(pool, 0) != TAKEN_START)
932                 return false;
933
934         /* First check metadata pages. */
935         /* Metadata pages will be marked TAKEN. */
936         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
937                 unsigned long start, end;
938
939                 start = pool_offset(pool, mh);
940                 if (start + sizeof(*mh) > poolsize)
941                         return false;
942
943                 end = pool_offset(pool, (char *)(mh+1)
944                                   + get_metalen(pool, poolsize, mh));
945                 if (end > poolsize)
946                         return false;
947
948                 /* Non-first pages should start on a page boundary. */
949                 if (mh != first_mheader(pool, poolsize)
950                     && start % getpagesize() != 0)
951                         return false;
952
953                 /* It should end on a page boundary. */
954                 if (end % getpagesize() != 0)
955                         return false;
956         }
957
958         for (i = 0; i < poolsize / getpagesize(); i++) {
959                 enum alloc_state state = get_page_state(pool, i);
960                 bool is_metadata = is_metadata_page(pool, poolsize,i);
961
962                 switch (state) {
963                 case FREE:
964                         /* metadata pages are never free. */
965                         if (is_metadata)
966                                 return false;
967                 case TAKEN_START:
968                         break;
969                 case TAKEN:
970                         /* This should continue a previous block. */
971                         if (last_state == FREE)
972                                 return false;
973                         if (is_metadata != was_metadata)
974                                 return false;
975                         break;
976                 case SPECIAL:
977                         /* Check metadata pointer etc. */
978                         if (!check_subpage(pool, poolsize, i))
979                                 return false;
980                 }
981                 last_state = state;
982                 was_metadata = is_metadata;
983         }
984         return true;
985 }
986
987 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
988 {
989         struct metaheader *mh;
990         struct uniform_cache *uc = pool;
991         unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
992         long i;
993
994         if (poolsize < MIN_SIZE) {
995                 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
996                 return;
997         }
998
999         tot = 0;
1000         for (i = 0; i < UNIFORM_CACHE_NUM; i++)
1001                 tot += (uc->size[i] != 0);
1002         fprintf(out, "Uniform cache (%lu entries):\n", tot);
1003         for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
1004                 unsigned int j, total = 0;
1005                 uint8_t *meta;
1006
1007                 if (!uc->size[i])
1008                         continue;
1009
1010                 /* First two bytes are header. */
1011                 meta = get_page_metadata(pool, uc->page[i]) + 2;
1012
1013                 for (j = 0; j < SUBPAGE_METAOFF / uc->size[i]; j++)
1014                         if (meta[j / 8] & (1 << (j % 8)))
1015                                 total++;
1016
1017                 printf("  %u: %u/%u (%u%% density)\n",
1018                        uc->size[j], total, SUBPAGE_METAOFF / uc->size[i],
1019                        (total * 100) / (SUBPAGE_METAOFF / uc->size[i]));
1020         }
1021
1022         memset(count, 0, sizeof(count));
1023         for (i = 0; i < poolsize / getpagesize(); i++)
1024                 count[get_page_state(pool, i)]++;
1025
1026         mh = first_mheader(pool, poolsize);
1027         pagebitlen = (uint8_t *)mh - get_page_statebits(pool);
1028         fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
1029                 pagebitlen, count[0], count[1], count[2], count[3]);
1030
1031         /* One metadata page for every page of page bits. */
1032         metadata_pages = div_up(pagebitlen, getpagesize());
1033
1034         /* Now do each metadata page. */
1035         for (; mh; mh = next_mheader(pool,mh)) {
1036                 unsigned long free = 0, bitmapblocks = 0, uniformblocks = 0,
1037                         len = 0, uniformlen = 0, bitmaplen = 0, metalen;
1038                 uint8_t *meta = (uint8_t *)(mh + 1);
1039
1040                 metalen = get_metalen(pool, poolsize, mh);
1041                 metadata_pages += (sizeof(*mh) + metalen) / getpagesize();
1042
1043                 for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
1044                         switch (get_bit_pair(meta, i)) {
1045                         case FREE:
1046                                 len = 1;
1047                                 free++;
1048                                 break;
1049                         case BITMAP:
1050                                 /* Skip over this allocated part. */
1051                                 len = BITMAP_METALEN * CHAR_BIT;
1052                                 bitmapblocks++;
1053                                 bitmaplen += len;
1054                                 break;
1055                         case UNIFORM:
1056                                 /* Skip over this part. */
1057                                 len = decode_usize(meta + i/METADATA_PER_BYTE);
1058                                 len = uniform_metalen(len) * METADATA_PER_BYTE;
1059                                 uniformblocks++;
1060                                 uniformlen += len;
1061                                 break;
1062                         default:
1063                                 assert(0);
1064                         }
1065                 }
1066
1067                 fprintf(out, "Metadata %lu-%lu: %lu free, %lu bitmapblocks, %lu uniformblocks, %lu%% density\n",
1068                         pool_offset(pool, mh),
1069                         pool_offset(pool, (char *)(mh+1) + metalen),
1070                         free, bitmapblocks, uniformblocks,
1071                         (bitmaplen + uniformlen) * 100
1072                         / (free + bitmaplen + uniformlen));
1073         }
1074
1075         /* Account for total pages allocated. */
1076         tot = (count[1] + count[2] - metadata_pages) * getpagesize();
1077
1078         fprintf(out, "Total metadata bytes = %lu\n",
1079                 metadata_pages * getpagesize());
1080
1081         /* Now do every subpage. */
1082         for (i = 0; i < poolsize / getpagesize(); i++) {
1083                 uint8_t *meta;
1084                 unsigned int j, allocated;
1085                 enum sub_metadata_type type;
1086
1087                 if (get_page_state(pool, i) != SPECIAL)
1088                         continue;
1089
1090                 memset(count, 0, sizeof(count));
1091
1092                 meta = get_page_metadata(pool, i);
1093                 type = get_bit_pair(meta, 0);
1094
1095                 if (type == BITMAP) {
1096                         for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
1097                                 count[get_page_state(meta, j)]++;
1098                         allocated = (count[1] + count[2]) * BITMAP_GRANULARITY;
1099                         fprintf(out, "Subpage bitmap ");
1100                 } else {
1101                         unsigned int usize = decode_usize(meta);
1102
1103                         assert(type == UNIFORM);
1104                         fprintf(out, "Subpage uniform (%u) ", usize);
1105                         meta += 2;
1106                         for (j = 0; j < SUBPAGE_METAOFF / usize; j++)
1107                                 count[!!(meta[j / 8] & (1 << (j % 8)))]++;
1108                         allocated = count[1] * usize;
1109                 }
1110                 fprintf(out, "%lu: FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %u%% density\n",
1111                         i, count[0], count[1], count[2],
1112                         allocated * 100 / getpagesize());
1113                 tot += allocated;
1114         }
1115
1116         /* This is optimistic, since we overalloc in several cases. */
1117         fprintf(out, "Best possible allocation density = %lu%%\n",
1118                 tot * 100 / poolsize);
1119 }