truffle: src/share/vm/utilities/taskqueue.hpp comparison

comparison src/share/vm/utilities/taskqueue.hpp @ 1311:2a1472c30599

4396719: Mark Sweep stack overflow on deeply nested Object arrays Summary: Use an explicit stack for object arrays and process them in chunks. Reviewed-by: iveresov, apetrusenko

author	jcoomes
date	Wed, 03 Mar 2010 14:48:26 -0800
parents	5f1f51edaff6
children	c18cbe5936b8

comparison

equal deleted inserted replaced

-:d47555d7aca8
+:2a1472c30599
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 *
 */
+template <unsigned int N>
 class TaskQueueSuper: public CHeapObj {
 protected:
 // Internal type for indexing the queue; also used for the tag.
 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t;
 // The first free element after the last one pushed (mod N).
 volatile uint _bottom;
-enum {
+enum { MOD_N_MASK = N - 1 };
-N = 1 << NOT_LP64(14) LP64_ONLY(17), // Queue size: 16K or 128K
-MOD_N_MASK = N - 1                   // To compute x mod N efficiently.
-};
 class Age {
 public:
 Age(size_t data = 0)         { _data = data; }
 Age(const Age& age)          { _data = age._data; }
 return (ind - 1) & MOD_N_MASK;
 }
 // Returns a number in the range [0..N).  If the result is "N-1", it should be
 // interpreted as 0.
-uint dirty_size(uint bot, uint top) {
+uint dirty_size(uint bot, uint top) const {
 return (bot - top) & MOD_N_MASK;
 }
 // Returns the size corresponding to the given "bot" and "top".
-uint size(uint bot, uint top) {
+uint size(uint bot, uint top) const {
 uint sz = dirty_size(bot, top);
 // Has the queue "wrapped", so that bottom is less than top?  There's a
 // complicated special case here.  A pair of threads could perform pop_local
 // and pop_global operations concurrently, starting from a state in which
 // _bottom == _top+1.  The pop_local could succeed in decrementing _bottom,
 }
 public:
 TaskQueueSuper() : _bottom(0), _age() {}
-// Return "true" if the TaskQueue contains any tasks.
+// Return true if the TaskQueue contains any tasks.
-bool peek();
+bool peek() { return _bottom != _age.top(); }
 // Return an estimate of the number of elements in the queue.
 // The "careful" version admits the possibility of pop_local/pop_global
 // races.
-uint size() {
+uint size() const {
 return size(_bottom, _age.top());
 }
-uint dirty_size() {
+uint dirty_size() const {
 return dirty_size(_bottom, _age.top());
 }
 void set_empty() {
 _bottom = 0;
 _age.set(0);
 }
 // Maximum number of elements allowed in the queue.  This is two less
 // than the actual queue size, for somewhat complicated reasons.
-uint max_elems() { return N - 2; }
+uint max_elems() const { return N - 2; }
 // Total size of queue.
 static const uint total_size() { return N; }
 };
-template<class E> class GenericTaskQueue: public TaskQueueSuper {
+template<class E, unsigned int N = TASKQUEUE_SIZE>
+class GenericTaskQueue: public TaskQueueSuper<N> {
+protected:
+typedef typename TaskQueueSuper<N>::Age Age;
+typedef typename TaskQueueSuper<N>::idx_t idx_t;
+using TaskQueueSuper<N>::_bottom;
+using TaskQueueSuper<N>::_age;
+using TaskQueueSuper<N>::increment_index;
+using TaskQueueSuper<N>::decrement_index;
+using TaskQueueSuper<N>::dirty_size;
+public:
+using TaskQueueSuper<N>::max_elems;
+using TaskQueueSuper<N>::size;
 private:
 // Slow paths for push, pop_local.  (pop_global has no fast path.)
 bool push_slow(E t, uint dirty_n_elems);
 bool pop_local_slow(uint localBot, Age oldAge);
 public:
+typedef E element_type;
 // Initializes the queue to empty.
 GenericTaskQueue();
 void initialize();
 private:
 // Element array.
 volatile E* _elems;
 };
-template<class E>
+template<class E, unsigned int N>
-GenericTaskQueue<E>::GenericTaskQueue():TaskQueueSuper() {
+GenericTaskQueue<E, N>::GenericTaskQueue() {
 assert(sizeof(Age) == sizeof(size_t), "Depends on this.");
 }
-template<class E>
+template<class E, unsigned int N>
-void GenericTaskQueue<E>::initialize() {
+void GenericTaskQueue<E, N>::initialize() {
 _elems = NEW_C_HEAP_ARRAY(E, N);
 guarantee(_elems != NULL, "Allocation failed.");
 }
-template<class E>
+template<class E, unsigned int N>
-void GenericTaskQueue<E>::oops_do(OopClosure* f) {
+void GenericTaskQueue<E, N>::oops_do(OopClosure* f) {
 // tty->print_cr("START OopTaskQueue::oops_do");
 uint iters = size();
 uint index = _bottom;
 for (uint i = 0; i < iters; ++i) {
 index = decrement_index(index);
 f->do_oop(p);
 }
 // tty->print_cr("END OopTaskQueue::oops_do");
 }
+template<class E, unsigned int N>
-template<class E>
+bool GenericTaskQueue<E, N>::push_slow(E t, uint dirty_n_elems) {
-bool GenericTaskQueue<E>::push_slow(E t, uint dirty_n_elems) {
 if (dirty_n_elems == N - 1) {
 // Actually means 0, so do the push.
 uint localBot = _bottom;
-_elems[localBot] = t;
+// g++ complains if the volatile result of the assignment is unused.
+const_cast<E&>(_elems[localBot] = t);
 OrderAccess::release_store(&_bottom, increment_index(localBot));
 return true;
 }
 return false;
 }
-template<class E>
+template<class E, unsigned int N>
-bool GenericTaskQueue<E>::
+bool GenericTaskQueue<E, N>::
 pop_local_slow(uint localBot, Age oldAge) {
 // This queue was observed to contain exactly one element; either this
 // thread will claim it, or a competing "pop_global".  In either case,
 // the queue will be logically empty afterwards.  Create a new Age value
 // that represents the empty queue for the given value of "_bottom".  (We
 _age.set(newAge);
 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
 return false;
 }
-template<class E>
+template<class E, unsigned int N>
-bool GenericTaskQueue<E>::pop_global(E& t) {
+bool GenericTaskQueue<E, N>::pop_global(E& t) {
 Age oldAge = _age.get();
 uint localBot = _bottom;
 uint n_elems = size(localBot, oldAge.top());
 if (n_elems == 0) {
 return false;
 }
-t = _elems[oldAge.top()];
+const_cast<E&>(t = _elems[oldAge.top()]);
 Age newAge(oldAge);
 newAge.increment();
 Age resAge = _age.cmpxchg(newAge, oldAge);
 // Note that using "_bottom" here might fail, since a pop_local might
 // have decremented it.
 assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");
 return resAge == oldAge;
 }
-template<class E>
+template<class E, unsigned int N>
-GenericTaskQueue<E>::~GenericTaskQueue() {
+GenericTaskQueue<E, N>::~GenericTaskQueue() {
 FREE_C_HEAP_ARRAY(E, _elems);
 }
 // Inherits the typedef of "Task" from above.
 class TaskQueueSetSuper: public CHeapObj {
 public:
 // Returns "true" if some TaskQueue in the set contains a task.
 virtual bool peek() = 0;
 };
-template<class E> class GenericTaskQueueSet: public TaskQueueSetSuper {
+template<class T>
+class GenericTaskQueueSet: public TaskQueueSetSuper {
 private:
 uint _n;
-GenericTaskQueue<E>** _queues;
+T** _queues;
 public:
+typedef typename T::element_type E;
 GenericTaskQueueSet(int n) : _n(n) {
-typedef GenericTaskQueue<E>* GenericTaskQueuePtr;
+typedef T* GenericTaskQueuePtr;
 _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n);
-guarantee(_queues != NULL, "Allocation failure.");
 for (int i = 0; i < n; i++) {
 _queues[i] = NULL;
 }
 }
 bool steal_1_random(uint queue_num, int* seed, E& t);
 bool steal_best_of_2(uint queue_num, int* seed, E& t);
 bool steal_best_of_all(uint queue_num, int* seed, E& t);
-void register_queue(uint i, GenericTaskQueue<E>* q);
+void register_queue(uint i, T* q);
-GenericTaskQueue<E>* queue(uint n);
+T* queue(uint n);
 // The thread with queue number "queue_num" (and whose random number seed
 // is at "seed") is trying to steal a task from some other queue.  (It
 // may try several queues, according to some configuration parameter.)
 // If some steal succeeds, returns "true" and sets "t" the stolen task,
 bool steal(uint queue_num, int* seed, E& t);
 bool peek();
 };
-template<class E>
+template<class T> void
-void GenericTaskQueueSet<E>::register_queue(uint i, GenericTaskQueue<E>* q) {
+GenericTaskQueueSet<T>::register_queue(uint i, T* q) {
 assert(i < _n, "index out of range.");
 _queues[i] = q;
 }
-template<class E>
+template<class T> T*
-GenericTaskQueue<E>* GenericTaskQueueSet<E>::queue(uint i) {
+GenericTaskQueueSet<T>::queue(uint i) {
 return _queues[i];
 }
-template<class E>
+template<class T> bool
-bool GenericTaskQueueSet<E>::steal(uint queue_num, int* seed, E& t) {
+GenericTaskQueueSet<T>::steal(uint queue_num, int* seed, E& t) {
 for (uint i = 0; i < 2 * _n; i++)
 if (steal_best_of_2(queue_num, seed, t))
 return true;
 return false;
 }
-template<class E>
+template<class T> bool
-bool GenericTaskQueueSet<E>::steal_best_of_all(uint queue_num, int* seed, E& t) {
+GenericTaskQueueSet<T>::steal_best_of_all(uint queue_num, int* seed, E& t) {
 if (_n > 2) {
 int best_k;
 uint best_sz = 0;
 for (uint k = 0; k < _n; k++) {
 if (k == queue_num) continue;
 assert(_n == 1, "can't be zero.");
 return false;
 }
 }
-template<class E>
+template<class T> bool
-bool GenericTaskQueueSet<E>::steal_1_random(uint queue_num, int* seed, E& t) {
+GenericTaskQueueSet<T>::steal_1_random(uint queue_num, int* seed, E& t) {
 if (_n > 2) {
 uint k = queue_num;
 while (k == queue_num) k = randomParkAndMiller(seed) % _n;
 return _queues[2]->pop_global(t);
 } else if (_n == 2) {
 assert(_n == 1, "can't be zero.");
 return false;
 }
 }
-template<class E>
+template<class T> bool
-bool GenericTaskQueueSet<E>::steal_best_of_2(uint queue_num, int* seed, E& t) {
+GenericTaskQueueSet<T>::steal_best_of_2(uint queue_num, int* seed, E& t) {
 if (_n > 2) {
 uint k1 = queue_num;
 while (k1 == queue_num) k1 = randomParkAndMiller(seed) % _n;
 uint k2 = queue_num;
 while (k2 == queue_num || k2 == k1) k2 = randomParkAndMiller(seed) % _n;
 assert(_n == 1, "can't be zero.");
 return false;
 }
 }
-template<class E>
+template<class T>
-bool GenericTaskQueueSet<E>::peek() {
+bool GenericTaskQueueSet<T>::peek() {
 // Try all the queues.
 for (uint j = 0; j < _n; j++) {
 if (_queues[j]->peek())
 return true;
 }
 static uint total_peeks() { return _total_peeks; }
 static void print_termination_counts();
 #endif
 };
-template<class E> inline bool GenericTaskQueue<E>::push(E t) {
+template<class E, unsigned int N> inline bool
+GenericTaskQueue<E, N>::push(E t) {
 uint localBot = _bottom;
 assert((localBot >= 0) && (localBot < N), "_bottom out of range.");
 idx_t top = _age.top();
 uint dirty_n_elems = dirty_size(localBot, top);
-assert((dirty_n_elems >= 0) && (dirty_n_elems < N), "n_elems out of range.");
+assert(dirty_n_elems < N, "n_elems out of range.");
 if (dirty_n_elems < max_elems()) {
-_elems[localBot] = t;
+// g++ complains if the volatile result of the assignment is unused.
+const_cast<E&>(_elems[localBot] = t);
 OrderAccess::release_store(&_bottom, increment_index(localBot));
 return true;
 } else {
 return push_slow(t, dirty_n_elems);
 }
 }
-template<class E> inline bool GenericTaskQueue<E>::pop_local(E& t) {
+template<class E, unsigned int N> inline bool
+GenericTaskQueue<E, N>::pop_local(E& t) {
 uint localBot = _bottom;
 // This value cannot be N-1.  That can only occur as a result of
 // the assignment to bottom in this method.  If it does, this method
 // resets the size( to 0 before the next call (which is sequential,
 // since this is pop_local.)
 localBot = decrement_index(localBot);
 _bottom = localBot;
 // This is necessary to prevent any read below from being reordered
 // before the store just above.
 OrderAccess::fence();
-t = _elems[localBot];
+const_cast<E&>(t = _elems[localBot]);
 // This is a second read of "age"; the "size()" above is the first.
 // If there's still at least one element in the queue, based on the
 // "_bottom" and "age" we've read, then there can be no interference with
 // a "pop_global" operation, and we're done.
 idx_t tp = _age.top();    // XXX
 return pop_local_slow(localBot, _age.get());
 }
 }
 typedef oop Task;
-typedef GenericTaskQueue<Task>         OopTaskQueue;
+typedef GenericTaskQueue<Task>            OopTaskQueue;
-typedef GenericTaskQueueSet<Task>      OopTaskQueueSet;
+typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet;
+#ifdef _MSC_VER
-#define COMPRESSED_OOP_MASK  1
+#pragma warning(push)
+// warning C4522: multiple assignment operators specified
+#pragma warning(disable:4522)
+#endif
 // This is a container class for either an oop* or a narrowOop*.
 // Both are pushed onto a task queue and the consumer will test is_narrow()
 // to determine which should be processed.
 class StarTask {
 void*  _holder;        // either union oop* or narrowOop*
+enum { COMPRESSED_OOP_MASK = 1 };
 public:
 StarTask(narrowOop* p) {
 assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!");
 _holder = (void *)((uintptr_t)p | COMPRESSED_OOP_MASK);
 }
 operator oop*()        { return (oop*)_holder; }
 operator narrowOop*()  {
 return (narrowOop*)((uintptr_t)_holder & ~COMPRESSED_OOP_MASK);
 }
-// Operators to preserve const/volatile in assignments required by gcc
+StarTask& operator=(const StarTask& t) {
-void operator=(const volatile StarTask& t) volatile { _holder = t._holder; }
+_holder = t._holder;
+return *this;
+}
+volatile StarTask& operator=(const volatile StarTask& t) volatile {
+_holder = t._holder;
+return *this;
+}
 bool is_narrow() const {
 return (((uintptr_t)_holder & COMPRESSED_OOP_MASK) != 0);
 }
 };
-typedef GenericTaskQueue<StarTask>     OopStarTaskQueue;
+class ObjArrayTask
-typedef GenericTaskQueueSet<StarTask>  OopStarTaskQueueSet;
+{
+public:
+ObjArrayTask(oop o = NULL, int idx = 0): _obj(o), _index(idx) { }
+ObjArrayTask(oop o, size_t idx): _obj(o), _index(int(idx)) {
+assert(idx <= size_t(max_jint), "too big");
+}
+ObjArrayTask(const ObjArrayTask& t): _obj(t._obj), _index(t._index) { }
+ObjArrayTask& operator =(const ObjArrayTask& t) {
+_obj = t._obj;
+_index = t._index;
+return *this;
+}
+volatile ObjArrayTask&
+operator =(const volatile ObjArrayTask& t) volatile {
+_obj = t._obj;
+_index = t._index;
+return *this;
+}
+inline oop obj()   const { return _obj; }
+inline int index() const { return _index; }
+DEBUG_ONLY(bool is_valid() const); // Tasks to be pushed/popped must be valid.
+private:
+oop _obj;
+int _index;
+};
+#ifdef _MSC_VER
+#pragma warning(pop)
+#endif
+typedef GenericTaskQueue<StarTask>            OopStarTaskQueue;
+typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet;
 typedef size_t RegionTask;  // index for region
-typedef GenericTaskQueue<RegionTask>    RegionTaskQueue;
+typedef GenericTaskQueue<RegionTask>         RegionTaskQueue;
-typedef GenericTaskQueueSet<RegionTask> RegionTaskQueueSet;
+typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet;
 class RegionTaskQueueWithOverflow: public CHeapObj {
 protected:
 RegionTaskQueue              _region_queue;
 GrowableArray<RegionTask>*   _overflow_stack;

Mercurial > hg > truffle

comparison src/share/vm/utilities/taskqueue.hpp @ 1311:2a1472c30599