1 /*
  2  * Copyright (c) 2018, 2023, Oracle and/or its affiliates. All rights reserved.
  3  * Copyright (c) 2020, Red Hat, Inc. and/or its affiliates.
  4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  5  *
  6  * This code is free software; you can redistribute it and/or modify it
  7  * under the terms of the GNU General Public License version 2 only, as
  8  * published by the Free Software Foundation.
  9  *
 10  * This code is distributed in the hope that it will be useful, but WITHOUT
 11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 13  * version 2 for more details (a copy is included in the LICENSE file that
 14  * accompanied this code).
 15  *
 16  * You should have received a copy of the GNU General Public License version
 17  * 2 along with this work; if not, write to the Free Software Foundation,
 18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 19  *
 20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 21  * or visit www.oracle.com if you need additional information or have any
 22  * questions.
 23  *
 24  */
 25 
 26 #ifndef SHARE_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_HPP
 27 #define SHARE_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_HPP
 28 
 29 #include "memory/memRegion.hpp"
 30 #include "runtime/atomic.hpp"
 31 #include "utilities/globalDefinitions.hpp"
 32 
 33 class ShenandoahMarkBitMap {
 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 the
 37                                 // bitmap, with BitsPerWord bits per element.
 38 
 39 private:
 40   // Values for get_next_bit_impl flip parameter.
 41   static const bm_word_t find_ones_flip = 0;
 42   static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
 43 
 44   int const _shift;
 45   MemRegion _covered;
 46 
 47   bm_word_t* _map;     // First word in bitmap
 48   idx_t      _size;    // Size of bitmap (in bits)
 49 
 50   // Threshold for performing small range operation, even when large range
 51   // operation was requested. Measured in words.
 52   static const size_t small_range_words = 32;
 53 
 54   static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
 55 
 56   inline size_t address_to_index(const HeapWord* addr) const;
 57   inline HeapWord* index_to_address(size_t offset) const;
 58 
 59   void check_mark(HeapWord* addr) const NOT_DEBUG_RETURN;
 60 
 61   // Return a mask that will select the specified bit, when applied to the word
 62   // containing the bit.
 63   static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
 64 
 65   // Return the bit number of the first bit in the specified word.
 66   static idx_t bit_index(idx_t word)  { return word << LogBitsPerWord; }
 67 
 68   // Return the position of bit within the word that contains it (e.g., if
 69   // bitmap words are 32 bits, return a number 0 <= n <= 31).
 70   static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
 71 
 72   bm_word_t* map()                 { return _map; }
 73   const bm_word_t* map() const     { return _map; }
 74   bm_word_t map(idx_t word) const { return _map[word]; }
 75 
 76   // Return a pointer to the word containing the specified bit.
 77   bm_word_t* word_addr(idx_t bit) {
 78     return map() + to_words_align_down(bit);
 79   }
 80 
 81   const bm_word_t* word_addr(idx_t bit) const {
 82     return map() + to_words_align_down(bit);
 83   }
 84 
 85   bool at(idx_t index) const {
 86     verify_index(index);
 87     return (*word_addr(index) & bit_mask(index)) != 0;
 88   }
 89 
 90   // Assumes relevant validity checking for bit has already been done.
 91   static idx_t raw_to_words_align_up(idx_t bit) {
 92     return raw_to_words_align_down(bit + (BitsPerWord - 1));
 93   }
 94 
 95   // Assumes relevant validity checking for bit has already been done.
 96   static idx_t raw_to_words_align_down(idx_t bit) {
 97     return bit >> LogBitsPerWord;
 98   }
 99 
100   // Word-aligns bit and converts it to a word offset.
101   // precondition: bit <= size()
102   idx_t to_words_align_up(idx_t bit) const {
103     verify_limit(bit);
104     return raw_to_words_align_up(bit);
105   }
106 
107   // Word-aligns bit and converts it to a word offset.
108   // precondition: bit <= size()
109   inline idx_t to_words_align_down(idx_t bit) const {
110     verify_limit(bit);
111     return raw_to_words_align_down(bit);
112   }
113 
114   // Helper for get_next_{zero,one}_bit variants.
115   // - flip designates whether searching for 1s or 0s.  Must be one of
116   //   find_{zeros,ones}_flip.
117   // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
118   template<bm_word_t flip, bool aligned_right>
119   inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
120 
121   inline idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const;
122 
123   void clear_large_range (idx_t beg, idx_t end);
124 
125   // Verify bit is less than size().
126   void verify_index(idx_t bit) const NOT_DEBUG_RETURN;
127   // Verify bit is not greater than size().
128   void verify_limit(idx_t bit) const NOT_DEBUG_RETURN;
129   // Verify [beg,end) is a valid range, e.g. beg <= end <= size().
130   void verify_range(idx_t beg, idx_t end) const NOT_DEBUG_RETURN;
131 
132 public:
133   static size_t compute_size(size_t heap_size);
134   // Returns the amount of bytes on the heap between two marks in the bitmap.
135   static size_t mark_distance();
136   // Returns how many bytes (or bits) of the heap a single byte (or bit) of the
137   // mark bitmap corresponds to. This is the same as the mark distance above.
138   static size_t heap_map_factor() {
139     return mark_distance();
140   }
141 
142   ShenandoahMarkBitMap(MemRegion heap, MemRegion storage);
143 
144   // Mark word as 'strong' if it hasn't been marked strong yet.
145   // Return true if the word has been marked strong, false if it has already been
146   // marked strong or if another thread has beat us by marking it
147   // strong.
148   // Words that have been marked final before or by a concurrent thread will be
149   // upgraded to strong. In this case, this method also returns true.
150   inline bool mark_strong(HeapWord* w, bool& was_upgraded);
151 
152   // Mark word as 'weak' if it hasn't been marked weak or strong yet.
153   // Return true if the word has been marked weak, false if it has already been
154   // marked strong or weak or if another thread has beat us by marking it
155   // strong or weak.
156   inline bool mark_weak(HeapWord* heap_addr);
157 
158   inline bool is_marked(HeapWord* addr) const;
159   inline bool is_marked_strong(HeapWord* w)  const;
160   inline bool is_marked_weak(HeapWord* addr) const;
161 
162   // Return the address corresponding to the next marked bit at or after
163   // "addr", and before "limit", if "limit" is non-null.  If there is no
164   // such bit, returns "limit" if that is non-null, or else "endWord()".
165   HeapWord* get_next_marked_addr(const HeapWord* addr,
166                                  const HeapWord* limit) const;
167 
168   bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
169   void  clear_range_within_word    (idx_t beg, idx_t end);
170   void clear_range (idx_t beg, idx_t end);
171   void clear_range_large(MemRegion mr);
172 
173   void clear_range_of_words(idx_t beg, idx_t end);
174   void clear_large_range_of_words(idx_t beg, idx_t end);
175   static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
176 
177 };
178 
179 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_HPP