>>>> +/** Compact bit-field representation class >>>> + * >>>> + * FileMap is aimed at holding UFS's internal file allocation table. >>> >>> I do not think FileMap is a compact representation of a bit-field, but >>> perhaps you meant something else? Consider this clarification: >>> >>> /** A bitmap used for managing UFS StoreEntry "file numbers". >>> * >>> * Nth bit represents whether file number N is used. >>> * The map automatically grows to hold up to 2^24 bits. >>> * New bit is "off" or zero by default, representing unused fileno. >>> */ >> >> Thanks. Done. >> >>>> + /// Test whether the num-th bit in the FileMap is set >>>> + int testBit(int num) const; >>> >>> I would rename that to isUsed(), isSet() or similar and return bool >>> instead of int, but that is not a big deal. >> >> Leaving as-is not to grow the scope. > > > SourceLayout refactoring does include code style updates to the current > guideline requirements. So I'm seconding that bool type usage please, if not > the name part.
Done the type changing. > in FileMap.h: > * max_n_files would be best called capacity_ or currentCapacity_ > internally. Should be unsigned too if that does not clash with sfileno > comparisons. It clashes. Changed to sfileno capacity_ > * n_files_in_map would be best called something_ internally. Also this > should be unsigned. changed to sfileno used_slots_ > * please use the available sfileno type instead of "int" for all variables > representing the file number. Ok. > in FileMap.cc: > * please change the squid.h include to config.h and add other minimal > includes as required to minimize the dependency. Done. > * the allocate() loop iterators count and bit can be defined in their loop > definitions. Done. > * in allocate() "debugs(8, 3, HERE << "growing fileMap");" can die, it is > covered by the message inside grow(). Done. > in UFSSwapDir::mapBitReset > * s/calling resetting/calling clearBit/ > * s/resetting doesn't/clearBit doesn't/ Done in a slightly different way. > NP: also this would be a good time to add that bounds checking and ensure > the n_files_in_map is correctly maintained by its owner class. Especially > since its a private. This goes for both setBit() and checkBit(). The return > value from setBit() appears not to be used anywhere, so both can change to > bool and report back success/fail to the caller in case it is ever needed. This would go in the "improvements" part. Also, there is a bit of layering breaking in UFSSwapDir where it has its own view of the map, including e.g. keeping a cached "last allocated" index to speed allocations up. I'd prefer not to address these at this time, but I could add a TODO to remind about them if you wish. V3 attached. -- /kinkie
=== added file 'src/FileMap.h' --- src/FileMap.h 1970-01-01 00:00:00 +0000 +++ src/FileMap.h 2011-11-27 18:04:58 +0000 @@ -0,0 +1,102 @@ +/* + * FileMap.h + * + * DEBUG: section 08 Swap File Bitmap + * AUTHOR: Harvest Derived + * + * SQUID Web Proxy Cache http://www.squid-cache.org/ + * ---------------------------------------------------------- + * + * Squid is the result of efforts by numerous individuals from + * the Internet community; see the CONTRIBUTORS file for full + * details. Many organizations have provided support for Squid's + * development; see the SPONSORS file for full details. Squid is + * Copyrighted (C) 2001 by the Regents of the University of + * California; see the COPYRIGHT file for full details. Squid + * incorporates software developed and/or copyrighted by other + * sources; see the CREDITS file for full details. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. + */ + +#ifndef FILEMAP_H_ +#define FILEMAP_H_ + +#include "typedefs.h" + +/** A bitmap used for managing UFS StoreEntry "file numbers". + * + * Nth bit represents whether file number N is used. + * The map automatically grows to hold up to 2^24 bits. + * New bit is "off" or zero by default, representing unused fileno. + * TODO: consider using std::bitset instead. + */ +class FileMap +{ +public: + FileMap(); + ~FileMap(); + + /** Set the num-th bit in the FileMap + * + * \warning FileMap's backing storage will be extended as needed to + * hold the representation, but if the bit is already set + * it will break the file number accounting, so the caller must + * ensure that setBit is only called if the bit is not already set, + * by using testBit on it before. + */ + bool setBit(sfileno num); + + /// Test whether the num-th bit in the FileMap is set + bool testBit(sfileno num) const; + + /** Clear the num-th bit in the FileMap + * + * \warning that clearBit doesn't do any bounds checking, nor it + * checks that the bit is set before clearing. The caller will have + * to ensure that both are true using testBit before clearing. + */ + void clearBit(sfileno num); + + /** locate an unused slot in the FileMap, possibly at or after position suggestion + * + * Obtain the location of an unused slot in the FileMap, + * growing it if needed. + * The suggestion is only an advice; there is no guarantee + * that it will be followed. + */ + sfileno allocate(sfileno suggestion); + + /// return the max number of slots in the FileMap + int capacity() const {return capacity_;} + + /// return the number of used slots in the FileMap + int numFilesInMap() const {return used_slots_;} +private: + /// grow the FileMap (size is doubled each time, up to 2^24 bits) + void grow(); + FileMap(const FileMap &); //no copying + FileMap& operator=(const FileMap &); //no assignments + + /// max number of files which can be tracked in the current store + sfileno capacity_; + /// used slots in the map + unsigned int used_slots_; + /// number of "long ints" making up the filemap + unsigned int nwords; + unsigned long *bitmap; +}; + +#endif /* FILEMAP_H_ */ === modified file 'src/Makefile.am' --- src/Makefile.am 2011-11-04 12:30:43 +0000 +++ src/Makefile.am 2011-11-26 09:58:30 +0000 @@ -306,40 +306,41 @@ enums.h \ err_type.h \ err_detail_type.h \ errorpage.cc \ errorpage.h \ ETag.cc \ ETag.h \ event.cc \ event.h \ EventLoop.h \ EventLoop.cc \ external_acl.cc \ ExternalACL.h \ ExternalACLEntry.cc \ ExternalACLEntry.h \ FadingCounter.h \ FadingCounter.cc \ fd.cc \ fde.cc \ fde.h \ + FileMap.h \ filemap.cc \ forward.cc \ forward.h \ fqdncache.cc \ ftp.cc \ Generic.h \ globals.h \ gopher.cc \ helper.cc \ helper.h \ HelperChildConfig.h \ HelperChildConfig.cc \ hier_code.h \ HierarchyLogEntry.h \ $(HTCPSOURCE) \ http.cc \ http.h \ HttpStatusCode.h \ HttpStatusLine.cc \ HttpStatusLine.h \ @@ -1117,40 +1118,41 @@ ## HttpHdrContRange.cc \ ## HttpHdrCc.cc \ ## HttpHdrRange.cc \ ## HttpHdrSc.cc \ ## HttpHdrScTarget.cc \ ## Packer.cc \ ## StatHist.cc \ ## String.cc \ ## ## disk.cc \ ## fs/libfs.la \ tests_testACLMaxUserIP_SOURCES= \ cbdata.cc \ ClientInfo.h \ ConfigOption.cc \ ConfigParser.cc \ DiskIO/ReadRequest.cc \ DiskIO/WriteRequest.cc \ ETag.cc \ event.cc \ + FileMap.h \ filemap.cc \ HelperChildConfig.h \ HelperChildConfig.cc \ HttpHeader.cc \ HttpHeaderTools.cc \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrSc.cc \ HttpHdrScTarget.cc \ HttpMsg.cc \ HttpRequestMethod.cc \ int.cc \ list.cc \ mem_node.cc \ Packer.cc \ Parsing.cc \ SquidMath.cc \ @@ -1279,40 +1281,41 @@ clientStream.cc \ ConfigOption.cc \ ConfigParser.cc \ CpuAffinityMap.cc \ CpuAffinityMap.h \ CpuAffinitySet.cc \ CpuAffinitySet.h \ $(DELAY_POOL_SOURCE) \ $(DISKIO_SOURCE) \ disk.cc \ dlink.h \ dlink.cc \ $(DNSSOURCE) \ errorpage.cc \ ETag.cc \ event.cc \ external_acl.cc \ ExternalACLEntry.cc \ fd.cc \ fde.cc \ + FileMap.h \ filemap.cc \ forward.cc \ fqdncache.cc \ ftp.cc \ gopher.cc \ hier_code.h \ helper.cc \ HelperChildConfig.h \ HelperChildConfig.cc \ $(HTCPSOURCE) \ http.cc \ HttpBody.cc \ HttpHeader.cc \ HttpHeaderTools.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ @@ -1429,40 +1432,41 @@ tests_testCacheManager_LDFLAGS = $(LIBADD_DL) tests_testCacheManager_DEPENDENCIES = \ $(REPL_OBJS) \ $(SQUID_CPPUNIT_LA) # tests/stub_CommIO.cc \ # tests/stub_comm.cc tests_testDiskIO_SOURCES = \ CacheDigest.cc \ cbdata.cc \ ClientInfo.h \ ConfigOption.cc \ ConfigParser.cc \ $(DELAY_POOL_SOURCE) \ $(DISKIO_SOURCE) \ disk.cc \ ETag.cc \ EventLoop.cc \ event.cc \ fd.cc \ + FileMap.h \ filemap.cc \ HttpBody.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrSc.cc \ HttpHdrScTarget.cc \ HttpHdrRange.cc \ HttpHeaderTools.cc \ HttpHeader.cc \ HttpMsg.cc \ HttpReply.cc \ HttpRequestMethod.cc \ HttpStatusLine.cc \ int.cc \ list.cc \ MemBuf.cc \ MemObject.cc \ mem_node.cc \ @@ -1595,40 +1599,41 @@ CpuAffinityMap.h \ CpuAffinitySet.cc \ CpuAffinitySet.h \ debug.cc \ $(DELAY_POOL_SOURCE) \ $(DISKIO_SOURCE) \ disk.cc \ dlink.h \ dlink.cc \ $(DNSSOURCE) \ errorpage.cc \ ETag.cc \ event.cc \ EventLoop.h \ EventLoop.cc \ external_acl.cc \ ExternalACLEntry.cc \ FadingCounter.cc \ fd.cc \ fde.cc \ + FileMap.h \ filemap.cc \ forward.cc \ fqdncache.cc \ ftp.cc \ gopher.cc \ helper.cc \ HelperChildConfig.h \ HelperChildConfig.cc \ hier_code.h \ $(HTCPSOURCE) \ http.cc \ HttpBody.cc \ HttpHeader.cc \ HttpHeaderTools.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ @@ -1783,40 +1788,41 @@ CpuAffinityMap.h \ CpuAffinitySet.cc \ CpuAffinitySet.h \ debug.cc \ $(DELAY_POOL_SOURCE) \ $(DISKIO_SOURCE) \ disk.cc \ dlink.h \ dlink.cc \ $(DNSSOURCE) \ errorpage.cc \ ETag.cc \ EventLoop.h \ EventLoop.cc \ event.cc \ external_acl.cc \ ExternalACLEntry.cc \ FadingCounter.cc \ fd.cc \ fde.cc \ + FileMap.h \ filemap.cc \ forward.cc \ fqdncache.cc \ ftp.cc \ gopher.cc \ helper.cc \ HelperChildConfig.h \ HelperChildConfig.cc \ hier_code.h \ $(HTCPSOURCE) \ http.cc \ HttpBody.cc \ HttpHeader.cc \ HttpHeaderTools.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ @@ -1969,40 +1975,41 @@ ConfigParser.cc \ CpuAffinityMap.cc \ CpuAffinityMap.h \ CpuAffinitySet.cc \ CpuAffinitySet.h \ debug.cc \ $(DELAY_POOL_SOURCE) \ $(DISKIO_SOURCE) \ disk.cc \ dlink.h \ dlink.cc \ $(DNSSOURCE) \ errorpage.cc \ ETag.cc \ event.cc \ external_acl.cc \ ExternalACLEntry.cc \ FadingCounter.cc \ fd.cc \ fde.cc \ + FileMap.h \ filemap.cc \ forward.cc \ fqdncache.cc \ ftp.cc \ gopher.cc \ helper.cc \ HelperChildConfig.h \ HelperChildConfig.cc \ hier_code.h \ $(HTCPSOURCE) \ http.cc \ HttpBody.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ HttpHdrScTarget.cc \ HttpHeader.cc \ @@ -2344,40 +2351,41 @@ tests_testHttpRequest_LDFLAGS = $(LIBADD_DL) tests_testHttpRequest_DEPENDENCIES = \ $(REPL_OBJS) \ $(SQUID_CPPUNIT_LA) ## why so many sources? well httpHeaderTools requites ACLChecklist & friends. ## first line - what we are testing. tests_testStore_SOURCES= \ CacheDigest.cc \ cbdata.cc \ ClientInfo.h \ ConfigOption.cc \ ConfigParser.cc \ $(DELAY_POOL_SOURCE) \ disk.cc \ DiskIO/ReadRequest.cc \ DiskIO/WriteRequest.cc \ ETag.cc \ event.cc \ EventLoop.cc \ + FileMap.h \ filemap.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ HttpHdrScTarget.cc \ HttpHeaderTools.cc \ HttpHeader.cc \ HttpMsg.cc \ HttpRequestMethod.cc \ int.cc \ list.cc \ mem.cc \ mem_node.cc \ MemBuf.cc \ Packer.cc \ Parsing.cc \ RemovalPolicy.cc \ @@ -2533,40 +2541,41 @@ $(SQUID_CPPUNIT_LA) tests_testUfs_SOURCES = \ tests/testUfs.cc \ tests/testMain.cc \ tests/testUfs.h \ tests/stub_cache_manager.cc \ tests/stub_client_db.cc \ tests/stub_HelperChildConfig.cc \ tests/stub_icp.cc \ tests/stub_ipc.cc \ tests/stub_MemStore.cc \ tests/stub_pconn.cc \ tests/stub_Port.cc \ tests/stub_UdsOp.cc \ tests/stub_internal.cc \ tests/stub_store_rebuild.cc \ tests/stub_store_stats.cc \ fd.cc \ disk.cc \ + FileMap.h \ filemap.cc \ HttpBody.cc \ HttpReply.cc \ HttpStatusLine.cc \ int.cc \ list.cc \ MemObject.cc \ StoreSwapLogData.cc \ StoreIOState.cc \ StoreMeta.cc \ StoreMetaMD5.cc \ StoreMetaSTD.cc \ StoreMetaSTDLFS.cc \ StoreMetaUnpacker.cc \ StoreMetaURL.cc \ StoreMetaVary.cc \ StoreFileSystem.cc \ store_io.cc \ store_swapout.cc \ store_swapmeta.cc \ @@ -2662,40 +2671,41 @@ $(top_builddir)/lib/libmiscutil.la \ $(REGEXLIB) \ $(SQUID_CPPUNIT_LIBS) \ $(SSLLIB) \ $(COMPAT_LIB) \ $(XTRA_LIBS) tests_testUfs_LDFLAGS = $(LIBADD_DL) tests_testUfs_DEPENDENCIES = \ $(SWAP_TEST_DS) tests_testRock_SOURCES = \ cbdata.cc \ CacheDigest.cc \ ConfigOption.cc \ ConfigParser.cc \ disk.cc \ ETag.cc \ EventLoop.cc \ event.cc \ fd.cc \ + FileMap.h \ filemap.cc \ HttpBody.cc \ HttpHdrCc.cc \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ HttpHdrScTarget.cc \ HttpHeader.cc \ HttpHeaderTools.cc \ HttpMsg.cc \ HttpReply.cc \ HttpRequestMethod.cc \ HttpStatusLine.cc \ int.cc \ list.cc \ mem.cc \ MemBuf.cc \ MemObject.cc \ mem_node.cc \ Packer.cc \ @@ -2791,40 +2801,41 @@ $(XTRA_LIBS) tests_testRock_LDFLAGS = $(LIBADD_DL) tests_testRock_DEPENDENCIES = \ $(SWAP_TEST_DS) tests_testCoss_SOURCES = \ tests/testCoss.cc \ tests/testMain.cc \ tests/testCoss.h \ tests/stub_cache_manager.cc \ tests/stub_client_db.cc \ tests/stub_debug.cc \ tests/stub_HelperChildConfig.cc \ tests/stub_internal.cc \ tests/stub_ipc.cc \ tests/stub_pconn.cc \ tests/stub_store_rebuild.cc \ tests/stub_store_stats.cc \ fd.cc \ disk.cc \ + FileMap.h \ filemap.cc \ HttpBody.cc \ HttpReply.cc \ HttpStatusLine.cc \ int.cc \ list.cc \ MemObject.cc \ StoreSwapLogData.cc \ StoreIOState.cc \ StoreMeta.cc \ StoreMetaMD5.cc \ StoreMetaSTD.cc \ StoreMetaSTDLFS.cc \ StoreMetaUnpacker.cc \ StoreMetaURL.cc \ StoreMetaVary.cc \ StoreFileSystem.cc \ store_io.cc \ store_swapout.cc \ store_swapmeta.cc \ @@ -2922,40 +2933,41 @@ $(top_builddir)/lib/libmiscutil.la \ $(SQUID_CPPUNIT_LIBS) \ $(REGEXLIB) \ $(SSLLIB) \ $(COMPAT_LIB) \ $(XTRA_LIBS) tests_testCoss_LDFLAGS = $(LIBADD_DL) tests_testCoss_DEPENDENCIES = \ $(SWAP_TEST_DS) tests_testNull_SOURCES = \ tests/testNull.cc \ tests/testMain.cc \ tests/testNull.h \ tests/stub_internal.cc \ tests/stub_CommIO.cc \ tests/stub_store_rebuild.cc \ tests/stub_store_stats.cc \ fd.cc \ disk.cc \ + FileMap.h \ filemap.cc \ HttpBody.cc \ HttpReply.cc \ HttpStatusLine.cc \ int.cc \ list.cc \ MemObject.cc \ StoreSwapLogData.cc \ StoreIOState.cc \ StoreMeta.cc \ StoreMetaMD5.cc \ StoreMetaSTD.cc \ StoreMetaSTDLFS.cc \ StoreMetaUnpacker.cc \ StoreMetaURL.cc \ StoreMetaVary.cc \ StoreFileSystem.cc \ store_io.cc \ store_swapout.cc \ store_swapmeta.cc \ @@ -3070,40 +3082,41 @@ ConfigOption.cc \ ConfigParser.cc \ CpuAffinityMap.cc \ CpuAffinityMap.h \ CpuAffinitySet.cc \ CpuAffinitySet.h \ $(DELAY_POOL_SOURCE) \ disk.cc \ DiskIO/ReadRequest.cc \ DiskIO/WriteRequest.cc \ dlink.h \ dlink.cc \ $(DNSSOURCE) \ errorpage.cc \ ETag.cc \ event.cc \ external_acl.cc \ ExternalACLEntry.cc \ fd.cc \ fde.cc \ + FileMap.h \ filemap.cc \ forward.cc \ fqdncache.cc \ ftp.cc \ gopher.cc \ helper.cc \ HelperChildConfig.h \ HelperChildConfig.cc \ hier_code.h \ $(HTCPSOURCE) \ http.cc \ HttpBody.cc \ HttpHdrCc.h \ HttpHdrCc.cc \ HttpHdrCc.cci \ HttpHdrContRange.cc \ HttpHdrRange.cc \ HttpHdrSc.cc \ HttpHdrScTarget.cc \ HttpHeader.cc \ === modified file 'src/filemap.cc' --- src/filemap.cc 2011-09-02 12:35:57 +0000 +++ src/filemap.cc 2011-11-27 18:01:06 +0000 @@ -1,186 +1,160 @@ /* - * $Id$ - * * DEBUG: section 08 Swap File Bitmap * AUTHOR: Harvest Derived * * SQUID Web Proxy Cache http://www.squid-cache.org/ * ---------------------------------------------------------- * * Squid is the result of efforts by numerous individuals from * the Internet community; see the CONTRIBUTORS file for full * details. Many organizations have provided support for Squid's * development; see the SPONSORS file for full details. Squid is * Copyrighted (C) 2001 by the Regents of the University of * California; see the COPYRIGHT file for full details. Squid * incorporates software developed and/or copyrighted by other * sources; see the CREDITS file for full details. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. * */ -#include "squid.h" +#include "config.h" +#include "Debug.h" +#include "FileMap.h" /* Number of bits in a long */ #if SIZEOF_LONG == 8 #define LONG_BIT_SHIFT 6 #define BITS_IN_A_LONG 0x40 #define LONG_BIT_MASK 0x3F #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF #elif SIZEOF_LONG == 4 #define LONG_BIT_SHIFT 5 #define BITS_IN_A_LONG 0x20 #define LONG_BIT_MASK 0x1F #define ALL_ONES (unsigned long) 0xFFFFFFFF #else #define LONG_BIT_SHIFT 5 #define BITS_IN_A_LONG 0x20 #define LONG_BIT_MASK 0x1F #define ALL_ONES (unsigned long) 0xFFFFFFFF #endif #define FM_INITIAL_NUMBER (1<<14) -fileMap * -file_map_create(void) +FileMap::FileMap() : + capacity_(FM_INITIAL_NUMBER), used_slots_(0), + nwords(capacity_ >> LONG_BIT_SHIFT) +{ + debugs(8, 3, HERE << "creating space for " << capacity_ << " files"); + debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each"); + bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap)); +} + +void +FileMap::grow() { - fileMap *fm = (fileMap *)xcalloc(1, sizeof(fileMap)); - fm->max_n_files = FM_INITIAL_NUMBER; - fm->nwords = fm->max_n_files >> LONG_BIT_SHIFT; - debugs(8, 3, "file_map_create: creating space for " << fm->max_n_files << " files"); - debugs(8, 5, "--> " << fm->nwords << " words of " << sizeof(*fm->file_map) << " bytes each"); - fm->file_map = (unsigned long *)xcalloc(fm->nwords, sizeof(*fm->file_map)); - /* XXX account fm->file_map */ - return fm; -} - -static void -file_map_grow(fileMap * fm) -{ - int old_sz = fm->nwords * sizeof(*fm->file_map); - void *old_map = fm->file_map; - fm->max_n_files <<= 1; - assert(fm->max_n_files <= (1 << 24)); /* swap_filen is 25 bits, signed */ - fm->nwords = fm->max_n_files >> LONG_BIT_SHIFT; - debugs(8, 3, "file_map_grow: creating space for " << fm->max_n_files << " files"); - debugs(8, 5, "--> " << fm->nwords << " words of " << sizeof(*fm->file_map) << " bytes each"); - fm->file_map = (unsigned long *)xcalloc(fm->nwords, sizeof(*fm->file_map)); + int old_sz = nwords * sizeof(*bitmap); + void *old_map = bitmap; + capacity_ <<= 1; + assert(capacity_ <= (1 << 24)); /* swap_filen is 25 bits, signed */ + nwords = capacity_ >> LONG_BIT_SHIFT; + debugs(8, 3, HERE << " creating space for " << capacity_ << " files"); + debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each"); + bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap)); debugs(8, 3, "copying " << old_sz << " old bytes"); - memcpy(fm->file_map, old_map, old_sz); + memcpy(bitmap, old_map, old_sz); xfree(old_map); - /* XXX account fm->file_map */ + /* XXX account fm->bitmap */ } -int -file_map_bit_set(fileMap * fm, int file_number) +bool +FileMap::setBit(sfileno file_number) { unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); - while (file_number >= fm->max_n_files) - file_map_grow(fm); + while (file_number >= capacity_) + grow(); - fm->file_map[file_number >> LONG_BIT_SHIFT] |= bitmask; + bitmap[file_number >> LONG_BIT_SHIFT] |= bitmask; - fm->n_files_in_map++; + used_slots_++; return file_number; } /* - * WARNING: file_map_bit_reset does not perform array bounds + * WARNING: clearBit does not perform array bounds * checking! It assumes that 'file_number' is valid, and that the * bit is already set. The caller must verify both of those - * conditions by calling file_map_bit_test() first. + * conditions by calling testBit + * () first. */ void -file_map_bit_reset(fileMap * fm, int file_number) +FileMap::clearBit(sfileno file_number) { unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); - fm->file_map[file_number >> LONG_BIT_SHIFT] &= ~bitmask; - fm->n_files_in_map--; + bitmap[file_number >> LONG_BIT_SHIFT] &= ~bitmask; + used_slots_--; } -int -file_map_bit_test(fileMap * fm, int file_number) +bool +FileMap::testBit(sfileno file_number) const { unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); - if (file_number >= fm->max_n_files) + if (file_number >= capacity_) return 0; /* be sure the return value is an int, not a u_long */ - return (fm->file_map[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0); + return (bitmap[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0); } -int -file_map_allocate(fileMap * fm, int suggestion) +sfileno +FileMap::allocate(sfileno suggestion) { int word; - int bit; - int count; - if (suggestion >= fm->max_n_files) + if (suggestion >= capacity_) suggestion = 0; - if (!file_map_bit_test(fm, suggestion)) + if (!testBit(suggestion)) return suggestion; word = suggestion >> LONG_BIT_SHIFT; - for (count = 0; count < fm->nwords; count++) { - if (fm->file_map[word] != ALL_ONES) + for (unsigned int count = 0; count < nwords; count++) { + if (bitmap[word] != ALL_ONES) break; - word = (word + 1) % fm->nwords; + word = (word + 1) % nwords; } - for (bit = 0; bit < BITS_IN_A_LONG; bit++) { + for (unsigned char bit = 0; bit < BITS_IN_A_LONG; bit++) { suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit; - if (!file_map_bit_test(fm, suggestion)) { + if (!testBit(suggestion)) { return suggestion; } } - debugs(8, 3, "growing from file_map_allocate"); - file_map_grow(fm); - return file_map_allocate(fm, fm->max_n_files >> 1); -} - -void -filemapFreeMemory(fileMap * fm) -{ - safe_free(fm->file_map); - safe_free(fm); + grow(); + return allocate(capacity_ >> 1); } -#ifdef TEST - -#define TEST_SIZE 1<<16 -main(argc, argv) +FileMap::~FileMap() { - int i; - - fm = file_map_create(TEST_SIZE); - - for (i = 0; i < TEST_SIZE; ++i) { - file_map_bit_set(i); - assert(file_map_bit_test(i)); - file_map_bit_reset(i); - } + safe_free(bitmap); } - -#endif === modified file 'src/fs/coss/store_dir_coss.cc' --- src/fs/coss/store_dir_coss.cc 2011-09-22 21:42:46 +0000 +++ src/fs/coss/store_dir_coss.cc 2011-11-26 15:44:03 +0000 @@ -964,42 +964,42 @@ int CossSwapDir::callback() { return io->callback(); } /* ========== LOCAL FUNCTIONS ABOVE, GLOBAL FUNCTIONS BELOW ========== */ void CossSwapDir::statfs(StoreEntry & sentry) const { storeAppendPrintf(&sentry, "\n"); storeAppendPrintf(&sentry, "Maximum Size: %"PRIu64" KB\n", maxSize() >> 10); storeAppendPrintf(&sentry, "Current Size: %.2f KB\n", currentSize() / 1024.0); storeAppendPrintf(&sentry, "Percent Used: %0.2f%%\n", Math::doublePercent(currentSize(), maxSize()) ); storeAppendPrintf(&sentry, "Number of object collisions: %d\n", (int) numcollisions); #if 0 /* is this applicable? I Hope not .. */ storeAppendPrintf(sentry, "Filemap bits in use: %d of %d (%d%%)\n", - SD->map->n_files_in_map, SD->map->max_n_files, - Math::intPercent(SD->map->n_files_in_map, SD->map->max_n_files)); + SD->map->numFilesInMap(), SD->map->capacity(), + Math::intPercent(SD->map->numFilesInMap(), SD->map->capacity())); #endif // storeAppendPrintf(&sentry, "Pending operations: %d out of %d\n", io->aq.aq_numpending, MAX_ASYNCOP); storeAppendPrintf(&sentry, "Flags:"); if (flags.selected) storeAppendPrintf(&sentry, " SELECTED"); if (flags.read_only) storeAppendPrintf(&sentry, " READ-ONLY"); storeAppendPrintf(&sentry, "\n"); } void CossSwapDir::parse(int anIndex, char *aPath) { const int i = GetInteger(); if (i <= 0) fatal("storeCossDirParse: invalid size value"); === modified file 'src/fs/ufs/store_dir_ufs.cc' --- src/fs/ufs/store_dir_ufs.cc 2011-11-08 15:00:17 +0000 +++ src/fs/ufs/store_dir_ufs.cc 2011-11-27 18:06:40 +0000 @@ -24,40 +24,41 @@ * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. * */ #include "squid.h" #include "Store.h" #include "fde.h" #include "ufscommon.h" #include "StoreSwapLogData.h" #include "ConfigOption.h" #include "DiskIO/DiskIOStrategy.h" #include "DiskIO/DiskIOModule.h" +#include "FileMap.h" #include "Parsing.h" #include "SquidMath.h" #include "SquidTime.h" #include "SwapDir.h" #include "swap_log_op.h" int UFSSwapDir::NumberOfUFSDirs = 0; int *UFSSwapDir::UFSDirToGlobalDirMapping = NULL; /* * storeUfsDirCheckObj * * This routine is called by storeDirSelectSwapDir to see if the given * object is able to be stored on this filesystem. UFS filesystems will * happily store anything as long as the LRU time isn't too small. */ bool UFSSwapDir::canStore(const StoreEntry &e, int64_t diskSpaceNeeded, int &load) const { if (!SwapDir::canStore(e, diskSpaceNeeded, load)) @@ -229,56 +230,56 @@ openLog(); rebuild(); if (!started_clean_event) { eventAdd("UFS storeDirClean", CleanEvent, NULL, 15.0, 1); started_clean_event = 1; } (void) storeDirGetBlkSize(path, &fs.blksize); } void UFSSwapDir::create() { debugs(47, 3, "Creating swap space in " << path); createDirectory(path, 0); createSwapSubDirs(); } -UFSSwapDir::UFSSwapDir(char const *aType, const char *anIOType) : SwapDir(aType), IO(NULL), map(file_map_create()), suggest(0), swaplog_fd (-1), currentIOOptions(new ConfigOptionVector()), ioType(xstrdup(anIOType)), cur_size(0), n_disk_objects(0) +UFSSwapDir::UFSSwapDir(char const *aType, const char *anIOType) : SwapDir(aType), IO(NULL), map(new FileMap()), suggest(0), swaplog_fd (-1), currentIOOptions(new ConfigOptionVector()), ioType(xstrdup(anIOType)), cur_size(0), n_disk_objects(0) { /* modulename is only set to disk modules that are built, by configure, * so the Find call should never return NULL here. */ IO = new UFSStrategy(DiskIOModule::Find(anIOType)->createStrategy()); } UFSSwapDir::~UFSSwapDir() { if (swaplog_fd > -1) { file_close(swaplog_fd); swaplog_fd = -1; } - filemapFreeMemory(map); + delete map; if (IO) delete IO; IO = NULL; safe_free(ioType); } void UFSSwapDir::dumpEntry(StoreEntry &e) const { debugs(47, 0, "UFSSwapDir::dumpEntry: FILENO "<< std::setfill('0') << std::hex << std::uppercase << std::setw(8) << e.swap_filen); debugs(47, 0, "UFSSwapDir::dumpEntry: PATH " << fullPath(e.swap_filen, NULL) ); e.dump(0); } /* * UFSSwapDir::doubleCheck * @@ -304,42 +305,42 @@ } return false; } void UFSSwapDir::statfs(StoreEntry & sentry) const { int totl_kb = 0; int free_kb = 0; int totl_in = 0; int free_in = 0; int x; storeAppendPrintf(&sentry, "First level subdirectories: %d\n", l1); storeAppendPrintf(&sentry, "Second level subdirectories: %d\n", l2); storeAppendPrintf(&sentry, "Maximum Size: %"PRIu64" KB\n", maxSize() >> 10); storeAppendPrintf(&sentry, "Current Size: %.2f KB\n", currentSize() / 1024.0); storeAppendPrintf(&sentry, "Percent Used: %0.2f%%\n", Math::doublePercent(currentSize(), maxSize())); storeAppendPrintf(&sentry, "Filemap bits in use: %d of %d (%d%%)\n", - map->n_files_in_map, map->max_n_files, - Math::intPercent(map->n_files_in_map, map->max_n_files)); + map->numFilesInMap(), map->capacity(), + Math::intPercent(map->numFilesInMap(), map->capacity())); x = storeDirGetUFSStats(path, &totl_kb, &free_kb, &totl_in, &free_in); if (0 == x) { storeAppendPrintf(&sentry, "Filesystem Space in use: %d/%d KB (%d%%)\n", totl_kb - free_kb, totl_kb, Math::intPercent(totl_kb - free_kb, totl_kb)); storeAppendPrintf(&sentry, "Filesystem Inodes in use: %d/%d (%d%%)\n", totl_in - free_in, totl_in, Math::intPercent(totl_in - free_in, totl_in)); } storeAppendPrintf(&sentry, "Flags:"); if (flags.selected) storeAppendPrintf(&sentry, " SELECTED"); if (flags.read_only) storeAppendPrintf(&sentry, " READ-ONLY"); @@ -433,70 +434,70 @@ repl->Dereferenced(repl, &e, &e.repl); return true; // keep e in the global store_table } StoreIOState::Pointer UFSSwapDir::createStoreIO(StoreEntry &e, StoreIOState::STFNCB * file_callback, StoreIOState::STIOCB * aCallback, void *callback_data) { return IO->create (this, &e, file_callback, aCallback, callback_data); } StoreIOState::Pointer UFSSwapDir::openStoreIO(StoreEntry &e, StoreIOState::STFNCB * file_callback, StoreIOState::STIOCB * aCallback, void *callback_data) { return IO->open (this, &e, file_callback, aCallback, callback_data); } int UFSSwapDir::mapBitTest(sfileno filn) { - return file_map_bit_test(map, filn); + return map->testBit(filn); } void UFSSwapDir::mapBitSet(sfileno filn) { - file_map_bit_set(map, filn); + map->setBit(filn); } void UFSSwapDir::mapBitReset(sfileno filn) { /* - * We have to test the bit before calling file_map_bit_reset. - * file_map_bit_reset doesn't do bounds checking. It assumes + * We have to test the bit before calling clearBit as + * it doesn't do bounds checking and blindly assumes * filn is a valid file number, but it might not be because * the map is dynamic in size. Also clearing an already clear * bit puts the map counter of-of-whack. */ - if (file_map_bit_test(map, filn)) - file_map_bit_reset(map, filn); + if (map->testBit(filn)) + map->clearBit(filn); } int UFSSwapDir::mapBitAllocate() { int fn; - fn = file_map_allocate(map, suggest); - file_map_bit_set(map, fn); + fn = map->allocate(suggest); + map->setBit(fn); suggest = fn + 1; return fn; } char * UFSSwapDir::swapSubDir(int subdirn)const { LOCAL_ARRAY(char, fullfilename, MAXPATHLEN); assert(0 <= subdirn && subdirn < l1); snprintf(fullfilename, MAXPATHLEN, "%s/%02X", path, subdirn); return fullfilename; } int UFSSwapDir::createDirectory(const char *aPath, int should_exist) { int created = 0; struct stat st; getCurrentTime(); @@ -1245,41 +1246,41 @@ D2 = (filn / L2) % L2; if (F2 != D2) return 0; return 1; } int UFSSwapDir::validFileno(sfileno filn, int flag) const { if (filn < 0) return 0; /* * If flag is set it means out-of-range file number should * be considered invalid. */ if (flag) - if (filn > map->max_n_files) + if (filn > map->capacity()) return 0; return 1; } /* * UFSSwapDir::unlinkFile * * This routine unlinks a file and pulls it out of the bitmap. * It used to be in commonUfsUnlink(), however an interface change * forced this bit of code here. Eeek. */ void UFSSwapDir::unlinkFile(sfileno f) { debugs(79, 3, "UFSSwapDir::unlinkFile: unlinking fileno " << std::setfill('0') << std::hex << std::uppercase << std::setw(8) << f << " '" << fullPath(f,NULL) << "'"); === modified file 'src/fs/ufs/ufscommon.h' --- src/fs/ufs/ufscommon.h 2011-10-27 23:14:28 +0000 +++ src/fs/ufs/ufscommon.h 2011-11-26 09:58:30 +0000 @@ -23,40 +23,41 @@ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. * */ #ifndef SQUID_UFSCOMMON_H #define SQUID_UFSCOMMON_H #define DefaultLevelOneDirs 16 #define DefaultLevelTwoDirs 256 #define STORE_META_BUFSZ 4096 class UFSStrategy; class ConfigOptionVector; class DiskIOModule; class StoreSearch; +class FileMap; #include "SwapDir.h" /// \ingroup UFS class UFSSwapDir : public SwapDir { public: static int IsUFSDir(SwapDir* sd); static int DirClean(int swap_index); static int FilenoBelongsHere(int fn, int F0, int F1, int F2); UFSSwapDir(char const *aType, const char *aModuleType); virtual void init(); virtual void create(); virtual void dump(StoreEntry &) const; ~UFSSwapDir(); virtual StoreSearch *search(String const url, HttpRequest *); virtual bool doubleCheck(StoreEntry &); virtual bool unlinkdUseful() const; @@ -99,41 +100,41 @@ time_t expires, time_t timestamp, time_t lastref, time_t lastmod, uint32_t refcount, uint16_t flags, int clean); int validFileno(sfileno filn, int flag) const; int mapBitAllocate(); virtual ConfigOption *getOptionTree() const; void *fsdata; bool validL2(int) const; bool validL1(int) const; void replacementAdd(StoreEntry *e); void replacementRemove(StoreEntry *e); protected: - fileMap *map; + FileMap *map; int suggest; int l1; int l2; private: void parseSizeL1L2(); static int NumberOfUFSDirs; static int * UFSDirToGlobalDirMapping; bool pathIsDirectory(const char *path)const; int swaplog_fd; static EVH CleanEvent; bool verifyCacheDirs(); void rebuild(); int createDirectory(const char *path, int); void createSwapSubDirs(); void dumpEntry(StoreEntry &) const; char *logFile(char const *ext = NULL)const; void changeIO(DiskIOModule *); bool optionIOParse(char const *option, const char *value, int reconfiguring); void optionIODump(StoreEntry * e) const; === modified file 'src/ipc/StoreMap.h' --- src/ipc/StoreMap.h 2011-10-28 01:01:41 +0000 +++ src/ipc/StoreMap.h 2011-11-26 09:58:30 +0000 @@ -178,24 +178,24 @@ template <class ExtrasT> ExtrasT & StoreMapWithExtras<ExtrasT>::extras(const sfileno fileno) { return const_cast<ExtrasT &>(const_cast<const StoreMapWithExtras *>(this)->extras(fileno)); } template <class ExtrasT> const ExtrasT & StoreMapWithExtras<ExtrasT>::extras(const sfileno fileno) const { assert(sharedExtras); assert(valid(fileno)); return sharedExtras[fileno]; } } // namespace Ipc -// We do not reuse struct _fileMap because we cannot control its size, +// We do not reuse FileMap because we cannot control its size, // resulting in sfilenos that are pointing beyond the database. #endif /* SQUID_IPC_STORE_MAP_H */ === modified file 'src/protos.h' --- src/protos.h 2011-11-03 10:02:02 +0000 +++ src/protos.h 2011-11-26 09:58:30 +0000 @@ -127,48 +127,40 @@ SQUIDCEXTERN void dnsShutdown(void); SQUIDCEXTERN void dnsInit(void); SQUIDCEXTERN void dnsSubmit(const char *lookup, HLPCB * callback, void *data); /* dns_internal.c */ SQUIDCEXTERN void idnsInit(void); SQUIDCEXTERN void idnsShutdown(void); SQUIDCEXTERN void idnsALookup(const char *, IDNSCB *, void *); SQUIDCEXTERN void idnsPTRLookup(const Ip::Address &, IDNSCB *, void *); SQUIDCEXTERN void fd_close(int fd); SQUIDCEXTERN void fd_open(int fd, unsigned int type, const char *); SQUIDCEXTERN void fd_note(int fd, const char *); SQUIDCEXTERN void fd_bytes(int fd, int len, unsigned int type); SQUIDCEXTERN void fdDumpOpen(void); SQUIDCEXTERN int fdUsageHigh(void); SQUIDCEXTERN void fdAdjustReserved(void); -SQUIDCEXTERN fileMap *file_map_create(void); -SQUIDCEXTERN int file_map_allocate(fileMap *, int); -SQUIDCEXTERN int file_map_bit_set(fileMap *, int); -SQUIDCEXTERN int file_map_bit_test(fileMap *, int); -SQUIDCEXTERN void file_map_bit_reset(fileMap *, int); -SQUIDCEXTERN void filemapFreeMemory(fileMap *); - - SQUIDCEXTERN void fqdncache_nbgethostbyaddr(const Ip::Address &, FQDNH *, void *); SQUIDCEXTERN const char *fqdncache_gethostbyaddr(const Ip::Address &, int flags); SQUIDCEXTERN void fqdncache_init(void); void fqdnStats(StoreEntry *); SQUIDCEXTERN void fqdncacheReleaseInvalid(const char *); SQUIDCEXTERN const char *fqdnFromAddr(const Ip::Address &); SQUIDCEXTERN int fqdncacheQueueDrain(void); SQUIDCEXTERN void fqdncacheFreeMemory(void); SQUIDCEXTERN void fqdncache_restart(void); void fqdncache_purgelru(void *); SQUIDCEXTERN void fqdncacheAddEntryFromHosts(char *addr, wordlist * hostnames); class FwdState; /** \defgroup ServerProtocolFTPAPI Server-Side FTP API \ingroup ServerProtocol */ === modified file 'src/structs.h' --- src/structs.h 2011-11-08 10:54:37 +0000 +++ src/structs.h 2011-11-26 09:58:30 +0000 @@ -679,48 +679,40 @@ void *client_data; }; struct _dwrite_q { off_t file_offset; char *buf; size_t len; size_t buf_offset; dwrite_q *next; FREE *free_func; }; struct _fde_disk { DWCB *wrt_handle; void *wrt_handle_data; dwrite_q *write_q; dwrite_q *write_q_tail; off_t offset; }; -struct _fileMap { - int max_n_files; - int n_files_in_map; - int toggle; - int nwords; - unsigned long *file_map; -}; - /* * Note: HttpBody is used only for messages with a small content that is * known a priory (e.g., error messages). */ class MemBuf; struct _HttpBody { /* private */ MemBuf *mb; }; #include "SquidString.h" /* http header extention field */ class HttpHdrExtField { String name; /* field-name from HTTP/1.1 (no column after name) */ String value; /* field-value from HTTP/1.1 */ }; === modified file 'src/typedefs.h' --- src/typedefs.h 2011-07-25 13:10:17 +0000 +++ src/typedefs.h 2011-11-26 09:58:30 +0000 @@ -39,42 +39,40 @@ typedef int32_t sfileno; typedef signed int sdirno; typedef uint32_t nfmark_t; typedef unsigned char tos_t; typedef struct { size_t bytes; size_t kb; } kb_t; struct http_port_list; struct https_port_list; typedef struct _close_handler close_handler; typedef struct _dread_ctrl dread_ctrl; typedef struct _dwrite_q dwrite_q; -typedef struct _fileMap fileMap; - typedef struct _HttpHeaderFieldAttrs HttpHeaderFieldAttrs; typedef struct _HttpHeaderStat HttpHeaderStat; typedef struct _HttpBody HttpBody; typedef struct _ConnCloseHelperData ConnCloseHelperData; typedef struct _domain_ping domain_ping; typedef struct _domain_type domain_type; typedef struct _DynPool DynPool; typedef struct _DigestFetchState DigestFetchState; typedef struct _net_db_name net_db_name; typedef struct _net_db_peer net_db_peer;
