src/filemap.cc

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