]>
Commit | Line | Data |
---|---|---|
30a4f2a8 | 1 | /* |
bf95c10a | 2 | * Copyright (C) 1996-2022 The Squid Software Foundation and contributors |
e25c139f | 3 | * |
bbc27441 AJ |
4 | * Squid software is distributed under GPLv2+ license and includes |
5 | * contributions from numerous individuals and organizations. | |
6 | * Please see the COPYING and CONTRIBUTORS files for details. | |
30a4f2a8 | 7 | */ |
ed43818f | 8 | |
bbc27441 AJ |
9 | /* DEBUG: section 08 Swap File Bitmap */ |
10 | ||
f7f3304a | 11 | #include "squid.h" |
75f8f9a2 FC |
12 | #include "Debug.h" |
13 | #include "FileMap.h" | |
090089c4 | 14 | |
15 | /* Number of bits in a long */ | |
16 | #if SIZEOF_LONG == 8 | |
17 | #define LONG_BIT_SHIFT 6 | |
18 | #define BITS_IN_A_LONG 0x40 | |
19 | #define LONG_BIT_MASK 0x3F | |
20 | #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF | |
21 | #elif SIZEOF_LONG == 4 | |
22 | #define LONG_BIT_SHIFT 5 | |
23 | #define BITS_IN_A_LONG 0x20 | |
24 | #define LONG_BIT_MASK 0x1F | |
25 | #define ALL_ONES (unsigned long) 0xFFFFFFFF | |
26 | #else | |
27 | #define LONG_BIT_SHIFT 5 | |
28 | #define BITS_IN_A_LONG 0x20 | |
29 | #define LONG_BIT_MASK 0x1F | |
30 | #define ALL_ONES (unsigned long) 0xFFFFFFFF | |
31 | #endif | |
32 | ||
8b108705 | 33 | #define FM_INITIAL_NUMBER (1<<14) |
34 | ||
75f8f9a2 | 35 | FileMap::FileMap() : |
f53969cc SM |
36 | capacity_(FM_INITIAL_NUMBER), usedSlots_(0), |
37 | nwords(capacity_ >> LONG_BIT_SHIFT) | |
090089c4 | 38 | { |
bf95c10a | 39 | debugs(8, 3, "creating space for " << capacity_ << " files"); |
75f8f9a2 FC |
40 | debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each"); |
41 | bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap)); | |
090089c4 | 42 | } |
43 | ||
75f8f9a2 FC |
44 | void |
45 | FileMap::grow() | |
8b108705 | 46 | { |
75f8f9a2 FC |
47 | int old_sz = nwords * sizeof(*bitmap); |
48 | void *old_map = bitmap; | |
49 | capacity_ <<= 1; | |
f53969cc | 50 | assert(capacity_ <= (1 << 24)); /* swap_filen is 25 bits, signed */ |
75f8f9a2 | 51 | nwords = capacity_ >> LONG_BIT_SHIFT; |
bf95c10a | 52 | debugs(8, 3, " creating space for " << capacity_ << " files"); |
75f8f9a2 FC |
53 | debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each"); |
54 | bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap)); | |
bf8fe701 | 55 | debugs(8, 3, "copying " << old_sz << " old bytes"); |
75f8f9a2 | 56 | memcpy(bitmap, old_map, old_sz); |
8b108705 | 57 | xfree(old_map); |
75f8f9a2 | 58 | /* XXX account fm->bitmap */ |
8b108705 | 59 | } |
60 | ||
75f8f9a2 FC |
61 | bool |
62 | FileMap::setBit(sfileno file_number) | |
090089c4 | 63 | { |
64 | unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); | |
62e76326 | 65 | |
75f8f9a2 FC |
66 | while (file_number >= capacity_) |
67 | grow(); | |
62e76326 | 68 | |
75f8f9a2 | 69 | bitmap[file_number >> LONG_BIT_SHIFT] |= bitmask; |
62e76326 | 70 | |
95dc7ff4 | 71 | ++usedSlots_; |
62e76326 | 72 | |
8b108705 | 73 | return file_number; |
090089c4 | 74 | } |
75 | ||
c8a9574c | 76 | /* |
75f8f9a2 | 77 | * WARNING: clearBit does not perform array bounds |
c8a9574c | 78 | * checking! It assumes that 'file_number' is valid, and that the |
79 | * bit is already set. The caller must verify both of those | |
75f8f9a2 FC |
80 | * conditions by calling testBit |
81 | * () first. | |
c8a9574c | 82 | */ |
b8d8561b | 83 | void |
75f8f9a2 | 84 | FileMap::clearBit(sfileno file_number) |
090089c4 | 85 | { |
86 | unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); | |
75f8f9a2 | 87 | bitmap[file_number >> LONG_BIT_SHIFT] &= ~bitmask; |
5e263176 | 88 | --usedSlots_; |
090089c4 | 89 | } |
90 | ||
75f8f9a2 FC |
91 | bool |
92 | FileMap::testBit(sfileno file_number) const | |
090089c4 | 93 | { |
94 | unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK)); | |
62e76326 | 95 | |
75f8f9a2 | 96 | if (file_number >= capacity_) |
62e76326 | 97 | return 0; |
98 | ||
090089c4 | 99 | /* be sure the return value is an int, not a u_long */ |
75f8f9a2 | 100 | return (bitmap[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0); |
090089c4 | 101 | } |
102 | ||
75f8f9a2 FC |
103 | sfileno |
104 | FileMap::allocate(sfileno suggestion) | |
090089c4 | 105 | { |
106 | int word; | |
62e76326 | 107 | |
75f8f9a2 | 108 | if (suggestion >= capacity_) |
62e76326 | 109 | suggestion = 0; |
110 | ||
75f8f9a2 | 111 | if (!testBit(suggestion)) |
62e76326 | 112 | return suggestion; |
113 | ||
090089c4 | 114 | word = suggestion >> LONG_BIT_SHIFT; |
62e76326 | 115 | |
95dc7ff4 | 116 | for (unsigned int count = 0; count < nwords; ++count) { |
75f8f9a2 | 117 | if (bitmap[word] != ALL_ONES) |
62e76326 | 118 | break; |
119 | ||
75f8f9a2 | 120 | word = (word + 1) % nwords; |
090089c4 | 121 | } |
62e76326 | 122 | |
95dc7ff4 | 123 | for (unsigned char bit = 0; bit < BITS_IN_A_LONG; ++bit) { |
62e76326 | 124 | suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit; |
125 | ||
75f8f9a2 | 126 | if (!testBit(suggestion)) { |
62e76326 | 127 | return suggestion; |
128 | } | |
090089c4 | 129 | } |
62e76326 | 130 | |
75f8f9a2 FC |
131 | grow(); |
132 | return allocate(capacity_ >> 1); | |
0a21bd84 | 133 | } |
134 | ||
75f8f9a2 | 135 | FileMap::~FileMap() |
090089c4 | 136 | { |
75f8f9a2 | 137 | safe_free(bitmap); |
090089c4 | 138 | } |
f53969cc | 139 |