#ifdef VMAP_VIRT_START

#include <xen/bitmap.h>

#include <xen/cache.h>

#include <xen/init.h>

#include <xen/mm.h>

#include <xen/pfn.h>

#include <xen/spinlock.h>

#include <xen/types.h>

#include <xen/vmap.h>

#include <asm/page.h>

static DEFINE_SPINLOCK(vm_lock);

static void *__read_mostly vm_base[VMAP_REGION_NR];

#define vm_bitmap(x) ((unsigned long *)vm_base[x])

/* highest allocated bit in the bitmap */

static unsigned int __read_mostly vm_top[VMAP_REGION_NR];

/* total number of bits in the bitmap */

static unsigned int __read_mostly vm_end[VMAP_REGION_NR];

/* lowest known clear bit in the bitmap */

static unsigned int vm_low[VMAP_REGION_NR];

void __init vm_init_type(enum vmap_region type, void *start, void *end)

{

    unsigned int i, nr;

    unsigned long va;

    ASSERT(!vm_base[type]);

    vm_base[type] = start;

    vm_end[type] = PFN_DOWN(end - start);

    vm_low[type]= PFN_UP((vm_end[type] + 7) / 8);

    nr = PFN_UP((vm_low[type] + 7) / 8);

    vm_top[type] = nr * PAGE_SIZE * 8;

    for ( i = 0, va = (unsigned long)vm_bitmap(type); i < nr; ++i, va += PAGE_SIZE )

    {

        struct page_info *pg = alloc_domheap_page(NULL, 0);

        map_pages_to_xen(va, page_to_mfn(pg), 1, PAGE_HYPERVISOR);

        clear_page((void *)va);

    }

    bitmap_fill(vm_bitmap(type), vm_low[type]);

    /* Populate page tables for the bitmap if necessary. */

    populate_pt_range(va, 0, vm_low[type] - nr);

}

static void *vm_alloc(unsigned int nr, unsigned int align,

                      enum vmap_region t)

{

    unsigned int start, bit;

    if ( !align )

        align = 1;

    else if ( align & (align - 1) )

        align &= -align;

    ASSERT((t >= VMAP_DEFAULT) && (t < VMAP_REGION_NR));

    if ( !vm_base[t] )

        return NULL;

    spin_lock(&vm_lock);

    for ( ; ; )

    {

        struct page_info *pg;

        ASSERT(vm_low[t] == vm_top[t] || !test_bit(vm_low[t], vm_bitmap(t)));

        for ( start = vm_low[t]; start < vm_top[t]; )

        {

            bit = find_next_bit(vm_bitmap(t), vm_top[t], start + 1);

            if ( bit > vm_top[t] )

                bit = vm_top[t];

            /*

             * Note that this skips the first bit, making the

             * corresponding page a guard one.

             */

            start = (start + align) & ~(align - 1);

            if ( bit < vm_top[t] )

            {

                if ( start + nr < bit )

                    break;

                start = find_next_zero_bit(vm_bitmap(t), vm_top[t], bit + 1);

            }

            else

            {

                if ( start + nr <= bit )

                    break;

                start = bit;

            }

        }

        if ( start < vm_top[t] )

            break;

        spin_unlock(&vm_lock);

        if ( vm_top[t] >= vm_end[t] )

            return NULL;

        pg = alloc_domheap_page(NULL, 0);

        if ( !pg )

            return NULL;

        spin_lock(&vm_lock);

        if ( start >= vm_top[t] )

        {

            unsigned long va = (unsigned long)vm_bitmap(t) + vm_top[t] / 8;

            if ( !map_pages_to_xen(va, page_to_mfn(pg), 1, PAGE_HYPERVISOR) )

            {

                clear_page((void *)va);

                vm_top[t] += PAGE_SIZE * 8;

                if ( vm_top[t] > vm_end[t] )

                    vm_top[t] = vm_end[t];

                continue;

            }

        }

        free_domheap_page(pg);

        if ( start >= vm_top[t] )

        {

            spin_unlock(&vm_lock);

            return NULL;

        }

    }

    for ( bit = start; bit < start + nr; ++bit )

        __set_bit(bit, vm_bitmap(t));

    if ( bit < vm_top[t] )

        ASSERT(!test_bit(bit, vm_bitmap(t)));

    else

        ASSERT(bit == vm_top[t]);

    if ( start <= vm_low[t] + 2 )

        vm_low[t] = bit;

    spin_unlock(&vm_lock);

    return vm_base[t] + start * PAGE_SIZE;

}

static unsigned int vm_index(const void *va, enum vmap_region type)

{

    unsigned long addr = (unsigned long)va & ~(PAGE_SIZE - 1);

    unsigned int idx;

    unsigned long start = (unsigned long)vm_base[type];

    if ( !start )

        return 0;

    if ( addr < start + (vm_end[type] / 8) ||

         addr >= start + vm_top[type] * PAGE_SIZE )

        return 0;

    idx = PFN_DOWN(va - vm_base[type]);

    return !test_bit(idx - 1, vm_bitmap(type)) &&

           test_bit(idx, vm_bitmap(type)) ? idx : 0;

}

static unsigned int vm_size(const void *va, enum vmap_region type)

{

    unsigned int start = vm_index(va, type), end;

    if ( !start )

        return 0;

    end = find_next_zero_bit(vm_bitmap(type), vm_top[type], start + 1);

    return min(end, vm_top[type]) - start;

}

static void vm_free(const void *va)

{

    enum vmap_region type = VMAP_DEFAULT;

    unsigned int bit = vm_index(va, type);

    if ( !bit )

    {

        type = VMAP_XEN;

        bit = vm_index(va, type);

    }

    if ( !bit )

    {

        WARN_ON(va != NULL);

        return;

    }

    spin_lock(&vm_lock);

    if ( bit < vm_low[type] )

    {

        vm_low[type] = bit - 1;

        while ( !test_bit(vm_low[type] - 1, vm_bitmap(type)) )

            --vm_low[type];

    }

    while ( __test_and_clear_bit(bit, vm_bitmap(type)) )

        if ( ++bit == vm_top[type] )

            break;

    spin_unlock(&vm_lock);

}

void *__vmap(const mfn_t *mfn, unsigned int granularity,

             unsigned int nr, unsigned int align, unsigned int flags,

             enum vmap_region type)

{

    void *va = vm_alloc(nr * granularity, align, type);

    unsigned long cur = (unsigned long)va;

    for ( ; va && nr--; ++mfn, cur += PAGE_SIZE * granularity )

    {

        if ( map_pages_to_xen(cur, mfn_x(*mfn), granularity, flags) )

        {

            vunmap(va);

            va = NULL;

        }

    }

    return va;

}

void *vmap(const mfn_t *mfn, unsigned int nr)

{

    return __vmap(mfn, 1, nr, 1, PAGE_HYPERVISOR, VMAP_DEFAULT);

}

void vunmap(const void *va)

{

    unsigned long addr = (unsigned long)va;

    unsigned int pages = vm_size(va, VMAP_DEFAULT);

    if ( !pages )

        pages = vm_size(va, VMAP_XEN);

#ifndef _PAGE_NONE

    destroy_xen_mappings(addr, addr + PAGE_SIZE * pages);

#else /* Avoid tearing down intermediate page tables. */

    map_pages_to_xen(addr, 0, pages, _PAGE_NONE);

#endif

    vm_free(va);

}

static void *vmalloc_type(size_t size, enum vmap_region type)

{

    mfn_t *mfn;

    size_t pages, i;

    struct page_info *pg;

    void *va;

    ASSERT(size);

    pages = PFN_UP(size);

    mfn = xmalloc_array(mfn_t, pages);

    if ( mfn == NULL )

        return NULL;

    for ( i = 0; i < pages; i++ )

    {

        pg = alloc_domheap_page(NULL, 0);

        if ( pg == NULL )

            goto error;

        mfn[i] = _mfn(page_to_mfn(pg));

    }

    va = __vmap(mfn, 1, pages, 1, PAGE_HYPERVISOR, type);

    if ( va == NULL )

        goto error;

    xfree(mfn);

    return va;

 error:

    while ( i-- )

        free_domheap_page(mfn_to_page(mfn_x(mfn[i])));

    xfree(mfn);

    return NULL;

}

void *vmalloc(size_t size)

{

    return vmalloc_type(size, VMAP_DEFAULT);

}

void *vmalloc_xen(size_t size)

{

    return vmalloc_type(size, VMAP_XEN);

}

void *vzalloc(size_t size)

{

    void *p = vmalloc_type(size, VMAP_DEFAULT);

    int i;

    if ( p == NULL )

        return NULL;

    for ( i = 0; i < size; i += PAGE_SIZE )

        clear_page(p + i);

    return p;

}

void vfree(void *va)

{

    unsigned int i, pages;

    struct page_info *pg;

    PAGE_LIST_HEAD(pg_list);

    enum vmap_region type = VMAP_DEFAULT;

    if ( !va )

        return;

    pages = vm_size(va, type);

    if ( !pages )

    {

        type = VMAP_XEN;

        pages = vm_size(va, type);

    }

    ASSERT(pages);

    for ( i = 0; i < pages; i++ )

    {

        struct page_info *page = vmap_to_page(va + i * PAGE_SIZE);

        ASSERT(page);

        page_list_add(page, &pg_list);

    }

    vunmap(va);

    while ( (pg = page_list_remove_head(&pg_list)) != NULL )

        free_domheap_page(pg);

}

#endif