130 void TaskQueueStats::reset() {

   130 void TaskQueueStats::reset() {

   131   memset(_stats, 0, sizeof(_stats));

   131   memset(_stats, 0, sizeof(_stats));

   132 }

   132 }

   133 #endif // TASKQUEUE_STATS

   133 #endif // TASKQUEUE_STATS

   134 

   134 

   137 protected:

   137 protected:

   138   // Internal type for indexing the queue; also used for the tag.

   138   // Internal type for indexing the queue; also used for the tag.

   139   typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t;

   139   typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t;

   140 

   140 

   141   // The first free element after the last one pushed (mod N).

   141   // The first free element after the last one pushed (mod N).

   247   static const uint total_size() { return N; }

   247   static const uint total_size() { return N; }

   248 

   248 

   249   TASKQUEUE_STATS_ONLY(TaskQueueStats stats;)

   249   TASKQUEUE_STATS_ONLY(TaskQueueStats stats;)

   250 };

   250 };

   251 

   251 

   254 protected:

   256 protected:

   268 

   273 

   269 private:

   274 private:

   270   // Slow paths for push, pop_local.  (pop_global has no fast path.)

   275   // Slow paths for push, pop_local.  (pop_global has no fast path.)

   271   bool push_slow(E t, uint dirty_n_elems);

   276   bool push_slow(E t, uint dirty_n_elems);

   272   bool pop_local_slow(uint localBot, Age oldAge);

   277   bool pop_local_slow(uint localBot, Age oldAge);

   300 private:

   305 private:

   301   // Element array.

   306   // Element array.

   302   volatile E* _elems;

   307   volatile E* _elems;

   303 };

   308 };

   304 

   309 

   307   assert(sizeof(Age) == sizeof(size_t), "Depends on this.");

   312   assert(sizeof(Age) == sizeof(size_t), "Depends on this.");

   308 }

   313 }

   309 

   314 

   317   // tty->print_cr("START OopTaskQueue::oops_do");

   322   // tty->print_cr("START OopTaskQueue::oops_do");

   318   uint iters = size();

   323   uint iters = size();

   319   uint index = _bottom;

   324   uint index = _bottom;

   320   for (uint i = 0; i < iters; ++i) {

   325   for (uint i = 0; i < iters; ++i) {

   321     index = decrement_index(index);

   326     index = decrement_index(index);

   327     f->do_oop(p);

   332     f->do_oop(p);

   328   }

   333   }

   329   // tty->print_cr("END OopTaskQueue::oops_do");

   334   // tty->print_cr("END OopTaskQueue::oops_do");

   330 }

   335 }

   331 

   336 

   334   if (dirty_n_elems == N - 1) {

   339   if (dirty_n_elems == N - 1) {

   335     // Actually means 0, so do the push.

   340     // Actually means 0, so do the push.

   336     uint localBot = _bottom;

   341     uint localBot = _bottom;

   337     // g++ complains if the volatile result of the assignment is unused.

   342     // g++ complains if the volatile result of the assignment is unused.

   338     const_cast<E&>(_elems[localBot] = t);

   343     const_cast<E&>(_elems[localBot] = t);

   347 // get the last task in the queue.  It will compete with pop_global()

   352 // get the last task in the queue.  It will compete with pop_global()

   348 // that will be used by other threads.  The tag age is incremented

   353 // that will be used by other threads.  The tag age is incremented

   349 // whenever the queue goes empty which it will do here if this thread

   354 // whenever the queue goes empty which it will do here if this thread

   350 // gets the last task or in pop_global() if the queue wraps (top == 0

   355 // gets the last task or in pop_global() if the queue wraps (top == 0

   351 // and pop_global() succeeds, see pop_global()).

   356 // and pop_global() succeeds, see pop_global()).

   354   // This queue was observed to contain exactly one element; either this

   359   // This queue was observed to contain exactly one element; either this

   355   // thread will claim it, or a competing "pop_global".  In either case,

   360   // thread will claim it, or a competing "pop_global".  In either case,

   356   // the queue will be logically empty afterwards.  Create a new Age value

   361   // the queue will be logically empty afterwards.  Create a new Age value

   357   // that represents the empty queue for the given value of "_bottom".  (We

   362   // that represents the empty queue for the given value of "_bottom".  (We

   358   // must also increment "tag" because of the case where "bottom == 1",

   363   // must also increment "tag" because of the case where "bottom == 1",

   380   _age.set(newAge);

   385   _age.set(newAge);

   381   assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");

   386   assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");

   382   return false;

   387   return false;

   383 }

   388 }

   384 

   389 

   387   Age oldAge = _age.get();

   392   Age oldAge = _age.get();

   388   uint localBot = _bottom;

   393   uint localBot = _bottom;

   389   uint n_elems = size(localBot, oldAge.top());

   394   uint n_elems = size(localBot, oldAge.top());

   390   if (n_elems == 0) {

   395   if (n_elems == 0) {

   391     return false;

   396     return false;

   400   // have decremented it.

   405   // have decremented it.

   401   assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");

   406   assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");

   402   return resAge == oldAge;

   407   return resAge == oldAge;

   403 }

   408 }

   404 

   409 

   408 }

   413 }

   409 

   414 

   410 // OverflowTaskQueue is a TaskQueue that also includes an overflow stack for

   415 // OverflowTaskQueue is a TaskQueue that also includes an overflow stack for

   411 // elements that do not fit in the TaskQueue.

   416 // elements that do not fit in the TaskQueue.

   412 //

   417 //

   416 // is_empty() - return true if both the TaskQueue and overflow stack are empty

   421 // is_empty() - return true if both the TaskQueue and overflow stack are empty

   417 //

   422 //

   418 // Note that size() is not hidden--it returns the number of elements in the

   423 // Note that size() is not hidden--it returns the number of elements in the

   419 // TaskQueue, and does not include the size of the overflow stack.  This

   424 // TaskQueue, and does not include the size of the overflow stack.  This

   420 // simplifies replacement of GenericTaskQueues with OverflowTaskQueues.

   425 // simplifies replacement of GenericTaskQueues with OverflowTaskQueues.

   423 {

   428 {

   424 public:

   429 public:

   427 

   432 

   428   TASKQUEUE_STATS_ONLY(using taskqueue_t::stats;)

   433   TASKQUEUE_STATS_ONLY(using taskqueue_t::stats;)

   429 

   434 

   430   // Push task t onto the queue or onto the overflow stack.  Return true.

   435   // Push task t onto the queue or onto the overflow stack.  Return true.

   431   inline bool push(E t);

   436   inline bool push(E t);

   443 

   448 

   444 private:

   449 private:

   445   overflow_t _overflow_stack;

   450   overflow_t _overflow_stack;

   446 };

   451 };

   447 

   452 

   450 {

   455 {

   451   if (!taskqueue_t::push(t)) {

   456   if (!taskqueue_t::push(t)) {

   452     overflow_stack()->push(t);

   457     overflow_stack()->push(t);

   453     TASKQUEUE_STATS_ONLY(stats.record_overflow(overflow_stack()->size()));

   458     TASKQUEUE_STATS_ONLY(stats.record_overflow(overflow_stack()->size()));

   454   }

   459   }

   455   return true;

   460   return true;

   456 }

   461 }

   457 

   462 

   460 {

   465 {

   461   if (overflow_empty()) return false;

   466   if (overflow_empty()) return false;

   462   t = overflow_stack()->pop();

   467   t = overflow_stack()->pop();

   463   return true;

   468   return true;

   464 }

   469 }

   465 

   470 

   467 protected:

   472 protected:

   468   static int randomParkAndMiller(int* seed0);

   473   static int randomParkAndMiller(int* seed0);

   469 public:

   474 public:

   470   // Returns "true" if some TaskQueue in the set contains a task.

   475   // Returns "true" if some TaskQueue in the set contains a task.

   471   virtual bool peek() = 0;

   476   virtual bool peek() = 0;

   472 };

   477 };

   473 

   478 

   476 private:

   484 private:

   477   uint _n;

   485   uint _n;

   478   T** _queues;

   486   T** _queues;

   479 

   487 

   480 public:

   488 public:

   481   typedef typename T::element_type E;

   489   typedef typename T::element_type E;

   482 

   490 

   483   GenericTaskQueueSet(int n) : _n(n) {

   491   GenericTaskQueueSet(int n) : _n(n) {

   484     typedef T* GenericTaskQueuePtr;

   492     typedef T* GenericTaskQueuePtr;

   486     for (int i = 0; i < n; i++) {

   494     for (int i = 0; i < n; i++) {

   487       _queues[i] = NULL;

   495       _queues[i] = NULL;

   488     }

   496     }

   489   }

   497   }

   490 

   498 

   504   bool steal(uint queue_num, int* seed, E& t);

   512   bool steal(uint queue_num, int* seed, E& t);

   505 

   513 

   506   bool peek();

   514   bool peek();

   507 };

   515 };

   508 

   516 

   511   assert(i < _n, "index out of range.");

   519   assert(i < _n, "index out of range.");

   512   _queues[i] = q;

   520   _queues[i] = q;

   513 }

   521 }

   514 

   522 

   517   return _queues[i];

   525   return _queues[i];

   518 }

   526 }

   519 

   527 

   522   for (uint i = 0; i < 2 * _n; i++) {

   530   for (uint i = 0; i < 2 * _n; i++) {

   523     if (steal_best_of_2(queue_num, seed, t)) {

   531     if (steal_best_of_2(queue_num, seed, t)) {

   524       TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(true));

   532       TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(true));

   525       return true;

   533       return true;

   526     }

   534     }

   527   }

   535   }

   528   TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(false));

   536   TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(false));

   529   return false;

   537   return false;

   530 }

   538 }

   531 

   539 

   534   if (_n > 2) {

   542   if (_n > 2) {

   535     int best_k;

   543     int best_k;

   536     uint best_sz = 0;

   544     uint best_sz = 0;

   537     for (uint k = 0; k < _n; k++) {

   545     for (uint k = 0; k < _n; k++) {

   538       if (k == queue_num) continue;

   546       if (k == queue_num) continue;

   551     assert(_n == 1, "can't be zero.");

   559     assert(_n == 1, "can't be zero.");

   552     return false;

   560     return false;

   553   }

   561   }

   554 }

   562 }

   555 

   563 

   558   if (_n > 2) {

   566   if (_n > 2) {

   559     uint k = queue_num;

   567     uint k = queue_num;

   561     return _queues[2]->pop_global(t);

   569     return _queues[2]->pop_global(t);

   562   } else if (_n == 2) {

   570   } else if (_n == 2) {

   563     // Just try the other one.

   571     // Just try the other one.

   564     int k = (queue_num + 1) % 2;

   572     int k = (queue_num + 1) % 2;

   565     return _queues[k]->pop_global(t);

   573     return _queues[k]->pop_global(t);

   567     assert(_n == 1, "can't be zero.");

   575     assert(_n == 1, "can't be zero.");

   568     return false;

   576     return false;

   569   }

   577   }

   570 }

   578 }

   571 

   579 

   574   if (_n > 2) {

   582   if (_n > 2) {

   575     uint k1 = queue_num;

   583     uint k1 = queue_num;

   577     uint k2 = queue_num;

   585     uint k2 = queue_num;

   579     // Sample both and try the larger.

   587     // Sample both and try the larger.

   580     uint sz1 = _queues[k1]->size();

   588     uint sz1 = _queues[k1]->size();

   581     uint sz2 = _queues[k2]->size();

   589     uint sz2 = _queues[k2]->size();

   582     if (sz2 > sz1) return _queues[k2]->pop_global(t);

   590     if (sz2 > sz1) return _queues[k2]->pop_global(t);

   583     else return _queues[k1]->pop_global(t);

   591     else return _queues[k1]->pop_global(t);

   589     assert(_n == 1, "can't be zero.");

   597     assert(_n == 1, "can't be zero.");

   590     return false;

   598     return false;

   591   }

   599   }

   592 }

   600 }

   593 

   601 

   596   // Try all the queues.

   604   // Try all the queues.

   597   for (uint j = 0; j < _n; j++) {

   605   for (uint j = 0; j < _n; j++) {

   598     if (_queues[j]->peek())

   606     if (_queues[j]->peek())

   599       return true;

   607       return true;

   600   }

   608   }

   601   return false;

   609   return false;

   602 }

   610 }

   603 

   611 

   604 // When to terminate from the termination protocol.

   612 // When to terminate from the termination protocol.

   606 public:

   614 public:

   607   virtual bool should_exit_termination() = 0;

   615   virtual bool should_exit_termination() = 0;

   608 };

   616 };

   609 

   617 

   610 // A class to aid in the termination of a set of parallel tasks using

   618 // A class to aid in the termination of a set of parallel tasks using

   663   static uint total_peeks() { return _total_peeks; }

   671   static uint total_peeks() { return _total_peeks; }

   664   static void print_termination_counts();

   672   static void print_termination_counts();

   665 #endif

   673 #endif

   666 };

   674 };

   667 

   675 

   670   uint localBot = _bottom;

   678   uint localBot = _bottom;

   671   assert((localBot >= 0) && (localBot < N), "_bottom out of range.");

   679   assert((localBot >= 0) && (localBot < N), "_bottom out of range.");

   672   idx_t top = _age.top();

   680   idx_t top = _age.top();

   673   uint dirty_n_elems = dirty_size(localBot, top);

   681   uint dirty_n_elems = dirty_size(localBot, top);

   674   assert(dirty_n_elems < N, "n_elems out of range.");

   682   assert(dirty_n_elems < N, "n_elems out of range.");

   681   } else {

   689   } else {

   682     return push_slow(t, dirty_n_elems);

   690     return push_slow(t, dirty_n_elems);

   683   }

   691   }

   684 }

   692 }

   685 

   693 

   688   uint localBot = _bottom;

   696   uint localBot = _bottom;

   689   // This value cannot be N-1.  That can only occur as a result of

   697   // This value cannot be N-1.  That can only occur as a result of

   690   // the assignment to bottom in this method.  If it does, this method

   698   // the assignment to bottom in this method.  If it does, this method

   691   // resets the size to 0 before the next call (which is sequential,

   699   // resets the size to 0 before the next call (which is sequential,

   692   // since this is pop_local.)

   700   // since this is pop_local.)

   713     // path.

   721     // path.

   714     return pop_local_slow(localBot, _age.get());

   722     return pop_local_slow(localBot, _age.get());

   715   }

   723   }

   716 }

   724 }

   717 

   725 

   720 

   728 

   721 #ifdef _MSC_VER

   729 #ifdef _MSC_VER

   722 #pragma warning(push)

   730 #pragma warning(push)

   723 // warning C4522: multiple assignment operators specified

   731 // warning C4522: multiple assignment operators specified

   724 #pragma warning(disable:4522)

   732 #pragma warning(disable:4522)

   794 

   802 

   795 #ifdef _MSC_VER

   803 #ifdef _MSC_VER

   796 #pragma warning(pop)

   804 #pragma warning(pop)

   797 #endif

   805 #endif

   798 

   806 

   804 

   812 

   805 

   813 

   806 #endif // SHARE_VM_UTILITIES_TASKQUEUE_HPP

   814 #endif // SHARE_VM_UTILITIES_TASKQUEUE_HPP