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 120 1999-01-20 15:41:38Z andi $
  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 void bitmap_setbit(BITBLOCK* bitmap,
 118                                    void* addr)
 119 {
 120         SETBIT(bitmap, addr);
 121 }
 122
 123 void bitmap_clearbit(BITBLOCK* bitmap,
 124                                          void* addr)
 125 {
 126         CLEARBIT(bitmap, addr);
 127 }
 128
 129 bool bitmap_testbit(BITBLOCK* bitmap,
 130                                         void* addr)
 131 {
 132         return TESTBIT(bitmap, addr);
 133 }
 134
 135 static
 136 void bitmap_boundscheck(bitmap_t* bitmap,
 137                                                 void*     addr)
 138 {
 139         /* check the lower bound */
 140         assert((void*)&bitmap->bitmap[ADDR_TO_BLOCK(addr)] >= bitmap->bitmap_memory);
 141
 142         /* check the upper bound */
 143         assert(&bitmap->bitmap[ADDR_TO_BLOCK(addr)] <= &bitmap->bitmap[bitmap->bitmap_top_block]);
 144         assert(addr < bitmap->bitmap_beyond_addr); /* a stricter way to check the upper bound */
 145 }
 146
 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 void bitmap_checking_clearbit(bitmap_t* bitmap,
 155                                                           void*   addr)
 156 {
 157         bitmap_boundscheck(bitmap, addr);
 158         bitmap_clearbit(bitmap->bitmap, addr);
 159 }
 160
 161 bool bitmap_checking_testbit(bitmap_t* bitmap,
 162                                                          void*    addr)
 163 {
 164         bitmap_boundscheck(bitmap, addr);
 165         return bitmap_testbit(bitmap->bitmap, addr);
 166 }
 167
 168 void bitmap_clear(bitmap_t* bitmap)
 169 {
 170         memset(bitmap->bitmap_memory, 0, bitmap->bytesize);
 171 }
 172
 173 bitmap_t* bitmap_allocate(void*         zero_addr,
 174                                                   OFFSET_T      size)
 175 {
 176         bitmap_t*  bitmap;
 177
 178         unsigned long bytesize = CALC_BITMAP_SIZE(size);                                         /* align */
 179         bitmap = (bitmap_t*)malloc(sizeof(bitmap_t));
 180
 181         CHECK_ADDR_ALIGNMENT(zero_addr);                        /* ensure correct alignment for zero_addr */
 182
 183         bitmap->bytesize = bytesize;
 184         bitmap->bitmap_memory = malloc(bytesize);
 185         bitmap->bitmap = (void*)((long)bitmap->bitmap_memory - CALC_ZERO_OFFSET(zero_addr));   /* offset for fast access */
 186
 187         bitmap->bitmap_beyond_addr = (void*)((long)zero_addr + size);
 188         bitmap->bitmap_top_block = ADDR_TO_BLOCK((long)bitmap->bitmap_beyond_addr - sizeof(BITBLOCK));
 189
 190         if (!bitmap->bitmap_memory) {
 191                 /* handle error -- unable to allocate enough memory */
 192                 fprintf(stderr, "bitmap2.c: Failed to allocate memory for a bitmap.\n");
 193                 exit(-1);  /* FIXME: I should probably call some sort of cacao-wide "panic" function ?! -- phil. */
 194         }
 195
 196         bitmap_clear(bitmap);
 197
 198         return bitmap;
 199 }
 200
 201 void bitmap_release(bitmap_t* bitmap)
 202 {
 203         if (bitmap) {
 204                 if (bitmap->bitmap_memory)
 205                         free(bitmap->bitmap_memory);
 206                 free(bitmap);
 207         }
 208 }
 209
 210
 211 static
 212 int offset_for_lowest(BITBLOCK i)
 213 {
 214         /* Maintainer, don't despair!
 215          *
 216          * The OFFSET_TO_ADDR adjusts an argument according to the size of heap-allocation blocks,
 217          * so that the resulting value can be used as an offset to a pointer.
 218          * I.e.: addr + OFFSET_TO_ADDR(i) is equivalent to addr + (sizeof(heap_block) * i)
 219          *
 220          * The definition of lowest just looks inefficient, everything should be expanded at
 221          * compile-time, though. -- phil.
 222          */
 223
 224         static signed char lowest[256] = {
 225                 OFFSET_TO_ADDR(0),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 226                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 227                 OFFSET_TO_ADDR(4),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 228                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 229                 OFFSET_TO_ADDR(5),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 230                 OFFSET_TO_ADDR(3),  0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
 231                 OFFSET_TO_ADDR(4),  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(6),  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(4),  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(5),  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(4),  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(7),  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(4),  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(5),  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(4),  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(6),  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(4),  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(5),  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(4),  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         };
 258
 259 #if U8_AVAILABLE
 260         if (i & 0xffffffffULL)
 261 #endif
 262                 if (i & 0xffffUL)
 263                         if (i & 0xffUL)
 264                                 return OFFSET_TO_ADDR(0) + lowest[(unsigned char)i];
 265                         else
 266                                 return OFFSET_TO_ADDR(8) + lowest[(unsigned char)(i>>8)];
 267                 else
 268                         if (i & 0xff0000UL)
 269                                 return OFFSET_TO_ADDR(16) + lowest[(unsigned char)(i>>16)];
 270                         else
 271                                 return OFFSET_TO_ADDR(24) + lowest[(unsigned char)(i>>24)];
 272 #if U8_AVAILABLE
 273         else
 274                 if (i & 0xffff00000000ULL)
 275                         if (i & 0xff00000000ULL)
 276                                 return OFFSET_TO_ADDR(32) + lowest[(unsigned char)(i>>32)];
 277                         else
 278                                 return OFFSET_TO_ADDR(40) + lowest[(unsigned char)(i>>40)];
 279                 else
 280                         if (i & 0xff000000000000ULL)
 281                                 return OFFSET_TO_ADDR(48) + lowest[(unsigned char)(i>>48)];
 282                         else
 283                                 return OFFSET_TO_ADDR(56) + lowest[(unsigned char)(i>>56)];
 284 #endif
 285 }
 286
 287 void*
 288 bitmap_find_next_setbit(bitmap_t* bitmap,
 289                                                 void*     addr)
 290 {
 291         OFFSET_T  block = ADDR_TO_BLOCK(addr);
 292         OFFSET_T  offset = ADDR_TO_OFFSET(addr);
 293         BITBLOCK  pattern;
 294
 295         bitmap_boundscheck(bitmap, addr);
 296
 297         /* 1. check the current block, starting from the bit indicated by addr */
 298         pattern = bitmap->bitmap[block] >> offset;
 299         if (pattern)
 300                 return (void*)((long)addr + offset_for_lowest(pattern));
 301
 302         /* 2. iteratively check block by block until the end of the bitmap */
 303         while (block < bitmap->bitmap_top_block) {
 304                 pattern = bitmap->bitmap[++block];
 305
 306                 if (pattern)
 307                         return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
 308         }
 309
 310         /* 3. failed to find a set bit... */
 311         return bitmap->bitmap_beyond_addr;
 312 }
 313
 314 void*
 315 bitmap_find_next_combination_set_unset(bitmap_t* bitmap,
 316                                                                            bitmap_t* invertedmap,
 317                                                                            void*     addr)
 318 {
 319         OFFSET_T  block = ADDR_TO_BLOCK(addr);
 320         OFFSET_T  offset = ADDR_TO_OFFSET(addr);
 321         BITBLOCK  pattern;
 322
 323         bitmap_boundscheck(bitmap, addr);
 324         bitmap_boundscheck(invertedmap, addr);
 325
 326         /* 1. check the current block, starting from the bit indicated by addr */
 327         pattern = (bitmap->bitmap[block] & ~invertedmap->bitmap[block]) >> offset;
 328         if (pattern)
 329                 return (void*)((long)addr + offset_for_lowest(pattern));
 330
 331         /* 2. iteratively check block by block until the end of the bitmap */
 332         while (block < bitmap->bitmap_top_block) {
 333                 pattern = bitmap->bitmap[++block] & ~invertedmap->bitmap[block];
 334
 335                 if (pattern)
 336                         return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
 337         }
 338
 339         /* 3. failed to find a combination... */
 340         return bitmap->bitmap_beyond_addr;
 341 }
 342
 343 void
 344 bitmap_mask_with_bitmap(bitmap_t* bitmap,
 345                                                 bitmap_t* mask)
 346 {
 347         BITBLOCK*       bits = (BITBLOCK*)bitmap->bitmap_memory;
 348         BITBLOCK*       maskbits = (BITBLOCK*)mask->bitmap_memory;
 349         BITBLOCK*       end = (void*)((unsigned long)bits + bitmap->bytesize);
 350
 351         assert(bitmap->bytesize == mask->bytesize);
 352
 353         while (bits < end)
 354                 *(bits++) &= *(maskbits++);
 355 }
 356
 357 /*
 358  * These are local overrides for various environment variables in Emacs.
 359  * Please do not remove this and leave it at the end of the file, where
 360  * Emacs will automagically detect them.
 361  * ---------------------------------------------------------------------
 362  * Local variables:
 363  * mode: c
 364  * indent-tabs-mode: t
 365  * c-basic-offset: 4
 366  * tab-width: 4
 367  * End:
 368  */