1 /*
   2  * Copyright (c) 2011, 2019, 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_GC_G1_HEAPREGIONSET_INLINE_HPP
  26 #define SHARE_GC_G1_HEAPREGIONSET_INLINE_HPP
  27 
  28 #include "gc/g1/g1NUMA.inline.hpp"
  29 #include "gc/g1/heapRegionSet.hpp"
  30 
  31 inline void HeapRegionSetBase::add(HeapRegion* hr) {
  32   check_mt_safety();
  33   assert_heap_region_set(hr->containing_set() == NULL, "should not already have a containing set");
  34   assert_heap_region_set(hr->next() == NULL, "should not already be linked");
  35   assert_heap_region_set(hr->prev() == NULL, "should not already be linked");
  36 
  37   _length++;
  38   hr->set_containing_set(this);
  39   verify_region(hr);
  40 }
  41 
  42 inline void HeapRegionSetBase::remove(HeapRegion* hr) {
  43   check_mt_safety();
  44   verify_region(hr);
  45   assert_heap_region_set(hr->next() == NULL, "should already be unlinked");
  46   assert_heap_region_set(hr->prev() == NULL, "should already be unlinked");
  47 
  48   hr->set_containing_set(NULL);
  49   assert_heap_region_set(_length > 0, "pre-condition");
  50   _length--;
  51 }
  52 
  53 inline void FreeRegionList::add_ordered(HeapRegion* hr) {
  54   assert_free_region_list((length() == 0 && _head == NULL && _tail == NULL && _last == NULL) ||
  55                           (length() >  0 && _head != NULL && _tail != NULL),
  56                           "invariant");
  57   // add() will verify the region and check mt safety.
  58   add(hr);
  59 
  60   // Now link the region
  61   if (_head != NULL) {
  62     HeapRegion* curr;
  63 
  64     if (_last != NULL && _last->hrm_index() < hr->hrm_index()) {
  65       curr = _last;
  66     } else {
  67       curr = _head;
  68     }
  69 
  70     // Find first entry with a Region Index larger than entry to insert.
  71     while (curr != NULL && curr->hrm_index() < hr->hrm_index()) {
  72       curr = curr->next();
  73     }
  74 
  75     hr->set_next(curr);
  76 
  77     if (curr == NULL) {
  78       // Adding at the end
  79       hr->set_prev(_tail);
  80       _tail->set_next(hr);
  81       _tail = hr;
  82     } else if (curr->prev() == NULL) {
  83       // Adding at the beginning
  84       hr->set_prev(NULL);
  85       _head = hr;
  86       curr->set_prev(hr);
  87     } else {
  88       hr->set_prev(curr->prev());
  89       hr->prev()->set_next(hr);
  90       curr->set_prev(hr);
  91     }
  92   } else {
  93     // The list was empty
  94     _tail = hr;
  95     _head = hr;
  96   }
  97   _last = hr;
  98 }
  99 
 100 inline HeapRegion* FreeRegionList::remove_from_head_impl() {
 101   HeapRegion* result = _head;
 102   _head = result->next();
 103   if (_head == NULL) {
 104     _tail = NULL;
 105   } else {
 106     _head->set_prev(NULL);
 107   }
 108   result->set_next(NULL);
 109   return result;
 110 }
 111 
 112 inline HeapRegion* FreeRegionList::remove_from_tail_impl() {
 113   HeapRegion* result = _tail;
 114 
 115   _tail = result->prev();
 116   if (_tail == NULL) {
 117     _head = NULL;
 118   } else {
 119     _tail->set_next(NULL);
 120   }
 121   result->set_prev(NULL);
 122   return result;
 123 }
 124 
 125 inline HeapRegion* FreeRegionList::remove_region(bool from_head) {
 126   check_mt_safety();
 127   verify_optional();
 128 
 129   if (is_empty()) {
 130     return NULL;
 131   }
 132   assert_free_region_list(length() > 0 && _head != NULL && _tail != NULL, "invariant");
 133 
 134   HeapRegion* hr;
 135 
 136   if (from_head) {
 137     hr = remove_from_head_impl();
 138   } else {
 139     hr = remove_from_tail_impl();
 140   }
 141 
 142   if (_last == hr) {
 143     _last = NULL;
 144   }
 145 
 146   // remove() will verify the region and check mt safety.
 147   remove(hr);
 148   return hr;
 149 }
 150 
 151 inline HeapRegion* FreeRegionList::remove_region_with_node_index(bool from_head,
 152                                                                  const uint requested_node_index,
 153                                                                  uint* allocated_node_index) {
 154   assert(UseNUMA, "Invariant");
 155 
 156   HeapRegion * cur;
 157   G1NUMA* numa = G1NUMA::numa();
 158 
 159   if (!numa->is_valid_numa_index(requested_node_index)) {
 160     return NULL;
 161   }
 162 
 163   // Multiple of 3 is just random number to limit iterations.
 164   uint const max_search_depth = 3 * numa->num_active_numa_ids();
 165 
 166   // Find the region to use, searching from _head or _tail as requested.
 167   size_t cur_depth = 0;
 168   if (from_head) {
 169     for (cur = _head;
 170          cur != NULL && cur_depth < max_search_depth;
 171          cur = cur->next(), ++cur_depth) {
 172       if (requested_node_index == cur->node_index()) {
 173         break;
 174       }
 175     }
 176   } else {
 177     for (cur = _tail;
 178          cur != NULL && cur_depth < max_search_depth;
 179          cur = cur->prev(), ++cur_depth) {
 180       if (requested_node_index == cur->node_index()) {
 181         break;
 182       }
 183     }
 184   }
 185 
 186   // Didn't find a region to use.
 187   if (cur == NULL || cur_depth >= max_search_depth) {
 188     return NULL;
 189   }
 190 
 191   // Splice the region out of the list.
 192   HeapRegion* prev = cur->prev();
 193   HeapRegion* next = cur->next();
 194   if (prev == NULL) {
 195     _head = next;
 196   } else {
 197     prev->set_next(next);
 198   }
 199   if (next == NULL) {
 200     _tail = prev;
 201   } else {
 202     next->set_prev(prev);
 203   }
 204   cur->set_prev(NULL);
 205   cur->set_next(NULL);
 206 
 207   if (_last == cur) {
 208     _last = NULL;
 209   }
 210 
 211   remove(cur);
 212   if (allocated_node_index != NULL) {
 213     *allocated_node_index = cur->node_index();
 214   }
 215 
 216   return cur;
 217 }
 218 
 219 #endif // SHARE_GC_G1_HEAPREGIONSET_INLINE_HPP