filemap.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
3  *
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.
7  */
8 
9 /* DEBUG: section 08 Swap File Bitmap */
10 
11 #include "squid.h"
12 #include "Debug.h"
13 #include "FileMap.h"
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 
33 #define FM_INITIAL_NUMBER (1<<14)
34 
36  capacity_(FM_INITIAL_NUMBER), usedSlots_(0),
37  nwords(capacity_ >> LONG_BIT_SHIFT)
38 {
39  debugs(8, 3, HERE << "creating space for " << capacity_ << " files");
40  debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each");
41  bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap));
42 }
43 
44 void
46 {
47  int old_sz = nwords * sizeof(*bitmap);
48  void *old_map = bitmap;
49  capacity_ <<= 1;
50  assert(capacity_ <= (1 << 24)); /* swap_filen is 25 bits, signed */
52  debugs(8, 3, HERE << " creating space for " << capacity_ << " files");
53  debugs(8, 5, "--> " << nwords << " words of " << sizeof(*bitmap) << " bytes each");
54  bitmap = (unsigned long *)xcalloc(nwords, sizeof(*bitmap));
55  debugs(8, 3, "copying " << old_sz << " old bytes");
56  memcpy(bitmap, old_map, old_sz);
57  xfree(old_map);
58  /* XXX account fm->bitmap */
59 }
60 
61 bool
63 {
64  unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
65 
66  while (file_number >= capacity_)
67  grow();
68 
69  bitmap[file_number >> LONG_BIT_SHIFT] |= bitmask;
70 
71  ++usedSlots_;
72 
73  return file_number;
74 }
75 
76 /*
77  * WARNING: clearBit does not perform array bounds
78  * checking! It assumes that 'file_number' is valid, and that the
79  * bit is already set. The caller must verify both of those
80  * conditions by calling testBit
81  * () first.
82  */
83 void
85 {
86  unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
87  bitmap[file_number >> LONG_BIT_SHIFT] &= ~bitmask;
88  --usedSlots_;
89 }
90 
91 bool
92 FileMap::testBit(sfileno file_number) const
93 {
94  unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
95 
96  if (file_number >= capacity_)
97  return 0;
98 
99  /* be sure the return value is an int, not a u_long */
100  return (bitmap[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0);
101 }
102 
103 sfileno
105 {
106  int word;
107 
108  if (suggestion >= capacity_)
109  suggestion = 0;
110 
111  if (!testBit(suggestion))
112  return suggestion;
113 
114  word = suggestion >> LONG_BIT_SHIFT;
115 
116  for (unsigned int count = 0; count < nwords; ++count) {
117  if (bitmap[word] != ALL_ONES)
118  break;
119 
120  word = (word + 1) % nwords;
121  }
122 
123  for (unsigned char bit = 0; bit < BITS_IN_A_LONG; ++bit) {
124  suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit;
125 
126  if (!testBit(suggestion)) {
127  return suggestion;
128  }
129  }
130 
131  grow();
132  return allocate(capacity_ >> 1);
133 }
134 
136 {
137  safe_free(bitmap);
138 }
139 
~FileMap()
Definition: filemap.cc:135
#define assert(EX)
Definition: assert.h:17
#define ALL_ONES
Definition: filemap.cc:30
unsigned long * bitmap
Definition: FileMap.h:76
bool setBit(sfileno num)
Definition: filemap.cc:62
#define xcalloc
Definition: membanger.c:57
bool testBit(sfileno num) const
Test whether the num-th bit in the FileMap is set.
Definition: filemap.cc:92
#define safe_free(x)
Definition: xalloc.h:73
sfileno allocate(sfileno suggestion)
Definition: filemap.cc:104
unsigned int nwords
number of "long ints" making up the filemap
Definition: FileMap.h:75
#define LONG_BIT_MASK
Definition: filemap.cc:29
#define FM_INITIAL_NUMBER
Definition: filemap.cc:33
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
void clearBit(sfileno num)
Definition: filemap.cc:84
#define BITS_IN_A_LONG
Definition: filemap.cc:28
signed_int32_t sfileno
Definition: forward.h:22
sfileno capacity_
max number of files which can be tracked in the current store
Definition: FileMap.h:71
std::ostream & HERE(std::ostream &s)
Definition: Debug.h:147
FileMap()
Definition: filemap.cc:35
unsigned int usedSlots_
used slots in the map
Definition: FileMap.h:73
#define LONG_BIT_SHIFT
Definition: filemap.cc:27
#define xfree
void grow()
grow the FileMap (size is doubled each time, up to 2^24 bits)
Definition: filemap.cc:45

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors