src/store.cc

   1
   2 /*
   3  * $Id: store.cc,v 1.473 1998/11/21 02:13:30 wessels Exp $
   4  *
   5  * DEBUG: section 20    Storage Manager
   6  * AUTHOR: Harvest Derived
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  Duane Wessels and the University of California San Diego.  Please
  16  *  see the COPYRIGHT file for full details.  Squid incorporates
  17  *  software developed and/or copyrighted by other sources.  Please see
  18  *  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
  38 #define REBUILD_TIMESTAMP_DELTA_MAX 2
  39
  40 #define STORE_IN_MEM_BUCKETS            (229)
  41
  42 const char *memStatusStr[] =
  43 {
  44     "NOT_IN_MEMORY",
  45     "IN_MEMORY"
  46 };
  47
  48 const char *pingStatusStr[] =
  49 {
  50     "PING_NONE",
  51     "PING_WAITING",
  52     "PING_TIMEOUT",
  53     "PING_DONE"
  54 };
  55
  56 const char *storeStatusStr[] =
  57 {
  58     "STORE_OK",
  59     "STORE_PENDING",
  60     "STORE_ABORTED"
  61 };
  62
  63 const char *swapStatusStr[] =
  64 {
  65     "SWAPOUT_NONE",
  66     "SWAPOUT_OPENING",
  67     "SWAPOUT_WRITING",
  68     "SWAPOUT_DONE"
  69 };
  70
  71 typedef struct lock_ctrl_t {
  72     SIH *callback;
  73     void *callback_data;
  74     StoreEntry *e;
  75 } lock_ctrl_t;
  76
  77 /*
  78  * local function prototypes
  79  */
  80 static int storeCheckExpired(const StoreEntry *);
  81 static int storeEntryLocked(const StoreEntry *);
  82 static int storeEntryValidLength(const StoreEntry *);
  83 static void storeGetMemSpace(int);
  84 static void storeHashDelete(StoreEntry *);
  85 static MemObject *new_MemObject(const char *, const char *);
  86 static void destroy_MemObject(StoreEntry *);
  87 static FREE destroy_StoreEntry;
  88 static void storePurgeMem(StoreEntry *);
  89 static int getKeyCounter(void);
  90 static int storeKeepInMemory(const StoreEntry *);
  91 static OBJH storeCheckCachableStats;
  92
  93 /*
  94  * local variables
  95  */
  96 static dlink_list inmem_list;
  97 static int store_pages_high = 0;
  98 static int store_pages_low = 0;
  99 static int store_swap_high = 0;
 100 static int store_swap_low = 0;
 101 static int store_swap_mid = 0;
 102 static int store_maintain_rate;
 103
 104 static MemObject *
 105 new_MemObject(const char *url, const char *log_url)
 106 {
 107     MemObject *mem = memAllocate(MEM_MEMOBJECT);
 108     mem->reply = httpReplyCreate();
 109     mem->url = xstrdup(url);
 110     mem->log_url = xstrdup(log_url);
 111     mem->swapout.fd = -1;
 112     mem->object_sz = -1;
 113     mem->fd = -1;
 114     /* XXX account log_url */
 115     debug(20, 3) ("new_MemObject: returning %p\n", mem);
 116     return mem;
 117 }
 118
 119 StoreEntry *
 120 new_StoreEntry(int mem_obj_flag, const char *url, const char *log_url)
 121 {
 122     StoreEntry *e = NULL;
 123     e = memAllocate(MEM_STOREENTRY);
 124     if (mem_obj_flag)
 125         e->mem_obj = new_MemObject(url, log_url);
 126     debug(20, 3) ("new_StoreEntry: returning %p\n", e);
 127     e->expires = e->lastmod = e->lastref = e->timestamp = -1;
 128     return e;
 129 }
 130
 131 static void
 132 destroy_MemObject(StoreEntry * e)
 133 {
 134     MemObject *mem = e->mem_obj;
 135     const Ctx ctx = ctx_enter(mem->url);
 136     debug(20, 3) ("destroy_MemObject: destroying %p\n", mem);
 137     e->mem_obj = NULL;
 138     if (!shutting_down)
 139         assert(mem->swapout.fd == -1);
 140     stmemFree(&mem->data_hdr);
 141     mem->inmem_hi = 0;
 142     /* XXX account log_url */
 143 #if USE_ASYNC_IO
 144     while (mem->clients != NULL)
 145         storeUnregister(e, mem->clients->callback_data);
 146 #endif
 147     /*
 148      * There is no way to abort FD-less clients, so they might
 149      * still have mem->clients set if mem->fd == -1
 150      */
 151     assert(mem->fd == -1 || mem->clients == NULL);
 152     httpReplyDestroy(mem->reply);
 153     requestUnlink(mem->request);
 154     mem->request = NULL;
 155     ctx_exit(ctx);              /* must exit before we free mem->url */
 156     safe_free(mem->url);
 157     safe_free(mem->log_url);
 158     memFree(MEM_MEMOBJECT, mem);
 159 }
 160
 161 static void
 162 destroy_StoreEntry(void *data)
 163 {
 164     StoreEntry *e = data;
 165     debug(20, 3) ("destroy_StoreEntry: destroying %p\n", e);
 166     assert(e != NULL);
 167     if (e->mem_obj)
 168         destroy_MemObject(e);
 169     storeHashDelete(e);
 170     assert(e->key == NULL);
 171     memFree(MEM_STOREENTRY, e);
 172 }
 173
 174 /* ----- INTERFACE BETWEEN STORAGE MANAGER AND HASH TABLE FUNCTIONS --------- */
 175
 176 void
 177 storeHashInsert(StoreEntry * e, const cache_key * key)
 178 {
 179     debug(20, 3) ("storeHashInsert: Inserting Entry %p key '%s'\n",
 180         e, storeKeyText(key));
 181     e->key = storeKeyDup(key);
 182     hash_join(store_table, (hash_link *) e);
 183     dlinkAdd(e, &e->lru, &store_list);
 184 }
 185
 186 static void
 187 storeHashDelete(StoreEntry * e)
 188 {
 189     hash_remove_link(store_table, (hash_link *) e);
 190     dlinkDelete(&e->lru, &store_list);
 191     storeKeyFree(e->key);
 192     e->key = NULL;
 193 }
 194
 195 /* -------------------------------------------------------------------------- */
 196
 197
 198 /* get rid of memory copy of the object */
 199 /* Only call this if storeCheckPurgeMem(e) returns 1 */
 200 static void
 201 storePurgeMem(StoreEntry * e)
 202 {
 203     if (e->mem_obj == NULL)
 204         return;
 205     debug(20, 3) ("storePurgeMem: Freeing memory-copy of %s\n",
 206         storeKeyText(e->key));
 207     storeSetMemStatus(e, NOT_IN_MEMORY);
 208     destroy_MemObject(e);
 209     if (e->swap_status != SWAPOUT_DONE)
 210         storeRelease(e);
 211 }
 212
 213 void
 214 storeLockObject(StoreEntry * e)
 215 {
 216     if (e->lock_count++ == 0) {
 217         dlinkDelete(&e->lru, &store_list);
 218         dlinkAdd(e, &e->lru, &store_list);
 219     }
 220     debug(20, 3) ("storeLockObject: key '%s' count=%d\n",
 221         storeKeyText(e->key), (int) e->lock_count);
 222     e->lastref = squid_curtime;
 223 }
 224
 225 void
 226 storeReleaseRequest(StoreEntry * e)
 227 {
 228     if (EBIT_TEST(e->flags, RELEASE_REQUEST))
 229         return;
 230     debug(20, 3) ("storeReleaseRequest: '%s'\n", storeKeyText(e->key));
 231     EBIT_SET(e->flags, RELEASE_REQUEST);
 232     /*
 233      * Clear cachable flag here because we might get called before
 234      * anyone else even looks at the cachability flag.  Also, this
 235      * prevents httpMakePublic from really setting a public key.
 236      */
 237     EBIT_CLR(e->flags, ENTRY_CACHABLE);
 238     storeSetPrivateKey(e);
 239 }
 240
 241 /* unlock object, return -1 if object get released after unlock
 242  * otherwise lock_count */
 243 int
 244 storeUnlockObject(StoreEntry * e)
 245 {
 246     e->lock_count--;
 247     debug(20, 3) ("storeUnlockObject: key '%s' count=%d\n",
 248         storeKeyText(e->key), e->lock_count);
 249     if (e->lock_count)
 250         return (int) e->lock_count;
 251     if (e->store_status == STORE_PENDING) {
 252         assert(!EBIT_TEST(e->flags, ENTRY_DISPATCHED));
 253         EBIT_SET(e->flags, RELEASE_REQUEST);
 254     }
 255     assert(storePendingNClients(e) == 0);
 256     if (EBIT_TEST(e->flags, RELEASE_REQUEST))
 257         storeRelease(e);
 258     else if (storeKeepInMemory(e)) {
 259         storeSetMemStatus(e, IN_MEMORY);
 260         requestUnlink(e->mem_obj->request);
 261         e->mem_obj->request = NULL;
 262     } else {
 263         storePurgeMem(e);
 264         if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
 265             dlinkDelete(&e->lru, &store_list);
 266             dlinkAddTail(e, &e->lru, &store_list);
 267         }
 268     }
 269     return 0;
 270 }
 271
 272 /* Lookup an object in the cache.
 273  * return just a reference to object, don't start swapping in yet. */
 274 StoreEntry *
 275 storeGet(const cache_key * key)
 276 {
 277     debug(20, 3) ("storeGet: looking up %s\n", storeKeyText(key));
 278     return (StoreEntry *) hash_lookup(store_table, key);
 279 }
 280
 281 StoreEntry *
 282 storeGetPublic(const char *uri, const method_t method)
 283 {
 284     return storeGet(storeKeyPublic(uri, method));
 285 }
 286
 287 static int
 288 getKeyCounter(void)
 289 {
 290     static int key_counter = 0;
 291     if (++key_counter < 0)
 292         key_counter = 1;
 293     return key_counter;
 294 }
 295
 296 void
 297 storeSetPrivateKey(StoreEntry * e)
 298 {
 299     const cache_key *newkey;
 300     MemObject *mem = e->mem_obj;
 301     if (e->key && EBIT_TEST(e->flags, KEY_PRIVATE))
 302         return;                 /* is already private */
 303     if (e->key) {
 304         if (e->swap_file_number > -1)
 305             storeDirSwapLog(e, SWAP_LOG_DEL);
 306         storeHashDelete(e);
 307     }
 308     if (mem != NULL) {
 309         mem->id = getKeyCounter();
 310         newkey = storeKeyPrivate(mem->url, mem->method, mem->id);
 311     } else {
 312         newkey = storeKeyPrivate("JUNK", METHOD_NONE, getKeyCounter());
 313     }
 314     assert(hash_lookup(store_table, newkey) == NULL);
 315     EBIT_SET(e->flags, KEY_PRIVATE);
 316     storeHashInsert(e, newkey);
 317 }
 318
 319 void
 320 storeSetPublicKey(StoreEntry * e)
 321 {
 322     StoreEntry *e2 = NULL;
 323     const cache_key *newkey;
 324     MemObject *mem = e->mem_obj;
 325     if (e->key && !EBIT_TEST(e->flags, KEY_PRIVATE))
 326         return;                 /* is already public */
 327     assert(mem);
 328     /*
 329      * We can't make RELEASE_REQUEST objects public.  Depending on
 330      * when RELEASE_REQUEST gets set, we might not be swapping out
 331      * the object.  If we're not swapping out, then subsequent
 332      * store clients won't be able to access object data which has
 333      * been freed from memory.
 334      *
 335      * If RELEASE_REQUEST is set, then ENTRY_CACHABLE should not
 336      * be set, and storeSetPublicKey() should not be called.
 337      */
 338     assert(!EBIT_TEST(e->flags, RELEASE_REQUEST));
 339     newkey = storeKeyPublic(mem->url, mem->method);
 340     if ((e2 = (StoreEntry *) hash_lookup(store_table, newkey))) {
 341         debug(20, 3) ("storeSetPublicKey: Making old '%s' private.\n", mem->url);
 342         storeSetPrivateKey(e2);
 343         storeRelease(e2);
 344         newkey = storeKeyPublic(mem->url, mem->method);
 345     }
 346     if (e->key)
 347         storeHashDelete(e);
 348     EBIT_CLR(e->flags, KEY_PRIVATE);
 349     storeHashInsert(e, newkey);
 350     if (e->swap_file_number > -1)
 351         storeDirSwapLog(e, SWAP_LOG_ADD);
 352 }
 353
 354 StoreEntry *
 355 storeCreateEntry(const char *url, const char *log_url, request_flags flags, method_t method)
 356 {
 357     StoreEntry *e = NULL;
 358     MemObject *mem = NULL;
 359     debug(20, 3) ("storeCreateEntry: '%s'\n", url);
 360
 361     e = new_StoreEntry(STORE_ENTRY_WITH_MEMOBJ, url, log_url);
 362     e->lock_count = 1;          /* Note lock here w/o calling storeLock() */
 363     mem = e->mem_obj;
 364     mem->method = method;
 365     if (neighbors_do_private_keys || !flags.hierarchical)
 366         storeSetPrivateKey(e);
 367     else
 368         storeSetPublicKey(e);
 369     if (flags.cachable) {
 370         EBIT_SET(e->flags, ENTRY_CACHABLE);
 371         EBIT_CLR(e->flags, RELEASE_REQUEST);
 372     } else {
 373         EBIT_CLR(e->flags, ENTRY_CACHABLE);
 374         storeReleaseRequest(e);
 375     }
 376     e->store_status = STORE_PENDING;
 377     storeSetMemStatus(e, NOT_IN_MEMORY);
 378     e->swap_status = SWAPOUT_NONE;
 379     e->swap_file_number = -1;
 380     e->refcount = 0;
 381     e->lastref = squid_curtime;
 382     e->timestamp = 0;           /* set in storeTimestampsSet() */
 383     e->ping_status = PING_NONE;
 384     EBIT_SET(e->flags, ENTRY_VALIDATED);
 385 #ifdef PPNR_WIP
 386     EBIT_SET(e->flags, ENTRY_FWD_HDR_WAIT);
 387 #endif /* PPNR_WIP */
 388     return e;
 389 }
 390
 391 /* Mark object as expired */
 392 void
 393 storeExpireNow(StoreEntry * e)
 394 {
 395     debug(20, 3) ("storeExpireNow: '%s'\n", storeKeyText(e->key));
 396     e->expires = squid_curtime;
 397 }
 398
 399 /* Append incoming data from a primary server to an entry. */
 400 void
 401 storeAppend(StoreEntry * e, const char *buf, int len)
 402 {
 403     MemObject *mem = e->mem_obj;
 404     assert(mem != NULL);
 405     assert(len >= 0);
 406     if (len) {
 407         debug(20, 5) ("storeAppend: appending %d bytes for '%s'\n",
 408             len,
 409             storeKeyText(e->key));
 410         storeGetMemSpace(len);
 411         stmemAppend(&mem->data_hdr, buf, len);
 412         mem->inmem_hi += len;
 413     }
 414     if (EBIT_TEST(e->flags, DELAY_SENDING))
 415         return;
 416 #ifdef OPTIMISTIC_IO
 417     storeLockObject(e);
 418 #endif
 419     InvokeHandlers(e);
 420     storeCheckSwapOut(e);
 421 #ifdef OPTIMISTIC_IO
 422     storeUnlockObject(e);
 423 #endif
 424 }
 425
 426 #ifdef __STDC__
 427 void
 428 storeAppendPrintf(StoreEntry * e, const char *fmt,...)
 429 {
 430     va_list args;
 431     va_start(args, fmt);
 432 #else
 433 void
 434 storeAppendPrintf(va_alist)
 435      va_dcl
 436 {
 437     va_list args;
 438     StoreEntry *e = NULL;
 439     const char *fmt = NULL;
 440     va_start(args);
 441     e = va_arg(args, StoreEntry *);
 442     fmt = va_arg(args, char *);
 443 #endif
 444     storeAppendVPrintf(e, fmt, args);
 445     va_end(args);
 446 }
 447
 448 /* used be storeAppendPrintf and Packer */
 449 void
 450 storeAppendVPrintf(StoreEntry * e, const char *fmt, va_list vargs)
 451 {
 452     LOCAL_ARRAY(char, buf, 4096);
 453     buf[0] = '\0';
 454     vsnprintf(buf, 4096, fmt, vargs);
 455     storeAppend(e, buf, strlen(buf));
 456 }
 457
 458 struct _store_check_cachable_hist {
 459     struct {
 460         int non_get;
 461         int not_entry_cachable;
 462         int release_request;
 463         int wrong_content_length;
 464         int negative_cached;
 465         int too_big;
 466         int private_key;
 467         int too_many_open_files;
 468         int too_many_open_fds;
 469         int lru_age_too_low;
 470     } no;
 471     struct {
 472         int Default;
 473     } yes;
 474 } store_check_cachable_hist;
 475
 476 int
 477 storeTooManyDiskFilesOpen(void)
 478 {
 479     if (Config.max_open_disk_fds == 0)
 480         return 0;
 481     if (open_disk_fd > Config.max_open_disk_fds)
 482         return 1;
 483     return 0;
 484 }
 485
 486 int
 487 storeCheckCachable(StoreEntry * e)
 488 {
 489 #if CACHE_ALL_METHODS
 490     if (e->mem_obj->method != METHOD_GET) {
 491         debug(20, 2) ("storeCheckCachable: NO: non-GET method\n");
 492         store_check_cachable_hist.no.non_get++;
 493     } else
 494 #endif
 495     if (!EBIT_TEST(e->flags, ENTRY_CACHABLE)) {
 496         debug(20, 2) ("storeCheckCachable: NO: not cachable\n");
 497         store_check_cachable_hist.no.not_entry_cachable++;
 498     } else if (EBIT_TEST(e->flags, RELEASE_REQUEST)) {
 499         debug(20, 2) ("storeCheckCachable: NO: release requested\n");
 500         store_check_cachable_hist.no.release_request++;
 501     } else if (e->store_status == STORE_OK && EBIT_TEST(e->flags, ENTRY_BAD_LENGTH)) {
 502         debug(20, 2) ("storeCheckCachable: NO: wrong content-length\n");
 503         store_check_cachable_hist.no.wrong_content_length++;
 504     } else if (EBIT_TEST(e->flags, ENTRY_NEGCACHED)) {
 505         debug(20, 3) ("storeCheckCachable: NO: negative cached\n");
 506         store_check_cachable_hist.no.negative_cached++;
 507         return 0;               /* avoid release call below */
 508     } else if (e->mem_obj->inmem_hi > Config.Store.maxObjectSize) {
 509         debug(20, 2) ("storeCheckCachable: NO: too big\n");
 510         store_check_cachable_hist.no.too_big++;
 511     } else if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
 512         debug(20, 3) ("storeCheckCachable: NO: private key\n");
 513         store_check_cachable_hist.no.private_key++;
 514     } else if (storeTooManyDiskFilesOpen()) {
 515         debug(20, 2) ("storeCheckCachable: NO: too many disk files open\n");
 516         store_check_cachable_hist.no.too_many_open_files++;
 517     } else if (fdNFree() < RESERVED_FD) {
 518         debug(20, 2) ("storeCheckCachable: NO: too FD's open\n");
 519         store_check_cachable_hist.no.too_many_open_fds++;
 520     } else if (storeExpiredReferenceAge() < 300) {
 521         debug(20, 2) ("storeCheckCachable: NO: LRU Age = %d\n",
 522             storeExpiredReferenceAge());
 523         store_check_cachable_hist.no.lru_age_too_low++;
 524     } else {
 525         store_check_cachable_hist.yes.Default++;
 526         return 1;
 527     }
 528     storeReleaseRequest(e);
 529     EBIT_CLR(e->flags, ENTRY_CACHABLE);
 530     return 0;
 531 }
 532
 533 static void
 534 storeCheckCachableStats(StoreEntry * sentry)
 535 {
 536     storeAppendPrintf(sentry, "Category\t Count\n");
 537
 538     storeAppendPrintf(sentry, "no.non_get\t%d\n",
 539         store_check_cachable_hist.no.non_get);
 540     storeAppendPrintf(sentry, "no.not_entry_cachable\t%d\n",
 541         store_check_cachable_hist.no.not_entry_cachable);
 542     storeAppendPrintf(sentry, "no.release_request\t%d\n",
 543         store_check_cachable_hist.no.release_request);
 544     storeAppendPrintf(sentry, "no.wrong_content_length\t%d\n",
 545         store_check_cachable_hist.no.wrong_content_length);
 546     storeAppendPrintf(sentry, "no.negative_cached\t%d\n",
 547         store_check_cachable_hist.no.negative_cached);
 548     storeAppendPrintf(sentry, "no.too_big\t%d\n",
 549         store_check_cachable_hist.no.too_big);
 550     storeAppendPrintf(sentry, "no.private_key\t%d\n",
 551         store_check_cachable_hist.no.private_key);
 552     storeAppendPrintf(sentry, "no.too_many_open_files\t%d\n",
 553         store_check_cachable_hist.no.too_many_open_files);
 554     storeAppendPrintf(sentry, "no.too_many_open_fds\t%d\n",
 555         store_check_cachable_hist.no.too_many_open_fds);
 556     storeAppendPrintf(sentry, "no.lru_age_too_low\t%d\n",
 557         store_check_cachable_hist.no.lru_age_too_low);
 558     storeAppendPrintf(sentry, "yes.default\t%d\n",
 559         store_check_cachable_hist.yes.Default);
 560 }
 561
 562 /* Complete transfer into the local cache.  */
 563 void
 564 storeComplete(StoreEntry * e)
 565 {
 566     debug(20, 3) ("storeComplete: '%s'\n", storeKeyText(e->key));
 567     assert(e->store_status == STORE_PENDING);
 568     e->mem_obj->object_sz = e->mem_obj->inmem_hi;
 569     e->store_status = STORE_OK;
 570     assert(e->mem_status == NOT_IN_MEMORY);
 571     if (!storeEntryValidLength(e)) {
 572         EBIT_SET(e->flags, ENTRY_BAD_LENGTH);
 573         storeReleaseRequest(e);
 574     }
 575 #if USE_CACHE_DIGESTS
 576     if (e->mem_obj->request)
 577         e->mem_obj->request->hier.store_complete_stop = current_time;
 578 #endif
 579     InvokeHandlers(e);
 580     storeCheckSwapOut(e);
 581 }
 582
 583 #ifdef PPNR_WIP
 584 void
 585 storePPNR(StoreEntry * e)
 586 {
 587     assert(EBIT_TEST(e->flags, ENTRY_FWD_HDR_WAIT));
 588     EBIT_CLR(e->flags, ENTRY_FWD_HDR_WAIT);
 589 }
 590
 591 #endif /* PPNR_WIP */
 592
 593 /*
 594  * Someone wants to abort this transfer.  Set the reason in the
 595  * request structure, call the server-side callback and mark the
 596  * entry for releasing
 597  */
 598 void
 599 storeAbort(StoreEntry * e, int cbflag)
 600 {
 601     MemObject *mem = e->mem_obj;
 602     STABH *callback;
 603     void *data;
 604     assert(e->store_status == STORE_PENDING);
 605     assert(mem != NULL);
 606     debug(20, 6) ("storeAbort: %s\n", storeKeyText(e->key));
 607     storeLockObject(e);         /* lock while aborting */
 608     storeNegativeCache(e);
 609     storeReleaseRequest(e);
 610     e->store_status = STORE_ABORTED;
 611     storeSetMemStatus(e, NOT_IN_MEMORY);
 612     /* No DISK swap for negative cached object */
 613     e->swap_status = SWAPOUT_NONE;
 614     /*
 615      * We assign an object length here.  The only other place we assign
 616      * the object length is in storeComplete()
 617      */
 618     mem->object_sz = mem->inmem_hi;
 619     /* Notify the server side */
 620     if (cbflag && mem->abort.callback) {
 621         callback = mem->abort.callback;
 622         data = mem->abort.data;
 623         mem->abort.callback = NULL;
 624         mem->abort.data = NULL;
 625         callback(data);
 626     }
 627     /* Notify the client side */
 628     InvokeHandlers(e);
 629     /* Do we need to close the swapout file? */
 630     /* Not if we never started swapping out */
 631     /* But we may need to cancel an open/stat in progress if using ASYNC */
 632 #if USE_ASYNC_IO
 633     aioCancel(-1, e);
 634 #endif
 635     if (e->swap_file_number > -1) {
 636 #if USE_ASYNC_IO
 637         /* Need to cancel any pending ASYNC writes right now */
 638         if (mem->swapout.fd >= 0)
 639             aioCancel(mem->swapout.fd, NULL);
 640 #endif
 641         /* we have to close the disk file if there is no write pending */
 642         if (!storeSwapOutWriteQueued(mem))
 643             storeSwapOutFileClose(e);
 644     }
 645     storeUnlockObject(e);       /* unlock */
 646 }
 647
 648 /* Clear Memory storage to accommodate the given object len */
 649 static void
 650 storeGetMemSpace(int size)
 651 {
 652     StoreEntry *e = NULL;
 653     int released = 0;
 654     static time_t last_check = 0;
 655     int pages_needed;
 656     dlink_node *m;
 657     dlink_node *head;
 658     dlink_node *prev = NULL;
 659     if (squid_curtime == last_check)
 660         return;
 661     last_check = squid_curtime;
 662     pages_needed = (size / SM_PAGE_SIZE) + 1;
 663     if (memInUse(MEM_STMEM_BUF) + pages_needed < store_pages_high)
 664         return;
 665     if (store_rebuilding)
 666         return;
 667     debug(20, 2) ("storeGetMemSpace: Starting, need %d pages\n", pages_needed);
 668     head = inmem_list.head;
 669     for (m = inmem_list.tail; m; m = prev) {
 670         if (m == head)
 671             break;
 672         prev = m->prev;
 673         e = m->data;
 674         if (storeEntryLocked(e)) {
 675             dlinkDelete(m, &inmem_list);
 676             dlinkAdd(e, m, &inmem_list);
 677             continue;
 678         }
 679         released++;
 680         storePurgeMem(e);
 681         if (memInUse(MEM_STMEM_BUF) + pages_needed < store_pages_high)
 682             break;
 683     }
 684     debug(20, 3) ("storeGetMemSpace stats:\n");
 685     debug(20, 3) ("  %6d HOT objects\n", hot_obj_count);
 686     debug(20, 3) ("  %6d were released\n", released);
 687 }
 688
 689 /* The maximum objects to scan for maintain storage space */
 690 #define MAINTAIN_MAX_SCAN       1024
 691 #define MAINTAIN_MAX_REMOVE     64
 692
 693 /*
 694  * This routine is to be called by main loop in main.c.
 695  * It removes expired objects on only one bucket for each time called.
 696  * returns the number of objects removed
 697  *
 698  * This should get called 1/s from main().
 699  */
 700 void
 701 storeMaintainSwapSpace(void *datanotused)
 702 {
 703     dlink_node *m;
 704     dlink_node *prev = NULL;
 705     StoreEntry *e = NULL;
 706     int scanned = 0;
 707     int locked = 0;
 708     int expired = 0;
 709     int max_scan;
 710     int max_remove;
 711     static time_t last_warn_time = 0;
 712     /* We can't delete objects while rebuilding swap */
 713     if (store_rebuilding) {
 714         eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 1.0, 1);
 715         return;
 716     } else if (store_swap_size < store_swap_mid) {
 717         max_scan = 100;
 718         max_remove = 8;
 719         eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 1.0, 1);
 720     } else if (store_swap_size < store_swap_high) {
 721         max_scan = 200;
 722         max_remove = 8;
 723         eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 0.1, 1);
 724     } else {
 725         max_scan = 500;
 726         max_remove = 32;
 727         eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 0.0, 1);
 728     }
 729     debug(20, 3) ("storeMaintainSwapSpace\n");
 730     for (m = store_list.tail; m; m = prev) {
 731         prev = m->prev;
 732         e = m->data;
 733         scanned++;
 734         if (storeEntryLocked(e)) {
 735             /*
 736              * If there is a locked entry at the tail of the LRU list,
 737              * move it to the beginning to get it out of the way.
 738              * Theoretically, we might have all locked objects at the
 739              * tail, and then we'll never remove anything here and the
 740              * LRU age will go to zero.
 741              */
 742             if (memInUse(MEM_STOREENTRY) > max_scan) {
 743                 dlinkDelete(&e->lru, &store_list);
 744                 dlinkAdd(e, &e->lru, &store_list);
 745             }
 746             locked++;
 747         } else if (storeCheckExpired(e)) {
 748             expired++;
 749             storeRelease(e);
 750         }
 751         if (expired >= max_remove)
 752             break;
 753         if (scanned >= max_scan)
 754             break;
 755     }
 756     debug(20, 3) ("storeMaintainSwapSpace stats:\n");
 757     debug(20, 3) ("  %6d objects\n", memInUse(MEM_STOREENTRY));
 758     debug(20, 3) ("  %6d were scanned\n", scanned);
 759     debug(20, 3) ("  %6d were locked\n", locked);
 760     debug(20, 3) ("  %6d were expired\n", expired);
 761     if (store_swap_size < Config.Swap.maxSize)
 762         return;
 763     if (squid_curtime - last_warn_time < 10)
 764         return;
 765     debug(20, 0) ("WARNING: Disk space over limit: %d KB > %d KB\n",
 766         store_swap_size, Config.Swap.maxSize);
 767     last_warn_time = squid_curtime;
 768 }
 769
 770
 771 /* release an object from a cache */
 772 /* return number of objects released. */
 773 void
 774 storeRelease(StoreEntry * e)
 775 {
 776     debug(20, 3) ("storeRelease: Releasing: '%s'\n", storeKeyText(e->key));
 777     /* If, for any reason we can't discard this object because of an
 778      * outstanding request, mark it for pending release */
 779     if (storeEntryLocked(e)) {
 780         storeExpireNow(e);
 781         debug(20, 3) ("storeRelease: Only setting RELEASE_REQUEST bit\n");
 782         storeReleaseRequest(e);
 783         return;
 784     }
 785     if (store_rebuilding) {
 786         debug(20, 2) ("storeRelease: Delaying release until store is rebuilt: '%s'\n",
 787             storeUrl(e));
 788         storeExpireNow(e);
 789         storeReleaseRequest(e);
 790         return;
 791     }
 792 #if USE_ASYNC_IO
 793     /*
 794      * Make sure all forgotten async ops are cancelled
 795      */
 796     aioCancel(-1, e);
 797 #endif
 798     storeLog(STORE_LOG_RELEASE, e);
 799     if (e->swap_file_number > -1) {
 800         storeUnlinkFileno(e->swap_file_number);
 801         storeDirMapBitReset(e->swap_file_number);
 802         if (e->swap_status == SWAPOUT_DONE)
 803             if (EBIT_TEST(e->flags, ENTRY_VALIDATED))
 804                 storeDirUpdateSwapSize(e->swap_file_number, e->swap_file_sz, -1);
 805         if (!EBIT_TEST(e->flags, KEY_PRIVATE))
 806             storeDirSwapLog(e, SWAP_LOG_DEL);
 807     }
 808     storeSetMemStatus(e, NOT_IN_MEMORY);
 809     destroy_StoreEntry(e);
 810 }
 811
 812 /* return 1 if a store entry is locked */
 813 static int
 814 storeEntryLocked(const StoreEntry * e)
 815 {
 816     if (e->lock_count)
 817         return 1;
 818     if (e->swap_status == SWAPOUT_OPENING)
 819         return 1;
 820     if (e->swap_status == SWAPOUT_WRITING)
 821         return 1;
 822     if (e->store_status == STORE_PENDING)
 823         return 1;
 824     if (EBIT_TEST(e->flags, ENTRY_SPECIAL))
 825         return 1;
 826     return 0;
 827 }
 828
 829 static int
 830 storeEntryValidLength(const StoreEntry * e)
 831 {
 832     int diff;
 833     const HttpReply *reply;
 834     assert(e->mem_obj != NULL);
 835     reply = e->mem_obj->reply;
 836     debug(20, 3) ("storeEntryValidLength: Checking '%s'\n", storeKeyText(e->key));
 837     debug(20, 5) ("storeEntryValidLength:     object_len = %d\n",
 838         objectLen(e));
 839     debug(20, 5) ("storeEntryValidLength:         hdr_sz = %d\n",
 840         reply->hdr_sz);
 841     debug(20, 5) ("storeEntryValidLength: content_length = %d\n",
 842         reply->content_length);
 843     if (reply->content_length < 0) {
 844         debug(20, 5) ("storeEntryValidLength: Unspecified content length: %s\n",
 845             storeKeyText(e->key));
 846         return 1;
 847     }
 848     if (reply->hdr_sz == 0) {
 849         debug(20, 5) ("storeEntryValidLength: Zero header size: %s\n",
 850             storeKeyText(e->key));
 851         return 1;
 852     }
 853     if (e->mem_obj->method == METHOD_HEAD) {
 854         debug(20, 5) ("storeEntryValidLength: HEAD request: %s\n",
 855             storeKeyText(e->key));
 856         return 1;
 857     }
 858     if (reply->sline.status == HTTP_NOT_MODIFIED)
 859         return 1;
 860     if (reply->sline.status == HTTP_NO_CONTENT)
 861         return 1;
 862     diff = reply->hdr_sz + reply->content_length - objectLen(e);
 863     if (diff == 0)
 864         return 1;
 865     debug(20, 3) ("storeEntryValidLength: %d bytes too %s; '%s'\n",
 866         diff < 0 ? -diff : diff,
 867         diff < 0 ? "big" : "small",
 868         storeKeyText(e->key));
 869     return 0;
 870 }
 871
 872 static void
 873 storeInitHashValues(void)
 874 {
 875     int i;
 876     /* Calculate size of hash table (maximum currently 64k buckets).  */
 877     i = Config.Swap.maxSize / Config.Store.avgObjectSize;
 878     debug(20, 1) ("Swap maxSize %d KB, estimated %d objects\n",
 879         Config.Swap.maxSize, i);
 880     i /= Config.Store.objectsPerBucket;
 881     debug(20, 1) ("Target number of buckets: %d\n", i);
 882     /* ideally the full scan period should be configurable, for the
 883      * moment it remains at approximately 24 hours.  */
 884     store_hash_buckets = storeKeyHashBuckets(i);
 885     store_maintain_rate = 86400 / store_hash_buckets;
 886     assert(store_maintain_rate > 0);
 887     debug(20, 1) ("Using %d Store buckets, replacement runs every %d second%s\n",
 888         store_hash_buckets,
 889         store_maintain_rate,
 890         store_maintain_rate == 1 ? null_string : "s");
 891     debug(20, 1) ("Max Mem  size: %d KB\n", Config.Mem.maxSize >> 10);
 892     debug(20, 1) ("Max Swap size: %d KB\n", Config.Swap.maxSize);
 893 }
 894
 895 void
 896 storeInit(void)
 897 {
 898     storeKeyInit();
 899     storeInitHashValues();
 900     store_table = hash_create(storeKeyHashCmp,
 901         store_hash_buckets, storeKeyHashHash);
 902     storeDigestInit();
 903     storeLogOpen();
 904     if (storeVerifyCacheDirs() < 0) {
 905         xstrncpy(tmp_error_buf,
 906             "\tFailed to verify one of the swap directories, Check cache.log\n"
 907             "\tfor details.  Run 'squid -z' to create swap directories\n"
 908             "\tif needed, or if running Squid for the first time.",
 909             ERROR_BUF_SZ);
 910         fatal(tmp_error_buf);
 911     }
 912     storeDirOpenSwapLogs();
 913     store_list.head = store_list.tail = NULL;
 914     inmem_list.head = inmem_list.tail = NULL;
 915     storeRebuildStart();
 916     cachemgrRegister("storedir",
 917         "Store Directory Stats",
 918         storeDirStats, 0, 1);
 919     cachemgrRegister("store_check_cachable_stats",
 920         "storeCheckCachable() Stats",
 921         storeCheckCachableStats, 0, 1);
 922 }
 923
 924 void
 925 storeConfigure(void)
 926 {
 927     int store_mem_high = 0;
 928     int store_mem_low = 0;
 929     store_mem_high = (long) (Config.Mem.maxSize / 100) *
 930         Config.Mem.highWaterMark;
 931     store_mem_low = (long) (Config.Mem.maxSize / 100) *
 932         Config.Mem.lowWaterMark;
 933
 934     store_swap_high = (long) (((float) Config.Swap.maxSize *
 935             (float) Config.Swap.highWaterMark) / (float) 100);
 936     store_swap_low = (long) (((float) Config.Swap.maxSize *
 937             (float) Config.Swap.lowWaterMark) / (float) 100);
 938     store_swap_mid = (store_swap_high >> 1) + (store_swap_low >> 1);
 939
 940     store_pages_high = store_mem_high / SM_PAGE_SIZE;
 941     store_pages_low = store_mem_low / SM_PAGE_SIZE;
 942 }
 943
 944 static int
 945 storeKeepInMemory(const StoreEntry * e)
 946 {
 947     MemObject *mem = e->mem_obj;
 948     if (mem == NULL)
 949         return 0;
 950     if (mem->data_hdr.head == NULL)
 951         return 0;
 952     return mem->inmem_lo == 0;
 953 }
 954
 955 static int
 956 storeCheckExpired(const StoreEntry * e)
 957 {
 958     if (storeEntryLocked(e))
 959         return 0;
 960     if (EBIT_TEST(e->flags, RELEASE_REQUEST))
 961         return 1;
 962     if (EBIT_TEST(e->flags, ENTRY_NEGCACHED) && squid_curtime >= e->expires)
 963         return 1;
 964     if (squid_curtime - e->lastref > storeExpiredReferenceAge())
 965         return 1;
 966     return 0;
 967 }
 968
 969 /*
 970  * storeExpiredReferenceAge
 971  *
 972  * The LRU age is scaled exponentially between 1 minute and
 973  * Config.referenceAge , when store_swap_low < store_swap_size <
 974  * store_swap_high.  This keeps store_swap_size within the low and high
 975  * water marks.  If the cache is very busy then store_swap_size stays
 976  * closer to the low water mark, if it is not busy, then it will stay
 977  * near the high water mark.  The LRU age value can be examined on the
 978  * cachemgr 'info' page.
 979  */
 980 time_t
 981 storeExpiredReferenceAge(void)
 982 {
 983     double x;
 984     double z;
 985     time_t age;
 986     x = (double) (store_swap_high - store_swap_size) / (store_swap_high - store_swap_low);
 987     x = x < 0.0 ? 0.0 : x > 1.0 ? 1.0 : x;
 988     z = pow((double) (Config.referenceAge / 60), x);
 989     age = (time_t) (z * 60.0);
 990     if (age < 60)
 991         age = 60;
 992     else if (age > 31536000)
 993         age = 31536000;
 994     return age;
 995 }
 996
 997 void
 998 storeNegativeCache(StoreEntry * e)
 999 {
1000     e->expires = squid_curtime + Config.negativeTtl;
1001     EBIT_SET(e->flags, ENTRY_NEGCACHED);
1002 }
1003
1004 void
1005 storeFreeMemory(void)
1006 {
1007     hashFreeItems(store_table, destroy_StoreEntry);
1008     hashFreeMemory(store_table);
1009     store_table = NULL;
1010 #if USE_CACHE_DIGEST
1011     if (store_digest)
1012         cacheDigestDestroy(store_digest);
1013 #endif
1014     store_digest = NULL;
1015 }
1016
1017 int
1018 expiresMoreThan(time_t expires, time_t when)
1019 {
1020     if (expires < 0)            /* No Expires given */
1021         return 1;
1022     return (expires > (squid_curtime + when));
1023 }
1024
1025 int
1026 storeEntryValidToSend(StoreEntry * e)
1027 {
1028     if (EBIT_TEST(e->flags, RELEASE_REQUEST))
1029         return 0;
1030     if (EBIT_TEST(e->flags, ENTRY_NEGCACHED))
1031         if (e->expires <= squid_curtime)
1032             return 0;
1033     if (e->store_status == STORE_ABORTED)
1034         return 0;
1035     return 1;
1036 }
1037
1038 void
1039 storeTimestampsSet(StoreEntry * entry)
1040 {
1041     time_t served_date = -1;
1042     const HttpReply *reply = entry->mem_obj->reply;
1043     served_date = reply->date;
1044     if (served_date < 0)
1045         served_date = squid_curtime;
1046     entry->expires = reply->expires;
1047     entry->lastmod = reply->last_modified;
1048     entry->timestamp = served_date;
1049 }
1050
1051 void
1052 storeRegisterAbort(StoreEntry * e, STABH * cb, void *data)
1053 {
1054     MemObject *mem = e->mem_obj;
1055     assert(mem);
1056     assert(mem->abort.callback == NULL);
1057     mem->abort.callback = cb;
1058     mem->abort.data = data;
1059 }
1060
1061 void
1062 storeUnregisterAbort(StoreEntry * e)
1063 {
1064     MemObject *mem = e->mem_obj;
1065     assert(mem);
1066     mem->abort.callback = NULL;
1067 }
1068
1069 void
1070 storeMemObjectDump(MemObject * mem)
1071 {
1072     debug(20, 1) ("MemObject->data.head: %p\n",
1073         mem->data_hdr.head);
1074     debug(20, 1) ("MemObject->data.tail: %p\n",
1075         mem->data_hdr.tail);
1076     debug(20, 1) ("MemObject->data.origin_offset: %d\n",
1077         mem->data_hdr.origin_offset);
1078     debug(20, 1) ("MemObject->start_ping: %d.%06d\n",
1079         (int) mem->start_ping.tv_sec,
1080         (int) mem->start_ping.tv_usec);
1081     debug(20, 1) ("MemObject->inmem_hi: %d\n",
1082         (int) mem->inmem_hi);
1083     debug(20, 1) ("MemObject->inmem_lo: %d\n",
1084         (int) mem->inmem_lo);
1085     debug(20, 1) ("MemObject->clients: %p\n",
1086         mem->clients);
1087     debug(20, 1) ("MemObject->nclients: %d\n",
1088         mem->nclients);
1089     debug(20, 1) ("MemObject->swapout.fd: %d\n",
1090         mem->swapout.fd);
1091     debug(20, 1) ("MemObject->reply: %p\n",
1092         mem->reply);
1093     debug(20, 1) ("MemObject->request: %p\n",
1094         mem->request);
1095     debug(20, 1) ("MemObject->log_url: %p %s\n",
1096         mem->log_url,
1097         checkNullString(mem->log_url));
1098 }
1099
1100 void
1101 storeEntryDump(StoreEntry * e, int l)
1102 {
1103     debug(20, l) ("StoreEntry->key: %s\n", storeKeyText(e->key));
1104     debug(20, l) ("StoreEntry->next: %p\n", e->next);
1105     debug(20, l) ("StoreEntry->mem_obj: %p\n", e->mem_obj);
1106     debug(20, l) ("StoreEntry->timestamp: %d\n", (int) e->timestamp);
1107     debug(20, l) ("StoreEntry->lastref: %d\n", (int) e->lastref);
1108     debug(20, l) ("StoreEntry->expires: %d\n", (int) e->expires);
1109     debug(20, l) ("StoreEntry->lastmod: %d\n", (int) e->lastmod);
1110     debug(20, l) ("StoreEntry->swap_file_sz: %d\n", (int) e->swap_file_sz);
1111     debug(20, l) ("StoreEntry->refcount: %d\n", e->refcount);
1112     debug(20, l) ("StoreEntry->flags: %s\n", storeEntryFlags(e));
1113     debug(20, l) ("StoreEntry->swap_file_number: %d\n", (int) e->swap_file_number);
1114     debug(20, l) ("StoreEntry->lock_count: %d\n", (int) e->lock_count);
1115     debug(20, l) ("StoreEntry->mem_status: %d\n", (int) e->mem_status);
1116     debug(20, l) ("StoreEntry->ping_status: %d\n", (int) e->ping_status);
1117     debug(20, l) ("StoreEntry->store_status: %d\n", (int) e->store_status);
1118     debug(20, l) ("StoreEntry->swap_status: %d\n", (int) e->swap_status);
1119 }
1120
1121 /* NOTE, this function assumes only two mem states */
1122 void
1123 storeSetMemStatus(StoreEntry * e, int new_status)
1124 {
1125     MemObject *mem = e->mem_obj;
1126     if (new_status == e->mem_status)
1127         return;
1128     assert(mem != NULL);
1129     if (new_status == IN_MEMORY) {
1130         assert(mem->inmem_lo == 0);
1131         dlinkAdd(e, &mem->lru, &inmem_list);
1132         hot_obj_count++;
1133     } else {
1134         dlinkDelete(&mem->lru, &inmem_list);
1135         hot_obj_count--;
1136     }
1137     e->mem_status = new_status;
1138 }
1139
1140 const char *
1141 storeUrl(const StoreEntry * e)
1142 {
1143     if (e == NULL)
1144         return "[null_entry]";
1145     else if (e->mem_obj == NULL)
1146         return "[null_mem_obj]";
1147     else
1148         return e->mem_obj->url;
1149 }
1150
1151 void
1152 storeCreateMemObject(StoreEntry * e, const char *url, const char *log_url)
1153 {
1154     if (e->mem_obj)
1155         return;
1156     e->mem_obj = new_MemObject(url, log_url);
1157 }
1158
1159 /* this just sets DELAY_SENDING */
1160 void
1161 storeBuffer(StoreEntry * e)
1162 {
1163     EBIT_SET(e->flags, DELAY_SENDING);
1164 }
1165
1166 /* this just clears DELAY_SENDING and Invokes the handlers */
1167 void
1168 storeBufferFlush(StoreEntry * e)
1169 {
1170     EBIT_CLR(e->flags, DELAY_SENDING);
1171     InvokeHandlers(e);
1172     storeCheckSwapOut(e);
1173 }
1174
1175 void
1176 storeUnlinkFileno(int fileno)
1177 {
1178     debug(20, 5) ("storeUnlinkFileno: %08X\n", fileno);
1179 #if USE_ASYNC_IO
1180     safeunlink(storeSwapFullPath(fileno, NULL), 1);
1181 #else
1182     unlinkdUnlink(storeSwapFullPath(fileno, NULL));
1183 #endif
1184 }
1185
1186 int
1187 objectLen(const StoreEntry * e)
1188 {
1189     assert(e->mem_obj != NULL);
1190     return e->mem_obj->object_sz;
1191 }
1192
1193 int
1194 contentLen(const StoreEntry * e)
1195 {
1196     assert(e->mem_obj != NULL);
1197     assert(e->mem_obj->reply != NULL);
1198     return e->mem_obj->object_sz - e->mem_obj->reply->hdr_sz;
1199 }
1200
1201 HttpReply *
1202 storeEntryReply(StoreEntry * e)
1203 {
1204     if (NULL == e)
1205         return NULL;
1206     if (NULL == e->mem_obj)
1207         return NULL;
1208     return e->mem_obj->reply;
1209 }