SparseBitmapTest.cpp

Go to the documentation of this file.
00001 /*
00002 // $Id: //open/dev/fennel/test/SparseBitmapTest.cpp#5 $
00003 // Fennel is a library of data storage and processing components.
00004 // Copyright (C) 2008-2009 The Eigenbase Project
00005 // Copyright (C) 2008-2009 SQLstream, Inc.
00006 // Copyright (C) 2008-2009 LucidEra, Inc.
00007 //
00008 // This program is free software; you can redistribute it and/or modify it
00009 // under the terms of the GNU General Public License as published by the Free
00010 // Software Foundation; either version 2 of the License, or (at your option)
00011 // any later version approved by The Eigenbase Project.
00012 //
00013 // This program is distributed in the hope that it will be useful,
00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 // GNU General Public License for more details.
00017 //
00018 // You should have received a copy of the GNU General Public License
00019 // along with this program; if not, write to the Free Software
00020 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
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 // NOTE jvs 25-Nov-2008:  This file contains the code for the example
00036 // in http://pub.eigenbase.org/wiki/FennelPageBasedDataStructureHowto;
00037 // if you modify the wiki page, please be sure to modify the code as well,
00038 // and vice versa.
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<SparseBitmapDirectory> 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_cast<fennel::PConstBuffer>(this + 1);
00120     }
00121 
00126     fennel::PBuffer getBytesForWrite()
00127     {
00128         return reinterpret_cast<fennel::PBuffer>(this + 1);
00129     }
00130 };
00131 
00135 typedef fennel::SegNodeLock<SparseBitmapLeaf> 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         // create new empty directory
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     // precompute some limits based on page and header sizes
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     // Lock directory page in shared mode
00291     SparseBitmapDirLock dirLock;
00292     dirLock.accessSegment(segmentAccessor);
00293     dirLock.lockShared(dirPageId);
00294 
00295     // Compute start offset of leaf page containing iOffset
00296     SparseBitmapOffset iLeafStartOffset =
00297         (iOffset / nBitsPerLeaf) * nBitsPerLeaf;
00298 
00299     // Look for it in the directory
00300     fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset);
00301     if (leafId == fennel::NULL_PAGE_ID) {
00302         // Not in directory, so the bit is not set
00303         return false;
00304     }
00305 
00306     // Unlock directory node early since we don't need it any more
00307     dirLock.unlock();
00308 
00309     // Lock leaf page and perform sanity check
00310     SparseBitmapLeafLock leafLock;
00311     leafLock.accessSegment(segmentAccessor);
00312     leafLock.lockShared(leafId);
00313     SparseBitmapLeaf const &leaf = leafLock.getNodeForRead();
00314     assert(leaf.iStartOffset == iLeafStartOffset);
00315 
00316     // Read bit value from leaf
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     // Lock directory page in exclusive mode
00331     SparseBitmapDirLock dirLock;
00332     dirLock.accessSegment(segmentAccessor);
00333     dirLock.lockExclusive(dirPageId);
00334 
00335     // Search directory; if it already has a corresponding leaf entry,
00336     // we won't need to modify the directory
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         // Leaf doesn't exist yet:  we'll need a new one
00346         SparseBitmapDirectory &dir = dirLock.getNodeForWrite();
00347         if (dir.nEntries >= nDirEntriesMax) {
00348             // Oops, directory is full and we have no provisions
00349             // for splitting it; we haven't modified the directory yet,
00350             // so the bitmap remains intact
00351             throw std::runtime_error("SparseBitmap directory full");
00352         }
00353         // Allocate new leaf and add it to the directory
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         // Leaf already exists, so no need to modify directory;
00364         // we can unlock the directory early
00365         dirLock.unlock();
00366         leafLock.lockExclusive(leafId);
00367     }
00368 
00369     // Write bit value to leaf
00370     SparseBitmapLeaf &leaf = leafLock.getNodeForWrite();
00371     fennel::PBuffer pBytes = leaf.getBytesForWrite();
00372     if (clearLeaf) {
00373         // We're initializing a new leaf, so clear all the bits first
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     // Create or load a file device
00445     pDevice.reset(
00446         new RandomAccessFileDevice(
00447             "bitmap.dat",
00448             deviceMode,
00449             0));
00450 
00451     // Set up the cache
00452     CacheParams cacheParams;
00453     cacheParams.readConfig(configMap);
00454     pCache = Cache::newCache(cacheParams);
00455     pCache->registerDevice(BITMAP_DEVICE_ID, pDevice);
00456 
00457     // Map a segment onto the file
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     // Regardless of how the test ends, be sure to close all resources
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     // Create a new bitmap and set a single bit at offset 0
00505     PageId dirPageId;
00506     openStorage(DeviceMode::createNew);
00507 
00508     {
00509         SparseBitmap bitmap(segmentAccessor);
00510         dirPageId = bitmap.getDirPageId();
00511         bitmap.setBit(0, 1);
00512 
00513         // Make sure we can read the bit back
00514         bool x = bitmap.getBit(0);
00515         BOOST_CHECK_EQUAL(1, x);
00516     }
00517 
00518     // Now close and re-open storage
00519     closeStorage();
00520     openStorage(DeviceMode::load);
00521 
00522     {
00523         // Verify that we can still read the bit back
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     // Similar to testBasic, but use a bunch of predefined bit offsets
00533 
00534     std::vector<SparseBitmapOffset> 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<SparseBitmapOffset> 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         // Also verify that some bits didn't get accidentally set
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         // Expected values below are only valid for 4K page size
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     // Negative test to make sure we get the expected failure
00596     // when the directory fills up completely
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         // stride forward to next leaf
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         // failure expected
00610     }
00611 }
00612 
00613 FENNEL_UNIT_TEST_SUITE(SparseBitmapTest);
00614 
00615 // End SparseBitmapTest.cpp

Generated on Mon Jun 22 04:00:21 2009 for Fennel by  doxygen 1.5.1