|
1 /* |
|
2 * Copyright (c) 2006 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of the License "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: Implementation of CHttpCacheEvictionHandler |
|
15 * |
|
16 */ |
|
17 |
|
18 // INCLUDE FILES |
|
19 #include "HttpCacheEvictionHandler.h" |
|
20 #include "HttpCacheEntry.h" |
|
21 #include "HttpCacheUtil.h" |
|
22 |
|
23 // EXTERNAL DATA STRUCTURES |
|
24 |
|
25 // EXTERNAL FUNCTION PROTOTYPES |
|
26 |
|
27 // CONSTANTS |
|
28 |
|
29 // MACROS |
|
30 |
|
31 // from KHTML loader.cpp |
|
32 #define FAST_LOG2(_log2,_n) \ |
|
33 unsigned int j_ = (unsigned int)(_n); \ |
|
34 (_log2) = 0; \ |
|
35 if ((j_) & ((j_)-1)) \ |
|
36 (_log2) += 1; \ |
|
37 if ((j_) >> 16) \ |
|
38 (_log2) += 16, (j_) >>= 16; \ |
|
39 if ((j_) >> 8) \ |
|
40 (_log2) += 8, (j_) >>= 8; \ |
|
41 if ((j_) >> 4) \ |
|
42 (_log2) += 4, (j_) >>= 4; \ |
|
43 if ((j_) >> 2) \ |
|
44 (_log2) += 2, (j_) >>= 2; \ |
|
45 if ((j_) >> 1) \ |
|
46 (_log2) += 1; |
|
47 |
|
48 const TUint KHttpCacheBucketNum = 5; |
|
49 |
|
50 // LOCAL CONSTANTS AND MACROS |
|
51 |
|
52 // MODULE DATA STRUCTURES |
|
53 |
|
54 // LOCAL FUNCTION PROTOTYPES |
|
55 |
|
56 // FORWARD DECLARATIONS |
|
57 |
|
58 // ============================= LOCAL FUNCTIONS =============================== |
|
59 |
|
60 // ============================ MEMBER FUNCTIONS =============================== |
|
61 |
|
62 // ----------------------------------------------------------------------------- |
|
63 // CHttpCacheEvictionHandler::CHttpCacheEvictionHandler |
|
64 // C++ default constructor can NOT contain any code, that |
|
65 // might leave. |
|
66 // ----------------------------------------------------------------------------- |
|
67 // |
|
68 CHttpCacheEvictionHandler::CHttpCacheEvictionHandler() |
|
69 { |
|
70 } |
|
71 |
|
72 // ----------------------------------------------------------------------------- |
|
73 // CHttpCacheEvictionHandler::ConstructL |
|
74 // Symbian 2nd phase constructor can leave. |
|
75 // ----------------------------------------------------------------------------- |
|
76 // |
|
77 void CHttpCacheEvictionHandler::ConstructL() |
|
78 { |
|
79 // 5 buckets |
|
80 // LRU, size/nref = 1 to 1 |
|
81 // LRU, size/nref = 2 to 3 |
|
82 // LRU, size/nref = 4 to 7 |
|
83 // LRU, size/nref = 8 to 15 |
|
84 // LRU, size/nref > 15 |
|
85 iBuckets = new(ELeave)CArrayPtrFlat<TBucket>( KHttpCacheBucketNum ); |
|
86 for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) |
|
87 { |
|
88 TBucket* bucket = new(ELeave)TBucket( CHttpCacheEntry::iOffset ); |
|
89 iBuckets->AppendL( bucket ); |
|
90 TBucket* bucketi = iBuckets->At( i ); |
|
91 } |
|
92 } |
|
93 |
|
94 // ----------------------------------------------------------------------------- |
|
95 // CHttpCacheEvictionHandler::NewL |
|
96 // Two-phased constructor. |
|
97 // ----------------------------------------------------------------------------- |
|
98 // |
|
99 CHttpCacheEvictionHandler* CHttpCacheEvictionHandler::NewL() |
|
100 { |
|
101 CHttpCacheEvictionHandler* self = new( ELeave ) CHttpCacheEvictionHandler(); |
|
102 |
|
103 CleanupStack::PushL( self ); |
|
104 self->ConstructL(); |
|
105 CleanupStack::Pop(); |
|
106 |
|
107 return self; |
|
108 } |
|
109 |
|
110 // Destructor |
|
111 CHttpCacheEvictionHandler::~CHttpCacheEvictionHandler() |
|
112 { |
|
113 if (iBuckets) |
|
114 { |
|
115 // delete the entries |
|
116 for( TInt i=0; i<iBuckets->Count(); ++i ) |
|
117 delete iBuckets->At( i ); |
|
118 } |
|
119 delete iBuckets; |
|
120 } |
|
121 |
|
122 // ----------------------------------------------------------------------------- |
|
123 // CHttpCacheEvictionHandler::InsertL |
|
124 // |
|
125 // ----------------------------------------------------------------------------- |
|
126 // |
|
127 void CHttpCacheEvictionHandler::Insert( |
|
128 CHttpCacheEntry& aCacheEntry ) |
|
129 { |
|
130 #ifdef __CACHELOG__ |
|
131 HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: item is inserted:" ), aCacheEntry.Url() ); |
|
132 // check double insert |
|
133 CHttpCacheEntry* entry; |
|
134 for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) |
|
135 { |
|
136 TBucketIter bucketIter( *iBuckets->At( i ) ); |
|
137 // |
|
138 bucketIter.SetToFirst(); |
|
139 while( ( entry = bucketIter++ ) != NULL ) |
|
140 { |
|
141 __ASSERT_DEBUG( ( entry != &aCacheEntry ) , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) ); |
|
142 } |
|
143 } |
|
144 // |
|
145 HttpCacheUtil::WriteLog( 0, _L( "insert entry to eviction table:" ), BucketIndex( FastLog2( aCacheEntry.Size() ) ) ); |
|
146 #endif // __CACHELOG__ |
|
147 // Objects are classified into a limited number of groups according to log2(Si/refi) |
|
148 // caclulate to which bucket it goes. |
|
149 // buckets are orderd by LRU |
|
150 Bucket( BucketIndex( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ) )->AddLast( aCacheEntry ); |
|
151 } |
|
152 |
|
153 // ----------------------------------------------------------------------------- |
|
154 // CHttpCacheEvictionHandler::Accessed |
|
155 // |
|
156 // ----------------------------------------------------------------------------- |
|
157 // |
|
158 void CHttpCacheEvictionHandler::Accessed( |
|
159 CHttpCacheEntry& aCacheEntry ) |
|
160 { |
|
161 HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: item is accessed:" ), aCacheEntry.Url() ); |
|
162 // first check where it is now |
|
163 TInt oldRef( aCacheEntry.Ref() - 1 ); |
|
164 if( oldRef > 0 ) |
|
165 { |
|
166 // |
|
167 // buckets are orderd by LRU |
|
168 // see if we need to move it to a new bucket |
|
169 TInt currentBucketIndex( BucketIndex( FastLog2( aCacheEntry.Size() / oldRef ) ) ); |
|
170 TInt newBucketIndex( BucketIndex( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ) ); |
|
171 // check if the item is really there |
|
172 TBool itemOk( ItemIsInBucket( currentBucketIndex, aCacheEntry ) ); |
|
173 |
|
174 if( itemOk ) |
|
175 { |
|
176 HttpCacheUtil::WriteLog( 0, _L( "item is in bucket:" ), currentBucketIndex ); |
|
177 if( currentBucketIndex == newBucketIndex ) |
|
178 { |
|
179 HttpCacheUtil::WriteLog( 0, _L( "move entry to the end of the bucket. it's safe there" ) ); |
|
180 TBucket* bucket( Bucket( currentBucketIndex ) ); |
|
181 // move it to the end |
|
182 if( !bucket->IsLast( &aCacheEntry ) ) |
|
183 { |
|
184 bucket->Remove( aCacheEntry ); |
|
185 bucket->AddLast( aCacheEntry ); |
|
186 } |
|
187 } |
|
188 else |
|
189 { |
|
190 HttpCacheUtil::WriteLog( 0, _L( "move item to a new bucket" ), newBucketIndex ); |
|
191 // new bucket |
|
192 TBucket* currBucket( Bucket( currentBucketIndex ) ); |
|
193 TBucket* newBucket( Bucket( newBucketIndex ) ); |
|
194 // remove from the current and add it to the |
|
195 // new as last item |
|
196 |
|
197 // make sure the item is there |
|
198 // move it to the end |
|
199 currBucket->Remove( aCacheEntry ); |
|
200 newBucket->AddLast( aCacheEntry ); |
|
201 } |
|
202 } |
|
203 else |
|
204 { |
|
205 // assert |
|
206 __ASSERT_DEBUG( EFalse , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) ); |
|
207 } |
|
208 } |
|
209 else if( oldRef == 0 ) |
|
210 { |
|
211 // first -original access. ignore it |
|
212 // as it is already placed at insert() |
|
213 } |
|
214 else |
|
215 { |
|
216 // entry with 0 starting refcount??? doh. |
|
217 __ASSERT_DEBUG( EFalse , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) ); |
|
218 } |
|
219 } |
|
220 |
|
221 // ----------------------------------------------------------------------------- |
|
222 // CHttpCacheEvictionHandler::Changed |
|
223 // |
|
224 // ----------------------------------------------------------------------------- |
|
225 // |
|
226 void CHttpCacheEvictionHandler::Changed( |
|
227 CHttpCacheEntry& /*aCacheEntry*/ ) |
|
228 { |
|
229 // check if size changed |
|
230 } |
|
231 |
|
232 // ----------------------------------------------------------------------------- |
|
233 // CHttpCacheEvictionHandler::Remove |
|
234 // |
|
235 // ----------------------------------------------------------------------------- |
|
236 // |
|
237 void CHttpCacheEvictionHandler::Remove( |
|
238 CHttpCacheEntry& aCacheEntry ) |
|
239 { |
|
240 HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: try to remove item:" ), aCacheEntry.Url() ); |
|
241 // |
|
242 TInt sizeFreqVal( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ); |
|
243 // check if the item is in the right bucket |
|
244 TInt bucketIndex( BucketIndex( sizeFreqVal ) ); |
|
245 TBucket* bucket( Bucket( bucketIndex ) ); |
|
246 TBool itemOk( ItemIsInBucket( bucketIndex, aCacheEntry ) ); |
|
247 |
|
248 if( itemOk ) |
|
249 { |
|
250 // |
|
251 HttpCacheUtil::WriteLog( 0, _L( "removed from bucket:" ), bucketIndex ); |
|
252 bucket->Remove( aCacheEntry ); |
|
253 } |
|
254 #ifdef __CACHELOG__ |
|
255 else |
|
256 { |
|
257 HttpCacheUtil::WriteLog( 0, _L( "item is not in bucket no." ), bucketIndex ); |
|
258 } |
|
259 #endif // __CACHELOG__ |
|
260 } |
|
261 |
|
262 // ----------------------------------------------------------------------------- |
|
263 // CHttpCacheEvictionHandler::Evict |
|
264 // |
|
265 // ----------------------------------------------------------------------------- |
|
266 // |
|
267 CArrayPtrFlat<CHttpCacheEntry>* CHttpCacheEvictionHandler::EvictL( |
|
268 TInt aSpaceNeeded ) |
|
269 { |
|
270 HttpCacheUtil::WriteLog( 0, _L( "need space:" ), aSpaceNeeded ); |
|
271 #ifdef __CACHELOG__ |
|
272 LogBuckets(); |
|
273 #endif // __CACHELOG__ |
|
274 // |
|
275 CArrayPtrFlat<CHttpCacheEntry>* evictedEntries = new(ELeave)CArrayPtrFlat<CHttpCacheEntry>( 10 ); |
|
276 CleanupStack::PushL( evictedEntries ); |
|
277 // |
|
278 // Each group is managed using a LRU |
|
279 // policy. The extended cost-to-size model is applied to the |
|
280 // eviction candidates from all nonempty groups, purging the |
|
281 // object with largest ( DeltaT * Size / Ref ) ->delataT == curr time - last accessed |
|
282 TTime currTime; |
|
283 currTime.HomeTime(); |
|
284 // |
|
285 while( aSpaceNeeded > 0 ) |
|
286 { |
|
287 // take one item from each bucket and |
|
288 // check who has to go |
|
289 TInt bucketInd( -1 ); |
|
290 TInt maxVal( -1 ); |
|
291 TTimeIntervalSeconds secInt; |
|
292 CHttpCacheEntry* candidate = NULL; |
|
293 for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) |
|
294 { |
|
295 CHttpCacheEntry* entry = NULL; |
|
296 TBucket* bucket = iBuckets->At( i ); |
|
297 // get the first (LRU) item from each bucket |
|
298 if( !bucket->IsEmpty() ) |
|
299 { |
|
300 entry = bucket->First(); |
|
301 } |
|
302 // evacuate nonactive entries only |
|
303 if( entry && entry->State() == CHttpCacheEntry::ECacheComplete ) |
|
304 { |
|
305 // watch out for 32 bit. it might overflow secInt. |
|
306 currTime.SecondsFrom( entry->LastAccessed(), secInt ); |
|
307 |
|
308 TInt val( secInt.Int() * entry->Size() / entry->Ref() ); |
|
309 // get the object with largest ( DeltaT * Size / Ref ) |
|
310 if( val > maxVal ) |
|
311 { |
|
312 maxVal = val; |
|
313 bucketInd = i; |
|
314 candidate = entry; |
|
315 } |
|
316 } |
|
317 } |
|
318 // remove from the bucket |
|
319 // add it to the evicted list |
|
320 // reduce space needed size |
|
321 if( candidate ) |
|
322 { |
|
323 #ifdef __CACHELOG__ |
|
324 // no protected entries should be evacuated |
|
325 if( candidate->Protected() ) |
|
326 { |
|
327 HttpCacheUtil::WriteUrlToLog( 0, _L( "PROTECTED entry is about to be removed" ), candidate->Url() ); |
|
328 } |
|
329 // |
|
330 HttpCacheUtil::WriteUrlToLog( 0, _L( "entry to remove:" ), candidate->Url() ); |
|
331 #endif //__CACHELOG__ |
|
332 // |
|
333 iBuckets->At( bucketInd )->Remove( *candidate ); |
|
334 // reduce size |
|
335 aSpaceNeeded-= candidate->Size(); |
|
336 aSpaceNeeded-= candidate->HeaderSize(); |
|
337 // |
|
338 evictedEntries->AppendL( candidate ); |
|
339 // |
|
340 HttpCacheUtil::WriteLog( 0, _L( "more space needed" ), aSpaceNeeded ); |
|
341 } |
|
342 else |
|
343 { |
|
344 // no candidate no free |
|
345 break; |
|
346 } |
|
347 } |
|
348 CleanupStack::Pop(); // evictedEntries |
|
349 return evictedEntries; |
|
350 } |
|
351 |
|
352 // ----------------------------------------------------------------------------- |
|
353 // CHttpCacheEvictionHandler::RemoveAll |
|
354 // |
|
355 // ----------------------------------------------------------------------------- |
|
356 // |
|
357 void CHttpCacheEvictionHandler::RemoveAll() |
|
358 { |
|
359 HttpCacheUtil::WriteLog( 0, _L( "Eviction table: remove all item:" ) ); |
|
360 // |
|
361 for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) |
|
362 { |
|
363 iBuckets->At( i )->Reset(); |
|
364 // |
|
365 } |
|
366 } |
|
367 |
|
368 // ----------------------------------------------------------------------------- |
|
369 // CHttpCacheEvictionHandler::Bucket |
|
370 // |
|
371 // ----------------------------------------------------------------------------- |
|
372 // |
|
373 TBucket* CHttpCacheEvictionHandler::Bucket( |
|
374 TInt aIndex ) |
|
375 { |
|
376 return iBuckets->At( aIndex ); |
|
377 } |
|
378 |
|
379 // ----------------------------------------------------------------------------- |
|
380 // CHttpCacheEvictionHandler::BucketIndex |
|
381 // |
|
382 // ----------------------------------------------------------------------------- |
|
383 // |
|
384 TInt CHttpCacheEvictionHandler::BucketIndex( |
|
385 TInt aSizeFrequencyValue ) |
|
386 { |
|
387 // last bucket by default |
|
388 TInt index( 4 ); |
|
389 // supports only 5 buckets at the moment |
|
390 if( aSizeFrequencyValue == 1 ) |
|
391 { |
|
392 index = 0; |
|
393 } |
|
394 else if( aSizeFrequencyValue < 4 ) |
|
395 { |
|
396 index = 1; |
|
397 } |
|
398 else if( aSizeFrequencyValue < 8 ) |
|
399 { |
|
400 index = 2; |
|
401 } |
|
402 else if( aSizeFrequencyValue < 16 ) |
|
403 { |
|
404 index = 3; |
|
405 } |
|
406 return index; |
|
407 } |
|
408 |
|
409 // ----------------------------------------------------------------------------- |
|
410 // CHttpCacheEvictionHandler::ItemIsInBucket |
|
411 // |
|
412 // ----------------------------------------------------------------------------- |
|
413 // |
|
414 TBool CHttpCacheEvictionHandler::ItemIsInBucket( |
|
415 TInt aBucketIndex, |
|
416 const CHttpCacheEntry& aCacheEntry ) |
|
417 { |
|
418 TBool found( EFalse ); |
|
419 CHttpCacheEntry* entry; |
|
420 |
|
421 TBucketIter bucketIter( *(iBuckets->At( aBucketIndex )) ); |
|
422 // |
|
423 bucketIter.SetToFirst(); |
|
424 while( ( entry = bucketIter++ ) != NULL ) |
|
425 { |
|
426 if( entry == &aCacheEntry ) |
|
427 { |
|
428 found = ETrue; |
|
429 break; |
|
430 } |
|
431 } |
|
432 #ifdef __CACHELOG__ |
|
433 if( !found ) |
|
434 { |
|
435 HttpCacheUtil::WriteLog( 0, _L( "Eviction table: item NOT FOUND" ) ); |
|
436 } |
|
437 #endif // __CACHELOG__ |
|
438 return found; |
|
439 } |
|
440 |
|
441 // ----------------------------------------------------------------------------- |
|
442 // CHttpCacheEvictionHandler::FastLog2 |
|
443 // |
|
444 // ----------------------------------------------------------------------------- |
|
445 // |
|
446 TInt CHttpCacheEvictionHandler::FastLog2( |
|
447 TUint aNum ) |
|
448 { |
|
449 TInt log2; |
|
450 FAST_LOG2( log2, aNum ); |
|
451 return log2; |
|
452 } |
|
453 |
|
454 #ifdef __CACHELOG__ |
|
455 // ----------------------------------------------------------------------------- |
|
456 // CHttpCacheEvictionHandler::LogBuckets |
|
457 // |
|
458 // ----------------------------------------------------------------------------- |
|
459 // |
|
460 void CHttpCacheEvictionHandler::LogBuckets() |
|
461 { |
|
462 CHttpCacheEntry* entry; |
|
463 for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) |
|
464 { |
|
465 HttpCacheUtil::WriteLog( 0, _L( "------------------------------" ), i ); |
|
466 |
|
467 TBucketIter bucketIter( *(iBuckets->At( i )) ); |
|
468 // |
|
469 bucketIter.SetToFirst(); |
|
470 while( ( entry = bucketIter++ ) != NULL ) |
|
471 { |
|
472 _LIT( KDateString,"%D%M%Y%/0%1%/1%2%/2%3%/3 %-B%:0%J%:1%T%:2%S%.%*C4%:3%+B"); |
|
473 _LIT( KRefSizeString,"size: %d refcount:%d"); |
|
474 |
|
475 TBuf<50> refStr; |
|
476 TBuf<50> lastAccessedStr; |
|
477 |
|
478 TTime lastAccessed( entry->LastAccessed() ); |
|
479 lastAccessed.FormatL( lastAccessedStr, KDateString ); |
|
480 // add size/refcount |
|
481 refStr.Format( KRefSizeString, entry->Size(), entry->Ref() ); |
|
482 // copy to 8bit string |
|
483 HttpCacheUtil::WriteUrlToLog( 0, refStr, entry->Url() ); |
|
484 HttpCacheUtil::WriteLog( 0, lastAccessedStr ); |
|
485 } |
|
486 } |
|
487 } |
|
488 #endif // __CACHELOG__ |
|
489 |
|
490 // End of File |