--- /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<TBucket>( 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; i<iBuckets->Count(); ++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<CHttpCacheEntry>* CHttpCacheEvictionHandler::EvictL(
+ TInt aSpaceNeeded )
+ {
+ HttpCacheUtil::WriteLog( 0, _L( "need space:" ), aSpaceNeeded );
+#ifdef __CACHELOG__
+ LogBuckets();
+#endif // __CACHELOG__
+ //
+ CArrayPtrFlat<CHttpCacheEntry>* evictedEntries = new(ELeave)CArrayPtrFlat<CHttpCacheEntry>( 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