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.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   const uint max_search_depth = G1NUMA::numa()->max_search_depth();
 157   HeapRegion* cur;
 158 
 159   // Find the region to use, searching from _head or _tail as requested.
 160   size_t cur_depth = 0;
 161   if (from_head) {
 162     for (cur = _head;
 163          cur != NULL && cur_depth < max_search_depth;
 164          cur = cur->next(), ++cur_depth) {
 165       if (requested_node_index == cur->node_index()) {
 166         break;
 167       }
 168     }
 169   } else {
 170     for (cur = _tail;
 171          cur != NULL && cur_depth < max_search_depth;
 172          cur = cur->prev(), ++cur_depth) {
 173       if (requested_node_index == cur->node_index()) {
 174         break;
 175       }
 176     }
 177   }
 178 
 179   // Didn't find a region to use.
 180   if (cur == NULL || cur_depth >= max_search_depth) {
 181     return NULL;
 182   }
 183 
 184   // Splice the region out of the list.
 185   HeapRegion* prev = cur->prev();
 186   HeapRegion* next = cur->next();
 187   if (prev == NULL) {
 188     _head = next;
 189   } else {
 190     prev->set_next(next);
 191   }
 192   if (next == NULL) {
 193     _tail = prev;
 194   } else {
 195     next->set_prev(prev);
 196   }
 197   cur->set_prev(NULL);
 198   cur->set_next(NULL);
 199 
 200   if (_last == cur) {
 201     _last = NULL;
 202   }
 203 
 204   remove(cur);
 205   if (allocated_node_index != NULL) {
 206     *allocated_node_index = cur->node_index();
 207   }
 208 
 209   return cur;
 210 }
 211 
 212 #endif // SHARE_GC_G1_HEAPREGIONSET_INLINE_HPP