src/filemap.cc

   1 /*
   2  * $Id: filemap.cc,v 1.11 1996/09/20 06:28:41 wessels Exp $
   3  *
   4  * DEBUG: section 8     Swap File Bitmap
   5  * AUTHOR: Harvest Derived
   6  *
   7  * SQUID Internet Object Cache  http://www.nlanr.net/Squid/
   8  * --------------------------------------------------------
   9  *
  10  *  Squid is the result of efforts by numerous individuals from the
  11  *  Internet community.  Development is led by Duane Wessels of the
  12  *  National Laboratory for Applied Network Research and funded by
  13  *  the National Science Foundation.
  14  *
  15  *  This program is free software; you can redistribute it and/or modify
  16  *  it under the terms of the GNU General Public License as published by
  17  *  the Free Software Foundation; either version 2 of the License, or
  18  *  (at your option) any later version.
  19  *
  20  *  This program is distributed in the hope that it will be useful,
  21  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  *  GNU General Public License for more details.
  24  *
  25  *  You should have received a copy of the GNU General Public License
  26  *  along with this program; if not, write to the Free Software
  27  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  28  *
  29  */
  30
  31 /*
  32  * Copyright (c) 1994, 1995.  All rights reserved.
  33  *
  34  *   The Harvest software was developed by the Internet Research Task
  35  *   Force Research Group on Resource Discovery (IRTF-RD):
  36  *
  37  *         Mic Bowman of Transarc Corporation.
  38  *         Peter Danzig of the University of Southern California.
  39  *         Darren R. Hardy of the University of Colorado at Boulder.
  40  *         Udi Manber of the University of Arizona.
  41  *         Michael F. Schwartz of the University of Colorado at Boulder.
  42  *         Duane Wessels of the University of Colorado at Boulder.
  43  *
  44  *   This copyright notice applies to software in the Harvest
  45  *   ``src/'' directory only.  Users should consult the individual
  46  *   copyright notices in the ``components/'' subdirectories for
  47  *   copyright information about other software bundled with the
  48  *   Harvest source code distribution.
  49  *
  50  * TERMS OF USE
  51  *
  52  *   The Harvest software may be used and re-distributed without
  53  *   charge, provided that the software origin and research team are
  54  *   cited in any use of the system.  Most commonly this is
  55  *   accomplished by including a link to the Harvest Home Page
  56  *   (http://harvest.cs.colorado.edu/) from the query page of any
  57  *   Broker you deploy, as well as in the query result pages.  These
  58  *   links are generated automatically by the standard Broker
  59  *   software distribution.
  60  *
  61  *   The Harvest software is provided ``as is'', without express or
  62  *   implied warranty, and with no support nor obligation to assist
  63  *   in its use, correction, modification or enhancement.  We assume
  64  *   no liability with respect to the infringement of copyrights,
  65  *   trade secrets, or any patents, and are not responsible for
  66  *   consequential damages.  Proper use of the Harvest software is
  67  *   entirely the responsibility of the user.
  68  *
  69  * DERIVATIVE WORKS
  70  *
  71  *   Users may make derivative works from the Harvest software, subject
  72  *   to the following constraints:
  73  *
  74  *     - You must include the above copyright notice and these
  75  *       accompanying paragraphs in all forms of derivative works,
  76  *       and any documentation and other materials related to such
  77  *       distribution and use acknowledge that the software was
  78  *       developed at the above institutions.
  79  *
  80  *     - You must notify IRTF-RD regarding your distribution of
  81  *       the derivative work.
  82  *
  83  *     - You must clearly notify users that your are distributing
  84  *       a modified version and not the original Harvest software.
  85  *
  86  *     - Any derivative product is also subject to these copyright
  87  *       and use restrictions.
  88  *
  89  *   Note that the Harvest software is NOT in the public domain.  We
  90  *   retain copyright, as specified above.
  91  *
  92  * HISTORY OF FREE SOFTWARE STATUS
  93  *
  94  *   Originally we required sites to license the software in cases
  95  *   where they were going to build commercial products/services
  96  *   around Harvest.  In June 1995 we changed this policy.  We now
  97  *   allow people to use the core Harvest software (the code found in
  98  *   the Harvest ``src/'' directory) for free.  We made this change
  99  *   in the interest of encouraging the widest possible deployment of
 100  *   the technology.  The Harvest software is really a reference
 101  *   implementation of a set of protocols and formats, some of which
 102  *   we intend to standardize.  We encourage commercial
 103  *   re-implementations of code complying to this set of standards.
 104  */
 105
 106 #include "squid.h"
 107
 108 /* Number of bits in a long */
 109 #if SIZEOF_LONG == 8
 110 #define LONG_BIT_SHIFT 6
 111 #define BITS_IN_A_LONG 0x40
 112 #define LONG_BIT_MASK  0x3F
 113 #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF
 114 #elif SIZEOF_LONG == 4
 115 #define LONG_BIT_SHIFT 5
 116 #define BITS_IN_A_LONG 0x20
 117 #define LONG_BIT_MASK  0x1F
 118 #define ALL_ONES (unsigned long) 0xFFFFFFFF
 119 #else
 120 #define LONG_BIT_SHIFT 5
 121 #define BITS_IN_A_LONG 0x20
 122 #define LONG_BIT_MASK  0x1F
 123 #define ALL_ONES (unsigned long) 0xFFFFFFFF
 124 #endif
 125
 126 extern int storeGetSwapSpace _PARAMS((int));
 127 extern void fatal_dump _PARAMS((char *));
 128
 129 static fileMap *fm = NULL;
 130
 131 fileMap *
 132 file_map_create(int n)
 133 {
 134     fm = xcalloc(1, sizeof(fileMap));
 135     fm->max_n_files = n;
 136     fm->nwords = n >> LONG_BIT_SHIFT;
 137     debug(8, 1, "file_map_create: creating space for %d files\n", n);
 138     debug(8, 5, "--> %d words of %d bytes each\n",
 139         fm->nwords, sizeof(unsigned long));
 140     fm->file_map = xcalloc(fm->nwords, sizeof(unsigned long));
 141     meta_data.misc += fm->nwords * sizeof(unsigned long);
 142     return (fm);
 143 }
 144
 145 int
 146 file_map_bit_set(int file_number)
 147 {
 148     unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
 149
 150 #ifdef XTRA_DEBUG
 151     if (fm->file_map[file_number >> LONG_BIT_SHIFT] & bitmask)
 152         debug(8, 0, "file_map_bit_set: WARNING: file number %d is already set!\n",
 153             file_number);
 154 #endif
 155
 156     fm->file_map[file_number >> LONG_BIT_SHIFT] |= bitmask;
 157
 158     fm->n_files_in_map++;
 159     if (!fm->toggle && (fm->n_files_in_map > ((fm->max_n_files * 7) >> 3))) {
 160         fm->toggle++;
 161         debug(8, 0, "You should increment MAX_SWAP_FILE\n");
 162     } else if (fm->n_files_in_map > (fm->max_n_files - 100)) {
 163         debug(8, 0, "You've run out of swap file numbers. Freeing 1MB\n");
 164         storeGetSwapSpace(1000000);
 165     }
 166     return (file_number);
 167 }
 168
 169 void
 170 file_map_bit_reset(int file_number)
 171 {
 172     unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
 173
 174     fm->file_map[file_number >> LONG_BIT_SHIFT] &= ~bitmask;
 175     fm->n_files_in_map--;
 176 }
 177
 178 int
 179 file_map_bit_test(int file_number)
 180 {
 181     unsigned long bitmask = (1L << (file_number & LONG_BIT_MASK));
 182     /* be sure the return value is an int, not a u_long */
 183     return (fm->file_map[file_number >> LONG_BIT_SHIFT] & bitmask ? 1 : 0);
 184 }
 185
 186 int
 187 file_map_allocate(int suggestion)
 188 {
 189     int word;
 190     int bit;
 191     int count;
 192
 193     if (!file_map_bit_test(suggestion)) {
 194         fm->last_file_number_allocated = suggestion;
 195         return file_map_bit_set(suggestion);
 196     }
 197     word = suggestion >> LONG_BIT_SHIFT;
 198     for (count = 0; count < fm->nwords; count++) {
 199         if (fm->file_map[word] != ALL_ONES)
 200             break;
 201         word = (word + 1) % fm->nwords;
 202     }
 203
 204     for (bit = 0; bit < BITS_IN_A_LONG; bit++) {
 205         suggestion = ((unsigned long) word << LONG_BIT_SHIFT) | bit;
 206         if (!file_map_bit_test(suggestion)) {
 207             fm->last_file_number_allocated = suggestion;
 208             return file_map_bit_set(suggestion);
 209         }
 210     }
 211
 212     debug(8, 0, "file_map_allocate: All %d files are in use!\n", fm->max_n_files);
 213     debug(8, 0, "You need to recompile with a larger value for MAX_SWAP_FILE\n");
 214     fatal_dump(NULL);
 215     return (0);                 /* NOTREACHED */
 216 }
 217
 218 #ifdef TEST
 219
 220 #define TEST_SIZE 1<<16
 221 main(argc, argv)
 222 {
 223     int i;
 224
 225     fm = file_map_create(TEST_SIZE);
 226
 227     for (i = 0; i < TEST_SIZE; ++i) {
 228         file_map_bit_set(i);
 229         if (!file_map_bit_test(i))
 230             fatal_dump(NULL);
 231         file_map_bit_reset(i);
 232     }
 233 }
 234 #endif