src/filemap.cc

   1 /*
   2  * $Id$
   3  *
   4  * DEBUG: section 08    Swap File Bitmap
   5  * AUTHOR: Harvest Derived
   6  *
   7  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   8  * ----------------------------------------------------------
   9  *
  10  *  Squid is the result of efforts by numerous individuals from
  11  *  the Internet community; see the CONTRIBUTORS file for full
  12  *  details.   Many organizations have provided support for Squid's
  13  *  development; see the SPONSORS file for full details.  Squid is
  14  *  Copyrighted (C) 2001 by the Regents of the University of
  15  *  California; see the COPYRIGHT file for full details.  Squid
  16  *  incorporates software developed and/or copyrighted by other
  17  *  sources; see the CREDITS file for full details.
  18  *
  19  *  This program is free software; you can redistribute it and/or modify
  20  *  it under the terms of the GNU General Public License as published by
  21  *  the Free Software Foundation; either version 2 of the License, or
  22  *  (at your option) any later version.
  23  *
  24  *  This program is distributed in the hope that it will be useful,
  25  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  26  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27  *  GNU General Public License for more details.
  28  *
  29  *  You should have received a copy of the GNU General Public License
  30  *  along with this program; if not, write to the Free Software
  31  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  32  *
  33  */
  34
  35 #include "squid.h"
  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
  55 #define FM_INITIAL_NUMBER (1<<14)
  56
  57 fileMap *
  58 file_map_create(void)
  59 {
  60     fileMap *fm = (fileMap *)xcalloc(1, sizeof(fileMap));
  61     fm->max_n_files = FM_INITIAL_NUMBER;
  62     fm->nwords = fm->max_n_files >> LONG_BIT_SHIFT;
  63     debugs(8, 3, "file_map_create: creating space for " << fm->max_n_files << " files");
  64     debugs(8, 5, "--> " << fm->nwords << " words of " << sizeof(*fm->file_map) << " bytes each");
  65     fm->file_map = (unsigned long *)xcalloc(fm->nwords, sizeof(*fm->file_map));
  66     /* XXX account fm->file_map */
  67     return fm;
  68 }
  69
  70 static void
  71 file_map_grow(fileMap * fm)
  72 {
  73     int old_sz = fm->nwords * sizeof(*fm->file_map);
  74     void *old_map = fm->file_map;
  75     fm->max_n_files <<= 1;
  76     assert(fm->max_n_files <= (1 << 24));       /* swap_filen is 25 bits, signed */
  77     fm->nwords = fm->max_n_files >> LONG_BIT_SHIFT;
  78     debugs(8, 3, "file_map_grow: creating space for " << fm->max_n_files << " files");
  79     debugs(8, 5, "--> " << fm->nwords << " words of " << sizeof(*fm->file_map) << " bytes each");
  80     fm->file_map = (unsigned long *)xcalloc(fm->nwords, sizeof(*fm->file_map));
  81     debugs(8, 3, "copying " << old_sz << " old bytes");
  82     memcpy(fm->file_map, old_map, old_sz);
  83     xfree(old_map);
  84     /* XXX account fm->file_map */
  85 }
  86
  87 int
  88 file_map_bit_set(fileMap * fm, int file_number)
  89 {
  90     unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
  91
  92     while (file_number >= fm->max_n_files)
  93         file_map_grow(fm);
  94
  95     fm->file_map[file_number >> LONG_BIT_SHIFT] |= bitmask;
  96
  97     fm->n_files_in_map++;
  98
  99     return file_number;
 100 }
 101
 102 /*
 103  * WARNING: file_map_bit_reset does not perform array bounds
 104  * checking!  It assumes that 'file_number' is valid, and that the
 105  * bit is already set.  The caller must verify both of those
 106  * conditions by calling file_map_bit_test() first.
 107  */
 108 void
 109 file_map_bit_reset(fileMap * fm, int file_number)
 110 {
 111     unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
 112     fm->file_map[file_number >> LONG_BIT_SHIFT] &= ~bitmask;
 113     fm->n_files_in_map--;
 114 }
 115
 116 int
 117 file_map_bit_test(fileMap * fm, int file_number)
 118 {
 119     unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
 120
 121     if (file_number >= fm->max_n_files)
 122         return 0;
 123
 124     /* be sure the return value is an int, not a u_long */
 125     return (fm->file_map[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0);
 126 }
 127
 128 int
 129 file_map_allocate(fileMap * fm, int suggestion)
 130 {
 131     int word;
 132     int bit;
 133     int count;
 134
 135     if (suggestion >= fm->max_n_files)
 136         suggestion = 0;
 137
 138     if (!file_map_bit_test(fm, suggestion))
 139         return suggestion;
 140
 141     word = suggestion >> LONG_BIT_SHIFT;
 142
 143     for (count = 0; count < fm->nwords; count++) {
 144         if (fm->file_map[word] != ALL_ONES)
 145             break;
 146
 147         word = (word + 1) % fm->nwords;
 148     }
 149
 150     for (bit = 0; bit < BITS_IN_A_LONG; bit++) {
 151         suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit;
 152
 153         if (!file_map_bit_test(fm, suggestion)) {
 154             return suggestion;
 155         }
 156     }
 157
 158     debugs(8, 3, "growing from file_map_allocate");
 159     file_map_grow(fm);
 160     return file_map_allocate(fm, fm->max_n_files >> 1);
 161 }
 162
 163 void
 164 filemapFreeMemory(fileMap * fm)
 165 {
 166     safe_free(fm->file_map);
 167     safe_free(fm);
 168 }
 169
 170 #ifdef TEST
 171
 172 #define TEST_SIZE 1<<16
 173 main(argc, argv)
 174 {
 175     int i;
 176
 177     fm = file_map_create(TEST_SIZE);
 178
 179     for (i = 0; i < TEST_SIZE; ++i) {
 180         file_map_bit_set(i);
 181         assert(file_map_bit_test(i));
 182         file_map_bit_reset(i);
 183     }
 184 }
 185
 186 #endif