Archipelago

/*

 * Copyright 2013 GRNET S.A. All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or

 * without modification, are permitted provided that the following

 * conditions are met:

 *

 *   1. Redistributions of source code must retain the above

 *      copyright notice, this list of conditions and the following

 *      disclaimer.

 *   2. Redistributions in binary form must reproduce the above

 *      copyright notice, this list of conditions and the following

 *      disclaimer in the documentation and/or other materials

 *      provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS

 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF

 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED

 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN

 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

 * POSSIBILITY OF SUCH DAMAGE.

 *

 * The views and conclusions contained in the software and

 * documentation are those of the authors and should not be

 * interpreted as representing official policies, either expressed

 * or implied, of GRNET S.A.

 */

#include <xtypes/xcache.h>

//TODO container aware and xptrs

/*

static struct xcache_entry * get_cache_entry(struct xcache *cache, xqindex idx)

{

   return &cache->entries[idx];

}

*/

static xqindex __get_cache_idx(struct xcache *cache, struct xcache_entry *ce)

{

        return (xqindex)(ce - cache->nodes);

}

static xqindex __alloc_cache_entry(struct xcache *cache)

{

        return __xq_pop_head(&cache->free_nodes);

}

static xqindex alloc_cache_entry(struct xcache *cache)

{

        return xq_pop_head(&cache->free_nodes, 1);

}

static void __free_cache_entry(struct xcache *cache, xqindex idx)

{

        __xq_append_head(&cache->free_nodes, idx);

}

static void free_cache_entry(struct xcache *cache, xqindex idx)

{

        xq_append_head(&cache->free_nodes, idx, 1);

}

static void xcache_entry_get(struct xcache *cache, xqindex idx)

{

        struct xcache_entry *ce = &cache->nodes[idx];

        ce->ref++;

        cache->times[idx] = cache->time++;

}

static void xcache_entry_put(struct xcache *cache, xqindex idx)

{

        struct xcache_entry *ce = &cache->nodes[idx];

        ce->ref--;

        if (!ce->ref){

                if (cache->ops.on_put)

                        cache->ops.on_put(cache->priv, ce->priv);

                free_cache_entry(cache, idx);

        }

}

static int xcache_entry_init(struct xcache *cache, xqindex idx, char *name)

{

        struct xcache_entry *ce = &cache->nodes[idx];

        xlock_release(&ce->lock);

        ce->ref = 0;

        strncpy(ce->name, name, XSEG_MAX_TARGETLEN);

        ce->name[XSEG_MAX_TARGETLEN] = 0;

        if (cache->ops.on_init)

                if (cache->ops.on_init(cache->priv, ce->priv) < 0)

                        return -1;

        xcache_entry_get(cache, idx);

        return 0;

}

static xqindex __xcache_lru(struct xcache *cache)

{

        uint64_t min = -2;

        xqindex i, lru = Noneidx;

        for (i = 0; i < cache->nr_nodes; i++) {

                if (min > cache->times[i]){

                        min = cache->times[i];

                        lru = i;

                }

        }

        return lru;

}

static xqindex __xcache_lookup(struct xcache *cache, char *name)

{

        xqindex xqi = Noneidx;

        if (xhash_lookup(cache->entries, (xhashidx)name, &xqi) < 0){

                return Noneidx;

        }

        xcache_entry_get(cache, xqi);

        return xqi;

}

static int __xcache_remove(struct xcache *cache, xcache_handler h)

{

        int r;

        xqindex idx = (xqindex)h;

        struct xcache_entry *ce = &cache->nodes[idx];

        r = xhash_delete(cache->entries, (xhashidx)ce->name);

        if (r < 0)

                return r;

        //put here, so the last one holding a ref to the entry will

        //free the node

        cache->times[idx] = -1;

        xcache_entry_put(cache, idx);

        return 0;

}

static int __xcache_insert(struct xcache *cache, xcache_handler h)

{

        int r;

        struct xcache_entry *ce;

        xqindex lru, idx;

        idx = (xqindex)h;

        ce = &cache->nodes[idx];

        //TODO lookup first to ensure we don't overwrite entries

retry:

        r = xhash_insert(cache->entries, (xhashidx)ce->name, idx);

        if (r == -XHASH_ENOSPC){

                lru = __xcache_lru(cache);

                //assert lru != Noneidx

                //validate lru

                if (__xcache_remove(cache, lru) < 0)

                        return -1;

                goto retry;

        }

        if (r == -XHASH_ERESIZE){

                xhash_t *new = xhash_resize(cache->entries,

                                cache->entries->size_shift,

                                cache->entries->limit, NULL);

                if (!new)

                        return -1;

                cache->entries = new;

                goto retry;

        }

        return r;

}

xcache_handler xcache_lookup(struct xcache *cache, char *name)

{

        xqindex xqi = Noneidx;

        xlock_acquire(&cache->lock, 1);

        xqi = __xcache_lookup(cache, name);

        xlock_release(&cache->lock);

        return (xcache_handler)xqi;

}

xcache_handler xcache_alloc_init(struct xcache *cache, char *name)

{

        xqindex idx = alloc_cache_entry(cache);

        if (idx == Noneidx)

                return idx;

        if (xcache_entry_init(cache, idx, name) < 0){

                free_cache_entry(cache, idx);

                idx = Noneidx;

        }

        return (xcache_handler)idx;

}

int xcache_init(struct xcache *cache, uint32_t xcache_size,

                struct xcache_ops *ops, void *priv)

{

        struct xcache_entry *ce;

        unsigned long i;

        xhashidx shift;

        /*TODO: Document why this is needed*/

        for (shift = 0; xcache_size > (1UL << shift); shift++) {}

        shift += 3;

        xlock_release(&cache->lock);

        cache->size = xcache_size;

        cache->nr_nodes = cache->size * 2;

        cache->time = 0;

        cache->ops = *ops;

        cache->priv = priv;

        if (!xq_alloc_seq(&cache->free_nodes, cache->nr_nodes,

                                cache->nr_nodes)){

                return -1;

        }

        cache->entries = xhash_new(shift, xcache_size, STRING);

        if (!cache->entries){

                return -1;

        }

        cache->nodes = xtypes_malloc(cache->nr_nodes *

                                                                        sizeof(struct xcache_entry));

        if (!cache->nodes){

                return -1;

        }

        cache->times = xtypes_malloc(cache->nr_nodes * sizeof(uint64_t));

        if (!cache->times){

                return -1;

        }

        for (i = 0; i < cache->nr_nodes; i++) {

                cache->times[i] = -1; //so lru will never return a -1 value;

        }

        if (cache->ops.on_node_init){

                for (i = 0; i < cache->nr_nodes; i++) {

                        ce = &cache->nodes[i];

                        ce->priv = cache->ops.on_node_init(cache->priv);

                }

        }

        return 0;

}

int xcache_insert(struct xcache *cache, xcache_handler h)

{

        int r;

        xlock_acquire(&cache->lock, 1);

        r = __xcache_insert(cache, h);

        xlock_release(&cache->lock);

        return r;

}

int xcache_remove(struct xcache *cache, xcache_handler h)

{

        int r;

        xlock_acquire(&cache->lock, 1);

        r = __xcache_remove(cache, h);

        xlock_release(&cache->lock);

        return r;

}

int xcache_invalidate(struct xcache *cache, char *name)

{

        xqindex xqi;

        int r = 0;

        xlock_acquire(&cache->lock, 1);

        if (xhash_lookup(cache->entries, (xhashidx)name, &xqi) >= 0){

                //validate xqi

                r =__xcache_remove(cache, xqi);

        }

        xlock_release(&cache->lock);

        return r;

}

void xcache_put(struct xcache *cache, xcache_handler h)

{

        xqindex idx = (xqindex)h;

        xcache_entry_put(cache, h);

}

void xcache_close(struct xcache *cache)

{

        return;

}

#ifdef __KERNEL__

#include <linux/module.h>

#include <xtypes/xcache_exports.h>

#endif