From 7ea5c06059ee6668d6e6d04c3b3dcb8557061696 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Fri, 15 Jun 2012 13:27:59 +0000 Subject: Bu::Myriad now only uses BitString during initialization, and I'm going to replace that with just an array, no problem. It's many, many, many times faster while streams are growing, and it should be constant time, not linear like it was before. It also handles myriad files in excess of 2gb correctly now, at least, it seems to just fine :) --- default.bld | 6 +-- src/stable/file.cpp | 14 ++++++- src/stable/myriad.cpp | 109 +++++++++++++++++++++++++++--------------------- src/stable/myriad.h | 13 +++--- src/tests/bigmyriad.cpp | 25 +++++++++++ 5 files changed, 111 insertions(+), 56 deletions(-) create mode 100644 src/tests/bigmyriad.cpp diff --git a/default.bld b/default.bld index 6b6bbc3..c1b93af 100644 --- a/default.bld +++ b/default.bld @@ -14,8 +14,8 @@ include "gensigs.bld"; CXXFLAGS += "-ggdb -W -Wall -I."; -// CXXFLAGS += "-pg"; -// LDFLAGS += "-pg"; +//CXXFLAGS += "-pg"; +//LDFLAGS += "-pg"; action "default" { @@ -151,7 +151,7 @@ target "viewcsv" LDFLAGS += "-lncurses"; } -target ["myriad", "myriadfs", "tests/myriad", "tests/myriadfs", "unit/myriad"] +target ["myriad", "myriadfs", "tests/myriad", "tests/myriadfs", "unit/myriad", "tests/bigmyriad"] { LDFLAGS += "-lpthread"; } diff --git a/src/stable/file.cpp b/src/stable/file.cpp index 33420f1..14e4f3c 100644 --- a/src/stable/file.cpp +++ b/src/stable/file.cpp @@ -91,7 +91,11 @@ Bu::size Bu::File::tell() if( fd < 0 ) throw FileException("File not open."); +#ifdef USE_64BIT_IO + return lseek64( fd, 0, SEEK_CUR ); +#else return lseek( fd, 0, SEEK_CUR ); +#endif } void Bu::File::seek( Bu::size offset ) @@ -99,7 +103,11 @@ void Bu::File::seek( Bu::size offset ) if( fd < 0 ) throw FileException("File not open."); +#ifdef USE_64BIT_IO + lseek64( fd, offset, SEEK_CUR ); +#else lseek( fd, offset, SEEK_CUR ); +#endif bEos = false; } @@ -108,7 +116,11 @@ void Bu::File::setPos( Bu::size pos ) if( fd < 0 ) throw FileException("File not open."); +#ifdef USE_64BIT_IO + lseek64( fd, pos, SEEK_SET ); +#else lseek( fd, pos, SEEK_SET ); +#endif bEos = false; } @@ -117,7 +129,7 @@ void Bu::File::setPosEnd( Bu::size pos ) if( fd < 0 ) throw FileException("File not open."); - lseek( fd, pos, SEEK_END ); + lseek64( fd, pos, SEEK_END ); bEos = false; } diff --git a/src/stable/myriad.cpp b/src/stable/myriad.cpp index 7246df3..4f65583 100644 --- a/src/stable/myriad.cpp +++ b/src/stable/myriad.cpp @@ -84,8 +84,9 @@ void Bu::Myriad::sync() void Bu::Myriad::initialize() { MutexLocker mLock( mHeader ); + lFreeBlocks.clear(); sStore.setPosEnd( 0 ); - int iSize = sStore.tell(); + Bu::size iSize = sStore.tell(); sStore.setPos( 0 ); unsigned char buf[4]; @@ -131,8 +132,11 @@ void Bu::Myriad::initialize() { pFakeHdr->aBlocks.append( j ); } - - bsBlockUsed.setSize( iBlocks, true ); + +// sio << "Blocks: " << iBlocks << " (size = " << iSize << "/" << iBlockSize +// << ")" << sio.nl; + Bu::BitString bsBlockUsed( iBlocks, false ); + bsBlockUsed.clear(); // bool bCanSkip = false; // Can skip around, post initial header stream i/o MyriadStream *pIn = new MyriadStream( *this, pFakeHdr ); @@ -174,12 +178,21 @@ void Bu::Myriad::initialize() } delete pIn; - //sio << "Myriad: Blocks used: " << bsBlockUsed.toString() << sio.nl; + for( int j = 0; j < iBlocks; j++ ) + { + if( bsBlockUsed.getBit( j ) == false ) + { +// sio << "Preinitialized block " << j << " is free." << sio.nl; + lFreeBlocks.append( j ); + } + } +// sio << "Myriad: Blocks used: " << bsBlockUsed.toString() << sio.nl; } void Bu::Myriad::initialize( int iBlockSize, int iPreAllocate ) { MutexLocker mLock( mHeader ); + lFreeBlocks.clear(); for( StreamArray::iterator i = aStreams.begin(); i; i++ ) { @@ -207,7 +220,7 @@ void Bu::Myriad::initialize( int iBlockSize, int iPreAllocate ) //sio << "Myriad: iHeaderSize=" << iHeaderSize << ", iBlockSize=" // << iBlockSize << ", iHeaderBlocks=" << iHeaderBlocks << sio.nl; - bsBlockUsed.setSize( iPreAllocate, true ); +// bsBlockUsed.setSize( iPreAllocate, true ); iUsed++; char *pBlock = new char[iBlockSize]; @@ -255,10 +268,16 @@ void Bu::Myriad::initialize( int iBlockSize, int iPreAllocate ) pStr->iSize = iHeaderSize; for( int j = 0; j < iHeaderBlocks; j++ ) { +// sio << "Started block " << j << " is header." << sio.nl; pStr->aBlocks.append( j ); - bsBlockUsed.setBit( j ); +// bsBlockUsed.setBit( j ); iUsed++; } + for( int j = iHeaderBlocks; j < this->iBlocks; j++ ) + { +// sio << "Started block " << j << " is free." << sio.nl; + lFreeBlocks.append( j ); + } aStreams.append( pStr ); @@ -302,7 +321,7 @@ void Bu::Myriad::updateHeader() // sio << "Myriad: updateHeader: Appending block " << iBlock // << " to header." << sio.nl; aStreams[0]->aBlocks.append( iBlock ); - bsBlockUsed.setBit( iBlock ); +// bsBlockUsed.setBit( iBlock ); iUsed++; iHeaderSize += 4; iNewBlocks = blkDiv( iHeaderSize, iBlockSize ); @@ -361,7 +380,7 @@ int Bu::Myriad::createStream( int iPreAllocate ) int iFreeBlock = findEmptyBlock(); // sio << "Myriad: Adding block " << iFreeBlock << sio.nl; pStr->aBlocks.append( iFreeBlock ); - bsBlockUsed.setBit( iFreeBlock ); +// bsBlockUsed.setBit( iFreeBlock ); iUsed++; } @@ -408,7 +427,7 @@ int Bu::Myriad::createStreamWithId( int iId, int iPreAllocate ) int iFreeBlock = findEmptyBlock(); // sio << "Myriad: Adding block " << iFreeBlock << sio.nl; pStr->aBlocks.append( iFreeBlock ); - bsBlockUsed.setBit( iFreeBlock ); +// bsBlockUsed.setBit( iFreeBlock ); iUsed++; } @@ -422,26 +441,15 @@ int Bu::Myriad::findEmptyBlock() { bHeaderChanged = true; - for( int j = 0; j < bsBlockUsed.getSize(); j++ ) + if( lFreeBlocks.isEmpty() ) { - if( bsBlockUsed.getBit( j ) == false ) - return j; + sStore.setSize( (iBlocks+1)*(Bu::size)iBlockSize ); + return iBlocks++; + } + else + { + return lFreeBlocks.dequeue(); } -// sio << "Myriad: findEmptyBlock(): No empty blocks, adding new one." << sio.nl; - - bsBlockUsed.setSize( bsBlockUsed.getSize()+1, false ); - /* - sStore.setPos( iBlockSize*iBlocks ); - - char *pBlock = new char[iBlockSize]; - memset( pBlock, 0, iBlockSize ); - sStore.write( pBlock, iBlockSize ); - delete[] pBlock; - */ - - sStore.setSize( (iBlocks+1)*iBlockSize ); - - return iBlocks++; } void Bu::Myriad::deleteStream( int iId ) @@ -461,7 +469,8 @@ void Bu::Myriad::deleteStream( int iId ) Stream *pStream = *i; for( BlockArray::iterator j = pStream->aBlocks.begin(); j; j++ ) { - bsBlockUsed.setBit( *j, false ); + lFreeBlocks.append( *j ); +// bsBlockUsed.setBit( *j, false ); iUsed--; } aStreams.erase( i ); @@ -536,11 +545,11 @@ int Bu::Myriad::getNumUsedBlocks() return iUsed; } -int Bu::Myriad::getTotalUsedBytes() +Bu::size Bu::Myriad::getTotalUsedBytes() { MutexLocker mLock( mHeader ); - int iTotalSize = 0; + Bu::size iTotalSize = 0; for( StreamArray::iterator i = aStreams.begin(); i; i++ ) { iTotalSize += (*i)->iSize; @@ -548,23 +557,23 @@ int Bu::Myriad::getTotalUsedBytes() return iTotalSize; } -int Bu::Myriad::getTotalUnusedBytes() +Bu::size Bu::Myriad::getTotalUnusedBytes() { MutexLocker mLock( mHeader ); - int iTotalSize = (iBlocks-iUsed)*iBlockSize; + Bu::size iTotalSize = (iBlocks-iUsed)*iBlockSize; for( StreamArray::iterator i = aStreams.begin(); i; i++ ) { - iTotalSize += iBlockSize - ((*i)->iSize%iBlockSize); + iTotalSize += iBlockSize - ((Bu::size)(*i)->iSize%iBlockSize); } return iTotalSize; } -int Bu::Myriad::getTotalUnusedBytes( int iFakeBlockSize ) +Bu::size Bu::Myriad::getTotalUnusedBytes( int iFakeBlockSize ) { MutexLocker mLock( mHeader ); - int iTotalSize = (iBlocks-iUsed)*iFakeBlockSize; + Bu::size iTotalSize = (iBlocks-iUsed)*iFakeBlockSize; for( StreamArray::iterator i = aStreams.begin(); i; i++ ) { iTotalSize += iFakeBlockSize - ((*i)->iSize%iFakeBlockSize); @@ -592,7 +601,7 @@ Bu::Myriad::Block *Bu::Myriad::getBlock( int iBlock ) // << iBlockSize*iBlock << "-" << iBlockSize*(iBlock+1) << sio.nl; Block *pBlock = new Block; pBlock->pData = new char[iBlockSize]; - sStore.setPos( iBlockSize * iBlock ); + sStore.setPos( iBlockSize * (Bu::size)iBlock ); sStore.read( pBlock->pData, iBlockSize ); pBlock->bChanged = false; pBlock->iBlockIndex = iBlock; @@ -623,7 +632,7 @@ void Bu::Myriad::syncBlock( Block *pBlock ) if( pBlock->bChanged ) { // sio << "Myriad: - Block changed, writing back to stream." << sio.nl; - sStore.setPos( iBlockSize * pBlock->iBlockIndex ); + sStore.setPos( iBlockSize * (Bu::size)pBlock->iBlockIndex ); sStore.write( pBlock->pData, iBlockSize ); pBlock->bChanged = false; } @@ -635,8 +644,8 @@ int Bu::Myriad::streamAddBlock( Stream *pStream ) int iBlock = findEmptyBlock(); pStream->aBlocks.append( iBlock ); - bsBlockUsed.setBit( iBlock ); - bHeaderChanged = true; +// bsBlockUsed.setBit( iBlock ); +// bHeaderChanged = true; iUsed++; return iBlock; } @@ -655,11 +664,12 @@ void Bu::Myriad::setStreamSize( Stream *pStream, long iSize ) for( int iNewSize = pStream->aBlocks.getSize()*iBlockSize; iNewSize-iBlockSize > iSize; iNewSize -= iBlockSize ) { - if( bsBlockUsed.getBit( pStream->aBlocks.last() ) ) +// if( bsBlockUsed.getBit( pStream->aBlocks.last() ) ) iUsed--; - else - sio << "Unused block used in stream? " << pStream->aBlocks.last() << sio.nl; - bsBlockUsed.setBit( pStream->aBlocks.last(), false ); +// else +// sio << "Unused block used in stream? " << pStream->aBlocks.last() << sio.nl; + lFreeBlocks.enqueue( pStream->aBlocks.last() ); +// bsBlockUsed.setBit( pStream->aBlocks.last(), false ); pStream->aBlocks.eraseLast(); } pStream->iSize = iSize; @@ -674,8 +684,8 @@ void Bu::Myriad::setStreamSize( Stream *pStream, long iSize ) //streamAddBlock( pStream ); int iBlock = findEmptyBlock(); pStream->aBlocks.append( iBlock ); - bsBlockUsed.setBit( iBlock ); - bHeaderChanged = true; +// bsBlockUsed.setBit( iBlock ); +// bHeaderChanged = true; iUsed++; } pStream->iSize = iSize; @@ -712,8 +722,13 @@ bool Bu::Myriad::isMyriad( Bu::Stream &sStore, uint8_t &uTmp ) return true; } -const Bu::BitString &Bu::Myriad::getBlocksUsed() const +const Bu::BitString Bu::Myriad::getBlocksUsed() const { - return bsBlockUsed; + Bu::BitString bs( iBlocks, false ); + for( int j = 0; j < iBlocks; j++ ) + bs.setBit( j ); + for( IndexList::const_iterator i = lFreeBlocks.begin(); i; i++ ) + bs.setBit( *i, false ); + return bs; } diff --git a/src/stable/myriad.h b/src/stable/myriad.h index 80b5c2b..6b1db41 100644 --- a/src/stable/myriad.h +++ b/src/stable/myriad.h @@ -14,6 +14,7 @@ #include "bu/array.h" #include "bu/hash.h" #include "bu/mutex.h" +#include "bu/extratypes.h" namespace Bu { @@ -139,9 +140,9 @@ namespace Bu int getBlockSize(); int getNumBlocks(); int getNumUsedBlocks(); - int getTotalUsedBytes(); - int getTotalUnusedBytes(); - int getTotalUnusedBytes( int iFakeBlockSize ); + Bu::size getTotalUsedBytes(); + Bu::size getTotalUnusedBytes(); + Bu::size getTotalUnusedBytes( int iFakeBlockSize ); /** * Syncronize the header data, etc. with the storage stream. It's not @@ -163,7 +164,7 @@ namespace Bu */ static bool isMyriad( Bu::Stream &sStore ); - const Bu::BitString &getBlocksUsed() const; + const Bu::BitString getBlocksUsed() const; private: /** @@ -219,7 +220,9 @@ namespace Bu int iBlockSize; int iBlocks; int iUsed; - Bu::BitString bsBlockUsed; + typedef Bu::List IndexList; + IndexList lFreeBlocks; +// Bu::BitString bsBlockUsed; StreamArray aStreams; typedef Bu::Hash BlockHash; BlockHash hActiveBlocks; diff --git a/src/tests/bigmyriad.cpp b/src/tests/bigmyriad.cpp new file mode 100644 index 0000000..6661bf1 --- /dev/null +++ b/src/tests/bigmyriad.cpp @@ -0,0 +1,25 @@ +#include +#include +#include + +int main() +{ + Bu::File f("big.myr", Bu::File::Read|Bu::File::Write|Bu::File::Create ); + Bu::Myriad m( f, 2048 ); + + char *buf = new char[1024*1024*10]; + memset( buf, 0, 1024*1024*10 ); + + for( int j = 0; j < 250; j++ ) + { + m.openStream( m.createStream() ).write( buf, 1024*1024*10 ); +// m.sync(); + printf("\r%03d%%", (j+1)*100/250 ); + fflush( stdout ); + } + + printf("\n\n"); + + return 0; +} + -- cgit v1.2.3