1 /*
   2  * Copyright (c) 2002, 2015, 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 
  25 #ifndef SHARE_VM_UTILITIES_WORKGROUP_HPP
  26 #define SHARE_VM_UTILITIES_WORKGROUP_HPP
  27 
  28 #include "runtime/thread.inline.hpp"
  29 #include "utilities/taskqueue.hpp"
  30 
  31 // Task class hierarchy:
  32 //   AbstractGangTask
  33 //     AbstractGangTaskWOopQueues
  34 //
  35 // Gang/Group class hierarchy:
  36 //   AbstractWorkGang
  37 //     WorkGang
  38 //       FlexibleWorkGang
  39 //         YieldingFlexibleWorkGang (defined in another file)
  40 //
  41 // Worker class hierarchy:
  42 //   GangWorker (subclass of WorkerThread)
  43 //     YieldingFlexibleGangWorker   (defined in another file)
  44 
  45 // Forward declarations of classes defined here
  46 
  47 class WorkGang;
  48 class GangWorker;
  49 class YieldingFlexibleGangWorker;
  50 class YieldingFlexibleGangTask;
  51 class WorkData;
  52 class AbstractWorkGang;
  53 
  54 // An abstract task to be worked on by a gang.
  55 // You subclass this to supply your own work() method
  56 class AbstractGangTask VALUE_OBJ_CLASS_SPEC {
  57 public:
  58   // The abstract work method.
  59   // The argument tells you which member of the gang you are.
  60   virtual void work(uint worker_id) = 0;
  61 
  62   // This method configures the task for proper termination.
  63   // Some tasks do not have any requirements on termination
  64   // and may inherit this method that does nothing.  Some
  65   // tasks do some coordination on termination and override
  66   // this method to implement that coordination.
  67   virtual void set_for_termination(uint active_workers) {};
  68 
  69   // Debugging accessor for the name.
  70   const char* name() const PRODUCT_RETURN_(return NULL;);
  71   int counter() { return _counter; }
  72   void set_counter(int value) { _counter = value; }
  73   int *address_of_counter() { return &_counter; }
  74 
  75   // RTTI
  76   NOT_PRODUCT(virtual bool is_YieldingFlexibleGang_task() const {
  77     return false;
  78   })
  79 
  80 private:
  81   NOT_PRODUCT(const char* _name;)
  82   // ??? Should a task have a priority associated with it?
  83   // ??? Or can the run method adjust priority as needed?
  84   int _counter;
  85 
  86 protected:
  87   // Constructor and desctructor: only construct subclasses.
  88   AbstractGangTask(const char* name)
  89   {
  90     NOT_PRODUCT(_name = name);
  91     _counter = 0;
  92   }
  93   ~AbstractGangTask() { }
  94 
  95 public:
  96 };
  97 
  98 class AbstractGangTaskWOopQueues : public AbstractGangTask {
  99   OopTaskQueueSet*       _queues;
 100   ParallelTaskTerminator _terminator;
 101  public:
 102   AbstractGangTaskWOopQueues(const char* name, OopTaskQueueSet* queues) :
 103     AbstractGangTask(name), _queues(queues), _terminator(0, _queues) {}
 104   ParallelTaskTerminator* terminator() { return &_terminator; }
 105   virtual void set_for_termination(uint active_workers) {
 106     terminator()->reset_for_reuse(active_workers);
 107   }
 108   OopTaskQueueSet* queues() { return _queues; }
 109 };
 110 
 111 
 112 // Class AbstractWorkGang:
 113 // An abstract class representing a gang of workers.
 114 // You subclass this to supply an implementation of run_task().
 115 class AbstractWorkGang: public CHeapObj<mtInternal> {
 116   // Here's the public interface to this class.
 117 public:
 118   // Constructor and destructor.
 119   AbstractWorkGang(const char* name, bool are_GC_task_threads,
 120                    bool are_ConcurrentGC_threads);
 121   ~AbstractWorkGang();
 122   // Run a task, returns when the task is done (or terminated).
 123   virtual void run_task(AbstractGangTask* task) = 0;
 124   // Stop and terminate all workers.
 125   virtual void stop();
 126   // Return true if more workers should be applied to the task.
 127   virtual bool needs_more_workers() const { return true; }
 128 public:
 129   // Debugging.
 130   const char* name() const;
 131 protected:
 132   // Initialize only instance data.
 133   const bool _are_GC_task_threads;
 134   const bool _are_ConcurrentGC_threads;
 135   // Printing support.
 136   const char* _name;
 137   // The monitor which protects these data,
 138   // and notifies of changes in it.
 139   Monitor*  _monitor;
 140   // The count of the number of workers in the gang.
 141   uint _total_workers;
 142   // Whether the workers should terminate.
 143   bool _terminate;
 144   // The array of worker threads for this gang.
 145   // This is only needed for cleaning up.
 146   GangWorker** _gang_workers;
 147   // The task for this gang.
 148   AbstractGangTask* _task;
 149   // A sequence number for the current task.
 150   int _sequence_number;
 151   // The number of started workers.
 152   uint _started_workers;
 153   // The number of finished workers.
 154   uint _finished_workers;
 155 public:
 156   // Accessors for fields
 157   Monitor* monitor() const {
 158     return _monitor;
 159   }
 160   uint total_workers() const {
 161     return _total_workers;
 162   }
 163   virtual uint active_workers() const {
 164     return _total_workers;
 165   }
 166   bool terminate() const {
 167     return _terminate;
 168   }
 169   GangWorker** gang_workers() const {
 170     return _gang_workers;
 171   }
 172   AbstractGangTask* task() const {
 173     return _task;
 174   }
 175   int sequence_number() const {
 176     return _sequence_number;
 177   }
 178   uint started_workers() const {
 179     return _started_workers;
 180   }
 181   uint finished_workers() const {
 182     return _finished_workers;
 183   }
 184   bool are_GC_task_threads() const {
 185     return _are_GC_task_threads;
 186   }
 187   bool are_ConcurrentGC_threads() const {
 188     return _are_ConcurrentGC_threads;
 189   }
 190   // Predicates.
 191   bool is_idle() const {
 192     return (task() == NULL);
 193   }
 194   // Return the Ith gang worker.
 195   GangWorker* gang_worker(uint i) const;
 196 
 197   void threads_do(ThreadClosure* tc) const;
 198 
 199   // Printing
 200   void print_worker_threads_on(outputStream *st) const;
 201   void print_worker_threads() const {
 202     print_worker_threads_on(tty);
 203   }
 204 
 205 protected:
 206   friend class GangWorker;
 207   friend class YieldingFlexibleGangWorker;
 208   // Note activation and deactivation of workers.
 209   // These methods should only be called with the mutex held.
 210   void internal_worker_poll(WorkData* data) const;
 211   void internal_note_start();
 212   void internal_note_finish();
 213 };
 214 
 215 class WorkData: public StackObj {
 216   // This would be a struct, but I want accessor methods.
 217 private:
 218   bool              _terminate;
 219   AbstractGangTask* _task;
 220   int               _sequence_number;
 221 public:
 222   // Constructor and destructor
 223   WorkData() {
 224     _terminate       = false;
 225     _task            = NULL;
 226     _sequence_number = 0;
 227   }
 228   ~WorkData() {
 229   }
 230   // Accessors and modifiers
 231   bool terminate()                       const { return _terminate;  }
 232   void set_terminate(bool value)               { _terminate = value; }
 233   AbstractGangTask* task()               const { return _task; }
 234   void set_task(AbstractGangTask* value)       { _task = value; }
 235   int sequence_number()                  const { return _sequence_number; }
 236   void set_sequence_number(int value)          { _sequence_number = value; }
 237 
 238   YieldingFlexibleGangTask* yf_task()    const {
 239     return (YieldingFlexibleGangTask*)_task;
 240   }
 241 };
 242 
 243 // Class WorkGang:
 244 class WorkGang: public AbstractWorkGang {
 245 public:
 246   // Constructor
 247   WorkGang(const char* name, uint workers,
 248            bool are_GC_task_threads, bool are_ConcurrentGC_threads);
 249   // Run a task, returns when the task is done (or terminated).
 250   virtual void run_task(AbstractGangTask* task);
 251   void run_task(AbstractGangTask* task, uint no_of_parallel_workers);
 252   // Allocate a worker and return a pointer to it.
 253   virtual GangWorker* allocate_worker(uint which);
 254   // Initialize workers in the gang.  Return true if initialization
 255   // succeeded. The type of the worker can be overridden in a derived
 256   // class with the appropriate implementation of allocate_worker().
 257   bool initialize_workers();
 258 };
 259 
 260 // Class GangWorker:
 261 //   Several instances of this class run in parallel as workers for a gang.
 262 class GangWorker: public WorkerThread {
 263 public:
 264   // Constructors and destructor.
 265   GangWorker(AbstractWorkGang* gang, uint id);
 266 
 267   // The only real method: run a task for the gang.
 268   virtual void run();
 269   // Predicate for Thread
 270   virtual bool is_GC_task_thread() const;
 271   virtual bool is_ConcurrentGC_thread() const;
 272   // Printing
 273   void print_on(outputStream* st) const;
 274   virtual void print() const { print_on(tty); }
 275 protected:
 276   AbstractWorkGang* _gang;
 277 
 278   virtual void initialize();
 279   virtual void loop();
 280 
 281 public:
 282   AbstractWorkGang* gang() const { return _gang; }
 283 };
 284 
 285 // Dynamic number of worker threads
 286 //
 287 // This type of work gang is used to run different numbers of
 288 // worker threads at different times.  The
 289 // number of workers run for a task is "_active_workers"
 290 // instead of "_total_workers" in a WorkGang.  The method
 291 // "needs_more_workers()" returns true until "_active_workers"
 292 // have been started and returns false afterwards.  The
 293 // implementation of "needs_more_workers()" in WorkGang always
 294 // returns true so that all workers are started.  The method
 295 // "loop()" in GangWorker was modified to ask "needs_more_workers()"
 296 // in its loop to decide if it should start working on a task.
 297 // A worker in "loop()" waits for notification on the WorkGang
 298 // monitor and execution of each worker as it checks for work
 299 // is serialized via the same monitor.  The "needs_more_workers()"
 300 // call is serialized and additionally the calculation for the
 301 // "part" (effectively the worker id for executing the task) is
 302 // serialized to give each worker a unique "part".  Workers that
 303 // are not needed for this tasks (i.e., "_active_workers" have
 304 // been started before it, continue to wait for work.
 305 
 306 class FlexibleWorkGang: public WorkGang {
 307   // The currently active workers in this gang.
 308   // This is a number that is dynamically adjusted
 309   // and checked in the run_task() method at each invocation.
 310   // As described above _active_workers determines the number
 311   // of threads started on a task.  It must also be used to
 312   // determine completion.
 313 
 314  protected:
 315   uint _active_workers;
 316  public:
 317   // Constructor and destructor.
 318   // Initialize active_workers to a minimum value.  Setting it to
 319   // the parameter "workers" will initialize it to a maximum
 320   // value which is not desirable.
 321   FlexibleWorkGang(const char* name, uint workers,
 322                    bool are_GC_task_threads,
 323                    bool  are_ConcurrentGC_threads) :
 324     WorkGang(name, workers, are_GC_task_threads, are_ConcurrentGC_threads),
 325     _active_workers(UseDynamicNumberOfGCThreads ? 1U : ParallelGCThreads) {}
 326   // Accessors for fields
 327   virtual uint active_workers() const { return _active_workers; }
 328   void set_active_workers(uint v) {
 329     assert(v <= _total_workers,
 330            "Trying to set more workers active than there are");
 331     _active_workers = MIN2(v, _total_workers);
 332     assert(v != 0, "Trying to set active workers to 0");
 333     _active_workers = MAX2(1U, _active_workers);
 334     assert(UseDynamicNumberOfGCThreads || _active_workers == _total_workers,
 335            "Unless dynamic should use total workers");
 336   }
 337   virtual void run_task(AbstractGangTask* task);
 338   virtual bool needs_more_workers() const {
 339     return _started_workers < _active_workers;
 340   }
 341 };
 342 
 343 // A class that acts as a synchronisation barrier. Workers enter
 344 // the barrier and must wait until all other workers have entered
 345 // before any of them may leave.
 346 
 347 class WorkGangBarrierSync : public StackObj {
 348 protected:
 349   Monitor _monitor;
 350   uint    _n_workers;
 351   uint    _n_completed;
 352   bool    _should_reset;
 353   bool    _aborted;
 354 
 355   Monitor* monitor()        { return &_monitor; }
 356   uint     n_workers()      { return _n_workers; }
 357   uint     n_completed()    { return _n_completed; }
 358   bool     should_reset()   { return _should_reset; }
 359   bool     aborted()        { return _aborted; }
 360 
 361   void     zero_completed() { _n_completed = 0; }
 362   void     inc_completed()  { _n_completed++; }
 363   void     set_aborted()    { _aborted = true; }
 364   void     set_should_reset(bool v) { _should_reset = v; }
 365 
 366 public:
 367   WorkGangBarrierSync();
 368   WorkGangBarrierSync(uint n_workers, const char* name);
 369 
 370   // Set the number of workers that will use the barrier.
 371   // Must be called before any of the workers start running.
 372   void set_n_workers(uint n_workers);
 373 
 374   // Enter the barrier. A worker that enters the barrier will
 375   // not be allowed to leave until all other threads have
 376   // also entered the barrier or the barrier is aborted.
 377   // Returns false if the barrier was aborted.
 378   bool enter();
 379 
 380   // Aborts the barrier and wakes up any threads waiting for
 381   // the barrier to complete. The barrier will remain in the
 382   // aborted state until the next call to set_n_workers().
 383   void abort();
 384 };
 385 
 386 // A class to manage claiming of subtasks within a group of tasks.  The
 387 // subtasks will be identified by integer indices, usually elements of an
 388 // enumeration type.
 389 
 390 class SubTasksDone: public CHeapObj<mtInternal> {
 391   uint* _tasks;
 392   uint _n_tasks;
 393   // _n_threads is used to determine when a sub task is done.
 394   // It does not control how many threads will execute the subtask
 395   // but must be initialized to the number that do execute the task
 396   // in order to correctly decide when the subtask is done (all the
 397   // threads working on the task have finished).
 398   uint _n_threads;
 399   uint _threads_completed;
 400 #ifdef ASSERT
 401   volatile uint _claimed;
 402 #endif
 403 
 404   // Set all tasks to unclaimed.
 405   void clear();
 406 
 407 public:
 408   // Initializes "this" to a state in which there are "n" tasks to be
 409   // processed, none of the which are originally claimed.  The number of
 410   // threads doing the tasks is initialized 1.
 411   SubTasksDone(uint n);
 412 
 413   // True iff the object is in a valid state.
 414   bool valid();
 415 
 416   // Get/set the number of parallel threads doing the tasks to "t".  Can only
 417   // be called before tasks start or after they are complete.
 418   uint n_threads() { return _n_threads; }
 419   void set_n_threads(uint t);
 420 
 421   // Returns "false" if the task "t" is unclaimed, and ensures that task is
 422   // claimed.  The task "t" is required to be within the range of "this".
 423   bool is_task_claimed(uint t);
 424 
 425   // The calling thread asserts that it has attempted to claim all the
 426   // tasks that it will try to claim.  Every thread in the parallel task
 427   // must execute this.  (When the last thread does so, the task array is
 428   // cleared.)
 429   void all_tasks_completed();
 430 
 431   // Destructor.
 432   ~SubTasksDone();
 433 };
 434 
 435 // As above, but for sequential tasks, i.e. instead of claiming
 436 // sub-tasks from a set (possibly an enumeration), claim sub-tasks
 437 // in sequential order. This is ideal for claiming dynamically
 438 // partitioned tasks (like striding in the parallel remembered
 439 // set scanning). Note that unlike the above class this is
 440 // a stack object - is there any reason for it not to be?
 441 
 442 class SequentialSubTasksDone : public StackObj {
 443 protected:
 444   uint _n_tasks;     // Total number of tasks available.
 445   uint _n_claimed;   // Number of tasks claimed.
 446   // _n_threads is used to determine when a sub task is done.
 447   // See comments on SubTasksDone::_n_threads
 448   uint _n_threads;   // Total number of parallel threads.
 449   uint _n_completed; // Number of completed threads.
 450 
 451   void clear();
 452 
 453 public:
 454   SequentialSubTasksDone() {
 455     clear();
 456   }
 457   ~SequentialSubTasksDone() {}
 458 
 459   // True iff the object is in a valid state.
 460   bool valid();
 461 
 462   // number of tasks
 463   uint n_tasks() const { return _n_tasks; }
 464 
 465   // Get/set the number of parallel threads doing the tasks to t.
 466   // Should be called before the task starts but it is safe
 467   // to call this once a task is running provided that all
 468   // threads agree on the number of threads.
 469   uint n_threads() { return _n_threads; }
 470   void set_n_threads(uint t) { _n_threads = t; }
 471 
 472   // Set the number of tasks to be claimed to t. As above,
 473   // should be called before the tasks start but it is safe
 474   // to call this once a task is running provided all threads
 475   // agree on the number of tasks.
 476   void set_n_tasks(uint t) { _n_tasks = t; }
 477 
 478   // Returns false if the next task in the sequence is unclaimed,
 479   // and ensures that it is claimed. Will set t to be the index
 480   // of the claimed task in the sequence. Will return true if
 481   // the task cannot be claimed and there are none left to claim.
 482   bool is_task_claimed(uint& t);
 483 
 484   // The calling thread asserts that it has attempted to claim
 485   // all the tasks it possibly can in the sequence. Every thread
 486   // claiming tasks must promise call this. Returns true if this
 487   // is the last thread to complete so that the thread can perform
 488   // cleanup if necessary.
 489   bool all_tasks_completed();
 490 };
 491 
 492 // Represents a set of free small integer ids.
 493 class FreeIdSet : public CHeapObj<mtInternal> {
 494   enum {
 495     end_of_list = -1,
 496     claimed = -2
 497   };
 498 
 499   int _sz;
 500   Monitor* _mon;
 501 
 502   int* _ids;
 503   int _hd;
 504   int _waiters;
 505   int _claimed;
 506 
 507   static bool _safepoint;
 508   typedef FreeIdSet* FreeIdSetPtr;
 509   static const int NSets = 10;
 510   static FreeIdSetPtr _sets[NSets];
 511   static bool _stat_init;
 512   int _index;
 513 
 514 public:
 515   FreeIdSet(int sz, Monitor* mon);
 516   ~FreeIdSet();
 517 
 518   static void set_safepoint(bool b);
 519 
 520   // Attempt to claim the given id permanently.  Returns "true" iff
 521   // successful.
 522   bool claim_perm_id(int i);
 523 
 524   // Returns an unclaimed parallel id (waiting for one to be released if
 525   // necessary).  Returns "-1" if a GC wakes up a wait for an id.
 526   int claim_par_id();
 527 
 528   void release_par_id(int id);
 529 };
 530 
 531 #endif // SHARE_VM_UTILITIES_WORKGROUP_HPP