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(T* stack);
66   T* pop();
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
157