1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/store/USTOR/UT_COLL.CPP Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,1155 @@
1.4 +// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +//
1.18 +
1.19 +#include "UT_STD.H"
1.20 +
1.21 +// PFS frame-related utilities
1.22 +
1.23 +TInt SkipLink(TInt anExtent)
1.24 +//
1.25 +// anExtent is the end-of-stream, where is the next link pos?
1.26 +// : add the size of the next frame link, or skip past anchor link
1.27 +//
1.28 + {return anExtent+Min(KSizeFrameDes16,(-anExtent)&KMaskFrameLength16);}
1.29 +
1.30 +inline TBool SpaceFor(TInt aSpace,TInt anEnd,TInt aLength)
1.31 +// Check if there is space for at least aLength between links at aSpace and anEnd
1.32 + {return SkipLink(aSpace+aLength)<=anEnd;}
1.33 +
1.34 +TBool Fits(TInt aSpace,TInt anEnd,TInt aLength)
1.35 +//
1.36 +// Check that aLength can be relocated into the space
1.37 +// either an exact fit, or leaves space for a free frame of at least one byte
1.38 +//
1.39 + {
1.40 + TInt end=SkipLink(aSpace+aLength);
1.41 + return end==anEnd ? ETrue : SpaceFor(end,anEnd,1);
1.42 + }
1.43 +
1.44 +TInt ExtentL(TStreamExchange& aHost,TStreamMark& aMark,TStreamPos aBase,TInt aStream)
1.45 +//
1.46 +// scan a stream to discover it's extent
1.47 +//
1.48 + {
1.49 + __ASSERT_DEBUG(aMark.RelatesTo(aHost),User::Invariant());
1.50 + __ASSERT_DEBUG(aBase>=KStreamBeginning,User::Invariant());
1.51 + __ASSERT_DEBUG(aStream>=0,User::Invariant());
1.52 +//
1.53 + aMark.SeekL(aHost,RFrame16Buf::Position(aBase,aStream)-KSizeFrameDes16);
1.54 + TFrameDes16 des;
1.55 + aMark.ReadL(aHost,&des,KSizeFrameDes16);
1.56 + TInt frame=des;
1.57 + if ((frame&KMaskFrameType16)!=EFrameData16)
1.58 + if ((frame&KMaskFrameType16)!=EFrameDescriptive16)
1.59 + {
1.60 + aMark.Withdraw(aHost);
1.61 + __LEAVE(KErrCorrupt);
1.62 + }
1.63 +//
1.64 + TInt anchor=((aStream>>KShiftFrameLength16)+1)<<KShiftFrameLength16;
1.65 + do
1.66 + {
1.67 + frame&=KMaskFrameLength16;
1.68 + TInt lim=anchor-aStream;
1.69 + if (frame!=KFrameOpen16)
1.70 + {
1.71 + if (frame>=lim)
1.72 + {
1.73 + aMark.Withdraw(aHost);
1.74 + __LEAVE(KErrCorrupt);
1.75 + }
1.76 + return aStream+frame;
1.77 + }
1.78 + aMark.SeekL(aHost,EStreamMark,lim);
1.79 + aStream=anchor;
1.80 + anchor+=KFrameFullLength16;
1.81 + aMark.ReadL(aHost,&des,KSizeFrameDes16);
1.82 + frame=des;
1.83 + } while ((frame&KMaskFrameType16)==EFrameContinuation16);
1.84 + return aStream;
1.85 + }
1.86 +
1.87 +
1.88 +
1.89 +// Class TRelocatorInput
1.90 +// Used to transfer a frame-set within the file
1.91 +
1.92 +const TInt KRelocatorBufferSize=0xc00;
1.93 +
1.94 +NONSHARABLE_CLASS(TRelocatorInput) : public MStreamInput
1.95 + {
1.96 +public:
1.97 + inline TRelocatorInput(TStreamExchange& aHost,TStreamMark& aMark);
1.98 + void OpenL(TFrameType16 aType,TStreamPos aBase,TInt aPos,TInt aLength,TInt aTerminator);
1.99 + void CommitL();
1.100 +private:
1.101 + TInt PushL(const TAny* aPtr,TInt aMaxLength);
1.102 + TStreamTransfer ReadFromL(MStreamBuf& aSource,TStreamTransfer aTransfer);
1.103 + void DesL(TFrameType16 aType);
1.104 +//
1.105 + inline TStreamExchange& Host() const;
1.106 + inline TStreamMark& Mark();
1.107 +private:
1.108 + TStreamExchange* iHost;
1.109 + TStreamMark* iMark;
1.110 + TFrameType16 iType;
1.111 + TInt iRemain;
1.112 + TInt iAnchor;
1.113 + TInt iTerminator;
1.114 + };
1.115 +
1.116 +inline TRelocatorInput::TRelocatorInput(TStreamExchange& aHost,TStreamMark& aMark)
1.117 + : iHost(&aHost),iMark(&aMark)
1.118 + {}
1.119 +inline TStreamExchange& TRelocatorInput::Host() const
1.120 + {
1.121 + __ASSERT_DEBUG(iHost!=NULL,User::Invariant());
1.122 + return *iHost;
1.123 + }
1.124 +inline TStreamMark& TRelocatorInput::Mark()
1.125 + {
1.126 + __ASSERT_DEBUG(iMark!=NULL,User::Invariant());
1.127 + return *iMark;
1.128 + }
1.129 +
1.130 +void TRelocatorInput::OpenL(TFrameType16 aType,TStreamPos aBase,TInt aPos,TInt aLength,TInt aTerminator)
1.131 +//
1.132 +// initiate the relocated stream
1.133 +//
1.134 + {
1.135 + __ASSERT_DEBUG(aType!=EFrameFree16,User::Invariant());
1.136 + __ASSERT_DEBUG(aBase>=KStreamBeginning,User::Invariant());
1.137 + __ASSERT_DEBUG(aPos>=0,User::Invariant());
1.138 + __ASSERT_DEBUG(aLength>0,User::Invariant());
1.139 +//
1.140 + iType=aType;
1.141 + iRemain=aLength;
1.142 + iTerminator=aTerminator;
1.143 + iAnchor=KFrameFullLength16-(aPos&KMaskFrameLength16);
1.144 + Mark().SeekL(Host(),RFrame16Buf::Position(aBase,aPos)-KSizeFrameDes16);
1.145 + }
1.146 +
1.147 +
1.148 +void TRelocatorInput::CommitL()
1.149 +//
1.150 +// complete the relocated stream
1.151 +//
1.152 + {
1.153 + __ASSERT_DEBUG(iRemain==0,User::Invariant());
1.154 + __ASSERT_DEBUG(iAnchor>=0,User::Invariant());
1.155 +//
1.156 + if (iTerminator<0)
1.157 + return;
1.158 +//
1.159 + TFrameDes16 des[2];
1.160 + des[1]=TFrameDes16(iTerminator);
1.161 + TInt l=KSizeFrameDes16;
1.162 + if (iAnchor<=KSizeFrameDes16)
1.163 + l+=iAnchor;
1.164 + Mark().WriteL(Host(),(const TUint8*)&des[2]-l,l);
1.165 + }
1.166 +
1.167 +TInt TRelocatorInput::PushL(const TAny*,TInt)
1.168 +//
1.169 +// use a passive write through to the host
1.170 +//
1.171 + {
1.172 + return 0;
1.173 + }
1.174 +
1.175 +void TRelocatorInput::DesL(TFrameType16 aType)
1.176 +//
1.177 +// Write the next frame descriptor
1.178 +//
1.179 + {
1.180 + __ASSERT_DEBUG(aType!=EFrameFree16,User::Invariant());
1.181 + TFrameDes16 des=TFrameDes16(iRemain<iAnchor ? aType+iRemain : aType+KFrameOpen16);
1.182 + Mark().WriteL(Host(),&des,KSizeFrameDes16);
1.183 + }
1.184 +
1.185 +TStreamTransfer TRelocatorInput::ReadFromL(MStreamBuf& aSource,TStreamTransfer aTransfer)
1.186 +//
1.187 +// bulk of the transfer happens here
1.188 +//
1.189 + {
1.190 + __ASSERT_DEBUG(!(aTransfer>iRemain),User::Invariant());
1.191 + do
1.192 + {
1.193 + TUint8 buf[KRelocatorBufferSize];
1.194 + TInt len=aSource.ReadL(buf,aTransfer[sizeof(buf)]);
1.195 + if (len==0)
1.196 + break;
1.197 + aTransfer-=len;
1.198 + const TUint8* p=buf;
1.199 + if (iType!=EFrameFree16)
1.200 + {
1.201 + DesL(iType);
1.202 + iType=EFrameFree16;
1.203 + }
1.204 + for (;;)
1.205 + {
1.206 + if (iAnchor==0)
1.207 + { // write next anchor
1.208 + iAnchor=KFrameFullLength16;
1.209 + DesL(EFrameContinuation16);
1.210 + }
1.211 + TInt frame=Min(len,iAnchor);
1.212 + Mark().WriteL(Host(),p,frame);
1.213 + iAnchor-=frame;
1.214 + iRemain-=frame;
1.215 + len-=frame;
1.216 + if (len==0)
1.217 + break;
1.218 + p+=frame;
1.219 + }
1.220 + } while (aTransfer>0);
1.221 + return aTransfer;
1.222 + }
1.223 +
1.224 +
1.225 +
1.226 +// Class TPermanentStoreRelocator
1.227 +// used to locate streams for relocation in limited memory
1.228 +
1.229 +class TPermanentStoreRelocator
1.230 + {
1.231 +#if defined(__SMALL_BUNDLE)
1.232 + enum {EBundleSize=8-1};
1.233 +#else
1.234 + enum {EBundleSize=64-1};
1.235 +#endif
1.236 +public:
1.237 + typedef CPermanentStoreCollector::TEntry TEntry;
1.238 +public:
1.239 + void Reset();
1.240 + TBool Reset(TInt aPos);
1.241 + TInt FillL(CPermanentStoreToc& aToc);
1.242 + void EvaluateLengthsL(TStreamExchange& aHost,TStreamMark& aMark,TStreamPos aBase);
1.243 +//
1.244 + TBool FindFit(TInt aSpace,TInt anEnd);
1.245 + inline const TEntry* Current() const;
1.246 + void Relocated(const TEntry* anEntry);
1.247 +//
1.248 + TInt Extent(TInt aStream) const;
1.249 + inline TInt MinLength() const;
1.250 +private:
1.251 + static void Push(TEntry* aHeap,TEntry* aHole,const TEntry& aValue);
1.252 + static TEntry PopPush(TEntry* aHeap,TEntry* anEnd,const TEntry& aValue);
1.253 +private:
1.254 + TEntry* iNext;
1.255 + const TEntry* iFinish;
1.256 + TInt iMore;
1.257 + TInt iPos;
1.258 + TInt iCurrentMin,iMinLength;
1.259 + TEntry iTable[EBundleSize];
1.260 + };
1.261 +
1.262 +inline const TPermanentStoreRelocator::TEntry* TPermanentStoreRelocator::Current() const
1.263 + {__ASSERT_DEBUG(iNext>=iTable&&iNext<iFinish,User::Invariant());return iNext;}
1.264 +inline TInt TPermanentStoreRelocator::MinLength() const
1.265 + {return iMinLength;}
1.266 +
1.267 +void TPermanentStoreRelocator::Reset()
1.268 +//
1.269 +// reset the cached length values
1.270 +//
1.271 + {
1.272 + iPos=0;
1.273 + iMinLength=1;
1.274 + }
1.275 +
1.276 +TBool TPermanentStoreRelocator::Reset(TInt aPos)
1.277 +//
1.278 +// reset the iterator for a new scan from aPos
1.279 +//
1.280 + {
1.281 + __ASSERT_DEBUG(aPos>=0,User::Invariant());
1.282 +//
1.283 + iCurrentMin=KMaxTInt;
1.284 + TEntry* e=iTable;
1.285 + if (aPos>=iPos || e==iFinish || aPos<e->entry.ref)
1.286 + { // rescan required
1.287 + iFinish=iNext=NULL;
1.288 + iMore=-1;
1.289 + iPos=aPos;
1.290 + return EFalse;
1.291 + }
1.292 +
1.293 +// can use current data
1.294 + for (;e->entry.ref!=aPos;++e)
1.295 + {
1.296 + __ASSERT_DEBUG(e->entry.ref<aPos,User::Invariant());
1.297 + __ASSERT_DEBUG(e<iFinish,User::Invariant());
1.298 + }
1.299 + __ASSERT_DEBUG(e->entry.handle>=0,User::Invariant());
1.300 + iNext=e;
1.301 + return ETrue;
1.302 + }
1.303 +
1.304 +TBool TPermanentStoreRelocator::FillL(CPermanentStoreToc& aToc)
1.305 +//
1.306 +// Fill the table with the next bundle of stream offsets
1.307 +// return if there are more available
1.308 +//
1.309 + {
1.310 + __ASSERT_DEBUG(iNext==iFinish,User::Invariant());
1.311 + if (!iMore)
1.312 + return EFalse;
1.313 +//
1.314 + __ASSERT_DEBUG(iPos>=0,User::Invariant());
1.315 +//
1.316 + RPermanentStoreTocIter iter(aToc);
1.317 + CleanupReleasePushL(iter);
1.318 +
1.319 + TInt streams=0;
1.320 + TInt from=iPos;
1.321 + TEntry* table=iTable;
1.322 + TEntry* last=table;
1.323 + TEntry* end=table+EBundleSize;
1.324 + TEntry entry;
1.325 + __DEBUG(entry.len=-1);
1.326 + for (iter.ResetL();iter.NextL(entry.entry);)
1.327 + {
1.328 + if (entry.entry.handle<0)
1.329 + continue;
1.330 + TInt off=entry.entry.ref;
1.331 + if (off<from)
1.332 + continue;
1.333 + ++streams;
1.334 + if (last<end)
1.335 + Push(table,last++,entry); // push onto the bottom
1.336 + else if (off<table->entry.ref)
1.337 + PopPush(table,last,entry); // replace item in heap
1.338 + }
1.339 + CleanupStack::PopAndDestroy();
1.340 +
1.341 + iMore=streams+table-last;
1.342 + if (streams)
1.343 + iPos=table->entry.ref+1; // largest offset in table
1.344 + iNext=table;
1.345 + iFinish=last;
1.346 + while (--last>table)
1.347 + *last=PopPush(table,last,*last);
1.348 + return streams>0;
1.349 + }
1.350 +
1.351 +void TPermanentStoreRelocator::Push(TEntry* aHeap,TEntry* aHole,const TEntry& aValue)
1.352 +//
1.353 +// push aValue onto the heap (which will grow)
1.354 +//
1.355 + {
1.356 + TInt ix=aHole+1-aHeap;
1.357 + while (aHole>aHeap)
1.358 + {
1.359 + TInt link=ix-(ix>>1);
1.360 + ix-=link;
1.361 + TEntry* parent=aHole-link;
1.362 + if (parent->entry.ref>=aValue.entry.ref)
1.363 + break;
1.364 + *aHole=*parent;
1.365 + aHole=parent;
1.366 + }
1.367 + *aHole=aValue;
1.368 + }
1.369 +
1.370 +TPermanentStoreRelocator::TEntry TPermanentStoreRelocator::PopPush(TEntry* aHeap,TEntry* anEnd,const TEntry& aValue)
1.371 +//
1.372 +// pop the top and push aValue
1.373 +//
1.374 + {
1.375 + TEntry top=*aHeap;
1.376 + TEntry* hole=aHeap;
1.377 + --anEnd;
1.378 + TInt ix=1;
1.379 + for (;;)
1.380 + {
1.381 + TEntry* child=hole+ix;
1.382 + ix<<=1;
1.383 + if (child>anEnd)
1.384 + break;
1.385 + if (child<anEnd && (child+1)->entry.ref>child->entry.ref)
1.386 + {
1.387 + ++ix;
1.388 + ++child;
1.389 + }
1.390 + if (child->entry.ref<=aValue.entry.ref)
1.391 + break;
1.392 + *hole=*child;
1.393 + hole=child;
1.394 + }
1.395 + *hole=aValue;
1.396 + return top;
1.397 + }
1.398 +
1.399 +void TPermanentStoreRelocator::EvaluateLengthsL(TStreamExchange& aHost,TStreamMark& aMark,TStreamPos aBase)
1.400 +//
1.401 +// Evaluate the lengths for all the entries in the table
1.402 +//
1.403 + {
1.404 + const TEntry* end=iFinish;
1.405 + for (TEntry* e=iTable;e<end;++e)
1.406 + {
1.407 + __ASSERT_DEBUG(e->entry.handle>=0,User::Invariant());
1.408 + __ASSERT_DEBUG(e->entry.ref>=0,User::Invariant());
1.409 + __ASSERT_DEBUG(e->len==-1,User::Invariant());
1.410 + TInt pos=e->entry.ref;
1.411 + e->len=ExtentL(aHost,aMark,aBase,pos)-pos;
1.412 + }
1.413 + }
1.414 +
1.415 +TBool TPermanentStoreRelocator::FindFit(TInt aSpace,TInt anEnd)
1.416 +//
1.417 +// Find a stream which will fit into the space
1.418 +//
1.419 + {
1.420 + const TEntry* end=iFinish;
1.421 + TEntry* e;
1.422 + for (e=iNext;e<end;++e)
1.423 + {
1.424 + if (e->entry.handle<0)
1.425 + continue;
1.426 + TInt len=e->len;
1.427 + __ASSERT_DEBUG(len>0,User::Invariant());
1.428 + if (Fits(aSpace,anEnd,len))
1.429 + {
1.430 + iNext=e;
1.431 + return ETrue;
1.432 + }
1.433 + // len has been left behind, check for minimum
1.434 + if (len<iCurrentMin)
1.435 + iCurrentMin=len;
1.436 + }
1.437 +// if no more data, use current min as cached value
1.438 + if (iMore==0)
1.439 + iMinLength=iCurrentMin;
1.440 + iNext=e;
1.441 + return EFalse;
1.442 + }
1.443 +
1.444 +void TPermanentStoreRelocator::Relocated(const TEntry* anEntry)
1.445 +//
1.446 +// Relocation has been successful
1.447 +//
1.448 + {
1.449 + __ASSERT_DEBUG(anEntry==iNext,User::Invariant());
1.450 + TEntry* e=CONST_CAST(TEntry*,anEntry);
1.451 + e->entry.handle=-1;
1.452 + iNext=e+1;
1.453 + }
1.454 +
1.455 +TInt TPermanentStoreRelocator::Extent(TInt aStream) const
1.456 +//
1.457 +// Return this stream extent if we know it
1.458 +//
1.459 + {
1.460 + const TEntry* e=iTable;
1.461 + if (aStream>=iPos || e==iFinish || aStream<e->entry.ref)
1.462 + return -1; // we don't know it
1.463 + for (;e->entry.ref!=aStream;++e)
1.464 + {
1.465 + __ASSERT_DEBUG(e->entry.ref<aStream,User::Invariant());
1.466 + __ASSERT_DEBUG(e<iFinish,User::Invariant());
1.467 + }
1.468 + __ASSERT_DEBUG(e->entry.handle>=0,User::Invariant());
1.469 + __ASSERT_DEBUG(e->len>=0,User::Invariant());
1.470 + return aStream+e->len;
1.471 + }
1.472 +
1.473 +
1.474 +
1.475 +// class TPermanentStoreStreamIter
1.476 +
1.477 +void TPermanentStoreStreamIter::Reset()
1.478 +//
1.479 +// reset the iterator for a new scan
1.480 +//
1.481 + {
1.482 + iNext=NULL;
1.483 + iFinish=NULL;
1.484 + iMore=-1;
1.485 + iPos=0;
1.486 + }
1.487 +
1.488 +TInt TPermanentStoreStreamIter::FillL(CPermanentStoreToc& aToc)
1.489 +//
1.490 +// Fill the table with the next bundle of stream offsets
1.491 +// return the total streams left to iterate
1.492 +//
1.493 + {
1.494 + __ASSERT_DEBUG(iNext==iFinish,User::Invariant());
1.495 + if (!iMore)
1.496 + return 0;
1.497 +//
1.498 + __ASSERT_DEBUG(iPos>=0,User::Invariant());
1.499 +//
1.500 + RPermanentStoreTocIter iter(aToc);
1.501 + CleanupReleasePushL(iter);
1.502 +
1.503 + TInt streams=0;
1.504 + TInt from=iPos;
1.505 + TInt* heap=iTable;
1.506 + TInt* last=heap;
1.507 + TInt* end=heap+EBundleSize;
1.508 + RPermanentStoreTocIter::TEntry entry;
1.509 + for (iter.ResetL();iter.NextL(entry);)
1.510 + {
1.511 + if (entry.handle<0)
1.512 + continue;
1.513 + TInt off=entry.ref;
1.514 + if (off<from)
1.515 + continue;
1.516 + ++streams;
1.517 + if (last<end)
1.518 + Push(heap,last++,off); // push onto the bottom
1.519 + else if (off<*heap)
1.520 + PopPush(heap,last,off); // replace item in heap
1.521 + }
1.522 + CleanupStack::PopAndDestroy();
1.523 +
1.524 + iMore=streams+(heap-last);
1.525 + iPos=*heap+1; // largest offset in table
1.526 + iNext=heap;
1.527 + iFinish=last;
1.528 + while (--last>heap)
1.529 + *last=PopPush(heap,last,*last);
1.530 + return streams;
1.531 + }
1.532 +
1.533 +TInt TPermanentStoreStreamIter::Next()
1.534 +//
1.535 +// return the next offset, or <0 if the table is empty
1.536 +//
1.537 + {
1.538 + __ASSERT_DEBUG(iMore>=0,User::Invariant());
1.539 +//
1.540 + while (iNext<iFinish)
1.541 + {
1.542 + TInt off=*iNext++;
1.543 + if (off>=0)
1.544 + return off;
1.545 + }
1.546 + return -1;
1.547 + }
1.548 +
1.549 +void TPermanentStoreStreamIter::Relocated(TInt aStream)
1.550 +//
1.551 +// aStream has been relocated, mark the table
1.552 +//
1.553 + {
1.554 + __ASSERT_DEBUG(iMore>=0,User::Invariant());
1.555 +//
1.556 + if (aStream>=iPos)
1.557 + return;
1.558 + TInt* p=iNext;
1.559 + for (;;)
1.560 + {
1.561 + if (p==iFinish)
1.562 + return;
1.563 + if (*p>=0)
1.564 + break;
1.565 + ++p;
1.566 + }
1.567 + if (aStream<*p)
1.568 + return;
1.569 +//
1.570 + for (;*p!=aStream;++p)
1.571 + {
1.572 + __ASSERT_DEBUG(p<iFinish,User::Invariant());
1.573 + __ASSERT_DEBUG(*p<aStream,User::Invariant());
1.574 + }
1.575 + if (p==iNext)
1.576 + iNext=p+1;
1.577 + else
1.578 + *p=-1;
1.579 + }
1.580 +
1.581 +void TPermanentStoreStreamIter::Push(TInt* aHeap,TInt* aHole,TInt aValue)
1.582 +//
1.583 +// push aValue onto the heap (which will grow)
1.584 +//
1.585 + {
1.586 + TInt ix=aHole+1-aHeap;
1.587 + while (aHole>aHeap)
1.588 + {
1.589 + TInt link=ix-(ix>>1);
1.590 + ix-=link;
1.591 + TInt* parent=aHole-link;
1.592 + if (*parent>=aValue)
1.593 + break;
1.594 + *aHole=*parent;
1.595 + aHole=parent;
1.596 + }
1.597 + *aHole=aValue;
1.598 + }
1.599 +
1.600 +TInt TPermanentStoreStreamIter::PopPush(TInt* aHeap,TInt* anEnd,TInt aValue)
1.601 +//
1.602 +// pop the top and push aValue
1.603 +//
1.604 + {
1.605 + TInt top=*aHeap;
1.606 + TInt* hole=aHeap;
1.607 + --anEnd;
1.608 + TInt ix=1;
1.609 + for (;;)
1.610 + {
1.611 + TInt* child=hole+ix;
1.612 + ix<<=1;
1.613 + if (child>anEnd)
1.614 + break;
1.615 + if (child<anEnd && *(child+1)>*child)
1.616 + {
1.617 + ++ix;
1.618 + ++child;
1.619 + }
1.620 + if (*child<=aValue)
1.621 + break;
1.622 + *hole=*child;
1.623 + hole=child;
1.624 + }
1.625 + *hole=aValue;
1.626 + return top;
1.627 + }
1.628 +
1.629 +
1.630 +
1.631 +// Class CPermanentStoreCollector
1.632 +
1.633 +CPermanentStoreCollector* CPermanentStoreCollector::CompactorL(CPermanentStoreCoord& aCoord)
1.634 + {
1.635 + CPermanentStoreCollector* self=ReclaimerL(aCoord);
1.636 + CleanupStack::PushL(self);
1.637 + self->iReloc=new(ELeave) TPermanentStoreRelocator;
1.638 + CleanupStack::Pop();
1.639 + return self;
1.640 + }
1.641 +
1.642 +CPermanentStoreCollector* CPermanentStoreCollector::ReclaimerL(CPermanentStoreCoord& aCoord)
1.643 + {
1.644 + return new(ELeave) CPermanentStoreCollector(aCoord);
1.645 + }
1.646 +
1.647 +CPermanentStoreCollector::CPermanentStoreCollector(CPermanentStoreCoord& aCoord)
1.648 + : iCoord(&aCoord),iHost(&aCoord.Host()),iStreams(EGranularity,_FOFF(TEntry,entry.ref))
1.649 + {
1.650 + Coord().Inc();
1.651 + }
1.652 +
1.653 +CPermanentStoreCollector::~CPermanentStoreCollector()
1.654 + {
1.655 + delete iReloc;
1.656 + iStreams.Close();
1.657 + iMark.Withdraw(Host());
1.658 + Coord().Dec();
1.659 + }
1.660 +
1.661 +void CPermanentStoreCollector::DoRelease()
1.662 + {
1.663 + delete this;
1.664 + }
1.665 +
1.666 +void CPermanentStoreCollector::DoResetL(TInt& aCount)
1.667 + {
1.668 + iMark.Withdraw(Host());
1.669 + iMark=KStreamBeginning;
1.670 + iCoordGen=Coord().Generation();
1.671 + iFree=0;
1.672 + TRAPD(r, aCount = FastResetL());
1.673 + if (r == KErrNone)
1.674 + return;
1.675 + if (r != KErrNoMemory)
1.676 + User::Leave(r);
1.677 +// fall back to fixed memory solution
1.678 + iState=EGetFree;
1.679 + if (Compacting())
1.680 + iReloc->Reset();
1.681 + iIter.Reset();
1.682 + TInt streams=iIter.FillL(Coord().ConsolidateL());
1.683 + aCount=streams+1;
1.684 + }
1.685 +
1.686 +const TInt KMaxStepEffort=9;
1.687 +
1.688 +void CPermanentStoreCollector::DoNextL(TInt& aStep,TInt& aTotal)
1.689 +//
1.690 +// Dispatch the next set of operations
1.691 +//
1.692 + {
1.693 + if (aStep<=0)
1.694 + {
1.695 + __DEBUG(Panic(TStorePanic()));
1.696 + return;
1.697 + }
1.698 +//
1.699 + if (iCoordGen!=Coord().Generation() || Coord().TableL().IsVirtual())
1.700 + __LEAVE(KErrNotReady);
1.701 +//
1.702 + TInt effort=0;
1.703 + do
1.704 + {
1.705 + switch (iState)
1.706 + {
1.707 + default:
1.708 + __DEBUG(User::Invariant());
1.709 + case EGetFree:
1.710 + effort+=GetFreeL();
1.711 + break;
1.712 + case ESkip:
1.713 + effort+=SkipL(aTotal);
1.714 + --aStep;
1.715 + break;
1.716 + case EInitRelocator:
1.717 + effort+=InitRelocator();
1.718 + break;
1.719 + case EFillRelocator:
1.720 + effort+=FillRelocatorL();
1.721 + break;
1.722 + case EEvalRelocator:
1.723 + effort+=EvalRelocatorL();
1.724 + break;
1.725 + case EScanRelocator:
1.726 + effort+=ScanRelocator();
1.727 + break;
1.728 + case ERelocateStream:
1.729 + effort+=RelocateStreamL();
1.730 + --aStep;
1.731 + break;
1.732 + case ERelocateToc:
1.733 + RelocateTocL(aTotal);
1.734 + iStreams.Close();
1.735 + __ASSERT_DEBUG(aStep==1,User::Invariant());
1.736 + aStep=0;
1.737 + return;
1.738 + case EFastSort:
1.739 + FastSort();
1.740 + --aStep;
1.741 + return;
1.742 + case EFastExtent:
1.743 + FastExtentL(aTotal);
1.744 + --aStep;
1.745 + return;
1.746 + case EFastRelocate:
1.747 + FastRelocateL(aTotal);
1.748 + --aStep;
1.749 + return;
1.750 + }
1.751 + } while(effort<KMaxStepEffort);
1.752 + __ASSERT_DEBUG(aStep>=1,User::Invariant());
1.753 + }
1.754 +
1.755 +TInt CPermanentStoreCollector::GetFreeL()
1.756 +//
1.757 +// find the end of the free space
1.758 +//
1.759 + {
1.760 + __ASSERT_DEBUG(iState==EGetFree,User::Invariant());
1.761 + __ASSERT_DEBUG(iFree>=0,User::Invariant());
1.762 +//
1.763 + TInt effort=0;
1.764 + iEnd=iIter.Next();
1.765 + if (iEnd<0)
1.766 + {
1.767 + if (iIter.FillL(Coord().ConsolidateL())==0)
1.768 + {
1.769 + iState=ERelocateToc; // no more streams
1.770 + return effort;
1.771 + }
1.772 + effort=KMaxStepEffort;
1.773 + iEnd=iIter.Next();
1.774 + __ASSERT_DEBUG(iEnd>=0,User::Invariant());
1.775 + }
1.776 + iState=Compacting() && HaveEnoughSpace() ? EInitRelocator : ESkip;
1.777 + return effort;
1.778 + }
1.779 +
1.780 +TInt CPermanentStoreCollector::SkipL(TInt& aTotal)
1.781 +//
1.782 +// Find some free space, iEnd was the last stream extracted from concat
1.783 +//
1.784 + {
1.785 + __ASSERT_DEBUG(iState==ESkip,User::Invariant());
1.786 + __ASSERT_DEBUG(iFree>=0&&iFree<=iEnd,User::Invariant());
1.787 +//
1.788 + aTotal+=iEnd-iFree;
1.789 + iFree=SkipLink(ExtentL(iEnd));
1.790 + iState=EGetFree;
1.791 + return 1; // effort
1.792 + }
1.793 +
1.794 +TInt CPermanentStoreCollector::InitRelocator()
1.795 +//
1.796 +// initialise the relocator for the free space
1.797 +//
1.798 + {
1.799 + __ASSERT_DEBUG(iState==EInitRelocator,User::Invariant());
1.800 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.801 +//
1.802 + iState=iReloc->Reset(iEnd) ? EScanRelocator : EFillRelocator;
1.803 + return 0; // no real work at all
1.804 + }
1.805 +
1.806 +TInt CPermanentStoreCollector::FillRelocatorL()
1.807 +//
1.808 +// Fill the relocator table
1.809 +//
1.810 + {
1.811 + __ASSERT_DEBUG(iState==EFillRelocator,User::Invariant());
1.812 + __ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());
1.813 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.814 +//
1.815 + TBool more=iReloc->FillL(Coord().ConsolidateL());
1.816 + iState=more ? EEvalRelocator : ESkip;
1.817 + return more ? KMaxStepEffort : 0;
1.818 + }
1.819 +
1.820 +TInt CPermanentStoreCollector::EvalRelocatorL()
1.821 +//
1.822 +// evaluate the extents for the relocator
1.823 +//
1.824 + {
1.825 + __ASSERT_DEBUG(iState==EEvalRelocator,User::Invariant());
1.826 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.827 +//
1.828 + iReloc->EvaluateLengthsL(Host(),iMark,Coord().Base());
1.829 + iState=EScanRelocator;
1.830 + return KMaxStepEffort;
1.831 + }
1.832 +
1.833 +TInt CPermanentStoreCollector::ScanRelocator()
1.834 +//
1.835 +// find a stream that will fit
1.836 +//
1.837 + {
1.838 + __ASSERT_DEBUG(iState==EScanRelocator,User::Invariant());
1.839 + __ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());
1.840 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.841 +//
1.842 + iState=iReloc->FindFit(iFree,iEnd) ? ERelocateStream : EFillRelocator;
1.843 + return 0;
1.844 + }
1.845 +
1.846 +TInt CPermanentStoreCollector::RelocateStreamL()
1.847 +//
1.848 +// find and relocate a stream
1.849 +//
1.850 + {
1.851 + __ASSERT_DEBUG(iState==ERelocateStream,User::Invariant());
1.852 + __ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());
1.853 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.854 +//
1.855 + const TEntry& e = *iReloc->Current();
1.856 + RelocateStreamL(e, iEnd);
1.857 + iState=e.entry.ref==iEnd ? EGetFree : HaveEnoughSpace() ? EScanRelocator : ESkip;
1.858 + iIter.Relocated(e.entry.ref);
1.859 + iReloc->Relocated(&e);
1.860 + return KMaxStepEffort;
1.861 + }
1.862 +
1.863 +void CPermanentStoreCollector::RelocateTocL(TInt& aTotal)
1.864 +//
1.865 +// relocate the toc - return any wasted bytes
1.866 +//
1.867 + {
1.868 + __ASSERT_DEBUG(iState==ERelocateToc,User::Invariant());
1.869 + __ASSERT_DEBUG(iFree>=0,User::Invariant());
1.870 +//
1.871 + TInt toc=Coord().iToc+KOffsetTocHeader;
1.872 + if (toc<0)
1.873 + return;
1.874 +//
1.875 + if (Compacting())
1.876 + {
1.877 + TInt len=Coord().TableL().Extent()-toc;
1.878 + if (Fits(iFree,toc,len))
1.879 + {
1.880 + RelocateL(toc, len, EFrameDescriptive16, toc);
1.881 + Coord().MoveL(iFree-KOffsetTocHeader,iFree + len);
1.882 + return;
1.883 + }
1.884 + }
1.885 + // don't move it
1.886 + aTotal += toc-iFree;
1.887 + }
1.888 +
1.889 +TBool CPermanentStoreCollector::HaveEnoughSpace() const
1.890 + {
1.891 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.892 +//
1.893 + return SpaceFor(iFree,iEnd,iReloc->MinLength());
1.894 + }
1.895 +
1.896 +TInt CPermanentStoreCollector::ExtentL(TInt aStream)
1.897 +//
1.898 +// Check if the relocator knows before scanning the file
1.899 +//
1.900 + {
1.901 + if (Compacting())
1.902 + {
1.903 + TInt ext=iReloc->Extent(aStream);
1.904 + if (ext>=0)
1.905 + return ext;
1.906 + }
1.907 + return ::ExtentL(Host(),iMark,Coord().Base(),aStream);
1.908 + }
1.909 +
1.910 +/* relocate a stream into [iFree, aExtent)
1.911 +
1.912 +During compaction, for each string which is to be moved from position A1 to B1, the sequence of operations is:
1.913 +
1.914 +1. Copy stream S1 content from position A1 to position B1 . The copy never overlaps so the old stream content is still good at this point.
1.915 +2. Optionally rewrite the file header to state that stream S1 is being relocated to B1 (more about the ‘optional below’)
1.916 +3. Overwrite the TOC entry for S1 to state that the content is now at B1
1.917 +
1.918 +This function completes 3 steps above and will be called again and again for every string to be moved.
1.919 +
1.920 +In terms of data consistency, first consider the impact of a mid-write failure in any of these steps (when write caching is disabled):
1.921 +1. If step #1 only partially completes the file is good as the original content is intact and the new content was being written to otherwise free space
1.922 +2. If step #2 only partially completes the header CRC fails and only the TOC reference is considered valid (so the corrupt stream relocation record is ignored).
1.923 + The TOC will be good because it is being overwritten with the same content.
1.924 +3. If step #3 only partially completes the entry for S1 in the TOC is corrupt, BUT the relocation record for S1 in the file header is good and will
1.925 + override the entry in the TOC.
1.926 +
1.927 +In all cases the file is never broken by a crash in mid-compaction.
1.928 +
1.929 +Step #2 is optional – there are many cases when step #3 cannot fail ‘halfway through’ because the underlying media makes atomic block/page based
1.930 +updates and the write does not cross any block boundaries. In STORE we assume that blocks cannot be smaller than 512 bytes and any flash based
1.931 +media provides the required behavior. Thus 99% of the step #2 writes are eliminated.
1.932 +
1.933 +Note that sequencing MATTERS even for just one stream. If the TOC update hits the disk before the content is moved, and then the device fails
1.934 +we will have a broken file: S1 points to B1 which contains garbage. Equally in the case where step #2 is required (i.e. when step #3 straddles
1.935 +a block boundary and could fail) step 2 has to go before the step 3. Otherwise write #3 could go to disk and fail part way through before write #2
1.936 +and leave the TOC corrupt with no recovery in the file header.
1.937 +
1.938 +Consider the case that step 2 was omitted, so the Store relies on step 3 being completed in order to know that S1 is in location B1;
1.939 +and that no flush is done after step 3. In step 4 the stream S2 is moved – at this point the old space for stream S1 at A1 is considered empty
1.940 +– and suppose it gets moved from A2 to B2 where B2 overlaps/overwrites A1. If the writes in step 3 and step 4 are re-ordered and the step 3
1.941 +write does not happen – then the TOC will claim that S1 is still at A1 but this location in the file has been overwritten with data from S2.
1.942 +A corrupted file.
1.943 +
1.944 +Based on the knowledge above, it is strongly recommended to set EFileWriteDirectIO bit when opening the file so that the order is maintained
1.945 +when writing to the file.
1.946 +*/
1.947 +void CPermanentStoreCollector::RelocateStreamL(const CPermanentStoreCollector::TEntry& aReloc, TInt aExtent)
1.948 + {
1.949 + if (Coord().Accessed()) // must have exclusive access to relocate the stream
1.950 + __LEAVE(KErrInUse);
1.951 +//
1.952 + TInt end=RelocateL(aReloc.entry.ref,aReloc.len,aReloc.entry.handle == KHandleTocBase ? EFrameDescriptive16 : EFrameData16, aExtent);
1.953 + //Step 1, 4,....
1.954 + Coord().RelocateL(aReloc.entry.handle, iFree);
1.955 + // Step 2 & 3, 5 & 6,...
1.956 + iCoordGen=Coord().Generation(); // changed by relocation
1.957 + iFree = end;
1.958 + }
1.959 +
1.960 +TInt CPermanentStoreCollector::RelocateL(TInt aStream, TInt aLength, TFrameType16 aType, TInt aExtent)
1.961 +//
1.962 +// Relocate a data stream into [iFree, aExtent)
1.963 +//
1.964 + {
1.965 + __ASSERT_DEBUG(Fits(iFree,aExtent,aLength),User::Invariant());
1.966 + __ASSERT_DEBUG(Compacting(),User::Invariant());
1.967 +//
1.968 + TInt end=SkipLink(iFree+aLength);
1.969 + TInt terminator;
1.970 + if (end==aExtent)
1.971 + terminator=-1;
1.972 + else
1.973 + {
1.974 + TInt anchor=((end>>KShiftFrameLength16)+1)<<KShiftFrameLength16;
1.975 + if (aExtent<anchor)
1.976 + {
1.977 + __ASSERT_DEBUG(aExtent-KSizeFrameDes16-end>0,User::Invariant());
1.978 + terminator=EFrameFree16+(aExtent-KSizeFrameDes16-end);
1.979 + }
1.980 + else
1.981 + terminator=EFrameFree16+KFrameOpen16;
1.982 + }
1.983 +//
1.984 + RFrame16Buf from(Coord().Base());
1.985 + from.Set(Host(),aStream,aStream+aLength,MStreamBuf::ERead);
1.986 + from.PushL();
1.987 + TRelocatorInput input(Host(),iMark);
1.988 + input.OpenL(aType,Coord().Base(),iFree,aLength,terminator);
1.989 + from.ReadL(input,aLength);
1.990 + input.CommitL();
1.991 + CleanupStack::PopAndDestroy();
1.992 +//
1.993 + return end;
1.994 + }
1.995 +
1.996 +
1.997 +TInt CPermanentStoreCollector::FastResetL()
1.998 +//
1.999 +// Fill the table with the streams with data in the store
1.1000 +//
1.1001 + {
1.1002 + iStreams.Reset();
1.1003 +//
1.1004 + CleanupClosePushL(iStreams);
1.1005 + RPermanentStoreTocIter iter(Coord().ConsolidateL());
1.1006 + CleanupReleasePushL(iter);
1.1007 + TEntry entry;
1.1008 + for (iter.ResetL();iter.NextL(entry.entry);)
1.1009 + {
1.1010 + if (entry.entry.handle<0)
1.1011 + continue;
1.1012 + if (entry.entry.ref<0)
1.1013 + continue;
1.1014 + User::LeaveIfError(iStreams.Append(entry));
1.1015 + }
1.1016 + CleanupStack::PopAndDestroy(&iter);
1.1017 + CleanupStack::Pop(&iStreams);
1.1018 +//
1.1019 + // always have final (toc) step
1.1020 + iState = ERelocateToc;
1.1021 + TInt streams = iStreams.Count();
1.1022 + if (streams == 0)
1.1023 + return 1;
1.1024 + iState = EFastSort;
1.1025 + // ordering is 1 step and evaluating the extents is several more
1.1026 + TInt count = 2 + (streams + EExtentStep - 1)/EExtentStep;
1.1027 + if (Compacting())
1.1028 + count += streams;
1.1029 + return count;
1.1030 + }
1.1031 +
1.1032 +void CPermanentStoreCollector::FastSort()
1.1033 + {
1.1034 + __ASSERT_DEBUG(iState == EFastSort, User::Invariant());
1.1035 +//
1.1036 + iStreams.SortSigned();
1.1037 + iNext = &iStreams[0];
1.1038 + iLast = iNext + iStreams.Count();
1.1039 + iState = EFastExtent;
1.1040 + }
1.1041 +
1.1042 +void CPermanentStoreCollector::FastExtentL(TInt& aTotal)
1.1043 +//
1.1044 +// Evaluate the lengths for all the streams
1.1045 +// if reclaiming, update aTotal with free space skipped
1.1046 +// return false until we've done the last one
1.1047 +//
1.1048 + {
1.1049 + __ASSERT_DEBUG(iState == EFastExtent, User::Invariant());
1.1050 + __ASSERT_DEBUG(iNext != iLast, User::Invariant());
1.1051 +
1.1052 + TEntry* e = iNext;
1.1053 + const TEntry* end = Min(iLast, e + EExtentStep);
1.1054 + do
1.1055 + {
1.1056 + TInt ref = e->entry.ref;
1.1057 + __ASSERT_DEBUG(TUint(iFree)<=TUint(ref),User::Invariant());
1.1058 + TInt ext = ::ExtentL(Host(), iMark, Coord().Base(), ref);
1.1059 + e->len = ext - ref;
1.1060 + if (!Compacting())
1.1061 + aTotal += ref - iFree;
1.1062 + iFree = SkipLink(ext);
1.1063 + } while (++e < end);
1.1064 + iNext = e;
1.1065 +//
1.1066 + if (e == iLast)
1.1067 + {
1.1068 + if (!Compacting())
1.1069 + iState = ERelocateToc;
1.1070 + else
1.1071 + {
1.1072 + iNext = &iStreams[0];
1.1073 + iFree = 0;
1.1074 + iState = EFastRelocate;
1.1075 + }
1.1076 + }
1.1077 + }
1.1078 +
1.1079 +CPermanentStoreCollector::TEntry* CPermanentStoreCollector::BestFit(TInt aPos, TInt aExt, TEntry* aFirst, TEntry* aLast)
1.1080 +//
1.1081 +// [aPos, aExt) is a hole - find the best fit to fill it in [aFirst, aLast)
1.1082 +//
1.1083 + {
1.1084 + __ASSERT_DEBUG(aPos <= aExt, User::Invariant());
1.1085 + TEntry* r = 0;
1.1086 + if (aPos == aExt)
1.1087 + return r;
1.1088 +//
1.1089 + if ((aExt & KMaskFrameLength16) != 0)
1.1090 + aExt -= KSizeFrameDes16;
1.1091 + const TInt mingap = Min(KSizeFrameDes16 + 1, (aExt & KMaskFrameLength16));
1.1092 + TInt rlen = 0;
1.1093 + TInt avail = aExt - aPos;
1.1094 + do
1.1095 + {
1.1096 + TInt len;
1.1097 + for (;;)
1.1098 + {
1.1099 + len = (--aLast)->len;
1.1100 + if (len > rlen)
1.1101 + break;
1.1102 + if (aFirst == aLast)
1.1103 + return r;
1.1104 + }
1.1105 + TInt d = avail - len;
1.1106 + if (d < 0)
1.1107 + continue;
1.1108 + if (d == 0) // exact fit
1.1109 + return aLast;
1.1110 + if (d < mingap)
1.1111 + continue;
1.1112 + r = aLast;
1.1113 + rlen = len;
1.1114 + } while (aFirst != aLast);
1.1115 + return r;
1.1116 + }
1.1117 +
1.1118 +void CPermanentStoreCollector::FastRelocateL(TInt& aTotal)
1.1119 +//
1.1120 +// Look for a stream to move. Either move a stream or fail to find a fit before returning
1.1121 +// fill holes from the front of the file with the biggest block that will fit (inverted current algorithm)
1.1122 +// return true when the last hole has been looked at
1.1123 +//
1.1124 + {
1.1125 + __ASSERT_DEBUG(iState == EFastRelocate, User::Invariant());
1.1126 + __ASSERT_DEBUG(iNext != iLast, User::Invariant());
1.1127 +
1.1128 + TEntry* e = iNext;
1.1129 + TInt ext = e->entry.ref;
1.1130 + __ASSERT_DEBUG(ext >= 0, User::Invariant());
1.1131 +
1.1132 + TEntry* r = BestFit(iFree, ext, e, iLast);
1.1133 + if (!r)
1.1134 + {
1.1135 + // Nothing fits, accumulate free space
1.1136 + aTotal += ext - iFree;
1.1137 + iFree = SkipLink(ext + e->len);
1.1138 + }
1.1139 + else
1.1140 + {
1.1141 + // lets move it
1.1142 + RelocateStreamL(*r, ext);
1.1143 + if (r != e)
1.1144 + {
1.1145 + // relocated a stream other than the one terminating the current hole
1.1146 + // mark it at moved
1.1147 + r->entry.ref = -1;
1.1148 + r->len = -1;
1.1149 + return;
1.1150 + }
1.1151 + }
1.1152 + // skip through any relocated streams
1.1153 + while (++e < iLast && e->entry.ref < 0)
1.1154 + ;
1.1155 + iNext = e;
1.1156 + if (e == iLast)
1.1157 + iState = ERelocateToc;
1.1158 + }