src/filemap.cc

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