xcache.c 23.5 KB
Newer Older
1
/*
Filippos Giannakos's avatar
Filippos Giannakos committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15
Copyright (C) 2010-2014 GRNET S.A.

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
16 17
 */

18 19 20
#include <xseg/xcache.h>
#include <string.h>

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
//TODO container aware and xptrs

#if 0
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 void __free_cache_entry(struct xcache *cache, xqindex idx)
{
	if (__xq_append_head(&cache->free_nodes, idx) == Noneidx)
42
		XSEGLOG2(W, "BUG: Could not free cache entry node. Queue is full");
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
}
#endif

/* table helper functions */
static xcache_handler __table_lookup(xhash_t *table, char *name)
{
	xqindex xqi = Noneidx;
	if (xhash_lookup(table, (xhashidx)name, &xqi) < 0)
		return NoEntry;
	return (xcache_handler)xqi;
}

static int __table_insert(xhash_t **table, struct xcache * cache, xcache_handler h)
{
	xhash_t *new;
	xqindex idx = (xqindex)h;
	struct xcache_entry *ce = &cache->nodes[idx];
	int r = 0;

Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
62 63
	r = xhash_insert(*table, (xhashidx)ce->name, idx);
	if (r == -XHASH_ERESIZE){
64
		XSEGLOG2(I, "Rebuilding internal hash table");
65
		new = xhash_resize(*table, (*table)->size_shift, (*table)->limit, NULL);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
66
		if (!new) {
67
			XSEGLOG2(W, "Error resizing hash table");
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
68 69 70 71 72
			return -1;
		}
		*table = new;

		/* We give insertion a second shot */
73
		r = xhash_insert(*table, (xhashidx)ce->name, idx);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
74
		if (r == -XHASH_ERESIZE) {
75
			XSEGLOG2(W, "BUG: failed to insert entry after resize");
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
76
			return -1;
77
		}
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
78
	}
79 80 81 82 83 84 85 86 87 88 89

	return r;
}

static int __table_remove(xhash_t *table, char *name)
{
	int r;

	r = xhash_delete(table, (xhashidx)name);
	if (UNLIKELY(r<0)){
		if (r == -XHASH_ERESIZE)
90
			XSEGLOG2(W, "BUG: hash table must be resized");
91
		else if (r == -XHASH_EEXIST)
92
			XSEGLOG2(W, "BUG: Entry %s not found in hash table", name);
93 94 95 96 97 98
	}
	return r;
}

static xqindex alloc_cache_entry(struct xcache *cache)
{
Filippos Giannakos's avatar
Filippos Giannakos committed
99
	return xq_pop_head(&cache->free_nodes);
100 101 102 103
}

static void __free_cache_entry(struct xcache *cache, xqindex idx)
{
Filippos Giannakos's avatar
Filippos Giannakos committed
104
	if (UNLIKELY(xq_append_head(&cache->free_nodes, idx) == Noneidx))
105
		XSEGLOG2(W, "BUG: Could not free cache entry node. Queue is full");
106 107 108 109 110
}

static void free_cache_entry(struct xcache *cache, xqindex idx)
{
	struct xcache_entry *ce = &cache->nodes[idx];
111 112

	if (ce->ref != 0)
113
		XSEGLOG2(W, "BUG: Free entry has ref %lu (priv: %p, h: %p)", ce->priv, idx);
114

115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
	__free_cache_entry(cache, idx);
	if (cache->ops.on_free)
		cache->ops.on_free(cache->priv, ce->priv);
}

static xqindex __count_free_nodes(struct xcache *cache)
{
	return xq_count(&cache->free_nodes);
}

static void __reset_times(struct xcache *cache)
{
	uint32_t i;
	struct xcache_entry *ce;
	xbinheapidx time;

	/* assert thatn cache->time does not get MAX value. If this happens, add
	 * one more, to overflow time and return to zero.
	 */
	if (cache->flags & XCACHE_LRU_ARRAY){
		for (i = 0; i < cache->size; i++) {
			if (cache->times[i] != XCACHE_LRU_MAX)
				cache->times[i] = cache->time++;
		}
	} else if (cache->flags & XCACHE_LRU_HEAP) {
		for (i = 0; i < cache->size; i++) {
			ce = &cache->nodes[i];
			if (ce->h == NoNode)
				continue;
			time = xbinheap_getkey(&cache->binheap, ce->h);
			if (time < cache->time)
				xbinheap_increasekey(&cache->binheap, ce->h, cache->time);
			else
				xbinheap_decreasekey(&cache->binheap, ce->h, cache->time);
		}
	}
}

/*
 * xbinheap should be protected by cache lock.
 */
static void __update_access_time(struct xcache *cache, xqindex idx)
{
	struct xcache_entry *ce = &cache->nodes[idx];

	/* assert thatn cache->time does not get MAX value. If this happen,
	 * reset it to zero, and also reset all access times.
	 */
	cache->time++;
	if (cache->time == XCACHE_LRU_MAX) {
		cache->time = 0;
		__reset_times(cache);
		return;
	}

	if (cache->flags & XCACHE_LRU_ARRAY){
		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){
178
				XSEGLOG2(W, "BUG: Cannot insert to lru binary heap");
179 180 181 182 183 184 185 186 187 188 189 190 191
			}
		}
	}
}

/* __xcache_entry_get needs no lock. */
static void __xcache_entry_get(struct xcache *cache, xqindex idx)
{
	struct xcache_entry *ce = &cache->nodes[idx];
	__sync_add_and_fetch(&ce->ref, 1);
}

/*
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
192 193
 * __xcache_entry_get_and_update must be called with cache->lock held, due to
 * the race for __update_access_time.
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
 */
static void __xcache_entry_get_and_update(struct xcache *cache, xqindex idx)
{
	__xcache_entry_get(cache, idx);
	__update_access_time(cache, idx);
}

/* after a succesfull call, the handler must be put */
static int __xcache_remove_entries(struct xcache *cache, xcache_handler h)
{
	int r;
	xqindex idx = (xqindex)h;
	struct xcache_entry *ce = &cache->nodes[idx];

	r = __table_remove(cache->entries, ce->name);
	if (UNLIKELY(r < 0)){
210
		XSEGLOG2(W, "Couldn't delete cache entry from hash table:\n"
211 212 213 214 215 216 217 218 219 220
				"h: %llu, name: %s, cache->nodes[h].priv: %p, ref: %llu",
				h, ce->name, cache->nodes[idx].priv, cache->nodes[idx].ref);
		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){
221
				XSEGLOG2(W, "BUG: cannot increase key to XCACHE_LRU_MAX");
222 223
			}
			if (xbinheap_extract(&cache->binheap) == NoNode){
224
				XSEGLOG2(W, "BUG: cannot remove cache entry from lru");
225 226 227 228
			}
			ce->h = NoNode;
		}
	}
229
	//XSEGLOG2(I, "cache->times[%llu] = %llu", idx, cache->times[idx]);
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244
	return 0;
}

/*
 * __xcache_remove_rm must always be called with cache->rm_lock held.
 * It finalizes the removal of an entry from the cache.
 */
static int __xcache_remove_rm(struct xcache *cache, xcache_handler h)
{
	int r;
	xqindex idx = (xqindex)h;
	struct xcache_entry *ce = &cache->nodes[idx];

	r = __table_remove(cache->rm_entries, ce->name);
	if (UNLIKELY(r < 0)) {
245
		XSEGLOG2(W, "Couldn't delete cache entry from hash table:\n"
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
				"h: %llu, name: %s, cache->nodes[h].priv: %p, ref: %llu",
				h, ce->name, cache->nodes[idx].priv, cache->nodes[idx].ref);
	}

	return r;
}

/*
 * __xcache_lookup_rm must always be called with cache->rm_lock held.
 * It checks if name exists in "rm_entries"
 */
static xcache_handler __xcache_lookup_rm(struct xcache *cache, char *name)
{
	return __table_lookup(cache->rm_entries, name);
}

262
/*
263 264 265
static xcache_handler __xcache_lookup_and_get_rm(struct xcache *cache, char *name)
{
	xcache_handler h;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
266

267 268 269 270
	h = __xcache_lookup_rm(cache, name);
	if (h != NoEntry){
		__xcache_entry_get_and_update(cache, h);
	}
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
271

272 273
	return h;
}
274
*/
275 276 277 278 279 280 281 282 283

static xcache_handler __xcache_lookup_entries(struct xcache *cache, char *name)
{
	return __table_lookup(cache->entries, name);
}

static xcache_handler __xcache_lookup_and_get_entries(struct xcache *cache, char *name)
{
	xcache_handler h;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
284

285 286 287 288
	h = __xcache_lookup_entries(cache, name);
	if (h != NoEntry){
		__xcache_entry_get_and_update(cache, h);
	}
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
289

290 291 292 293 294 295 296 297 298 299 300 301
	return h;
}

static xcache_handler __xcache_insert_rm(struct xcache *cache, xcache_handler h)
{
	return __table_insert(&cache->rm_entries, cache, h);
}

static xcache_handler __xcache_insert_entries(struct xcache *cache, xcache_handler h)
{
	return __table_insert(&cache->entries, cache, h);
}
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
302

303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
/*
 * xcache_entry_put is thread-safe even without cache->lock (cache->rm_lock is
 * crucial though). This is why:
 *
 * a. We put the entry's refcount. If it doesn't drop to zero, we can move on.
 * b. If it drops to zero, then we inform the peer that the cache entry is about
 *    to leave with the "on_evict" hook.
 * c. If peer returns a negative value, we do not free the entry yet and leave.
 * d. If everything is ok, we get the rm_lock.
 * e. Since rm_lock is needed for a re-insertion or a simple 'get' for this
 *    entry, we can safely check again the entry's ref here. If it's > 0, then
 *    someone beat us to it and has a job to do. If it's 0 though, then by
 *    removing the entry from "rm_entries" we are safe to free that entry
 *    without rm_lock.
 */
static void xcache_entry_put(struct xcache *cache, xqindex idx)
{
	struct xcache_entry *ce = &cache->nodes[idx];
321 322
	unsigned long ref;

323
	if (cache->flags & XCACHE_USE_RMTABLE) {
324
		xlock_acquire(&cache->rm_lock);
325

326 327 328
		ref = __sync_sub_and_fetch(&ce->ref, 1);
		if (ref > 0)
			goto out;
329

330 331
		if (cache->ops.on_finalize)
			cache->ops.on_finalize(cache->priv, ce->priv);
332

333 334 335 336 337 338 339 340 341 342
		/*
		 * 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)
			goto out;
		if (__xcache_remove_rm(cache, idx) < 0)
			goto out;
343

344 345 346 347
		xlock_release(&cache->rm_lock);
	} else if ( __sync_sub_and_fetch(&ce->ref, 1) > 0) {
		return;
	}
348 349 350 351

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

352 353 354 355
	free_cache_entry(cache, idx);

	return;

356
out:	/* For XCACHE_USE_RMTABLE only */
357
	xlock_release(&cache->rm_lock);
358 359 360 361 362 363 364 365 366
}

static int xcache_entry_init(struct xcache *cache, xqindex idx, char *name)
{
	int r = 0;
	struct xcache_entry *ce = &cache->nodes[idx];

	xlock_release(&ce->lock);
	if (UNLIKELY(ce->ref != 0))
367
		XSEGLOG2(W, "BUG: New entry has ref != 0 (h: %lu, ref: %lu, priv: %p)",
368
				idx, ce->ref, ce->priv);
369 370 371 372 373
	ce->ref = 1;
	strncpy(ce->name, name, XSEG_MAX_TARGETLEN);
	ce->name[XSEG_MAX_TARGETLEN] = 0;
	ce->h = NoNode;
	ce->state = NODE_ACTIVE;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
374

375 376
	if (cache->ops.on_init)
		r = cache->ops.on_init(cache->priv, ce->priv);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
377

378 379 380 381 382 383 384 385 386 387 388 389
	return r;
}


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++) {
390
			//XSEGLOG2(I, "cache->times[%llu] = %llu", i, cache->times[i]);
391 392 393 394 395 396 397
			if (min > cache->times[i]){
				min = cache->times[i];
				lru = i;
			}
		}
		//FIXME if cache->times[lru] == XCACHE_LRU_MAX
		//	lru = NoEntry;
398
		//XSEGLOG2(I, "Found lru cache->times[%llu] = %llu", lru, cache->times[lru]);
399 400 401 402 403 404 405 406 407 408 409 410 411 412 413
	} 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 int __xcache_evict(struct xcache *cache, xcache_handler h)
{
	//pre_evict
	//remove from entries
	//post_evict
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
414
	//insert to rm_entries
415 416 417

	struct xcache_entry *ce;
	int r;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
418

419 420
	r = __xcache_remove_entries(cache, h);
	if (r < 0) {
421
		XSEGLOG2(W, "Failed to evict %llu from entries", h);
422 423 424 425 426 427 428 429
		return -1;
	}

	/*
	if (NoPendingActions)
		return 0;
	*/
	ce = &cache->nodes[h];
430 431

	if (UNLIKELY(ce->state == NODE_EVICTED))
432
		XSEGLOG2(W, "BUG: Evicting an already evicted entry (h: %lu, priv: %p)",
433
			 h, ce->priv);
434 435

	if (!(cache->flags & XCACHE_USE_RMTABLE))
436 437 438
		return 0;

	ce->state = NODE_EVICTED;
439
	xlock_acquire(&cache->rm_lock);
440 441 442 443 444
	r = __xcache_insert_rm(cache, h);
	xlock_release(&cache->rm_lock);

	if (r < 0) {
		ce->state = NODE_ACTIVE;
445
		XSEGLOG2(W, "BUG: Failed insert %llu to rm_entries", h);
446 447 448 449 450 451 452 453 454 455 456 457 458
		return -1;
	}

	return 0;
}

static xcache_handler __xcache_evict_lru(struct xcache *cache)
{
	int r;
	xcache_handler lru;

	lru = __xcache_lru(cache);
	if (lru == NoEntry){
459
		XSEGLOG2(W, "BUG: No lru found");
460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483
		return NoEntry;
	}

	r = __xcache_evict(cache, lru);
	if (r < 0)
		return NoEntry;
	return lru;
}

static int __xcache_remove(struct xcache *cache, xcache_handler h)
{
	return __xcache_remove_entries(cache, h);
}

/*
 * __xcache_insert is called with cache->lock held and has to hold
 * cache->rm_lock too when looking/inserting an entry in rm_entries. The
 * process is the following:
 *
 * 1. First, we search in "entries" to check if there was a race. If so, we
 *    return the appropriate handler.
 * 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.
 *
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
484
 * <if any of these steps fail, we return NoEntry.>
485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511
 *
 * 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
 *    exists, we remove the oldest entry (LRU) and insert the new entry,
 *
 * When a valid handler is returned, the associated entry's refcount as well as
 * access time will always be increased. A re-inserted entry is 'got' two times,
 * the one to equalize the put that occured after its removal.
 * FIXME: Not the sanest decision to delete entries *first* from one table
 * *and then* copy them to other tables. Handle fails properly.
 */
static xcache_handler __xcache_insert(struct xcache *cache, xcache_handler h,
					xcache_handler *lru_handler,
					xcache_handler *reinsert_handler)
{
	int r;
	struct xcache_entry *ce;
	xcache_handler tmp_h, lru;

	lru = NoEntry;
	ce = &cache->nodes[h];

	/* lookup first to ensure we don't overwrite entries */
	tmp_h = __xcache_lookup_and_get_entries(cache, ce->name);
	if (tmp_h != NoEntry)
		return tmp_h;

512 513 514
	if (!(cache->flags & XCACHE_USE_RMTABLE))
		goto insert;

515
	/* check if our "older self" exists in the rm_entries */
516
	xlock_acquire(&cache->rm_lock);
517 518
	tmp_h = __xcache_lookup_rm(cache, ce->name);
	if (tmp_h != NoEntry) {
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
519
		/* if so then remove it from rm table */
520
		r = __xcache_remove_rm(cache, tmp_h);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
521
		if (UNLIKELY(r < 0)) {
522
			XSEGLOG2(W, "Could not remove found entry (%llu) for %s"
523 524 525 526
				"from rm_entries", tmp_h, ce->name);
			xlock_release(&cache->rm_lock);
			return NoEntry;
		}
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
527 528

		/* and prepare it for reinsertion */
529
		ce = &cache->nodes[tmp_h];
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
530
		if (UNLIKELY(ce->state != NODE_EVICTED))
531
			XSEGLOG2(W, "BUG: Entry (%llu) in rm table not in evicted state", tmp_h);
532
		ce->state = NODE_ACTIVE;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
533 534

		__xcache_entry_get(cache, tmp_h);
535 536 537 538 539
		h = tmp_h;
		*reinsert_handler = tmp_h;
	}
	xlock_release(&cache->rm_lock);

540
insert:
541 542 543 544 545
	/* insert new entry to cache */
	r = __xcache_insert_entries(cache, h);
	if (r == -XHASH_ENOSPC){
		lru = __xcache_evict_lru(cache);
		if (UNLIKELY(lru == NoEntry)) {
546
			XSEGLOG2(W, "BUG: Failed to evict lru entry");
547 548 549
			return NoEntry;
		}
		*lru_handler = lru;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
550

551 552 553 554 555 556
		/*
		 * Cache entry is put when this function returns, without the
		 * cache lock held.
		 */
		r = __xcache_insert_entries(cache, h);
		if (r < 0) {
557
			XSEGLOG2(W, "BUG: failed to insert enries after eviction");
558 559 560 561
			return NoEntry;
		}
	}

562
	if (UNLIKELY(r >= 0 && ce->ref == 0))
563
		XSEGLOG2(W, "BUG: (Re)inserted entry has ref 0 (priv: %p, h: %lu)",
564 565
				ce->priv, h);

Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
566 567 568 569
	if (r >= 0)
		__xcache_entry_get_and_update(cache, h);

	return (r < 0 ? NoEntry : h);
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
}

/*
 * xcache_insert tries to insert an xcache handler in cache.
 * On success, it returns either the same xcache handler or another one that is
 * associated with a cache entry with the same key (name).
 * If the cache node is marked as deleted, we return DelEntry.
 * If the insertion fails for any other reason, we return NoEntry.
 *
 * Finally, if a successful insertion results to an LRU eviction, we put the
 * LRU entry.
 */
xcache_handler xcache_insert(struct xcache *cache, xcache_handler h)
{
	struct xcache_entry *ce;
	xcache_handler ret = NoEntry;
	xcache_handler lru = NoEntry;
	xcache_handler reinsert_handler = NoEntry;

589
	xlock_acquire(&cache->lock);
590 591 592 593 594
	ret = __xcache_insert(cache, h, &lru, &reinsert_handler);
	xlock_release(&cache->lock);

	if (lru != NoEntry) {
		if (UNLIKELY(ret == NoEntry))
595
			XSEGLOG2(W, "BUG: Unsuccessful insertion lead to LRU eviction.");
596 597 598
		ce = &cache->nodes[lru];
		if (cache->ops.on_evict)
			cache->ops.on_evict(cache->priv, ce->priv);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
599
		xcache_entry_put(cache, lru);
600 601 602
	}

	if (reinsert_handler != NoEntry) {
603
		if (UNLIKELY(ret != reinsert_handler))
604
			XSEGLOG2(W, "BUG: Re-insert handler is different from returned handler"
605
					"(rei_h = %llu, ret_h = %llu)", reinsert_handler, ret);
606 607 608 609 610 611 612 613 614
		ce = &cache->nodes[reinsert_handler];
		if (cache->ops.on_reinsert)
			cache->ops.on_reinsert(cache->priv, ce->priv);
	}

	return ret;
}

/*
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
615 616
 * xcache_lookup looks only in "entries". There are several arguments behind
 * this choice:
617
 *
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
618
 * a. Speed: xcache_lookup won't bother with geting rm->lock or re-inserting
619 620 621 622 623 624 625
 *    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;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
626

627
	xlock_acquire(&cache->lock);
628 629
	h = __xcache_lookup_and_get_entries(cache, name);
	xlock_release(&cache->lock);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
630

631 632 633 634 635 636 637 638
	return h;
}

xcache_handler xcache_alloc_init(struct xcache *cache, char *name)
{
	int r;
	xcache_handler h;
	xqindex idx = alloc_cache_entry(cache);
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
639

640 641
	if (idx == Noneidx)
		return NoEntry;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
642

643 644 645 646 647 648
	r = xcache_entry_init(cache, idx, name);
	if (r < 0){
		free_cache_entry(cache, idx);
		return NoEntry;
	}
	h = idx;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
649

650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
	return h;
}

/*
 * xcache_init initializes the following:
 * a. Two xhash tables:
 *    i. "entries", which indexes the active cache entries.
 *    ii. "rm_entries", which indexes the removed cache entries that are on the
 *        process of flushing their dirty data and/or finishing their pending
 *        requests.
 * b. The cache nodes. They are typically 2 x cache_size, since we need room for
 *    the removed cache entries too.
 * c. The LRU, which is chosen on compile time.
 */
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;
	uint32_t tmp_size, floor_size, ceil_size;

	if (!xcache_size)
		return -1;

	/* xcache size must be a power of 2.
	 * Enforce it, by choosing the power of two that is closer to the xcache
	 * size requested.
	 */
	floor_size = 1 << (sizeof(xcache_size) * 8 - __builtin_clz(xcache_size) -1);
	ceil_size = 1 << (sizeof(xcache_size) * 8 - __builtin_clz(xcache_size));

	if (xcache_size - floor_size < ceil_size - xcache_size)
		cache->size = floor_size;
	else
		cache->size = ceil_size;

	if (cache->size != xcache_size)
688
		XSEGLOG2(I, "Cache has been resized from %lu entries to %lu entries",
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715
				xcache_size, cache->size);

	/*
	 * 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.
	 *
	 */

	tmp_size = 3 * cache->size  / 2;
	shift = sizeof(tmp_size) * 8 - __builtin_clz(tmp_size);
	shift += 3;

	xlock_release(&cache->lock);
	xlock_release(&cache->rm_lock);
	cache->nr_nodes = cache->size * 2;
	cache->time = 0;
	cache->ops = *ops;
	cache->priv = priv;
	cache->flags = flags;

716
	/* TODO: assert  cache->size is not UINT64_MAX */
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
717 718
	if (cache->size == (uint64_t)(-1))
		return -1;
719 720 721 722 723 724

	if (!xq_alloc_seq(&cache->free_nodes, cache->nr_nodes,
				cache->nr_nodes)){
		return -1;
	}

725
	cache->entries = xhash_new(shift, cache->size, XHASH_STRING);
726 727 728 729
	if (!cache->entries){
		goto out_free_q;
	}

730 731 732 733 734
	if (flags & XCACHE_USE_RMTABLE) {
		/*
		 * "rm_entries" must have the same size as "entries" since each one indexes
		 * at most (cache->nodes / 2) entries
		 */
735
		cache->rm_entries = xhash_new(shift, cache->size, XHASH_STRING);
736 737 738
		if (!cache->rm_entries){
			goto out_free_entries;
		}
739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759
	}

	cache->nodes = xtypes_malloc(cache->nr_nodes * sizeof(struct xcache_entry));
	if (!cache->nodes){
		goto out_free_rm_entries;
	}

	if (flags & XCACHE_LRU_ARRAY){
		cache->times = xtypes_malloc(cache->nr_nodes * sizeof(uint64_t));
		if (!cache->times){
			goto out_free_nodes;
		}
		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->ref = 0;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
760
			/* FIXME: Is (void *) typecast necessary? */
761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792
			ce->priv = cache->ops.on_node_init(cache->priv, (void *)&i);
			if (!ce->priv)
				goto out_free_times;
		}
	}
	if (flags & XCACHE_LRU_HEAP){
		if (xbinheap_init(&cache->binheap, cache->size, XBINHEAP_MIN,
					NULL) < 0){
			goto out_free_times;
		}
	}

	return 0;

out_free_times:
	if (flags & XCACHE_LRU_ARRAY)
		xtypes_free(cache->times);
out_free_nodes:
	xtypes_free(cache->nodes);
out_free_rm_entries:
	xhash_free(cache->rm_entries);
out_free_entries:
	xhash_free(cache->entries);
out_free_q:
	xq_free(&cache->free_nodes);
	return -1;

}

int xcache_remove(struct xcache *cache, xcache_handler h)
{
	int r;
793
	xlock_acquire(&cache->lock);
794 795 796 797 798 799 800 801 802 803 804 805
	r = __xcache_remove(cache, h);
	xlock_release(&cache->lock);
	return r;
}

//This is just an atomic
//	lookup
//	remove if Found
int xcache_invalidate(struct xcache *cache, char *name)
{
	int r = 0;
	xcache_handler h;
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
806

807
	xlock_acquire(&cache->lock);
808 809 810 811 812 813 814

	h = __xcache_lookup_entries(cache, name);
	if (h != NoEntry){
		r = __xcache_remove_entries(cache, h);
		goto out_put;
	}

815
	if (cache->flags & XCACHE_USE_RMTABLE) {
816
		xlock_acquire(&cache->rm_lock);
817
		xlock_release(&cache->lock);
818

819 820 821 822 823 824 825 826 827
		h = __xcache_lookup_rm(cache, name);
		if (h != NoEntry){
			r = __xcache_remove_rm(cache, h);
		}

		xlock_release(&cache->rm_lock);
	} else {
		xlock_release(&cache->lock);
	}
828 829 830 831 832 833

	return r;

out_put:
	xlock_release(&cache->lock);

Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
834
	if (r >= 0)
835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865
		xcache_put(cache, h);
	return r;

}

/*
 * xcache_get is called with no locking.
 * It simply increases the refcount by one. The entry can either be in "entries"
 * or "rm_entries".
 */
void xcache_get(struct xcache *cache, xcache_handler h)
{
	xqindex idx = (xqindex)h;
	__xcache_entry_get(cache, idx);
}

/*
 * xcache_put is called with no locking, but when the refcount of the entry
 * drops to 0, it takes rm_lock.
 * The entry can either be in "entries" or "rm_entries".
 */
void xcache_put(struct xcache *cache, xcache_handler h)
{
	xqindex idx = (xqindex)h;
	xcache_entry_put(cache, idx);
}

/*
 * 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
Alex Pyrgiotis's avatar
Alex Pyrgiotis committed
866
 * drop to zero
867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917
 */
void xcache_free_new(struct xcache *cache, xcache_handler h)
{
	xqindex idx = (xqindex)h;
	struct xcache_entry *ce = &cache->nodes[idx];

	ce->ref = 0;
	free_cache_entry(cache, idx);
}
/*
 * 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)
{
	uint32_t i;
	struct xcache_entry *ce;
	for (i = 0; i < cache->nr_nodes; i++) {
		ce = &cache->nodes[i];
		if (!ce->ref)
			continue;
		xcache_invalidate(cache, ce->name);
		xcache_entry_put(cache, i);
	}
}

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

/*
 * Return how many free nodes exist.
 * Hint only, since its racy.
 */
uint64_t xcache_free_nodes(struct xcache *cache)
{
	return (uint64_t)__count_free_nodes(cache);
}

#ifdef __KERNEL__
#include <linux/module.h>
#include <xtypes/xcache_exports.h>
#endif