]>
Commit | Line | Data |
---|---|---|
30a4f2a8 | 1 | /* |
b510f3a1 | 2 | * DEBUG: section 08 Swap File Bitmap |
30a4f2a8 | 3 | * AUTHOR: Harvest Derived |
4 | * | |
2b6662ba | 5 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 6 | * ---------------------------------------------------------- |
30a4f2a8 | 7 | * |
2b6662ba | 8 | * Squid is the result of efforts by numerous individuals from |
9 | * the Internet community; see the CONTRIBUTORS file for full | |
10 | * details. Many organizations have provided support for Squid's | |
11 | * development; see the SPONSORS file for full details. Squid is | |
12 | * Copyrighted (C) 2001 by the Regents of the University of | |
13 | * California; see the COPYRIGHT file for full details. Squid | |
14 | * incorporates software developed and/or copyrighted by other | |
15 | * sources; see the CREDITS file for full details. | |
30a4f2a8 | 16 | * |
17 | * This program is free software; you can redistribute it and/or modify | |
18 | * it under the terms of the GNU General Public License as published by | |
19 | * the Free Software Foundation; either version 2 of the License, or | |
20 | * (at your option) any later version. | |
26ac0430 | 21 | * |
30a4f2a8 | 22 | * This program is distributed in the hope that it will be useful, |
23 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
24 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
25 | * GNU General Public License for more details. | |
26ac0430 | 26 | * |
30a4f2a8 | 27 | * You should have received a copy of the GNU General Public License |
28 | * along with this program; if not, write to the Free Software | |
cbdec147 | 29 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 30 | * |
30a4f2a8 | 31 | */ |
ed43818f | 32 | |
75f8f9a2 FC |
33 | #include "config.h" |
34 | #include "Debug.h" | |
35 | #include "FileMap.h" | |
090089c4 | 36 | |
37 | /* Number of bits in a long */ | |
38 | #if SIZEOF_LONG == 8 | |
39 | #define LONG_BIT_SHIFT 6 | |
40 | #define BITS_IN_A_LONG 0x40 | |
41 | #define LONG_BIT_MASK 0x3F | |
42 | #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF | |
43 | #elif SIZEOF_LONG == 4 | |
44 | #define LONG_BIT_SHIFT 5 | |
45 | #define BITS_IN_A_LONG 0x20 | |
46 | #define LONG_BIT_MASK 0x1F | |
47 | #define ALL_ONES (unsigned long) 0xFFFFFFFF | |
48 | #else | |
49 | #define LONG_BIT_SHIFT 5 | |
50 | #define BITS_IN_A_LONG 0x20 | |
51 | #define LONG_BIT_MASK 0x1F | |
52 | #define ALL_ONES (unsigned long) 0xFFFFFFFF | |
53 | #endif | |
54 | ||
8b108705 | 55 | #define FM_INITIAL_NUMBER (1<<14) |
56 | ||
75f8f9a2 | 57 | FileMap::FileMap() : |
ce88d0eb A |
58 | capacity_(FM_INITIAL_NUMBER), usedSlots_(0), |
59 | nwords(capacity_ >> LONG_BIT_SHIFT) | |
090089c4 | 60 | { |
75f8f9a2 FC |
61 | debugs(8, 3, HERE << "creating space for " << capacity_ << " files"); |
62 | debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each"); | |
63 | bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap)); | |
090089c4 | 64 | } |
65 | ||
75f8f9a2 FC |
66 | void |
67 | FileMap::grow() | |
8b108705 | 68 | { |
75f8f9a2 FC |
69 | int old_sz = nwords * sizeof(*bitmap); |
70 | void *old_map = bitmap; | |
71 | capacity_ <<= 1; | |
72 | assert(capacity_ <= (1 << 24)); /* swap_filen is 25 bits, signed */ | |
73 | nwords = capacity_ >> LONG_BIT_SHIFT; | |
74 | debugs(8, 3, HERE << " creating space for " << capacity_ << " files"); | |
75 | debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each"); | |
76 | bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap)); | |
bf8fe701 | 77 | debugs(8, 3, "copying " << old_sz << " old bytes"); |
75f8f9a2 | 78 | memcpy(bitmap, old_map, old_sz); |
8b108705 | 79 | xfree(old_map); |
75f8f9a2 | 80 | /* XXX account fm->bitmap */ |
8b108705 | 81 | } |
82 | ||
75f8f9a2 FC |
83 | bool |
84 | FileMap::setBit(sfileno file_number) | |
090089c4 | 85 | { |
86 | unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); | |
62e76326 | 87 | |
75f8f9a2 FC |
88 | while (file_number >= capacity_) |
89 | grow(); | |
62e76326 | 90 | |
75f8f9a2 | 91 | bitmap[file_number >> LONG_BIT_SHIFT] |= bitmask; |
62e76326 | 92 | |
e12f6fa3 | 93 | usedSlots_++; |
62e76326 | 94 | |
8b108705 | 95 | return file_number; |
090089c4 | 96 | } |
97 | ||
c8a9574c | 98 | /* |
75f8f9a2 | 99 | * WARNING: clearBit does not perform array bounds |
c8a9574c | 100 | * checking! It assumes that 'file_number' is valid, and that the |
101 | * bit is already set. The caller must verify both of those | |
75f8f9a2 FC |
102 | * conditions by calling testBit |
103 | * () first. | |
c8a9574c | 104 | */ |
b8d8561b | 105 | void |
75f8f9a2 | 106 | FileMap::clearBit(sfileno file_number) |
090089c4 | 107 | { |
108 | unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); | |
75f8f9a2 | 109 | bitmap[file_number >> LONG_BIT_SHIFT] &= ~bitmask; |
e12f6fa3 | 110 | usedSlots_--; |
090089c4 | 111 | } |
112 | ||
75f8f9a2 FC |
113 | bool |
114 | FileMap::testBit(sfileno file_number) const | |
090089c4 | 115 | { |
116 | unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); | |
62e76326 | 117 | |
75f8f9a2 | 118 | if (file_number >= capacity_) |
62e76326 | 119 | return 0; |
120 | ||
090089c4 | 121 | /* be sure the return value is an int, not a u_long */ |
75f8f9a2 | 122 | return (bitmap[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0); |
090089c4 | 123 | } |
124 | ||
75f8f9a2 FC |
125 | sfileno |
126 | FileMap::allocate(sfileno suggestion) | |
090089c4 | 127 | { |
128 | int word; | |
62e76326 | 129 | |
75f8f9a2 | 130 | if (suggestion >= capacity_) |
62e76326 | 131 | suggestion = 0; |
132 | ||
75f8f9a2 | 133 | if (!testBit(suggestion)) |
62e76326 | 134 | return suggestion; |
135 | ||
090089c4 | 136 | word = suggestion >> LONG_BIT_SHIFT; |
62e76326 | 137 | |
75f8f9a2 FC |
138 | for (unsigned int count = 0; count < nwords; count++) { |
139 | if (bitmap[word] != ALL_ONES) | |
62e76326 | 140 | break; |
141 | ||
75f8f9a2 | 142 | word = (word + 1) % nwords; |
090089c4 | 143 | } |
62e76326 | 144 | |
75f8f9a2 | 145 | for (unsigned char bit = 0; bit < BITS_IN_A_LONG; bit++) { |
62e76326 | 146 | suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit; |
147 | ||
75f8f9a2 | 148 | if (!testBit(suggestion)) { |
62e76326 | 149 | return suggestion; |
150 | } | |
090089c4 | 151 | } |
62e76326 | 152 | |
75f8f9a2 FC |
153 | grow(); |
154 | return allocate(capacity_ >> 1); | |
0a21bd84 | 155 | } |
156 | ||
75f8f9a2 | 157 | FileMap::~FileMap() |
090089c4 | 158 | { |
75f8f9a2 | 159 | safe_free(bitmap); |
090089c4 | 160 | } |