mm/bitmap2.c

   1 /*
   2  * cacao/mm/bitmap2.c
   3  *
   4  * Copyright (c) 1998 A. Krall, R. Grafl, M. Gschwind, M. Probst, P. Tomsich
   5  * See file COPYRIGHT for information on usage and disclaimer of warranties
   6  *
   7  * Authors: Philipp Tomsich     EMAIL: cacao@complang.tuwien.ac.at
   8  *
   9  * $Id: bitmap2.c 37 1998-11-04 12:39:19Z phil $
  10  */
  11
  12 /*
  13  * This file contains the new bitmap management; it's used within the garbage
  14  * collector and allocator to maintain and access the objectstart-, marker-
  15  * and reference-bitmaps.
  16  *
  17  * Notes:
  18  * 1. For efficencies sake, the memory used for the bitmap is never accessed
  19  *    directly using a heap-offset, but through a pointer offset at bitmap
  20  *    creation; this saves all the subtractions and additions necessary to
  21  *    convert between an address on the heap and an offset into the heap.
  22  *
  23  * 2. I finally added a bitmap_t structure to encapsulate some state
  24  *    information. It contains everything necessary to access the bitmap,
  25  *    caches a few precomputable values and allows for freeing the bitmap.
  26  *
  27  * 3. There's no checks whatsoever to determine whether an address passed is
  28  *    valid or not. These were removed, in order to allow passing the offset
  29  *    address of the bitmap instead of the bitmap structure.
  30  *    I.e., checking addresses to determine whether they are pointing onto
  31  *          the heap must be done before passing them to the bitmap management
  32  *          functions.
  33  *
  34  * 4. Just added exceptions to note 3: Now we have new functions checking the
  35  *    validity of the address to aid in debugging. They are named
  36  *    bitmap_checking_{set|clear|test}bit and will cause an assertion to fail
  37  *    if the addr argument is out of range.
  38  */
  39
  40 #include <assert.h>  /* assert */
  41 #include <stdio.h>   /* printf, fprintf */
  42 #include <stdlib.h>  /* malloc, free */
  43 #include <string.h>  /* memset */
  44 #include <unistd.h>  /* exit */
  45
  46 #include "bitmap2.h"
  47
  48 #warning "bitmap2.c untested in 32-bit mode -- phil."
  49
  50 /* FIXME: I haven't decided, whether to keep these macro definitions here or
  51  *        move them to the header file; they are implementation details, so
  52  *        they should stay here, but moving them would make the SETBIT,
  53  *        TESTBIT and CLEARBIT macros available to the general public. --phil.
  54  */
  55
  56 /* FIXME: HEAPBLOCK_SIZE is an alias for POINTER_ALIGNMENT and should be
  57  *        removed. --phil.
  58  */
  59
  60 /* Please note: All values are log2 */
  61 #if U8_AVAILABLE
  62 #define POINTER_ALIGNMENT                       3  /* alignment of pointers onto the
  63                                                                                   heap == heapblocksize */
  64 #define BITBLOCK_SIZE                           3  /* bytes/BITBLOCK */
  65 #else
  66 #define POINTER_ALIGNMENT                       2
  67 #define BITBLOCK_SIZE                           2
  68 #endif
  69
  70 #define HEAPBLOCK_SIZE                          POINTER_ALIGNMENT
  71 #define BITS_PER_BYTE                           3  /* actually quite self-explanatory */
  72 #define HEAPBLOCKS_PER_BITBLOCK         (BITBLOCK_SIZE + BITS_PER_BYTE)
  73
  74 #define ADDR_TO_BLOCK(addr)                     ((OFFSET_T)(addr) >> (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT))
  75 #define ADDR_TO_OFFSET(addr)            (((OFFSET_T)(addr) & ((1 << (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT)) - 1)) >> HEAPBLOCK_SIZE)
  76 #define BLOCK_TO_ADDR(block)            ((block) << (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT))
  77 #define OFFSET_TO_ADDR(offset)          ((offset) << HEAPBLOCK_SIZE)
  78 #define CALC_BITMAP_SIZE(size)          (((size) + ((1 << (POINTER_ALIGNMENT + HEAPBLOCK_SIZE)) - 1)) >> BITS_PER_BYTE)
  79
  80 #define CHECK_ADDR_ALIGNMENT(addr)      { assert(!((OFFSET_T)addr & ((1 << POINTER_ALIGNMENT) - 1))); }
  81 #define CALC_ZERO_OFFSET(zero)          (((OFFSET_T)(zero) >> (HEAPBLOCK_SIZE + BITS_PER_BYTE)))
  82
  83 #define BIT_AT_OFFSET(offset)           ((BITBLOCK)1 << (offset))
  84 #define BIT_FOR_ADDR(addr)                      BIT_AT_OFFSET(ADDR_TO_OFFSET((addr)))
  85
  86 #define SETBIT(bitmap, addr)            { bitmap[ADDR_TO_BLOCK(addr)] |=  BIT_FOR_ADDR(addr); }
  87 #define CLEARBIT(bitmap, addr)          { bitmap[ADDR_TO_BLOCK(addr)] &= ~BIT_FOR_ADDR(addr); }
  88 #define TESTBIT(bitmap, addr)           ( (bitmap[ADDR_TO_BLOCK(addr)] & BIT_FOR_ADDR(addr)) != 0 )
  89
  90
  91 /* Operations per macro (relative cost):
  92  *
  93  *   Macro            | & | &= | |= | ~ | >> | << | + | dereference |
  94  *   -----------------+---+----+----+---+----+----+---+-------------+
  95  *   ADDR_TO_BLOCK    | 0 |  0 |  0 | 0 |  1 |  0 | 0 |           0 |
  96  *   ADDR_TO_OFFSET   | 1 |  0 |  0 | 0 |  1 |  0 | 0 |           0 |
  97  *   BLOCK_TO_ADDR    | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
  98  *   OFFSET_TO_ADDR   | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
  99  *   CALC_BITMAP_SIZE | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
 100  *   CALC_ZERO_OFFSET | 0 |  0 |  0 | 0 |  1 |  0 | 0 |           0 |
 101  *   -----------------+---+----+----+---+----+----+---+-------------+
 102  *   BIT_AT_OFFSET    | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
 103  *   BIT_FOR_ADDR     | 1 |  0 |  0 | 0 |  1 |  1 | 0 |           0 |
 104  *   -----------------+---+----+----+---+----+----+---+-------------+
 105  *   SETBIT           | 1 |  0 |  1 | 0 |  2 |  1 | 0 |           1 |
 106  *   CLEARBIT         | 1 |  1 |  0 | 1 |  2 |  1 | 0 |           1 |
 107  *   TESTBIT          | 2 |  0 |  0 | 0 |  2 |  1 | 0 |           1 |
 108  */
 109
 110
 111 __inline__
 112 void bitmap_setbit(BITBLOCK* bitmap,
 113                                    void* addr)
 114 {
 115         SETBIT(bitmap, addr);
 116 }
 117
 118 __inline__
 119 void bitmap_clearbit(BITBLOCK* bitmap,
 120                                          void* addr)
 121 {
 122         CLEARBIT(bitmap, addr);
 123 }
 124
 125 __inline__
 126 bool bitmap_testbit(BITBLOCK* bitmap,
 127                                         void* addr)
 128 {
 129         return TESTBIT(bitmap, addr);
 130 }
 131
 132 __inline__
 133 static
 134 void bitmap_boundscheck(bitmap_t* bitmap,
 135                                                 void*     addr)
 136 {
 137         /* check the lower bound */
 138         assert((void*)&bitmap->bitmap[ADDR_TO_BLOCK(addr)] >= bitmap->bitmap_memory);
 139         /* check the upper bound */
 140         assert(&bitmap->bitmap[
 141                                                    ADDR_TO_BLOCK(addr)]
 142                    <= &bitmap->bitmap[bitmap->bitmap_top_block]);
 143         assert(addr < bitmap->bitmap_beyond_addr); /* a stricter way to check the upper bound */
 144 }
 145
 146 __inline__
 147 void bitmap_checking_setbit(bitmap_t* bitmap,
 148                                                         void*     addr)
 149 {
 150         bitmap_boundscheck(bitmap, addr);
 151         bitmap_setbit(bitmap->bitmap, addr);
 152 }
 153
 154 __inline__
 155 void bitmap_checking_clearbit(bitmap_t* bitmap,
 156                                                           void*   addr)
 157 {
 158         bitmap_boundscheck(bitmap, addr);
 159         bitmap_clearbit(bitmap->bitmap, addr);
 160 }
 161
 162 __inline__
 163 bool bitmap_checking_testbit(bitmap_t* bitmap,
 164                                                          void*    addr)
 165 {
 166         bitmap_boundscheck(bitmap, addr);
 167         return bitmap_testbit(bitmap->bitmap, addr);
 168 }
 169
 170 __inline__
 171 void bitmap_clear(bitmap_t* bitmap)
 172 {
 173         memset(bitmap->bitmap_memory, 0, bitmap->bytesize);
 174 }
 175
 176 __inline__
 177 bitmap_t* bitmap_allocate(void*         zero_addr,
 178                                                   OFFSET_T      size)
 179 {
 180         bitmap_t*  bitmap;
 181
 182         unsigned long bytesize = CALC_BITMAP_SIZE(size);                                         /* align */
 183         bitmap = (bitmap_t*)malloc(sizeof(bitmap_t));
 184
 185         CHECK_ADDR_ALIGNMENT(zero_addr);                        /* ensure correct alignment for zero_addr */
 186
 187         bitmap->bytesize = bytesize;
 188         bitmap->bitmap_memory = malloc(bytesize);
 189         bitmap->bitmap = bitmap->bitmap_memory - CALC_ZERO_OFFSET(zero_addr);   /* offset for fast access */
 190
 191         bitmap->bitmap_beyond_addr = zero_addr + size;
 192         bitmap->bitmap_top_block = ADDR_TO_BLOCK(bitmap->bitmap_beyond_addr - sizeof(BITBLOCK));
 193
 194         if (!bitmap->bitmap_memory) {
 195                 /* handle error -- unable to allocate enough memory */
 196                 fprintf(stderr, "bitmap2.c: Failed to allocate memory for a bitmap.\n");
 197                 exit(-1);  /* FIXME: I should probably call some sort of cacao-wide "panic" function ?! -- phil. */
 198         }
 199
 200         bitmap_clear(bitmap);
 201
 202         return bitmap;
 203 }
 204
 205 __inline__
 206 void bitmap_release(bitmap_t* bitmap)
 207 {
 208         if (bitmap) {
 209                 if (bitmap->bitmap_memory)
 210                         free(bitmap->bitmap_memory);
 211                 free(bitmap);
 212         }
 213 }
 214
 215
 216 __inline__
 217 static
 218 int offset_for_lowest(BITBLOCK i)
 219 {
 220         /* Maintainer, don't despair!
 221          *
 222          * The OFFSET_TO_ADDR adjusts an argument according to the size of heap-allocation blocks,
 223          * so that the resulting value can be used as an offset to a pointer.
 224          * I.e.: addr + OFFSET_TO_ADDR(i) is equivalent to addr + (sizeof(heap_block) * i)
 225          *
 226          * The definition of lowest just looks inefficient, everything should be expanded at
 227          * compile-time, though. -- phil.
 228          */
 229
 230         static signed char lowest[256] = {
 231                 OFFSET_TO_ADDR(0),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 232                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 233                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 234                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 235                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 236                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 237                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 238                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 239                 OFFSET_TO_ADDR(6),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 240                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 241                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 242                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 243                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 244                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 245                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 246                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 247                 OFFSET_TO_ADDR(7),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 248                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 249                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 250                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 251                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 252                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 253                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 254                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 255                 OFFSET_TO_ADDR(6),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 256                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 257                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 258                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 259                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 260                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 261                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 262                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 263         };
 264
 265 #if U8_AVAILABLE
 266         if (i & 0xffffffffffULL)
 267 #endif
 268                 if (i & 0xffffUL)
 269                         if (i & 0xffUL)
 270                                 return OFFSET_TO_ADDR(0) + lowest[(unsigned char)i];
 271                         else
 272                                 return OFFSET_TO_ADDR(8) + lowest[(unsigned char)(i>>8)];
 273                 else
 274                         if (i & 0xff0000UL)
 275                                 return OFFSET_TO_ADDR(16) + lowest[(unsigned char)(i>>16)];
 276                         else
 277                                 return OFFSET_TO_ADDR(24) + lowest[(unsigned char)(i>>24)];
 278 #if U8_AVAILABLE
 279         else
 280                 if (i & 0xffff00000000ULL)
 281                         if (i & 0xff00000000ULL)
 282                                 return OFFSET_TO_ADDR(32) + lowest[(unsigned char)(i>>32)];
 283                         else
 284                                 return OFFSET_TO_ADDR(40) + lowest[(unsigned char)(i>>40)];
 285                 else
 286                         if (i & 0xff000000000000ULL)
 287                                 return OFFSET_TO_ADDR(48) + lowest[(unsigned char)(i>>48)];
 288                         else
 289                                 return OFFSET_TO_ADDR(56) + lowest[(unsigned char)(i>>56)];
 290 #endif
 291 }
 292
 293 __inline__
 294 void*
 295 bitmap_find_next_setbit(bitmap_t* bitmap,
 296                                                 void*     addr)
 297 {
 298         OFFSET_T  block = ADDR_TO_BLOCK(addr);
 299         OFFSET_T  offset = ADDR_TO_OFFSET(addr);
 300         BITBLOCK  pattern;
 301
 302         bitmap_boundscheck(bitmap, addr);
 303
 304         /* 1. check the current block, starting from the bit indicated by addr */
 305         pattern = bitmap->bitmap[block] >> offset;
 306         if (pattern)
 307                 return (void*)(addr + offset_for_lowest(pattern));
 308
 309         /* 2. iteratively check block by block until the end of the bitmap */
 310         while (block < bitmap->bitmap_top_block) {
 311                 pattern = bitmap->bitmap[++block];
 312
 313                 if (pattern)
 314                         return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
 315         }
 316
 317         /* 3. failed to find a set bit... */
 318         return bitmap->bitmap_beyond_addr;
 319 }
 320
 321 __inline__
 322 void*
 323 bitmap_find_next_combination_set_unset(bitmap_t* bitmap,
 324                                                                            bitmap_t* invertedmap,
 325                                                                            void*     addr)
 326 {
 327         OFFSET_T  block = ADDR_TO_BLOCK(addr);
 328         OFFSET_T  offset = ADDR_TO_OFFSET(addr);
 329         BITBLOCK  pattern;
 330
 331         bitmap_boundscheck(bitmap, addr);
 332
 333         /* 1. check the current block, starting from the bit indicated by addr */
 334         pattern = (bitmap->bitmap[block] & ~invertedmap->bitmap[block]) >> offset;
 335         if (pattern)
 336                 return (void*)(addr + offset_for_lowest(pattern));
 337
 338         /* 2. iteratively check block by block until the end of the bitmap */
 339         while (block < bitmap->bitmap_top_block) {
 340                 pattern = bitmap->bitmap[++block] & ~invertedmap->bitmap[block];
 341
 342                 if (pattern)
 343                         return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
 344         }
 345
 346         /* 3. failed to find a combination... */
 347         return bitmap->bitmap_beyond_addr;
 348 }
 349
 350 /*
 351  * These are local overrides for various environment variables in Emacs.
 352  * Please do not remove this and leave it at the end of the file, where
 353  * Emacs will automagically detect them.
 354  * ---------------------------------------------------------------------
 355  * Local variables:
 356  * mode: c
 357  * indent-tabs-mode: t
 358  * c-basic-offset: 4
 359  * tab-width: 4
 360  * End:
 361  */