1/*
2 * Copyright (c) 2005, 2017, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25#ifndef SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
26#define SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
27
28#include "runtime/atomic.hpp"
29#include "utilities/bitMap.hpp"
30
31inline void BitMap::set_bit(idx_t bit) {
32  verify_index(bit);
33  *word_addr(bit) |= bit_mask(bit);
34}
35
36inline void BitMap::clear_bit(idx_t bit) {
37  verify_index(bit);
38  *word_addr(bit) &= ~bit_mask(bit);
39}
40
41inline bool BitMap::par_set_bit(idx_t bit) {
42  verify_index(bit);
43  volatile bm_word_t* const addr = word_addr(bit);
44  const bm_word_t mask = bit_mask(bit);
45  bm_word_t old_val = *addr;
46
47  do {
48    const bm_word_t new_val = old_val | mask;
49    if (new_val == old_val) {
50      return false;     // Someone else beat us to it.
51    }
52    const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val);
53    if (cur_val == old_val) {
54      return true;      // Success.
55    }
56    old_val = cur_val;  // The value changed, try again.
57  } while (true);
58}
59
60inline bool BitMap::par_clear_bit(idx_t bit) {
61  verify_index(bit);
62  volatile bm_word_t* const addr = word_addr(bit);
63  const bm_word_t mask = ~bit_mask(bit);
64  bm_word_t old_val = *addr;
65
66  do {
67    const bm_word_t new_val = old_val & mask;
68    if (new_val == old_val) {
69      return false;     // Someone else beat us to it.
70    }
71    const bm_word_t cur_val = Atomic::cmpxchg(new_val, addr, old_val);
72    if (cur_val == old_val) {
73      return true;      // Success.
74    }
75    old_val = cur_val;  // The value changed, try again.
76  } while (true);
77}
78
79inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
80  if (hint == small_range && end - beg == 1) {
81    set_bit(beg);
82  } else {
83    if (hint == large_range) {
84      set_large_range(beg, end);
85    } else {
86      set_range(beg, end);
87    }
88  }
89}
90
91inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
92  if (end - beg == 1) {
93    clear_bit(beg);
94  } else {
95    if (hint == large_range) {
96      clear_large_range(beg, end);
97    } else {
98      clear_range(beg, end);
99    }
100  }
101}
102
103inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
104  if (hint == small_range && end - beg == 1) {
105    par_at_put(beg, true);
106  } else {
107    if (hint == large_range) {
108      par_at_put_large_range(beg, end, true);
109    } else {
110      par_at_put_range(beg, end, true);
111    }
112  }
113}
114
115inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
116  bm_word_t* map = _map;
117  for (idx_t i = beg; i < end; ++i) map[i] = ~(bm_word_t)0;
118}
119
120inline void BitMap::clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end) {
121  for (idx_t i = beg; i < end; ++i) map[i] = 0;
122}
123
124inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
125  clear_range_of_words(_map, beg, end);
126}
127
128inline void BitMap::clear() {
129  clear_range_of_words(0, size_in_words());
130}
131
132inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
133  if (hint == small_range && end - beg == 1) {
134    par_at_put(beg, false);
135  } else {
136    if (hint == large_range) {
137      par_at_put_large_range(beg, end, false);
138    } else {
139      par_at_put_range(beg, end, false);
140    }
141  }
142}
143
144inline BitMap::idx_t
145BitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const {
146  assert(l_offset <= size(), "BitMap index out of bounds");
147  assert(r_offset <= size(), "BitMap index out of bounds");
148  assert(l_offset <= r_offset, "l_offset > r_offset ?");
149
150  if (l_offset == r_offset) {
151    return l_offset;
152  }
153  idx_t   index = word_index(l_offset);
154  idx_t r_index = word_index(r_offset-1) + 1;
155  idx_t res_offset = l_offset;
156
157  // check bits including and to the _left_ of offset's position
158  idx_t pos = bit_in_word(res_offset);
159  bm_word_t res = map(index) >> pos;
160  if (res != 0) {
161    // find the position of the 1-bit
162    for (; !(res & 1); res_offset++) {
163      res = res >> 1;
164    }
165
166#ifdef ASSERT
167    // In the following assert, if r_offset is not bitamp word aligned,
168    // checking that res_offset is strictly less than r_offset is too
169    // strong and will trip the assert.
170    //
171    // Consider the case where l_offset is bit 15 and r_offset is bit 17
172    // of the same map word, and where bits [15:16:17:18] == [00:00:00:01].
173    // All the bits in the range [l_offset:r_offset) are 0.
174    // The loop that calculates res_offset, above, would yield the offset
175    // of bit 18 because it's in the same map word as l_offset and there
176    // is a set bit in that map word above l_offset (i.e. res != NoBits).
177    //
178    // In this case, however, we can assert is that res_offset is strictly
179    // less than size() since we know that there is at least one set bit
180    // at an offset above, but in the same map word as, r_offset.
181    // Otherwise, if r_offset is word aligned then it will not be in the
182    // same map word as l_offset (unless it equals l_offset). So either
183    // there won't be a set bit between l_offset and the end of it's map
184    // word (i.e. res == NoBits), or res_offset will be less than r_offset.
185
186    idx_t limit = is_word_aligned(r_offset) ? r_offset : size();
187    assert(res_offset >= l_offset && res_offset < limit, "just checking");
188#endif // ASSERT
189    return MIN2(res_offset, r_offset);
190  }
191  // skip over all word length 0-bit runs
192  for (index++; index < r_index; index++) {
193    res = map(index);
194    if (res != 0) {
195      // found a 1, return the offset
196      for (res_offset = bit_index(index); !(res & 1); res_offset++) {
197        res = res >> 1;
198      }
199      assert(res & 1, "tautology; see loop condition");
200      assert(res_offset >= l_offset, "just checking");
201      return MIN2(res_offset, r_offset);
202    }
203  }
204  return r_offset;
205}
206
207inline BitMap::idx_t
208BitMap::get_next_zero_offset(idx_t l_offset, idx_t r_offset) const {
209  assert(l_offset <= size(), "BitMap index out of bounds");
210  assert(r_offset <= size(), "BitMap index out of bounds");
211  assert(l_offset <= r_offset, "l_offset > r_offset ?");
212
213  if (l_offset == r_offset) {
214    return l_offset;
215  }
216  idx_t   index = word_index(l_offset);
217  idx_t r_index = word_index(r_offset-1) + 1;
218  idx_t res_offset = l_offset;
219
220  // check bits including and to the _left_ of offset's position
221  idx_t pos = bit_in_word(res_offset);
222  bm_word_t res = ~map(index) >> pos; // flip bits and shift for l_offset
223
224  if (res != 0) {
225    // find the position of the 1-bit
226    for (; !(res & 1); res_offset++) {
227      res = res >> 1;
228    }
229    assert(res_offset >= l_offset, "just checking");
230    return MIN2(res_offset, r_offset);
231  }
232  // skip over all word length 1-bit runs
233  for (index++; index < r_index; index++) {
234    res = map(index);
235    if (res != ~(bm_word_t)0) {
236      // found a 0, return the offset
237      for (res_offset = index << LogBitsPerWord; res & 1;
238           res_offset++) {
239        res = res >> 1;
240      }
241      assert(!(res & 1), "tautology; see loop condition");
242      assert(res_offset >= l_offset, "just checking");
243      return MIN2(res_offset, r_offset);
244    }
245  }
246  return r_offset;
247}
248
249inline BitMap::idx_t
250BitMap::get_next_one_offset_aligned_right(idx_t l_offset, idx_t r_offset) const
251{
252  verify_range(l_offset, r_offset);
253  assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned");
254
255  if (l_offset == r_offset) {
256    return l_offset;
257  }
258  idx_t   index = word_index(l_offset);
259  idx_t r_index = word_index(r_offset);
260  idx_t res_offset = l_offset;
261
262  // check bits including and to the _left_ of offset's position
263  bm_word_t res = map(index) >> bit_in_word(res_offset);
264  if (res != 0) {
265    // find the position of the 1-bit
266    for (; !(res & 1); res_offset++) {
267      res = res >> 1;
268    }
269    assert(res_offset >= l_offset &&
270           res_offset < r_offset, "just checking");
271    return res_offset;
272  }
273  // skip over all word length 0-bit runs
274  for (index++; index < r_index; index++) {
275    res = map(index);
276    if (res != 0) {
277      // found a 1, return the offset
278      for (res_offset = bit_index(index); !(res & 1); res_offset++) {
279        res = res >> 1;
280      }
281      assert(res & 1, "tautology; see loop condition");
282      assert(res_offset >= l_offset && res_offset < r_offset, "just checking");
283      return res_offset;
284    }
285  }
286  return r_offset;
287}
288
289
290// Returns a bit mask for a range of bits [beg, end) within a single word.  Each
291// bit in the mask is 0 if the bit is in the range, 1 if not in the range.  The
292// returned mask can be used directly to clear the range, or inverted to set the
293// range.  Note:  end must not be 0.
294inline BitMap::bm_word_t
295BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
296  assert(end != 0, "does not work when end == 0");
297  assert(beg == end || word_index(beg) == word_index(end - 1),
298         "must be a single-word range");
299  bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
300  if (bit_in_word(end) != 0) {
301    mask |= ~(bit_mask(end) - 1);       // high (left) bits
302  }
303  return mask;
304}
305
306inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
307  memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(bm_word_t));
308}
309
310inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
311  memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t));
312}
313
314inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
315  idx_t bit_rounded_up = bit + (BitsPerWord - 1);
316  // Check for integer arithmetic overflow.
317  return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
318}
319
320inline bool BitMap2D::is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) {
321  verify_bit_within_slot_index(bit_within_slot_index);
322  return (bit_index(slot_index, bit_within_slot_index) < size_in_bits());
323}
324
325inline bool BitMap2D::at(idx_t slot_index, idx_t bit_within_slot_index) const {
326  verify_bit_within_slot_index(bit_within_slot_index);
327  return _map.at(bit_index(slot_index, bit_within_slot_index));
328}
329
330inline void BitMap2D::set_bit(idx_t slot_index, idx_t bit_within_slot_index) {
331  verify_bit_within_slot_index(bit_within_slot_index);
332  _map.set_bit(bit_index(slot_index, bit_within_slot_index));
333}
334
335inline void BitMap2D::clear_bit(idx_t slot_index, idx_t bit_within_slot_index) {
336  verify_bit_within_slot_index(bit_within_slot_index);
337  _map.clear_bit(bit_index(slot_index, bit_within_slot_index));
338}
339
340inline void BitMap2D::at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
341  verify_bit_within_slot_index(bit_within_slot_index);
342  _map.at_put(bit_index(slot_index, bit_within_slot_index), value);
343}
344
345inline void BitMap2D::at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
346  verify_bit_within_slot_index(bit_within_slot_index);
347
348  idx_t bit = bit_index(slot_index, bit_within_slot_index);
349  if (bit >= _map.size()) {
350    _map.resize(2 * MAX2(_map.size(), bit));
351  }
352  _map.at_put(bit, value);
353}
354
355#endif // SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
356