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
7 * Authors: Philipp Tomsich EMAIL: cacao@complang.tuwien.ac.at
9 * $Id: bitmap2.c 60 1998-11-11 02:22:30Z phil $
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.
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.
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.
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
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.
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!
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 */
54 #warning "bitmap2.c untested in 32-bit mode -- phil."
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.
62 /* FIXME: HEAPBLOCK_SIZE is an alias for POINTER_ALIGNMENT and should be
66 /* Please note: All values are log2 */
68 #define POINTER_ALIGNMENT 3 /* alignment of pointers onto the
69 heap == heapblocksize */
70 #define BITBLOCK_SIZE 3 /* bytes/BITBLOCK */
72 #define POINTER_ALIGNMENT 2
73 #define BITBLOCK_SIZE 2
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)
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)
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)))
89 #define BIT_AT_OFFSET(offset) ((BITBLOCK)1 << (offset))
90 #define BIT_FOR_ADDR(addr) BIT_AT_OFFSET(ADDR_TO_OFFSET((addr)))
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 )
97 /* Operations per macro (relative cost):
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 |
118 void bitmap_setbit(BITBLOCK* bitmap,
121 SETBIT(bitmap, addr);
125 void bitmap_clearbit(BITBLOCK* bitmap,
128 CLEARBIT(bitmap, addr);
132 bool bitmap_testbit(BITBLOCK* bitmap,
135 return TESTBIT(bitmap, addr);
140 void bitmap_boundscheck(bitmap_t* bitmap,
143 /* check the lower bound */
144 assert((void*)&bitmap->bitmap[ADDR_TO_BLOCK(addr)] >= bitmap->bitmap_memory);
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 */
152 void bitmap_checking_setbit(bitmap_t* bitmap,
155 bitmap_boundscheck(bitmap, addr);
156 bitmap_setbit(bitmap->bitmap, addr);
160 void bitmap_checking_clearbit(bitmap_t* bitmap,
163 bitmap_boundscheck(bitmap, addr);
164 bitmap_clearbit(bitmap->bitmap, addr);
168 bool bitmap_checking_testbit(bitmap_t* bitmap,
171 bitmap_boundscheck(bitmap, addr);
172 return bitmap_testbit(bitmap->bitmap, addr);
176 void bitmap_clear(bitmap_t* bitmap)
178 memset(bitmap->bitmap_memory, 0, bitmap->bytesize);
182 bitmap_t* bitmap_allocate(void* zero_addr,
187 unsigned long bytesize = CALC_BITMAP_SIZE(size); /* align */
188 bitmap = (bitmap_t*)malloc(sizeof(bitmap_t));
190 CHECK_ADDR_ALIGNMENT(zero_addr); /* ensure correct alignment for zero_addr */
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 */
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));
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. */
205 bitmap_clear(bitmap);
211 void bitmap_release(bitmap_t* bitmap)
214 if (bitmap->bitmap_memory)
215 free(bitmap->bitmap_memory);
223 int offset_for_lowest(BITBLOCK i)
225 /* Maintainer, don't despair!
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)
231 * The definition of lowest just looks inefficient, everything should be expanded at
232 * compile-time, though. -- phil.
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,
271 if (i & 0xffffffffULL)
275 return OFFSET_TO_ADDR(0) + lowest[(unsigned char)i];
277 return OFFSET_TO_ADDR(8) + lowest[(unsigned char)(i>>8)];
280 return OFFSET_TO_ADDR(16) + lowest[(unsigned char)(i>>16)];
282 return OFFSET_TO_ADDR(24) + lowest[(unsigned char)(i>>24)];
285 if (i & 0xffff00000000ULL)
286 if (i & 0xff00000000ULL)
287 return OFFSET_TO_ADDR(32) + lowest[(unsigned char)(i>>32)];
289 return OFFSET_TO_ADDR(40) + lowest[(unsigned char)(i>>40)];
291 if (i & 0xff000000000000ULL)
292 return OFFSET_TO_ADDR(48) + lowest[(unsigned char)(i>>48)];
294 return OFFSET_TO_ADDR(56) + lowest[(unsigned char)(i>>56)];
300 bitmap_find_next_setbit(bitmap_t* bitmap,
303 OFFSET_T block = ADDR_TO_BLOCK(addr);
304 OFFSET_T offset = ADDR_TO_OFFSET(addr);
307 bitmap_boundscheck(bitmap, addr);
309 /* 1. check the current block, starting from the bit indicated by addr */
310 pattern = bitmap->bitmap[block] >> offset;
312 return (void*)((long)addr + offset_for_lowest(pattern));
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];
319 return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
322 /* 3. failed to find a set bit... */
323 return bitmap->bitmap_beyond_addr;
328 bitmap_find_next_combination_set_unset(bitmap_t* bitmap,
329 bitmap_t* invertedmap,
332 OFFSET_T block = ADDR_TO_BLOCK(addr);
333 OFFSET_T offset = ADDR_TO_OFFSET(addr);
336 bitmap_boundscheck(bitmap, addr);
337 bitmap_boundscheck(invertedmap, addr);
339 /* 1. check the current block, starting from the bit indicated by addr */
340 pattern = (bitmap->bitmap[block] & ~invertedmap->bitmap[block]) >> offset;
342 return (void*)((long)addr + offset_for_lowest(pattern));
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];
349 return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
352 /* 3. failed to find a combination... */
353 return bitmap->bitmap_beyond_addr;
357 * These are local overrides for various environment variables in Emacs.
358 * Please do not remove this and leave it at the end of the file, where
359 * Emacs will automagically detect them.
360 * ---------------------------------------------------------------------
363 * indent-tabs-mode: t