1 /*
   2  * Copyright (c) 2000, 2015, 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_GC_SHARED_CARDTABLEMODREFBS_HPP
  26 #define SHARE_VM_GC_SHARED_CARDTABLEMODREFBS_HPP
  27 
  28 #include "gc/shared/modRefBarrierSet.hpp"
  29 #include "oops/oop.hpp"
  30 
  31 // This kind of "BarrierSet" allows a "CollectedHeap" to detect and
  32 // enumerate ref fields that have been modified (since the last
  33 // enumeration.)
  34 
  35 // As it currently stands, this barrier is *imprecise*: when a ref field in
  36 // an object "o" is modified, the card table entry for the card containing
  37 // the head of "o" is dirtied, not necessarily the card containing the
  38 // modified field itself.  For object arrays, however, the barrier *is*
  39 // precise; only the card containing the modified element is dirtied.
  40 // Closures used to scan dirty cards should take these
  41 // considerations into account.
  42 
  43 class Generation;
  44 class OopsInGenClosure;
  45 class DirtyCardToOopClosure;
  46 class ClearNoncleanCardWrapper;
  47 class CardTableRS;
  48 
  49 class CardTableModRefBS: public ModRefBarrierSet {
  50   // Some classes get to look at some private stuff.
  51   friend class BytecodeInterpreter;
  52   friend class VMStructs;
  53   friend class CardTableRS;
  54   friend class CheckForUnmarkedOops; // Needs access to raw card bytes.
  55   friend class SharkBuilder;
  56 #ifndef PRODUCT
  57   // For debugging.
  58   friend class GuaranteeNotModClosure;
  59 #endif
  60  protected:
  61 
  62   enum CardValues {
  63     clean_card                  = -1,
  64     // The mask contains zeros in places for all other values.
  65     clean_card_mask             = clean_card - 31,
  66 
  67     dirty_card                  =  0,
  68     precleaned_card             =  1,
  69     claimed_card                =  2,
  70     deferred_card               =  4,
  71     last_card                   =  8,
  72     CT_MR_BS_last_reserved      = 16
  73   };
  74 
  75   // a word's worth (row) of clean card values
  76   static const intptr_t clean_card_row = (intptr_t)(-1);
  77 
  78   // dirty and precleaned are equivalent wrt younger_refs_iter.
  79   static bool card_is_dirty_wrt_gen_iter(jbyte cv) {
  80     return cv == dirty_card || cv == precleaned_card;
  81   }
  82 
  83   // Returns "true" iff the value "cv" will cause the card containing it
  84   // to be scanned in the current traversal.  May be overridden by
  85   // subtypes.
  86   virtual bool card_will_be_scanned(jbyte cv) {
  87     return CardTableModRefBS::card_is_dirty_wrt_gen_iter(cv);
  88   }
  89 
  90   // Returns "true" iff the value "cv" may have represented a dirty card at
  91   // some point.
  92   virtual bool card_may_have_been_dirty(jbyte cv) {
  93     return card_is_dirty_wrt_gen_iter(cv);
  94   }
  95 
  96   // The declaration order of these const fields is important; see the
  97   // constructor before changing.
  98   const MemRegion _whole_heap;       // the region covered by the card table
  99   size_t          _guard_index;      // index of very last element in the card
 100                                      // table; it is set to a guard value
 101                                      // (last_card) and should never be modified
 102   size_t          _last_valid_index; // index of the last valid element
 103   const size_t    _page_size;        // page size used when mapping _byte_map
 104   size_t          _byte_map_size;    // in bytes
 105   jbyte*          _byte_map;         // the card marking array
 106 
 107   int _cur_covered_regions;
 108   // The covered regions should be in address order.
 109   MemRegion* _covered;
 110   // The committed regions correspond one-to-one to the covered regions.
 111   // They represent the card-table memory that has been committed to service
 112   // the corresponding covered region.  It may be that committed region for
 113   // one covered region corresponds to a larger region because of page-size
 114   // roundings.  Thus, a committed region for one covered region may
 115   // actually extend onto the card-table space for the next covered region.
 116   MemRegion* _committed;
 117 
 118   // The last card is a guard card, and we commit the page for it so
 119   // we can use the card for verification purposes. We make sure we never
 120   // uncommit the MemRegion for that page.
 121   MemRegion _guard_region;
 122 
 123  protected:
 124   // Initialization utilities; covered_words is the size of the covered region
 125   // in, um, words.
 126   inline size_t cards_required(size_t covered_words) {
 127     // Add one for a guard card, used to detect errors.
 128     const size_t words = align_size_up(covered_words, card_size_in_words);
 129     return words / card_size_in_words + 1;
 130   }
 131 
 132   inline size_t compute_byte_map_size();
 133 
 134   // Finds and return the index of the region, if any, to which the given
 135   // region would be contiguous.  If none exists, assign a new region and
 136   // returns its index.  Requires that no more than the maximum number of
 137   // covered regions defined in the constructor are ever in use.
 138   int find_covering_region_by_base(HeapWord* base);
 139 
 140   // Same as above, but finds the region containing the given address
 141   // instead of starting at a given base address.
 142   int find_covering_region_containing(HeapWord* addr);
 143 
 144   // Resize one of the regions covered by the remembered set.
 145   virtual void resize_covered_region(MemRegion new_region);
 146 
 147   // Returns the leftmost end of a committed region corresponding to a
 148   // covered region before covered region "ind", or else "NULL" if "ind" is
 149   // the first covered region.
 150   HeapWord* largest_prev_committed_end(int ind) const;
 151 
 152   // Returns the part of the region mr that doesn't intersect with
 153   // any committed region other than self.  Used to prevent uncommitting
 154   // regions that are also committed by other regions.  Also protects
 155   // against uncommitting the guard region.
 156   MemRegion committed_unique_to_self(int self, MemRegion mr) const;
 157 
 158   // Mapping from address to card marking array entry
 159   jbyte* byte_for(const void* p) const {
 160     assert(_whole_heap.contains(p),
 161            err_msg("Attempt to access p = "PTR_FORMAT" out of bounds of "
 162                    " card marking array's _whole_heap = ["PTR_FORMAT","PTR_FORMAT")",
 163                    p2i(p), p2i(_whole_heap.start()), p2i(_whole_heap.end())));
 164     jbyte* result = &byte_map_base[uintptr_t(p) >> card_shift];
 165     assert(result >= _byte_map && result < _byte_map + _byte_map_size,
 166            "out of bounds accessor for card marking array");
 167     return result;
 168   }
 169 
 170   // The card table byte one after the card marking array
 171   // entry for argument address. Typically used for higher bounds
 172   // for loops iterating through the card table.
 173   jbyte* byte_after(const void* p) const {
 174     return byte_for(p) + 1;
 175   }
 176 
 177   // Iterate over the portion of the card-table which covers the given
 178   // region mr in the given space and apply cl to any dirty sub-regions
 179   // of mr. Clears the dirty cards as they are processed.
 180   void non_clean_card_iterate_possibly_parallel(Space* sp, MemRegion mr,
 181                                                 OopsInGenClosure* cl, CardTableRS* ct,
 182                                                 uint n_threads);
 183 
 184  private:
 185   // Work method used to implement non_clean_card_iterate_possibly_parallel()
 186   // above in the parallel case.
 187   void non_clean_card_iterate_parallel_work(Space* sp, MemRegion mr,
 188                                             OopsInGenClosure* cl, CardTableRS* ct,
 189                                             uint n_threads);
 190 
 191  protected:
 192   // Dirty the bytes corresponding to "mr" (not all of which must be
 193   // covered.)
 194   void dirty_MemRegion(MemRegion mr);
 195 
 196   // Clear (to clean_card) the bytes entirely contained within "mr" (not
 197   // all of which must be covered.)
 198   void clear_MemRegion(MemRegion mr);
 199 
 200   // *** Support for parallel card scanning.
 201 
 202   // This is an array, one element per covered region of the card table.
 203   // Each entry is itself an array, with one element per chunk in the
 204   // covered region.  Each entry of these arrays is the lowest non-clean
 205   // card of the corresponding chunk containing part of an object from the
 206   // previous chunk, or else NULL.
 207   typedef jbyte*  CardPtr;
 208   typedef CardPtr* CardArr;
 209   CardArr* _lowest_non_clean;
 210   size_t*  _lowest_non_clean_chunk_size;
 211   uintptr_t* _lowest_non_clean_base_chunk_index;
 212   int* _last_LNC_resizing_collection;
 213 
 214   // Initializes "lowest_non_clean" to point to the array for the region
 215   // covering "sp", and "lowest_non_clean_base_chunk_index" to the chunk
 216   // index of the corresponding to the first element of that array.
 217   // Ensures that these arrays are of sufficient size, allocating if necessary.
 218   // May be called by several threads concurrently.
 219   void get_LNC_array_for_space(Space* sp,
 220                                jbyte**& lowest_non_clean,
 221                                uintptr_t& lowest_non_clean_base_chunk_index,
 222                                size_t& lowest_non_clean_chunk_size);
 223 
 224   // Returns the number of chunks necessary to cover "mr".
 225   size_t chunks_to_cover(MemRegion mr) {
 226     return (size_t)(addr_to_chunk_index(mr.last()) -
 227                     addr_to_chunk_index(mr.start()) + 1);
 228   }
 229 
 230   // Returns the index of the chunk in a stride which
 231   // covers the given address.
 232   uintptr_t addr_to_chunk_index(const void* addr) {
 233     uintptr_t card = (uintptr_t) byte_for(addr);
 234     return card / ParGCCardsPerStrideChunk;
 235   }
 236 
 237   // Apply cl, which must either itself apply dcto_cl or be dcto_cl,
 238   // to the cards in the stride (of n_strides) within the given space.
 239   void process_stride(Space* sp,
 240                       MemRegion used,
 241                       jint stride, int n_strides,
 242                       bool parallel,
 243                       OopsInGenClosure* cl,
 244                       CardTableRS* ct,
 245                       jbyte** lowest_non_clean,
 246                       uintptr_t lowest_non_clean_base_chunk_index,
 247                       size_t lowest_non_clean_chunk_size);
 248 
 249   // Makes sure that chunk boundaries are handled appropriately, by
 250   // adjusting the min_done of dcto_cl, and by using a special card-table
 251   // value to indicate how min_done should be set.
 252   void process_chunk_boundaries(Space* sp,
 253                                 DirtyCardToOopClosure* dcto_cl,
 254                                 MemRegion chunk_mr,
 255                                 MemRegion used,
 256                                 jbyte** lowest_non_clean,
 257                                 uintptr_t lowest_non_clean_base_chunk_index,
 258                                 size_t    lowest_non_clean_chunk_size);
 259 
 260 public:
 261   // Constants
 262   enum SomePublicConstants {
 263     card_shift                  = 9,
 264     card_size                   = 1 << card_shift,
 265     card_size_in_words          = card_size / sizeof(HeapWord)
 266   };
 267 
 268   static int clean_card_val()      { return clean_card; }
 269   static int clean_card_mask_val() { return clean_card_mask; }
 270   static int dirty_card_val()      { return dirty_card; }
 271   static int claimed_card_val()    { return claimed_card; }
 272   static int precleaned_card_val() { return precleaned_card; }
 273   static int deferred_card_val()   { return deferred_card; }
 274 
 275   virtual void initialize();
 276 
 277   // *** Barrier set functions.
 278 
 279   bool has_write_ref_pre_barrier() { return false; }
 280 
 281 protected:
 282 
 283   CardTableModRefBS(MemRegion whole_heap, const BarrierSet::FakeRtti& fake_rtti);
 284   ~CardTableModRefBS();
 285 
 286   // Record a reference update. Note that these versions are precise!
 287   // The scanning code has to handle the fact that the write barrier may be
 288   // either precise or imprecise. We make non-virtual inline variants of
 289   // these functions here for performance.
 290 
 291   void write_ref_field_work(oop obj, size_t offset, oop newVal);
 292   virtual void write_ref_field_work(void* field, oop newVal, bool release = false);
 293 public:
 294 
 295   bool has_write_ref_array_opt() { return true; }
 296   bool has_write_region_opt() { return true; }
 297 
 298   inline void inline_write_region(MemRegion mr) {
 299     dirty_MemRegion(mr);
 300   }
 301 protected:
 302   void write_region_work(MemRegion mr) {
 303     inline_write_region(mr);
 304   }
 305 public:
 306 
 307   inline void inline_write_ref_array(MemRegion mr) {
 308     dirty_MemRegion(mr);
 309   }
 310 protected:
 311   void write_ref_array_work(MemRegion mr) {
 312     inline_write_ref_array(mr);
 313   }
 314 public:
 315 
 316   bool is_aligned(HeapWord* addr) {
 317     return is_card_aligned(addr);
 318   }
 319 
 320   // *** Card-table-barrier-specific things.
 321 
 322   template <class T> inline void inline_write_ref_field_pre(T* field, oop newVal) {}
 323 
 324   template <class T> inline void inline_write_ref_field(T* field, oop newVal, bool release);
 325 
 326   // These are used by G1, when it uses the card table as a temporary data
 327   // structure for card claiming.
 328   bool is_card_dirty(size_t card_index) {
 329     return _byte_map[card_index] == dirty_card_val();
 330   }
 331 
 332   void mark_card_dirty(size_t card_index) {
 333     _byte_map[card_index] = dirty_card_val();
 334   }
 335 
 336   bool is_card_clean(size_t card_index) {
 337     return _byte_map[card_index] == clean_card_val();
 338   }
 339 
 340   // Card marking array base (adjusted for heap low boundary)
 341   // This would be the 0th element of _byte_map, if the heap started at 0x0.
 342   // But since the heap starts at some higher address, this points to somewhere
 343   // before the beginning of the actual _byte_map.
 344   jbyte* byte_map_base;
 345 
 346   // Return true if "p" is at the start of a card.
 347   bool is_card_aligned(HeapWord* p) {
 348     jbyte* pcard = byte_for(p);
 349     return (addr_for(pcard) == p);
 350   }
 351 
 352   HeapWord* align_to_card_boundary(HeapWord* p) {
 353     jbyte* pcard = byte_for(p + card_size_in_words - 1);
 354     return addr_for(pcard);
 355   }
 356 
 357   // The kinds of precision a CardTableModRefBS may offer.
 358   enum PrecisionStyle {
 359     Precise,
 360     ObjHeadPreciseArray
 361   };
 362 
 363   // Tells what style of precision this card table offers.
 364   PrecisionStyle precision() {
 365     return ObjHeadPreciseArray; // Only one supported for now.
 366   }
 367 
 368   // ModRefBS functions.
 369   virtual void invalidate(MemRegion mr, bool whole_heap = false);
 370   void clear(MemRegion mr);
 371   void dirty(MemRegion mr);
 372 
 373   // *** Card-table-RemSet-specific things.
 374 
 375   static uintx ct_max_alignment_constraint();
 376 
 377   // Apply closure "cl" to the dirty cards containing some part of
 378   // MemRegion "mr".
 379   void dirty_card_iterate(MemRegion mr, MemRegionClosure* cl);
 380 
 381   // Return the MemRegion corresponding to the first maximal run
 382   // of dirty cards lying completely within MemRegion mr.
 383   // If reset is "true", then sets those card table entries to the given
 384   // value.
 385   MemRegion dirty_card_range_after_reset(MemRegion mr, bool reset,
 386                                          int reset_val);
 387 
 388   // Provide read-only access to the card table array.
 389   const jbyte* byte_for_const(const void* p) const {
 390     return byte_for(p);
 391   }
 392   const jbyte* byte_after_const(const void* p) const {
 393     return byte_after(p);
 394   }
 395 
 396   // Mapping from card marking array entry to address of first word
 397   HeapWord* addr_for(const jbyte* p) const {
 398     assert(p >= _byte_map && p < _byte_map + _byte_map_size,
 399            "out of bounds access to card marking array");
 400     size_t delta = pointer_delta(p, byte_map_base, sizeof(jbyte));
 401     HeapWord* result = (HeapWord*) (delta << card_shift);
 402     assert(_whole_heap.contains(result),
 403            err_msg("Returning result = "PTR_FORMAT" out of bounds of "
 404                    " card marking array's _whole_heap = ["PTR_FORMAT","PTR_FORMAT")",
 405                    p2i(result), p2i(_whole_heap.start()), p2i(_whole_heap.end())));
 406     return result;
 407   }
 408 
 409   // Mapping from address to card marking array index.
 410   size_t index_for(void* p) {
 411     assert(_whole_heap.contains(p),
 412            err_msg("Attempt to access p = "PTR_FORMAT" out of bounds of "
 413                    " card marking array's _whole_heap = ["PTR_FORMAT","PTR_FORMAT")",
 414                    p2i(p), p2i(_whole_heap.start()), p2i(_whole_heap.end())));
 415     return byte_for(p) - _byte_map;
 416   }
 417 
 418   const jbyte* byte_for_index(const size_t card_index) const {
 419     return _byte_map + card_index;
 420   }
 421 
 422   // Print a description of the memory for the barrier set
 423   virtual void print_on(outputStream* st) const;
 424 
 425   void verify();
 426   void verify_guard();
 427 
 428   // val_equals -> it will check that all cards covered by mr equal val
 429   // !val_equals -> it will check that all cards covered by mr do not equal val
 430   void verify_region(MemRegion mr, jbyte val, bool val_equals) PRODUCT_RETURN;
 431   void verify_not_dirty_region(MemRegion mr) PRODUCT_RETURN;
 432   void verify_dirty_region(MemRegion mr) PRODUCT_RETURN;
 433 };
 434 
 435 template<>
 436 struct BarrierSet::GetName<CardTableModRefBS> {
 437   static const BarrierSet::Name value = BarrierSet::CardTableModRef;
 438 };
 439 
 440 class CardTableRS;
 441 
 442 // A specialization for the CardTableRS gen rem set.
 443 class CardTableModRefBSForCTRS: public CardTableModRefBS {
 444   CardTableRS* _rs;
 445 protected:
 446   bool card_will_be_scanned(jbyte cv);
 447   bool card_may_have_been_dirty(jbyte cv);
 448 public:
 449   CardTableModRefBSForCTRS(MemRegion whole_heap) :
 450     CardTableModRefBS(
 451       whole_heap,
 452       // Concrete tag should be BarrierSet::CardTableForRS.
 453       // That will presently break things in a bunch of places though.
 454       // The concrete tag is used as a dispatch key in many places, and
 455       // CardTableForRS does not correctly dispatch in some of those
 456       // uses. This will be addressed as part of a reorganization of the
 457       // BarrierSet hierarchy.
 458       BarrierSet::FakeRtti(BarrierSet::CardTableModRef, 0).add_tag(BarrierSet::CardTableForRS))
 459     {}
 460 
 461   void set_CTRS(CardTableRS* rs) { _rs = rs; }
 462 };
 463 
 464 template<>
 465 struct BarrierSet::GetName<CardTableModRefBSForCTRS> {
 466   static const BarrierSet::Name value = BarrierSet::CardTableForRS;
 467 };
 468 
 469 
 470 #endif // SHARE_VM_GC_SHARED_CARDTABLEMODREFBS_HPP