1 /*
   2  * Copyright (c) 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 #include "precompiled.hpp"
  26 #include "gc/g1/g1FreeIdSet.hpp"
  27 #include "memory/allocation.inline.hpp"
  28 #include "runtime/atomic.hpp"
  29 #include "utilities/debug.hpp"
  30 #include "utilities/globalDefinitions.hpp"
  31 #include "utilities/macros.hpp"
  32 
  33 const uint claimed = UINT_MAX;
  34 
  35 G1FreeIdSet::G1FreeIdSet(uint start, uint size) :
  36   _sem(size),          // counting semaphore for available ids
  37   _next(NULL),         // array of "next" indices
  38   _start(start),       // first id value
  39   _size(size),         // number of available ids
  40   _head_index_mask(0), // mask for extracting index from a _head value.
  41   _head(0)             // low part: index; high part: update counter
  42 {
  43   assert(size != 0, "precondition");
  44   assert(start <= (UINT_MAX - size),
  45          "start (%u) + size (%u) overflow: ", start, size);
  46   // 2^shift must be greater than size. Equal is not permitted, because
  47   // size is the "end of list" value, and can be the index part of _head.
  48   uint shift = log2_intptr((uintptr_t)size) + 1;
  49   assert(shift <= (BitsPerWord / 2), "excessive size %u", size);
  50   _head_index_mask = (uintx(1) << shift) - 1;
  51   assert(size <= _head_index_mask, "invariant");
  52   _next = NEW_C_HEAP_ARRAY(uint, size, mtGC);
  53   for (uint i = 0; i < size; ++i) {
  54     _next[i] = i + 1;
  55   }
  56 }
  57 
  58 G1FreeIdSet::~G1FreeIdSet() {
  59   FREE_C_HEAP_ARRAY(uint, _next);
  60 }
  61 
  62 uint G1FreeIdSet::head_index(uintx head) const {
  63   return head & _head_index_mask;
  64 }
  65 
  66 uintx G1FreeIdSet::make_head(uint index, uintx old_head) const {
  67   // Include incremented old update counter to avoid ABA problem.
  68   return index | ((old_head & ~_head_index_mask) + 1 + _head_index_mask);
  69 }
  70 
  71 uint G1FreeIdSet::claim_par_id() {
  72   _sem.wait();
  73   // Semaphore gate permits passage by no more than the number of
  74   // available ids, so there must be one that we can claim.  But there
  75   // may be multiple threads trying to claim ids at the same time.
  76   uintx old_head = Atomic::load(&_head);
  77   uint index;
  78   while (true) {
  79     index = head_index(old_head);
  80     assert(index < _size, "invariant");
  81     uintx new_head = make_head(_next[index], old_head);
  82     new_head = Atomic::cmpxchg(new_head, &_head, old_head);
  83     if (new_head == old_head) break;
  84     old_head = new_head;
  85   }
  86   DEBUG_ONLY(_next[index] = claimed;)
  87   return _start + index;
  88 }
  89 
  90 void G1FreeIdSet::release_par_id(uint id) {
  91   uint index = id - _start;
  92   assert(index < _size, "invalid id %u", id);
  93   assert(_next[index] == claimed, "precondition");
  94   uintx old_head = Atomic::load(&_head);
  95   while (true) {
  96     _next[index] = head_index(old_head);
  97     uintx new_head = make_head(index, old_head);
  98     new_head = Atomic::cmpxchg(new_head, &_head, old_head);
  99     if (new_head == old_head) break;
 100     old_head = new_head;
 101   }
 102   // Now that id has been released, permit another thread through the gate.
 103   _sem.signal();
 104 }