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_MEMORY_CARDTABLEMODREFBS_HPP
  26 #define SHARE_VM_MEMORY_CARDTABLEMODREFBS_HPP
  27 
  28 #include "memory/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 
 183  private:
 184   // Work method used to implement non_clean_card_iterate_possibly_parallel()
 185   // above in the parallel case.
 186   void non_clean_card_iterate_parallel_work(Space* sp, MemRegion mr,
 187                                             OopsInGenClosure* cl, CardTableRS* ct,
 188                                             int n_threads);
 189 
 190  protected:
 191   // Dirty the bytes corresponding to "mr" (not all of which must be
 192   // covered.)
 193   void dirty_MemRegion(MemRegion mr);
 194 
 195   // Clear (to clean_card) the bytes entirely contained within "mr" (not
 196   // all of which must be covered.)
 197   void clear_MemRegion(MemRegion mr);
 198 
 199   // *** Support for parallel card scanning.
 200 
 201   // This is an array, one element per covered region of the card table.
 202   // Each entry is itself an array, with one element per chunk in the
 203   // covered region.  Each entry of these arrays is the lowest non-clean
 204   // card of the corresponding chunk containing part of an object from the
 205   // previous chunk, or else NULL.
 206   typedef jbyte*  CardPtr;
 207   typedef CardPtr* CardArr;
 208   CardArr* _lowest_non_clean;
 209   size_t*  _lowest_non_clean_chunk_size;
 210   uintptr_t* _lowest_non_clean_base_chunk_index;
 211   int* _last_LNC_resizing_collection;
 212 
 213   // Initializes "lowest_non_clean" to point to the array for the region
 214   // covering "sp", and "lowest_non_clean_base_chunk_index" to the chunk
 215   // index of the corresponding to the first element of that array.
 216   // Ensures that these arrays are of sufficient size, allocating if necessary.
 217   // May be called by several threads concurrently.
 218   void get_LNC_array_for_space(Space* sp,
 219                                jbyte**& lowest_non_clean,
 220                                uintptr_t& lowest_non_clean_base_chunk_index,
 221                                size_t& lowest_non_clean_chunk_size);
 222 
 223   // Returns the number of chunks necessary to cover "mr".
 224   size_t chunks_to_cover(MemRegion mr) {
 225     return (size_t)(addr_to_chunk_index(mr.last()) -
 226                     addr_to_chunk_index(mr.start()) + 1);
 227   }
 228 
 229   // Returns the index of the chunk in a stride which
 230   // covers the given address.
 231   uintptr_t addr_to_chunk_index(const void* addr) {
 232     uintptr_t card = (uintptr_t) byte_for(addr);
 233     return card / ParGCCardsPerStrideChunk;
 234   }
 235 
 236   // Apply cl, which must either itself apply dcto_cl or be dcto_cl,
 237   // to the cards in the stride (of n_strides) within the given space.
 238   void process_stride(Space* sp,
 239                       MemRegion used,
 240                       jint stride, int n_strides,
 241                       OopsInGenClosure* cl,
 242                       CardTableRS* ct,
 243                       jbyte** lowest_non_clean,
 244                       uintptr_t lowest_non_clean_base_chunk_index,
 245                       size_t lowest_non_clean_chunk_size);
 246 
 247   // Makes sure that chunk boundaries are handled appropriately, by
 248   // adjusting the min_done of dcto_cl, and by using a special card-table
 249   // value to indicate how min_done should be set.
 250   void process_chunk_boundaries(Space* sp,
 251                                 DirtyCardToOopClosure* dcto_cl,
 252                                 MemRegion chunk_mr,
 253                                 MemRegion used,
 254                                 jbyte** lowest_non_clean,
 255                                 uintptr_t lowest_non_clean_base_chunk_index,
 256                                 size_t    lowest_non_clean_chunk_size);
 257 
 258 public:
 259   // Constants
 260   enum SomePublicConstants {
 261     card_shift                  = 9,
 262     card_size                   = 1 << card_shift,
 263     card_size_in_words          = card_size / sizeof(HeapWord)
 264   };
 265 
 266   static int clean_card_val()      { return clean_card; }
 267   static int clean_card_mask_val() { return clean_card_mask; }
 268   static int dirty_card_val()      { return dirty_card; }
 269   static int claimed_card_val()    { return claimed_card; }
 270   static int precleaned_card_val() { return precleaned_card; }
 271   static int deferred_card_val()   { return deferred_card; }
 272 
 273   virtual void initialize();
 274 
 275   // *** Barrier set functions.
 276 
 277   bool has_write_ref_pre_barrier() { return false; }
 278 
 279 protected:
 280 
 281   CardTableModRefBS(MemRegion whole_heap, const BarrierSet::FakeRtti& fake_rtti);
 282   ~CardTableModRefBS();
 283 
 284   // Record a reference update. Note that these versions are precise!
 285   // The scanning code has to handle the fact that the write barrier may be
 286   // either precise or imprecise. We make non-virtual inline variants of
 287   // these functions here for performance.
 288 
 289   void write_ref_field_work(oop obj, size_t offset, oop newVal);
 290   virtual void write_ref_field_work(void* field, oop newVal, bool release = false);
 291 public:
 292 
 293   bool has_write_ref_array_opt() { return true; }
 294   bool has_write_region_opt() { return true; }
 295 
 296   inline void inline_write_region(MemRegion mr) {
 297     dirty_MemRegion(mr);
 298   }
 299 protected:
 300   void write_region_work(MemRegion mr) {
 301     inline_write_region(mr);
 302   }
 303 public:
 304 
 305   inline void inline_write_ref_array(MemRegion mr) {
 306     dirty_MemRegion(mr);
 307   }
 308 protected:
 309   void write_ref_array_work(MemRegion mr) {
 310     inline_write_ref_array(mr);
 311   }
 312 public:
 313 
 314   bool is_aligned(HeapWord* addr) {
 315     return is_card_aligned(addr);
 316   }
 317 
 318   // *** Card-table-barrier-specific things.
 319 
 320   template <class T> inline void inline_write_ref_field_pre(T* field, oop newVal) {}
 321 
 322   template <class T> inline void inline_write_ref_field(T* field, oop newVal, bool release);
 323 
 324   // These are used by G1, when it uses the card table as a temporary data
 325   // structure for card claiming.
 326   bool is_card_dirty(size_t card_index) {
 327     return _byte_map[card_index] == dirty_card_val();
 328   }
 329 
 330   void mark_card_dirty(size_t card_index) {
 331     _byte_map[card_index] = dirty_card_val();
 332   }
 333 
 334   bool is_card_clean(size_t card_index) {
 335     return _byte_map[card_index] == clean_card_val();
 336   }
 337 
 338   // Card marking array base (adjusted for heap low boundary)
 339   // This would be the 0th element of _byte_map, if the heap started at 0x0.
 340   // But since the heap starts at some higher address, this points to somewhere
 341   // before the beginning of the actual _byte_map.
 342   jbyte* byte_map_base;
 343 
 344   // Return true if "p" is at the start of a card.
 345   bool is_card_aligned(HeapWord* p) {
 346     jbyte* pcard = byte_for(p);
 347     return (addr_for(pcard) == p);
 348   }
 349 
 350   HeapWord* align_to_card_boundary(HeapWord* p) {
 351     jbyte* pcard = byte_for(p + card_size_in_words - 1);
 352     return addr_for(pcard);
 353   }
 354 
 355   // The kinds of precision a CardTableModRefBS may offer.
 356   enum PrecisionStyle {
 357     Precise,
 358     ObjHeadPreciseArray
 359   };
 360 
 361   // Tells what style of precision this card table offers.
 362   PrecisionStyle precision() {
 363     return ObjHeadPreciseArray; // Only one supported for now.
 364   }
 365 
 366   // ModRefBS functions.
 367   virtual void invalidate(MemRegion mr, bool whole_heap = false);
 368   void clear(MemRegion mr);
 369   void dirty(MemRegion mr);
 370 
 371   // *** Card-table-RemSet-specific things.
 372 
 373   static uintx ct_max_alignment_constraint();
 374 
 375   // Apply closure "cl" to the dirty cards containing some part of
 376   // MemRegion "mr".
 377   void dirty_card_iterate(MemRegion mr, MemRegionClosure* cl);
 378 
 379   // Return the MemRegion corresponding to the first maximal run
 380   // of dirty cards lying completely within MemRegion mr.
 381   // If reset is "true", then sets those card table entries to the given
 382   // value.
 383   MemRegion dirty_card_range_after_reset(MemRegion mr, bool reset,
 384                                          int reset_val);
 385 
 386   // Provide read-only access to the card table array.
 387   const jbyte* byte_for_const(const void* p) const {
 388     return byte_for(p);
 389   }
 390   const jbyte* byte_after_const(const void* p) const {
 391     return byte_after(p);
 392   }
 393 
 394   // Mapping from card marking array entry to address of first word
 395   HeapWord* addr_for(const jbyte* p) const {
 396     assert(p >= _byte_map && p < _byte_map + _byte_map_size,
 397            "out of bounds access to card marking array");
 398     size_t delta = pointer_delta(p, byte_map_base, sizeof(jbyte));
 399     HeapWord* result = (HeapWord*) (delta << card_shift);
 400     assert(_whole_heap.contains(result),
 401            err_msg("Returning result = "PTR_FORMAT" out of bounds of "
 402                    " card marking array's _whole_heap = ["PTR_FORMAT","PTR_FORMAT")",
 403                    p2i(result), p2i(_whole_heap.start()), p2i(_whole_heap.end())));
 404     return result;
 405   }
 406 
 407   // Mapping from address to card marking array index.
 408   size_t index_for(void* p) {
 409     assert(_whole_heap.contains(p),
 410            err_msg("Attempt to access p = "PTR_FORMAT" out of bounds of "
 411                    " card marking array's _whole_heap = ["PTR_FORMAT","PTR_FORMAT")",
 412                    p2i(p), p2i(_whole_heap.start()), p2i(_whole_heap.end())));
 413     return byte_for(p) - _byte_map;
 414   }
 415 
 416   const jbyte* byte_for_index(const size_t card_index) const {
 417     return _byte_map + card_index;
 418   }
 419 
 420   // Print a description of the memory for the barrier set
 421   virtual void print_on(outputStream* st) const;
 422 
 423   void verify();
 424   void verify_guard();
 425 
 426   // val_equals -> it will check that all cards covered by mr equal val
 427   // !val_equals -> it will check that all cards covered by mr do not equal val
 428   void verify_region(MemRegion mr, jbyte val, bool val_equals) PRODUCT_RETURN;
 429   void verify_not_dirty_region(MemRegion mr) PRODUCT_RETURN;
 430   void verify_dirty_region(MemRegion mr) PRODUCT_RETURN;
 431 };
 432 
 433 template<>
 434 struct BarrierSet::GetName<CardTableModRefBS> {
 435   static const BarrierSet::Name value = BarrierSet::CardTableModRef;
 436 };
 437 
 438 class CardTableRS;
 439 
 440 // A specialization for the CardTableRS gen rem set.
 441 class CardTableModRefBSForCTRS: public CardTableModRefBS {
 442   CardTableRS* _rs;
 443 protected:
 444   bool card_will_be_scanned(jbyte cv);
 445   bool card_may_have_been_dirty(jbyte cv);
 446 public:
 447   CardTableModRefBSForCTRS(MemRegion whole_heap) :
 448     CardTableModRefBS(
 449       whole_heap,
 450       // Concrete tag should be BarrierSet::CardTableForRS.
 451       // That will presently break things in a bunch of places though.
 452       // The concrete tag is used as a dispatch key in many places, and
 453       // CardTableForRS does not correctly dispatch in some of those
 454       // uses. This will be addressed as part of a reorganization of the
 455       // BarrierSet hierarchy.
 456       BarrierSet::FakeRtti(BarrierSet::CardTableModRef, 0).add_tag(BarrierSet::CardTableForRS))
 457     {}
 458 
 459   void set_CTRS(CardTableRS* rs) { _rs = rs; }
 460 };
 461 
 462 template<>
 463 struct BarrierSet::GetName<CardTableModRefBSForCTRS> {
 464   static const BarrierSet::Name value = BarrierSet::CardTableForRS;
 465 };
 466 
 467 
 468 #endif // SHARE_VM_MEMORY_CARDTABLEMODREFBS_HPP