src/filemap.cc

   1 /*
   2  * Copyright (C) 1996-2021 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
  35 FileMap::FileMap() :
  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
  45 FileMap::grow()
  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 */
  51     nwords = capacity_ >> LONG_BIT_SHIFT;
  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
  62 FileMap::setBit(sfileno file_number)
  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
  84 FileMap::clearBit(sfileno file_number)
  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
 104 FileMap::allocate(sfileno suggestion)
 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
 135 FileMap::~FileMap()
 136 {
 137     safe_free(bitmap);
 138 }
 139