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 #ifndef SHARE_GC_Z_ZMARKSTACK_HPP

    25 #define SHARE_GC_Z_ZMARKSTACK_HPP

    26 

    27 #include "gc/z/zGlobals.hpp"

    28 #include "gc/z/zLock.hpp"

    29 #include "gc/z/zMarkStackEntry.hpp"

    30 #include "memory/allocation.hpp"

    31 #include "utilities/globalDefinitions.hpp"

    32 

    33 template <typename T, size_t S>

    34 class ZStack {

    35 private:

    36   size_t        _top;

    37   ZStack<T, S>* _next;

    38   T             _slots[S];

    39 

    40   bool is_full() const;

    41 

    42 public:

    43   ZStack();

    44 

    45   bool is_empty() const;

    46 

    47   bool push(T value);

    48   bool pop(T& value);

    49 

    50   ZStack<T, S>* next() const;

    51   ZStack<T, S>** next_addr();

    52 };

    53 

    54 template <typename T>

    55 class ZStackList {

    56 private:

    57   T* volatile _head;

    58 

    59   T* encode_versioned_pointer(const T* stack, uint32_t version) const;

    60   void decode_versioned_pointer(const T* vstack, T** stack, uint32_t* version) const;

    61 

    62 public:

    63   ZStackList();

    64 

    65   bool is_empty() const;

    66 

    67   void push_atomic(T* stack);

    68   T* pop_atomic();

    69 };

    70 

    71 typedef ZStack<ZMarkStackEntry, ZMarkStackSlots>     ZMarkStack;

    72 typedef ZStackList<ZMarkStack>                       ZMarkStackList;

    73 typedef ZStack<ZMarkStack*, ZMarkStackMagazineSlots> ZMarkStackMagazine;

    74 typedef ZStackList<ZMarkStackMagazine>               ZMarkStackMagazineList;

    75 

    76 class ZMarkStackSpace {

    77 private:

    78   ZLock              _expand_lock;

    79   volatile uintptr_t _top;

    80   volatile uintptr_t _end;

    81 

    82   bool expand();

    83 

    84   uintptr_t alloc_space(size_t size);

    85   uintptr_t expand_and_alloc_space(size_t size);

    86 

    87 public:

    88   ZMarkStackSpace();

    89 

    90   bool is_initialized() const;

    91 

    92   uintptr_t alloc(size_t size);

    93 };

    94 

    95 class ZMarkStackAllocator {

    96 private:

    97   ZMarkStackMagazineList _freelist ATTRIBUTE_ALIGNED(ZCacheLineSize);

    98   ZMarkStackSpace        _space    ATTRIBUTE_ALIGNED(ZCacheLineSize);

    99 

   100   void prime_freelist();

   101   ZMarkStackMagazine* create_magazine_from_space(uintptr_t addr, size_t size);

   102 

   103 public:

   104   ZMarkStackAllocator();

   105 

   106   bool is_initialized() const;

   107 

   108   ZMarkStackMagazine* alloc_magazine();

   109   void free_magazine(ZMarkStackMagazine* magazine);

   110 };

   111 

   112 class ZMarkStripe {

   113 private:

   114   ZMarkStackList _published  ATTRIBUTE_ALIGNED(ZCacheLineSize);

   115   ZMarkStackList _overflowed ATTRIBUTE_ALIGNED(ZCacheLineSize);

   116 

   117 public:

   118   ZMarkStripe();

   119 

   120   bool is_empty() const;

   121 

   122   void publish_stack(ZMarkStack* stack, bool publish = true);

   123   ZMarkStack* steal_stack();

   124 };

   125 

   126 class ZMarkStripeSet {

   127 private:

   128   size_t      _nstripes;

   129   size_t      _nstripes_mask;

   130   ZMarkStripe _stripes[ZMarkStripesMax];

   131 

   132 public:

   133   ZMarkStripeSet();

   134 

   135   size_t nstripes() const;

   136   void set_nstripes(size_t nstripes);

   137 

   138   bool is_empty() const;

   139 

   140   size_t stripe_id(const ZMarkStripe* stripe) const;

   141   ZMarkStripe* stripe_at(size_t index);

   142   ZMarkStripe* stripe_next(ZMarkStripe* stripe);

   143   ZMarkStripe* stripe_for_worker(uint nworkers, uint worker_id);

   144   ZMarkStripe* stripe_for_addr(uintptr_t addr);

   145 };

   146 

   147 class ZMarkThreadLocalStacks {

   148 private:

   149   ZMarkStackMagazine* _magazine;

   150   ZMarkStack*         _stacks[ZMarkStripesMax];

   151 

   152   ZMarkStack* allocate_stack(ZMarkStackAllocator* allocator);

   153   void free_stack(ZMarkStackAllocator* allocator, ZMarkStack* stack);

   154 

   155   bool push_slow(ZMarkStackAllocator* allocator,

   156                  ZMarkStripe* stripe,

   157                  ZMarkStack** stackp,

   158                  ZMarkStackEntry entry,

   159                  bool publish);

   160 

   161   bool pop_slow(ZMarkStackAllocator* allocator,

   162                 ZMarkStripe* stripe,

   163                 ZMarkStack** stackp,

   164                 ZMarkStackEntry& entry);

   165 

   166 public:

   167   ZMarkThreadLocalStacks();

   168 

   169   bool is_empty(const ZMarkStripeSet* stripes) const;

   170 

   171   void install(ZMarkStripeSet* stripes,

   172                ZMarkStripe* stripe,

   173                ZMarkStack* stack);

   174 

   175   bool push(ZMarkStackAllocator* allocator,

   176             ZMarkStripeSet* stripes,

   177             ZMarkStripe* stripe,

   178             ZMarkStackEntry entry,

   179             bool publish);

   180 

   181   bool pop(ZMarkStackAllocator* allocator,

   182            ZMarkStripeSet* stripes,

   183            ZMarkStripe* stripe,

   184            ZMarkStackEntry& entry);

   185 

   186   bool flush(ZMarkStackAllocator* allocator,

   187              ZMarkStripeSet* stripes);

   188 

   189   void free(ZMarkStackAllocator* allocator);

   190 };

   191 

   192 #endif // SHARE_GC_Z_ZMARKSTACK_HPP