1 /* 2 * Copyright (c) 2002, 2013, 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(int 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(int 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 // Note on use of FlexibleWorkGang's for GC. 307 // There are three places where task completion is determined. 308 // In 309 // 1) ParallelTaskTerminator::offer_termination() where _n_threads 310 // must be set to the correct value so that count of workers that 311 // have offered termination will exactly match the number 312 // working on the task. Tasks such as those derived from GCTask 313 // use ParallelTaskTerminator's. Tasks that want load balancing 314 // by work stealing use this method to gauge completion. 315 // 2) SubTasksDone has a variable _n_threads that is used in 316 // all_tasks_completed() to determine completion. all_tasks_complete() 317 // counts the number of tasks that have been done and then reset 318 // the SubTasksDone so that it can be used again. When the number of 319 // tasks is set to the number of GC workers, then _n_threads must 320 // be set to the number of active GC workers. G1RootProcessor and 321 // GenCollectedHeap have SubTasksDone. 322 // 3) SequentialSubTasksDone has an _n_threads that is used in 323 // a way similar to SubTasksDone and has the same dependency on the 324 // number of active GC workers. CompactibleFreeListSpace and Space 325 // have SequentialSubTasksDone's. 326 // 327 // Examples of using SubTasksDone and SequentialSubTasksDone: 328 // G1RootProcessor and GenCollectedHeap::process_roots() use 329 // SubTasksDone* _process_strong_tasks to claim tasks for workers 330 // 331 // GenCollectedHeap::gen_process_roots() calls 332 // rem_set()->younger_refs_iterate() 333 // to scan the card table and which eventually calls down into 334 // CardTableModRefBS::par_non_clean_card_iterate_work(). This method 335 // uses SequentialSubTasksDone* _pst to claim tasks. 336 // Both SubTasksDone and SequentialSubTasksDone call their method 337 // all_tasks_completed() to count the number of GC workers that have 338 // finished their work. That logic is "when all the workers are 339 // finished the tasks are finished". 340 // 341 // The pattern that appears in the code is to set _n_threads 342 // to a value > 1 before a task that you would like executed in parallel 343 // and then to set it to 0 after that task has completed. A value of 344 // 0 is a "special" value in set_n_threads() which translates to 345 // setting _n_threads to 1. 346 // 347 // Some code uses _n_termination to decide if work should be done in 348 // parallel. The notorious possibly_parallel_oops_do() in threads.cpp 349 // is an example of such code. Look for variable "is_par" for other 350 // examples. 351 // 352 // The active_workers is not reset to 0 after a parallel phase. It's 353 // value may be used in later phases and in one instance at least 354 // (the parallel remark) it has to be used (the parallel remark depends 355 // on the partitioning done in the previous parallel scavenge). 356 357 class FlexibleWorkGang: public WorkGang { 358 // The currently active workers in this gang. 359 // This is a number that is dynamically adjusted 360 // and checked in the run_task() method at each invocation. 361 // As described above _active_workers determines the number 362 // of threads started on a task. It must also be used to 363 // determine completion. 364 365 protected: 366 uint _active_workers; 367 public: 368 // Constructor and destructor. 369 // Initialize active_workers to a minimum value. Setting it to 370 // the parameter "workers" will initialize it to a maximum 371 // value which is not desirable. 372 FlexibleWorkGang(const char* name, uint workers, 373 bool are_GC_task_threads, 374 bool are_ConcurrentGC_threads) : 375 WorkGang(name, workers, are_GC_task_threads, are_ConcurrentGC_threads), 376 _active_workers(UseDynamicNumberOfGCThreads ? 1U : ParallelGCThreads) {} 377 // Accessors for fields 378 virtual uint active_workers() const { return _active_workers; } 379 void set_active_workers(uint v) { 380 assert(v <= _total_workers, 381 "Trying to set more workers active than there are"); 382 _active_workers = MIN2(v, _total_workers); 383 assert(v != 0, "Trying to set active workers to 0"); 384 _active_workers = MAX2(1U, _active_workers); 385 assert(UseDynamicNumberOfGCThreads || _active_workers == _total_workers, 386 "Unless dynamic should use total workers"); 387 } 388 virtual void run_task(AbstractGangTask* task); 389 virtual bool needs_more_workers() const { 390 return _started_workers < _active_workers; 391 } 392 }; 393 394 // Work gangs in garbage collectors: 2009-06-10 395 // 396 // SharedHeap - work gang for stop-the-world parallel collection. 397 // Used by 398 // ParNewGeneration 399 // CMSParRemarkTask 400 // CMSRefProcTaskExecutor 401 // G1CollectedHeap 402 // G1ParFinalCountTask 403 // ConcurrentMark 404 // CMSCollector 405 406 // A class that acts as a synchronisation barrier. Workers enter 407 // the barrier and must wait until all other workers have entered 408 // before any of them may leave. 409 410 class WorkGangBarrierSync : public StackObj { 411 protected: 412 Monitor _monitor; 413 uint _n_workers; 414 uint _n_completed; 415 bool _should_reset; 416 bool _aborted; 417 418 Monitor* monitor() { return &_monitor; } 419 uint n_workers() { return _n_workers; } 420 uint n_completed() { return _n_completed; } 421 bool should_reset() { return _should_reset; } 422 bool aborted() { return _aborted; } 423 424 void zero_completed() { _n_completed = 0; } 425 void inc_completed() { _n_completed++; } 426 void set_aborted() { _aborted = true; } 427 void set_should_reset(bool v) { _should_reset = v; } 428 429 public: 430 WorkGangBarrierSync(); 431 WorkGangBarrierSync(uint n_workers, const char* name); 432 433 // Set the number of workers that will use the barrier. 434 // Must be called before any of the workers start running. 435 void set_n_workers(uint n_workers); 436 437 // Enter the barrier. A worker that enters the barrier will 438 // not be allowed to leave until all other threads have 439 // also entered the barrier or the barrier is aborted. 440 // Returns false if the barrier was aborted. 441 bool enter(); 442 443 // Aborts the barrier and wakes up any threads waiting for 444 // the barrier to complete. The barrier will remain in the 445 // aborted state until the next call to set_n_workers(). 446 void abort(); 447 }; 448 449 // A class to manage claiming of subtasks within a group of tasks. The 450 // subtasks will be identified by integer indices, usually elements of an 451 // enumeration type. 452 453 class SubTasksDone: public CHeapObj<mtInternal> { 454 uint* _tasks; 455 uint _n_tasks; 456 // _n_threads is used to determine when a sub task is done. 457 // It does not control how many threads will execute the subtask 458 // but must be initialized to the number that do execute the task 459 // in order to correctly decide when the subtask is done (all the 460 // threads working on the task have finished). 461 uint _n_threads; 462 uint _threads_completed; 463 #ifdef ASSERT 464 volatile uint _claimed; 465 #endif 466 467 // Set all tasks to unclaimed. 468 void clear(); 469 470 public: 471 // Initializes "this" to a state in which there are "n" tasks to be 472 // processed, none of the which are originally claimed. The number of 473 // threads doing the tasks is initialized 1. 474 SubTasksDone(uint n); 475 476 // True iff the object is in a valid state. 477 bool valid(); 478 479 // Get/set the number of parallel threads doing the tasks to "t". Can only 480 // be called before tasks start or after they are complete. 481 uint n_threads() { return _n_threads; } 482 void set_n_threads(uint t); 483 484 // Returns "false" if the task "t" is unclaimed, and ensures that task is 485 // claimed. The task "t" is required to be within the range of "this". 486 bool is_task_claimed(uint t); 487 488 // The calling thread asserts that it has attempted to claim all the 489 // tasks that it will try to claim. Every thread in the parallel task 490 // must execute this. (When the last thread does so, the task array is 491 // cleared.) 492 void all_tasks_completed(); 493 494 // Destructor. 495 ~SubTasksDone(); 496 }; 497 498 // As above, but for sequential tasks, i.e. instead of claiming 499 // sub-tasks from a set (possibly an enumeration), claim sub-tasks 500 // in sequential order. This is ideal for claiming dynamically 501 // partitioned tasks (like striding in the parallel remembered 502 // set scanning). Note that unlike the above class this is 503 // a stack object - is there any reason for it not to be? 504 505 class SequentialSubTasksDone : public StackObj { 506 protected: 507 uint _n_tasks; // Total number of tasks available. 508 uint _n_claimed; // Number of tasks claimed. 509 // _n_threads is used to determine when a sub task is done. 510 // See comments on SubTasksDone::_n_threads 511 uint _n_threads; // Total number of parallel threads. 512 uint _n_completed; // Number of completed threads. 513 514 void clear(); 515 516 public: 517 SequentialSubTasksDone() { 518 clear(); 519 } 520 ~SequentialSubTasksDone() {} 521 522 // True iff the object is in a valid state. 523 bool valid(); 524 525 // number of tasks 526 uint n_tasks() const { return _n_tasks; } 527 528 // Get/set the number of parallel threads doing the tasks to t. 529 // Should be called before the task starts but it is safe 530 // to call this once a task is running provided that all 531 // threads agree on the number of threads. 532 uint n_threads() { return _n_threads; } 533 void set_n_threads(uint t) { _n_threads = t; } 534 535 // Set the number of tasks to be claimed to t. As above, 536 // should be called before the tasks start but it is safe 537 // to call this once a task is running provided all threads 538 // agree on the number of tasks. 539 void set_n_tasks(uint t) { _n_tasks = t; } 540 541 // Returns false if the next task in the sequence is unclaimed, 542 // and ensures that it is claimed. Will set t to be the index 543 // of the claimed task in the sequence. Will return true if 544 // the task cannot be claimed and there are none left to claim. 545 bool is_task_claimed(uint& t); 546 547 // The calling thread asserts that it has attempted to claim 548 // all the tasks it possibly can in the sequence. Every thread 549 // claiming tasks must promise call this. Returns true if this 550 // is the last thread to complete so that the thread can perform 551 // cleanup if necessary. 552 bool all_tasks_completed(); 553 }; 554 555 // Represents a set of free small integer ids. 556 class FreeIdSet : public CHeapObj<mtInternal> { 557 enum { 558 end_of_list = -1, 559 claimed = -2 560 }; 561 562 int _sz; 563 Monitor* _mon; 564 565 int* _ids; 566 int _hd; 567 int _waiters; 568 int _claimed; 569 570 static bool _safepoint; 571 typedef FreeIdSet* FreeIdSetPtr; 572 static const int NSets = 10; 573 static FreeIdSetPtr _sets[NSets]; 574 static bool _stat_init; 575 int _index; 576 577 public: 578 FreeIdSet(int sz, Monitor* mon); 579 ~FreeIdSet(); 580 581 static void set_safepoint(bool b); 582 583 // Attempt to claim the given id permanently. Returns "true" iff 584 // successful. 585 bool claim_perm_id(int i); 586 587 // Returns an unclaimed parallel id (waiting for one to be released if 588 // necessary). Returns "-1" if a GC wakes up a wait for an id. 589 int claim_par_id(); 590 591 void release_par_id(int id); 592 }; 593 594 #endif // SHARE_VM_UTILITIES_WORKGROUP_HPP