SparseBitmapTest.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 #include "fennel/common/CommonPreamble.h" 00024 #include "fennel/segment/SegPageLock.h" 00025 #include "fennel/segment/SegmentFactory.h" 00026 #include "fennel/segment/LinearDeviceSegment.h" 00027 #include "fennel/device/RandomAccessFileDevice.h" 00028 #include "fennel/cache/Cache.h" 00029 #include "fennel/cache/CacheParams.h" 00030 #include "fennel/test/TestBase.h" 00031 00032 #include <boost/test/test_tools.hpp> 00033 #include <boost/bind.hpp> 00034 00035 00036 00037 00038 00039 00043 typedef uint64_t SparseBitmapOffset; 00044 00048 struct SparseBitmapDirEntry 00049 { 00053 SparseBitmapOffset iLeafStartOffset; 00054 00058 fennel::PageId leafId; 00059 }; 00060 00064 struct SparseBitmapDirectory : public fennel::StoredNode 00065 { 00066 static const fennel::MagicNumber MAGIC_NUMBER = 0x82009900461412f0LL; 00067 00071 uint nEntries; 00072 00077 SparseBitmapDirEntry const *getEntriesForRead() const 00078 { 00079 return reinterpret_cast<SparseBitmapDirEntry const *>( 00080 this + 1); 00081 } 00082 00087 SparseBitmapDirEntry *getEntriesForWrite() 00088 { 00089 return reinterpret_cast<SparseBitmapDirEntry *>( 00090 this + 1); 00091 } 00092 }; 00093 00097 typedef fennel::SegNodeLock SparseBitmapDirLock; 00098 00102 struct SparseBitmapLeaf : public fennel::StoredNode 00103 { 00104 static const fennel::MagicNumber MAGIC_NUMBER = 0xba107d175b3338dcLL; 00105 00111 SparseBitmapOffset iStartOffset; 00112 00117 fennel::PConstBuffer getBytesForRead() const 00118 { 00119 return reinterpret_castfennel::PConstBuffer(this + 1); 00120 } 00121 00126 fennel::PBuffer getBytesForWrite() 00127 { 00128 return reinterpret_castfennel::PBuffer(this + 1); 00129 } 00130 }; 00131 00135 typedef fennel::SegNodeLock SparseBitmapLeafLock; 00136 00142 class SparseBitmap 00143 { 00147 fennel::SegmentAccessor segmentAccessor; 00148 00152 fennel::PageId dirPageId; 00153 00159 size_t nBitsPerLeaf; 00160 00167 size_t nDirEntriesMax; 00168 00179 fennel::PageId searchDirectory( 00180 SparseBitmapDirLock &dirLock, 00181 SparseBitmapOffset iLeafStartOffset); 00182 00183 public: 00193 explicit SparseBitmap( 00194 fennel::SegmentAccessor segmentAccessor, 00195 fennel::PageId dirPageId = fennel::NULL_PAGE_ID); 00196 00200 virtual ~SparseBitmap(); 00201 00209 bool getBit(SparseBitmapOffset iOffset); 00210 00218 void setBit(SparseBitmapOffset iOffset, bool value); 00219 00223 fennel::PageId getDirPageId() const; 00224 00228 size_t getBitsPerLeaf() const; 00229 00234 size_t getMaxDirectoryEntries() const; 00235 }; 00236 00237 SparseBitmap::SparseBitmap( 00238 fennel::SegmentAccessor segmentAccessorInit, 00239 fennel::PageId dirPageIdInit) 00240 { 00241 segmentAccessor = segmentAccessorInit; 00242 dirPageId = dirPageIdInit; 00243 00244 if (dirPageId == fennel::NULL_PAGE_ID) { 00245
00246 SparseBitmapDirLock dirLock; 00247 dirLock.accessSegment(segmentAccessor); 00248 dirPageId = dirLock.allocatePage(fennel::ANON_PAGE_OWNER_ID); 00249 SparseBitmapDirectory &dir = dirLock.getNodeForWrite(); 00250 dir.nEntries = 0; 00251 } 00252 00253
00254 size_t cbPage = segmentAccessor.pSegment->getUsablePageSize(); 00255 size_t nBytesPerLeaf = cbPage - sizeof(SparseBitmapLeaf); 00256 nBitsPerLeaf = nBytesPerLeaf * 8; 00257 assert(nBitsPerLeaf > 0); 00258 00259 nDirEntriesMax = 00260 (cbPage - sizeof(SparseBitmapDirectory)) / sizeof(SparseBitmapDirEntry); 00261 assert(nDirEntriesMax > 0); 00262 } 00263 00264 SparseBitmap::~SparseBitmap() 00265 { 00266 } 00267 00268 fennel::PageId SparseBitmap::searchDirectory( 00269 SparseBitmapDirLock &dirLock, 00270 SparseBitmapOffset iLeafStartOffset) 00271 { 00272 SparseBitmapDirectory const &dir = dirLock.getNodeForRead(); 00273 00274 SparseBitmapDirEntry const *pFirst = dir.getEntriesForRead(); 00275 SparseBitmapDirEntry const *pLast = pFirst + dir.nEntries; 00276 SparseBitmapDirEntry const *pFound = 00277 std::find_if( 00278 pFirst, 00279 pLast, 00280 boost::bind(&SparseBitmapDirEntry::iLeafStartOffset, _1) 00281 == iLeafStartOffset); 00282 if (pFound == pLast) { 00283 return fennel::NULL_PAGE_ID; 00284 } 00285 return pFound->leafId; 00286 } 00287 00288 bool SparseBitmap::getBit(SparseBitmapOffset iOffset) 00289 { 00290
00291 SparseBitmapDirLock dirLock; 00292 dirLock.accessSegment(segmentAccessor); 00293 dirLock.lockShared(dirPageId); 00294 00295
00296 SparseBitmapOffset iLeafStartOffset = 00297 (iOffset / nBitsPerLeaf) * nBitsPerLeaf; 00298 00299
00300 fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset); 00301 if (leafId == fennel::NULL_PAGE_ID) { 00302
00303 return false; 00304 } 00305 00306
00307 dirLock.unlock(); 00308 00309
00310 SparseBitmapLeafLock leafLock; 00311 leafLock.accessSegment(segmentAccessor); 00312 leafLock.lockShared(leafId); 00313 SparseBitmapLeaf const &leaf = leafLock.getNodeForRead(); 00314 assert(leaf.iStartOffset == iLeafStartOffset); 00315 00316
00317 fennel::PConstBuffer pBytes = leaf.getBytesForRead(); 00318 size_t iBit = iOffset - iLeafStartOffset; 00319 size_t iByte = iBit / 8; 00320 size_t iBitInByte = iBit - 8 * iByte; 00321 if (pBytes[iByte] & (1 << iBitInByte)) { 00322 return true; 00323 } else { 00324 return false; 00325 } 00326 } 00327 00328 void SparseBitmap::setBit(SparseBitmapOffset iOffset, bool value) 00329 { 00330
00331 SparseBitmapDirLock dirLock; 00332 dirLock.accessSegment(segmentAccessor); 00333 dirLock.lockExclusive(dirPageId); 00334 00335
00336
00337 SparseBitmapOffset iLeafStartOffset = 00338 (iOffset / nBitsPerLeaf) * nBitsPerLeaf; 00339 fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset); 00340 00341 SparseBitmapLeafLock leafLock; 00342 leafLock.accessSegment(segmentAccessor); 00343 bool clearLeaf = false; 00344 if (leafId == fennel::NULL_PAGE_ID) { 00345
00346 SparseBitmapDirectory &dir = dirLock.getNodeForWrite(); 00347 if (dir.nEntries >= nDirEntriesMax) { 00348
00349
00350
00351 throw std::runtime_error("SparseBitmap directory full"); 00352 } 00353
00354 SparseBitmapDirEntry *pLast = 00355 dir.getEntriesForWrite() + dir.nEntries; 00356 leafId = leafLock.allocatePage(fennel::ANON_PAGE_OWNER_ID); 00357 pLast->iLeafStartOffset = iLeafStartOffset; 00358 pLast->leafId = leafId; 00359 dir.nEntries++; 00360 clearLeaf = true; 00361 dirLock.unlock(); 00362 } else { 00363
00364
00365 dirLock.unlock(); 00366 leafLock.lockExclusive(leafId); 00367 } 00368 00369
00370 SparseBitmapLeaf &leaf = leafLock.getNodeForWrite(); 00371 fennel::PBuffer pBytes = leaf.getBytesForWrite(); 00372 if (clearLeaf) { 00373
00374 leaf.iStartOffset = iLeafStartOffset; 00375 memset(pBytes, 0, nBitsPerLeaf / 8); 00376 } 00377 size_t iBit = iOffset - iLeafStartOffset; 00378 size_t iByte = iBit / 8; 00379 size_t iBitInByte = iBit - 8 * iByte; 00380 if (value) { 00381 pBytes[iByte] |= (1 << iBitInByte); 00382 } else { 00383 pBytes[iByte] &= ~(1 << iBitInByte); 00384 } 00385 } 00386 00387 fennel::PageId SparseBitmap::getDirPageId() const 00388 { 00389 return dirPageId; 00390 } 00391 00392 size_t SparseBitmap::getBitsPerLeaf() const 00393 { 00394 return nBitsPerLeaf; 00395 } 00396 00397 size_t SparseBitmap::getMaxDirectoryEntries() const 00398 { 00399 return nDirEntriesMax; 00400 } 00401 00402 using namespace fennel; 00403 00407 class SparseBitmapTest : virtual public TestBase 00408 { 00409 SharedRandomAccessDevice pDevice; 00410 SharedCache pCache; 00411 SharedSegmentFactory pSegmentFactory; 00412 SharedSegment pSegment; 00413 SegmentAccessor segmentAccessor; 00414 00415 static const DeviceId BITMAP_DEVICE_ID; 00416 00417 void openStorage(DeviceMode deviceMode); 00418 void closeStorage(); 00419 00420 public: 00421 explicit SparseBitmapTest() 00422 { 00423 FENNEL_UNIT_TEST_CASE(SparseBitmapTest,testBasic); 00424 FENNEL_UNIT_TEST_CASE(SparseBitmapTest,testSpread); 00425 FENNEL_UNIT_TEST_CASE(SparseBitmapTest,testSizes); 00426 FENNEL_UNIT_TEST_CASE(SparseBitmapTest,testFullDirectory); 00427 } 00428 00429 virtual void testCaseTearDown(); 00430 00431 void testBasic(); 00432 void testSpread(); 00433 void testSizes(); 00434 void testFullDirectory(); 00435 }; 00436 00440 const DeviceId SparseBitmapTest::BITMAP_DEVICE_ID = DeviceId(1); 00441 00442 void SparseBitmapTest::openStorage(DeviceMode deviceMode) 00443 { 00444
00445 pDevice.reset( 00446 new RandomAccessFileDevice( 00447 "bitmap.dat", 00448 deviceMode, 00449 0)); 00450 00451
00452 CacheParams cacheParams; 00453 cacheParams.readConfig(configMap); 00454 pCache = Cache::newCache(cacheParams); 00455 pCache->registerDevice(BITMAP_DEVICE_ID, pDevice); 00456 00457
00458 pSegmentFactory = 00459 SegmentFactory::newSegmentFactory(configMap, shared_from_this()); 00460 LinearDeviceSegmentParams segParams; 00461 CompoundId::setDeviceId(segParams.firstBlockId, BITMAP_DEVICE_ID); 00462 CompoundId::setBlockNum(segParams.firstBlockId, 0); 00463 if (!deviceMode.create) { 00464 segParams.nPagesAllocated = MAXU; 00465 } 00466 pSegment = pSegmentFactory->newLinearDeviceSegment( 00467 pCache, 00468 segParams); 00469 segmentAccessor.pSegment = pSegment; 00470 segmentAccessor.pCacheAccessor = pCache; 00471 } 00472 00473 void SparseBitmapTest::testCaseTearDown() 00474 { 00475
00476 closeStorage(); 00477 TestBase::testCaseTearDown(); 00478 } 00479 00480 void SparseBitmapTest::closeStorage() 00481 { 00482 segmentAccessor.reset(); 00483 if (pSegment) { 00484 assert(pSegment.unique()); 00485 pSegment.reset(); 00486 } 00487 if (pSegmentFactory) { 00488 assert(pSegmentFactory.unique()); 00489 pSegmentFactory.reset(); 00490 } 00491 if (pCache) { 00492 pCache->unregisterDevice(BITMAP_DEVICE_ID); 00493 assert(pCache.unique()); 00494 pCache.reset(); 00495 } 00496 if (pDevice) { 00497 assert(pDevice.unique()); 00498 pDevice.reset(); 00499 } 00500 } 00501 00502 void SparseBitmapTest::testBasic() 00503 { 00504
00505 PageId dirPageId; 00506 openStorage(DeviceMode::createNew); 00507 00508 { 00509 SparseBitmap bitmap(segmentAccessor); 00510 dirPageId = bitmap.getDirPageId(); 00511 bitmap.setBit(0, 1); 00512 00513
00514 bool x = bitmap.getBit(0); 00515 BOOST_CHECK_EQUAL(1, x); 00516 } 00517 00518
00519 closeStorage(); 00520 openStorage(DeviceMode::load); 00521 00522 { 00523
00524 SparseBitmap bitmap(segmentAccessor, dirPageId); 00525 bool x = bitmap.getBit(0); 00526 BOOST_CHECK_EQUAL(1, x); 00527 } 00528 } 00529 00530 void SparseBitmapTest::testSpread() 00531 { 00532
00533 00534 std::vector filledOffsets; 00535 filledOffsets.push_back(5); 00536 filledOffsets.push_back(6); 00537 filledOffsets.push_back(8); 00538 filledOffsets.push_back(100); 00539 filledOffsets.push_back(50000); 00540 filledOffsets.push_back(50001); 00541 filledOffsets.push_back(50004); 00542 filledOffsets.push_back(55000); 00543 00544 std::vector emptyOffsets; 00545 emptyOffsets.push_back(0); 00546 emptyOffsets.push_back(7); 00547 emptyOffsets.push_back(1000); 00548 emptyOffsets.push_back(50003); 00549 emptyOffsets.push_back(1000000); 00550 00551 PageId dirPageId; 00552 openStorage(DeviceMode::createNew); 00553 00554 { 00555 SparseBitmap bitmap(segmentAccessor); 00556 dirPageId = bitmap.getDirPageId(); 00557 for (int i = 0; i < filledOffsets.size(); ++i) { 00558 bitmap.setBit(filledOffsets[i], 1); 00559 } 00560 } 00561 00562 closeStorage(); 00563 00564 openStorage(DeviceMode::load); 00565 00566 { 00567 SparseBitmap bitmap(segmentAccessor, dirPageId); 00568 for (int i = 0; i < filledOffsets.size(); ++i) { 00569 bool x = bitmap.getBit(filledOffsets[i]); 00570 BOOST_CHECK_EQUAL(1, x); 00571 } 00572 00573
00574 for (int i = 0; i < emptyOffsets.size(); ++i) { 00575 bool x = bitmap.getBit(emptyOffsets[i]); 00576 BOOST_CHECK_EQUAL(0, x); 00577 } 00578 } 00579 } 00580 00581 void SparseBitmapTest::testSizes() 00582 { 00583 openStorage(DeviceMode::createNew); 00584 if (pCache->getPageSize() != 4096) { 00585
00586 return; 00587 } 00588 SparseBitmap bitmap(segmentAccessor); 00589 BOOST_CHECK_EQUAL(32640, bitmap.getBitsPerLeaf()); 00590 BOOST_CHECK_EQUAL(255, bitmap.getMaxDirectoryEntries()); 00591 } 00592 00593 void SparseBitmapTest::testFullDirectory() 00594 { 00595
00596
00597 openStorage(DeviceMode::createNew); 00598 SparseBitmap bitmap(segmentAccessor); 00599 int iOffset = 10; 00600 for (int i = 0; i < bitmap.getMaxDirectoryEntries(); ++i) { 00601 bitmap.setBit(iOffset, 1); 00602
00603 iOffset += bitmap.getBitsPerLeaf(); 00604 } 00605 try { 00606 bitmap.setBit(iOffset, 1); 00607 BOOST_FAIL("directory full exception expected"); 00608 } catch (std::exception ex) { 00609
00610 } 00611 } 00612 00613 FENNEL_UNIT_TEST_SUITE(SparseBitmapTest); 00614 00615