1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 #include "memcached.h" 3 #include <sys/stat.h> 4 #include <sys/socket.h> 5 #include <sys/signal.h> 6 #include <sys/resource.h> 7 #include <fcntl.h> 8 #include <netinet/in.h> 9 #include <errno.h> 10 #include <stdlib.h> 11 #include <stdio.h> 12 #include <string.h> 13 #include <time.h> 14 #include <assert.h> 15 #include <unistd.h> 16 17 /* Forward Declarations */ 18 static void item_link_q(item *it); 19 static void item_unlink_q(item *it); 20 21 #define LARGEST_ID POWER_LARGEST 22 typedef struct { 23 uint64_t evicted; 24 uint64_t evicted_nonzero; 25 rel_time_t evicted_time; 26 uint64_t reclaimed; 27 uint64_t outofmemory; 28 uint64_t tailrepairs; 29 uint64_t expired_unfetched; 30 uint64_t evicted_unfetched; 31 uint64_t crawler_reclaimed; 32 uint64_t lrutail_reflocked; 33 } itemstats_t; 34 35 static item *heads[LARGEST_ID]; 36 static item *tails[LARGEST_ID]; 37 static crawler crawlers[LARGEST_ID]; 38 static itemstats_t itemstats[LARGEST_ID]; 39 static unsigned int sizes[LARGEST_ID]; 40 41 static int crawler_count = 0; 42 static volatile int do_run_lru_crawler_thread = 0; 43 static int lru_crawler_initialized = 0; 44 static pthread_mutex_t lru_crawler_lock = PTHREAD_MUTEX_INITIALIZER; 45 static pthread_cond_t lru_crawler_cond = PTHREAD_COND_INITIALIZER; 46 47 void item_stats_reset(void) { 48 mutex_lock(&cache_lock); 49 memset(itemstats, 0, sizeof(itemstats)); 50 mutex_unlock(&cache_lock); 51 } 52 53 54 /* Get the next CAS id for a new item. */ 55 uint64_t get_cas_id(void) { 56 static uint64_t cas_id = 0; 57 return ++cas_id; 58 } 59 60 /* Enable this for reference-count debugging. */ 61 #if 0 62 # define DEBUG_REFCNT(it,op) \ 63 fprintf(stderr, "item %x refcnt(%c) %d %c%c%c\n", \ 64 it, op, it->refcount, \ 65 (it->it_flags & ITEM_LINKED) ? 'L' : ' ', \ 66 (it->it_flags & ITEM_SLABBED) ? 'S' : ' ') 67 #else 68 # define DEBUG_REFCNT(it,op) while(0) 69 #endif 70 71 /** 72 * Generates the variable-sized part of the header for an object. 73 * 74 * key - The key 75 * nkey - The length of the key 76 * flags - key flags 77 * nbytes - Number of bytes to hold value and addition CRLF terminator 78 * suffix - Buffer for the "VALUE" line suffix (flags, size). 79 * nsuffix - The length of the suffix is stored here. 80 * 81 * Returns the total size of the header. 82 */ 83 static size_t item_make_header(const uint8_t nkey, const int flags, const int nbytes, 84 char *suffix, uint8_t *nsuffix) { 85 /* suffix is defined at 40 chars elsewhere.. */ 86 *nsuffix = (uint8_t) snprintf(suffix, 40, " %d %d\r\n", flags, nbytes - 2); 87 return sizeof(item) + nkey + *nsuffix + nbytes; 88 } 89 90 /*@null@*/ 91 item *do_item_alloc(char *key, const size_t nkey, const int flags, 92 const rel_time_t exptime, const int nbytes, 93 const uint32_t cur_hv) { 94 uint8_t nsuffix; 95 item *it = NULL; 96 char suffix[40]; 97 size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix); 98 if (settings.use_cas) { 99 ntotal += sizeof(uint64_t); 100 } 101 102 unsigned int id = slabs_clsid(ntotal); 103 if (id == 0) 104 return 0; 105 106 mutex_lock(&cache_lock); 107 /* do a quick check if we have any expired items in the tail.. */ 108 int tries = 5; 109 /* Avoid hangs if a slab has nothing but refcounted stuff in it. */ 110 int tries_lrutail_reflocked = 1000; 111 int tried_alloc = 0; 112 item *search; 113 item *next_it; 114 void *hold_lock = NULL; 115 rel_time_t oldest_live = settings.oldest_live; 116 117 search = tails[id]; 118 /* We walk up *only* for locked items. Never searching for expired. 119 * Waste of CPU for almost all deployments */ 120 for (; tries > 0 && search != NULL; tries--, search=next_it) { 121 /* we might relink search mid-loop, so search->prev isn't reliable */ 122 next_it = search->prev; 123 if (search->nbytes == 0 && search->nkey == 0 && search->it_flags == 1) { 124 /* We are a crawler, ignore it. */ 125 tries++; 126 continue; 127 } 128 uint32_t hv = hash(ITEM_key(search), search->nkey); 129 /* Attempt to hash item lock the "search" item. If locked, no 130 * other callers can incr the refcount 131 */ 132 /* Don't accidentally grab ourselves, or bail if we can't quicklock */ 133 if (hv == cur_hv || (hold_lock = item_trylock(hv)) == NULL) 134 continue; 135 /* Now see if the item is refcount locked */ 136 if (refcount_incr(&search->refcount) != 2) { 137 /* Avoid pathological case with ref'ed items in tail */ 138 do_item_update_nolock(search); 139 tries_lrutail_reflocked--; 140 tries++; 141 refcount_decr(&search->refcount); 142 itemstats[id].lrutail_reflocked++; 143 /* Old rare bug could cause a refcount leak. We haven't seen 144 * it in years, but we leave this code in to prevent failures 145 * just in case */ 146 if (settings.tail_repair_time && 147 search->time + settings.tail_repair_time < current_time) { 148 itemstats[id].tailrepairs++; 149 search->refcount = 1; 150 do_item_unlink_nolock(search, hv); 151 } 152 if (hold_lock) 153 item_trylock_unlock(hold_lock); 154 155 if (tries_lrutail_reflocked < 1) 156 break; 157 158 continue; 159 } 160 161 /* Expired or flushed */ 162 if ((search->exptime != 0 && search->exptime < current_time) 163 || (search->time <= oldest_live && oldest_live <= current_time)) { 164 itemstats[id].reclaimed++; 165 if ((search->it_flags & ITEM_FETCHED) == 0) { 166 itemstats[id].expired_unfetched++; 167 } 168 it = search; 169 slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal); 170 do_item_unlink_nolock(it, hv); 171 /* Initialize the item block: */ 172 it->slabs_clsid = 0; 173 } else if ((it = slabs_alloc(ntotal, id)) == NULL) { 174 tried_alloc = 1; 175 if (settings.evict_to_free == 0) { 176 itemstats[id].outofmemory++; 177 } else { 178 itemstats[id].evicted++; 179 itemstats[id].evicted_time = current_time - search->time; 180 if (search->exptime != 0) 181 itemstats[id].evicted_nonzero++; 182 if ((search->it_flags & ITEM_FETCHED) == 0) { 183 itemstats[id].evicted_unfetched++; 184 } 185 it = search; 186 slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal); 187 do_item_unlink_nolock(it, hv); 188 /* Initialize the item block: */ 189 it->slabs_clsid = 0; 190 191 /* If we've just evicted an item, and the automover is set to 192 * angry bird mode, attempt to rip memory into this slab class. 193 * TODO: Move valid object detection into a function, and on a 194 * "successful" memory pull, look behind and see if the next alloc 195 * would be an eviction. Then kick off the slab mover before the 196 * eviction happens. 197 */ 198 if (settings.slab_automove == 2) 199 slabs_reassign(-1, id); 200 } 201 } 202 203 refcount_decr(&search->refcount); 204 /* If hash values were equal, we don't grab a second lock */ 205 if (hold_lock) 206 item_trylock_unlock(hold_lock); 207 break; 208 } 209 210 if (!tried_alloc && (tries == 0 || search == NULL)) 211 it = slabs_alloc(ntotal, id); 212 213 if (it == NULL) { 214 itemstats[id].outofmemory++; 215 mutex_unlock(&cache_lock); 216 return NULL; 217 } 218 219 assert(it->slabs_clsid == 0); 220 assert(it != heads[id]); 221 222 /* Item initialization can happen outside of the lock; the item's already 223 * been removed from the slab LRU. 224 */ 225 it->refcount = 1; /* the caller will have a reference */ 226 mutex_unlock(&cache_lock); 227 it->next = it->prev = it->h_next = 0; 228 it->slabs_clsid = id; 229 230 DEBUG_REFCNT(it, '*'); 231 it->it_flags = settings.use_cas ? ITEM_CAS : 0; 232 it->nkey = nkey; 233 it->nbytes = nbytes; 234 memcpy(ITEM_key(it), key, nkey); 235 it->exptime = exptime; 236 memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix); 237 it->nsuffix = nsuffix; 238 return it; 239 } 240 241 void item_free(item *it) { 242 size_t ntotal = ITEM_ntotal(it); 243 unsigned int clsid; 244 assert((it->it_flags & ITEM_LINKED) == 0); 245 assert(it != heads[it->slabs_clsid]); 246 assert(it != tails[it->slabs_clsid]); 247 assert(it->refcount == 0); 248 249 /* so slab size changer can tell later if item is already free or not */ 250 clsid = it->slabs_clsid; 251 it->slabs_clsid = 0; 252 DEBUG_REFCNT(it, 'F'); 253 slabs_free(it, ntotal, clsid); 254 } 255 256 /** 257 * Returns true if an item will fit in the cache (its size does not exceed 258 * the maximum for a cache entry.) 259 */ 260 bool item_size_ok(const size_t nkey, const int flags, const int nbytes) { 261 char prefix[40]; 262 uint8_t nsuffix; 263 264 size_t ntotal = item_make_header(nkey + 1, flags, nbytes, 265 prefix, &nsuffix); 266 if (settings.use_cas) { 267 ntotal += sizeof(uint64_t); 268 } 269 270 return slabs_clsid(ntotal) != 0; 271 } 272 273 static void item_link_q(item *it) { /* item is the new head */ 274 item **head, **tail; 275 assert(it->slabs_clsid < LARGEST_ID); 276 assert((it->it_flags & ITEM_SLABBED) == 0); 277 278 head = &heads[it->slabs_clsid]; 279 tail = &tails[it->slabs_clsid]; 280 assert(it != *head); 281 assert((*head && *tail) || (*head == 0 && *tail == 0)); 282 it->prev = 0; 283 it->next = *head; 284 if (it->next) it->next->prev = it; 285 *head = it; 286 if (*tail == 0) *tail = it; 287 sizes[it->slabs_clsid]++; 288 return; 289 } 290 291 static void item_unlink_q(item *it) { 292 item **head, **tail; 293 assert(it->slabs_clsid < LARGEST_ID); 294 head = &heads[it->slabs_clsid]; 295 tail = &tails[it->slabs_clsid]; 296 297 if (*head == it) { 298 assert(it->prev == 0); 299 *head = it->next; 300 } 301 if (*tail == it) { 302 assert(it->next == 0); 303 *tail = it->prev; 304 } 305 assert(it->next != it); 306 assert(it->prev != it); 307 308 if (it->next) it->next->prev = it->prev; 309 if (it->prev) it->prev->next = it->next; 310 sizes[it->slabs_clsid]--; 311 return; 312 } 313 314 int do_item_link(item *it, const uint32_t hv) { 315 MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes); 316 assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0); 317 mutex_lock(&cache_lock); 318 it->it_flags |= ITEM_LINKED; 319 it->time = current_time; 320 321 STATS_LOCK(); 322 stats.curr_bytes += ITEM_ntotal(it); 323 stats.curr_items += 1; 324 stats.total_items += 1; 325 STATS_UNLOCK(); 326 327 /* Allocate a new CAS ID on link. */ 328 ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0); 329 assoc_insert(it, hv); 330 item_link_q(it); 331 refcount_incr(&it->refcount); 332 mutex_unlock(&cache_lock); 333 334 return 1; 335 } 336 337 void do_item_unlink(item *it, const uint32_t hv) { 338 MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes); 339 mutex_lock(&cache_lock); 340 if ((it->it_flags & ITEM_LINKED) != 0) { 341 it->it_flags &= ~ITEM_LINKED; 342 STATS_LOCK(); 343 stats.curr_bytes -= ITEM_ntotal(it); 344 stats.curr_items -= 1; 345 STATS_UNLOCK(); 346 assoc_delete(ITEM_key(it), it->nkey, hv); 347 item_unlink_q(it); 348 do_item_remove(it); 349 } 350 mutex_unlock(&cache_lock); 351 } 352 353 /* FIXME: Is it necessary to keep this copy/pasted code? */ 354 void do_item_unlink_nolock(item *it, const uint32_t hv) { 355 MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes); 356 if ((it->it_flags & ITEM_LINKED) != 0) { 357 it->it_flags &= ~ITEM_LINKED; 358 STATS_LOCK(); 359 stats.curr_bytes -= ITEM_ntotal(it); 360 stats.curr_items -= 1; 361 STATS_UNLOCK(); 362 assoc_delete(ITEM_key(it), it->nkey, hv); 363 item_unlink_q(it); 364 do_item_remove(it); 365 } 366 } 367 368 void do_item_remove(item *it) { 369 MEMCACHED_ITEM_REMOVE(ITEM_key(it), it->nkey, it->nbytes); 370 assert((it->it_flags & ITEM_SLABBED) == 0); 371 assert(it->refcount > 0); 372 373 if (refcount_decr(&it->refcount) == 0) { 374 item_free(it); 375 } 376 } 377 378 /* Copy/paste to avoid adding two extra branches for all common calls, since 379 * _nolock is only used in an uncommon case. */ 380 void do_item_update_nolock(item *it) { 381 MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes); 382 if (it->time < current_time - ITEM_UPDATE_INTERVAL) { 383 assert((it->it_flags & ITEM_SLABBED) == 0); 384 385 if ((it->it_flags & ITEM_LINKED) != 0) { 386 item_unlink_q(it); 387 it->time = current_time; 388 item_link_q(it); 389 } 390 } 391 } 392 393 void do_item_update(item *it) { 394 MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes); 395 if (it->time < current_time - ITEM_UPDATE_INTERVAL) { 396 assert((it->it_flags & ITEM_SLABBED) == 0); 397 398 mutex_lock(&cache_lock); 399 if ((it->it_flags & ITEM_LINKED) != 0) { 400 item_unlink_q(it); 401 it->time = current_time; 402 item_link_q(it); 403 } 404 mutex_unlock(&cache_lock); 405 } 406 } 407 408 int do_item_replace(item *it, item *new_it, const uint32_t hv) { 409 MEMCACHED_ITEM_REPLACE(ITEM_key(it), it->nkey, it->nbytes, 410 ITEM_key(new_it), new_it->nkey, new_it->nbytes); 411 assert((it->it_flags & ITEM_SLABBED) == 0); 412 413 do_item_unlink(it, hv); 414 return do_item_link(new_it, hv); 415 } 416 417 /*@null@*/ 418 char *do_item_cachedump(const unsigned int slabs_clsid, const unsigned int limit, unsigned int *bytes) { 419 unsigned int memlimit = 2 * 1024 * 1024; /* 2MB max response size */ 420 char *buffer; 421 unsigned int bufcurr; 422 item *it; 423 unsigned int len; 424 unsigned int shown = 0; 425 char key_temp[KEY_MAX_LENGTH + 1]; 426 char temp[512]; 427 428 it = heads[slabs_clsid]; 429 430 buffer = malloc((size_t)memlimit); 431 if (buffer == 0) return NULL; 432 bufcurr = 0; 433 434 while (it != NULL && (limit == 0 || shown < limit)) { 435 assert(it->nkey <= KEY_MAX_LENGTH); 436 if (it->nbytes == 0 && it->nkey == 0) { 437 it = it->next; 438 continue; 439 } 440 /* Copy the key since it may not be null-terminated in the struct */ 441 strncpy(key_temp, ITEM_key(it), it->nkey); 442 key_temp[it->nkey] = 0x00; /* terminate */ 443 len = snprintf(temp, sizeof(temp), "ITEM %s [%d b; %lu s]\r\n", 444 key_temp, it->nbytes - 2, 445 (unsigned long)it->exptime + process_started); 446 if (bufcurr + len + 6 > memlimit) /* 6 is END\r\n\0 */ 447 break; 448 memcpy(buffer + bufcurr, temp, len); 449 bufcurr += len; 450 shown++; 451 it = it->next; 452 } 453 454 memcpy(buffer + bufcurr, "END\r\n", 6); 455 bufcurr += 5; 456 457 *bytes = bufcurr; 458 return buffer; 459 } 460 461 void item_stats_evictions(uint64_t *evicted) { 462 int i; 463 mutex_lock(&cache_lock); 464 for (i = 0; i < LARGEST_ID; i++) { 465 evicted[i] = itemstats[i].evicted; 466 } 467 mutex_unlock(&cache_lock); 468 } 469 470 void do_item_stats_totals(ADD_STAT add_stats, void *c) { 471 itemstats_t totals; 472 memset(&totals, 0, sizeof(itemstats_t)); 473 int i; 474 for (i = 0; i < LARGEST_ID; i++) { 475 totals.expired_unfetched += itemstats[i].expired_unfetched; 476 totals.evicted_unfetched += itemstats[i].evicted_unfetched; 477 totals.evicted += itemstats[i].evicted; 478 totals.reclaimed += itemstats[i].reclaimed; 479 totals.crawler_reclaimed += itemstats[i].crawler_reclaimed; 480 totals.lrutail_reflocked += itemstats[i].lrutail_reflocked; 481 } 482 APPEND_STAT("expired_unfetched", "%llu", 483 (unsigned long long)totals.expired_unfetched); 484 APPEND_STAT("evicted_unfetched", "%llu", 485 (unsigned long long)totals.evicted_unfetched); 486 APPEND_STAT("evictions", "%llu", 487 (unsigned long long)totals.evicted); 488 APPEND_STAT("reclaimed", "%llu", 489 (unsigned long long)totals.reclaimed); 490 APPEND_STAT("crawler_reclaimed", "%llu", 491 (unsigned long long)totals.crawler_reclaimed); 492 APPEND_STAT("lrutail_reflocked", "%llu", 493 (unsigned long long)totals.lrutail_reflocked); 494 } 495 496 void do_item_stats(ADD_STAT add_stats, void *c) { 497 int i; 498 for (i = 0; i < LARGEST_ID; i++) { 499 if (tails[i] != NULL) { 500 const char *fmt = "items:%d:%s"; 501 char key_str[STAT_KEY_LEN]; 502 char val_str[STAT_VAL_LEN]; 503 int klen = 0, vlen = 0; 504 if (tails[i] == NULL) { 505 /* We removed all of the items in this slab class */ 506 continue; 507 } 508 APPEND_NUM_FMT_STAT(fmt, i, "number", "%u", sizes[i]); 509 APPEND_NUM_FMT_STAT(fmt, i, "age", "%u", current_time - tails[i]->time); 510 APPEND_NUM_FMT_STAT(fmt, i, "evicted", 511 "%llu", (unsigned long long)itemstats[i].evicted); 512 APPEND_NUM_FMT_STAT(fmt, i, "evicted_nonzero", 513 "%llu", (unsigned long long)itemstats[i].evicted_nonzero); 514 APPEND_NUM_FMT_STAT(fmt, i, "evicted_time", 515 "%u", itemstats[i].evicted_time); 516 APPEND_NUM_FMT_STAT(fmt, i, "outofmemory", 517 "%llu", (unsigned long long)itemstats[i].outofmemory); 518 APPEND_NUM_FMT_STAT(fmt, i, "tailrepairs", 519 "%llu", (unsigned long long)itemstats[i].tailrepairs); 520 APPEND_NUM_FMT_STAT(fmt, i, "reclaimed", 521 "%llu", (unsigned long long)itemstats[i].reclaimed); 522 APPEND_NUM_FMT_STAT(fmt, i, "expired_unfetched", 523 "%llu", (unsigned long long)itemstats[i].expired_unfetched); 524 APPEND_NUM_FMT_STAT(fmt, i, "evicted_unfetched", 525 "%llu", (unsigned long long)itemstats[i].evicted_unfetched); 526 APPEND_NUM_FMT_STAT(fmt, i, "crawler_reclaimed", 527 "%llu", (unsigned long long)itemstats[i].crawler_reclaimed); 528 APPEND_NUM_FMT_STAT(fmt, i, "lrutail_reflocked", 529 "%llu", (unsigned long long)itemstats[i].lrutail_reflocked); 530 } 531 } 532 533 /* getting here means both ascii and binary terminators fit */ 534 add_stats(NULL, 0, NULL, 0, c); 535 } 536 537 /** dumps out a list of objects of each size, with granularity of 32 bytes */ 538 /*@null@*/ 539 void do_item_stats_sizes(ADD_STAT add_stats, void *c) { 540 541 /* max 1MB object, divided into 32 bytes size buckets */ 542 const int num_buckets = 32768; 543 unsigned int *histogram = calloc(num_buckets, sizeof(int)); 544 545 if (histogram != NULL) { 546 int i; 547 548 /* build the histogram */ 549 for (i = 0; i < LARGEST_ID; i++) { 550 item *iter = heads[i]; 551 while (iter) { 552 int ntotal = ITEM_ntotal(iter); 553 int bucket = ntotal / 32; 554 if ((ntotal % 32) != 0) bucket++; 555 if (bucket < num_buckets) histogram[bucket]++; 556 iter = iter->next; 557 } 558 } 559 560 /* write the buffer */ 561 for (i = 0; i < num_buckets; i++) { 562 if (histogram[i] != 0) { 563 char key[8]; 564 snprintf(key, sizeof(key), "%d", i * 32); 565 APPEND_STAT(key, "%u", histogram[i]); 566 } 567 } 568 free(histogram); 569 } 570 add_stats(NULL, 0, NULL, 0, c); 571 } 572 573 /** wrapper around assoc_find which does the lazy expiration logic */ 574 item *do_item_get(const char *key, const size_t nkey, const uint32_t hv) { 575 //mutex_lock(&cache_lock); 576 item *it = assoc_find(key, nkey, hv); 577 if (it != NULL) { 578 refcount_incr(&it->refcount); 579 /* Optimization for slab reassignment. prevents popular items from 580 * jamming in busy wait. Can only do this here to satisfy lock order 581 * of item_lock, cache_lock, slabs_lock. */ 582 if (slab_rebalance_signal && 583 ((void *)it >= slab_rebal.slab_start && (void *)it < slab_rebal.slab_end)) { 584 do_item_unlink_nolock(it, hv); 585 do_item_remove(it); 586 it = NULL; 587 } 588 } 589 //mutex_unlock(&cache_lock); 590 int was_found = 0; 591 592 if (settings.verbose > 2) { 593 int ii; 594 if (it == NULL) { 595 fprintf(stderr, "> NOT FOUND "); 596 } else { 597 fprintf(stderr, "> FOUND KEY "); 598 was_found++; 599 } 600 for (ii = 0; ii < nkey; ++ii) { 601 fprintf(stderr, "%c", key[ii]); 602 } 603 } 604 605 if (it != NULL) { 606 if (settings.oldest_live != 0 && settings.oldest_live <= current_time && 607 it->time <= settings.oldest_live) { 608 do_item_unlink(it, hv); 609 do_item_remove(it); 610 it = NULL; 611 if (was_found) { 612 fprintf(stderr, " -nuked by flush"); 613 } 614 } else if (it->exptime != 0 && it->exptime <= current_time) { 615 do_item_unlink(it, hv); 616 do_item_remove(it); 617 it = NULL; 618 if (was_found) { 619 fprintf(stderr, " -nuked by expire"); 620 } 621 } else { 622 it->it_flags |= ITEM_FETCHED; 623 DEBUG_REFCNT(it, '+'); 624 } 625 } 626 627 if (settings.verbose > 2) 628 fprintf(stderr, "\n"); 629 630 return it; 631 } 632 633 item *do_item_touch(const char *key, size_t nkey, uint32_t exptime, 634 const uint32_t hv) { 635 item *it = do_item_get(key, nkey, hv); 636 if (it != NULL) { 637 it->exptime = exptime; 638 } 639 return it; 640 } 641 642 /* expires items that are more recent than the oldest_live setting. */ 643 void do_item_flush_expired(void) { 644 int i; 645 item *iter, *next; 646 if (settings.oldest_live == 0) 647 return; 648 for (i = 0; i < LARGEST_ID; i++) { 649 /* The LRU is sorted in decreasing time order, and an item's timestamp 650 * is never newer than its last access time, so we only need to walk 651 * back until we hit an item older than the oldest_live time. 652 * The oldest_live checking will auto-expire the remaining items. 653 */ 654 for (iter = heads[i]; iter != NULL; iter = next) { 655 /* iter->time of 0 are magic objects. */ 656 if (iter->time != 0 && iter->time >= settings.oldest_live) { 657 next = iter->next; 658 if ((iter->it_flags & ITEM_SLABBED) == 0) { 659 do_item_unlink_nolock(iter, hash(ITEM_key(iter), iter->nkey)); 660 } 661 } else { 662 /* We've hit the first old item. Continue to the next queue. */ 663 break; 664 } 665 } 666 } 667 } 668 669 static void crawler_link_q(item *it) { /* item is the new tail */ 670 item **head, **tail; 671 assert(it->slabs_clsid < LARGEST_ID); 672 assert(it->it_flags == 1); 673 assert(it->nbytes == 0); 674 675 head = &heads[it->slabs_clsid]; 676 tail = &tails[it->slabs_clsid]; 677 assert(*tail != 0); 678 assert(it != *tail); 679 assert((*head && *tail) || (*head == 0 && *tail == 0)); 680 it->prev = *tail; 681 it->next = 0; 682 if (it->prev) { 683 assert(it->prev->next == 0); 684 it->prev->next = it; 685 } 686 *tail = it; 687 if (*head == 0) *head = it; 688 return; 689 } 690 691 static void crawler_unlink_q(item *it) { 692 item **head, **tail; 693 assert(it->slabs_clsid < LARGEST_ID); 694 head = &heads[it->slabs_clsid]; 695 tail = &tails[it->slabs_clsid]; 696 697 if (*head == it) { 698 assert(it->prev == 0); 699 *head = it->next; 700 } 701 if (*tail == it) { 702 assert(it->next == 0); 703 *tail = it->prev; 704 } 705 assert(it->next != it); 706 assert(it->prev != it); 707 708 if (it->next) it->next->prev = it->prev; 709 if (it->prev) it->prev->next = it->next; 710 return; 711 } 712 713 /* This is too convoluted, but it's a difficult shuffle. Try to rewrite it 714 * more clearly. */ 715 static item *crawler_crawl_q(item *it) { 716 item **head, **tail; 717 assert(it->it_flags == 1); 718 assert(it->nbytes == 0); 719 assert(it->slabs_clsid < LARGEST_ID); 720 head = &heads[it->slabs_clsid]; 721 tail = &tails[it->slabs_clsid]; 722 723 /* We've hit the head, pop off */ 724 if (it->prev == 0) { 725 assert(*head == it); 726 if (it->next) { 727 *head = it->next; 728 assert(it->next->prev == it); 729 it->next->prev = 0; 730 } 731 return NULL; /* Done */ 732 } 733 734 /* Swing ourselves in front of the next item */ 735 /* NB: If there is a prev, we can't be the head */ 736 assert(it->prev != it); 737 if (it->prev) { 738 if (*head == it->prev) { 739 /* Prev was the head, now we're the head */ 740 *head = it; 741 } 742 if (*tail == it) { 743 /* We are the tail, now they are the tail */ 744 *tail = it->prev; 745 } 746 assert(it->next != it); 747 if (it->next) { 748 assert(it->prev->next == it); 749 it->prev->next = it->next; 750 it->next->prev = it->prev; 751 } else { 752 /* Tail. Move this above? */ 753 it->prev->next = 0; 754 } 755 /* prev->prev's next is it->prev */ 756 it->next = it->prev; 757 it->prev = it->next->prev; 758 it->next->prev = it; 759 /* New it->prev now, if we're not at the head. */ 760 if (it->prev) { 761 it->prev->next = it; 762 } 763 } 764 assert(it->next != it); 765 assert(it->prev != it); 766 767 return it->next; /* success */ 768 } 769 770 /* I pulled this out to make the main thread clearer, but it reaches into the 771 * main thread's values too much. Should rethink again. 772 */ 773 static void item_crawler_evaluate(item *search, uint32_t hv, int i) { 774 rel_time_t oldest_live = settings.oldest_live; 775 if ((search->exptime != 0 && search->exptime < current_time) 776 || (search->time <= oldest_live && oldest_live <= current_time)) { 777 itemstats[i].crawler_reclaimed++; 778 779 if (settings.verbose > 1) { 780 int ii; 781 char *key = ITEM_key(search); 782 fprintf(stderr, "LRU crawler found an expired item (flags: %d, slab: %d): ", 783 search->it_flags, search->slabs_clsid); 784 for (ii = 0; ii < search->nkey; ++ii) { 785 fprintf(stderr, "%c", key[ii]); 786 } 787 fprintf(stderr, "\n"); 788 } 789 if ((search->it_flags & ITEM_FETCHED) == 0) { 790 itemstats[i].expired_unfetched++; 791 } 792 do_item_unlink_nolock(search, hv); 793 do_item_remove(search); 794 assert(search->slabs_clsid == 0); 795 } else { 796 refcount_decr(&search->refcount); 797 } 798 } 799 800 static void *item_crawler_thread(void *arg) { 801 int i; 802 803 pthread_mutex_lock(&lru_crawler_lock); 804 if (settings.verbose > 2) 805 fprintf(stderr, "Starting LRU crawler background thread\n"); 806 while (do_run_lru_crawler_thread) { 807 pthread_cond_wait(&lru_crawler_cond, &lru_crawler_lock); 808 809 while (crawler_count) { 810 item *search = NULL; 811 void *hold_lock = NULL; 812 813 for (i = 0; i < LARGEST_ID; i++) { 814 if (crawlers[i].it_flags != 1) { 815 continue; 816 } 817 pthread_mutex_lock(&cache_lock); 818 search = crawler_crawl_q((item *)&crawlers[i]); 819 if (search == NULL || 820 (crawlers[i].remaining && --crawlers[i].remaining < 1)) { 821 if (settings.verbose > 2) 822 fprintf(stderr, "Nothing left to crawl for %d\n", i); 823 crawlers[i].it_flags = 0; 824 crawler_count--; 825 crawler_unlink_q((item *)&crawlers[i]); 826 pthread_mutex_unlock(&cache_lock); 827 continue; 828 } 829 uint32_t hv = hash(ITEM_key(search), search->nkey); 830 /* Attempt to hash item lock the "search" item. If locked, no 831 * other callers can incr the refcount 832 */ 833 if ((hold_lock = item_trylock(hv)) == NULL) { 834 pthread_mutex_unlock(&cache_lock); 835 continue; 836 } 837 /* Now see if the item is refcount locked */ 838 if (refcount_incr(&search->refcount) != 2) { 839 refcount_decr(&search->refcount); 840 if (hold_lock) 841 item_trylock_unlock(hold_lock); 842 pthread_mutex_unlock(&cache_lock); 843 continue; 844 } 845 846 /* Frees the item or decrements the refcount. */ 847 /* Interface for this could improve: do the free/decr here 848 * instead? */ 849 item_crawler_evaluate(search, hv, i); 850 851 if (hold_lock) 852 item_trylock_unlock(hold_lock); 853 pthread_mutex_unlock(&cache_lock); 854 855 if (settings.lru_crawler_sleep) 856 usleep(settings.lru_crawler_sleep); 857 } 858 } 859 if (settings.verbose > 2) 860 fprintf(stderr, "LRU crawler thread sleeping\n"); 861 STATS_LOCK(); 862 stats.lru_crawler_running = false; 863 STATS_UNLOCK(); 864 } 865 pthread_mutex_unlock(&lru_crawler_lock); 866 if (settings.verbose > 2) 867 fprintf(stderr, "LRU crawler thread stopping\n"); 868 869 return NULL; 870 } 871 872 static pthread_t item_crawler_tid; 873 874 int stop_item_crawler_thread(void) { 875 int ret; 876 pthread_mutex_lock(&lru_crawler_lock); 877 do_run_lru_crawler_thread = 0; 878 pthread_cond_signal(&lru_crawler_cond); 879 pthread_mutex_unlock(&lru_crawler_lock); 880 if ((ret = pthread_join(item_crawler_tid, NULL)) != 0) { 881 fprintf(stderr, "Failed to stop LRU crawler thread: %s\n", strerror(ret)); 882 return -1; 883 } 884 settings.lru_crawler = false; 885 return 0; 886 } 887 888 int start_item_crawler_thread(void) { 889 int ret; 890 891 if (settings.lru_crawler) 892 return -1; 893 pthread_mutex_lock(&lru_crawler_lock); 894 do_run_lru_crawler_thread = 1; 895 settings.lru_crawler = true; 896 if ((ret = pthread_create(&item_crawler_tid, NULL, 897 item_crawler_thread, NULL)) != 0) { 898 fprintf(stderr, "Can't create LRU crawler thread: %s\n", 899 strerror(ret)); 900 pthread_mutex_unlock(&lru_crawler_lock); 901 return -1; 902 } 903 pthread_mutex_unlock(&lru_crawler_lock); 904 905 return 0; 906 } 907 908 enum crawler_result_type lru_crawler_crawl(char *slabs) { 909 char *b = NULL; 910 uint32_t sid = 0; 911 uint8_t tocrawl[POWER_LARGEST]; 912 if (pthread_mutex_trylock(&lru_crawler_lock) != 0) { 913 return CRAWLER_RUNNING; 914 } 915 pthread_mutex_lock(&cache_lock); 916 917 if (strcmp(slabs, "all") == 0) { 918 for (sid = 0; sid < LARGEST_ID; sid++) { 919 tocrawl[sid] = 1; 920 } 921 } else { 922 for (char *p = strtok_r(slabs, ",", &b); 923 p != NULL; 924 p = strtok_r(NULL, ",", &b)) { 925 926 if (!safe_strtoul(p, &sid) || sid < POWER_SMALLEST 927 || sid > POWER_LARGEST) { 928 pthread_mutex_unlock(&cache_lock); 929 pthread_mutex_unlock(&lru_crawler_lock); 930 return CRAWLER_BADCLASS; 931 } 932 tocrawl[sid] = 1; 933 } 934 } 935 936 for (sid = 0; sid < LARGEST_ID; sid++) { 937 if (tocrawl[sid] != 0 && tails[sid] != NULL) { 938 if (settings.verbose > 2) 939 fprintf(stderr, "Kicking LRU crawler off for slab %d\n", sid); 940 crawlers[sid].nbytes = 0; 941 crawlers[sid].nkey = 0; 942 crawlers[sid].it_flags = 1; /* For a crawler, this means enabled. */ 943 crawlers[sid].next = 0; 944 crawlers[sid].prev = 0; 945 crawlers[sid].time = 0; 946 crawlers[sid].remaining = settings.lru_crawler_tocrawl; 947 crawlers[sid].slabs_clsid = sid; 948 crawler_link_q((item *)&crawlers[sid]); 949 crawler_count++; 950 } 951 } 952 pthread_mutex_unlock(&cache_lock); 953 pthread_cond_signal(&lru_crawler_cond); 954 STATS_LOCK(); 955 stats.lru_crawler_running = true; 956 STATS_UNLOCK(); 957 pthread_mutex_unlock(&lru_crawler_lock); 958 return CRAWLER_OK; 959 } 960 961 int init_lru_crawler(void) { 962 if (lru_crawler_initialized == 0) { 963 if (pthread_cond_init(&lru_crawler_cond, NULL) != 0) { 964 fprintf(stderr, "Can't initialize lru crawler condition\n"); 965 return -1; 966 } 967 pthread_mutex_init(&lru_crawler_lock, NULL); 968 lru_crawler_initialized = 1; 969 } 970 return 0; 971 } 972