+static bool huge_allocated(struct header *head, unsigned long offset)
+{
+ unsigned long i;
+ struct huge_alloc *ha;
+
+ for (i = head->huge; i; i = ha->next) {
+ ha = (void *)((char *)head + i);
+ if (ha->off <= offset && ha->off + ha->len > offset)
+ return true;
+ }
+ return false;
+}
+
+/* They want something really big. Aim for contiguous pages (slow). */
+static COLD_ATTRIBUTE
+void *huge_alloc(void *pool, unsigned long poolsize,
+ unsigned long size, unsigned long align)
+{
+ struct header *head = pool;
+ struct huge_alloc *ha;
+ unsigned long i, sp_bits, lp_bits, num, header_size;
+
+ sp_bits = small_page_bits(poolsize);
+ lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;
+
+ /* Allocate tracking structure optimistically. */
+ ha = alloc_get(pool, poolsize, sizeof(*ha), ALIGNOF(*ha));
+ if (!ha)
+ return NULL;
+
+ /* First search for contiguous small pages... */
+ header_size = sizeof(*head) + sizeof(head->bs) * (max_bucket(lp_bits)-1);
+
+ num = 0;
+ for (i = (header_size + (1 << sp_bits) - 1) >> sp_bits;
+ i << sp_bits < poolsize;
+ i++) {
+ struct page_header *pg;
+ unsigned long off = (i << sp_bits);
+
+ /* Skip over large pages. */
+ if (test_bit(head->pagesize, i >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
+ i += (1 << BITS_FROM_SMALL_TO_LARGE_PAGE)-1;
+ continue;
+ }
+
+ /* Does this page meet alignment requirements? */
+ if (!num && off % align != 0)
+ continue;
+
+ /* FIXME: This makes us O(n^2). */
+ if (huge_allocated(head, off)) {
+ num = 0;
+ continue;
+ }
+
+ pg = (struct page_header *)((char *)head + off);
+ if (pg->elements_used) {
+ num = 0;
+ continue;
+ }
+
+ num++;
+ if (num << sp_bits >= size) {
+ unsigned long pgnum;
+
+ /* Remove from free list. */
+ for (pgnum = i; pgnum > i - num; pgnum--) {
+ pg = from_pgnum(head, pgnum, sp_bits);
+ del_from_list(head,
+ &head->small_free_list,
+ pg, sp_bits);
+ }
+ ha->off = (i - num + 1) << sp_bits;
+ ha->len = num << sp_bits;
+ goto done;
+ }
+ }
+
+ /* Now search for large pages... */
+ recombine_small_pages(head, poolsize, sp_bits);
+
+ num = 0;
+ for (i = (header_size + (1 << lp_bits) - 1) >> lp_bits;
+ (i << lp_bits) < poolsize; i++) {
+ struct page_header *pg;
+ unsigned long off = (i << lp_bits);
+
+ /* Ignore small pages. */
+ if (!test_bit(head->pagesize, i))
+ continue;
+
+ /* Does this page meet alignment requirements? */
+ if (!num && off % align != 0)
+ continue;
+
+ /* FIXME: This makes us O(n^2). */
+ if (huge_allocated(head, off)) {
+ num = 0;
+ continue;
+ }
+
+ pg = (struct page_header *)((char *)head + off);
+ if (pg->elements_used) {
+ num = 0;
+ continue;
+ }
+
+ num++;
+ if (num << lp_bits >= size) {
+ unsigned long pgnum;
+
+ /* Remove from free list. */
+ for (pgnum = i; pgnum > i - num; pgnum--) {
+ pg = from_pgnum(head, pgnum, lp_bits);
+ del_from_list(head,
+ &head->large_free_list,
+ pg, sp_bits);
+ }
+ ha->off = (i - num + 1) << lp_bits;
+ ha->len = num << lp_bits;
+ goto done;
+ }
+ }
+
+ /* Unable to satisfy: free huge alloc structure. */
+ alloc_free(pool, poolsize, ha);
+ return NULL;
+
+done:
+ add_to_huge_list(pool, ha);
+ return (char *)pool + ha->off;
+}
+
+static COLD_ATTRIBUTE void
+huge_free(struct header *head, unsigned long poolsize, void *free)
+{
+ unsigned long i, off, pgnum, free_off = (char *)free - (char *)head;
+ unsigned int sp_bits, lp_bits;
+ struct huge_alloc *ha;
+
+ for (i = head->huge; i; i = ha->next) {
+ ha = (void *)((char *)head + i);
+ if (free_off == ha->off)
+ break;
+ }
+ assert(i);
+
+ /* Free up all the pages, delete and free ha */
+ sp_bits = small_page_bits(poolsize);
+ lp_bits = sp_bits + BITS_FROM_SMALL_TO_LARGE_PAGE;
+ pgnum = free_off >> sp_bits;
+
+ if (test_bit(head->pagesize, pgnum >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
+ for (off = ha->off; off < ha->off + ha->len; off += 1 << lp_bits) {
+ add_large_page_to_freelist(head,
+ (void *)((char *)head + off),
+ sp_bits);
+ }
+ } else {
+ for (off = ha->off; off < ha->off + ha->len; off += 1 << sp_bits) {
+ add_small_page_to_freelist(head,
+ (void *)((char *)head + off),
+ sp_bits);
+ }
+ }
+ del_from_huge(head, ha);
+ alloc_free(head, poolsize, ha);
+}
+
+static COLD_ATTRIBUTE unsigned long
+huge_size(struct header *head, void *p)
+{
+ unsigned long i, off = (char *)p - (char *)head;
+ struct huge_alloc *ha;
+
+ for (i = head->huge; i; i = ha->next) {
+ ha = (void *)((char *)head + i);
+ if (off == ha->off) {
+ return ha->len;
+ }
+ }
+ abort();
+}
+