filemap.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 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/Stream.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, "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
44void
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, " 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
61bool
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 */
83void
85{
86 unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
87 bitmap[file_number >> LONG_BIT_SHIFT] &= ~bitmask;
88 --usedSlots_;
89}
90
91bool
92FileMap::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
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{
138}
139
#define assert(EX)
Definition: assert.h:19
~FileMap()
Definition: filemap.cc:135
unsigned int nwords
number of "long ints" making up the filemap
Definition: FileMap.h:75
bool testBit(sfileno num) const
Test whether the num-th bit in the FileMap is set.
Definition: filemap.cc:92
void clearBit(sfileno num)
Definition: filemap.cc:84
unsigned long * bitmap
Definition: FileMap.h:76
void grow()
grow the FileMap (size is doubled each time, up to 2^24 bits)
Definition: filemap.cc:45
sfileno allocate(sfileno suggestion)
Definition: filemap.cc:104
sfileno capacity_
max number of files which can be tracked in the current store
Definition: FileMap.h:71
bool setBit(sfileno num)
Definition: filemap.cc:62
FileMap()
Definition: filemap.cc:35
unsigned int usedSlots_
used slots in the map
Definition: FileMap.h:73
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
#define FM_INITIAL_NUMBER
Definition: filemap.cc:33
#define BITS_IN_A_LONG
Definition: filemap.cc:28
#define LONG_BIT_MASK
Definition: filemap.cc:29
#define LONG_BIT_SHIFT
Definition: filemap.cc:27
#define ALL_ONES
Definition: filemap.cc:30
#define xfree
signed_int32_t sfileno
Definition: forward.h:22
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
#define safe_free(x)
Definition: xalloc.h:73

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors