1 /* 2 * Copyright (C) 2002 - David W. Durham 3 * 4 * This file is part of ReZound, an audio editing application, but 5 * could be used for other applications which could use the PoolFile 6 * class's functionality. 7 * 8 * PoolFile is free software; you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License as published 10 * by the Free Software Foundation; either version 2 of the License, 11 * or (at your option) any later version. 12 * 13 * PoolFile is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 21 */ 22 23 #ifndef __TPoolFile_H__ 24 #define __TPoolFile_H__ 25 26 #include "../../config/common.h" 27 28 #include <stddef.h> 29 #include <stdint.h> 30 31 #include <string> 32 #include <map> 33 #include <vector> 34 #include <queue> 35 #include <set> 36 37 #include <CMutex.h> 38 #include <CRWMutex.h> 39 40 #include "CMultiFile.h" 41 42 template<class pool_element_t,class pool_file_t> class TStaticPoolAccesser; 43 44 // ??? perhaps rename the word 'pool' it's more of a line that doesn't change order.. pool implies almost that the order doesnt matter 45 46 /* 47 - This class maintains a file as blocks of large typed arrays called pools. 48 49 - The two template parametes are the logical address space type and the 50 physical address space type. Both are address space IN BYTES. 51 - !!!NOTE!!! they must be unsigned types 52 53 - Use createPool to create pools giving it a name and the type of data being 54 stored in the pool. 55 56 - Use getPoolAccesser to retrieve a pool accesser object to manipulate the 57 size of and data within a pool. 58 */ 59 template<class _l_addr_t,class _p_addr_t> class TPoolFile 60 { 61 public: 62 typedef _l_addr_t l_addr_t; 63 typedef _p_addr_t p_addr_t; // is written to file 64 typedef uint32_t alignment_t; // is written to file 65 typedef uint32_t blocksize_t; // is written to file 66 typedef size_t poolId_t; 67 68 69 // formatSignature MUST be an 8 byte (not counting an unncessary null terminator) signature to look for when opening a file 70 TPoolFile(const blocksize_t maxBlockSize=32768,const char *formatSignature="DavyBlox"); 71 explicit TPoolFile(const TPoolFile<l_addr_t,p_addr_t> &src); //INVALID 72 virtual ~TPoolFile(); 73 74 // open/close methods 75 void openFile(const string _filename,const bool canCreate=true); 76 77 // removes all files that would be generated if a pool file was opened with the given name 78 // it cleans up the .SAT[12] files 79 static void removeFile(const string filename); 80 81 const bool isOpen() const; 82 83 void copyToFile(const string filename); 84 85 const string getFilename() const; 86 void rename(const string newFilename); 87 88 void flushData(); 89 90 // for now, since insertSpace doesn't backupSAT for speed reasons, I need 91 // to be able to call it in case of a crash after I'm finished inserting 92 void backupSAT(); 93 94 void closeFile(const bool defrag,const bool removeFile); 95 96 97 98 // mutex methods 99 void sharedLock() const; 100 const bool sharedTrylock() const; 101 void sharedUnlock() const; 102 const size_t getSharedLockCount() const; 103 104 void exclusiveLock() const; 105 const bool exclusiveTrylock() const; 106 void exclusiveUnlock() const; 107 const bool isExclusiveLocked() const; 108 109 110 // accesser methods 111 template<class pool_element_t> TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > getPoolAccesser(const poolId_t poolId); 112 template<class pool_element_t> TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > getPoolAccesser(const string poolName); 113 114 template<class pool_element_t> const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > getPoolAccesser(const poolId_t poolId) const; 115 template<class pool_element_t> const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > getPoolAccesser(const string poolName) const; 116 117 // these methods can be used to read raw data from a pool disregarding the alignment of the pool 118 l_addr_t readPoolRaw(const poolId_t poolId,void *buffer,l_addr_t readSize,l_addr_t pos=0); 119 l_addr_t readPoolRaw(const string poolName,void *buffer,l_addr_t readSize,l_addr_t pos=0); 120 121 // these methods can be used to write raw data to a pool disregarding the alignment of the pool (the pool must already be the correct size before writing) 122 l_addr_t writePoolRaw(const poolId_t poolId,void *buffer,l_addr_t writeSize,l_addr_t pos=0); 123 l_addr_t writePoolRaw(const string poolName,void *buffer,l_addr_t writeSize,l_addr_t pos=0); 124 125 126 // pool information/managment methods 127 const l_addr_t getPoolSize(poolId_t poolId) const; 128 const l_addr_t getPoolSize(const string poolName) const; 129 130 template<class pool_element_t> TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > createPool(const string poolName,const bool throwOnExistance=true); 131 132 void removePool(const poolId_t poolId); 133 void removePool(const string poolName,const bool throwIfNotExists=true); 134 void clear(); // removes all pools 135 136 const bool containsPool(const string poolName) const; 137 138 // ??? these may not be ncessary to have as public.. then remove the one that takes a string 139 const alignment_t getPoolAlignment(const poolId_t poolId) const; 140 const alignment_t getPoolAlignment(const string poolName) const; 141 142 // these can be used to change the alignment of a pool, but the pool MUST be empty when this operation is performed 143 void setPoolAlignment(const poolId_t poolId,size_t alignment); 144 void setPoolAlignment(const string poolName,size_t alignment); 145 146 void swapPools(const poolId_t poolId1,const poolId_t poolId2); 147 void swapPools(const string poolName1,const string poolName2); 148 149 const size_t getPoolIndexCount() const; // to iterate through the pools use this method and getPoolIdByIndex(); the indexes will access the pools in alphabetical order 150 151 const poolId_t getPoolIdByName(const string poolName) const; 152 const poolId_t getPoolIdByIndex(const size_t index) const; // where index is 0 to getPoolIndexCount()-1 153 const string getPoolNameById(const poolId_t poolId) const; 154 const bool isValidPoolId(const poolId_t poolId) const; 155 156 void clearPool(const poolId_t poolId); 157 void clearPool(const string poolName); 158 159 const p_addr_t getFileSize() const; 160 161 162 // methods to make sure that the pool file is consistant 163 void verifyAllBlockInfo(bool expectContinuousPhysicalAllocs=false); 164 void printSAT() const; 165 166 // returns whether it did anything 167 bool defrag(); 168 169 #ifndef TESTING_TPOOLFILE 170 private: 171 #endif 172 173 struct RLogicalBlock; 174 175 // ??? is there some way to say any type T but only L and P being l_addr_t and p_addr_t 176 template <class T,class P> friend class TPoolAccesser; 177 template <class T,class P> friend class TStaticPoolAccesser; 178 179 friend struct RLogicalBlock; 180 181 mutable CRWMutex structureMutex; 182 183 mutable CMutex accesserInfoMutex; 184 185 const char *formatSignature; 186 187 const blocksize_t maxBlockSize; 188 const l_addr_t maxLogicalAddress; 189 const p_addr_t maxPhysicalAddress; 190 191 bool opened; 192 string filename,SATFilename; 193 194 CMultiFile blockFile; 195 196 struct RPoolInfo 197 { 198 l_addr_t size; 199 alignment_t alignment; 200 bool isValid; // false if the pool has been removed, but the poolId hasn't been reused yet 201 202 RPoolInfo(); 203 RPoolInfo(const l_addr_t _size,const alignment_t _alignment,const bool _isValid); 204 RPoolInfo(const RPoolInfo &src); 205 RPoolInfo &operator=(const RPoolInfo &src); 206 207 void writeToFile(CMultiFile *f,CMultiFile::RHandle &multiFileHandle) const; 208 void readFromFile(CMultiFile *f,CMultiFile::RHandle &multiFileHandle,int formatVersion); 209 }; 210 211 map<const string,poolId_t> poolNames; // the integer data indexes into pools and SAT given a name string key, which is the 'poolId' 212 vector<RPoolInfo> pools; // this list is parallel to SAT 213 vector<vector<RLogicalBlock> > SAT; // the outer vector is parallel to pools; note, the inner vector is kept sorted by logicalStart, so we shan't modify logicalStart such that it becomes out of order 214 215 216 // Misc 217 void setup(); 218 void init(const bool createInitialCachedBlocks=true); 219 const bool prvGetPoolIdByName(const string poolName,poolId_t &poolId) const; 220 const p_addr_t getProceedingPoolSizes(const poolId_t poolId) const; 221 const blocksize_t getMaxBlockSizeFromAlignment(const alignment_t alignment) const; 222 void writeMetaData(CMultiFile *f,bool writeSAT); 223 void prvCreatePool(const string poolName,const alignment_t alignment,const bool throwOnExistance=true,const bool useOldPoolIds=true); 224 void addPool(const poolId_t poolId,const alignment_t alignment,bool isValid); 225 const string getPoolDescription(const poolId_t poolId) const; 226 void writeDirtyIndicator(const bool dirty,CMultiFile *f); 227 void appendNewSAT(); 228 229 void offsetLogicalAddressSpace(typename vector<RLogicalBlock>::iterator first,typename vector<RLogicalBlock>::iterator end,const l_addr_t offset,int add_or_sub); 230 231 // Structural Integrity Methods 232 CMultiFile SATFiles[2]; // for now, I just use the same IO module for storing the SATs as well as the data... when 64bit FS is normal.. there won't be a difference 233 uint8_t whichSATFile; 234 void openSATFiles(const bool mustExist=false); 235 void closeSATFiles(const bool removeFiles=true); 236 void writeWhichSATFile(); 237 void writeSATToFile(CMultiFile *f,const p_addr_t writeWhere); 238 void restoreSAT(int formatVersion); 239 void buildSATFromFile(CMultiFile *f,const p_addr_t readWhere,int formatVersion); 240 241 // SAT operations 242 const size_t findSATBlockContaining(const poolId_t poolId,const l_addr_t where,bool &atStartOfBlock) const; 243 244 static const bool isInWindow(const p_addr_t start,const p_addr_t end,const p_addr_t windowStart,const p_addr_t windowEnd); 245 void joinAllAdjacentBlocks(); 246 void joinAdjacentBlocks(const poolId_t poolId); 247 void joinAdjacentBlocks(const poolId_t poolId,const size_t firstBlockIndex,const size_t blockCount); 248 249 // Pool modification 250 void insertSpace(const poolId_t poolId,const l_addr_t peWhere,const l_addr_t peCount); 251 void removeSpace(const poolId_t poolId,const l_addr_t peWhere,const l_addr_t peCount); 252 // moves peCount pool-elements of data from the srcPoolId at peSrcWhere to the destPoolId at peDestWhere 253 void moveData(const poolId_t destPoolId,const l_addr_t peDestWhere,const poolId_t srcPoolId,const l_addr_t peSrcWhere,const l_addr_t peCount); 254 255 // Pool Data Access 256 struct RCachedBlock 257 { 258 poolId_t poolId; 259 void *buffer; 260 size_t referenceCount; 261 bool dirty; 262 l_addr_t logicalStart; 263 blocksize_t size; 264 265 RCachedBlock(const blocksize_t maxBlockSize); 266 virtual ~RCachedBlock(); 267 bool containsAddress(l_addr_t where) const; 268 void init(const poolId_t _poolId,const l_addr_t _logicalStart,const blocksize_t _size); 269 }; 270 271 // 'char', just to have something since the list needs to hold pointers to all types of TStaticAccesser instantiation 272 typedef TStaticPoolAccesser<char,TPoolFile<l_addr_t,p_addr_t> > CGenericPoolAccesser; 273 vector<const CGenericPoolAccesser *> accessers; 274 275 deque<RCachedBlock *> unusedCachedBlocks; // available, not caching anything 276 set<RCachedBlock *> unreferencedCachedBlocks; // is caching data, but is not currently referenced by any PoolAccesser object 277 set<RCachedBlock *> activeCachedBlocks; // is caching data, and is currently being used by one or more PoolAccesser objects 278 279 280 template<class pool_element_t> void cacheBlock(const l_addr_t byteWhere,const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > *accesser); 281 template<class pool_element_t> void invalidateAccesser(const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > *accesser); 282 void invalidateCachedBlock(RCachedBlock *cachedBlock); 283 template<class pool_element_t> void unreferenceCachedBlock(const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > *accesser); 284 void invalidateAllCachedBlocks(bool allPools=true,poolId_t poolId=0); 285 template<class pool_element_t> void addAccesser(const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > *accesser); 286 template<class pool_element_t> void removeAccesser(const TStaticPoolAccesser<pool_element_t,TPoolFile<l_addr_t,p_addr_t> > *accesser); 287 288 bool physicallyMoveBlock(RLogicalBlock &block,p_addr_t physicallyWhere,map<p_addr_t,p_addr_t> &physicalBlockList,int8_t *temp); 289 290 struct RLogicalBlock 291 { 292 l_addr_t logicalStart; // key 293 blocksize_t size; // data 294 p_addr_t physicalStart; // data 295 296 RLogicalBlock(); 297 RLogicalBlock(const l_addr_t _logicalStart); 298 RLogicalBlock(const RLogicalBlock &src); 299 RLogicalBlock &operator=(const RLogicalBlock &src); 300 301 const bool operator==(const RLogicalBlock &src) const; 302 const bool operator!=(const RLogicalBlock &src) const { return !operator==(src); } 303 const bool operator>(const RLogicalBlock &src) const { return !operator<=(src); } 304 const bool operator>=(const RLogicalBlock &src) const { return !operator<(src); } 305 const bool operator<(const RLogicalBlock &src) const; 306 const bool operator<=(const RLogicalBlock &src) const { return operator<(src) || operator==(src); } 307 308 const size_t getMemSize(int formatVersion); 309 void writeToMem(uint8_t *mem,size_t &offset) const; 310 void readFromMem(const uint8_t *mem,size_t &offset,int formatVersion); 311 312 void print() const; 313 }; 314 315 316 class CPhysicalAddressSpaceManager 317 { 318 public: 319 CPhysicalAddressSpaceManager(CMultiFile &file); 320 321 // returns the addr of the new physical block 322 p_addr_t alloc(blocksize_t size); 323 // returns the addr of the new (right side) physical block created by the split 324 p_addr_t split_block(p_addr_t addr,blocksize_t newBlockStartsAt); 325 // returns the new addr of the physical block 326 p_addr_t partial_free(p_addr_t addr,p_addr_t newAddr,blocksize_t newSize); 327 void free(p_addr_t addr); 328 void free_all(); 329 330 // allocate space by appending space to the file 331 p_addr_t appendAlloc(const p_addr_t size); 332 333 334 // if addr1 is followed immediately by addr2 then this method will join the blocks 335 // together, making only addr1 an allocated block of a now larger size 336 void join_blocks(p_addr_t addr1,p_addr_t addr2); 337 338 void buildFromSAT(const vector<vector<RLogicalBlock> > &SAT); 339 340 void make_file_smallest(); 341 342 343 void verify(bool expectContinuousPhysicalAllocs=false); 344 void print() const; 345 346 // only used by verifyAllBlockInfo isAlloced(p_addr_t addr)347 bool isAlloced(p_addr_t addr) const { return alloced.find(addr)!=alloced.end(); } getAllocedSize(p_addr_t addr)348 blocksize_t getAllocedSize(p_addr_t addr) const { return isAlloced(addr) ? (alloced.find(addr)->second) : 0; } 349 350 // just a utility function for verification 351 static bool overlap(p_addr_t addr1,p_addr_t size1,p_addr_t addr2,p_addr_t size2); 352 353 354 // ??? these should be private, they're only called by TPoolFile::physicallyMoveBlock, but I can't figure out the friend syntax 355 void set_file_size(const p_addr_t newSize); 356 const p_addr_t get_file_size() const; 357 358 #ifndef TESTING_TPOOLFILE 359 private: 360 #endif 361 362 CMultiFile &file; 363 364 // physical address space: [...XXXX...X....XXXXX...XX...XXXX....X...] 365 // X's are allocated .'s are holes 366 // 367 // alloced is indexed by the start of the allocated block, the key, and its data is the size of the block 368 // holes is indexed by the start of an unalloced block, the key, and its data is the size of the unallocated block 369 // holeSizeIndex is indexed by the size a hole, the key, and its data is an iterator into holes for that unallocated block 370 371 // start, size 372 typedef map<p_addr_t, blocksize_t> alloced_t; 373 alloced_t alloced; 374 375 // start, size 376 typedef map<p_addr_t, p_addr_t> holes_t; 377 holes_t holes; 378 379 // size, iterator into holes 380 typedef multimap<p_addr_t,typename holes_t::iterator> holeSizeIndex_t; 381 holeSizeIndex_t holeSizeIndex; 382 383 typename holeSizeIndex_t::iterator findHoleSizeIndexEntry(const p_addr_t size,const p_addr_t addr); 384 385 // used for optimizing repeated consecutive appends 386 // know these two things tells us if there will be no hole to fit a new alloc into 387 p_addr_t lastAllocSize; 388 bool lastAllocAppended; 389 390 } pasm; 391 392 393 // inserts i, into container, c, in its sorted location 394 template<class C,class I> static void sortedInsert(C &c,const I &i); 395 396 // read/write a string to a CMultiFile 397 static void readString(string &s,CMultiFile *f,CMultiFile::RHandle &multiFileHandle); 398 static void writeString(const string &s,CMultiFile *f,CMultiFile::RHandle &multiFileHandle); 399 400 }; 401 402 #define __TPoolFile_H__CPP 403 #include "TPoolFile.cpp" 404 #undef __TPoolFile_H__CPP 405 406 #endif 407