Mercurial > jdk8-mips64-public > hotspot / changeset

     1.1 --- a/src/share/vm/gc_implementation/g1/concurrentMark.cpp	Mon Mar 24 15:34:10 2014 -0700
     1.2 +++ b/src/share/vm/gc_implementation/g1/concurrentMark.cpp	Mon Mar 24 16:56:16 2014 -0700
     1.3 @@ -1929,7 +1929,7 @@
     1.4          }
     1.5        }
     1.6  
     1.7 -      _cleanup_list->add_as_tail(&local_cleanup_list);
     1.8 +      _cleanup_list->add_ordered(&local_cleanup_list);
     1.9        assert(local_cleanup_list.is_empty(), "post-condition");
    1.10  
    1.11        HeapRegionRemSet::finish_cleanup_task(&hrrs_cleanup_task);
    1.12 @@ -2158,9 +2158,9 @@
    1.13    // so it's not necessary to take any locks
    1.14    while (!_cleanup_list.is_empty()) {
    1.15      HeapRegion* hr = _cleanup_list.remove_head();
    1.16 -    assert(hr != NULL, "the list was not empty");
    1.17 +    assert(hr != NULL, "Got NULL from a non-empty list");
    1.18      hr->par_clear();
    1.19 -    tmp_free_list.add_as_tail(hr);
    1.20 +    tmp_free_list.add_ordered(hr);
    1.21  
    1.22      // Instead of adding one region at a time to the secondary_free_list,
    1.23      // we accumulate them in the local list and move them a few at a
    1.24 @@ -2180,7 +2180,7 @@
    1.25  
    1.26        {
    1.27          MutexLockerEx x(SecondaryFreeList_lock, Mutex::_no_safepoint_check_flag);
    1.28 -        g1h->secondary_free_list_add_as_tail(&tmp_free_list);
    1.29 +        g1h->secondary_free_list_add(&tmp_free_list);
    1.30          SecondaryFreeList_lock->notify_all();
    1.31        }
    1.32  

     2.1 --- a/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Mon Mar 24 15:34:10 2014 -0700
     2.2 +++ b/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Mon Mar 24 16:56:16 2014 -0700
     2.3 @@ -517,7 +517,7 @@
     2.4  // Private methods.
     2.5  
     2.6  HeapRegion*
     2.7 -G1CollectedHeap::new_region_try_secondary_free_list() {
     2.8 +G1CollectedHeap::new_region_try_secondary_free_list(bool is_old) {
     2.9    MutexLockerEx x(SecondaryFreeList_lock, Mutex::_no_safepoint_check_flag);
    2.10    while (!_secondary_free_list.is_empty() || free_regions_coming()) {
    2.11      if (!_secondary_free_list.is_empty()) {
    2.12 @@ -533,7 +533,7 @@
    2.13  
    2.14        assert(!_free_list.is_empty(), "if the secondary_free_list was not "
    2.15               "empty we should have moved at least one entry to the free_list");
    2.16 -      HeapRegion* res = _free_list.remove_head();
    2.17 +      HeapRegion* res = _free_list.remove_region(is_old);
    2.18        if (G1ConcRegionFreeingVerbose) {
    2.19          gclog_or_tty->print_cr("G1ConcRegionFreeing [region alloc] : "
    2.20                                 "allocated "HR_FORMAT" from secondary_free_list",
    2.21 @@ -555,7 +555,7 @@
    2.22    return NULL;
    2.23  }
    2.24  
    2.25 -HeapRegion* G1CollectedHeap::new_region(size_t word_size, bool do_expand) {
    2.26 +HeapRegion* G1CollectedHeap::new_region(size_t word_size, bool is_old, bool do_expand) {
    2.27    assert(!isHumongous(word_size) || word_size <= HeapRegion::GrainWords,
    2.28           "the only time we use this to allocate a humongous region is "
    2.29           "when we are allocating a single humongous region");
    2.30 @@ -567,19 +567,21 @@
    2.31          gclog_or_tty->print_cr("G1ConcRegionFreeing [region alloc] : "
    2.32                                 "forced to look at the secondary_free_list");
    2.33        }
    2.34 -      res = new_region_try_secondary_free_list();
    2.35 +      res = new_region_try_secondary_free_list(is_old);
    2.36        if (res != NULL) {
    2.37          return res;
    2.38        }
    2.39      }
    2.40    }
    2.41 -  res = _free_list.remove_head_or_null();
    2.42 +
    2.43 +  res = _free_list.remove_region(is_old);
    2.44 +
    2.45    if (res == NULL) {
    2.46      if (G1ConcRegionFreeingVerbose) {
    2.47        gclog_or_tty->print_cr("G1ConcRegionFreeing [region alloc] : "
    2.48                               "res == NULL, trying the secondary_free_list");
    2.49      }
    2.50 -    res = new_region_try_secondary_free_list();
    2.51 +    res = new_region_try_secondary_free_list(is_old);
    2.52    }
    2.53    if (res == NULL && do_expand && _expand_heap_after_alloc_failure) {
    2.54      // Currently, only attempts to allocate GC alloc regions set
    2.55 @@ -596,12 +598,9 @@
    2.56      if (expand(word_size * HeapWordSize)) {
    2.57        // Given that expand() succeeded in expanding the heap, and we
    2.58        // always expand the heap by an amount aligned to the heap
    2.59 -      // region size, the free list should in theory not be empty. So
    2.60 -      // it would probably be OK to use remove_head(). But the extra
    2.61 -      // check for NULL is unlikely to be a performance issue here (we
    2.62 -      // just expanded the heap!) so let's just be conservative and
    2.63 -      // use remove_head_or_null().
    2.64 -      res = _free_list.remove_head_or_null();
    2.65 +      // region size, the free list should in theory not be empty.
    2.66 +      // In either case remove_region() will check for NULL.
    2.67 +      res = _free_list.remove_region(is_old);
    2.68      } else {
    2.69        _expand_heap_after_alloc_failure = false;
    2.70      }
    2.71 @@ -619,7 +618,7 @@
    2.72      // Only one region to allocate, no need to go through the slower
    2.73      // path. The caller will attempt the expansion if this fails, so
    2.74      // let's not try to expand here too.
    2.75 -    HeapRegion* hr = new_region(word_size, false /* do_expand */);
    2.76 +    HeapRegion* hr = new_region(word_size, true /* is_old */, false /* do_expand */);
    2.77      if (hr != NULL) {
    2.78        first = hr->hrs_index();
    2.79      } else {
    2.80 @@ -5970,7 +5969,7 @@
    2.81      _cg1r->hot_card_cache()->reset_card_counts(hr);
    2.82    }
    2.83    hr->hr_clear(par, true /* clear_space */, locked /* locked */);
    2.84 -  free_list->add_as_head(hr);
    2.85 +  free_list->add_ordered(hr);
    2.86  }
    2.87  
    2.88  void G1CollectedHeap::free_humongous_region(HeapRegion* hr,
    2.89 @@ -6010,7 +6009,7 @@
    2.90    assert(list != NULL, "list can't be null");
    2.91    if (!list->is_empty()) {
    2.92      MutexLockerEx x(FreeList_lock, Mutex::_no_safepoint_check_flag);
    2.93 -    _free_list.add_as_head(list);
    2.94 +    _free_list.add_ordered(list);
    2.95    }
    2.96  }
    2.97  
    2.98 @@ -6481,6 +6480,7 @@
    2.99    bool young_list_full = g1_policy()->is_young_list_full();
   2.100    if (force || !young_list_full) {
   2.101      HeapRegion* new_alloc_region = new_region(word_size,
   2.102 +                                              false /* is_old */,
   2.103                                                false /* do_expand */);
   2.104      if (new_alloc_region != NULL) {
   2.105        set_region_short_lived_locked(new_alloc_region);
   2.106 @@ -6539,14 +6539,16 @@
   2.107    assert(FreeList_lock->owned_by_self(), "pre-condition");
   2.108  
   2.109    if (count < g1_policy()->max_regions(ap)) {
   2.110 +    bool survivor = (ap == GCAllocForSurvived);
   2.111      HeapRegion* new_alloc_region = new_region(word_size,
   2.112 +                                              !survivor,
   2.113                                                true /* do_expand */);
   2.114      if (new_alloc_region != NULL) {
   2.115        // We really only need to do this for old regions given that we
   2.116        // should never scan survivors. But it doesn't hurt to do it
   2.117        // for survivors too.
   2.118        new_alloc_region->set_saved_mark();
   2.119 -      if (ap == GCAllocForSurvived) {
   2.120 +      if (survivor) {
   2.121          new_alloc_region->set_survivor();
   2.122          _hr_printer.alloc(new_alloc_region, G1HRPrinter::Survivor);
   2.123        } else {

     3.1 --- a/src/share/vm/gc_implementation/g1/g1CollectedHeap.hpp	Mon Mar 24 15:34:10 2014 -0700
     3.2 +++ b/src/share/vm/gc_implementation/g1/g1CollectedHeap.hpp	Mon Mar 24 16:56:16 2014 -0700
     3.3 @@ -497,13 +497,14 @@
     3.4    // check whether there's anything available on the
     3.5    // secondary_free_list and/or wait for more regions to appear on
     3.6    // that list, if _free_regions_coming is set.
     3.7 -  HeapRegion* new_region_try_secondary_free_list();
     3.8 +  HeapRegion* new_region_try_secondary_free_list(bool is_old);
     3.9  
    3.10    // Try to allocate a single non-humongous HeapRegion sufficient for
    3.11    // an allocation of the given word_size. If do_expand is true,
    3.12    // attempt to expand the heap if necessary to satisfy the allocation
    3.13 -  // request.
    3.14 -  HeapRegion* new_region(size_t word_size, bool do_expand);
    3.15 +  // request. If the region is to be used as an old region or for a
    3.16 +  // humongous object, set is_old to true. If not, to false.
    3.17 +  HeapRegion* new_region(size_t word_size, bool is_old, bool do_expand);
    3.18  
    3.19    // Attempt to satisfy a humongous allocation request of the given
    3.20    // size by finding a contiguous set of free regions of num_regions
    3.21 @@ -1246,12 +1247,12 @@
    3.22    // Wrapper for the region list operations that can be called from
    3.23    // methods outside this class.
    3.24  
    3.25 -  void secondary_free_list_add_as_tail(FreeRegionList* list) {
    3.26 -    _secondary_free_list.add_as_tail(list);
    3.27 +  void secondary_free_list_add(FreeRegionList* list) {
    3.28 +    _secondary_free_list.add_ordered(list);
    3.29    }
    3.30  
    3.31    void append_secondary_free_list() {
    3.32 -    _free_list.add_as_head(&_secondary_free_list);
    3.33 +    _free_list.add_ordered(&_secondary_free_list);
    3.34    }
    3.35  
    3.36    void append_secondary_free_list_if_not_empty_with_lock() {

     4.1 --- a/src/share/vm/gc_implementation/g1/heapRegion.cpp	Mon Mar 24 15:34:10 2014 -0700
     4.2 +++ b/src/share/vm/gc_implementation/g1/heapRegion.cpp	Mon Mar 24 16:56:16 2014 -0700
     4.3 @@ -356,7 +356,7 @@
     4.4      _claimed(InitialClaimValue), _evacuation_failed(false),
     4.5      _prev_marked_bytes(0), _next_marked_bytes(0), _gc_efficiency(0.0),
     4.6      _young_type(NotYoung), _next_young_region(NULL),
     4.7 -    _next_dirty_cards_region(NULL), _next(NULL), _pending_removal(false),
     4.8 +    _next_dirty_cards_region(NULL), _next(NULL), _prev(NULL), _pending_removal(false),
     4.9  #ifdef ASSERT
    4.10      _containing_set(NULL),
    4.11  #endif // ASSERT

     5.1 --- a/src/share/vm/gc_implementation/g1/heapRegion.hpp	Mon Mar 24 15:34:10 2014 -0700
     5.2 +++ b/src/share/vm/gc_implementation/g1/heapRegion.hpp	Mon Mar 24 16:56:16 2014 -0700
     5.3 @@ -271,6 +271,7 @@
     5.4  
     5.5    // Fields used by the HeapRegionSetBase class and subclasses.
     5.6    HeapRegion* _next;
     5.7 +  HeapRegion* _prev;
     5.8  #ifdef ASSERT
     5.9    HeapRegionSetBase* _containing_set;
    5.10  #endif // ASSERT
    5.11 @@ -531,11 +532,13 @@
    5.12  
    5.13    // Methods used by the HeapRegionSetBase class and subclasses.
    5.14  
    5.15 -  // Getter and setter for the next field used to link regions into
    5.16 +  // Getter and setter for the next and prev fields used to link regions into
    5.17    // linked lists.
    5.18    HeapRegion* next()              { return _next; }
    5.19 +  HeapRegion* prev()              { return _prev; }
    5.20  
    5.21    void set_next(HeapRegion* next) { _next = next; }
    5.22 +  void set_prev(HeapRegion* prev) { _prev = prev; }
    5.23  
    5.24    // Every region added to a set is tagged with a reference to that
    5.25    // set. This is used for doing consistency checking to make sure that

     6.1 --- a/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Mon Mar 24 15:34:10 2014 -0700
     6.2 +++ b/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Mon Mar 24 16:56:16 2014 -0700
     6.3 @@ -1,5 +1,5 @@
     6.4  /*
     6.5 - * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
     6.6 + * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
     6.7   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     6.8   *
     6.9   * This code is free software; you can redistribute it and/or modify it
    6.10 @@ -135,9 +135,11 @@
    6.11      assert(length() > 0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
    6.12      if (as_head) {
    6.13        from_list->_tail->set_next(_head);
    6.14 +      _head->set_prev(from_list->_tail);
    6.15        _head = from_list->_head;
    6.16      } else {
    6.17        _tail->set_next(from_list->_head);
    6.18 +      from_list->_head->set_prev(_tail);
    6.19        _tail = from_list->_tail;
    6.20      }
    6.21    }
    6.22 @@ -167,6 +169,7 @@
    6.23  
    6.24      HeapRegion* next = curr->next();
    6.25      curr->set_next(NULL);
    6.26 +    curr->set_prev(NULL);
    6.27      curr->set_containing_set(NULL);
    6.28      curr = next;
    6.29    }
    6.30 @@ -175,6 +178,74 @@
    6.31    verify_optional();
    6.32  }
    6.33  
    6.34 +void FreeRegionList::add_ordered(FreeRegionList* from_list) {
    6.35 +  check_mt_safety();
    6.36 +  from_list->check_mt_safety();
    6.37 +
    6.38 +  verify_optional();
    6.39 +  from_list->verify_optional();
    6.40 +
    6.41 +  if (from_list->is_empty()) {
    6.42 +    return;
    6.43 +  }
    6.44 +
    6.45 +  if (is_empty()) {
    6.46 +    add_as_head(from_list);
    6.47 +    return;
    6.48 +  }
    6.49 +
    6.50 +  #ifdef ASSERT
    6.51 +  FreeRegionListIterator iter(from_list);
    6.52 +  while (iter.more_available()) {
    6.53 +    HeapRegion* hr = iter.get_next();
    6.54 +    // In set_containing_set() we check that we either set the value
    6.55 +    // from NULL to non-NULL or vice versa to catch bugs. So, we have
    6.56 +    // to NULL it first before setting it to the value.
    6.57 +    hr->set_containing_set(NULL);
    6.58 +    hr->set_containing_set(this);
    6.59 +  }
    6.60 +  #endif // ASSERT
    6.61 +
    6.62 +  HeapRegion* curr_to = _head;
    6.63 +  HeapRegion* curr_from = from_list->_head;
    6.64 +
    6.65 +  while (curr_from != NULL) {
    6.66 +    while (curr_to != NULL && curr_to->hrs_index() < curr_from->hrs_index()) {
    6.67 +      curr_to = curr_to->next();
    6.68 +    }
    6.69 +
    6.70 +    if (curr_to == NULL) {
    6.71 +      // The rest of the from list should be added as tail
    6.72 +      _tail->set_next(curr_from);
    6.73 +      curr_from->set_prev(_tail);
    6.74 +      curr_from = NULL;
    6.75 +    } else {
    6.76 +      HeapRegion* next_from = curr_from->next();
    6.77 +
    6.78 +      curr_from->set_next(curr_to);
    6.79 +      curr_from->set_prev(curr_to->prev());
    6.80 +      if (curr_to->prev() == NULL) {
    6.81 +        _head = curr_from;
    6.82 +      } else {
    6.83 +        curr_to->prev()->set_next(curr_from);
    6.84 +      }
    6.85 +      curr_to->set_prev(curr_from);
    6.86 +
    6.87 +      curr_from = next_from;
    6.88 +    }
    6.89 +  }
    6.90 +
    6.91 +  if (_tail->hrs_index() < from_list->_tail->hrs_index()) {
    6.92 +    _tail = from_list->_tail;
    6.93 +  }
    6.94 +
    6.95 +  _count.increment(from_list->length(), from_list->total_capacity_bytes());
    6.96 +  from_list->clear();
    6.97 +
    6.98 +  verify_optional();
    6.99 +  from_list->verify_optional();
   6.100 +}
   6.101 +
   6.102  void FreeRegionList::remove_all_pending(uint target_count) {
   6.103    check_mt_safety();
   6.104    assert(target_count > 1, hrs_ext_msg(this, "pre-condition"));
   6.105 @@ -184,11 +255,11 @@
   6.106    DEBUG_ONLY(uint old_length = length();)
   6.107  
   6.108    HeapRegion* curr = _head;
   6.109 -  HeapRegion* prev = NULL;
   6.110    uint count = 0;
   6.111    while (curr != NULL) {
   6.112      verify_region(curr);
   6.113      HeapRegion* next = curr->next();
   6.114 +    HeapRegion* prev = curr->prev();
   6.115  
   6.116      if (curr->pending_removal()) {
   6.117        assert(count < target_count,
   6.118 @@ -208,9 +279,14 @@
   6.119          _tail = prev;
   6.120        } else {
   6.121          assert(_tail != curr, hrs_ext_msg(this, "invariant"));
   6.122 +        next->set_prev(prev);
   6.123 +      }
   6.124 +      if (_last = curr) {
   6.125 +        _last = NULL;
   6.126        }
   6.127  
   6.128        curr->set_next(NULL);
   6.129 +      curr->set_prev(NULL);
   6.130        remove(curr);
   6.131        curr->set_pending_removal(false);
   6.132  
   6.133 @@ -221,8 +297,6 @@
   6.134        // carry on iterating to make sure there are not more regions
   6.135        // tagged with pending removal.
   6.136        DEBUG_ONLY(if (count == target_count) break;)
   6.137 -    } else {
   6.138 -      prev = curr;
   6.139      }
   6.140      curr = next;
   6.141    }
   6.142 @@ -255,6 +329,7 @@
   6.143    _count = HeapRegionSetCount();
   6.144    _head = NULL;
   6.145    _tail = NULL;
   6.146 +  _last = NULL;
   6.147  }
   6.148  
   6.149  void FreeRegionList::print_on(outputStream* out, bool print_contents) {
   6.150 @@ -279,6 +354,9 @@
   6.151    HeapRegion* prev0 = NULL;
   6.152    uint count = 0;
   6.153    size_t capacity = 0;
   6.154 +  uint last_index = 0;
   6.155 +
   6.156 +  guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev");
   6.157    while (curr != NULL) {
   6.158      verify_region(curr);
   6.159  
   6.160 @@ -286,6 +364,12 @@
   6.161      guarantee(count < _unrealistically_long_length,
   6.162          hrs_err_msg("[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: "PTR_FORMAT" prev0: "PTR_FORMAT" " "prev1: "PTR_FORMAT" length: %u", name(), count, curr, prev0, prev1, length()));
   6.163  
   6.164 +    if (curr->next() != NULL) {
   6.165 +      guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up");
   6.166 +    }
   6.167 +    guarantee(curr->hrs_index() == 0 || curr->hrs_index() > last_index, "List should be sorted");
   6.168 +    last_index = curr->hrs_index();
   6.169 +
   6.170      capacity += curr->capacity();
   6.171  
   6.172      prev1 = prev0;
   6.173 @@ -294,7 +378,7 @@
   6.174    }
   6.175  
   6.176    guarantee(tail() == prev0, err_msg("Expected %s to end with %u but it ended with %u.", name(), tail()->hrs_index(), prev0->hrs_index()));
   6.177 -
   6.178 +  guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next");
   6.179    guarantee(length() == count, err_msg("%s count mismatch. Expected %u, actual %u.", name(), length(), count));
   6.180    guarantee(total_capacity_bytes() == capacity, err_msg("%s capacity mismatch. Expected " SIZE_FORMAT ", actual " SIZE_FORMAT,
   6.181        name(), total_capacity_bytes(), capacity));

     7.1 --- a/src/share/vm/gc_implementation/g1/heapRegionSet.hpp	Mon Mar 24 15:34:10 2014 -0700
     7.2 +++ b/src/share/vm/gc_implementation/g1/heapRegionSet.hpp	Mon Mar 24 16:56:16 2014 -0700
     7.3 @@ -1,5 +1,5 @@
     7.4  /*
     7.5 - * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
     7.6 + * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
     7.7   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     7.8   *
     7.9   * This code is free software; you can redistribute it and/or modify it
    7.10 @@ -191,11 +191,14 @@
    7.11    }
    7.12  };
    7.13  
    7.14 -// A set that links all the regions added to it in a singly-linked
    7.15 +// A set that links all the regions added to it in a doubly-linked
    7.16  // list. We should try to avoid doing operations that iterate over
    7.17  // such lists in performance critical paths. Typically we should
    7.18 -// add / remove one region at a time or concatenate two lists. All
    7.19 -// those operations are done in constant time.
    7.20 +// add / remove one region at a time or concatenate two lists. There are
    7.21 +// two ways to treat your lists, ordered and un-ordered. All un-ordered
    7.22 +// operations are done in constant time. To keep a list ordered only use
    7.23 +// add_ordered() to add elements to the list. If a list is not ordered
    7.24 +// from start, there is no way to sort it later.
    7.25  
    7.26  class FreeRegionListIterator;
    7.27  
    7.28 @@ -206,6 +209,11 @@
    7.29    HeapRegion* _head;
    7.30    HeapRegion* _tail;
    7.31  
    7.32 +  // _last is used to keep track of where we added an element the last
    7.33 +  // time in ordered lists. It helps to improve performance when adding
    7.34 +  // several ordered items in a row.
    7.35 +  HeapRegion* _last;
    7.36 +
    7.37    static uint _unrealistically_long_length;
    7.38  
    7.39    void add_as_head_or_tail(FreeRegionList* from_list, bool as_head);
    7.40 @@ -229,6 +237,11 @@
    7.41  
    7.42    static void set_unrealistically_long_length(uint len);
    7.43  
    7.44 +  // Add hr to the list. The region should not be a member of another set.
    7.45 +  // Assumes that the list is ordered and will preserve that order. The order
    7.46 +  // is determined by hrs_index.
    7.47 +  inline void add_ordered(HeapRegion* hr);
    7.48 +
    7.49    // It adds hr to the list as the new head. The region should not be
    7.50    // a member of another set.
    7.51    inline void add_as_head(HeapRegion* hr);
    7.52 @@ -244,6 +257,20 @@
    7.53    // Convenience method.
    7.54    inline HeapRegion* remove_head_or_null();
    7.55  
    7.56 +  // Removes and returns the last element (_tail) of the list. It assumes
    7.57 +  // that the list isn't empty so that it can return a non-NULL value.
    7.58 +  inline HeapRegion* remove_tail();
    7.59 +
    7.60 +  // Convenience method
    7.61 +  inline HeapRegion* remove_tail_or_null();
    7.62 +
    7.63 +  // Removes from head or tail based on the given argument.
    7.64 +  inline HeapRegion* remove_region(bool from_head);
    7.65 +
    7.66 +  // Merge two ordered lists. The result is also ordered. The order is
    7.67 +  // determined by hrs_index.
    7.68 +  void add_ordered(FreeRegionList* from_list);
    7.69 +
    7.70    // It moves the regions from from_list to this list and empties
    7.71    // from_list. The new regions will appear in the same order as they
    7.72    // were in from_list and be linked in the beginning of this list.
    7.73 @@ -276,7 +303,7 @@
    7.74  class FreeRegionListIterator : public StackObj {
    7.75  private:
    7.76    FreeRegionList* _list;
    7.77 -  HeapRegion*           _curr;
    7.78 +  HeapRegion*     _curr;
    7.79  
    7.80  public:
    7.81    bool more_available() {
    7.82 @@ -296,8 +323,7 @@
    7.83      return hr;
    7.84    }
    7.85  
    7.86 -  FreeRegionListIterator(FreeRegionList* list)
    7.87 -    : _curr(NULL), _list(list) {
    7.88 +  FreeRegionListIterator(FreeRegionList* list) : _curr(NULL), _list(list) {
    7.89      _curr = list->head();
    7.90    }
    7.91  };

     8.1 --- a/src/share/vm/gc_implementation/g1/heapRegionSet.inline.hpp	Mon Mar 24 15:34:10 2014 -0700
     8.2 +++ b/src/share/vm/gc_implementation/g1/heapRegionSet.inline.hpp	Mon Mar 24 16:56:16 2014 -0700
     8.3 @@ -1,5 +1,5 @@
     8.4  /*
     8.5 - * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
     8.6 + * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
     8.7   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     8.8   *
     8.9   * This code is free software; you can redistribute it and/or modify it
    8.10 @@ -47,6 +47,54 @@
    8.11    _count.decrement(1u, hr->capacity());
    8.12  }
    8.13  
    8.14 +inline void FreeRegionList::add_ordered(HeapRegion* hr) {
    8.15 +  check_mt_safety();
    8.16 +  assert((length() == 0 && _head == NULL && _tail == NULL) ||
    8.17 +         (length() >  0 && _head != NULL && _tail != NULL),
    8.18 +         hrs_ext_msg(this, "invariant"));
    8.19 +  // add() will verify the region and check mt safety.
    8.20 +  add(hr);
    8.21 +
    8.22 +  // Now link the region
    8.23 +  if (_head != NULL) {
    8.24 +    HeapRegion* curr;
    8.25 +
    8.26 +    if (_last != NULL && _last->hrs_index() < hr->hrs_index()) {
    8.27 +      curr = _last;
    8.28 +    } else {
    8.29 +      curr = _head;
    8.30 +    }
    8.31 +
    8.32 +    // Find first entry with a Region Index larger than entry to insert.
    8.33 +    while (curr != NULL && curr->hrs_index() < hr->hrs_index()) {
    8.34 +      curr = curr->next();
    8.35 +    }
    8.36 +
    8.37 +    hr->set_next(curr);
    8.38 +
    8.39 +    if (curr == NULL) {
    8.40 +      // Adding at the end
    8.41 +      hr->set_prev(_tail);
    8.42 +      _tail->set_next(hr);
    8.43 +      _tail = hr;
    8.44 +    } else if (curr->prev() == NULL) {
    8.45 +      // Adding at the beginning
    8.46 +      hr->set_prev(NULL);
    8.47 +      _head = hr;
    8.48 +      curr->set_prev(hr);
    8.49 +    } else {
    8.50 +      hr->set_prev(curr->prev());
    8.51 +      hr->prev()->set_next(hr);
    8.52 +      curr->set_prev(hr);
    8.53 +    }
    8.54 +  } else {
    8.55 +    // The list was empty
    8.56 +    _tail = hr;
    8.57 +    _head = hr;
    8.58 +  }
    8.59 +  _last = hr;
    8.60 +}
    8.61 +
    8.62  inline void FreeRegionList::add_as_head(HeapRegion* hr) {
    8.63    assert((length() == 0 && _head == NULL && _tail == NULL) ||
    8.64           (length() >  0 && _head != NULL && _tail != NULL),
    8.65 @@ -57,6 +105,7 @@
    8.66    // Now link the region.
    8.67    if (_head != NULL) {
    8.68      hr->set_next(_head);
    8.69 +    _head->set_prev(hr);
    8.70    } else {
    8.71      _tail = hr;
    8.72    }
    8.73 @@ -68,12 +117,13 @@
    8.74    assert((length() == 0 && _head == NULL && _tail == NULL) ||
    8.75           (length() >  0 && _head != NULL && _tail != NULL),
    8.76           hrs_ext_msg(this, "invariant"));
    8.77 -  // add() will verify the region and check mt safety
    8.78 +  // add() will verify the region and check mt safety.
    8.79    add(hr);
    8.80  
    8.81    // Now link the region.
    8.82    if (_tail != NULL) {
    8.83      _tail->set_next(hr);
    8.84 +    hr->set_prev(_tail);
    8.85    } else {
    8.86      _head = hr;
    8.87    }
    8.88 @@ -90,10 +140,16 @@
    8.89    _head = hr->next();
    8.90    if (_head == NULL) {
    8.91      _tail = NULL;
    8.92 +  } else {
    8.93 +    _head->set_prev(NULL);
    8.94    }
    8.95    hr->set_next(NULL);
    8.96  
    8.97 -  // remove() will verify the region and check mt safety
    8.98 +  if (_last == hr) {
    8.99 +    _last = NULL;
   8.100 +  }
   8.101 +
   8.102 +  // remove() will verify the region and check mt safety.
   8.103    remove(hr);
   8.104    return hr;
   8.105  }
   8.106 @@ -107,4 +163,47 @@
   8.107    }
   8.108  }
   8.109  
   8.110 +inline HeapRegion* FreeRegionList::remove_tail() {
   8.111 +  assert(!is_empty(), hrs_ext_msg(this, "The list should not be empty"));
   8.112 +  assert(length() > 0 && _head != NULL && _tail != NULL,
   8.113 +         hrs_ext_msg(this, "invariant"));
   8.114 +
   8.115 +  // We need to unlink it first
   8.116 +  HeapRegion* hr = _tail;
   8.117 +
   8.118 +  _tail = hr->prev();
   8.119 +  if (_tail == NULL) {
   8.120 +    _head = NULL;
   8.121 +  } else {
   8.122 +    _tail->set_next(NULL);
   8.123 +  }
   8.124 +  hr->set_prev(NULL);
   8.125 +
   8.126 +  if (_last == hr) {
   8.127 +    _last = NULL;
   8.128 +  }
   8.129 +
   8.130 +  // remove() will verify the region and check mt safety.
   8.131 +  remove(hr);
   8.132 +  return hr;
   8.133 +}
   8.134 +
   8.135 +inline HeapRegion* FreeRegionList::remove_tail_or_null() {
   8.136 +  check_mt_safety();
   8.137 +
   8.138 +  if (!is_empty()) {
   8.139 +    return remove_tail();
   8.140 +  } else {
   8.141 +    return NULL;
   8.142 +  }
   8.143 +}
   8.144 +
   8.145 +inline HeapRegion* FreeRegionList::remove_region(bool from_head) {
   8.146 +  if (from_head) {
   8.147 +    return remove_head_or_null();
   8.148 +  } else {
   8.149 +    return remove_tail_or_null();
   8.150 +  }
   8.151 +}
   8.152 +
   8.153  #endif // SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSET_INLINE_HPP