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 93 1998-11-25 11:49:36Z 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 /* TODO:
  41  *   Rewrite bitmap_find_next_setbit and bitmap_find_next_combination_set_unset
  42  *   to use more pointer arithmetic and less indexed accesses. --phil.
  43  *   Reason: Most compilers are simply dumb, while some programmers are not!
  44  */
  45
  46 #include <assert.h>  /* assert */
  47 #include <stdio.h>   /* printf, fprintf */
  48 #include <stdlib.h>  /* malloc, free */
  49 #include <string.h>  /* memset */
  50 #include <unistd.h>  /* exit */
  51
  52 #include "bitmap2.h"
  53
  54 #warning "bitmap2.c untested in 32-bit mode -- phil."
  55
  56 /* FIXME: I haven't decided, whether to keep these macro definitions here or
  57  *        move them to the header file; they are implementation details, so
  58  *        they should stay here, but moving them would make the SETBIT,
  59  *        TESTBIT and CLEARBIT macros available to the general public. --phil.
  60  */
  61
  62 /* FIXME: HEAPBLOCK_SIZE is an alias for POINTER_ALIGNMENT and should be
  63  *        removed. --phil.
  64  */
  65
  66 /* Please note: All values are log2 */
  67 #if U8_AVAILABLE
  68 #define POINTER_ALIGNMENT                       3  /* alignment of pointers onto the
  69                                                                                   heap == heapblocksize */
  70 #define BITBLOCK_SIZE                           3  /* bytes/BITBLOCK */
  71 #else
  72 #define POINTER_ALIGNMENT                       2
  73 #define BITBLOCK_SIZE                           2
  74 #endif
  75
  76 #define HEAPBLOCK_SIZE                          POINTER_ALIGNMENT
  77 #define BITS_PER_BYTE                           3  /* actually quite self-explanatory */
  78 #define HEAPBLOCKS_PER_BITBLOCK         (BITBLOCK_SIZE + BITS_PER_BYTE)
  79
  80 #define ADDR_TO_BLOCK(addr)                     ((OFFSET_T)(addr) >> (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT))
  81 #define ADDR_TO_OFFSET(addr)            (((OFFSET_T)(addr) & ((1 << (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT)) - 1)) >> HEAPBLOCK_SIZE)
  82 #define BLOCK_TO_ADDR(block)            ((block) << (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT))
  83 #define OFFSET_TO_ADDR(offset)          ((offset) << HEAPBLOCK_SIZE)
  84 #define CALC_BITMAP_SIZE(size)          (((size) + ((1 << (POINTER_ALIGNMENT + HEAPBLOCK_SIZE)) - 1)) >> BITS_PER_BYTE)
  85
  86 #define CHECK_ADDR_ALIGNMENT(addr)      { assert(!((OFFSET_T)addr & ((1 << POINTER_ALIGNMENT) - 1))); }
  87 #define CALC_ZERO_OFFSET(zero)          (((OFFSET_T)(zero) >> (HEAPBLOCK_SIZE + BITS_PER_BYTE)))
  88
  89 #define BIT_AT_OFFSET(offset)           ((BITBLOCK)1 << (offset))
  90 #define BIT_FOR_ADDR(addr)                      BIT_AT_OFFSET(ADDR_TO_OFFSET((addr)))
  91
  92 #define SETBIT(bitmap, addr)            { bitmap[ADDR_TO_BLOCK(addr)] |=  BIT_FOR_ADDR(addr); }
  93 #define CLEARBIT(bitmap, addr)          { bitmap[ADDR_TO_BLOCK(addr)] &= ~BIT_FOR_ADDR(addr); }
  94 #define TESTBIT(bitmap, addr)           ( (bitmap[ADDR_TO_BLOCK(addr)] & BIT_FOR_ADDR(addr)) != 0 )
  95
  96
  97 /* Operations per macro (relative cost):
  98  *
  99  *   Macro            | & | &= | |= | ~ | >> | << | + | dereference |
 100  *   -----------------+---+----+----+---+----+----+---+-------------+
 101  *   ADDR_TO_BLOCK    | 0 |  0 |  0 | 0 |  1 |  0 | 0 |           0 |
 102  *   ADDR_TO_OFFSET   | 1 |  0 |  0 | 0 |  1 |  0 | 0 |           0 |
 103  *   BLOCK_TO_ADDR    | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
 104  *   OFFSET_TO_ADDR   | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
 105  *   CALC_BITMAP_SIZE | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
 106  *   CALC_ZERO_OFFSET | 0 |  0 |  0 | 0 |  1 |  0 | 0 |           0 |
 107  *   -----------------+---+----+----+---+----+----+---+-------------+
 108  *   BIT_AT_OFFSET    | 0 |  0 |  0 | 0 |  0 |  1 | 0 |           0 |
 109  *   BIT_FOR_ADDR     | 1 |  0 |  0 | 0 |  1 |  1 | 0 |           0 |
 110  *   -----------------+---+----+----+---+----+----+---+-------------+
 111  *   SETBIT           | 1 |  0 |  1 | 0 |  2 |  1 | 0 |           1 |
 112  *   CLEARBIT         | 1 |  1 |  0 | 1 |  2 |  1 | 0 |           1 |
 113  *   TESTBIT          | 2 |  0 |  0 | 0 |  2 |  1 | 0 |           1 |
 114  */
 115
 116
 117 __inline__
 118 void bitmap_setbit(BITBLOCK* bitmap,
 119                                    void* addr)
 120 {
 121         SETBIT(bitmap, addr);
 122 }
 123
 124 __inline__
 125 void bitmap_clearbit(BITBLOCK* bitmap,
 126                                          void* addr)
 127 {
 128         CLEARBIT(bitmap, addr);
 129 }
 130
 131 __inline__
 132 bool bitmap_testbit(BITBLOCK* bitmap,
 133                                         void* addr)
 134 {
 135         return TESTBIT(bitmap, addr);
 136 }
 137
 138 __inline__
 139 static
 140 void bitmap_boundscheck(bitmap_t* bitmap,
 141                                                 void*     addr)
 142 {
 143         /* check the lower bound */
 144         assert((void*)&bitmap->bitmap[ADDR_TO_BLOCK(addr)] >= bitmap->bitmap_memory);
 145
 146         /* check the upper bound */
 147         assert(&bitmap->bitmap[ADDR_TO_BLOCK(addr)] <= &bitmap->bitmap[bitmap->bitmap_top_block]);
 148         assert(addr < bitmap->bitmap_beyond_addr); /* a stricter way to check the upper bound */
 149 }
 150
 151 __inline__
 152 void bitmap_checking_setbit(bitmap_t* bitmap,
 153                                                         void*     addr)
 154 {
 155         bitmap_boundscheck(bitmap, addr);
 156         bitmap_setbit(bitmap->bitmap, addr);
 157 }
 158
 159 __inline__
 160 void bitmap_checking_clearbit(bitmap_t* bitmap,
 161                                                           void*   addr)
 162 {
 163         bitmap_boundscheck(bitmap, addr);
 164         bitmap_clearbit(bitmap->bitmap, addr);
 165 }
 166
 167 __inline__
 168 bool bitmap_checking_testbit(bitmap_t* bitmap,
 169                                                          void*    addr)
 170 {
 171         bitmap_boundscheck(bitmap, addr);
 172         return bitmap_testbit(bitmap->bitmap, addr);
 173 }
 174
 175 __inline__
 176 void bitmap_clear(bitmap_t* bitmap)
 177 {
 178         memset(bitmap->bitmap_memory, 0, bitmap->bytesize);
 179 }
 180
 181 __inline__
 182 bitmap_t* bitmap_allocate(void*         zero_addr,
 183                                                   OFFSET_T      size)
 184 {
 185         bitmap_t*  bitmap;
 186
 187         unsigned long bytesize = CALC_BITMAP_SIZE(size);                                         /* align */
 188         bitmap = (bitmap_t*)malloc(sizeof(bitmap_t));
 189
 190         CHECK_ADDR_ALIGNMENT(zero_addr);                        /* ensure correct alignment for zero_addr */
 191
 192         bitmap->bytesize = bytesize;
 193         bitmap->bitmap_memory = malloc(bytesize);
 194         bitmap->bitmap = (void*)((long)bitmap->bitmap_memory - CALC_ZERO_OFFSET(zero_addr));   /* offset for fast access */
 195
 196         bitmap->bitmap_beyond_addr = (void*)((long)zero_addr + size);
 197         bitmap->bitmap_top_block = ADDR_TO_BLOCK((long)bitmap->bitmap_beyond_addr - sizeof(BITBLOCK));
 198
 199         if (!bitmap->bitmap_memory) {
 200                 /* handle error -- unable to allocate enough memory */
 201                 fprintf(stderr, "bitmap2.c: Failed to allocate memory for a bitmap.\n");
 202                 exit(-1);  /* FIXME: I should probably call some sort of cacao-wide "panic" function ?! -- phil. */
 203         }
 204
 205         bitmap_clear(bitmap);
 206
 207         return bitmap;
 208 }
 209
 210 __inline__
 211 void bitmap_release(bitmap_t* bitmap)
 212 {
 213         if (bitmap) {
 214                 if (bitmap->bitmap_memory)
 215                         free(bitmap->bitmap_memory);
 216                 free(bitmap);
 217         }
 218 }
 219
 220
 221 __inline__
 222 static
 223 int offset_for_lowest(BITBLOCK i)
 224 {
 225         /* Maintainer, don't despair!
 226          *
 227          * The OFFSET_TO_ADDR adjusts an argument according to the size of heap-allocation blocks,
 228          * so that the resulting value can be used as an offset to a pointer.
 229          * I.e.: addr + OFFSET_TO_ADDR(i) is equivalent to addr + (sizeof(heap_block) * i)
 230          *
 231          * The definition of lowest just looks inefficient, everything should be expanded at
 232          * compile-time, though. -- phil.
 233          */
 234
 235         static signed char lowest[256] = {
 236                 OFFSET_TO_ADDR(0),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 237                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 238                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 239                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 240                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 241                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 242                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 243                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 244                 OFFSET_TO_ADDR(6),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 245                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 246                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 247                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 248                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 249                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 250                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 251                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 252                 OFFSET_TO_ADDR(7),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 253                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 254                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 255                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 256                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 257                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 258                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 259                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 260                 OFFSET_TO_ADDR(6),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 261                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 262                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 263                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 264                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 265                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 266                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 267                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 268         };
 269
 270 #if U8_AVAILABLE
 271         if (i & 0xffffffffULL)
 272 #endif
 273                 if (i & 0xffffUL)
 274                         if (i & 0xffUL)
 275                                 return OFFSET_TO_ADDR(0) + lowest[(unsigned char)i];
 276                         else
 277                                 return OFFSET_TO_ADDR(8) + lowest[(unsigned char)(i>>8)];
 278                 else
 279                         if (i & 0xff0000UL)
 280                                 return OFFSET_TO_ADDR(16) + lowest[(unsigned char)(i>>16)];
 281                         else
 282                                 return OFFSET_TO_ADDR(24) + lowest[(unsigned char)(i>>24)];
 283 #if U8_AVAILABLE
 284         else
 285                 if (i & 0xffff00000000ULL)
 286                         if (i & 0xff00000000ULL)
 287                                 return OFFSET_TO_ADDR(32) + lowest[(unsigned char)(i>>32)];
 288                         else
 289                                 return OFFSET_TO_ADDR(40) + lowest[(unsigned char)(i>>40)];
 290                 else
 291                         if (i & 0xff000000000000ULL)
 292                                 return OFFSET_TO_ADDR(48) + lowest[(unsigned char)(i>>48)];
 293                         else
 294                                 return OFFSET_TO_ADDR(56) + lowest[(unsigned char)(i>>56)];
 295 #endif
 296 }
 297
 298 __inline__
 299 void*
 300 bitmap_find_next_setbit(bitmap_t* bitmap,
 301                                                 void*     addr)
 302 {
 303         OFFSET_T  block = ADDR_TO_BLOCK(addr);
 304         OFFSET_T  offset = ADDR_TO_OFFSET(addr);
 305         BITBLOCK  pattern;
 306
 307         bitmap_boundscheck(bitmap, addr);
 308
 309         /* 1. check the current block, starting from the bit indicated by addr */
 310         pattern = bitmap->bitmap[block] >> offset;
 311         if (pattern)
 312                 return (void*)((long)addr + offset_for_lowest(pattern));
 313
 314         /* 2. iteratively check block by block until the end of the bitmap */
 315         while (block < bitmap->bitmap_top_block) {
 316                 pattern = bitmap->bitmap[++block];
 317
 318                 if (pattern)
 319                         return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
 320         }
 321
 322         /* 3. failed to find a set bit... */
 323         return bitmap->bitmap_beyond_addr;
 324 }
 325
 326 __inline__
 327 void*
 328 bitmap_find_next_combination_set_unset(bitmap_t* bitmap,
 329                                                                            bitmap_t* invertedmap,
 330                                                                            void*     addr)
 331 {
 332         OFFSET_T  block = ADDR_TO_BLOCK(addr);
 333         OFFSET_T  offset = ADDR_TO_OFFSET(addr);
 334         BITBLOCK  pattern;
 335
 336         bitmap_boundscheck(bitmap, addr);
 337         bitmap_boundscheck(invertedmap, addr);
 338
 339         /* 1. check the current block, starting from the bit indicated by addr */
 340         pattern = (bitmap->bitmap[block] & ~invertedmap->bitmap[block]) >> offset;
 341         if (pattern)
 342                 return (void*)((long)addr + offset_for_lowest(pattern));
 343
 344         /* 2. iteratively check block by block until the end of the bitmap */
 345         while (block < bitmap->bitmap_top_block) {
 346                 pattern = bitmap->bitmap[++block] & ~invertedmap->bitmap[block];
 347
 348                 if (pattern)
 349                         return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
 350         }
 351
 352         /* 3. failed to find a combination... */
 353         return bitmap->bitmap_beyond_addr;
 354 }
 355
 356 __inline__
 357 void
 358 bitmap_mask_with_bitmap(bitmap_t* bitmap,
 359                                                 bitmap_t* mask)
 360 {
 361         BITBLOCK*       bits = (BITBLOCK*)bitmap->bitmap_memory;
 362         BITBLOCK*       maskbits = (BITBLOCK*)mask->bitmap_memory;
 363         BITBLOCK*       end = (void*)((unsigned long)bits + bitmap->bytesize);
 364
 365         assert(bitmap->bytesize == mask->bytesize);
 366
 367         while (bits < end)
 368                 *(bits++) &= *(maskbits++);
 369 }
 370
 371 /*
 372  * These are local overrides for various environment variables in Emacs.
 373  * Please do not remove this and leave it at the end of the file, where
 374  * Emacs will automagically detect them.
 375  * ---------------------------------------------------------------------
 376  * Local variables:
 377  * mode: c
 378  * indent-tabs-mode: t
 379  * c-basic-offset: 4
 380  * tab-width: 4
 381  * End:
 382  */