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/zMarkStackEntry.hpp"
 29 #include "utilities/globalDefinitions.hpp"
 30 
 31 template <typename T, size_t S>
 32 class ZStack {
 33 private:
 34   size_t        _top;
 35   ZStack<T, S>* _next;
 36   T             _slots[S];
 37 
 38   bool is_full() const;
 39 
 40 public:
 41   ZStack();
 42 
 43   bool is_empty() const;
 44 
 45   bool push(T value);
 46   bool pop(T& value);
 47 
 48   ZStack<T, S>* next() const;
 49   ZStack<T, S>** next_addr();
 50 };
 51 
 52 template <typename T>
 53 class ZStackList {
 54 private:
 55   T* volatile _head;
 56 
 57   T* encode_versioned_pointer(const T* stack, uint32_t version) const;
 58   void decode_versioned_pointer(const T* vstack, T** stack, uint32_t* version) const;
 59 
 60 public:
 61   ZStackList();
 62 
 63   bool is_empty() const;
 64 
 65   void push_atomic(T* stack);
 66   T* pop_atomic();
 67 };
 68 
 69 typedef ZStack<ZMarkStackEntry, ZMarkStackSlots>     ZMarkStack;
 70 typedef ZStackList<ZMarkStack>                       ZMarkStackList;
 71 typedef ZStack<ZMarkStack*, ZMarkStackMagazineSlots> ZMarkStackMagazine;
 72 typedef ZStackList<ZMarkStackMagazine>               ZMarkStackMagazineList;
 73 
 74 class ZMarkStripe {
 75 private:
 76   ZCACHE_ALIGNED ZMarkStackList _published;
 77   ZCACHE_ALIGNED ZMarkStackList _overflowed;
 78 
 79 public:
 80   ZMarkStripe();
 81 
 82   bool is_empty() const;
 83 
 84   void publish_stack(ZMarkStack* stack, bool publish = true);
 85   ZMarkStack* steal_stack();
 86 };
 87 
 88 class ZMarkStripeSet {
 89 private:
 90   size_t      _nstripes;
 91   size_t      _nstripes_mask;
 92   ZMarkStripe _stripes[ZMarkStripesMax];
 93 
 94 public:
 95   ZMarkStripeSet();
 96 
 97   size_t nstripes() const;
 98   void set_nstripes(size_t nstripes);
 99 
100   bool is_empty() const;
101 
102   size_t stripe_id(const ZMarkStripe* stripe) const;
103   ZMarkStripe* stripe_at(size_t index);
104   ZMarkStripe* stripe_next(ZMarkStripe* stripe);
105   ZMarkStripe* stripe_for_worker(uint nworkers, uint worker_id);
106   ZMarkStripe* stripe_for_addr(uintptr_t addr);
107 };
108 
109 class ZMarkStackAllocator;
110 
111 class ZMarkThreadLocalStacks {
112 private:
113   ZMarkStackMagazine* _magazine;
114   ZMarkStack*         _stacks[ZMarkStripesMax];
115 
116   ZMarkStack* allocate_stack(ZMarkStackAllocator* allocator);
117   void free_stack(ZMarkStackAllocator* allocator, ZMarkStack* stack);
118 
119   bool push_slow(ZMarkStackAllocator* allocator,
120                  ZMarkStripe* stripe,
121                  ZMarkStack** stackp,
122                  ZMarkStackEntry entry,
123                  bool publish);
124 
125   bool pop_slow(ZMarkStackAllocator* allocator,
126                 ZMarkStripe* stripe,
127                 ZMarkStack** stackp,
128                 ZMarkStackEntry& entry);
129 
130 public:
131   ZMarkThreadLocalStacks();
132 
133   bool is_empty(const ZMarkStripeSet* stripes) const;
134 
135   void install(ZMarkStripeSet* stripes,
136                ZMarkStripe* stripe,
137                ZMarkStack* stack);
138 
139   bool push(ZMarkStackAllocator* allocator,
140             ZMarkStripeSet* stripes,
141             ZMarkStripe* stripe,
142             ZMarkStackEntry entry,
143             bool publish);
144 
145   bool pop(ZMarkStackAllocator* allocator,
146            ZMarkStripeSet* stripes,
147            ZMarkStripe* stripe,
148            ZMarkStackEntry& entry);
149 
150   bool flush(ZMarkStackAllocator* allocator,
151              ZMarkStripeSet* stripes);
152 
153   void free(ZMarkStackAllocator* allocator);
154 };
155 
156 #endif // SHARE_GC_Z_ZMARKSTACK_HPP