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