Fennel: /home/pub/open/dev/fennel/segment/RandomAllocationSegmentBase.cpp Source File (original) (raw)
00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "fennel/common/CommonPreamble.h"
00025 #include "fennel/segment/RandomAllocationSegmentBaseImpl.h"
00026
00027 FENNEL_BEGIN_CPPFILE("$Id: //open/dev/fennel/segment/RandomAllocationSegmentBase.cpp#12 $");
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 RandomAllocationSegmentBase::RandomAllocationSegmentBase(
00042 SharedSegment delegateSegment)
00043 : DelegatingSegment(delegateSegment)
00044 {
00045 permAssert(DelegatingSegment::getAllocationOrder() == LINEAR_ALLOCATION);
00046
00047
00048
00049 nExtentsPerSegAlloc =
00050 (getUsablePageSize() - sizeof(SegmentAllocationNode))
00051 / sizeof(SegmentAllocationNode::ExtentEntry);
00052
00053 nPagesOccupiedHighWater = 0;
00054 nPagesAllocated = 0;
00055 netDeallocations = 0;
00056 }
00057
00058 RandomAllocationSegmentBase::~RandomAllocationSegmentBase()
00059 {
00060 }
00061
00062 void RandomAllocationSegmentBase::initForUse()
00063 {
00064 countAllocatedPages();
00065 }
00066
00067 void RandomAllocationSegmentBase::format()
00068 {
00069
00070 uint nSegAllocPages = inferSegAllocCount();
00071
00072
00073 ExtentNum nExtents = (nSegAllocPages-1)nExtentsPerSegAlloc;
00074
00075
00076 BlockNum nRemainderPages = DelegatingSegment::getAllocatedSizeInPages();
00077 nRemainderPages -= (nExtentsnPagesPerExtent+nSegAllocPages);
00078
00079 if (nRemainderPages) {
00080
00081
00082 nExtents += nRemainderPages / nPagesPerExtent;
00083 } else {
00084
00085 nExtents += nExtentsPerSegAlloc;
00086 }
00087
00088
00089
00090 if (!nExtents) {
00091 nSegAllocPages = 1;
00092 nExtents = 1;
00093 }
00094
00095
00096 bool bigEnough = DelegatingSegment::ensureAllocatedSize(
00097 nExtents*nPagesPerExtent + nSegAllocPages);
00098 permAssert(bigEnough);
00099
00100
00101
00102 ExtentNum extentNum = 0;
00103 SegmentAccessor selfAccessor(getTracingSegment(), pCache);
00104 SegAllocLock segAllocLock(selfAccessor);
00105 for (uint iSegAlloc = 0; iSegAlloc < nSegAllocPages; iSegAlloc++) {
00106 PageId segAllocPageId = getSegAllocPageId(iSegAlloc);
00107 segAllocLock.lockExclusive(segAllocPageId);
00108
00109
00110
00111
00112 segAllocLock.setMagicNumber();
00113 SegmentAllocationNode &segAllocNode = segAllocLock.getNodeForWrite();
00114
00115 uint iNextSegAlloc = iSegAlloc + 1;
00116 if (iNextSegAlloc < nSegAllocPages) {
00117
00118 segAllocNode.nextSegAllocPageId = getSegAllocPageId(iNextSegAlloc);
00119 } else {
00120
00121 segAllocNode.nextSegAllocPageId = NULL_PAGE_ID;
00122 }
00123
00124
00125 segAllocNode.nPagesPerExtent = nPagesPerExtent;
00126 segAllocNode.nExtents = std::min(nExtents,nExtentsPerSegAlloc);
00127 nExtents -= segAllocNode.nExtents;
00128
00129
00130 formatPageExtents(segAllocNode, extentNum);
00131 }
00132
00133 permAssert(!nExtents);
00134 }
00135
00136 void RandomAllocationSegmentBase::markPageEntryUnused(
00137 PageEntry &pageEntry)
00138 {
00139 pageEntry.ownerId = UNALLOCATED_PAGE_OWNER_ID;
00140 pageEntry.successorId = NULL_PAGE_ID;
00141 }
00142
00143 uint RandomAllocationSegmentBase::inferSegAllocCount()
00144 {
00145 BlockNum nPages = DelegatingSegment::getAllocatedSizeInPages();
00146
00147 return nPages / nPagesPerSegAlloc +
00148 (nPages % nPagesPerSegAlloc ? 1 : 0);
00149 }
00150
00151 PageId RandomAllocationSegmentBase::allocatePageIdFromSegment(
00152 PageOwnerId ownerId,
00153 SharedSegment allocNodeSegment)
00154 {
00155 ExtentNum extentNum = 0;
00156 SegmentAccessor segAccessor(allocNodeSegment, pCache);
00157 SegAllocLock segAllocLock(segAccessor);
00158
00159
00160 PageId origSegAllocPageId = getFirstSegAllocPageId();
00161 PageId segAllocPageId = getSegAllocPageIdForWrite(origSegAllocPageId);
00162 for (uint iSegAlloc = 0; ; ++iSegAlloc) {
00163
00164
00165
00166 segAllocLock.lockExclusive(segAllocPageId);
00167 SegmentAllocationNode const &readOnlySegAllocNode =
00168 segAllocLock.getNodeForRead();
00169
00170
00171 for (uint i = 0; i < readOnlySegAllocNode.nExtents; ++i, ++extentNum) {
00172 SegmentAllocationNode::ExtentEntry const &readOnlyExtentEntry =
00173 readOnlySegAllocNode.getExtentEntry(i);
00174 if (readOnlyExtentEntry.nUnallocatedPages) {
00175
00176 SegmentAllocationNode &writableSegAllocNode =
00177 segAllocLock.getNodeForWrite();
00178 SegmentAllocationNode::ExtentEntry &writableExtentEntry =
00179 writableSegAllocNode.getExtentEntry(i);
00180 writableExtentEntry.nUnallocatedPages--;
00181
00182
00183
00184
00185
00186 segAllocLock.unlock();
00187 incrementPageCounters();
00188 return allocateFromExtent(extentNum,ownerId);
00189 }
00190 }
00191
00192 if (readOnlySegAllocNode.nextSegAllocPageId != NULL_PAGE_ID) {
00193
00194
00195 undoSegAllocPageWrite(origSegAllocPageId);
00196
00197
00198 origSegAllocPageId = readOnlySegAllocNode.nextSegAllocPageId;
00199 segAllocPageId = getSegAllocPageIdForWrite(origSegAllocPageId);
00200 continue;
00201 }
00202
00203
00204
00205
00206
00207 if (readOnlySegAllocNode.nExtents < nExtentsPerSegAlloc) {
00208
00209
00210
00211 try {
00212 if ((
00213 makePageNum(extentNum,nPagesPerExtent)))
00214 {
00215
00216 undoSegAllocPageWrite(origSegAllocPageId);
00217 return NULL_PAGE_ID;
00218 }
00219 } catch (...) {
00220 undoSegAllocPageWrite(origSegAllocPageId);
00221 throw;
00222 }
00223
00224
00225 SegmentAllocationNode &writableSegAllocNode =
00226 segAllocLock.getNodeForWrite();
00227 writableSegAllocNode.nExtents++;
00228 SegmentAllocationNode::ExtentEntry &writableExtentEntry =
00229 writableSegAllocNode.getExtentEntry(
00230 writableSegAllocNode.nExtents - 1);
00231
00232
00233
00234 writableExtentEntry.nUnallocatedPages = nPagesPerExtent - 2;
00235
00236 incrementPageCounters();
00237
00238 incrementPagesOccupiedCounter();
00239 return allocateFromNewExtent(extentNum, ownerId);
00240 }
00241
00242
00243
00244 undoSegAllocPageWrite(origSegAllocPageId);
00245
00246
00247
00248
00249 if ((
00250 makePageNum(extentNum + 1,0)))
00251 {
00252
00253 return NULL_PAGE_ID;
00254 }
00255
00256 SegAllocLock newSegAllocLock(segAccessor);
00257 origSegAllocPageId = getSegAllocPageId(iSegAlloc + 1);
00258 segAllocPageId = getSegAllocPageIdForWrite(origSegAllocPageId);
00259 newSegAllocLock.lockExclusive(segAllocPageId);
00260 newSegAllocLock.setMagicNumber();
00261 SegmentAllocationNode &newNode = newSegAllocLock.getNodeForWrite();
00262 newNode.nPagesPerExtent = nPagesPerExtent;
00263 newNode.nExtents = 0;
00264 newNode.nextSegAllocPageId = NULL_PAGE_ID;
00265
00266 incrementPagesOccupiedCounter();
00267
00268
00269 SegmentAllocationNode &writableSegAllocNode =
00270 segAllocLock.getNodeForWrite();
00271 writableSegAllocNode.nextSegAllocPageId = origSegAllocPageId;
00272
00273
00274
00275
00276 }
00277 }
00278
00279 void RandomAllocationSegmentBase::splitPageId(
00280 PageId pageId,uint &iSegAlloc,
00281 ExtentNum &extentNum,BlockNum &iPageInExtent) const
00282 {
00283
00284 BlockNum iPageInSegAlloc = getLinearBlockNum(pageId) % nPagesPerSegAlloc;
00285 iSegAlloc = getLinearBlockNum(pageId) / nPagesPerSegAlloc;
00286 if (!iPageInSegAlloc) {
00287
00288 extentNum = MAXU;
00289 iPageInExtent = 0;
00290 } else {
00291
00292 --iPageInSegAlloc;
00293 extentNum =
00294 iPageInSegAlloc / nPagesPerExtent + nExtentsPerSegAlloc * iSegAlloc;
00295 iPageInExtent = iPageInSegAlloc % nPagesPerExtent;
00296 }
00297 }
00298
00299 void RandomAllocationSegmentBase::incrementPageCounters()
00300 {
00301 StrictMutexGuard mutexGuard(pageCounterMutex);
00302
00303
00304
00305 if (netDeallocations > 0) {
00306 --netDeallocations;
00307 } else {
00308 ++nPagesOccupiedHighWater;
00309 }
00310 ++nPagesAllocated;
00311 }
00312
00313 void RandomAllocationSegmentBase::incrementPagesOccupiedCounter()
00314 {
00315 StrictMutexGuard mutexGuard(pageCounterMutex);
00316 ++nPagesOccupiedHighWater;
00317 }
00318
00319 void RandomAllocationSegmentBase::decrementPageCounters()
00320 {
00321 StrictMutexGuard mutexGuard(pageCounterMutex);
00322 ++netDeallocations;
00323 --nPagesAllocated;
00324 }
00325
00326 void RandomAllocationSegmentBase::deallocatePageRange(
00327 PageId startPageId,
00328 PageId endPageId)
00329 {
00330 permAssert(startPageId == endPageId);
00331 if (startPageId != NULL_PAGE_ID) {
00332 deallocatePageId(startPageId);
00333 } else {
00334 format();
00335 }
00336 }
00337
00338 void RandomAllocationSegmentBase::deallocatePageId(PageId pageId)
00339 {
00340 permAssert(pageId != NULL_PAGE_ID);
00341 assert(isPageIdAllocated(pageId));
00342
00343
00344 BlockId blockId = DelegatingSegment::translatePageId(pageId);
00345 pCache->discardPage(blockId);
00346
00347 ExtentNum extentNum;
00348 BlockNum iPageInExtent;
00349 uint iSegAlloc;
00350 splitPageId(pageId,iSegAlloc,extentNum,iPageInExtent);
00351 permAssert(iPageInExtent);
00352
00353
00354
00355
00356 freePageEntry(extentNum, iPageInExtent);
00357
00358 SegmentAccessor selfAccessor(getTracingSegment(), pCache);
00359 SegAllocLock segAllocLock(selfAccessor);
00360 PageId segAllocPageId = getSegAllocPageId(iSegAlloc);
00361 segAllocLock.lockExclusive(segAllocPageId);
00362 SegmentAllocationNode &segAllocNode = segAllocLock.getNodeForWrite();
00363 ExtentNum relativeExtentNum = extentNum % nExtentsPerSegAlloc;
00364 segAllocNode.getExtentEntry(relativeExtentNum).nUnallocatedPages++;
00365 permAssert(
00366 segAllocNode.getExtentEntry(relativeExtentNum).nUnallocatedPages
00367 <= nPagesPerExtent);
00368
00369 decrementPageCounters();
00370 }
00371
00372 Segment::AllocationOrder RandomAllocationSegmentBase::getAllocationOrder() const
00373 {
00374 return RANDOM_ALLOCATION;
00375 }
00376
00377 BlockId RandomAllocationSegmentBase::translatePageId(PageId pageId)
00378 {
00379 assert(
00380 const_cast<RandomAllocationSegmentBase *>(this)->isPageIdValid(pageId));
00381
00382 return DelegatingSegment::translatePageId(pageId);
00383 }
00384
00385 bool RandomAllocationSegmentBase::testPageId(
00386 PageId pageId,
00387 bool testAllocation,
00388 bool thisSegment)
00389 {
00390 if ((pageId)) {
00391 return false;
00392 }
00393
00394 uint iSegAlloc;
00395 ExtentNum extentNum;
00396 BlockNum iPageInExtent;
00397 splitPageId(pageId,iSegAlloc,extentNum,iPageInExtent);
00398 if (!iPageInExtent) {
00399
00400
00401
00402 if (testAllocation) {
00403 return false;
00404 } else {
00405 return true;
00406 }
00407 }
00408 PageOwnerId ownerId = getPageOwnerId(pageId, thisSegment);
00409 return (ownerId != UNALLOCATED_PAGE_OWNER_ID);
00410 }
00411
00412 bool RandomAllocationSegmentBase::isPageIdValid(PageId pageId)
00413 {
00414 return testPageId(pageId,false,true);
00415 }
00416
00417 bool RandomAllocationSegmentBase::isPageIdAllocated(PageId pageId)
00418 {
00419 return testPageId(pageId,true,true);
00420 }
00421
00422 BlockNum RandomAllocationSegmentBase::getAllocatedSizeInPages()
00423 {
00424 return nPagesAllocated;
00425 }
00426
00427 void RandomAllocationSegmentBase::countAllocatedPages()
00428 {
00429 StrictMutexGuard mutexGuard(pageCounterMutex);
00430 PageId origSegAllocPageId = getFirstSegAllocPageId();
00431 do {
00432 SharedSegment allocNodeSegment;
00433 PageId segAllocPageId =
00434 getSegAllocPageIdForRead(origSegAllocPageId, allocNodeSegment);
00435
00436 PageId nextSegAllocPageId;
00437 tallySegAllocNodePages(
00438 segAllocPageId,
00439 allocNodeSegment,
00440 nextSegAllocPageId);
00441
00442 ++nPagesOccupiedHighWater;
00443
00444 origSegAllocPageId = nextSegAllocPageId;
00445 } while (origSegAllocPageId != NULL_PAGE_ID);
00446 }
00447
00448 BlockNum RandomAllocationSegmentBase::getNumPagesOccupiedHighWater()
00449 {
00450 return nPagesOccupiedHighWater;
00451 }
00452
00453 void RandomAllocationSegmentBase::tallySegAllocNodePages(
00454 PageId segAllocPageId,
00455 SharedSegment allocNodeSegment,
00456 PageId &nextSegAllocPageId)
00457 {
00458 SegmentAccessor segAccessor(allocNodeSegment, pCache);
00459 SegAllocLock segAllocLock(segAccessor);
00460
00461
00462
00463 segAllocLock.lockExclusive(segAllocPageId);
00464 SegmentAllocationNode const &node = segAllocLock.getNodeForRead();
00465 uint i;
00466 for (i = 0; i < node.nExtents; i++) {
00467
00468 BlockNum numPages =
00469 nPagesPerExtent
00470 - node.getExtentEntry(i).nUnallocatedPages;
00471 nPagesAllocated += (numPages - 1);
00472 nPagesOccupiedHighWater += numPages;
00473 }
00474 nextSegAllocPageId = node.nextSegAllocPageId;
00475 }
00476
00477 FENNEL_END_CPPFILE("$Id: //open/dev/fennel/segment/RandomAllocationSegmentBase.cpp#12 $");
00478
00479