rcache_vma_tree.c

MPI stands for the Message Passing Interface. Written by the MPI Forum (a large committee comprising

        mca_rcache_vma_module_t* vma_rcache, unsigned char *base,
        unsigned char *bound)
{
    mca_rcache_vma_t *vma;
    mca_rcache_vma_reg_list_item_t *item;

    vma = ompi_rb_tree_find_with(&vma_rcache->rb_tree, base, 
            mca_rcache_vma_tree_node_compare_search);

    if(!vma)
        return NULL;
    
    item = (mca_rcache_vma_reg_list_item_t*)opal_list_get_first(&vma->reg_list);

    do {
        if(item->reg->bound >= bound)
            return item->reg;
        if(!(item->reg->flags & MCA_MPOOL_FLAGS_PERSIST))
            break;
        item = (mca_rcache_vma_reg_list_item_t*)opal_list_get_next(item);
    } while(item !=
            (mca_rcache_vma_reg_list_item_t*)opal_list_get_end(&vma->reg_list));

    return NULL;
}

static inline bool is_reg_in_array(ompi_pointer_array_t *regs, void *p)
{
    int i;

    for(i = 0; i < ompi_pointer_array_get_size(regs); i++) {
        if(ompi_pointer_array_get_item(regs, i) == p)
            return true;
    }

    return false;
}

int mca_rcache_vma_tree_find_all(
        mca_rcache_vma_module_t *vma_rcache, unsigned char *base,
        unsigned char *bound, ompi_pointer_array_t *regs)
{
    int cnt = 0;

    if(opal_list_get_size(&vma_rcache->vma_list) == 0)
        return cnt;

    do {
        mca_rcache_vma_t *vma;
        opal_list_item_t *item;
        vma = ompi_rb_tree_find_with(&vma_rcache->rb_tree, base,
                mca_rcache_vma_tree_node_compare_closest);

        if(NULL == vma) {
            /* base is bigger than any registered memory */
            base = bound + 1;
            continue;
        }

        if(base < (unsigned char*)vma->start) {
            base = (unsigned char*)vma->start;
            continue;
        }

        for(item = opal_list_get_first(&vma->reg_list);
                item != opal_list_get_end(&vma->reg_list);
                item = opal_list_get_next(item)) {
            mca_rcache_vma_reg_list_item_t *vma_item;
            vma_item = (mca_rcache_vma_reg_list_item_t*)item;
            if(is_reg_in_array(regs, (void*)vma_item->reg)) {
                continue;
            }
            ompi_pointer_array_add(regs, (void*)vma_item->reg);
            cnt++;
        }

        base = (unsigned char *)vma->end + 1;
    } while(bound >= base);

    return cnt;
}

static inline int mca_rcache_vma_can_insert(
        mca_rcache_vma_module_t *vma_rcache, size_t nbytes, size_t limit)
{
    if(0 == limit)
        return 1;

    if(vma_rcache->reg_cur_cache_size + nbytes <= limit)
        return 1;

    return 0;
}

static inline void mca_rcache_vma_update_byte_count(
        mca_rcache_vma_module_t* vma_rcache,
        size_t nbytes)
{
    vma_rcache->reg_cur_cache_size += nbytes;
}
        
int mca_rcache_vma_tree_insert(mca_rcache_vma_module_t* vma_rcache,
        mca_mpool_base_registration_t* reg, size_t limit)
{
    mca_rcache_vma_t *i;
    uintptr_t begin = (uintptr_t)reg->base, end = (uintptr_t)reg->bound;

    i = (mca_rcache_vma_t*)ompi_rb_tree_find_with(&vma_rcache->rb_tree,
            (void*)begin, mca_rcache_vma_tree_node_compare_closest);

    if(!i)
        i = (mca_rcache_vma_t*)opal_list_get_end(&vma_rcache->vma_list);

    while (begin <= end) {
        mca_rcache_vma_t *vma;

        if((mca_rcache_vma_t*)opal_list_get_end(&vma_rcache->vma_list) == i) {
            vma = NULL;
            if(mca_rcache_vma_can_insert(vma_rcache, end - begin + 1, limit))
                vma = mca_rcache_vma_new(vma_rcache, begin, end);

            if(!vma)
                goto remove;

            mca_rcache_vma_update_byte_count(vma_rcache, end - begin + 1);
           
            opal_list_append(&vma_rcache->vma_list, &vma->super);
            begin = vma->end + 1;
            mca_rcache_vma_add_reg(vma, reg);
        } else if(i->start > begin) {
            uintptr_t tend = (i->start <= end)?(i->start - 1):end;
            vma = NULL;
            if(mca_rcache_vma_can_insert(vma_rcache, tend - begin + 1, limit))
                vma = mca_rcache_vma_new(vma_rcache, begin, tend);

            if(!vma)
                goto remove;

            mca_rcache_vma_update_byte_count(vma_rcache, tend - begin + 1);

            /* insert before */
            opal_list_insert_pos(&vma_rcache->vma_list, &i->super, &vma->super);
            i = vma;
            begin = vma->end + 1;
            mca_rcache_vma_add_reg(vma, reg);
        } else if(i->start == begin) {
            if (i->end > end) {
                vma = mca_rcache_vma_new(vma_rcache, end+1, i->end);
                if(!vma)
                    goto remove;

                i->end = end;

                mca_rcache_vma_copy_reg_list(vma, i);

                /* add after */
                opal_list_insert_pos(&vma_rcache->vma_list,
                        opal_list_get_next(&i->super),
                        &vma->super);
                mca_rcache_vma_add_reg(i, reg);
                begin = end + 1;
            } else {
                mca_rcache_vma_add_reg(i, reg);
                begin = i->end + 1;
            }
        } else {
                vma = mca_rcache_vma_new(vma_rcache, begin, i->end);

                if(!vma)
                    goto remove;

                i->end = begin - 1;

                mca_rcache_vma_copy_reg_list(vma, i);

                /* add after */
                opal_list_insert_pos(&vma_rcache->vma_list,
                        opal_list_get_next(&i->super),
                        &vma->super);
        }

        i = (mca_rcache_vma_t*)opal_list_get_next(&i->super);
    }

    return OMPI_SUCCESS;

remove:
    mca_rcache_vma_tree_delete(vma_rcache, reg);
    return OMPI_ERR_TEMP_OUT_OF_RESOURCE;
}

/**
 * Function to remove previously memory from the tree without freeing it
 *
 * @param base pointer to the memory to free
 *
 * @retval OMPI_SUCCESS
 * @retval OMPI_ERR_BAD_PARAM if the passed base pointer was invalid
 */
int mca_rcache_vma_tree_delete(mca_rcache_vma_module_t* vma_rcache, 
                          mca_mpool_base_registration_t* reg)
{
    mca_rcache_vma_t *vma;

    vma = ompi_rb_tree_find_with(&vma_rcache->rb_tree, reg->base, 
            mca_rcache_vma_tree_node_compare_search);

    if(!vma)
        return OMPI_ERROR;

    while(vma != (mca_rcache_vma_t*)opal_list_get_end(&vma_rcache->vma_list)
            && vma->start <= (uintptr_t)reg->bound) {
        mca_rcache_vma_remove_reg(vma, reg);
        
        if(opal_list_is_empty(&vma->reg_list)) {
            mca_rcache_vma_t *next = (mca_rcache_vma_t*)opal_list_get_next(&vma->super);
            ompi_rb_tree_delete(&vma_rcache->rb_tree, vma);
            mca_rcache_vma_update_byte_count(vma_rcache,
                    vma->start - vma->end - 1);
            opal_list_remove_item(&vma_rcache->vma_list, &vma->super);
            mca_rcache_vma_destroy(vma);
            vma = next;
        } else {
            int merged;

            do {
                mca_rcache_vma_t *prev = NULL, *next = NULL;
                if(opal_list_get_begin(&vma_rcache->vma_list) != 
                        opal_list_get_prev(vma))
                    prev = (mca_rcache_vma_t*)opal_list_get_prev(vma);
                merged = 0;

                if(prev && vma->start == prev->end + 1 &&
                        mca_rcache_vma_compare_reg_lists(vma, prev)) {
                    prev->end = vma->end;
                    opal_list_remove_item(&vma_rcache->vma_list, &vma->super);
                    ompi_rb_tree_delete(&vma_rcache->rb_tree, vma);
                    mca_rcache_vma_destroy(vma);
                    vma = prev;
                    merged = 1;
                }
                if(opal_list_get_end(&vma_rcache->vma_list) != 
                        opal_list_get_next(vma))
                    next = (mca_rcache_vma_t*)opal_list_get_next(vma);

                if(next && vma->end + 1 == next->start &&
                        mca_rcache_vma_compare_reg_lists(vma, next)) {
                    vma->end = next->end;
                    opal_list_remove_item(&vma_rcache->vma_list, &next->super);
                    ompi_rb_tree_delete(&vma_rcache->rb_tree, next);
                    mca_rcache_vma_destroy(next);
                    merged = 1;
                }
            } while(merged);
            vma = (mca_rcache_vma_t*)opal_list_get_next(vma);
        }
    }
    return 0;
}