1 /*
   2  * Copyright (c) 2016, 2018, 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 #include "precompiled.hpp"
  25 #include "gc/z/zErrno.hpp"
  26 #include "gc/z/zGlobals.hpp"
  27 #include "gc/z/zLock.inline.hpp"
  28 #include "gc/z/zMarkStack.inline.hpp"
  29 #include "logging/log.hpp"
  30 #include "runtime/atomic.hpp"
  31 #include "utilities/debug.hpp"
  32 
  33 #include <sys/mman.h>
  34 #include <sys/types.h>
  35 
  36 ZMarkStackSpace::ZMarkStackSpace() :
  37     _expand_lock(),
  38     _top(0),
  39     _end(0) {
  40   assert(ZMarkStacksMax >= ZMarkStackSpaceExpandSize, "ZMarkStacksMax too small");
  41   assert(ZMarkStacksMax <= ZMarkStackSpaceSize, "ZMarkStacksMax too large");
  42 
  43   // Reserve address space
  44   const void* res = mmap((void*)ZMarkStackSpaceStart, ZMarkStackSpaceSize,
  45                          PROT_NONE, MAP_ANONYMOUS|MAP_PRIVATE|MAP_NORESERVE, -1, 0);
  46   if (res != (void*)ZMarkStackSpaceStart) {
  47     log_error(gc, marking)("Failed to reserve address space for marking stacks");
  48     return;
  49   }
  50 
  51   // Successfully initialized
  52   _top = _end = ZMarkStackSpaceStart;
  53 }
  54 
  55 bool ZMarkStackSpace::is_initialized() const {
  56   return _top != 0;
  57 }
  58 
  59 bool ZMarkStackSpace::expand() {
  60   const size_t max = ZMarkStackSpaceStart + ZMarkStacksMax;
  61   if (_end + ZMarkStackSpaceExpandSize > max) {
  62     // Expansion limit reached
  63     return false;
  64   }
  65 
  66   void* const res = mmap((void*)_end, ZMarkStackSpaceExpandSize,
  67                          PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE|MAP_FIXED, -1, 0);
  68   if (res == MAP_FAILED) {
  69     ZErrno err;
  70     log_error(gc, marking)("Failed to map memory for marking stacks (%s)", err.to_string());
  71     return false;
  72   }
  73 
  74   return true;
  75 }
  76 
  77 uintptr_t ZMarkStackSpace::alloc_space(size_t size) {
  78   uintptr_t top = _top;
  79 
  80   for (;;) {
  81     const uintptr_t new_top = top + size;
  82     if (new_top > _end) {
  83       // Not enough space left
  84       return 0;
  85     }
  86 
  87     const uintptr_t prev_top = Atomic::cmpxchg(new_top, &_top, top);
  88     if (prev_top == top) {
  89       // Success
  90       return top;
  91     }
  92 
  93     // Retry
  94     top = prev_top;
  95   }
  96 }
  97 
  98 uintptr_t ZMarkStackSpace::expand_and_alloc_space(size_t size) {
  99   ZLocker locker(&_expand_lock);
 100 
 101   // Retry allocation before expanding
 102   uintptr_t addr = alloc_space(size);
 103   if (addr != 0) {
 104     return addr;
 105   }
 106 
 107   // Expand stack space
 108   if (!expand()) {
 109     // We currently can't handle the situation where we
 110     // are running out of mark stack space.
 111     fatal("Mark stack overflow (allocated " SIZE_FORMAT "M, size " SIZE_FORMAT "M, max " SIZE_FORMAT "M),"
 112           " use -XX:ZMarkStacksMax=? to increase this limit",
 113           (_end - ZMarkStackSpaceStart) / M, size / M, ZMarkStacksMax / M);
 114     return 0;
 115   }
 116 
 117   log_debug(gc, marking)("Expanding mark stack space: " SIZE_FORMAT "M->" SIZE_FORMAT "M",
 118                          (_end - ZMarkStackSpaceStart) / M,
 119                          (_end - ZMarkStackSpaceStart + ZMarkStackSpaceExpandSize) / M);
 120 
 121   // Increment top before end to make sure another
 122   // thread can't steal out newly expanded space.
 123   addr = Atomic::add(size, &_top) - size;
 124   _end += ZMarkStackSpaceExpandSize;
 125 
 126   return addr;
 127 }
 128 
 129 uintptr_t ZMarkStackSpace::alloc(size_t size) {
 130   const uintptr_t addr = alloc_space(size);
 131   if (addr != 0) {
 132     return addr;
 133   }
 134 
 135   return expand_and_alloc_space(size);
 136 }
 137 
 138 ZMarkStackAllocator::ZMarkStackAllocator() :
 139     _freelist(),
 140     _space() {
 141   guarantee(sizeof(ZMarkStack) == ZMarkStackSize, "Size mismatch");
 142   guarantee(sizeof(ZMarkStackMagazine) <= ZMarkStackSize, "Size mismatch");
 143 
 144   // Prime free list to avoid an immediate space
 145   // expansion when marking starts.
 146   if (_space.is_initialized()) {
 147     prime_freelist();
 148   }
 149 }
 150 
 151 bool ZMarkStackAllocator::is_initialized() const {
 152   return _space.is_initialized();
 153 }
 154 
 155 void ZMarkStackAllocator::prime_freelist() {
 156   for (size_t size = 0; size < ZMarkStackSpaceExpandSize; size += ZMarkStackMagazineSize) {
 157     const uintptr_t addr = _space.alloc(ZMarkStackMagazineSize);
 158     ZMarkStackMagazine* const magazine = create_magazine_from_space(addr, ZMarkStackMagazineSize);
 159     free_magazine(magazine);
 160   }
 161 }
 162 
 163 ZMarkStackMagazine* ZMarkStackAllocator::create_magazine_from_space(uintptr_t addr, size_t size) {
 164   assert(is_aligned(size, ZMarkStackSize), "Invalid size");
 165 
 166   // Use first stack as magazine
 167   ZMarkStackMagazine* const magazine = new ((void*)addr) ZMarkStackMagazine();
 168   for (size_t i = ZMarkStackSize; i < size; i += ZMarkStackSize) {
 169     ZMarkStack* const stack = new ((void*)(addr + i)) ZMarkStack();
 170     const bool success = magazine->push(stack);
 171     assert(success, "Magazine should never get full");
 172   }
 173 
 174   return magazine;
 175 }
 176 
 177 ZMarkStackMagazine* ZMarkStackAllocator::alloc_magazine() {
 178   // Try allocating from the free list first
 179   ZMarkStackMagazine* const magazine = _freelist.pop_atomic();
 180   if (magazine != NULL) {
 181     return magazine;
 182   }
 183 
 184   // Allocate new magazine
 185   const uintptr_t addr = _space.alloc(ZMarkStackMagazineSize);
 186   if (addr == 0) {
 187     return NULL;
 188   }
 189 
 190   return create_magazine_from_space(addr, ZMarkStackMagazineSize);
 191 }
 192 
 193 void ZMarkStackAllocator::free_magazine(ZMarkStackMagazine* magazine) {
 194   _freelist.push_atomic(magazine);
 195 }
 196 
 197 ZMarkStripe::ZMarkStripe() :
 198     _published(),
 199     _overflowed() {}
 200 
 201 ZMarkStripeSet::ZMarkStripeSet() :
 202     _nstripes(0),
 203     _nstripes_mask(0),
 204     _stripes() {}
 205 
 206 void ZMarkStripeSet::set_nstripes(size_t nstripes) {
 207   assert(is_power_of_2(nstripes), "Must be a power of two");
 208   assert(is_power_of_2(ZMarkStripesMax), "Must be a power of two");
 209   assert(nstripes >= 1, "Invalid number of stripes");
 210   assert(nstripes <= ZMarkStripesMax, "Invalid number of stripes");
 211 
 212   _nstripes = nstripes;
 213   _nstripes_mask = nstripes - 1;
 214 
 215   log_debug(gc, marking)("Using " SIZE_FORMAT " mark stripes", _nstripes);
 216 }
 217 
 218 bool ZMarkStripeSet::is_empty() const {
 219   for (size_t i = 0; i < _nstripes; i++) {
 220     if (!_stripes[i].is_empty()) {
 221       return false;
 222     }
 223   }
 224 
 225   return true;
 226 }
 227 
 228 ZMarkStripe* ZMarkStripeSet::stripe_for_worker(uint nworkers, uint worker_id) {
 229   const size_t spillover_limit = (nworkers / _nstripes) * _nstripes;
 230   size_t index;
 231 
 232   if (worker_id < spillover_limit) {
 233     // Not a spillover worker, use natural stripe
 234     index = worker_id & _nstripes_mask;
 235   } else {
 236     // Distribute spillover workers evenly across stripes
 237     const size_t spillover_nworkers = nworkers - spillover_limit;
 238     const size_t spillover_worker_id = worker_id - spillover_limit;
 239     const double spillover_chunk = (double)_nstripes / (double)spillover_nworkers;
 240     index = spillover_worker_id * spillover_chunk;
 241   }
 242 
 243   assert(index < _nstripes, "Invalid index");
 244   return &_stripes[index];
 245 }
 246 
 247 ZMarkThreadLocalStacks::ZMarkThreadLocalStacks() :
 248     _magazine(NULL) {
 249   for (size_t i = 0; i < ZMarkStripesMax; i++) {
 250     _stacks[i] = NULL;
 251   }
 252 }
 253 
 254 bool ZMarkThreadLocalStacks::is_empty(const ZMarkStripeSet* stripes) const {
 255   for (size_t i = 0; i < stripes->nstripes(); i++) {
 256     ZMarkStack* const stack = _stacks[i];
 257     if (stack != NULL) {
 258       return false;
 259     }
 260   }
 261 
 262   return true;
 263 }
 264 
 265 ZMarkStack* ZMarkThreadLocalStacks::allocate_stack(ZMarkStackAllocator* allocator) {
 266   if (_magazine == NULL) {
 267     // Allocate new magazine
 268     _magazine = allocator->alloc_magazine();
 269     if (_magazine == NULL) {
 270       return NULL;
 271     }
 272   }
 273 
 274   ZMarkStack* stack = NULL;
 275 
 276   if (!_magazine->pop(stack)) {
 277     // Magazine is empty, convert magazine into a new stack
 278     _magazine->~ZMarkStackMagazine();
 279     stack = new ((void*)_magazine) ZMarkStack();
 280     _magazine = NULL;
 281   }
 282 
 283   return stack;
 284 }
 285 
 286 void ZMarkThreadLocalStacks::free_stack(ZMarkStackAllocator* allocator, ZMarkStack* stack) {
 287   for (;;) {
 288     if (_magazine == NULL) {
 289       // Convert stack into a new magazine
 290       stack->~ZMarkStack();
 291       _magazine = new ((void*)stack) ZMarkStackMagazine();
 292       return;
 293     }
 294 
 295     if (_magazine->push(stack)) {
 296       // Success
 297       return;
 298     }
 299 
 300     // Free and uninstall full magazine
 301     allocator->free_magazine(_magazine);
 302     _magazine = NULL;
 303   }
 304 }
 305 
 306 bool ZMarkThreadLocalStacks::push_slow(ZMarkStackAllocator* allocator,
 307                                        ZMarkStripe* stripe,
 308                                        ZMarkStack** stackp,
 309                                        ZMarkStackEntry entry,
 310                                        bool publish) {
 311   ZMarkStack* stack = *stackp;
 312 
 313   for (;;) {
 314     if (stack == NULL) {
 315       // Allocate and install new stack
 316       *stackp = stack = allocate_stack(allocator);
 317       if (stack == NULL) {
 318         // Out of mark stack memory
 319         return false;
 320       }
 321     }
 322 
 323     if (stack->push(entry)) {
 324       // Success
 325       return true;
 326     }
 327 
 328     // Publish/Overflow and uninstall stack
 329     stripe->publish_stack(stack, publish);
 330     *stackp = stack = NULL;
 331   }
 332 }
 333 
 334 bool ZMarkThreadLocalStacks::pop_slow(ZMarkStackAllocator* allocator,
 335                                       ZMarkStripe* stripe,
 336                                       ZMarkStack** stackp,
 337                                       ZMarkStackEntry& entry) {
 338   ZMarkStack* stack = *stackp;
 339 
 340   for (;;) {
 341     if (stack == NULL) {
 342       // Try steal and install stack
 343       *stackp = stack = stripe->steal_stack();
 344       if (stack == NULL) {
 345         // Nothing to steal
 346         return false;
 347       }
 348     }
 349 
 350     if (stack->pop(entry)) {
 351       // Success
 352       return true;
 353     }
 354 
 355     // Free and uninstall stack
 356     free_stack(allocator, stack);
 357     *stackp = stack = NULL;
 358   }
 359 }
 360 
 361 bool ZMarkThreadLocalStacks::flush(ZMarkStackAllocator* allocator, ZMarkStripeSet* stripes) {
 362   bool flushed = false;
 363 
 364   // Flush all stacks
 365   for (size_t i = 0; i < stripes->nstripes(); i++) {
 366     ZMarkStripe* const stripe = stripes->stripe_at(i);
 367     ZMarkStack** const stackp = &_stacks[i];
 368     ZMarkStack* const stack = *stackp;
 369     if (stack == NULL) {
 370       continue;
 371     }
 372 
 373     // Free/Publish and uninstall stack
 374     if (stack->is_empty()) {
 375       free_stack(allocator, stack);
 376     } else {
 377       stripe->publish_stack(stack);
 378       flushed = true;
 379     }
 380     *stackp = NULL;
 381   }
 382 
 383   return flushed;
 384 }
 385 
 386 void ZMarkThreadLocalStacks::free(ZMarkStackAllocator* allocator) {
 387   // Free and uninstall magazine
 388   if (_magazine != NULL) {
 389     allocator->free_magazine(_magazine);
 390     _magazine = NULL;
 391   }
 392 }