Thu, 20 Nov 2008 16:56:09 -0800
6684579: SoftReference processing can be made more efficient
Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not.
Reviewed-by: jmasa
1 /*
2 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
25 // Forward decl;
26 class BitMapClosure;
28 // Operations for bitmaps represented as arrays of unsigned integers.
29 // Bit offsets are numbered from 0 to size-1.
31 class BitMap VALUE_OBJ_CLASS_SPEC {
32 friend class BitMap2D;
34 public:
35 typedef size_t idx_t; // Type used for bit and word indices.
36 typedef uintptr_t bm_word_t; // Element type of array that represents
37 // the bitmap.
39 // Hints for range sizes.
40 typedef enum {
41 unknown_range, small_range, large_range
42 } RangeSizeHint;
44 private:
45 bm_word_t* _map; // First word in bitmap
46 idx_t _size; // Size of bitmap (in bits)
48 // Puts the given value at the given offset, using resize() to size
49 // the bitmap appropriately if needed using factor-of-two expansion.
50 void at_put_grow(idx_t index, bool value);
52 protected:
53 // Return the position of bit within the word that contains it (e.g., if
54 // bitmap words are 32 bits, return a number 0 <= n <= 31).
55 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
57 // Return a mask that will select the specified bit, when applied to the word
58 // containing the bit.
59 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
61 // Return the index of the word containing the specified bit.
62 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
64 // Return the bit number of the first bit in the specified word.
65 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
67 // Return the array of bitmap words, or a specific word from it.
68 bm_word_t* map() const { return _map; }
69 bm_word_t map(idx_t word) const { return _map[word]; }
71 // Return a pointer to the word containing the specified bit.
72 bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); }
74 // Set a word to a specified value or to all ones; clear a word.
75 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
76 void set_word (idx_t word) { set_word(word, ~(uintptr_t)0); }
77 void clear_word(idx_t word) { _map[word] = 0; }
79 // Utilities for ranges of bits. Ranges are half-open [beg, end).
81 // Ranges within a single word.
82 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
83 void set_range_within_word (idx_t beg, idx_t end);
84 void clear_range_within_word (idx_t beg, idx_t end);
85 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
87 // Ranges spanning entire words.
88 void set_range_of_words (idx_t beg, idx_t end);
89 void clear_range_of_words (idx_t beg, idx_t end);
90 void set_large_range_of_words (idx_t beg, idx_t end);
91 void clear_large_range_of_words (idx_t beg, idx_t end);
93 // The index of the first full word in a range.
94 idx_t word_index_round_up(idx_t bit) const;
96 // Verification, statistics.
97 void verify_index(idx_t index) const;
98 void verify_range(idx_t beg_index, idx_t end_index) const;
100 static idx_t* _pop_count_table;
101 static void init_pop_count_table();
102 static idx_t num_set_bits(bm_word_t w);
103 static idx_t num_set_bits_from_table(unsigned char c);
105 public:
107 // Constructs a bitmap with no map, and size 0.
108 BitMap() : _map(NULL), _size(0) {}
110 // Constructs a bitmap with the given map and size.
111 BitMap(bm_word_t* map, idx_t size_in_bits);
113 // Constructs an empty bitmap of the given size (that is, this clears the
114 // new bitmap). Allocates the map array in resource area if
115 // "in_resource_area" is true, else in the C heap.
116 BitMap(idx_t size_in_bits, bool in_resource_area = true);
118 // Set the map and size.
119 void set_map(bm_word_t* map) { _map = map; }
120 void set_size(idx_t size_in_bits) { _size = size_in_bits; }
122 // Allocates necessary data structure, either in the resource area
123 // or in the C heap, as indicated by "in_resource_area."
124 // Preserves state currently in bit map by copying data.
125 // Zeros any newly-addressable bits.
126 // If "in_resource_area" is false, frees the current map.
127 // (Note that this assumes that all calls to "resize" on the same BitMap
128 // use the same value for "in_resource_area".)
129 void resize(idx_t size_in_bits, bool in_resource_area = true);
131 // Accessing
132 idx_t size() const { return _size; }
133 idx_t size_in_words() const {
134 return word_index(size() + BitsPerWord - 1);
135 }
137 bool at(idx_t index) const {
138 verify_index(index);
139 return (*word_addr(index) & bit_mask(index)) != 0;
140 }
142 // Align bit index up or down to the next bitmap word boundary, or check
143 // alignment.
144 static idx_t word_align_up(idx_t bit) {
145 return align_size_up(bit, BitsPerWord);
146 }
147 static idx_t word_align_down(idx_t bit) {
148 return align_size_down(bit, BitsPerWord);
149 }
150 static bool is_word_aligned(idx_t bit) {
151 return word_align_up(bit) == bit;
152 }
154 // Set or clear the specified bit.
155 inline void set_bit(idx_t bit);
156 void clear_bit(idx_t bit);
158 // Atomically set or clear the specified bit.
159 bool par_set_bit(idx_t bit);
160 bool par_clear_bit(idx_t bit);
162 // Put the given value at the given offset. The parallel version
163 // will CAS the value into the bitmap and is quite a bit slower.
164 // The parallel version also returns a value indicating if the
165 // calling thread was the one that changed the value of the bit.
166 void at_put(idx_t index, bool value);
167 bool par_at_put(idx_t index, bool value);
169 // Update a range of bits. Ranges are half-open [beg, end).
170 void set_range (idx_t beg, idx_t end);
171 void clear_range (idx_t beg, idx_t end);
172 void set_large_range (idx_t beg, idx_t end);
173 void clear_large_range (idx_t beg, idx_t end);
174 void at_put_range(idx_t beg, idx_t end, bool value);
175 void par_at_put_range(idx_t beg, idx_t end, bool value);
176 void at_put_large_range(idx_t beg, idx_t end, bool value);
177 void par_at_put_large_range(idx_t beg, idx_t end, bool value);
179 // Update a range of bits, using a hint about the size. Currently only
180 // inlines the predominant case of a 1-bit range. Works best when hint is a
181 // compile-time constant.
182 void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
183 void clear_range(idx_t beg, idx_t end, RangeSizeHint hint);
184 void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint);
185 void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint);
187 // It performs the union operation between subsets of equal length
188 // of two bitmaps (the target bitmap of the method and the
189 // from_bitmap) and stores the result to the target bitmap. The
190 // from_start_index represents the first bit index of the subrange
191 // of the from_bitmap. The to_start_index is the equivalent of the
192 // target bitmap. Both indexes should be word-aligned, i.e. they
193 // should correspond to the first bit on a bitmap word (it's up to
194 // the caller to ensure this; the method does check it). The length
195 // of the subset is specified with word_num and it is in number of
196 // bitmap words. The caller should ensure that this is at least 2
197 // (smaller ranges are not support to save extra checks). Again,
198 // this is checked in the method.
199 //
200 // Atomicity concerns: it is assumed that any contention on the
201 // target bitmap with other threads will happen on the first and
202 // last words; the ones in between will be "owned" exclusively by
203 // the calling thread and, in fact, they will already be 0. So, the
204 // method performs a CAS on the first word, copies the next
205 // word_num-2 words, and finally performs a CAS on the last word.
206 void mostly_disjoint_range_union(BitMap* from_bitmap,
207 idx_t from_start_index,
208 idx_t to_start_index,
209 size_t word_num);
212 // Clearing
213 void clear_large();
214 inline void clear();
216 // Iteration support. Returns "true" if the iteration completed, false
217 // if the iteration terminated early (because the closure "blk" returned
218 // false).
219 bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex);
220 bool iterate(BitMapClosure* blk) {
221 // call the version that takes an interval
222 return iterate(blk, 0, size());
223 }
225 // Looking for 1's and 0's at indices equal to or greater than "l_index",
226 // stopping if none has been found before "r_index", and returning
227 // "r_index" (which must be at most "size") in that case.
228 idx_t get_next_one_offset_inline (idx_t l_index, idx_t r_index) const;
229 idx_t get_next_zero_offset_inline(idx_t l_index, idx_t r_index) const;
231 // Like "get_next_one_offset_inline", except requires that "r_index" is
232 // aligned to bitsizeof(bm_word_t).
233 idx_t get_next_one_offset_inline_aligned_right(idx_t l_index,
234 idx_t r_index) const;
236 // Non-inline versionsof the above.
237 idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
238 idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const;
240 idx_t get_next_one_offset(idx_t offset) const {
241 return get_next_one_offset(offset, size());
242 }
243 idx_t get_next_zero_offset(idx_t offset) const {
244 return get_next_zero_offset(offset, size());
245 }
247 // Returns the number of bits set in the bitmap.
248 idx_t count_one_bits() const;
250 // Set operations.
251 void set_union(BitMap bits);
252 void set_difference(BitMap bits);
253 void set_intersection(BitMap bits);
254 // Returns true iff "this" is a superset of "bits".
255 bool contains(const BitMap bits) const;
256 // Returns true iff "this and "bits" have a non-empty intersection.
257 bool intersects(const BitMap bits) const;
259 // Returns result of whether this map changed
260 // during the operation
261 bool set_union_with_result(BitMap bits);
262 bool set_difference_with_result(BitMap bits);
263 bool set_intersection_with_result(BitMap bits);
265 // Requires the submap of "bits" starting at offset to be at least as
266 // large as "this". Modifies "this" to be the intersection of its
267 // current contents and the submap of "bits" starting at "offset" of the
268 // same length as "this."
269 // (For expedience, currently requires the offset to be aligned to the
270 // bitsize of a uintptr_t. This should go away in the future though it
271 // will probably remain a good case to optimize.)
272 void set_intersection_at_offset(BitMap bits, idx_t offset);
274 void set_from(BitMap bits);
276 bool is_same(BitMap bits);
278 // Test if all bits are set or cleared
279 bool is_full() const;
280 bool is_empty() const;
283 #ifndef PRODUCT
284 public:
285 // Printing
286 void print_on(outputStream* st) const;
287 #endif
288 };
291 // Convenience class wrapping BitMap which provides multiple bits per slot.
292 class BitMap2D VALUE_OBJ_CLASS_SPEC {
293 public:
294 typedef BitMap::idx_t idx_t; // Type used for bit and word indices.
295 typedef BitMap::bm_word_t bm_word_t; // Element type of array that
296 // represents the bitmap.
297 private:
298 BitMap _map;
299 idx_t _bits_per_slot;
301 idx_t bit_index(idx_t slot_index, idx_t bit_within_slot_index) const {
302 return slot_index * _bits_per_slot + bit_within_slot_index;
303 }
305 void verify_bit_within_slot_index(idx_t index) const {
306 assert(index < _bits_per_slot, "bit_within_slot index out of bounds");
307 }
309 public:
310 // Construction. bits_per_slot must be greater than 0.
311 BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot);
313 // Allocates necessary data structure in resource area. bits_per_slot must be greater than 0.
314 BitMap2D(idx_t size_in_slots, idx_t bits_per_slot);
316 idx_t size_in_bits() {
317 return _map.size();
318 }
320 // Returns number of full slots that have been allocated
321 idx_t size_in_slots() {
322 // Round down
323 return _map.size() / _bits_per_slot;
324 }
326 bool is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) {
327 verify_bit_within_slot_index(bit_within_slot_index);
328 return (bit_index(slot_index, bit_within_slot_index) < size_in_bits());
329 }
331 bool at(idx_t slot_index, idx_t bit_within_slot_index) const {
332 verify_bit_within_slot_index(bit_within_slot_index);
333 return _map.at(bit_index(slot_index, bit_within_slot_index));
334 }
336 void set_bit(idx_t slot_index, idx_t bit_within_slot_index) {
337 verify_bit_within_slot_index(bit_within_slot_index);
338 _map.set_bit(bit_index(slot_index, bit_within_slot_index));
339 }
341 void clear_bit(idx_t slot_index, idx_t bit_within_slot_index) {
342 verify_bit_within_slot_index(bit_within_slot_index);
343 _map.clear_bit(bit_index(slot_index, bit_within_slot_index));
344 }
346 void at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
347 verify_bit_within_slot_index(bit_within_slot_index);
348 _map.at_put(bit_index(slot_index, bit_within_slot_index), value);
349 }
351 void at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
352 verify_bit_within_slot_index(bit_within_slot_index);
353 _map.at_put_grow(bit_index(slot_index, bit_within_slot_index), value);
354 }
356 void clear();
357 };
359 // Closure for iterating over BitMaps
361 class BitMapClosure VALUE_OBJ_CLASS_SPEC {
362 public:
363 // Callback when bit in map is set. Should normally return "true";
364 // return of false indicates that the bitmap iteration should terminate.
365 virtual bool do_bit(BitMap::idx_t offset) = 0;
366 };