diff -r 000000000000 -r dd21522fd290 webengine/osswebengine/cache/src/HttpCacheEvictionHandler.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/webengine/osswebengine/cache/src/HttpCacheEvictionHandler.cpp Mon Mar 30 12:54:55 2009 +0300 @@ -0,0 +1,490 @@ +/* +* Copyright (c) 2006 Nokia Corporation and/or its subsidiary(-ies). +* All rights reserved. +* This component and the accompanying materials are made available +* under the terms of the License "Eclipse Public License v1.0" +* which accompanies this distribution, and is available +* at the URL "http://www.eclipse.org/legal/epl-v10.html". +* +* Initial Contributors: +* Nokia Corporation - initial contribution. +* +* Contributors: +* +* Description: Implementation of CHttpCacheEvictionHandler +* +*/ + +// INCLUDE FILES +#include "HttpCacheEvictionHandler.h" +#include "HttpCacheEntry.h" +#include "HttpCacheUtil.h" + +// EXTERNAL DATA STRUCTURES + +// EXTERNAL FUNCTION PROTOTYPES + +// CONSTANTS + +// MACROS + +// from KHTML loader.cpp +#define FAST_LOG2(_log2,_n) \ + unsigned int j_ = (unsigned int)(_n); \ + (_log2) = 0; \ + if ((j_) & ((j_)-1)) \ + (_log2) += 1; \ + if ((j_) >> 16) \ + (_log2) += 16, (j_) >>= 16; \ + if ((j_) >> 8) \ + (_log2) += 8, (j_) >>= 8; \ + if ((j_) >> 4) \ + (_log2) += 4, (j_) >>= 4; \ + if ((j_) >> 2) \ + (_log2) += 2, (j_) >>= 2; \ + if ((j_) >> 1) \ + (_log2) += 1; + +const TUint KHttpCacheBucketNum = 5; + +// LOCAL CONSTANTS AND MACROS + +// MODULE DATA STRUCTURES + +// LOCAL FUNCTION PROTOTYPES + +// FORWARD DECLARATIONS + +// ============================= LOCAL FUNCTIONS =============================== + +// ============================ MEMBER FUNCTIONS =============================== + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::CHttpCacheEvictionHandler +// C++ default constructor can NOT contain any code, that +// might leave. +// ----------------------------------------------------------------------------- +// +CHttpCacheEvictionHandler::CHttpCacheEvictionHandler() + { + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::ConstructL +// Symbian 2nd phase constructor can leave. +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::ConstructL() + { + // 5 buckets + // LRU, size/nref = 1 to 1 + // LRU, size/nref = 2 to 3 + // LRU, size/nref = 4 to 7 + // LRU, size/nref = 8 to 15 + // LRU, size/nref > 15 + iBuckets = new(ELeave)CArrayPtrFlat( KHttpCacheBucketNum ); + for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) + { + TBucket* bucket = new(ELeave)TBucket( CHttpCacheEntry::iOffset ); + iBuckets->AppendL( bucket ); + TBucket* bucketi = iBuckets->At( i ); + } + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::NewL +// Two-phased constructor. +// ----------------------------------------------------------------------------- +// +CHttpCacheEvictionHandler* CHttpCacheEvictionHandler::NewL() + { + CHttpCacheEvictionHandler* self = new( ELeave ) CHttpCacheEvictionHandler(); + + CleanupStack::PushL( self ); + self->ConstructL(); + CleanupStack::Pop(); + + return self; + } + +// Destructor +CHttpCacheEvictionHandler::~CHttpCacheEvictionHandler() + { + if (iBuckets) + { + // delete the entries + for( TInt i=0; iCount(); ++i ) + delete iBuckets->At( i ); + } + delete iBuckets; + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::InsertL +// +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::Insert( + CHttpCacheEntry& aCacheEntry ) + { +#ifdef __CACHELOG__ + HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: item is inserted:" ), aCacheEntry.Url() ); + // check double insert + CHttpCacheEntry* entry; + for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) + { + TBucketIter bucketIter( *iBuckets->At( i ) ); + // + bucketIter.SetToFirst(); + while( ( entry = bucketIter++ ) != NULL ) + { + __ASSERT_DEBUG( ( entry != &aCacheEntry ) , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) ); + } + } + // + HttpCacheUtil::WriteLog( 0, _L( "insert entry to eviction table:" ), BucketIndex( FastLog2( aCacheEntry.Size() ) ) ); +#endif // __CACHELOG__ + // Objects are classified into a limited number of groups according to log2(Si/refi) + // caclulate to which bucket it goes. + // buckets are orderd by LRU + Bucket( BucketIndex( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ) )->AddLast( aCacheEntry ); + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::Accessed +// +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::Accessed( + CHttpCacheEntry& aCacheEntry ) + { + HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: item is accessed:" ), aCacheEntry.Url() ); + // first check where it is now + TInt oldRef( aCacheEntry.Ref() - 1 ); + if( oldRef > 0 ) + { + // + // buckets are orderd by LRU + // see if we need to move it to a new bucket + TInt currentBucketIndex( BucketIndex( FastLog2( aCacheEntry.Size() / oldRef ) ) ); + TInt newBucketIndex( BucketIndex( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ) ); + // check if the item is really there + TBool itemOk( ItemIsInBucket( currentBucketIndex, aCacheEntry ) ); + + if( itemOk ) + { + HttpCacheUtil::WriteLog( 0, _L( "item is in bucket:" ), currentBucketIndex ); + if( currentBucketIndex == newBucketIndex ) + { + HttpCacheUtil::WriteLog( 0, _L( "move entry to the end of the bucket. it's safe there" ) ); + TBucket* bucket( Bucket( currentBucketIndex ) ); + // move it to the end + if( !bucket->IsLast( &aCacheEntry ) ) + { + bucket->Remove( aCacheEntry ); + bucket->AddLast( aCacheEntry ); + } + } + else + { + HttpCacheUtil::WriteLog( 0, _L( "move item to a new bucket" ), newBucketIndex ); + // new bucket + TBucket* currBucket( Bucket( currentBucketIndex ) ); + TBucket* newBucket( Bucket( newBucketIndex ) ); + // remove from the current and add it to the + // new as last item + + // make sure the item is there + // move it to the end + currBucket->Remove( aCacheEntry ); + newBucket->AddLast( aCacheEntry ); + } + } + else + { + // assert + __ASSERT_DEBUG( EFalse , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) ); + } + } + else if( oldRef == 0 ) + { + // first -original access. ignore it + // as it is already placed at insert() + } + else + { + // entry with 0 starting refcount??? doh. + __ASSERT_DEBUG( EFalse , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) ); + } + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::Changed +// +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::Changed( + CHttpCacheEntry& /*aCacheEntry*/ ) + { + // check if size changed + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::Remove +// +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::Remove( + CHttpCacheEntry& aCacheEntry ) + { + HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: try to remove item:" ), aCacheEntry.Url() ); + // + TInt sizeFreqVal( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ); + // check if the item is in the right bucket + TInt bucketIndex( BucketIndex( sizeFreqVal ) ); + TBucket* bucket( Bucket( bucketIndex ) ); + TBool itemOk( ItemIsInBucket( bucketIndex, aCacheEntry ) ); + + if( itemOk ) + { + // + HttpCacheUtil::WriteLog( 0, _L( "removed from bucket:" ), bucketIndex ); + bucket->Remove( aCacheEntry ); + } +#ifdef __CACHELOG__ + else + { + HttpCacheUtil::WriteLog( 0, _L( "item is not in bucket no." ), bucketIndex ); + } +#endif // __CACHELOG__ + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::Evict +// +// ----------------------------------------------------------------------------- +// +CArrayPtrFlat* CHttpCacheEvictionHandler::EvictL( + TInt aSpaceNeeded ) + { + HttpCacheUtil::WriteLog( 0, _L( "need space:" ), aSpaceNeeded ); +#ifdef __CACHELOG__ + LogBuckets(); +#endif // __CACHELOG__ + // + CArrayPtrFlat* evictedEntries = new(ELeave)CArrayPtrFlat( 10 ); + CleanupStack::PushL( evictedEntries ); + // + // Each group is managed using a LRU + // policy. The extended cost-to-size model is applied to the + // eviction candidates from all nonempty groups, purging the + // object with largest ( DeltaT * Size / Ref ) ->delataT == curr time - last accessed + TTime currTime; + currTime.HomeTime(); + // + while( aSpaceNeeded > 0 ) + { + // take one item from each bucket and + // check who has to go + TInt bucketInd( -1 ); + TInt maxVal( -1 ); + TTimeIntervalSeconds secInt; + CHttpCacheEntry* candidate = NULL; + for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) + { + CHttpCacheEntry* entry = NULL; + TBucket* bucket = iBuckets->At( i ); + // get the first (LRU) item from each bucket + if( !bucket->IsEmpty() ) + { + entry = bucket->First(); + } + // evacuate nonactive entries only + if( entry && entry->State() == CHttpCacheEntry::ECacheComplete ) + { + // watch out for 32 bit. it might overflow secInt. + currTime.SecondsFrom( entry->LastAccessed(), secInt ); + + TInt val( secInt.Int() * entry->Size() / entry->Ref() ); + // get the object with largest ( DeltaT * Size / Ref ) + if( val > maxVal ) + { + maxVal = val; + bucketInd = i; + candidate = entry; + } + } + } + // remove from the bucket + // add it to the evicted list + // reduce space needed size + if( candidate ) + { +#ifdef __CACHELOG__ + // no protected entries should be evacuated + if( candidate->Protected() ) + { + HttpCacheUtil::WriteUrlToLog( 0, _L( "PROTECTED entry is about to be removed" ), candidate->Url() ); + } + // + HttpCacheUtil::WriteUrlToLog( 0, _L( "entry to remove:" ), candidate->Url() ); +#endif //__CACHELOG__ + // + iBuckets->At( bucketInd )->Remove( *candidate ); + // reduce size + aSpaceNeeded-= candidate->Size(); + aSpaceNeeded-= candidate->HeaderSize(); + // + evictedEntries->AppendL( candidate ); + // + HttpCacheUtil::WriteLog( 0, _L( "more space needed" ), aSpaceNeeded ); + } + else + { + // no candidate no free + break; + } + } + CleanupStack::Pop(); // evictedEntries + return evictedEntries; + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::RemoveAll +// +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::RemoveAll() + { + HttpCacheUtil::WriteLog( 0, _L( "Eviction table: remove all item:" ) ); + // + for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) + { + iBuckets->At( i )->Reset(); + // + } + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::Bucket +// +// ----------------------------------------------------------------------------- +// +TBucket* CHttpCacheEvictionHandler::Bucket( + TInt aIndex ) + { + return iBuckets->At( aIndex ); + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::BucketIndex +// +// ----------------------------------------------------------------------------- +// +TInt CHttpCacheEvictionHandler::BucketIndex( + TInt aSizeFrequencyValue ) + { + // last bucket by default + TInt index( 4 ); + // supports only 5 buckets at the moment + if( aSizeFrequencyValue == 1 ) + { + index = 0; + } + else if( aSizeFrequencyValue < 4 ) + { + index = 1; + } + else if( aSizeFrequencyValue < 8 ) + { + index = 2; + } + else if( aSizeFrequencyValue < 16 ) + { + index = 3; + } + return index; + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::ItemIsInBucket +// +// ----------------------------------------------------------------------------- +// +TBool CHttpCacheEvictionHandler::ItemIsInBucket( + TInt aBucketIndex, + const CHttpCacheEntry& aCacheEntry ) + { + TBool found( EFalse ); + CHttpCacheEntry* entry; + + TBucketIter bucketIter( *(iBuckets->At( aBucketIndex )) ); + // + bucketIter.SetToFirst(); + while( ( entry = bucketIter++ ) != NULL ) + { + if( entry == &aCacheEntry ) + { + found = ETrue; + break; + } + } +#ifdef __CACHELOG__ + if( !found ) + { + HttpCacheUtil::WriteLog( 0, _L( "Eviction table: item NOT FOUND" ) ); + } +#endif // __CACHELOG__ + return found; + } + +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::FastLog2 +// +// ----------------------------------------------------------------------------- +// +TInt CHttpCacheEvictionHandler::FastLog2( + TUint aNum ) + { + TInt log2; + FAST_LOG2( log2, aNum ); + return log2; + } + +#ifdef __CACHELOG__ +// ----------------------------------------------------------------------------- +// CHttpCacheEvictionHandler::LogBuckets +// +// ----------------------------------------------------------------------------- +// +void CHttpCacheEvictionHandler::LogBuckets() + { + CHttpCacheEntry* entry; + for( TInt i = 0; i < KHttpCacheBucketNum; i++ ) + { + HttpCacheUtil::WriteLog( 0, _L( "------------------------------" ), i ); + + TBucketIter bucketIter( *(iBuckets->At( i )) ); + // + bucketIter.SetToFirst(); + while( ( entry = bucketIter++ ) != NULL ) + { + _LIT( KDateString,"%D%M%Y%/0%1%/1%2%/2%3%/3 %-B%:0%J%:1%T%:2%S%.%*C4%:3%+B"); + _LIT( KRefSizeString,"size: %d refcount:%d"); + + TBuf<50> refStr; + TBuf<50> lastAccessedStr; + + TTime lastAccessed( entry->LastAccessed() ); + lastAccessed.FormatL( lastAccessedStr, KDateString ); + // add size/refcount + refStr.Format( KRefSizeString, entry->Size(), entry->Ref() ); + // copy to 8bit string + HttpCacheUtil::WriteUrlToLog( 0, refStr, entry->Url() ); + HttpCacheUtil::WriteLog( 0, lastAccessedStr ); + } + } + } +#endif // __CACHELOG__ + +// End of File