+static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
+ unsigned long size, unsigned long align)
+{
+ unsigned long i;
+ uint8_t *metadata;
+
+ /* Look for partial page. */
+ for (i = 0; i < poolsize / getpagesize(); i++) {
+ unsigned long ret;
+ if (get_page_state(pool, i) != SPECIAL)
+ continue;
+
+ ret = sub_page_alloc(pool, i, size, align);
+ if (ret)
+ return ret;
+ }
+
+ /* Create new SUBPAGE page. */
+ i = alloc_get_pages(pool, poolsize, 1, 1);
+ if (i == 0)
+ return 0;
+
+ /* Get metadata for page. */
+ metadata = new_metadata(pool, poolsize, BITMAP_METALEN);
+ if (!metadata) {
+ alloc_free_pages(pool, i);
+ return 0;
+ }
+
+ /* Actually, this is a subpage page now. */
+ set_page_state(pool, i, SPECIAL);
+
+ /* Set metadata pointer for page. */
+ set_page_metadata(pool, i, metadata);
+
+ /* Do allocation like normal */
+ return sub_page_alloc(pool, i, size, align);
+}
+
+/* Returns true if we cleaned any pages. */
+static bool clean_empty_subpages(void *pool, unsigned long poolsize)
+{
+ unsigned long i;
+ bool progress = false;
+
+ for (i = 0; i < poolsize/getpagesize(); i++) {
+ uint8_t *meta;
+ unsigned int j;
+ if (get_page_state(pool, i) != SPECIAL)
+ continue;
+
+ meta = get_page_metadata(pool, i);
+ for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
+ if (get_page_state(meta, j) != FREE)
+ break;
+
+ /* So, is this page totally empty? */
+ if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY) {
+ set_page_state(pool, i, FREE);
+ progress = true;
+ }
+ }
+ return progress;
+}
+
+/* Returns true if we cleaned any pages. */
+static bool clean_metadata(void *pool, unsigned long poolsize)
+{
+ struct metaheader *mh, *prev_mh = NULL;
+ bool progress = false;
+
+ for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+ uint8_t *meta;
+ long i;
+
+ meta = (uint8_t *)(mh + 1);
+ BUILD_ASSERT(FREE == 0);
+ for (i = mh->metalen - 1; i > 0; i--)
+ if (meta[i] != 0)
+ break;
+
+ /* Completely empty? */
+ if (prev_mh && i == mh->metalen) {
+ alloc_free_pages(pool,
+ pool_offset(pool, mh)/getpagesize());
+ prev_mh->next = mh->next;
+ mh = prev_mh;
+ progress = true;
+ } else {
+ uint8_t *p;
+
+ /* Some pages at end are free? */
+ for (p = (uint8_t *)(mh+1)+mh->metalen - getpagesize();
+ p > meta + i;
+ p -= getpagesize()) {
+ set_page_state(pool,
+ pool_offset(pool, p)
+ / getpagesize(),
+ FREE);
+ progress = true;
+ }
+ }
+ }
+
+ return progress;
+}
+
+void *alloc_get(void *pool, unsigned long poolsize,
+ unsigned long size, unsigned long align)
+{
+ bool subpage_clean = false, metadata_clean = false;
+ unsigned long ret;
+
+ if (poolsize < MIN_SIZE)
+ return NULL;
+
+again:
+ /* Sub-page allocations have an overhead of ~12%. */
+ if (size + size/8 >= getpagesize() || align >= getpagesize()) {
+ unsigned long pages = div_up(size, getpagesize());
+
+ ret = alloc_get_pages(pool, poolsize, pages, align)
+ * getpagesize();
+ } else
+ ret = alloc_sub_page(pool, poolsize, size, align);
+
+ if (ret != 0)
+ return (char *)pool + ret;
+
+ /* Allocation failed: garbage collection. */
+ if (!subpage_clean) {
+ subpage_clean = true;
+ if (clean_empty_subpages(pool, poolsize))
+ goto again;
+ }
+
+ if (!metadata_clean) {
+ metadata_clean = true;
+ if (clean_metadata(pool, poolsize))
+ goto again;
+ }
+
+ /* FIXME: Compact metadata? */
+ return NULL;
+}
+
+static void subpage_free(void *pool, unsigned long pagenum, void *free)
+{
+ unsigned long off = (unsigned long)free % getpagesize();
+ uint8_t *metadata;
+
+ assert(off < SUBPAGE_METAOFF);
+ assert(off % BITMAP_GRANULARITY == 0);
+
+ metadata = get_page_metadata(pool, pagenum);
+
+ off /= BITMAP_GRANULARITY;
+
+ set_page_state(metadata, off++, FREE);
+ while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
+ && get_page_state(metadata, off) == TAKEN)
+ set_page_state(metadata, off++, FREE);
+}
+
+void alloc_free(void *pool, unsigned long poolsize, void *free)
+{
+ unsigned long pagenum;
+ struct metaheader *mh;
+
+ if (!free)
+ return;
+
+ assert(poolsize >= MIN_SIZE);
+
+ mh = first_mheader(pool, poolsize);
+ assert((char *)free >= (char *)(mh + 1) + mh->metalen);
+ assert((char *)pool + poolsize > (char *)free);
+
+ pagenum = pool_offset(pool, free) / getpagesize();
+
+ if (get_page_state(pool, pagenum) == SPECIAL)
+ subpage_free(pool, pagenum, free);
+ else {
+ assert((unsigned long)free % getpagesize() == 0);
+ alloc_free_pages(pool, pagenum);
+ }
+}
+
+static bool is_metadata_page(void *pool, unsigned long poolsize,
+ unsigned long page)
+{
+ struct metaheader *mh;
+
+ for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+ unsigned long start, end;
+
+ start = pool_offset(pool, mh);
+ end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
+ if (page >= start/getpagesize() && page < end/getpagesize())
+ return true;
+ }
+ return false;
+}
+
+static bool check_subpage(void *pool, unsigned long poolsize,
+ unsigned long page)
+{
+ unsigned long *mhoff = metadata_off(pool, page);
+ unsigned int i;
+ enum alloc_state last_state = FREE;
+
+ if (*mhoff + sizeof(struct metaheader) > poolsize)
+ return false;
+
+ if (*mhoff % ALIGNOF(struct metaheader) != 0)
+ return false;
+
+ /* It must point to a metadata page. */
+ if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
+ return false;
+
+ /* Marker at end of subpage allocation is "taken" */
+ if (get_bit_pair((uint8_t *)pool + *mhoff,
+ getpagesize()/BITMAP_GRANULARITY - 1) != TAKEN)
+ return false;
+
+ for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
+ enum alloc_state state;
+
+ state = get_bit_pair((uint8_t *)pool + *mhoff, i);
+ switch (state) {
+ case SPECIAL:
+ return false;
+ case TAKEN:
+ if (last_state == FREE)
+ return false;
+ break;
+ default:
+ break;
+ }
+ last_state = state;
+ }
+ return true;
+}
+