The Tor Browser / file comparison

comparison: netwerk/cache/nsMemoryCacheDevice.cpp

netwerk/cache/nsMemoryCacheDevice.cpp

branch
TOR_BUG_9701
changeset 9
a63d609f5ebe
equal deleted inserted replaced
-1:000000000000 0:f1aacd68c34f
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /* vim: set ts=8 sts=4 et sw=4 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "nsCache.h"
8 #include "nsMemoryCacheDevice.h"
9 #include "nsCacheService.h"
10 #include "nsICacheService.h"
11 #include "nsICacheVisitor.h"
12 #include "nsIStorageStream.h"
13 #include "nsCRT.h"
14 #include "nsReadableUtils.h"
15 #include "mozilla/MathAlgorithms.h"
16 #include "mozilla/Telemetry.h"
17 #include <algorithm>
18
19 // The memory cache implements the "LRU-SP" caching algorithm
20 // described in "LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement
21 // Algorithm for Web Caching" by Kai Cheng and Yahiko Kambayashi.
22
23 // We keep kQueueCount LRU queues, which should be about ceil(log2(mHardLimit))
24 // The queues hold exponentially increasing ranges of floor(log2((size/nref)))
25 // values for entries.
26 // Entries larger than 2^(kQueueCount-1) go in the last queue.
27 // Entries with no expiration go in the first queue.
28
29 const char *gMemoryDeviceID = "memory";
30
31
32 nsMemoryCacheDevice::nsMemoryCacheDevice()
33 : mInitialized(false),
34 mHardLimit(4 * 1024 * 1024), // default, if no pref
35 mSoftLimit((mHardLimit * 9) / 10), // default, if no pref
36 mTotalSize(0),
37 mInactiveSize(0),
38 mEntryCount(0),
39 mMaxEntryCount(0),
40 mMaxEntrySize(-1) // -1 means "no limit"
41 {
42 for (int i=0; i<kQueueCount; ++i)
43 PR_INIT_CLIST(&mEvictionList[i]);
44 }
45
46
47 nsMemoryCacheDevice::~nsMemoryCacheDevice()
48 {
49 Shutdown();
50 }
51
52
53 nsresult
54 nsMemoryCacheDevice::Init()
55 {
56 if (mInitialized) return NS_ERROR_ALREADY_INITIALIZED;
57
58 nsresult rv = mMemCacheEntries.Init();
59 mInitialized = NS_SUCCEEDED(rv);
60 return rv;
61 }
62
63
64 nsresult
65 nsMemoryCacheDevice::Shutdown()
66 {
67 NS_ASSERTION(mInitialized, "### attempting shutdown while not initialized");
68 NS_ENSURE_TRUE(mInitialized, NS_ERROR_NOT_INITIALIZED);
69
70 mMemCacheEntries.Shutdown();
71
72 // evict all entries
73 nsCacheEntry * entry, * next;
74
75 for (int i = kQueueCount - 1; i >= 0; --i) {
76 entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
77 while (entry != &mEvictionList[i]) {
78 NS_ASSERTION(!entry->IsInUse(), "### shutting down with active entries");
79 next = (nsCacheEntry *)PR_NEXT_LINK(entry);
80 PR_REMOVE_AND_INIT_LINK(entry);
81
82 // update statistics
83 int32_t memoryRecovered = (int32_t)entry->DataSize();
84 mTotalSize -= memoryRecovered;
85 mInactiveSize -= memoryRecovered;
86 --mEntryCount;
87
88 delete entry;
89 entry = next;
90 }
91 }
92
93 /*
94 * we're not factoring in changes to meta data yet...
95 * NS_ASSERTION(mTotalSize == 0, "### mem cache leaking entries?");
96 */
97 NS_ASSERTION(mInactiveSize == 0, "### mem cache leaking entries?");
98 NS_ASSERTION(mEntryCount == 0, "### mem cache leaking entries?");
99
100 mInitialized = false;
101
102 return NS_OK;
103 }
104
105
106 const char *
107 nsMemoryCacheDevice::GetDeviceID()
108 {
109 return gMemoryDeviceID;
110 }
111
112
113 nsCacheEntry *
114 nsMemoryCacheDevice::FindEntry(nsCString * key, bool *collision)
115 {
116 mozilla::Telemetry::AutoTimer<mozilla::Telemetry::CACHE_MEMORY_SEARCH_2> timer;
117 nsCacheEntry * entry = mMemCacheEntries.GetEntry(key);
118 if (!entry) return nullptr;
119
120 // move entry to the tail of an eviction list
121 PR_REMOVE_AND_INIT_LINK(entry);
122 PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, 0)]);
123
124 mInactiveSize -= entry->DataSize();
125
126 return entry;
127 }
128
129
130 nsresult
131 nsMemoryCacheDevice::DeactivateEntry(nsCacheEntry * entry)
132 {
133 CACHE_LOG_DEBUG(("nsMemoryCacheDevice::DeactivateEntry for entry 0x%p\n",
134 entry));
135 if (entry->IsDoomed()) {
136 #ifdef DEBUG
137 // XXX verify we've removed it from mMemCacheEntries & eviction list
138 #endif
139 delete entry;
140 CACHE_LOG_DEBUG(("deleted doomed entry 0x%p\n", entry));
141 return NS_OK;
142 }
143
144 #ifdef DEBUG
145 nsCacheEntry * ourEntry = mMemCacheEntries.GetEntry(entry->Key());
146 NS_ASSERTION(ourEntry, "DeactivateEntry called for an entry we don't have!");
147 NS_ASSERTION(entry == ourEntry, "entry doesn't match ourEntry");
148 if (ourEntry != entry)
149 return NS_ERROR_INVALID_POINTER;
150 #endif
151
152 mInactiveSize += entry->DataSize();
153 EvictEntriesIfNecessary();
154
155 return NS_OK;
156 }
157
158
159 nsresult
160 nsMemoryCacheDevice::BindEntry(nsCacheEntry * entry)
161 {
162 if (!entry->IsDoomed()) {
163 NS_ASSERTION(PR_CLIST_IS_EMPTY(entry),"entry is already on a list!");
164
165 // append entry to the eviction list
166 PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, 0)]);
167
168 // add entry to hashtable of mem cache entries
169 nsresult rv = mMemCacheEntries.AddEntry(entry);
170 if (NS_FAILED(rv)) {
171 PR_REMOVE_AND_INIT_LINK(entry);
172 return rv;
173 }
174
175 // add size of entry to memory totals
176 ++mEntryCount;
177 if (mMaxEntryCount < mEntryCount) mMaxEntryCount = mEntryCount;
178
179 mTotalSize += entry->DataSize();
180 EvictEntriesIfNecessary();
181 }
182
183 return NS_OK;
184 }
185
186
187 void
188 nsMemoryCacheDevice::DoomEntry(nsCacheEntry * entry)
189 {
190 #ifdef DEBUG
191 // debug code to verify we have entry
192 nsCacheEntry * hashEntry = mMemCacheEntries.GetEntry(entry->Key());
193 if (!hashEntry) NS_WARNING("no entry for key");
194 else if (entry != hashEntry) NS_WARNING("entry != hashEntry");
195 #endif
196 CACHE_LOG_DEBUG(("Dooming entry 0x%p in memory cache\n", entry));
197 EvictEntry(entry, DO_NOT_DELETE_ENTRY);
198 }
199
200
201 nsresult
202 nsMemoryCacheDevice::OpenInputStreamForEntry( nsCacheEntry * entry,
203 nsCacheAccessMode mode,
204 uint32_t offset,
205 nsIInputStream ** result)
206 {
207 NS_ENSURE_ARG_POINTER(entry);
208 NS_ENSURE_ARG_POINTER(result);
209
210 nsCOMPtr<nsIStorageStream> storage;
211 nsresult rv;
212
213 nsISupports *data = entry->Data();
214 if (data) {
215 storage = do_QueryInterface(data, &rv);
216 if (NS_FAILED(rv))
217 return rv;
218 }
219 else {
220 rv = NS_NewStorageStream(4096, uint32_t(-1), getter_AddRefs(storage));
221 if (NS_FAILED(rv))
222 return rv;
223 entry->SetData(storage);
224 }
225
226 return storage->NewInputStream(offset, result);
227 }
228
229
230 nsresult
231 nsMemoryCacheDevice::OpenOutputStreamForEntry( nsCacheEntry * entry,
232 nsCacheAccessMode mode,
233 uint32_t offset,
234 nsIOutputStream ** result)
235 {
236 NS_ENSURE_ARG_POINTER(entry);
237 NS_ENSURE_ARG_POINTER(result);
238
239 nsCOMPtr<nsIStorageStream> storage;
240 nsresult rv;
241
242 nsISupports *data = entry->Data();
243 if (data) {
244 storage = do_QueryInterface(data, &rv);
245 if (NS_FAILED(rv))
246 return rv;
247 }
248 else {
249 rv = NS_NewStorageStream(4096, uint32_t(-1), getter_AddRefs(storage));
250 if (NS_FAILED(rv))
251 return rv;
252 entry->SetData(storage);
253 }
254
255 return storage->GetOutputStream(offset, result);
256 }
257
258
259 nsresult
260 nsMemoryCacheDevice::GetFileForEntry( nsCacheEntry * entry,
261 nsIFile ** result )
262 {
263 return NS_ERROR_NOT_IMPLEMENTED;
264 }
265
266 bool
267 nsMemoryCacheDevice::EntryIsTooBig(int64_t entrySize)
268 {
269 CACHE_LOG_DEBUG(("nsMemoryCacheDevice::EntryIsTooBig "
270 "[size=%d max=%d soft=%d]\n",
271 entrySize, mMaxEntrySize, mSoftLimit));
272 if (mMaxEntrySize == -1)
273 return entrySize > mSoftLimit;
274 else
275 return (entrySize > mSoftLimit || entrySize > mMaxEntrySize);
276 }
277
278 size_t
279 nsMemoryCacheDevice::TotalSize()
280 {
281 return mTotalSize;
282 }
283
284 nsresult
285 nsMemoryCacheDevice::OnDataSizeChange( nsCacheEntry * entry, int32_t deltaSize)
286 {
287 if (entry->IsStreamData()) {
288 // we have the right to refuse or pre-evict
289 uint32_t newSize = entry->DataSize() + deltaSize;
290 if (EntryIsTooBig(newSize)) {
291 #ifdef DEBUG
292 nsresult rv =
293 #endif
294 nsCacheService::DoomEntry(entry);
295 NS_ASSERTION(NS_SUCCEEDED(rv),"DoomEntry() failed.");
296 return NS_ERROR_ABORT;
297 }
298 }
299
300 // adjust our totals
301 mTotalSize += deltaSize;
302
303 if (!entry->IsDoomed()) {
304 // move entry to the tail of the appropriate eviction list
305 PR_REMOVE_AND_INIT_LINK(entry);
306 PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, deltaSize)]);
307 }
308
309 EvictEntriesIfNecessary();
310 return NS_OK;
311 }
312
313
314 void
315 nsMemoryCacheDevice::AdjustMemoryLimits(int32_t softLimit, int32_t hardLimit)
316 {
317 mSoftLimit = softLimit;
318 mHardLimit = hardLimit;
319
320 // First, evict entries that won't fit into the new cache size.
321 EvictEntriesIfNecessary();
322 }
323
324
325 void
326 nsMemoryCacheDevice::EvictEntry(nsCacheEntry * entry, bool deleteEntry)
327 {
328 CACHE_LOG_DEBUG(("Evicting entry 0x%p from memory cache, deleting: %d\n",
329 entry, deleteEntry));
330 // remove entry from our hashtable
331 mMemCacheEntries.RemoveEntry(entry);
332
333 // remove entry from the eviction list
334 PR_REMOVE_AND_INIT_LINK(entry);
335
336 // update statistics
337 int32_t memoryRecovered = (int32_t)entry->DataSize();
338 mTotalSize -= memoryRecovered;
339 if (!entry->IsDoomed())
340 mInactiveSize -= memoryRecovered;
341 --mEntryCount;
342
343 if (deleteEntry) delete entry;
344 }
345
346
347 void
348 nsMemoryCacheDevice::EvictEntriesIfNecessary(void)
349 {
350 nsCacheEntry * entry;
351 nsCacheEntry * maxEntry;
352 CACHE_LOG_DEBUG(("EvictEntriesIfNecessary. mTotalSize: %d, mHardLimit: %d,"
353 "mInactiveSize: %d, mSoftLimit: %d\n",
354 mTotalSize, mHardLimit, mInactiveSize, mSoftLimit));
355
356 if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
357 return;
358
359 uint32_t now = SecondsFromPRTime(PR_Now());
360 uint64_t entryCost = 0;
361 uint64_t maxCost = 0;
362 do {
363 // LRU-SP eviction selection: Check the head of each segment (each
364 // eviction list, kept in LRU order) and select the maximal-cost
365 // entry for eviction. Cost is time-since-accessed * size / nref.
366 maxEntry = 0;
367 for (int i = kQueueCount - 1; i >= 0; --i) {
368 entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
369
370 // If the head of a list is in use, check the next available entry
371 while ((entry != &mEvictionList[i]) &&
372 (entry->IsInUse())) {
373 entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
374 }
375
376 if (entry != &mEvictionList[i]) {
377 entryCost = (uint64_t)
378 (now - entry->LastFetched()) * entry->DataSize() /
379 std::max(1, entry->FetchCount());
380 if (!maxEntry || (entryCost > maxCost)) {
381 maxEntry = entry;
382 maxCost = entryCost;
383 }
384 }
385 }
386 if (maxEntry) {
387 EvictEntry(maxEntry, DELETE_ENTRY);
388 } else {
389 break;
390 }
391 }
392 while ((mTotalSize >= mHardLimit) || (mInactiveSize >= mSoftLimit));
393 }
394
395
396 int
397 nsMemoryCacheDevice::EvictionList(nsCacheEntry * entry, int32_t deltaSize)
398 {
399 // favor items which never expire by putting them in the lowest-index queue
400 if (entry->ExpirationTime() == nsICache::NO_EXPIRATION_TIME)
401 return 0;
402
403 // compute which eviction queue this entry should go into,
404 // based on floor(log2(size/nref))
405 int32_t size = deltaSize + (int32_t)entry->DataSize();
406 int32_t fetchCount = std::max(1, entry->FetchCount());
407
408 return std::min((int)mozilla::FloorLog2(size / fetchCount), kQueueCount - 1);
409 }
410
411
412 nsresult
413 nsMemoryCacheDevice::Visit(nsICacheVisitor * visitor)
414 {
415 nsMemoryCacheDeviceInfo * deviceInfo = new nsMemoryCacheDeviceInfo(this);
416 nsCOMPtr<nsICacheDeviceInfo> deviceRef(deviceInfo);
417 if (!deviceInfo) return NS_ERROR_OUT_OF_MEMORY;
418
419 bool keepGoing;
420 nsresult rv = visitor->VisitDevice(gMemoryDeviceID, deviceInfo, &keepGoing);
421 if (NS_FAILED(rv)) return rv;
422
423 if (!keepGoing)
424 return NS_OK;
425
426 nsCacheEntry * entry;
427 nsCOMPtr<nsICacheEntryInfo> entryRef;
428
429 for (int i = kQueueCount - 1; i >= 0; --i) {
430 entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
431 while (entry != &mEvictionList[i]) {
432 nsCacheEntryInfo * entryInfo = new nsCacheEntryInfo(entry);
433 if (!entryInfo) return NS_ERROR_OUT_OF_MEMORY;
434 entryRef = entryInfo;
435
436 rv = visitor->VisitEntry(gMemoryDeviceID, entryInfo, &keepGoing);
437 entryInfo->DetachEntry();
438 if (NS_FAILED(rv)) return rv;
439 if (!keepGoing) break;
440
441 entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
442 }
443 }
444 return NS_OK;
445 }
446
447
448 static bool
449 IsEntryPrivate(nsCacheEntry* entry, void* args)
450 {
451 return entry->IsPrivate();
452 }
453
454 struct ClientIDArgs {
455 const char* clientID;
456 uint32_t prefixLength;
457 };
458
459 static bool
460 EntryMatchesClientID(nsCacheEntry* entry, void* args)
461 {
462 const char * clientID = static_cast<ClientIDArgs*>(args)->clientID;
463 uint32_t prefixLength = static_cast<ClientIDArgs*>(args)->prefixLength;
464 const char * key = entry->Key()->get();
465 return !clientID || nsCRT::strncmp(clientID, key, prefixLength) == 0;
466 }
467
468 nsresult
469 nsMemoryCacheDevice::DoEvictEntries(bool (*matchFn)(nsCacheEntry* entry, void* args), void* args)
470 {
471 nsCacheEntry * entry;
472
473 for (int i = kQueueCount - 1; i >= 0; --i) {
474 PRCList * elem = PR_LIST_HEAD(&mEvictionList[i]);
475 while (elem != &mEvictionList[i]) {
476 entry = (nsCacheEntry *)elem;
477 elem = PR_NEXT_LINK(elem);
478
479 if (!matchFn(entry, args))
480 continue;
481
482 if (entry->IsInUse()) {
483 nsresult rv = nsCacheService::DoomEntry(entry);
484 if (NS_FAILED(rv)) {
485 CACHE_LOG_WARNING(("memCache->DoEvictEntries() aborted: rv =%x", rv));
486 return rv;
487 }
488 } else {
489 EvictEntry(entry, DELETE_ENTRY);
490 }
491 }
492 }
493
494 return NS_OK;
495 }
496
497 nsresult
498 nsMemoryCacheDevice::EvictEntries(const char * clientID)
499 {
500 ClientIDArgs args = {clientID, clientID ? uint32_t(strlen(clientID)) : 0};
501 return DoEvictEntries(&EntryMatchesClientID, &args);
502 }
503
504 nsresult
505 nsMemoryCacheDevice::EvictPrivateEntries()
506 {
507 return DoEvictEntries(&IsEntryPrivate, nullptr);
508 }
509
510
511 // WARNING: SetCapacity can get called before Init()
512 void
513 nsMemoryCacheDevice::SetCapacity(int32_t capacity)
514 {
515 int32_t hardLimit = capacity * 1024; // convert k into bytes
516 int32_t softLimit = (hardLimit * 9) / 10;
517 AdjustMemoryLimits(softLimit, hardLimit);
518 }
519
520 void
521 nsMemoryCacheDevice::SetMaxEntrySize(int32_t maxSizeInKilobytes)
522 {
523 // Internal unit is bytes. Changing this only takes effect *after* the
524 // change and has no consequences for existing cache-entries
525 if (maxSizeInKilobytes >= 0)
526 mMaxEntrySize = maxSizeInKilobytes * 1024;
527 else
528 mMaxEntrySize = -1;
529 }
530
531 #ifdef DEBUG
532 static PLDHashOperator
533 CountEntry(PLDHashTable * table, PLDHashEntryHdr * hdr, uint32_t number, void * arg)
534 {
535 int32_t *entryCount = (int32_t *)arg;
536 ++(*entryCount);
537 return PL_DHASH_NEXT;
538 }
539
540 void
541 nsMemoryCacheDevice::CheckEntryCount()
542 {
543 if (!mInitialized) return;
544
545 int32_t evictionListCount = 0;
546 for (int i=0; i<kQueueCount; ++i) {
547 PRCList * elem = PR_LIST_HEAD(&mEvictionList[i]);
548 while (elem != &mEvictionList[i]) {
549 elem = PR_NEXT_LINK(elem);
550 ++evictionListCount;
551 }
552 }
553 NS_ASSERTION(mEntryCount == evictionListCount, "### mem cache badness");
554
555 int32_t entryCount = 0;
556 mMemCacheEntries.VisitEntries(CountEntry, &entryCount);
557 NS_ASSERTION(mEntryCount == entryCount, "### mem cache badness");
558 }
559 #endif
560
561 /******************************************************************************
562 * nsMemoryCacheDeviceInfo - for implementing about:cache
563 *****************************************************************************/
564
565
566 NS_IMPL_ISUPPORTS(nsMemoryCacheDeviceInfo, nsICacheDeviceInfo)
567
568
569 NS_IMETHODIMP
570 nsMemoryCacheDeviceInfo::GetDescription(char ** result)
571 {
572 NS_ENSURE_ARG_POINTER(result);
573 *result = NS_strdup("Memory cache device");
574 if (!*result) return NS_ERROR_OUT_OF_MEMORY;
575 return NS_OK;
576 }
577
578
579 NS_IMETHODIMP
580 nsMemoryCacheDeviceInfo::GetUsageReport(char ** result)
581 {
582 NS_ENSURE_ARG_POINTER(result);
583 nsCString buffer;
584
585 buffer.AssignLiteral(" <tr>\n"
586 " <th>Inactive storage:</th>\n"
587 " <td>");
588 buffer.AppendInt(mDevice->mInactiveSize / 1024);
589 buffer.AppendLiteral(" KiB</td>\n"
590 " </tr>\n");
591
592 *result = ToNewCString(buffer);
593 if (!*result) return NS_ERROR_OUT_OF_MEMORY;
594 return NS_OK;
595 }
596
597
598 NS_IMETHODIMP
599 nsMemoryCacheDeviceInfo::GetEntryCount(uint32_t * result)
600 {
601 NS_ENSURE_ARG_POINTER(result);
602 // XXX compare calculated count vs. mEntryCount
603 *result = (uint32_t)mDevice->mEntryCount;
604 return NS_OK;
605 }
606
607
608 NS_IMETHODIMP
609 nsMemoryCacheDeviceInfo::GetTotalSize(uint32_t * result)
610 {
611 NS_ENSURE_ARG_POINTER(result);
612 *result = (uint32_t)mDevice->mTotalSize;
613 return NS_OK;
614 }
615
616
617 NS_IMETHODIMP
618 nsMemoryCacheDeviceInfo::GetMaximumSize(uint32_t * result)
619 {
620 NS_ENSURE_ARG_POINTER(result);
621 *result = (uint32_t)mDevice->mHardLimit;
622 return NS_OK;
623 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial