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