141 class TaskQueueSuper: public CHeapObj<F> { |
141 class TaskQueueSuper: public CHeapObj<F> { |
142 protected: |
142 protected: |
143 // Internal type for indexing the queue; also used for the tag. |
143 // Internal type for indexing the queue; also used for the tag. |
144 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t; |
144 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t; |
145 |
145 |
|
146 #ifdef MIPS64 |
|
147 private: |
|
148 #endif |
146 // The first free element after the last one pushed (mod N). |
149 // The first free element after the last one pushed (mod N). |
147 volatile uint _bottom; |
150 volatile uint _bottom; |
|
151 |
|
152 #ifdef MIPS64 |
|
153 protected: |
|
154 inline uint get_bottom() const { |
|
155 return OrderAccess::load_acquire((volatile juint*)&_bottom); |
|
156 } |
|
157 |
|
158 inline void set_bottom(uint new_bottom) { |
|
159 OrderAccess::release_store(&_bottom, new_bottom); |
|
160 } |
|
161 #endif |
148 |
162 |
149 enum { MOD_N_MASK = N - 1 }; |
163 enum { MOD_N_MASK = N - 1 }; |
150 |
164 |
151 class Age { |
165 class Age { |
152 public: |
166 public: |
153 Age(size_t data = 0) { _data = data; } |
167 Age(size_t data = 0) { _data = data; } |
154 Age(const Age& age) { _data = age._data; } |
168 Age(const Age& age) { _data = age._data; } |
155 Age(idx_t top, idx_t tag) { _fields._top = top; _fields._tag = tag; } |
169 Age(idx_t top, idx_t tag) { _fields._top = top; _fields._tag = tag; } |
156 |
170 |
|
171 #ifndef MIPS64 |
157 Age get() const volatile { return _data; } |
172 Age get() const volatile { return _data; } |
158 void set(Age age) volatile { _data = age._data; } |
173 void set(Age age) volatile { _data = age._data; } |
159 |
|
160 idx_t top() const volatile { return _fields._top; } |
174 idx_t top() const volatile { return _fields._top; } |
161 idx_t tag() const volatile { return _fields._tag; } |
175 idx_t tag() const volatile { return _fields._tag; } |
|
176 #else |
|
177 Age get() const volatile { |
|
178 size_t res = OrderAccess::load_ptr_acquire((volatile intptr_t*) &_data); |
|
179 return *(Age*)(&res); |
|
180 } |
|
181 |
|
182 void set(Age age) volatile { OrderAccess::release_store_ptr((volatile intptr_t*) &_data, *(size_t*)(&age._data)); } |
|
183 idx_t top() const volatile { return OrderAccess::load_acquire((volatile idx_t*) &(_fields._top)); } |
|
184 idx_t tag() const volatile { return OrderAccess::load_acquire((volatile idx_t*) &(_fields._tag)); } |
|
185 #endif |
162 |
186 |
163 // Increment top; if it wraps, increment tag also. |
187 // Increment top; if it wraps, increment tag also. |
164 void increment() { |
188 void increment() { |
165 _fields._top = increment_index(_fields._top); |
189 _fields._top = increment_index(_fields._top); |
166 if (_fields._top == 0) ++_fields._tag; |
190 if (_fields._top == 0) ++_fields._tag; |
223 |
247 |
224 public: |
248 public: |
225 TaskQueueSuper() : _bottom(0), _age() {} |
249 TaskQueueSuper() : _bottom(0), _age() {} |
226 |
250 |
227 // Return true if the TaskQueue contains/does not contain any tasks. |
251 // Return true if the TaskQueue contains/does not contain any tasks. |
228 bool peek() const { return _bottom != _age.top(); } |
252 bool peek() const { |
|
253 #ifdef MIPS64 |
|
254 return get_bottom() != _age.top(); |
|
255 #else |
|
256 return _bottom != _age.top(); |
|
257 #endif |
|
258 } |
|
259 |
229 bool is_empty() const { return size() == 0; } |
260 bool is_empty() const { return size() == 0; } |
230 |
261 |
231 // Return an estimate of the number of elements in the queue. |
262 // Return an estimate of the number of elements in the queue. |
232 // The "careful" version admits the possibility of pop_local/pop_global |
263 // The "careful" version admits the possibility of pop_local/pop_global |
233 // races. |
264 // races. |
234 uint size() const { |
265 uint size() const { |
|
266 #ifdef MIPS64 |
|
267 return size(get_bottom(), _age.top()); |
|
268 #else |
235 return size(_bottom, _age.top()); |
269 return size(_bottom, _age.top()); |
|
270 #endif |
236 } |
271 } |
237 |
272 |
238 uint dirty_size() const { |
273 uint dirty_size() const { |
|
274 #ifdef MIPS64 |
|
275 return dirty_size(get_bottom(), _age.top()); |
|
276 #else |
239 return dirty_size(_bottom, _age.top()); |
277 return dirty_size(_bottom, _age.top()); |
|
278 #endif |
240 } |
279 } |
241 |
280 |
242 void set_empty() { |
281 void set_empty() { |
|
282 #ifdef MIPS64 |
|
283 set_bottom(0); |
|
284 #else |
243 _bottom = 0; |
285 _bottom = 0; |
|
286 #endif |
244 _age.set(0); |
287 _age.set(0); |
245 } |
288 } |
246 |
289 |
247 // Maximum number of elements allowed in the queue. This is two less |
290 // Maximum number of elements allowed in the queue. This is two less |
248 // than the actual queue size, for somewhat complicated reasons. |
291 // than the actual queue size, for somewhat complicated reasons. |
290 ArrayAllocator<E, F> _array_allocator; |
333 ArrayAllocator<E, F> _array_allocator; |
291 protected: |
334 protected: |
292 typedef typename TaskQueueSuper<N, F>::Age Age; |
335 typedef typename TaskQueueSuper<N, F>::Age Age; |
293 typedef typename TaskQueueSuper<N, F>::idx_t idx_t; |
336 typedef typename TaskQueueSuper<N, F>::idx_t idx_t; |
294 |
337 |
|
338 #ifndef MIPS64 |
295 using TaskQueueSuper<N, F>::_bottom; |
339 using TaskQueueSuper<N, F>::_bottom; |
|
340 #endif |
296 using TaskQueueSuper<N, F>::_age; |
341 using TaskQueueSuper<N, F>::_age; |
297 using TaskQueueSuper<N, F>::increment_index; |
342 using TaskQueueSuper<N, F>::increment_index; |
298 using TaskQueueSuper<N, F>::decrement_index; |
343 using TaskQueueSuper<N, F>::decrement_index; |
299 using TaskQueueSuper<N, F>::dirty_size; |
344 using TaskQueueSuper<N, F>::dirty_size; |
300 |
345 |
354 |
399 |
355 template<class E, MEMFLAGS F, unsigned int N> |
400 template<class E, MEMFLAGS F, unsigned int N> |
356 void GenericTaskQueue<E, F, N>::oops_do(OopClosure* f) { |
401 void GenericTaskQueue<E, F, N>::oops_do(OopClosure* f) { |
357 // tty->print_cr("START OopTaskQueue::oops_do"); |
402 // tty->print_cr("START OopTaskQueue::oops_do"); |
358 uint iters = size(); |
403 uint iters = size(); |
|
404 #ifdef MIPS64 |
|
405 uint index = this->get_bottom(); |
|
406 #else |
359 uint index = _bottom; |
407 uint index = _bottom; |
|
408 #endif |
360 for (uint i = 0; i < iters; ++i) { |
409 for (uint i = 0; i < iters; ++i) { |
361 index = decrement_index(index); |
410 index = decrement_index(index); |
362 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, |
411 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, |
363 // index, &_elems[index], _elems[index]); |
412 // index, &_elems[index], _elems[index]); |
364 E* t = (E*)&_elems[index]; // cast away volatility |
413 E* t = (E*)&_elems[index]; // cast away volatility |
371 |
420 |
372 template<class E, MEMFLAGS F, unsigned int N> |
421 template<class E, MEMFLAGS F, unsigned int N> |
373 bool GenericTaskQueue<E, F, N>::push_slow(E t, uint dirty_n_elems) { |
422 bool GenericTaskQueue<E, F, N>::push_slow(E t, uint dirty_n_elems) { |
374 if (dirty_n_elems == N - 1) { |
423 if (dirty_n_elems == N - 1) { |
375 // Actually means 0, so do the push. |
424 // Actually means 0, so do the push. |
|
425 #ifdef MIPS64 |
|
426 uint localBot = this->get_bottom(); |
|
427 #else |
376 uint localBot = _bottom; |
428 uint localBot = _bottom; |
|
429 #endif |
377 // g++ complains if the volatile result of the assignment is |
430 // g++ complains if the volatile result of the assignment is |
378 // unused, so we cast the volatile away. We cannot cast directly |
431 // unused, so we cast the volatile away. We cannot cast directly |
379 // to void, because gcc treats that as not using the result of the |
432 // to void, because gcc treats that as not using the result of the |
380 // assignment. However, casting to E& means that we trigger an |
433 // assignment. However, casting to E& means that we trigger an |
381 // unused-value warning. So, we cast the E& to void. |
434 // unused-value warning. So, we cast the E& to void. |
382 (void)const_cast<E&>(_elems[localBot] = t); |
435 (void)const_cast<E&>(_elems[localBot] = t); |
|
436 #ifdef MIPS64 |
|
437 this->set_bottom(increment_index(localBot)); |
|
438 #else |
383 OrderAccess::release_store(&_bottom, increment_index(localBot)); |
439 OrderAccess::release_store(&_bottom, increment_index(localBot)); |
|
440 #endif |
384 TASKQUEUE_STATS_ONLY(stats.record_push()); |
441 TASKQUEUE_STATS_ONLY(stats.record_push()); |
385 return true; |
442 return true; |
386 } |
443 } |
387 return false; |
444 return false; |
388 } |
445 } |
433 // to guarantee that bottom is not older than age, |
490 // to guarantee that bottom is not older than age, |
434 // which is crucial for the correctness of the algorithm. |
491 // which is crucial for the correctness of the algorithm. |
435 #if !(defined SPARC || defined IA32 || defined AMD64) |
492 #if !(defined SPARC || defined IA32 || defined AMD64) |
436 OrderAccess::fence(); |
493 OrderAccess::fence(); |
437 #endif |
494 #endif |
|
495 #ifdef MIPS64 |
|
496 uint localBot = this->get_bottom(); |
|
497 #else |
438 uint localBot = OrderAccess::load_acquire((volatile juint*)&_bottom); |
498 uint localBot = OrderAccess::load_acquire((volatile juint*)&_bottom); |
|
499 #endif |
439 uint n_elems = size(localBot, oldAge.top()); |
500 uint n_elems = size(localBot, oldAge.top()); |
440 if (n_elems == 0) { |
501 if (n_elems == 0) { |
441 return false; |
502 return false; |
442 } |
503 } |
443 |
504 |
681 #endif |
742 #endif |
682 }; |
743 }; |
683 |
744 |
684 template<class E, MEMFLAGS F, unsigned int N> inline bool |
745 template<class E, MEMFLAGS F, unsigned int N> inline bool |
685 GenericTaskQueue<E, F, N>::push(E t) { |
746 GenericTaskQueue<E, F, N>::push(E t) { |
|
747 #ifdef MIPS64 |
|
748 uint localBot = this->get_bottom(); |
|
749 #else |
686 uint localBot = _bottom; |
750 uint localBot = _bottom; |
|
751 #endif |
687 assert(localBot < N, "_bottom out of range."); |
752 assert(localBot < N, "_bottom out of range."); |
688 idx_t top = _age.top(); |
753 idx_t top = _age.top(); |
689 uint dirty_n_elems = dirty_size(localBot, top); |
754 uint dirty_n_elems = dirty_size(localBot, top); |
690 assert(dirty_n_elems < N, "n_elems out of range."); |
755 assert(dirty_n_elems < N, "n_elems out of range."); |
691 if (dirty_n_elems < max_elems()) { |
756 if (dirty_n_elems < max_elems()) { |
693 // unused, so we cast the volatile away. We cannot cast directly |
758 // unused, so we cast the volatile away. We cannot cast directly |
694 // to void, because gcc treats that as not using the result of the |
759 // to void, because gcc treats that as not using the result of the |
695 // assignment. However, casting to E& means that we trigger an |
760 // assignment. However, casting to E& means that we trigger an |
696 // unused-value warning. So, we cast the E& to void. |
761 // unused-value warning. So, we cast the E& to void. |
697 (void) const_cast<E&>(_elems[localBot] = t); |
762 (void) const_cast<E&>(_elems[localBot] = t); |
|
763 #ifdef MIPS64 |
|
764 this->set_bottom(increment_index(localBot)); |
|
765 #else |
698 OrderAccess::release_store(&_bottom, increment_index(localBot)); |
766 OrderAccess::release_store(&_bottom, increment_index(localBot)); |
|
767 #endif |
699 TASKQUEUE_STATS_ONLY(stats.record_push()); |
768 TASKQUEUE_STATS_ONLY(stats.record_push()); |
700 return true; |
769 return true; |
701 } else { |
770 } else { |
702 return push_slow(t, dirty_n_elems); |
771 return push_slow(t, dirty_n_elems); |
703 } |
772 } |
704 } |
773 } |
705 |
774 |
706 template<class E, MEMFLAGS F, unsigned int N> inline bool |
775 template<class E, MEMFLAGS F, unsigned int N> inline bool |
707 GenericTaskQueue<E, F, N>::pop_local(volatile E& t) { |
776 GenericTaskQueue<E, F, N>::pop_local(volatile E& t) { |
|
777 #ifdef MIPS64 |
|
778 uint localBot = this->get_bottom(); |
|
779 #else |
708 uint localBot = _bottom; |
780 uint localBot = _bottom; |
|
781 #endif |
709 // This value cannot be N-1. That can only occur as a result of |
782 // This value cannot be N-1. That can only occur as a result of |
710 // the assignment to bottom in this method. If it does, this method |
783 // the assignment to bottom in this method. If it does, this method |
711 // resets the size to 0 before the next call (which is sequential, |
784 // resets the size to 0 before the next call (which is sequential, |
712 // since this is pop_local.) |
785 // since this is pop_local.) |
713 uint dirty_n_elems = dirty_size(localBot, _age.top()); |
786 uint dirty_n_elems = dirty_size(localBot, _age.top()); |
714 assert(dirty_n_elems != N - 1, "Shouldn't be possible..."); |
787 assert(dirty_n_elems != N - 1, "Shouldn't be possible..."); |
715 if (dirty_n_elems == 0) return false; |
788 if (dirty_n_elems == 0) return false; |
716 localBot = decrement_index(localBot); |
789 localBot = decrement_index(localBot); |
|
790 #ifdef MIPS64 |
|
791 this->set_bottom(localBot); |
|
792 #else |
717 _bottom = localBot; |
793 _bottom = localBot; |
|
794 #endif |
718 // This is necessary to prevent any read below from being reordered |
795 // This is necessary to prevent any read below from being reordered |
719 // before the store just above. |
796 // before the store just above. |
720 OrderAccess::fence(); |
797 OrderAccess::fence(); |
721 // g++ complains if the volatile result of the assignment is |
798 // g++ complains if the volatile result of the assignment is |
722 // unused, so we cast the volatile away. We cannot cast directly |
799 // unused, so we cast the volatile away. We cannot cast directly |