3 * $Id: store.cc,v 1.514 2000/02/01 05:43:02 wessels Exp $
5 * DEBUG: section 20 Storage Manager
6 * AUTHOR: Harvest Derived
8 * SQUID Internet Object Cache http://squid.nlanr.net/Squid/
9 * ----------------------------------------------------------
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.
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.
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.
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.
38 #define REBUILD_TIMESTAMP_DELTA_MAX 2
40 #define STORE_IN_MEM_BUCKETS (229)
42 const char *memStatusStr
[] =
48 const char *pingStatusStr
[] =
55 const char *storeStatusStr
[] =
61 const char *swapStatusStr
[] =
68 typedef struct lock_ctrl_t
{
75 * local function prototypes
77 static int storeCheckExpired(const StoreEntry
*);
78 static int storeEntryLocked(const StoreEntry
*);
79 static int storeEntryValidLength(const StoreEntry
*);
80 static void storeGetMemSpace(int);
81 static void storeHashDelete(StoreEntry
*);
82 static MemObject
*new_MemObject(const char *, const char *);
83 static void destroy_MemObject(StoreEntry
*);
84 static FREE destroy_StoreEntry
;
85 static void storePurgeMem(StoreEntry
*);
86 static int getKeyCounter(void);
87 static int storeKeepInMemory(const StoreEntry
*);
88 static OBJH storeCheckCachableStats
;
89 static EVH storeLateRelease
;
91 static heap_key_func HeapKeyGen_StoreEntry_LFUDA
;
92 static heap_key_func HeapKeyGen_StoreEntry_GDSF
;
93 static heap_key_func HeapKeyGen_StoreEntry_LRU
;
101 * The heap equivalent of inmem_list, inmem_heap, is in globals.c so other
102 * modules can access it when updating object metadata (e.g., refcount)
105 static dlink_list inmem_list
;
107 static int store_pages_max
= 0;
108 static int store_swap_high
= 0;
109 static int store_swap_low
= 0;
110 static Stack LateReleaseStack
;
112 #if URL_CHECKSUM_DEBUG
114 url_checksum(const char *url
)
118 static unsigned char digest
[16];
120 MD5Update(&M
, (unsigned char *) url
, strlen(url
));
121 MD5Final(digest
, &M
);
122 xmemcpy(&ck
, digest
, sizeof(ck
));
128 new_MemObject(const char *url
, const char *log_url
)
130 MemObject
*mem
= memAllocate(MEM_MEMOBJECT
);
131 mem
->reply
= httpReplyCreate();
132 mem
->url
= xstrdup(url
);
133 #if URL_CHECKSUM_DEBUG
134 mem
->chksum
= url_checksum(mem
->url
);
136 mem
->log_url
= xstrdup(log_url
);
139 /* XXX account log_url */
140 debug(20, 3) ("new_MemObject: returning %p\n", mem
);
145 new_StoreEntry(int mem_obj_flag
, const char *url
, const char *log_url
)
147 StoreEntry
*e
= NULL
;
148 e
= memAllocate(MEM_STOREENTRY
);
150 e
->mem_obj
= new_MemObject(url
, log_url
);
151 debug(20, 3) ("new_StoreEntry: returning %p\n", e
);
152 e
->expires
= e
->lastmod
= e
->lastref
= e
->timestamp
= -1;
153 e
->swap_file_number
= -1;
158 destroy_MemObject(StoreEntry
* e
)
160 MemObject
*mem
= e
->mem_obj
;
161 const Ctx ctx
= ctx_enter(mem
->url
);
162 debug(20, 3) ("destroy_MemObject: destroying %p\n", mem
);
163 #if URL_CHECKSUM_DEBUG
164 assert(mem
->chksum
== url_checksum(mem
->url
));
168 assert(mem
->swapout
.sio
== NULL
);
169 stmemFree(&mem
->data_hdr
);
172 * There is no way to abort FD-less clients, so they might
173 * still have mem->clients set if mem->fd == -1
175 assert(mem
->fd
== -1 || mem
->clients
== NULL
);
176 httpReplyDestroy(mem
->reply
);
177 requestUnlink(mem
->request
);
179 ctx_exit(ctx
); /* must exit before we free mem->url */
181 safe_free(mem
->log_url
); /* XXX account log_url */
182 memFree(mem
, MEM_MEMOBJECT
);
186 destroy_StoreEntry(void *data
)
188 StoreEntry
*e
= data
;
189 debug(20, 3) ("destroy_StoreEntry: destroying %p\n", e
);
192 destroy_MemObject(e
);
194 assert(e
->key
== NULL
);
195 memFree(e
, MEM_STOREENTRY
);
198 /* ----- INTERFACE BETWEEN STORAGE MANAGER AND HASH TABLE FUNCTIONS --------- */
201 storeHashInsert(StoreEntry
* e
, const cache_key
* key
)
203 debug(20, 3) ("storeHashInsert: Inserting Entry %p key '%s'\n",
204 e
, storeKeyText(key
));
205 e
->key
= storeKeyDup(key
);
206 hash_join(store_table
, (hash_link
*) e
);
208 if (EBIT_TEST(e
->flags
, ENTRY_SPECIAL
)) {
211 e
->node
= heap_insert(store_heap
, e
);
212 debug(20, 4) ("storeHashInsert: inserted node %p\n", e
->node
);
218 storeHashDelete(StoreEntry
* e
)
220 hash_remove_link(store_table
, (hash_link
*) e
);
223 debug(20, 4) ("storeHashDelete: deleting node %p\n", e
->node
);
224 heap_delete(store_heap
, e
->node
);
228 storeKeyFree(e
->key
);
232 /* -------------------------------------------------------------------------- */
235 /* get rid of memory copy of the object */
236 /* Only call this if storeCheckPurgeMem(e) returns 1 */
238 storePurgeMem(StoreEntry
* e
)
240 if (e
->mem_obj
== NULL
)
242 debug(20, 3) ("storePurgeMem: Freeing memory-copy of %s\n",
243 storeKeyText(e
->key
));
244 storeSetMemStatus(e
, NOT_IN_MEMORY
);
245 destroy_MemObject(e
);
246 if (e
->swap_status
!= SWAPOUT_DONE
)
251 storeLockObject(StoreEntry
* e
)
253 if (e
->lock_count
++ == 0) {
256 * There is no reason to take any action here. Squid by
257 * default is moving locked objects to the end of the LRU
258 * list to keep them from getting bumped into by the
259 * replacement algorithm. We can't do that so we will just
260 * have to handle them.
262 debug(20, 4) ("storeLockObject: just locked node %p\n", e
->node
);
264 storeDirLRUDelete(e
);
268 debug(20, 3) ("storeLockObject: key '%s' count=%d\n",
269 storeKeyText(e
->key
), (int) e
->lock_count
);
270 e
->lastref
= squid_curtime
;
274 storeReleaseRequest(StoreEntry
* e
)
276 if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
))
278 debug(20, 3) ("storeReleaseRequest: '%s'\n", storeKeyText(e
->key
));
279 EBIT_SET(e
->flags
, RELEASE_REQUEST
);
281 * Clear cachable flag here because we might get called before
282 * anyone else even looks at the cachability flag. Also, this
283 * prevents httpMakePublic from really setting a public key.
285 EBIT_CLR(e
->flags
, ENTRY_CACHABLE
);
286 storeSetPrivateKey(e
);
289 /* unlock object, return -1 if object get released after unlock
290 * otherwise lock_count */
292 storeUnlockObject(StoreEntry
* e
)
295 debug(20, 3) ("storeUnlockObject: key '%s' count=%d\n",
296 storeKeyText(e
->key
), e
->lock_count
);
298 return (int) e
->lock_count
;
299 if (e
->store_status
== STORE_PENDING
)
300 EBIT_SET(e
->flags
, RELEASE_REQUEST
);
301 assert(storePendingNClients(e
) == 0);
303 storeHeapPositionUpdate(e
);
305 storeDirLRUDelete(e
);
308 if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
))
310 else if (storeKeepInMemory(e
)) {
311 storeSetMemStatus(e
, IN_MEMORY
);
312 requestUnlink(e
->mem_obj
->request
);
313 e
->mem_obj
->request
= NULL
;
316 if (EBIT_TEST(e
->flags
, KEY_PRIVATE
))
317 debug(20, 1) ("WARNING: %s:%d: found KEY_PRIVATE\n", __FILE__
, __LINE__
);
322 /* Lookup an object in the cache.
323 * return just a reference to object, don't start swapping in yet. */
325 storeGet(const cache_key
* key
)
327 debug(20, 3) ("storeGet: looking up %s\n", storeKeyText(key
));
328 return (StoreEntry
*) hash_lookup(store_table
, key
);
332 storeGetPublic(const char *uri
, const method_t method
)
334 return storeGet(storeKeyPublic(uri
, method
));
340 static int key_counter
= 0;
341 if (++key_counter
< 0)
347 storeSetPrivateKey(StoreEntry
* e
)
349 const cache_key
*newkey
;
350 MemObject
*mem
= e
->mem_obj
;
351 if (e
->key
&& EBIT_TEST(e
->flags
, KEY_PRIVATE
))
352 return; /* is already private */
354 if (e
->swap_file_number
> -1)
355 storeDirSwapLog(e
, SWAP_LOG_DEL
);
359 mem
->id
= getKeyCounter();
360 newkey
= storeKeyPrivate(mem
->url
, mem
->method
, mem
->id
);
362 newkey
= storeKeyPrivate("JUNK", METHOD_NONE
, getKeyCounter());
364 assert(hash_lookup(store_table
, newkey
) == NULL
);
365 EBIT_SET(e
->flags
, KEY_PRIVATE
);
366 storeHashInsert(e
, newkey
);
370 storeSetPublicKey(StoreEntry
* e
)
372 StoreEntry
*e2
= NULL
;
373 const cache_key
*newkey
;
374 MemObject
*mem
= e
->mem_obj
;
375 if (e
->key
&& !EBIT_TEST(e
->flags
, KEY_PRIVATE
))
376 return; /* is already public */
379 * We can't make RELEASE_REQUEST objects public. Depending on
380 * when RELEASE_REQUEST gets set, we might not be swapping out
381 * the object. If we're not swapping out, then subsequent
382 * store clients won't be able to access object data which has
383 * been freed from memory.
385 * If RELEASE_REQUEST is set, then ENTRY_CACHABLE should not
386 * be set, and storeSetPublicKey() should not be called.
389 if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
))
390 debug(20, 1) ("assertion failed: RELEASE key %s, url %s\n",
393 assert(!EBIT_TEST(e
->flags
, RELEASE_REQUEST
));
394 newkey
= storeKeyPublic(mem
->url
, mem
->method
);
395 if ((e2
= (StoreEntry
*) hash_lookup(store_table
, newkey
))) {
396 debug(20, 3) ("storeSetPublicKey: Making old '%s' private.\n", mem
->url
);
397 storeSetPrivateKey(e2
);
399 newkey
= storeKeyPublic(mem
->url
, mem
->method
);
403 EBIT_CLR(e
->flags
, KEY_PRIVATE
);
404 storeHashInsert(e
, newkey
);
405 if (e
->swap_file_number
> -1)
406 storeDirSwapLog(e
, SWAP_LOG_ADD
);
410 storeCreateEntry(const char *url
, const char *log_url
, request_flags flags
, method_t method
)
412 StoreEntry
*e
= NULL
;
413 MemObject
*mem
= NULL
;
414 debug(20, 3) ("storeCreateEntry: '%s'\n", url
);
416 e
= new_StoreEntry(STORE_ENTRY_WITH_MEMOBJ
, url
, log_url
);
417 e
->lock_count
= 1; /* Note lock here w/o calling storeLock() */
419 mem
->method
= method
;
420 if (neighbors_do_private_keys
|| !flags
.hierarchical
)
421 storeSetPrivateKey(e
);
423 storeSetPublicKey(e
);
424 if (flags
.cachable
) {
425 EBIT_SET(e
->flags
, ENTRY_CACHABLE
);
426 EBIT_CLR(e
->flags
, RELEASE_REQUEST
);
428 EBIT_CLR(e
->flags
, ENTRY_CACHABLE
);
429 storeReleaseRequest(e
);
431 e
->store_status
= STORE_PENDING
;
432 storeSetMemStatus(e
, NOT_IN_MEMORY
);
433 e
->swap_status
= SWAPOUT_NONE
;
434 e
->swap_file_number
= -1;
436 e
->lastref
= squid_curtime
;
437 e
->timestamp
= 0; /* set in storeTimestampsSet() */
438 e
->ping_status
= PING_NONE
;
439 EBIT_SET(e
->flags
, ENTRY_VALIDATED
);
443 /* Mark object as expired */
445 storeExpireNow(StoreEntry
* e
)
447 debug(20, 3) ("storeExpireNow: '%s'\n", storeKeyText(e
->key
));
448 e
->expires
= squid_curtime
;
451 /* Append incoming data from a primary server to an entry. */
453 storeAppend(StoreEntry
* e
, const char *buf
, int len
)
455 MemObject
*mem
= e
->mem_obj
;
458 assert(e
->store_status
== STORE_PENDING
);
460 debug(20, 5) ("storeAppend: appending %d bytes for '%s'\n",
462 storeKeyText(e
->key
));
463 storeGetMemSpace(len
);
464 stmemAppend(&mem
->data_hdr
, buf
, len
);
465 mem
->inmem_hi
+= len
;
467 if (EBIT_TEST(e
->flags
, DELAY_SENDING
))
475 storeAppendPrintf(StoreEntry
* e
, const char *fmt
,...)
477 storeAppendPrintf(va_alist
)
486 StoreEntry
*e
= NULL
;
487 const char *fmt
= NULL
;
489 e
= va_arg(args
, StoreEntry
*);
490 fmt
= va_arg(args
, char *);
492 storeAppendVPrintf(e
, fmt
, args
);
496 /* used be storeAppendPrintf and Packer */
498 storeAppendVPrintf(StoreEntry
* e
, const char *fmt
, va_list vargs
)
500 LOCAL_ARRAY(char, buf
, 4096);
502 vsnprintf(buf
, 4096, fmt
, vargs
);
503 storeAppend(e
, buf
, strlen(buf
));
506 struct _store_check_cachable_hist
{
509 int not_entry_cachable
;
511 int wrong_content_length
;
515 int too_many_open_files
;
516 int too_many_open_fds
;
521 } store_check_cachable_hist
;
524 storeTooManyDiskFilesOpen(void)
526 if (Config
.max_open_disk_fds
== 0)
528 if (store_open_disk_fd
> Config
.max_open_disk_fds
)
534 storeCheckCachable(StoreEntry
* e
)
536 #if CACHE_ALL_METHODS
537 if (e
->mem_obj
->method
!= METHOD_GET
) {
538 debug(20, 2) ("storeCheckCachable: NO: non-GET method\n");
539 store_check_cachable_hist
.no
.non_get
++;
542 if (!EBIT_TEST(e
->flags
, ENTRY_CACHABLE
)) {
543 debug(20, 2) ("storeCheckCachable: NO: not cachable\n");
544 store_check_cachable_hist
.no
.not_entry_cachable
++;
545 } else if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
)) {
546 debug(20, 2) ("storeCheckCachable: NO: release requested\n");
547 store_check_cachable_hist
.no
.release_request
++;
548 } else if (e
->store_status
== STORE_OK
&& EBIT_TEST(e
->flags
, ENTRY_BAD_LENGTH
)) {
549 debug(20, 2) ("storeCheckCachable: NO: wrong content-length\n");
550 store_check_cachable_hist
.no
.wrong_content_length
++;
551 } else if (EBIT_TEST(e
->flags
, ENTRY_NEGCACHED
)) {
552 debug(20, 3) ("storeCheckCachable: NO: negative cached\n");
553 store_check_cachable_hist
.no
.negative_cached
++;
554 return 0; /* avoid release call below */
555 } else if (e
->mem_obj
->inmem_hi
> Config
.Store
.maxObjectSize
) {
556 debug(20, 2) ("storeCheckCachable: NO: too big\n");
557 store_check_cachable_hist
.no
.too_big
++;
558 } else if (e
->mem_obj
->reply
->content_length
> (int) Config
.Store
.maxObjectSize
) {
559 debug(20, 2) ("storeCheckCachable: NO: too big\n");
560 store_check_cachable_hist
.no
.too_big
++;
561 } else if (EBIT_TEST(e
->flags
, KEY_PRIVATE
)) {
562 debug(20, 3) ("storeCheckCachable: NO: private key\n");
563 store_check_cachable_hist
.no
.private_key
++;
564 } else if (e
->swap_status
!= SWAPOUT_NONE
) {
566 * here we checked the swap_status because the remaining
567 * cases are only relevant only if we haven't started swapping
568 * out the object yet.
571 } else if (storeTooManyDiskFilesOpen()) {
572 debug(20, 2) ("storeCheckCachable: NO: too many disk files open\n");
573 store_check_cachable_hist
.no
.too_many_open_files
++;
574 } else if (fdNFree() < RESERVED_FD
) {
575 debug(20, 2) ("storeCheckCachable: NO: too many FD's open\n");
576 store_check_cachable_hist
.no
.too_many_open_fds
++;
578 store_check_cachable_hist
.yes
.Default
++;
581 storeReleaseRequest(e
);
582 EBIT_CLR(e
->flags
, ENTRY_CACHABLE
);
587 storeCheckCachableStats(StoreEntry
* sentry
)
589 storeAppendPrintf(sentry
, "Category\t Count\n");
591 storeAppendPrintf(sentry
, "no.non_get\t%d\n",
592 store_check_cachable_hist
.no
.non_get
);
593 storeAppendPrintf(sentry
, "no.not_entry_cachable\t%d\n",
594 store_check_cachable_hist
.no
.not_entry_cachable
);
595 storeAppendPrintf(sentry
, "no.release_request\t%d\n",
596 store_check_cachable_hist
.no
.release_request
);
597 storeAppendPrintf(sentry
, "no.wrong_content_length\t%d\n",
598 store_check_cachable_hist
.no
.wrong_content_length
);
599 storeAppendPrintf(sentry
, "no.negative_cached\t%d\n",
600 store_check_cachable_hist
.no
.negative_cached
);
601 storeAppendPrintf(sentry
, "no.too_big\t%d\n",
602 store_check_cachable_hist
.no
.too_big
);
603 storeAppendPrintf(sentry
, "no.private_key\t%d\n",
604 store_check_cachable_hist
.no
.private_key
);
605 storeAppendPrintf(sentry
, "no.too_many_open_files\t%d\n",
606 store_check_cachable_hist
.no
.too_many_open_files
);
607 storeAppendPrintf(sentry
, "no.too_many_open_fds\t%d\n",
608 store_check_cachable_hist
.no
.too_many_open_fds
);
609 storeAppendPrintf(sentry
, "yes.default\t%d\n",
610 store_check_cachable_hist
.yes
.Default
);
613 /* Complete transfer into the local cache. */
615 storeComplete(StoreEntry
* e
)
617 debug(20, 3) ("storeComplete: '%s'\n", storeKeyText(e
->key
));
618 if (e
->store_status
!= STORE_PENDING
) {
620 * if we're not STORE_PENDING, then probably we got aborted
621 * and there should be NO clients on this entry
623 assert(EBIT_TEST(e
->flags
, ENTRY_ABORTED
));
624 assert(e
->mem_obj
->nclients
== 0);
627 e
->mem_obj
->object_sz
= e
->mem_obj
->inmem_hi
;
628 e
->store_status
= STORE_OK
;
629 assert(e
->mem_status
== NOT_IN_MEMORY
);
630 if (!storeEntryValidLength(e
)) {
631 EBIT_SET(e
->flags
, ENTRY_BAD_LENGTH
);
632 storeReleaseRequest(e
);
634 #if USE_CACHE_DIGESTS
635 if (e
->mem_obj
->request
)
636 e
->mem_obj
->request
->hier
.store_complete_stop
= current_time
;
643 * Someone wants to abort this transfer. Set the reason in the
644 * request structure, call the server-side callback and mark the
645 * entry for releasing
648 storeAbort(StoreEntry
* e
)
650 MemObject
*mem
= e
->mem_obj
;
651 assert(e
->store_status
== STORE_PENDING
);
653 debug(20, 6) ("storeAbort: %s\n", storeKeyText(e
->key
));
654 storeLockObject(e
); /* lock while aborting */
655 storeNegativeCache(e
);
656 storeReleaseRequest(e
);
657 EBIT_SET(e
->flags
, ENTRY_ABORTED
);
658 storeSetMemStatus(e
, NOT_IN_MEMORY
);
659 e
->store_status
= STORE_OK
;
661 * We assign an object length here. The only other place we assign
662 * the object length is in storeComplete()
664 mem
->object_sz
= mem
->inmem_hi
;
665 /* Notify the server side */
666 if (mem
->abort
.callback
) {
667 eventAdd("mem->abort.callback",
672 mem
->abort
.callback
= NULL
;
673 mem
->abort
.data
= NULL
;
675 /* Notify the client side */
677 /* Do we need to close the swapout file? */
678 /* Not if we never started swapping out */
679 if (e
->swap_file_number
> -1) {
680 storeSwapOutFileClose(e
);
682 storeUnlockObject(e
); /* unlock */
685 /* Clear Memory storage to accommodate the given object len */
687 storeGetMemSpace(int size
)
689 StoreEntry
*e
= NULL
;
691 static time_t last_check
= 0;
694 #if !HEAP_REPLACEMENT
697 dlink_node
*prev
= NULL
;
700 heap_key min_age
= 0.0;
701 link_list
*locked_entries
= NULL
;
703 if (squid_curtime
== last_check
)
705 last_check
= squid_curtime
;
706 pages_needed
= (size
/ SM_PAGE_SIZE
) + 1;
707 if (memInUse(MEM_STMEM_BUF
) + pages_needed
< store_pages_max
)
709 debug(20, 2) ("storeGetMemSpace: Starting, need %d pages\n", pages_needed
);
711 while (heap_nodes(inmem_heap
) > 0) {
712 age
= heap_peepminkey(inmem_heap
);
713 e
= heap_extractmin(inmem_heap
);
714 e
->mem_obj
->node
= NULL
; /* no longer in the heap */
715 if (storeEntryLocked(e
)) {
717 debug(20, 5) ("storeGetMemSpace: locked key %s\n",
718 storeKeyText(e
->key
));
719 linklistPush(&locked_entries
, e
);
723 debug(20, 3) ("Released memory object with key %f size %d refs %d url %s\n",
724 age
, e
->swap_file_sz
, e
->refcount
, e
->mem_obj
->url
);
727 if (memInUse(MEM_STMEM_BUF
) + pages_needed
< store_pages_max
)
731 * Increase the heap age factor.
734 inmem_heap
->age
= min_age
;
736 * Reinsert all bumped locked entries back into heap...
738 while ((e
= linklistShift(&locked_entries
)))
739 e
->mem_obj
->node
= heap_insert(inmem_heap
, e
);
741 head
= inmem_list
.head
;
742 for (m
= inmem_list
.tail
; m
; m
= prev
) {
747 if (storeEntryLocked(e
)) {
749 dlinkDelete(m
, &inmem_list
);
750 dlinkAdd(e
, m
, &inmem_list
);
755 if (memInUse(MEM_STMEM_BUF
) + pages_needed
< store_pages_max
)
759 debug(20, 3) ("storeGetMemSpace: released %d/%d locked %d\n",
760 released
, hot_obj_count
, locked
);
761 debug(20, 3) ("storeGetMemSpace stats:\n");
762 debug(20, 3) (" %6d HOT objects\n", hot_obj_count
);
763 debug(20, 3) (" %6d were released\n", released
);
766 /* The maximum objects to scan for maintain storage space */
767 #define MAINTAIN_MAX_SCAN 1024
768 #define MAINTAIN_MAX_REMOVE 64
771 * This routine is to be called by main loop in main.c.
772 * It removes expired objects on only one bucket for each time called.
773 * returns the number of objects removed
775 * This should get called 1/s from main().
778 storeMaintainSwapSpace(void *datanotused
)
780 StoreEntry
*e
= NULL
;
790 static time_t last_warn_time
= 0;
791 #if !HEAP_REPLACEMENT
795 heap_key min_age
= 0.0;
796 link_list
*locked_entries
= NULL
;
797 #if HEAP_REPLACEMENT_DEBUG
798 if (!verify_heap_property(store_heap
)) {
799 debug(20, 1) ("Heap property violated!\n");
803 /* We can't delete objects while rebuilding swap */
804 if (store_dirs_rebuilding
) {
805 eventAdd("MaintainSwapSpace", storeMaintainSwapSpace
, NULL
, 1.0, 1);
808 f
= (double) (store_swap_size
- store_swap_low
) / (store_swap_high
- store_swap_low
);
809 f
= f
< 0.0 ? 0.0 : f
> 1.0 ? 1.0 : f
;
810 max_scan
= (int) (f
* 400.0 + 100.0);
811 if ((max_remove
= stat5minClientRequests()) < 10)
813 eventAdd("MaintainSwapSpace", storeMaintainSwapSpace
, NULL
, 1.0 - f
, 1);
815 debug(20, 3) ("storeMaintainSwapSpace: f=%f, max_scan=%d, max_remove=%d\n",
816 f
, max_scan
, max_remove
);
818 while (heap_nodes(store_heap
) > 0) {
819 if (store_swap_size
< store_swap_low
)
821 if (expired
>= max_remove
)
823 if (scanned
>= max_scan
)
825 age
= heap_peepminkey(store_heap
);
826 e
= heap_extractmin(store_heap
);
827 e
->node
= NULL
; /* no longer in the heap */
829 if (storeEntryLocked(e
)) {
831 * Entry is in use ... put it in a linked list to ignore it.
833 if (!EBIT_TEST(e
->flags
, ENTRY_SPECIAL
)) {
835 * If this was a "SPECIAL" do not add it back into the heap.
836 * It will always be "SPECIAL" and therefore never removed.
838 debug(20, 4) ("storeMaintainSwapSpace: locked url %s\n",
839 (e
->mem_obj
&& e
->mem_obj
->url
) ? e
->mem_obj
->url
: storeKeyText(e
->key
));
840 linklistPush(&locked_entries
, e
);
844 } else if (storeCheckExpired(e
)) {
846 * Note: This will not check the reference age ifdef
847 * HEAP_REPLACEMENT, but it does some other useful
851 debug(20, 3) ("Released store object age %f size %d refs %d key %s\n",
852 age
, e
->swap_file_sz
, e
->refcount
, storeKeyText(e
->key
));
857 * Did not expire the object so we need to add it back
860 debug(20, 5) ("storeMaintainSwapSpace: non-expired %s\n",
861 storeKeyText(e
->key
));
862 linklistPush(&locked_entries
, e
);
865 if (store_swap_size
< store_swap_low
)
867 else if (expired
>= max_remove
)
869 else if (scanned
>= max_scan
)
873 * Bump the heap age factor.
876 store_heap
->age
= min_age
;
878 * Reinsert all bumped locked entries back into heap...
880 while ((e
= linklistShift(&locked_entries
)))
881 e
->node
= heap_insert(store_heap
, e
);
883 for (i
= 0; i
< Config
.cacheSwap
.n_configured
; i
++) {
884 sd
= &Config
.cacheSwap
.swapDirs
[i
];
885 sd
->lru_walker
= sd
->lru_list
.tail
;
889 for (i
= 0; i
< Config
.cacheSwap
.n_configured
; i
++) {
890 if (ndir
>= Config
.cacheSwap
.n_configured
)
891 ndir
= ndir
% Config
.cacheSwap
.n_configured
;
892 sd
= &Config
.cacheSwap
.swapDirs
[ndir
++];
893 if (sd
->cur_size
< sd
->high_size
)
895 if (NULL
== sd
->lru_walker
)
897 e
= sd
->lru_walker
->data
;
898 sd
->lru_walker
= sd
->lru_walker
->prev
;
902 if (storeEntryLocked(e
)) {
904 * If there is a locked entry at the tail of the LRU list,
905 * move it to the beginning to get it out of the way.
906 * Theoretically, we might have all locked objects at the
907 * tail, and then we'll never remove anything here and the
908 * LRU age will go to zero.
910 if (memInUse(MEM_STOREENTRY
) > max_scan
) {
911 storeDirLRUDelete(e
);
912 if (!EBIT_TEST(e
->flags
, ENTRY_SPECIAL
))
916 } else if (storeCheckExpired(e
)) {
921 if (expired
>= max_remove
)
923 if (scanned
>= max_scan
)
926 } while (j
> 0 && expired
< max_remove
&& scanned
< max_scan
);
928 debug(20, (expired
? 2 : 3)) ("storeMaintainSwapSpace: scanned %d/%d removed %d/%d locked %d f=%.03f\n",
929 scanned
, max_scan
, expired
, max_remove
, locked
, f
);
930 debug(20, 3) ("storeMaintainSwapSpace stats:\n");
931 debug(20, 3) (" %6d objects\n", memInUse(MEM_STOREENTRY
));
932 debug(20, 3) (" %6d were scanned\n", scanned
);
933 debug(20, 3) (" %6d were locked\n", locked
);
934 debug(20, 3) (" %6d were expired\n", expired
);
935 if (store_swap_size
< Config
.Swap
.maxSize
)
937 if (squid_curtime
- last_warn_time
< 10)
939 debug(20, 0) ("WARNING: Disk space over limit: %d KB > %d KB\n",
940 store_swap_size
, Config
.Swap
.maxSize
);
941 last_warn_time
= squid_curtime
;
945 /* release an object from a cache */
946 /* return number of objects released. */
948 storeRelease(StoreEntry
* e
)
950 debug(20, 3) ("storeRelease: Releasing: '%s'\n", storeKeyText(e
->key
));
951 /* If, for any reason we can't discard this object because of an
952 * outstanding request, mark it for pending release */
953 if (storeEntryLocked(e
)) {
955 debug(20, 3) ("storeRelease: Only setting RELEASE_REQUEST bit\n");
956 storeReleaseRequest(e
);
959 if (store_dirs_rebuilding
&& e
->swap_file_number
> -1) {
960 storeSetPrivateKey(e
);
962 storeSetMemStatus(e
, NOT_IN_MEMORY
);
963 destroy_MemObject(e
);
966 * Fake a call to storeLockObject(). When rebuilding is done,
967 * we'll just call storeUnlockObject() on these.
970 EBIT_SET(e
->flags
, RELEASE_REQUEST
);
971 stackPush(&LateReleaseStack
, e
);
974 storeLog(STORE_LOG_RELEASE
, e
);
975 if (e
->swap_file_number
> -1) {
976 storeUnlink(e
->swap_file_number
);
977 if (e
->swap_status
== SWAPOUT_DONE
)
978 if (EBIT_TEST(e
->flags
, ENTRY_VALIDATED
))
979 storeDirUpdateSwapSize(e
->swap_file_number
, e
->swap_file_sz
, -1);
980 if (!EBIT_TEST(e
->flags
, KEY_PRIVATE
))
981 storeDirSwapLog(e
, SWAP_LOG_DEL
);
982 storeSwapFileNumberSet(e
, -1);
984 storeSetMemStatus(e
, NOT_IN_MEMORY
);
985 destroy_StoreEntry(e
);
989 storeLateRelease(void *unused
)
994 if (store_dirs_rebuilding
) {
995 eventAdd("storeLateRelease", storeLateRelease
, NULL
, 1.0, 1);
998 for (i
= 0; i
< 10; i
++) {
999 e
= stackPop(&LateReleaseStack
);
1002 debug(20, 1) ("storeLateRelease: released %d objects\n", n
);
1005 storeUnlockObject(e
);
1008 eventAdd("storeLateRelease", storeLateRelease
, NULL
, 0.0, 1);
1011 /* return 1 if a store entry is locked */
1013 storeEntryLocked(const StoreEntry
* e
)
1017 if (e
->swap_status
== SWAPOUT_WRITING
)
1019 if (e
->store_status
== STORE_PENDING
)
1022 * SPECIAL, PUBLIC entries should be "locked"
1024 if (EBIT_TEST(e
->flags
, ENTRY_SPECIAL
))
1025 if (!EBIT_TEST(e
->flags
, KEY_PRIVATE
))
1031 storeEntryValidLength(const StoreEntry
* e
)
1034 const HttpReply
*reply
;
1035 assert(e
->mem_obj
!= NULL
);
1036 reply
= e
->mem_obj
->reply
;
1037 debug(20, 3) ("storeEntryValidLength: Checking '%s'\n", storeKeyText(e
->key
));
1038 debug(20, 5) ("storeEntryValidLength: object_len = %d\n",
1040 debug(20, 5) ("storeEntryValidLength: hdr_sz = %d\n",
1042 debug(20, 5) ("storeEntryValidLength: content_length = %d\n",
1043 reply
->content_length
);
1044 if (reply
->content_length
< 0) {
1045 debug(20, 5) ("storeEntryValidLength: Unspecified content length: %s\n",
1046 storeKeyText(e
->key
));
1049 if (reply
->hdr_sz
== 0) {
1050 debug(20, 5) ("storeEntryValidLength: Zero header size: %s\n",
1051 storeKeyText(e
->key
));
1054 if (e
->mem_obj
->method
== METHOD_HEAD
) {
1055 debug(20, 5) ("storeEntryValidLength: HEAD request: %s\n",
1056 storeKeyText(e
->key
));
1059 if (reply
->sline
.status
== HTTP_NOT_MODIFIED
)
1061 if (reply
->sline
.status
== HTTP_NO_CONTENT
)
1063 diff
= reply
->hdr_sz
+ reply
->content_length
- objectLen(e
);
1066 debug(20, 3) ("storeEntryValidLength: %d bytes too %s; '%s'\n",
1067 diff
< 0 ? -diff
: diff
,
1068 diff
< 0 ? "big" : "small",
1069 storeKeyText(e
->key
));
1074 storeInitHashValues(void)
1077 /* Calculate size of hash table (maximum currently 64k buckets). */
1078 i
= Config
.Swap
.maxSize
/ Config
.Store
.avgObjectSize
;
1079 debug(20, 1) ("Swap maxSize %d KB, estimated %d objects\n",
1080 Config
.Swap
.maxSize
, i
);
1081 i
/= Config
.Store
.objectsPerBucket
;
1082 debug(20, 1) ("Target number of buckets: %d\n", i
);
1083 /* ideally the full scan period should be configurable, for the
1084 * moment it remains at approximately 24 hours. */
1085 store_hash_buckets
= storeKeyHashBuckets(i
);
1086 debug(20, 1) ("Using %d Store buckets\n", store_hash_buckets
);
1087 debug(20, 1) ("Max Mem size: %d KB\n", Config
.memMaxSize
>> 10);
1088 debug(20, 1) ("Max Swap size: %d KB\n", Config
.Swap
.maxSize
);
1091 #if HEAP_REPLACEMENT
1092 #include "store_heap_replacement.c"
1099 storeInitHashValues();
1100 store_table
= hash_create(storeKeyHashCmp
,
1101 store_hash_buckets
, storeKeyHashHash
);
1104 #if HEAP_REPLACEMENT
1106 * Create new heaps with cache replacement policies attached to them.
1107 * The cache replacement policy is specified as either GDSF or LFUDA in
1108 * the squid.conf configuration file. Note that the replacement policy
1109 * applies only to the disk replacement algorithm. Memory replacement
1110 * always uses GDSF since we want to maximize object hit rate.
1112 inmem_heap
= new_heap(1000, HeapKeyGen_StoreEntry_GDSF
);
1113 if (Config
.replPolicy
) {
1114 if (tolower(Config
.replPolicy
[0]) == 'g') {
1115 debug(20, 1) ("Using GDSF disk replacement policy\n");
1116 store_heap
= new_heap(10000, HeapKeyGen_StoreEntry_GDSF
);
1117 } else if (tolower(Config
.replPolicy
[0]) == 'l') {
1118 if (tolower(Config
.replPolicy
[1]) == 'f') {
1119 debug(20, 1) ("Using LFUDA disk replacement policy\n");
1120 store_heap
= new_heap(10000, HeapKeyGen_StoreEntry_LFUDA
);
1121 } else if (tolower(Config
.replPolicy
[1]) == 'r') {
1122 debug(20, 1) ("Using LRU heap disk replacement policy\n");
1123 store_heap
= new_heap(10000, HeapKeyGen_StoreEntry_LRU
);
1126 debug(20, 1) ("Unrecognized replacement_policy; using GDSF\n");
1127 store_heap
= new_heap(10000, HeapKeyGen_StoreEntry_GDSF
);
1130 debug(20, 1) ("Using default disk replacement policy (GDSF)\n");
1131 store_heap
= new_heap(10000, HeapKeyGen_StoreEntry_GDSF
);
1134 inmem_list
.head
= inmem_list
.tail
= NULL
;
1136 stackInit(&LateReleaseStack
);
1137 eventAdd("storeLateRelease", storeLateRelease
, NULL
, 1.0, 1);
1139 storeRebuildStart();
1140 cachemgrRegister("storedir",
1141 "Store Directory Stats",
1142 storeDirStats
, 0, 1);
1143 cachemgrRegister("store_check_cachable_stats",
1144 "storeCheckCachable() Stats",
1145 storeCheckCachableStats
, 0, 1);
1149 storeConfigure(void)
1151 store_swap_high
= (long) (((float) Config
.Swap
.maxSize
*
1152 (float) Config
.Swap
.highWaterMark
) / (float) 100);
1153 store_swap_low
= (long) (((float) Config
.Swap
.maxSize
*
1154 (float) Config
.Swap
.lowWaterMark
) / (float) 100);
1155 store_pages_max
= Config
.memMaxSize
/ SM_PAGE_SIZE
;
1159 storeKeepInMemory(const StoreEntry
* e
)
1161 MemObject
*mem
= e
->mem_obj
;
1164 if (mem
->data_hdr
.head
== NULL
)
1166 return mem
->inmem_lo
== 0;
1170 storeCheckExpired(const StoreEntry
* e
)
1172 if (storeEntryLocked(e
))
1174 if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
))
1176 if (EBIT_TEST(e
->flags
, ENTRY_NEGCACHED
) && squid_curtime
>= e
->expires
)
1181 #if !HEAP_REPLACEMENT
1183 * storeExpiredReferenceAge
1185 * The LRU age is scaled exponentially between 1 minute and
1186 * Config.referenceAge , when store_swap_low < store_swap_size <
1187 * store_swap_high. This keeps store_swap_size within the low and high
1188 * water marks. If the cache is very busy then store_swap_size stays
1189 * closer to the low water mark, if it is not busy, then it will stay
1190 * near the high water mark. The LRU age value can be examined on the
1191 * cachemgr 'info' page.
1194 storeExpiredReferenceAge(void)
1199 x
= (double) (store_swap_high
- store_swap_size
) / (store_swap_high
- store_swap_low
);
1200 x
= x
< 0.0 ? 0.0 : x
> 1.0 ? 1.0 : x
;
1201 z
= pow((double) (Config
.referenceAge
/ 60), x
);
1202 age
= (time_t) (z
* 60.0);
1205 else if (age
> 31536000)
1212 storeNegativeCache(StoreEntry
* e
)
1214 e
->expires
= squid_curtime
+ Config
.negativeTtl
;
1215 EBIT_SET(e
->flags
, ENTRY_NEGCACHED
);
1219 storeFreeMemory(void)
1221 hashFreeItems(store_table
, destroy_StoreEntry
);
1222 hashFreeMemory(store_table
);
1224 #if USE_CACHE_DIGESTS
1226 cacheDigestDestroy(store_digest
);
1228 store_digest
= NULL
;
1232 expiresMoreThan(time_t expires
, time_t when
)
1234 if (expires
< 0) /* No Expires given */
1236 return (expires
> (squid_curtime
+ when
));
1240 storeEntryValidToSend(StoreEntry
* e
)
1242 if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
))
1244 if (EBIT_TEST(e
->flags
, ENTRY_NEGCACHED
))
1245 if (e
->expires
<= squid_curtime
)
1247 if (EBIT_TEST(e
->flags
, ENTRY_ABORTED
))
1253 storeTimestampsSet(StoreEntry
* entry
)
1255 const HttpReply
*reply
= entry
->mem_obj
->reply
;
1256 time_t served_date
= reply
->date
;
1257 /* make sure that 0 <= served_date <= squid_curtime */
1258 if (served_date
< 0 || served_date
> squid_curtime
)
1259 served_date
= squid_curtime
;
1260 entry
->expires
= reply
->expires
;
1261 entry
->lastmod
= reply
->last_modified
;
1262 entry
->timestamp
= served_date
;
1266 storeRegisterAbort(StoreEntry
* e
, STABH
* cb
, void *data
)
1268 MemObject
*mem
= e
->mem_obj
;
1270 assert(mem
->abort
.callback
== NULL
);
1271 mem
->abort
.callback
= cb
;
1272 mem
->abort
.data
= data
;
1276 storeUnregisterAbort(StoreEntry
* e
)
1278 MemObject
*mem
= e
->mem_obj
;
1280 mem
->abort
.callback
= NULL
;
1284 storeMemObjectDump(MemObject
* mem
)
1286 debug(20, 1) ("MemObject->data.head: %p\n",
1287 mem
->data_hdr
.head
);
1288 debug(20, 1) ("MemObject->data.tail: %p\n",
1289 mem
->data_hdr
.tail
);
1290 debug(20, 1) ("MemObject->data.origin_offset: %d\n",
1291 mem
->data_hdr
.origin_offset
);
1292 debug(20, 1) ("MemObject->start_ping: %d.%06d\n",
1293 (int) mem
->start_ping
.tv_sec
,
1294 (int) mem
->start_ping
.tv_usec
);
1295 debug(20, 1) ("MemObject->inmem_hi: %d\n",
1296 (int) mem
->inmem_hi
);
1297 debug(20, 1) ("MemObject->inmem_lo: %d\n",
1298 (int) mem
->inmem_lo
);
1299 debug(20, 1) ("MemObject->clients: %p\n",
1301 debug(20, 1) ("MemObject->nclients: %d\n",
1303 debug(20, 1) ("MemObject->reply: %p\n",
1305 debug(20, 1) ("MemObject->request: %p\n",
1307 debug(20, 1) ("MemObject->log_url: %p %s\n",
1309 checkNullString(mem
->log_url
));
1313 storeEntryDump(const StoreEntry
* e
, int l
)
1315 debug(20, l
) ("StoreEntry->key: %s\n", storeKeyText(e
->key
));
1316 debug(20, l
) ("StoreEntry->next: %p\n", e
->next
);
1317 debug(20, l
) ("StoreEntry->mem_obj: %p\n", e
->mem_obj
);
1318 debug(20, l
) ("StoreEntry->timestamp: %d\n", (int) e
->timestamp
);
1319 debug(20, l
) ("StoreEntry->lastref: %d\n", (int) e
->lastref
);
1320 debug(20, l
) ("StoreEntry->expires: %d\n", (int) e
->expires
);
1321 debug(20, l
) ("StoreEntry->lastmod: %d\n", (int) e
->lastmod
);
1322 debug(20, l
) ("StoreEntry->swap_file_sz: %d\n", (int) e
->swap_file_sz
);
1323 debug(20, l
) ("StoreEntry->refcount: %d\n", e
->refcount
);
1324 debug(20, l
) ("StoreEntry->flags: %s\n", storeEntryFlags(e
));
1325 debug(20, l
) ("StoreEntry->swap_file_number: %d\n", (int) e
->swap_file_number
);
1326 debug(20, l
) ("StoreEntry->lock_count: %d\n", (int) e
->lock_count
);
1327 debug(20, l
) ("StoreEntry->mem_status: %d\n", (int) e
->mem_status
);
1328 debug(20, l
) ("StoreEntry->ping_status: %d\n", (int) e
->ping_status
);
1329 debug(20, l
) ("StoreEntry->store_status: %d\n", (int) e
->store_status
);
1330 debug(20, l
) ("StoreEntry->swap_status: %d\n", (int) e
->swap_status
);
1334 * NOTE, this function assumes only two mem states
1337 storeSetMemStatus(StoreEntry
* e
, int new_status
)
1339 MemObject
*mem
= e
->mem_obj
;
1340 if (new_status
== e
->mem_status
)
1342 assert(mem
!= NULL
);
1343 if (new_status
== IN_MEMORY
) {
1344 assert(mem
->inmem_lo
== 0);
1345 #if HEAP_REPLACEMENT
1346 if (mem
->node
== NULL
) {
1347 if (EBIT_TEST(e
->flags
, ENTRY_SPECIAL
)) {
1348 debug(20, 4) ("storeSetMemStatus: not inserting special %s\n",
1351 mem
->node
= heap_insert(inmem_heap
, e
);
1352 debug(20, 4) ("storeSetMemStatus: inserted mem node %p\n",
1357 dlinkAdd(e
, &mem
->lru
, &inmem_list
);
1361 #if HEAP_REPLACEMENT
1363 * It's being removed from the memory heap; is it already gone?
1366 heap_delete(inmem_heap
, mem
->node
);
1367 debug(20, 4) ("storeSetMemStatus: deleted mem node %p\n",
1372 dlinkDelete(&mem
->lru
, &inmem_list
);
1376 e
->mem_status
= new_status
;
1380 storeUrl(const StoreEntry
* e
)
1383 return "[null_entry]";
1384 else if (e
->mem_obj
== NULL
)
1385 return "[null_mem_obj]";
1387 return e
->mem_obj
->url
;
1391 storeCreateMemObject(StoreEntry
* e
, const char *url
, const char *log_url
)
1395 e
->mem_obj
= new_MemObject(url
, log_url
);
1398 /* this just sets DELAY_SENDING */
1400 storeBuffer(StoreEntry
* e
)
1402 EBIT_SET(e
->flags
, DELAY_SENDING
);
1405 /* this just clears DELAY_SENDING and Invokes the handlers */
1407 storeBufferFlush(StoreEntry
* e
)
1409 EBIT_CLR(e
->flags
, DELAY_SENDING
);
1415 objectLen(const StoreEntry
* e
)
1417 assert(e
->mem_obj
!= NULL
);
1418 return e
->mem_obj
->object_sz
;
1422 contentLen(const StoreEntry
* e
)
1424 assert(e
->mem_obj
!= NULL
);
1425 assert(e
->mem_obj
->reply
!= NULL
);
1426 return e
->mem_obj
->object_sz
- e
->mem_obj
->reply
->hdr_sz
;
1430 storeEntryReply(StoreEntry
* e
)
1434 if (NULL
== e
->mem_obj
)
1436 return e
->mem_obj
->reply
;
1440 storeEntryReset(StoreEntry
* e
)
1442 MemObject
*mem
= e
->mem_obj
;
1443 debug(20, 3) ("storeEntryReset: %s\n", storeUrl(e
));
1444 assert(mem
->swapout
.sio
== NULL
);
1445 stmemFree(&mem
->data_hdr
);
1446 mem
->inmem_hi
= mem
->inmem_lo
= 0;
1447 httpReplyDestroy(mem
->reply
);
1448 mem
->reply
= httpReplyCreate();
1449 e
->expires
= e
->lastmod
= e
->timestamp
= -1;
1452 #if HEAP_REPLACEMENT
1454 storeHeapPositionUpdate(StoreEntry
* e
)
1457 heap_update(store_heap
, e
->node
, e
);
1458 if (e
->mem_obj
&& e
->mem_obj
->node
)
1459 heap_update(inmem_heap
, e
->mem_obj
->node
, e
);
1464 storeSwapFileNumberSet(StoreEntry
* e
, sfileno filn
)
1466 if (e
->swap_file_number
== filn
)
1470 storeDirMapBitReset(e
->swap_file_number
);
1471 storeDirLRUDelete(e
);
1472 e
->swap_file_number
= -1;
1474 assert(-1 == e
->swap_file_number
);
1475 storeDirMapBitSet(e
->swap_file_number
= filn
);