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 G1FreeIdSet::G1FreeIdSet(uint start, uint size) :

    34   _sem(size),          // counting semaphore for available ids

    35   _next(NULL),         // array of "next" indices

    36   _start(start),       // first id value

    37   _size(size),         // number of available ids

    38   _head_index_mask(0), // mask for extracting index from a _head value.

    39   _head(0)             // low part: index; high part: update counter

    40 {

    41   assert(size != 0, "precondition");

    42   assert(start <= (UINT_MAX - size),

    43          "start (%u) + size (%u) overflow: ", start, size);

    44   // 2^shift must be greater than size. Equal is not permitted, because

    45   // size is the "end of list" value, and can be the index part of _head.

    46   uint shift = log2_intptr((uintptr_t)size) + 1;

    47   assert(shift <= (BitsPerWord / 2), "excessive size %u", size);

    48   _head_index_mask = (uintx(1) << shift) - 1;

    49   assert(size <= _head_index_mask, "invariant");

    50   _next = NEW_C_HEAP_ARRAY(uint, size, mtGC);

    51   for (uint i = 0; i < size; ++i) {

    52     _next[i] = i + 1;

    53   }

    54 }

    55 

    56 G1FreeIdSet::~G1FreeIdSet() {

    57   FREE_C_HEAP_ARRAY(uint, _next);

    58 }

    59 

    60 uint G1FreeIdSet::head_index(uintx head) const {

    61   return head & _head_index_mask;

    62 }

    63 

    64 uintx G1FreeIdSet::make_head(uint index, uintx old_head) const {

    65   // Include incremented old update counter to avoid ABA problem.

    66   return index | ((old_head & ~_head_index_mask) + 1 + _head_index_mask);

    67 }

    68 

    69 const uint Claimed = UINT_MAX;

    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 }