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);

}

/*

 * xbinheap should be protected by cache lock.

 */

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

{

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

        if (cache->flags & XCACHE_LRU_ARRAY){

                //cache->times[idx] = __sync_add_and_fetch(&cache->time, 1);

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

        } else if (cache->flags & XCACHE_LRU_HEAP) {

                if (ce->h != NoNode){

                        xbinheap_increasekey(&cache->binheap, ce->h, cache->time++);

                } else {

                        ce->h = xbinheap_insert(&cache->binheap, cache->time++, idx);

                        if (ce->h == NoNode){

                                XSEGLOG("BUG: Cannot insert to lru binary heap");

                        }

                }

        }

        //XSEGLOG("cache->times[%llu] = %llu", idx, cache->times[idx]);

}

/*

 * Proper precautions should be taken, when getting a cache entry.

 * There is a race with removal and finding lru cache entry.

 */

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

{

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

        __sync_add_and_fetch(&ce->ref, 1);

        __update_access_time(cache, idx);

}

/* put should be called with no locking */

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

{

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

        unsigned long ref = __sync_sub_and_fetch(&ce->ref, 1);

        if (!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 = 1;

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

        ce->name[XSEG_MAX_TARGETLEN] = 0;

        ce->h = NoNode;

        if (cache->ops.on_init)

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

                        return -1;

        return 0;

}

static xqindex __xcache_lru(struct xcache *cache)

{

        uint64_t min = -2;

        xqindex i, lru = Noneidx;

        struct xcache_entry *ce;

        if (cache->flags & XCACHE_LRU_ARRAY){

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

                        //XSEGLOG("cache->times[%llu] = %llu", i, cache->times[i]);

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

                                min = cache->times[i];

                                lru = i;

                        }

                }

                //XSEGLOG("Found lru cache->times[%llu] = %llu", lru, cache->times[lru]);

        } else if (cache->flags & XCACHE_LRU_HEAP) {

                lru = xbinheap_extract(&cache->binheap);

                if (lru == NoNode)

                        return Noneidx;

                ce = &cache->nodes[lru];

                ce->h = NoNode;

        }

        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;

}

/* after a succesfull call, the handler must be put */

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){

                //XSEGLOG("Couldn't delete cache entry(h: %llu, cache->nodes[h].priv: %p",

                //                h, cache->nodes[idx].priv);

                return r;

        }

        if (cache->flags & XCACHE_LRU_ARRAY)

                cache->times[idx] = XCACHE_LRU_MAX;

        else if (cache->flags & XCACHE_LRU_HEAP) {

                if (ce->h != NoNode) {

                        if (xbinheap_increasekey(&cache->binheap, ce->h, XCACHE_LRU_MAX) < 0){

                                XSEGLOG("BUG: cannot increase key to XCACHE_LRU_MAX");

                        }

                        if (xbinheap_extract(&cache->binheap) == NoNode){

                                XSEGLOG("BUG: cannot remove cache entry from lru");

                        }

                        ce->h = NoNode;

                }

        }

        //XSEGLOG("cache->times[%llu] = %llu", idx, cache->times[idx]);

        return 0;

}

/*

 * Inserts a new entry to cache or returns a diffrent entry with the same key

 * (name).

 * In either case, ref count on the returned entry, gets increased

 *

 */

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

                                        xcache_handler *lru_handler)

{

        int r;

        struct xcache_entry *ce;

        xqindex lru, idx, xqi;

        xhash_t *new;

        idx = (xqindex)h;

        ce = &cache->nodes[idx];

        *lru_handler = NoEntry;

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

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

                xcache_entry_get(cache, xqi);

                return xqi;

        }

        /* insert new entry to cache */

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 NoEntry;

                /* Cache entry is put when this function returns, without the

                 * cache lock held.

                 */

                goto retry;

        }

        if (r == -XHASH_ERESIZE){

                XSEGLOG("Rebuilding internal hash table");

                new = xhash_resize(cache->entries,

                                cache->entries->size_shift,

                                cache->entries->limit, NULL);

                if (!new)

                        return NoEntry;

                cache->entries = new;

                goto retry;

        }

        if (r >= 0){

                xcache_entry_get(cache, idx);

                *lru_handler = (xcache_handler)lru;

        }

        return ((r < 0) ? NoEntry : h);

}

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, uint32_t flags, void *priv)

{

        struct xcache_entry *ce;

        unsigned long i;

        xhashidx shift;

        /*

         * Here we choose a proper size for the hash table.

         * It must be able to contain at least xcache_size elements, before

         * returns an -EXHASH_RESIZE.

         * Thus it must be at least 3/2 * xcache_size (OK, the minimum power of

         * two that meets this requirement to be exact).

         *

         * By choosing a xhash size 8 times the minimum required, we drastically

         * decrease the number or xhash rebuilts required by xhash for

         * perfomance reasons, sacrificing a logical amount of memory.

         *

         */

        for (shift = 0; 3*xcache_size/2 >= (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;

        cache->flags = flags;

        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;

        }

        if (flags & XCACHE_LRU_ARRAY){

                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] = XCACHE_LRU_MAX; //so lru will never return a this 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);

                        if (!ce->priv)

                                return -1;

                }

        }

        if (flags & XCACHE_LRU_HEAP){

                if (xbinheap_init(&cache->binheap, xcache_size, XBINHEAP_MIN,NULL) < 0){

                return -1;

                }

        }

        return 0;

}

xcache_handler xcache_insert(struct xcache *cache, xcache_handler h)

{

        xcache_handler ret, lru = NoEntry;

        struct xcache_entry *new_ce, *evicted_ce;

        int r;

        xlock_acquire(&cache->lock, 1);

        ret = __xcache_insert(cache, h, &lru);

        xlock_release(&cache->lock);

        if (lru != NoEntry){

                //assert ret != h

                new_ce = &cache->nodes[h];

                evicted_ce = &cache->nodes[lru];

                r = cache->ops.on_evict(cache->priv, evicted_ce->priv, new_ce->priv);

                if (!r){

                        xcache_entry_put(cache, lru);

                }

        }

        return ret;

}

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);

        if (r >= 0)

                xcache_entry_put(cache, h);

        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);

                if (r >= 0)

                        xcache_entry_put(cache, xqi);

        } else {

                xlock_release(&cache->lock);

        }

        return r;

}

void xcache_put(struct xcache *cache, xcache_handler h)

{

        xqindex idx = (xqindex)h;

        //xlock_acquire(&cache->lock, 1);

        xcache_entry_put(cache, idx);

        //xlock_release(&cache->lock);

}

/*

 * Put all cache entries.

 * Does not free cache resources.

 * xcache_free should be called by the client when all entries are put.

 */

void xcache_close(struct xcache *cache)

{

        unsigned long i;

        struct xcache_entry *ce;

        xlock_acquire(&cache->lock, 1);

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

                if (cache->flags & XCACHE_LRU_ARRAY){

                        if (cache->times[i] == XCACHE_LRU_MAX)

                                continue;

                        xcache_entry_put(cache, (xqindex)i);

                } else if (cache->flags & XCACHE_LRU_HEAP) {

                        ce = &cache->nodes[i];

                        if (ce->h == NoNode)

                                continue;

                        xcache_entry_put(cache, (xqindex)i);

                }

        }

        xlock_release(&cache->lock);

}

void xcache_free(struct xcache *cache)

{

        if (cache->flags & XCACHE_LRU_HEAP){

                xbinheap_free(&cache->binheap);

        } else if (cache->flags & XCACHE_LRU_ARRAY){

                xtypes_free(cache->times);

        }

        xtypes_free(cache->nodes);

        xhash_free(cache->entries);

}

#ifdef __KERNEL__

#include <linux/module.h>

#include <xtypes/xcache_exports.h>

#endif