struct xcache_entry *ce = &cache->nodes[idx];
int r = 0;
- do {
+ r = xhash_insert(*table, (xhashidx)ce->name, idx);
+ if (r == -XHASH_ERESIZE){
+ XSEGLOG("Rebuilding internal hash table");
+ new = xhash_resize(*table,
+ cache->rm_entries->size_shift,
+ cache->rm_entries->limit, NULL);
+ if (!new) {
+ XSEGLOG("Error resizing hash table");
+ return -1;
+ }
+ *table = new;
+
+ /* We give insertion a second shot */
r = xhash_insert(*table, (xhashidx)ce->name, idx);
- if (r == -XHASH_ERESIZE){
- XSEGLOG("Rebuilding internal hash table");
- new = xhash_resize(*table,
- cache->rm_entries->size_shift,
- cache->rm_entries->limit, NULL);
- if (!new) {
- XSEGLOG("Error resizing hash table");
- return -1;
- }
- *table = new;
+ if (r == -XHASH_ERESIZE) {
+ XSEGLOG("BUG: failed to insert entry after resize");
+ return -1;
}
- } while (r == -XHASH_ERESIZE);
+ }
return r;
}
return r;
}
-
-
-
static xqindex alloc_cache_entry(struct xcache *cache)
{
return xq_pop_head(&cache->free_nodes, 1);
}
/*
- * __xcache_entry_get_and_update must be called with cache->lock held, due to the race for
- * __update_access_time.
+ * __xcache_entry_get_and_update must be called with cache->lock held, due to
+ * the race for __update_access_time.
*/
static void __xcache_entry_get_and_update(struct xcache *cache, xqindex idx)
{
XSEGLOG("Couldn't delete cache entry from hash table:\n"
"h: %llu, name: %s, cache->nodes[h].priv: %p, ref: %llu",
h, ce->name, cache->nodes[idx].priv, cache->nodes[idx].ref);
- return r;
}
return r;
static xcache_handler __xcache_lookup_and_get_rm(struct xcache *cache, char *name)
{
xcache_handler h;
+
h = __xcache_lookup_rm(cache, name);
if (h != NoEntry){
__xcache_entry_get_and_update(cache, h);
}
+
return h;
}
static xcache_handler __xcache_lookup_and_get_entries(struct xcache *cache, char *name)
{
xcache_handler h;
+
h = __xcache_lookup_entries(cache, name);
if (h != NoEntry){
__xcache_entry_get_and_update(cache, h);
}
+
return h;
}
{
return __table_insert(&cache->entries, cache, h);
}
+
/*
* xcache_entry_put is thread-safe even without cache->lock (cache->rm_lock is
* crucial though). This is why:
if (ce->state == NODE_EVICTED) {
xlock_acquire(&cache->rm_lock, 1);
+ /*
+ * FIXME: BUG! Why? Say that on finalize has deemed that ce is clear.
+ * If we get descheduled before getting rm_lock and in the meantime, the
+ * cache entry is reinserted, dirtied and evicted? The ce->ref will be
+ * zero but we shouldn't leave since there are still dirty buckets.
+ */
if (ce->ref == 0)
r = __xcache_remove_rm(cache, idx);
+ else
+ r = -1;
xlock_release(&cache->rm_lock);
}
ce->name[XSEG_MAX_TARGETLEN] = 0;
ce->h = NoNode;
ce->state = NODE_ACTIVE;
+
if (cache->ops.on_init)
r = cache->ops.on_init(cache->priv, ce->priv);
+
return r;
}
{
//pre_evict
//remove from entries
- //insert to rm_entries
//post_evict
+ //insert to rm_entries
struct xcache_entry *ce;
int r;
+
r = __xcache_remove_entries(cache, h);
if (r < 0) {
XSEGLOG("Failed to evict %llu from entries", h);
* 2. Then, we search in "rm_entries", to check if the target has been removed.
* If so we update its ref and try to insert it in cache.
*
- * <if any of these steps fail, we return NoEntry. If the node is invalid, we
- * return DelEntry>
+ * <if any of these steps fail, we return NoEntry.>
*
* 3. We now have a valid handler, either the one we started with or the one we
* re-insert. We check if there is space for it in "entries". If no space
xlock_acquire(&cache->rm_lock, 1);
tmp_h = __xcache_lookup_rm(cache, ce->name);
if (tmp_h != NoEntry) {
+ /* if so then remove it from rm table */
r = __xcache_remove_rm(cache, tmp_h);
- if (r < 0) {
+ if (UNLIKELY(r < 0)) {
XSEGLOG("Could not remove found entry (%llu) for %s"
"from rm_entries", tmp_h, ce->name);
xlock_release(&cache->rm_lock);
return NoEntry;
}
+
+ /* and prepare it for reinsertion */
ce = &cache->nodes[tmp_h];
- //assert state = NODE_EVICTED
+ if (UNLIKELY(ce->state != NODE_EVICTED))
+ XSEGLOG("BUG: Entry (%llu) in rm table not in evicted state", tmp_h);
ce->state = NODE_ACTIVE;
- /* we need to 'get' entry with rm_lock */
- __xcache_entry_get_and_update(cache, tmp_h);
+
+ __xcache_entry_get(cache, tmp_h);
h = tmp_h;
*reinsert_handler = tmp_h;
}
if (r == -XHASH_ENOSPC){
lru = __xcache_evict_lru(cache);
if (UNLIKELY(lru == NoEntry)) {
- XSEGLOG("Failed to evict lru entry");
+ XSEGLOG("BUG: Failed to evict lru entry");
return NoEntry;
}
*lru_handler = lru;
+
/*
* Cache entry is put when this function returns, without the
* cache lock held.
return NoEntry;
}
}
- if (r >= 0) {
- if (h != tmp_h)
- __xcache_entry_get_and_update(cache, h);
- }
- return ((r < 0) ? NoEntry : h);
+ if (r >= 0)
+ __xcache_entry_get_and_update(cache, h);
+
+ return (r < 0 ? NoEntry : h);
}
/*
if (lru != NoEntry) {
if (UNLIKELY(ret == NoEntry))
XSEGLOG("BUG: Unsuccessful insertion lead to LRU eviction.");
- xcache_entry_put(cache, lru);
ce = &cache->nodes[lru];
if (cache->ops.on_evict)
cache->ops.on_evict(cache->priv, ce->priv);
+ xcache_entry_put(cache, lru);
}
if (reinsert_handler != NoEntry) {
}
/*
- * xcache_lookup looks only in "entries". The are several arguments behind this
- * choice:
+ * xcache_lookup looks only in "entries". There are several arguments behind
+ * this choice:
*
- * a. Speed: xcache_lookup won't bother with geting rm->lock or re-insert
+ * a. Speed: xcache_lookup won't bother with geting rm->lock or re-inserting
* entries in other hash tables this way.
* b. Common case: Rarely will we ever need to lookup in "rm_entries"
* c. Simplicity: <self-explanatory>
xcache_handler xcache_lookup(struct xcache *cache, char *name)
{
xcache_handler h = NoEntry;
+
xlock_acquire(&cache->lock, 1);
h = __xcache_lookup_and_get_entries(cache, name);
xlock_release(&cache->lock);
+
return h;
}
int r;
xcache_handler h;
xqindex idx = alloc_cache_entry(cache);
+
if (idx == Noneidx)
return NoEntry;
-// h = (xcache_handle)idx
+
r = xcache_entry_init(cache, idx, name);
if (r < 0){
free_cache_entry(cache, idx);
return NoEntry;
}
h = idx;
+
return h;
}
cache->priv = priv;
cache->flags = flags;
- /* TODO: assert cache->nodes isn't UINT64_MAX */
+ /* FIXME: If cache->size is UINT64_MAX then cache->nodes has overflowed */
+ if (cache->size == (uint64_t)(-1))
+ return -1;
if (!xq_alloc_seq(&cache->free_nodes, cache->nr_nodes,
cache->nr_nodes)){
for (i = 0; i < cache->nr_nodes; i++) {
ce = &cache->nodes[i];
ce->ref = 0;
+ /* FIXME: Is (void *) typecast necessary? */
ce->priv = cache->ops.on_node_init(cache->priv, (void *)&i);
if (!ce->priv)
goto out_free_times;
{
int r = 0;
xcache_handler h;
+
xlock_acquire(&cache->lock, 1);
xlock_acquire(&cache->rm_lock, 1);
-
h = __xcache_lookup_entries(cache, name);
if (h != NoEntry){
r = __xcache_remove_entries(cache, h);
r = __xcache_remove_rm(cache, h);
}
-out:
xlock_release(&cache->rm_lock);
xlock_release(&cache->lock);
xlock_release(&cache->rm_lock);
xlock_release(&cache->lock);
- if (r >=0)
+ if (r >= 0)
xcache_put(cache, h);
return r;
void xcache_get(struct xcache *cache, xcache_handler h)
{
xqindex idx = (xqindex)h;
- //xlock_acquire(&cache->lock, 1);
__xcache_entry_get(cache, idx);
- //xlock_release(&cache->lock);
}
/*
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);
}
/*
* xcache_free_new is called with no locking and will not hold any lock too.
* It must be called when an entry has not been inserted in cache (e.g. due to
* re-insertion) and we want to free it. In this case, the refcount can safely
- * drop manually to zero
+ * drop to zero
*/
void xcache_free_new(struct xcache *cache, xcache_handler h)
{
/*
* Called with out cache lock held:
*
- * on_init: called on cache entry initialization.
- * Should return negative on error to abort cache entry
- * initialization.
+ * on_init: called on cache entry initialization.
+ * Should return negative on error to abort cache entry
+ * initialization.
*
- * on_put: called when the last reference to the cache entry is put
+ * on_put: called when the last reference to the cache entry is put
*
- * on_evict: called when a cache entry is evicted. It is called with the old
- * cache entry that gets evicted and the new cache entry that
- * trigger the eviction as arguments.
- * Return value interpretation:
- * < 0 : Failure.
- * = 0 : Success. Finished with the old cache entry.
- * > 0 : Success. Pending actions on the old cache entry.
+ * on_evict: called when a cache entry is evicted. It is called with the old
+ * cache entry that gets evicted and the new cache entry that
+ * trigger the eviction as arguments.
+ * Return value interpretation:
+ * < 0 : Failure.
+ * = 0 : Success. Finished with the old cache entry.
+ * > 0 : Success. Pending actions on the old cache entry.
*
- * on_node_init: called on initial node preparation.
- * Must return NULL on error, to abort cache initialization.
- * post_evict: called after an eviction has occured, with cache lock held.
- * Must return 0 if there are no pending actions to the entry.
- * On non-zero value, user should get the entry which will be put
- * to the evicted table.
- * on_free: called when a cache entry is freed.
- * on_finalize: FILLME
- * Must return 0 if there are no pending actions to the entry.
- * On non-zero value, user should get the entry which will be put
- * to the evicted table.
+ * on_node_init:
+ * called on initial node preparation.
+ * Must return NULL on error, to abort cache initialization.
+ *
+ * post_evict: called after an eviction has occured, with cache lock held.
+ * Must return 0 if there are no pending actions to the entry.
+ * On non-zero value, user should get the entry which will be put
+ * to the evicted table.
+ *
+ * on_free: called when a cache entry is freed.
+ *
+ * on_finalize: FILLME
+ * Must return 0 if there are no pending actions to the entry.
+ * On non-zero value, user should get the entry which will be put
+ * to the evicted table.
*/
struct xcache_ops {
int (*on_init)(void *cache_data, void *user_data);
}
/*
- * Return a pointer to a the associated cache entry.
+ * Return a pointer to the associated cache entry.
*/
-static void * xcache_get_entry(struct xcache *cache, xcache_handler h)
+static void *xcache_get_entry(struct xcache *cache, xcache_handler h)
{
xqindex idx = (xqindex)h;
- //validate idx
+
if (!__validate_idx(cache, idx))
return NULL;
+
return cache->nodes[idx].priv;
}
* Return a pointer to a NULL terminated string holding the name of the
* associated cache entry.
*/
-static char * xcache_get_name(struct xcache *cache, xcache_handler h)
+static char *xcache_get_name(struct xcache *cache, xcache_handler h)
{
xqindex idx = (xqindex)h;
- //validate idx
+
if (!__validate_idx(cache, idx))
return NULL;
+
return cache->nodes[idx].name;
}