src/store_dir.cc

   1
   2 /*
   3  * $Id$
   4  *
   5  * DEBUG: section 47    Store Directory Routines
   6  * AUTHOR: Duane Wessels
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37 #include "Store.h"
  38 #include "MemObject.h"
  39 #include "MemStore.h"
  40 #include "mem_node.h"
  41 #include "SquidMath.h"
  42 #include "SquidTime.h"
  43 #include "SwapDir.h"
  44 #include "swap_log_op.h"
  45
  46 #if HAVE_STATVFS
  47 #if HAVE_SYS_STATVFS_H
  48 #include <sys/statvfs.h>
  49 #endif
  50 #endif /* HAVE_STATVFS */
  51 /* statfs() needs <sys/param.h> and <sys/mount.h> on BSD systems */
  52 #if HAVE_SYS_PARAM_H
  53 #include <sys/param.h>
  54 #endif
  55 #if HAVE_SYS_MOUNT_H
  56 #include <sys/mount.h>
  57 #endif
  58 /* Windows and Linux use sys/vfs.h */
  59 #if HAVE_SYS_VFS_H
  60 #include <sys/vfs.h>
  61 #endif
  62
  63 #include "StoreHashIndex.h"
  64
  65 static STDIRSELECT storeDirSelectSwapDirRoundRobin;
  66 static STDIRSELECT storeDirSelectSwapDirLeastLoad;
  67
  68 /*
  69  * store_dirs_rebuilding is initialized to _1_ as a hack so that
  70  * storeDirWriteCleanLogs() doesn't try to do anything unless _all_
  71  * cache_dirs have been read.  For example, without this hack, Squid
  72  * will try to write clean log files if -kparse fails (becasue it
  73  * calls fatal()).
  74  */
  75 int StoreController::store_dirs_rebuilding = 1;
  76
  77 StoreController::StoreController() : swapDir (new StoreHashIndex())
  78     , memStore(NULL)
  79 {}
  80
  81 StoreController::~StoreController()
  82 {
  83     delete memStore;
  84 }
  85
  86 /*
  87  * This function pointer is set according to 'store_dir_select_algorithm'
  88  * in squid.conf.
  89  */
  90 STDIRSELECT *storeDirSelectSwapDir = storeDirSelectSwapDirLeastLoad;
  91
  92 void
  93 StoreController::init()
  94 {
  95     if (UsingSmp() && IamWorkerProcess()) {
  96         memStore = new MemStore;
  97         memStore->init();
  98     }
  99
 100     swapDir->init();
 101
 102     if (0 == strcasecmp(Config.store_dir_select_algorithm, "round-robin")) {
 103         storeDirSelectSwapDir = storeDirSelectSwapDirRoundRobin;
 104         debugs(47, 1, "Using Round Robin store dir selection");
 105     } else {
 106         storeDirSelectSwapDir = storeDirSelectSwapDirLeastLoad;
 107         debugs(47, 1, "Using Least Load store dir selection");
 108     }
 109 }
 110
 111 void
 112 StoreController::createOneStore(Store &aStore)
 113 {
 114     /*
 115      * On Windows, fork() is not available.
 116      * The following is a workaround for create store directories sequentially
 117      * when running on native Windows port.
 118      */
 119 #ifndef _SQUID_MSWIN_
 120
 121     if (fork())
 122         return;
 123
 124 #endif
 125
 126     aStore.create();
 127
 128 #ifndef _SQUID_MSWIN_
 129
 130     exit(0);
 131
 132 #endif
 133 }
 134
 135 void
 136 StoreController::create()
 137 {
 138     swapDir->create();
 139
 140 #ifndef _SQUID_MSWIN_
 141
 142     pid_t pid;
 143
 144     do {
 145         int status;
 146 #ifdef _SQUID_NEXT_
 147
 148         pid = wait3(&status, WNOHANG, NULL);
 149 #else
 150
 151         pid = waitpid(-1, &status, 0);
 152 #endif
 153
 154     } while (pid > 0 || (pid < 0 && errno == EINTR));
 155
 156 #endif
 157 }
 158
 159 /**
 160  * Determine whether the given directory can handle this object
 161  * size
 162  *
 163  * Note: if the object size is -1, then the only swapdirs that
 164  * will return true here are ones that have min and max unset,
 165  * ie any-sized-object swapdirs. This is a good thing.
 166  */
 167 bool
 168 SwapDir::objectSizeIsAcceptable(int64_t objsize) const
 169 {
 170     // If the swapdir has no range limits, then it definitely can
 171     if (min_objsize <= 0 && max_objsize == -1)
 172         return true;
 173
 174     /*
 175      * If the object size is -1 and the storedir has limits we
 176      * can't store it there.
 177      */
 178     if (objsize == -1)
 179         return false;
 180
 181     // Else, make sure that the object size will fit.
 182     return min_objsize <= objsize && max_objsize > objsize;
 183 }
 184
 185
 186 /*
 187  * This new selection scheme simply does round-robin on all SwapDirs.
 188  * A SwapDir is skipped if it is over the max_size (100%) limit, or
 189  * overloaded.
 190  */
 191 static int
 192 storeDirSelectSwapDirRoundRobin(const StoreEntry * e)
 193 {
 194     static int dirn = 0;
 195     int i;
 196     int load;
 197     RefCount<SwapDir> sd;
 198
 199     // e->objectLen() is negative at this point when we are still STORE_PENDING
 200     ssize_t objsize = e->mem_obj->expectedReplySize();
 201     if (objsize != -1)
 202         objsize += e->mem_obj->swap_hdr_sz;
 203
 204     for (i = 0; i < Config.cacheSwap.n_configured; i++) {
 205         if (++dirn >= Config.cacheSwap.n_configured)
 206             dirn = 0;
 207
 208         sd = dynamic_cast<SwapDir *>(INDEXSD(dirn));
 209
 210         if (!sd->canStore(*e, objsize, load))
 211             continue;
 212
 213         if (load < 0 || load > 1000) {
 214             continue;
 215         }
 216
 217         return dirn;
 218     }
 219
 220     return -1;
 221 }
 222
 223 /*
 224  * Spread load across all of the store directories
 225  *
 226  * Note: We should modify this later on to prefer sticking objects
 227  * in the *tightest fit* swapdir to conserve space, along with the
 228  * actual swapdir usage. But for now, this hack will do while
 229  * testing, so you should order your swapdirs in the config file
 230  * from smallest maxobjsize to unlimited (-1) maxobjsize.
 231  *
 232  * We also have to choose nleast == nconf since we need to consider
 233  * ALL swapdirs, regardless of state. Again, this is a hack while
 234  * we sort out the real usefulness of this algorithm.
 235  */
 236 static int
 237 storeDirSelectSwapDirLeastLoad(const StoreEntry * e)
 238 {
 239     uint64_t most_free = 0;
 240     ssize_t least_objsize = -1;
 241     int least_load = INT_MAX;
 242     int load;
 243     int dirn = -1;
 244     int i;
 245     RefCount<SwapDir> SD;
 246
 247     // e->objectLen() is negative at this point when we are still STORE_PENDING
 248     ssize_t objsize = e->mem_obj->expectedReplySize();
 249
 250     if (objsize != -1)
 251         objsize += e->mem_obj->swap_hdr_sz;
 252
 253     for (i = 0; i < Config.cacheSwap.n_configured; i++) {
 254         SD = dynamic_cast<SwapDir *>(INDEXSD(i));
 255         SD->flags.selected = 0;
 256
 257         if (!SD->canStore(*e, objsize, load))
 258             continue;
 259
 260         if (load < 0 || load > 1000)
 261             continue;
 262
 263         if (load > least_load)
 264             continue;
 265
 266         const uint64_t cur_free = (SD->max_size << 10) - SD->currentSize();
 267
 268         /* If the load is equal, then look in more details */
 269         if (load == least_load) {
 270             /* closest max_objsize fit */
 271
 272             if (least_objsize != -1)
 273                 if (SD->max_objsize > least_objsize || SD->max_objsize == -1)
 274                     continue;
 275
 276             /* most free */
 277             if (cur_free < most_free)
 278                 continue;
 279         }
 280
 281         least_load = load;
 282         least_objsize = SD->max_objsize;
 283         most_free = cur_free;
 284         dirn = i;
 285     }
 286
 287     if (dirn >= 0)
 288         dynamic_cast<SwapDir *>(INDEXSD(dirn))->flags.selected = 1;
 289
 290     return dirn;
 291 }
 292
 293 /*
 294  * An entry written to the swap log MUST have the following
 295  * properties.
 296  *   1.  It MUST be a public key.  It does no good to log
 297  *       a public ADD, change the key, then log a private
 298  *       DEL.  So we need to log a DEL before we change a
 299  *       key from public to private.
 300  *   2.  It MUST have a valid (> -1) swap_filen.
 301  */
 302 void
 303 storeDirSwapLog(const StoreEntry * e, int op)
 304 {
 305     assert (e);
 306     assert(!EBIT_TEST(e->flags, KEY_PRIVATE));
 307     assert(e->swap_filen >= 0);
 308     /*
 309      * icons and such; don't write them to the swap log
 310      */
 311
 312     if (EBIT_TEST(e->flags, ENTRY_SPECIAL))
 313         return;
 314
 315     assert(op > SWAP_LOG_NOP && op < SWAP_LOG_MAX);
 316
 317     debugs(20, 3, "storeDirSwapLog: " <<
 318            swap_log_op_str[op] << " " <<
 319            e->getMD5Text() << " " <<
 320            e->swap_dirn << " " <<
 321            std::hex << std::uppercase << std::setfill('0') << std::setw(8) << e->swap_filen);
 322
 323     dynamic_cast<SwapDir *>(INDEXSD(e->swap_dirn))->logEntry(*e, op);
 324 }
 325
 326 void
 327 StoreController::updateSize(int64_t size, int sign)
 328 {
 329     fatal("StoreController has no independent size\n");
 330 }
 331
 332 void
 333 SwapDir::updateSize(int64_t size, int sign)
 334 {
 335     const int64_t blks = (size + fs.blksize - 1) / fs.blksize;
 336     const int64_t k = blks * fs.blksize * sign;
 337     cur_size += k;
 338
 339     if (sign > 0)
 340         n_disk_objects++;
 341     else if (sign < 0)
 342         n_disk_objects--;
 343 }
 344
 345 void
 346 StoreController::stat(StoreEntry &output) const
 347 {
 348     const double currentSizeInKB = currentSize() / 1024.0;
 349     storeAppendPrintf(&output, "Store Directory Statistics:\n");
 350     storeAppendPrintf(&output, "Store Entries          : %lu\n",
 351                       (unsigned long int)StoreEntry::inUseCount());
 352     storeAppendPrintf(&output, "Maximum Swap Size      : %"PRIu64" KB\n",
 353                       maxSize());
 354     storeAppendPrintf(&output, "Current Store Swap Size: %.2f KB\n",
 355                       currentSizeInKB);
 356     storeAppendPrintf(&output, "Current Capacity       : %.2f%% used, %.2f%% free\n",
 357                       Math::doublePercent(currentSizeInKB, maxSize()),
 358                       Math::doublePercent((maxSize() - currentSizeInKB), maxSize()));
 359
 360     if (memStore)
 361         memStore->stat(output);
 362
 363     /* now the swapDir */
 364     swapDir->stat(output);
 365 }
 366
 367 /* if needed, this could be taught to cache the result */
 368 uint64_t
 369 StoreController::maxSize() const
 370 {
 371     /* TODO: include memory cache ? */
 372     return swapDir->maxSize();
 373 }
 374
 375 uint64_t
 376 StoreController::minSize() const
 377 {
 378     /* TODO: include memory cache ? */
 379     return swapDir->minSize();
 380 }
 381
 382 uint64_t
 383 StoreController::currentSize() const
 384 {
 385     return swapDir->currentSize();
 386 }
 387
 388 uint64_t
 389 StoreController::currentCount() const
 390 {
 391     return swapDir->currentCount();
 392 }
 393
 394 int64_t
 395 StoreController::maxObjectSize() const
 396 {
 397     return swapDir->maxObjectSize();
 398 }
 399
 400 void
 401 SwapDir::diskFull()
 402 {
 403     if (currentSize() >= max_size << 10)
 404         return;
 405
 406     max_size = currentSize() >> 10;
 407
 408     debugs(20, 1, "WARNING: Shrinking cache_dir #" << index << " to " << currentSize() / 1024.0 << " KB");
 409 }
 410
 411 void
 412 storeDirOpenSwapLogs(void)
 413 {
 414     for (int dirn = 0; dirn < Config.cacheSwap.n_configured; ++dirn)
 415         dynamic_cast<SwapDir *>(INDEXSD(dirn))->openLog();
 416 }
 417
 418 void
 419 storeDirCloseSwapLogs(void)
 420 {
 421     for (int dirn = 0; dirn < Config.cacheSwap.n_configured; ++dirn)
 422         dynamic_cast<SwapDir *>(INDEXSD(dirn))->closeLog();
 423 }
 424
 425 /*
 426  *  storeDirWriteCleanLogs
 427  *
 428  *  Writes a "clean" swap log file from in-memory metadata.
 429  *  This is a rewrite of the original function to troll each
 430  *  StoreDir and write the logs, and flush at the end of
 431  *  the run. Thanks goes to Eric Stern, since this solution
 432  *  came out of his COSS code.
 433  */
 434 int
 435 storeDirWriteCleanLogs(int reopen)
 436 {
 437     const StoreEntry *e = NULL;
 438     int n = 0;
 439
 440     struct timeval start;
 441     double dt;
 442     RefCount<SwapDir> sd;
 443     int dirn;
 444     int notdone = 1;
 445
 446     if (StoreController::store_dirs_rebuilding) {
 447         debugs(20, 1, "Not currently OK to rewrite swap log.");
 448         debugs(20, 1, "storeDirWriteCleanLogs: Operation aborted.");
 449         return 0;
 450     }
 451
 452     debugs(20, 1, "storeDirWriteCleanLogs: Starting...");
 453     getCurrentTime();
 454     start = current_time;
 455
 456     for (dirn = 0; dirn < Config.cacheSwap.n_configured; dirn++) {
 457         sd = dynamic_cast<SwapDir *>(INDEXSD(dirn));
 458
 459         if (sd->writeCleanStart() < 0) {
 460             debugs(20, 1, "log.clean.start() failed for dir #" << sd->index);
 461             continue;
 462         }
 463     }
 464
 465     /*
 466      * This may look inefficient as CPU wise it is more efficient to do this
 467      * sequentially, but I/O wise the parallellism helps as it allows more
 468      * hdd spindles to be active.
 469      */
 470     while (notdone) {
 471         notdone = 0;
 472
 473         for (dirn = 0; dirn < Config.cacheSwap.n_configured; dirn++) {
 474             sd = dynamic_cast<SwapDir *>(INDEXSD(dirn));
 475
 476             if (NULL == sd->cleanLog)
 477                 continue;
 478
 479             e = sd->cleanLog->nextEntry();
 480
 481             if (!e)
 482                 continue;
 483
 484             notdone = 1;
 485
 486             if (!sd->canLog(*e))
 487                 continue;
 488
 489             sd->cleanLog->write(*e);
 490
 491             if ((++n & 0xFFFF) == 0) {
 492                 getCurrentTime();
 493                 debugs(20, 1, "  " << std::setw(7) << n  <<
 494                        " entries written so far.");
 495             }
 496         }
 497     }
 498
 499     /* Flush */
 500     for (dirn = 0; dirn < Config.cacheSwap.n_configured; dirn++)
 501         dynamic_cast<SwapDir *>(INDEXSD(dirn))->writeCleanDone();
 502
 503     if (reopen)
 504         storeDirOpenSwapLogs();
 505
 506     getCurrentTime();
 507
 508     dt = tvSubDsec(start, current_time);
 509
 510     debugs(20, 1, "  Finished.  Wrote " << n << " entries.");
 511     debugs(20, 1, "  Took "<< std::setw(3)<< std::setprecision(2) << dt <<
 512            " seconds ("<< std::setw(6) << ((double) n / (dt > 0.0 ? dt : 1.0)) << " entries/sec).");
 513
 514
 515     return n;
 516 }
 517
 518 StoreSearch *
 519 StoreController::search(String const url, HttpRequest *request)
 520 {
 521     /* cheat, for now you can't search the memory hot cache */
 522     return swapDir->search(url, request);
 523 }
 524
 525 StorePointer
 526 StoreHashIndex::store(int const x) const
 527 {
 528     return INDEXSD(x);
 529 }
 530
 531 SwapDir &
 532 StoreHashIndex::dir(const int i) const
 533 {
 534     SwapDir *sd = dynamic_cast<SwapDir*>(INDEXSD(i));
 535     assert(sd);
 536     return *sd;
 537 }
 538
 539 void
 540 StoreController::sync(void)
 541 {
 542     if (memStore)
 543         memStore->sync();
 544     swapDir->sync();
 545 }
 546
 547 /*
 548  * handle callbacks all avaliable fs'es
 549  */
 550 int
 551 StoreController::callback()
 552 {
 553     /* This will likely double count. Thats ok. */
 554     PROF_start(storeDirCallback);
 555
 556     /* mem cache callbacks ? */
 557     int result = swapDir->callback();
 558
 559     PROF_stop(storeDirCallback);
 560
 561     return result;
 562 }
 563
 564 int
 565 storeDirGetBlkSize(const char *path, int *blksize)
 566 {
 567 #if HAVE_STATVFS
 568
 569     struct statvfs sfs;
 570
 571     if (statvfs(path, &sfs)) {
 572         debugs(50, 1, "" << path << ": " << xstrerror());
 573         *blksize = 2048;
 574         return 1;
 575     }
 576
 577     *blksize = (int) sfs.f_frsize;
 578 #else
 579
 580     struct statfs sfs;
 581
 582     if (statfs(path, &sfs)) {
 583         debugs(50, 1, "" << path << ": " << xstrerror());
 584         *blksize = 2048;
 585         return 1;
 586     }
 587
 588     *blksize = (int) sfs.f_bsize;
 589 #endif
 590     /*
 591      * Sanity check; make sure we have a meaningful value.
 592      */
 593
 594     if (*blksize < 512)
 595         *blksize = 2048;
 596
 597     return 0;
 598 }
 599
 600 #define fsbtoblk(num, fsbs, bs) \
 601     (((fsbs) != 0 && (fsbs) < (bs)) ? \
 602             (num) / ((bs) / (fsbs)) : (num) * ((fsbs) / (bs)))
 603 int
 604 storeDirGetUFSStats(const char *path, int *totl_kb, int *free_kb, int *totl_in, int *free_in)
 605 {
 606 #if HAVE_STATVFS
 607
 608     struct statvfs sfs;
 609
 610     if (statvfs(path, &sfs)) {
 611         debugs(50, 1, "" << path << ": " << xstrerror());
 612         return 1;
 613     }
 614
 615     *totl_kb = (int) fsbtoblk(sfs.f_blocks, sfs.f_frsize, 1024);
 616     *free_kb = (int) fsbtoblk(sfs.f_bfree, sfs.f_frsize, 1024);
 617     *totl_in = (int) sfs.f_files;
 618     *free_in = (int) sfs.f_ffree;
 619 #else
 620
 621     struct statfs sfs;
 622
 623     if (statfs(path, &sfs)) {
 624         debugs(50, 1, "" << path << ": " << xstrerror());
 625         return 1;
 626     }
 627
 628     *totl_kb = (int) fsbtoblk(sfs.f_blocks, sfs.f_bsize, 1024);
 629     *free_kb = (int) fsbtoblk(sfs.f_bfree, sfs.f_bsize, 1024);
 630     *totl_in = (int) sfs.f_files;
 631     *free_in = (int) sfs.f_ffree;
 632 #endif
 633
 634     return 0;
 635 }
 636
 637 void
 638 allocate_new_swapdir(SquidConfig::_cacheSwap * swap)
 639 {
 640     if (swap->swapDirs == NULL) {
 641         swap->n_allocated = 4;
 642         swap->swapDirs = static_cast<SwapDir::Pointer *>(xcalloc(swap->n_allocated, sizeof(SwapDir::Pointer)));
 643     }
 644
 645     if (swap->n_allocated == swap->n_configured) {
 646         swap->n_allocated <<= 1;
 647         SwapDir::Pointer *const tmp = static_cast<SwapDir::Pointer *>(xcalloc(swap->n_allocated, sizeof(SwapDir::Pointer)));
 648         memcpy(tmp, swap->swapDirs, swap->n_configured * sizeof(SwapDir *));
 649         xfree(swap->swapDirs);
 650         swap->swapDirs = tmp;
 651     }
 652 }
 653
 654 void
 655 free_cachedir(SquidConfig::_cacheSwap * swap)
 656 {
 657     int i;
 658     /* DON'T FREE THESE FOR RECONFIGURE */
 659
 660     if (reconfiguring)
 661         return;
 662
 663     for (i = 0; i < swap->n_configured; i++) {
 664         /* TODO XXX this lets the swapdir free resources asynchronously
 665         * swap->swapDirs[i]->deactivate();
 666         * but there may be such a means already.
 667         * RBC 20041225
 668         */
 669         swap->swapDirs[i] = NULL;
 670     }
 671
 672     safe_free(swap->swapDirs);
 673     swap->swapDirs = NULL;
 674     swap->n_allocated = 0;
 675     swap->n_configured = 0;
 676 }
 677
 678 /* this should be a virtual method on StoreEntry,
 679  * i.e. e->referenced()
 680  * so that the entry can notify the creating Store
 681  */
 682 void
 683 StoreController::reference(StoreEntry &e)
 684 {
 685     /* Notify the fs that we're referencing this object again */
 686
 687     if (e.swap_dirn > -1)
 688         e.store()->reference(e);
 689
 690     // Notify the memory cache that we're referencing this object again
 691     if (memStore && e.mem_status == IN_MEMORY)
 692         memStore->reference(e);
 693
 694     // TODO: move this code to a non-shared memory cache class when we have it
 695     if (e.mem_obj) {
 696         if (mem_policy->Referenced)
 697             mem_policy->Referenced(mem_policy, &e, &e.mem_obj->repl);
 698     }
 699 }
 700
 701 void
 702 StoreController::dereference(StoreEntry & e)
 703 {
 704     /* Notify the fs that we're not referencing this object any more */
 705
 706     if (e.swap_filen > -1)
 707         e.store()->dereference(e);
 708
 709     // Notify the memory cache that we're not referencing this object any more
 710     if (memStore && e.mem_status == IN_MEMORY)
 711         memStore->dereference(e);
 712
 713     // TODO: move this code to a non-shared memory cache class when we have it
 714     if (e.mem_obj) {
 715         if (mem_policy->Dereferenced)
 716             mem_policy->Dereferenced(mem_policy, &e, &e.mem_obj->repl);
 717     }
 718 }
 719
 720 StoreEntry *
 721 StoreController::get(const cache_key *key)
 722 {
 723     if (StoreEntry *e = swapDir->get(key)) {
 724         // TODO: ignore and maybe handleIdleEntry() unlocked intransit entries
 725         // because their backing store slot may be gone already.
 726         debugs(20, 3, HERE << "got in-transit entry: " << *e);
 727         return e;
 728     }
 729
 730     if (memStore) {
 731         if (StoreEntry *e = memStore->get(key)) {
 732             debugs(20, 3, HERE << "got mem-cached entry: " << *e);
 733             return e;
 734         }
 735     }
 736
 737     // TODO: this disk iteration is misplaced; move to StoreHashIndex
 738     if (const int cacheDirs = Config.cacheSwap.n_configured) {
 739         // ask each cache_dir until the entry is found; use static starting
 740         // point to avoid asking the same subset of disks more often
 741         // TODO: coordinate with put() to be able to guess the right disk often
 742         static int idx = 0;
 743         for (int n = 0; n < cacheDirs; ++n) {
 744             idx = (idx + 1) % cacheDirs;
 745             SwapDir *sd = dynamic_cast<SwapDir*>(INDEXSD(idx));
 746             if (!sd->active())
 747                 continue;
 748
 749             if (StoreEntry *e = sd->get(key)) {
 750                 debugs(20, 3, HERE << "cache_dir " << idx <<
 751                     " got cached entry: " << *e);
 752                 return e;
 753             }
 754         }
 755     }
 756
 757     debugs(20, 4, HERE << "none of " << Config.cacheSwap.n_configured <<
 758         " cache_dirs have " << storeKeyText(key));
 759     return NULL;
 760 }
 761
 762 void
 763 StoreController::get(String const key, STOREGETCLIENT aCallback, void *aCallbackData)
 764 {
 765     fatal("not implemented");
 766 }
 767
 768 void
 769 StoreController::handleIdleEntry(StoreEntry &e)
 770 {
 771     bool keepInLocalMemory = false;
 772     if (memStore) {
 773         memStore->considerKeeping(e);
 774         // leave keepInLocalMemory false; memStore maintains its own cache
 775     } else {
 776         keepInLocalMemory = e.memoryCachable() && // entry is in good shape and
 777             // the local memory cache is not overflowing
 778             (mem_node::InUseCount() <= store_pages_max);
 779     }
 780
 781     dereference(e);
 782
 783     // XXX: Rock store specific: Since each SwapDir controls its index,
 784     // unlocked entries should not stay in the global store_table.
 785     if (fileno >= 0) {
 786         debugs(20, 5, HERE << "destroying unlocked entry: " << &e << ' ' << e);
 787         destroyStoreEntry(static_cast<hash_link*>(&e));
 788         return;
 789     }
 790
 791     // TODO: move this into [non-shared] memory cache class when we have one
 792     if (keepInLocalMemory) {
 793         e.setMemStatus(IN_MEMORY);
 794         e.mem_obj->unlinkRequest();
 795     } else {
 796         e.purgeMem(); // may free e
 797     }
 798 }
 799
 800 StoreHashIndex::StoreHashIndex()
 801 {
 802     if (store_table)
 803         abort();
 804     assert (store_table == NULL);
 805 }
 806
 807 StoreHashIndex::~StoreHashIndex()
 808 {
 809     if (store_table) {
 810         hashFreeItems(store_table, destroyStoreEntry);
 811         hashFreeMemory(store_table);
 812         store_table = NULL;
 813     }
 814 }
 815
 816 int
 817 StoreHashIndex::callback()
 818 {
 819     int result = 0;
 820     int j;
 821     static int ndir = 0;
 822
 823     do {
 824         j = 0;
 825
 826         for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 827             if (ndir >= Config.cacheSwap.n_configured)
 828                 ndir = ndir % Config.cacheSwap.n_configured;
 829
 830             int temp_result = store(ndir)->callback();
 831
 832             ++ndir;
 833
 834             j += temp_result;
 835
 836             result += temp_result;
 837
 838             if (j > 100)
 839                 fatal ("too much io\n");
 840         }
 841     } while (j > 0);
 842
 843     ndir++;
 844
 845     return result;
 846 }
 847
 848 void
 849 StoreHashIndex::create()
 850 {
 851     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 852         if (dir(i).active())
 853             store(i)->create();
 854     }
 855 }
 856
 857 /* Lookup an object in the cache.
 858  * return just a reference to object, don't start swapping in yet. */
 859 StoreEntry *
 860 StoreHashIndex::get(const cache_key *key)
 861 {
 862     PROF_start(storeGet);
 863     debugs(20, 3, "storeGet: looking up " << storeKeyText(key));
 864     StoreEntry *p = static_cast<StoreEntry *>(hash_lookup(store_table, key));
 865     PROF_stop(storeGet);
 866     return p;
 867 }
 868
 869 void
 870 StoreHashIndex::get(String const key, STOREGETCLIENT aCallback, void *aCallbackData)
 871 {
 872     fatal("not implemented");
 873 }
 874
 875 void
 876 StoreHashIndex::init()
 877 {
 878     /* Calculate size of hash table (maximum currently 64k buckets).  */
 879     /* this is very bogus, its specific to the any Store maintaining an
 880      * in-core index, not global */
 881     size_t buckets = (Store::Root().maxSize() + ( Config.memMaxSize >> 10)) / Config.Store.avgObjectSize;
 882     debugs(20, 1, "Swap maxSize " << Store::Root().maxSize() <<
 883            " + " << ( Config.memMaxSize >> 10) << " KB, estimated " << buckets << " objects");
 884     buckets /= Config.Store.objectsPerBucket;
 885     debugs(20, 1, "Target number of buckets: " << buckets);
 886     /* ideally the full scan period should be configurable, for the
 887      * moment it remains at approximately 24 hours.  */
 888     store_hash_buckets = storeKeyHashBuckets(buckets);
 889     debugs(20, 1, "Using " << store_hash_buckets << " Store buckets");
 890     debugs(20, 1, "Max Mem  size: " << ( Config.memMaxSize >> 10) << " KB");
 891     debugs(20, 1, "Max Swap size: " << Store::Root().maxSize() << " KB");
 892
 893     store_table = hash_create(storeKeyHashCmp,
 894                               store_hash_buckets, storeKeyHashHash);
 895
 896     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 897         /* this starts a search of the store dirs, loading their
 898          * index. under the new Store api this should be
 899          * driven by the StoreHashIndex, not by each store.
 900         *
 901         * That is, the HashIndex should perform a search of each dir it is
 902         * indexing to do the hash insertions. The search is then able to
 903         * decide 'from-memory', or 'from-clean-log' or 'from-dirty-log' or
 904         * 'from-no-log'.
 905         *
 906          * Step 1: make the store rebuilds use a search internally
 907         * Step 2: change the search logic to use the four modes described
 908         *         above
 909         * Step 3: have the hash index walk the searches itself.
 910          */
 911         if (dir(i).active())
 912             store(i)->init();
 913     }
 914 }
 915
 916 uint64_t
 917 StoreHashIndex::maxSize() const
 918 {
 919     uint64_t result = 0;
 920
 921     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 922         if (dir(i).doReportStat())
 923             result += store(i)->maxSize();
 924     }
 925
 926     return result;
 927 }
 928
 929 uint64_t
 930 StoreHashIndex::minSize() const
 931 {
 932     uint64_t result = 0;
 933
 934     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 935         if (dir(i).doReportStat())
 936             result += store(i)->minSize();
 937     }
 938
 939     return result;
 940 }
 941
 942 uint64_t
 943 StoreHashIndex::currentSize() const
 944 {
 945     uint64_t result = 0;
 946
 947     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 948         if (dir(i).doReportStat())
 949             result += store(i)->currentSize();
 950     }
 951
 952     return result;
 953 }
 954
 955 uint64_t
 956 StoreHashIndex::currentCount() const
 957 {
 958     uint64_t result = 0;
 959
 960     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 961         if (dir(i).doReportStat())
 962             result += store(i)->currentCount();
 963     }
 964
 965     return result;
 966 }
 967
 968 int64_t
 969 StoreHashIndex::maxObjectSize() const
 970 {
 971     int64_t result = -1;
 972
 973     for (int i = 0; i < Config.cacheSwap.n_configured; i++) {
 974         if (dir(i).active() && store(i)->maxObjectSize() > result)
 975             result = store(i)->maxObjectSize();
 976     }
 977
 978     return result;
 979 }
 980
 981 void
 982 StoreHashIndex::stat(StoreEntry & output) const
 983 {
 984     int i;
 985
 986     /* Now go through each store, calling its stat routine */
 987
 988     for (i = 0; i < Config.cacheSwap.n_configured; i++) {
 989         storeAppendPrintf(&output, "\n");
 990         store(i)->stat(output);
 991     }
 992 }
 993
 994 void
 995 StoreHashIndex::reference(StoreEntry&)
 996 {}
 997
 998 void
 999 StoreHashIndex::dereference(StoreEntry&)
1000 {}
1001
1002 void
1003 StoreHashIndex::maintain()
1004 {
1005     int i;
1006     /* walk each fs */
1007
1008     for (i = 0; i < Config.cacheSwap.n_configured; i++) {
1009         /* XXX FixMe: This should be done "in parallell" on the different
1010          * cache_dirs, not one at a time.
1011          */
1012         /* call the maintain function .. */
1013         store(i)->maintain();
1014     }
1015 }
1016
1017 void
1018 StoreHashIndex::updateSize(int64_t, int)
1019 {}
1020
1021 void
1022 StoreHashIndex::sync()
1023 {
1024     for (int i = 0; i < Config.cacheSwap.n_configured; ++i)
1025         store(i)->sync();
1026 }
1027
1028 StoreSearch *
1029 StoreHashIndex::search(String const url, HttpRequest *)
1030 {
1031     if (url.size())
1032         fatal ("Cannot search by url yet\n");
1033
1034     return new StoreSearchHashIndex (this);
1035 }
1036
1037 CBDATA_CLASS_INIT(StoreSearchHashIndex);
1038
1039 StoreSearchHashIndex::StoreSearchHashIndex(RefCount<StoreHashIndex> aSwapDir) : sd(aSwapDir), _done (false), bucket (0)
1040 {}
1041
1042 /* do not link
1043 StoreSearchHashIndex::StoreSearchHashIndex(StoreSearchHashIndex const &);
1044 */
1045
1046 StoreSearchHashIndex::~StoreSearchHashIndex()
1047 {}
1048
1049 void
1050 StoreSearchHashIndex::next(void (aCallback)(void *), void *aCallbackData)
1051 {
1052     next();
1053     aCallback (aCallbackData);
1054 }
1055
1056 bool
1057 StoreSearchHashIndex::next()
1058 {
1059     if (entries.size())
1060         entries.pop_back();
1061
1062     while (!isDone() && !entries.size())
1063         copyBucket();
1064
1065     return currentItem() != NULL;
1066 }
1067
1068 bool
1069 StoreSearchHashIndex::error() const
1070 {
1071     return false;
1072 }
1073
1074 bool
1075 StoreSearchHashIndex::isDone() const
1076 {
1077     return bucket >= store_hash_buckets || _done;
1078 }
1079
1080 StoreEntry *
1081 StoreSearchHashIndex::currentItem()
1082 {
1083     if (!entries.size())
1084         return NULL;
1085
1086     return entries.back();
1087 }
1088
1089 void
1090 StoreSearchHashIndex::copyBucket()
1091 {
1092     /* probably need to lock the store entries...
1093      * we copy them all to prevent races on the links. */
1094     debugs(47, 3, "StoreSearchHashIndex::copyBucket #" << bucket);
1095     assert (!entries.size());
1096     hash_link *link_ptr = NULL;
1097     hash_link *link_next = NULL;
1098     link_next = hash_get_bucket(store_table, bucket);
1099
1100     while (NULL != (link_ptr = link_next)) {
1101         link_next = link_ptr->next;
1102         StoreEntry *e = (StoreEntry *) link_ptr;
1103
1104         entries.push_back(e);
1105     }
1106
1107     bucket++;
1108     debugs(47,3, "got entries: " << entries.size());
1109 }