#include "moar.h"

/* Creates a new second generation allocator. */
MVMGen2Allocator * MVM_gc_gen2_create(MVMInstance *i) {
    /* Create allocator data structure. */
    MVMGen2Allocator *al = MVM_malloc(sizeof(MVMGen2Allocator));

    /* Create empty size classes array data structure. */
    al->size_classes = (MVMGen2SizeClass *)MVM_calloc(MVM_GEN2_BINS, sizeof(MVMGen2SizeClass));

    /* Set up overflows area. */
    al->alloc_overflows = MVM_GEN2_OVERFLOWS;
    al->num_overflows = 0;
    al->overflows = MVM_malloc(al->alloc_overflows * sizeof(MVMCollectable *));

    return al;
}

/* Sets up a size class bin in the second generation. */
static void setup_bin(MVMGen2Allocator *al, MVMuint32 bin) {
    /* Work out page size we want. */
    MVMuint32 page_size = MVM_GEN2_PAGE_ITEMS * ((bin + 1) << MVM_GEN2_BIN_BITS);

    /* We'll just allocate a single page to start off with. */
    al->size_classes[bin].num_pages = 1;
    al->size_classes[bin].pages     = MVM_malloc(sizeof(void *) * al->size_classes[bin].num_pages);
    al->size_classes[bin].pages[0]  = MVM_malloc(page_size);

    /* Set up allocation position and limit. */
    al->size_classes[bin].alloc_pos = al->size_classes[bin].pages[0];
    al->size_classes[bin].alloc_limit = al->size_classes[bin].alloc_pos + page_size;

    /* Free list is empty until GC run (and we just do page by page allocation). */
    al->size_classes[bin].free_list = NULL;
}

/* Adds a new page to a size class bin. */
static void add_page(MVMGen2Allocator *al, MVMuint32 bin) {
    /* Work out page size. */
    MVMuint32 page_size = MVM_GEN2_PAGE_ITEMS * ((bin + 1) << MVM_GEN2_BIN_BITS);

    /* Add the extra page. */
    MVMuint32 cur_page = al->size_classes[bin].num_pages;
    al->size_classes[bin].num_pages++;
    al->size_classes[bin].pages = MVM_realloc(al->size_classes[bin].pages,
        sizeof(void *) * al->size_classes[bin].num_pages);
    al->size_classes[bin].pages[cur_page] = MVM_malloc(page_size);

    /* Set up allocation position and limit. */
    al->size_classes[bin].alloc_pos = al->size_classes[bin].pages[cur_page];
    al->size_classes[bin].alloc_limit = al->size_classes[bin].alloc_pos + page_size;

    /* set the cur_page to a proper value */
    al->size_classes[bin].cur_page = cur_page;
}

/* Allocates space using the second generation allocator and returns
 * a pointer to the allocated space. Does not zero the space or set
 * it up in any way. */
void * MVM_gc_gen2_allocate(MVMGen2Allocator *al, MVMuint32 size) {
    void *result;

    /* Determine the bin. If we hit a bin exactly then it's off-by-one,
     * since the bins list is base-0. Otherwise we've some extra bits,
     * which round us up to the next bin, but that's a no-op. */
    MVMuint32 bin = (size >> MVM_GEN2_BIN_BITS);
    if ((size & MVM_GEN2_BIN_MASK) == 0)
        bin--;

    /* If the selected bin is in range... */
    if (bin < MVM_GEN2_BINS) {
        /* If we've no pages yet, never encountered this bin; set it up. */
        if (al->size_classes[bin].pages == NULL)
            setup_bin(al, bin);

        /* If there's a free list entry, use that. */
        if (al->size_classes[bin].free_list) {
            result = (void *)al->size_classes[bin].free_list;
            al->size_classes[bin].free_list = (char **)*(al->size_classes[bin].free_list);
        }
        else {
            /* If we're at the page limit, add a new page. */
            if (al->size_classes[bin].alloc_pos == al->size_classes[bin].alloc_limit)
                add_page(al, bin);

            /* Now we can allocate. */
            result = al->size_classes[bin].alloc_pos;
            al->size_classes[bin].alloc_pos += (bin + 1) << MVM_GEN2_BIN_BITS;
        }
    }
    else {
        /* We're beyond the size class bins, so resort to malloc. */
        result = MVM_malloc(size);

        /* Add to overflows list. */
        if (al->num_overflows == al->alloc_overflows) {
            al->alloc_overflows *= 2;
            al->overflows = MVM_realloc(al->overflows,
                al->alloc_overflows * sizeof(MVMCollectable *));
        }
        al->overflows[al->num_overflows++] = result;
    }

    return result;
}

/* Allocates space using the second generation allocator and returns
 * a pointer to the allocated space. Promises the memory will be
 * zeroed, except that the MVMCollectable gen 2 flag will get set. */
void * MVM_gc_gen2_allocate_zeroed(MVMGen2Allocator *al, MVMuint32 size) {
    void *a = MVM_gc_gen2_allocate(al, size);
    memset(a, 0, size);
    ((MVMCollectable *)a)->flags2 = MVM_CF_SECOND_GEN;
    return a;
}

/* Frees all memory associated with the second generation. */
void MVM_gc_gen2_destroy(MVMInstance *i, MVMGen2Allocator *al) {
    MVMuint32 j, k;

    /* Remove all pages. */
    for (j = 0; j < MVM_GEN2_BINS; j++) {
        for (k = 0; k < al->size_classes[j].num_pages; k++)
            MVM_free(al->size_classes[j].pages[k]);
        MVM_free(al->size_classes[j].pages);
    }

    /* Free any allocated overflows. */
    for (j = 0; j < al->num_overflows; j++)
        if (al->overflows[j])
            MVM_free(al->overflows[j]);

    /* Clean up allocator data structure. */
    MVM_free(al->size_classes);
    al->size_classes = NULL;
    MVM_free(al->overflows);
    al->overflows = NULL;
    MVM_free(al);
}

/* blindly move pages from one gen2 to another */
void MVM_gc_gen2_transfer(MVMThreadContext *src, MVMThreadContext *dest) {
    MVMGen2Allocator *gen2 = src->gen2, *dest_gen2 = dest->gen2;
    MVMuint32 bin, obj_size, page;
    char ***freelist_insert_pos;

    for (bin = 0; bin < MVM_GEN2_BINS; bin++) {
        MVMuint32 orig_dest_num_pages = dest_gen2->size_classes[bin].num_pages;
        char *cur_ptr, *end_ptr;
        /* If we've nothing allocated in this size class, skip it. */
        if (gen2->size_classes[bin].pages == NULL)
            continue;

        if (dest_gen2->size_classes[bin].pages == NULL)
            dest_gen2->size_classes[bin].free_list = NULL;

        /* Calculate object size for this bin. */
        obj_size = (bin + 1) << MVM_GEN2_BIN_BITS;

        /* freelist_insert_pos is a pointer to a memory location that
         * stores the address of the last traversed free list node (char **). */
        /* Initialize freelist insertion position to free list head. */
        freelist_insert_pos = &gen2->size_classes[bin].free_list;

        if (dest_gen2->size_classes[bin].pages == NULL) {
            dest_gen2->size_classes[bin].pages
                = MVM_malloc(sizeof(void *) * gen2->size_classes[bin].num_pages);
            dest_gen2->size_classes[bin].num_pages = gen2->size_classes[bin].num_pages;
        }
        else {
            dest_gen2->size_classes[bin].num_pages
                += gen2->size_classes[bin].num_pages;
            dest_gen2->size_classes[bin].pages
                = MVM_realloc(dest_gen2->size_classes[bin].pages,
                    sizeof(void *) * dest_gen2->size_classes[bin].num_pages);
        }

        /* Visit each page in the source. */
        for (page = 0; page < gen2->size_classes[bin].num_pages; page++) {
            /* Visit all the objects, looking for dead ones and swap the
             * owner for each of them. */
            cur_ptr = gen2->size_classes[bin].pages[page];
            end_ptr = page + 1 == gen2->size_classes[bin].num_pages
                ? gen2->size_classes[bin].alloc_pos
                : cur_ptr + obj_size * MVM_GEN2_PAGE_ITEMS;
            while (cur_ptr < end_ptr) {
                if (cur_ptr == (char *)freelist_insert_pos) {
                    /* skip */
                }
                else if (cur_ptr == (char *)*freelist_insert_pos) {
/*                    printf("found a free list slot in bin %d page %d: %d with value %d and start %d and limit %d\n",
                        bin, page, cur_ptr, *(void **)cur_ptr, gen2->size_classes[bin].pages[page],
                        dest_gen2->size_classes[bin].alloc_limit);*/
                    freelist_insert_pos = (char ***)cur_ptr;
                }
                else { /* note: we don't have tests that exercise this path yet. */
/*                    printf("updating an owner from %d to %d\n", ((MVMCollectable *)cur_ptr)->owner, dest->thread_id);*/
                    ((MVMCollectable *)cur_ptr)->owner = dest->thread_id;
                }

                /* Move to the next object. */
                cur_ptr += obj_size;
            }
            dest_gen2->size_classes[bin].pages[page + orig_dest_num_pages] = gen2->size_classes[bin].pages[page];
        }

        freelist_insert_pos = &dest_gen2->size_classes[bin].free_list;
        while (*freelist_insert_pos) {
            freelist_insert_pos = (char ***)*freelist_insert_pos;
        }
        /* chain the destination's freelist through any remaining unallocated area */
        if (dest_gen2->size_classes[bin].alloc_pos) {
            cur_ptr = dest_gen2->size_classes[bin].alloc_pos;
            end_ptr = dest_gen2->size_classes[bin].alloc_limit;
            while (cur_ptr < end_ptr) {
                *freelist_insert_pos = (char **)cur_ptr;
                freelist_insert_pos = (char ***)cur_ptr;
                cur_ptr += obj_size;
            }
        }

        /* link to the new pages, if any */
        *freelist_insert_pos = gen2->size_classes[bin].free_list;

        dest_gen2->size_classes[bin].alloc_pos = gen2->size_classes[bin].alloc_pos;
        dest_gen2->size_classes[bin].alloc_limit = gen2->size_classes[bin].alloc_limit;

        MVM_free(gen2->size_classes[bin].pages);
        gen2->size_classes[bin].pages = NULL;
        gen2->size_classes[bin].num_pages = 0;
    }
    { /* transfer the overflows */
        MVMuint32 i;
        if (gen2->num_overflows + dest_gen2->num_overflows > dest_gen2->alloc_overflows) {
            dest_gen2->alloc_overflows = (
                gen2->alloc_overflows > dest_gen2->alloc_overflows
                ? gen2->alloc_overflows
                : dest_gen2->alloc_overflows
            ) * 2; /* double the larger of the 2 sizes */
            dest_gen2->overflows = MVM_realloc(dest_gen2->overflows,
                dest_gen2->alloc_overflows * sizeof(MVMCollectable *));
        }
        for (i = 0; i < gen2->num_overflows; i++)
            gen2->overflows[i]->owner = dest->thread_id;
        memcpy(
            &dest_gen2->overflows[dest_gen2->num_overflows],
            gen2->overflows,
            gen2->num_overflows * sizeof(MVMCollectable *)
        );
        dest_gen2->num_overflows += gen2->num_overflows;

        gen2->num_overflows = 0;
        gen2->alloc_overflows = 0;
        MVM_free(gen2->overflows);
        gen2->overflows = NULL;
    }
    { /* copy the roots... */
        MVMuint32 i, n = src->num_gen2roots;
        for ( i = 0; i < n; i++) {
            MVM_gc_root_gen2_add(dest, src->gen2roots[i]);
        }
        src->num_gen2roots = 0;
        src->alloc_gen2roots = 0;
        MVM_free(src->gen2roots);
        src->gen2roots = NULL;
    }
}


void MVM_gc_gen2_compact_overflows(MVMGen2Allocator *al) {
    /* compact the overflow list to prevent it from growing without bounds */
    MVMCollectable **overflows     = al->overflows;
    const MVMuint32  num_overflows = al->num_overflows;
    MVMuint32        cursor = 0;
    MVMuint32        live;

    /* Find the first NULL object. */
    while (cursor < num_overflows && overflows[cursor])
        cursor++;
    live = cursor;

    /* Slide others back so the alive ones are at the start of the list. */
    while (cursor < num_overflows) {
        if (overflows[cursor]) {
            overflows[live++] = overflows[cursor];
        }
        cursor++;
    }

    al->num_overflows = live;
}