Thu, 11 Feb 2010 15:52:19 -0800
6923991: G1: improve scalability of RSet scanning
Summary: Implemented block-based work stealing. Moved copying during the rset scanning phase to the main copying phase. Made the size of rset table depend on the region size.
Reviewed-by: apetrusenko, tonyp
duke@435 | 1 | /* |
duke@435 | 2 | * Copyright 2005 Sun Microsystems, Inc. All Rights Reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
duke@435 | 19 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
duke@435 | 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
duke@435 | 21 | * have any questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
duke@435 | 25 | # include "incls/_precompiled.incl" |
duke@435 | 26 | # include "incls/_yieldingWorkgroup.cpp.incl" |
duke@435 | 27 | |
duke@435 | 28 | // Forward declaration of classes declared here. |
duke@435 | 29 | |
duke@435 | 30 | class GangWorker; |
duke@435 | 31 | class WorkData; |
duke@435 | 32 | |
duke@435 | 33 | YieldingFlexibleWorkGang::YieldingFlexibleWorkGang( |
ysr@777 | 34 | const char* name, int workers, bool are_GC_task_threads) : |
ysr@777 | 35 | AbstractWorkGang(name, are_GC_task_threads, false) { |
duke@435 | 36 | // Save arguments. |
duke@435 | 37 | _total_workers = workers; |
duke@435 | 38 | assert(_total_workers > 0, "Must have more than 1 worker"); |
duke@435 | 39 | |
duke@435 | 40 | _yielded_workers = 0; |
duke@435 | 41 | |
duke@435 | 42 | if (TraceWorkGang) { |
duke@435 | 43 | tty->print_cr("Constructing work gang %s with %d threads", name, workers); |
duke@435 | 44 | } |
duke@435 | 45 | _gang_workers = NEW_C_HEAP_ARRAY(GangWorker*, workers); |
duke@435 | 46 | assert(gang_workers() != NULL, "Failed to allocate gang workers"); |
duke@435 | 47 | for (int worker = 0; worker < total_workers(); worker += 1) { |
duke@435 | 48 | YieldingFlexibleGangWorker* new_worker = |
duke@435 | 49 | new YieldingFlexibleGangWorker(this, worker); |
duke@435 | 50 | assert(new_worker != NULL, "Failed to allocate YieldingFlexibleGangWorker"); |
duke@435 | 51 | _gang_workers[worker] = new_worker; |
duke@435 | 52 | if (new_worker == NULL || !os::create_thread(new_worker, os::pgc_thread)) |
duke@435 | 53 | vm_exit_out_of_memory(0, "Cannot create worker GC thread. Out of system resources."); |
duke@435 | 54 | if (!DisableStartThread) { |
duke@435 | 55 | os::start_thread(new_worker); |
duke@435 | 56 | } |
duke@435 | 57 | } |
duke@435 | 58 | } |
duke@435 | 59 | |
duke@435 | 60 | // Run a task; returns when the task is done, or the workers yield, |
duke@435 | 61 | // or the task is aborted, or the work gang is terminated via stop(). |
duke@435 | 62 | // A task that has been yielded can be continued via this interface |
duke@435 | 63 | // by using the same task repeatedly as the argument to the call. |
duke@435 | 64 | // It is expected that the YieldingFlexibleGangTask carries the appropriate |
duke@435 | 65 | // continuation information used by workers to continue the task |
duke@435 | 66 | // from its last yield point. Thus, a completed task will return |
duke@435 | 67 | // immediately with no actual work having been done by the workers. |
duke@435 | 68 | ///////////////////// |
duke@435 | 69 | // Implementatiuon notes: remove before checking XXX |
duke@435 | 70 | /* |
duke@435 | 71 | Each gang is working on a task at a certain time. |
duke@435 | 72 | Some subset of workers may have yielded and some may |
duke@435 | 73 | have finished their quota of work. Until this task has |
duke@435 | 74 | been completed, the workers are bound to that task. |
duke@435 | 75 | Once the task has been completed, the gang unbounds |
duke@435 | 76 | itself from the task. |
duke@435 | 77 | |
duke@435 | 78 | The yielding work gang thus exports two invokation |
duke@435 | 79 | interfaces: run_task() and continue_task(). The |
duke@435 | 80 | first is used to initiate a new task and bind it |
duke@435 | 81 | to the workers; the second is used to continue an |
duke@435 | 82 | already bound task that has yielded. Upon completion |
duke@435 | 83 | the binding is released and a new binding may be |
duke@435 | 84 | created. |
duke@435 | 85 | |
duke@435 | 86 | The shape of a yielding work gang is as follows: |
duke@435 | 87 | |
duke@435 | 88 | Overseer invokes run_task(*task). |
duke@435 | 89 | Lock gang monitor |
duke@435 | 90 | Check that there is no existing binding for the gang |
duke@435 | 91 | If so, abort with an error |
duke@435 | 92 | Else, create a new binding of this gang to the given task |
duke@435 | 93 | Set number of active workers (as asked) |
duke@435 | 94 | Notify workers that work is ready to be done |
duke@435 | 95 | [the requisite # workers would then start up |
duke@435 | 96 | and do the task] |
duke@435 | 97 | Wait on the monitor until either |
duke@435 | 98 | all work is completed or the task has yielded |
duke@435 | 99 | -- this is normally done through |
duke@435 | 100 | yielded + completed == active |
duke@435 | 101 | [completed workers are rest to idle state by overseer?] |
duke@435 | 102 | return appropriate status to caller |
duke@435 | 103 | |
duke@435 | 104 | Overseer invokes continue_task(*task), |
duke@435 | 105 | Lock gang monitor |
duke@435 | 106 | Check that task is the same as current binding |
duke@435 | 107 | If not, abort with an error |
duke@435 | 108 | Else, set the number of active workers as requested? |
duke@435 | 109 | Notify workers that they can continue from yield points |
duke@435 | 110 | New workers can also start up as required |
duke@435 | 111 | while satisfying the constraint that |
duke@435 | 112 | active + yielded does not exceed required number |
duke@435 | 113 | Wait (as above). |
duke@435 | 114 | |
duke@435 | 115 | NOTE: In the above, for simplicity in a first iteration |
duke@435 | 116 | our gangs will be of fixed population and will not |
duke@435 | 117 | therefore be flexible work gangs, just yielding work |
duke@435 | 118 | gangs. Once this works well, we will in a second |
duke@435 | 119 | iteration.refinement introduce flexibility into |
duke@435 | 120 | the work gang. |
duke@435 | 121 | |
duke@435 | 122 | NOTE: we can always create a new gang per each iteration |
duke@435 | 123 | in order to get the flexibility, but we will for now |
duke@435 | 124 | desist that simplified route. |
duke@435 | 125 | |
duke@435 | 126 | */ |
duke@435 | 127 | ///////////////////// |
duke@435 | 128 | void YieldingFlexibleWorkGang::start_task(YieldingFlexibleGangTask* new_task) { |
duke@435 | 129 | MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag); |
duke@435 | 130 | assert(task() == NULL, "Gang currently tied to a task"); |
duke@435 | 131 | assert(new_task != NULL, "Null task"); |
duke@435 | 132 | // Bind task to gang |
duke@435 | 133 | _task = new_task; |
duke@435 | 134 | new_task->set_gang(this); // Establish 2-way binding to support yielding |
duke@435 | 135 | _sequence_number++; |
duke@435 | 136 | |
duke@435 | 137 | int requested_size = new_task->requested_size(); |
duke@435 | 138 | assert(requested_size >= 0, "Should be non-negative"); |
duke@435 | 139 | if (requested_size != 0) { |
duke@435 | 140 | _active_workers = MIN2(requested_size, total_workers()); |
duke@435 | 141 | } else { |
duke@435 | 142 | _active_workers = total_workers(); |
duke@435 | 143 | } |
duke@435 | 144 | new_task->set_actual_size(_active_workers); |
duke@435 | 145 | |
duke@435 | 146 | assert(_started_workers == 0, "Tabula rasa non"); |
duke@435 | 147 | assert(_finished_workers == 0, "Tabula rasa non"); |
duke@435 | 148 | assert(_yielded_workers == 0, "Tabula rasa non"); |
duke@435 | 149 | yielding_task()->set_status(ACTIVE); |
duke@435 | 150 | |
duke@435 | 151 | // Wake up all the workers, the first few will get to work, |
duke@435 | 152 | // and the rest will go back to sleep |
duke@435 | 153 | monitor()->notify_all(); |
duke@435 | 154 | wait_for_gang(); |
duke@435 | 155 | } |
duke@435 | 156 | |
duke@435 | 157 | void YieldingFlexibleWorkGang::wait_for_gang() { |
duke@435 | 158 | |
duke@435 | 159 | assert(monitor()->owned_by_self(), "Data race"); |
duke@435 | 160 | // Wait for task to complete or yield |
duke@435 | 161 | for (Status status = yielding_task()->status(); |
duke@435 | 162 | status != COMPLETED && status != YIELDED && status != ABORTED; |
duke@435 | 163 | status = yielding_task()->status()) { |
duke@435 | 164 | assert(started_workers() <= active_workers(), "invariant"); |
duke@435 | 165 | assert(finished_workers() <= active_workers(), "invariant"); |
duke@435 | 166 | assert(yielded_workers() <= active_workers(), "invariant"); |
duke@435 | 167 | monitor()->wait(Mutex::_no_safepoint_check_flag); |
duke@435 | 168 | } |
duke@435 | 169 | switch (yielding_task()->status()) { |
duke@435 | 170 | case COMPLETED: |
duke@435 | 171 | case ABORTED: { |
duke@435 | 172 | assert(finished_workers() == active_workers(), "Inconsistent status"); |
duke@435 | 173 | assert(yielded_workers() == 0, "Invariant"); |
duke@435 | 174 | reset(); // for next task; gang<->task binding released |
duke@435 | 175 | break; |
duke@435 | 176 | } |
duke@435 | 177 | case YIELDED: { |
duke@435 | 178 | assert(yielded_workers() > 0, "Invariant"); |
duke@435 | 179 | assert(yielded_workers() + finished_workers() == active_workers(), |
duke@435 | 180 | "Inconsistent counts"); |
duke@435 | 181 | break; |
duke@435 | 182 | } |
duke@435 | 183 | case ACTIVE: |
duke@435 | 184 | case INACTIVE: |
duke@435 | 185 | case COMPLETING: |
duke@435 | 186 | case YIELDING: |
duke@435 | 187 | case ABORTING: |
duke@435 | 188 | default: |
duke@435 | 189 | ShouldNotReachHere(); |
duke@435 | 190 | } |
duke@435 | 191 | } |
duke@435 | 192 | |
duke@435 | 193 | void YieldingFlexibleWorkGang::continue_task( |
duke@435 | 194 | YieldingFlexibleGangTask* gang_task) { |
duke@435 | 195 | |
duke@435 | 196 | MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag); |
duke@435 | 197 | assert(task() != NULL && task() == gang_task, "Incorrect usage"); |
duke@435 | 198 | // assert(_active_workers == total_workers(), "For now"); |
duke@435 | 199 | assert(_started_workers == _active_workers, "Precondition"); |
duke@435 | 200 | assert(_yielded_workers > 0 && yielding_task()->status() == YIELDED, |
duke@435 | 201 | "Else why are we calling continue_task()"); |
duke@435 | 202 | // Restart the yielded gang workers |
duke@435 | 203 | yielding_task()->set_status(ACTIVE); |
duke@435 | 204 | monitor()->notify_all(); |
duke@435 | 205 | wait_for_gang(); |
duke@435 | 206 | } |
duke@435 | 207 | |
duke@435 | 208 | void YieldingFlexibleWorkGang::reset() { |
duke@435 | 209 | _started_workers = 0; |
duke@435 | 210 | _finished_workers = 0; |
duke@435 | 211 | _active_workers = 0; |
duke@435 | 212 | yielding_task()->set_gang(NULL); |
duke@435 | 213 | _task = NULL; // unbind gang from task |
duke@435 | 214 | } |
duke@435 | 215 | |
duke@435 | 216 | void YieldingFlexibleWorkGang::yield() { |
duke@435 | 217 | assert(task() != NULL, "Inconsistency; should have task binding"); |
duke@435 | 218 | MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag); |
duke@435 | 219 | assert(yielded_workers() < active_workers(), "Consistency check"); |
duke@435 | 220 | if (yielding_task()->status() == ABORTING) { |
duke@435 | 221 | // Do not yield; we need to abort as soon as possible |
duke@435 | 222 | // XXX NOTE: This can cause a performance pathology in the |
duke@435 | 223 | // current implementation in Mustang, as of today, and |
duke@435 | 224 | // pre-Mustang in that as soon as an overflow occurs, |
duke@435 | 225 | // yields will not be honoured. The right way to proceed |
duke@435 | 226 | // of course is to fix bug # TBF, so that abort's cause |
duke@435 | 227 | // us to return at each potential yield point. |
duke@435 | 228 | return; |
duke@435 | 229 | } |
duke@435 | 230 | if (++_yielded_workers + finished_workers() == active_workers()) { |
duke@435 | 231 | yielding_task()->set_status(YIELDED); |
duke@435 | 232 | monitor()->notify_all(); |
duke@435 | 233 | } else { |
duke@435 | 234 | yielding_task()->set_status(YIELDING); |
duke@435 | 235 | } |
duke@435 | 236 | |
duke@435 | 237 | while (true) { |
duke@435 | 238 | switch (yielding_task()->status()) { |
duke@435 | 239 | case YIELDING: |
duke@435 | 240 | case YIELDED: { |
duke@435 | 241 | monitor()->wait(Mutex::_no_safepoint_check_flag); |
duke@435 | 242 | break; // from switch |
duke@435 | 243 | } |
duke@435 | 244 | case ACTIVE: |
duke@435 | 245 | case ABORTING: |
duke@435 | 246 | case COMPLETING: { |
duke@435 | 247 | assert(_yielded_workers > 0, "Else why am i here?"); |
duke@435 | 248 | _yielded_workers--; |
duke@435 | 249 | return; |
duke@435 | 250 | } |
duke@435 | 251 | case INACTIVE: |
duke@435 | 252 | case ABORTED: |
duke@435 | 253 | case COMPLETED: |
duke@435 | 254 | default: { |
duke@435 | 255 | ShouldNotReachHere(); |
duke@435 | 256 | } |
duke@435 | 257 | } |
duke@435 | 258 | } |
duke@435 | 259 | // Only return is from inside switch statement above |
duke@435 | 260 | ShouldNotReachHere(); |
duke@435 | 261 | } |
duke@435 | 262 | |
duke@435 | 263 | void YieldingFlexibleWorkGang::abort() { |
duke@435 | 264 | assert(task() != NULL, "Inconsistency; should have task binding"); |
duke@435 | 265 | MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag); |
duke@435 | 266 | assert(yielded_workers() < active_workers(), "Consistency check"); |
duke@435 | 267 | #ifndef PRODUCT |
duke@435 | 268 | switch (yielding_task()->status()) { |
duke@435 | 269 | // allowed states |
duke@435 | 270 | case ACTIVE: |
duke@435 | 271 | case ABORTING: |
duke@435 | 272 | case COMPLETING: |
duke@435 | 273 | case YIELDING: |
duke@435 | 274 | break; |
duke@435 | 275 | // not allowed states |
duke@435 | 276 | case INACTIVE: |
duke@435 | 277 | case ABORTED: |
duke@435 | 278 | case COMPLETED: |
duke@435 | 279 | case YIELDED: |
duke@435 | 280 | default: |
duke@435 | 281 | ShouldNotReachHere(); |
duke@435 | 282 | } |
duke@435 | 283 | #endif // !PRODUCT |
duke@435 | 284 | Status prev_status = yielding_task()->status(); |
duke@435 | 285 | yielding_task()->set_status(ABORTING); |
duke@435 | 286 | if (prev_status == YIELDING) { |
duke@435 | 287 | assert(yielded_workers() > 0, "Inconsistency"); |
duke@435 | 288 | // At least one thread has yielded, wake it up |
duke@435 | 289 | // so it can go back to waiting stations ASAP. |
duke@435 | 290 | monitor()->notify_all(); |
duke@435 | 291 | } |
duke@435 | 292 | } |
duke@435 | 293 | |
duke@435 | 294 | /////////////////////////////// |
duke@435 | 295 | // YieldingFlexibleGangTask |
duke@435 | 296 | /////////////////////////////// |
duke@435 | 297 | void YieldingFlexibleGangTask::yield() { |
duke@435 | 298 | assert(gang() != NULL, "No gang to signal"); |
duke@435 | 299 | gang()->yield(); |
duke@435 | 300 | } |
duke@435 | 301 | |
duke@435 | 302 | void YieldingFlexibleGangTask::abort() { |
duke@435 | 303 | assert(gang() != NULL, "No gang to signal"); |
duke@435 | 304 | gang()->abort(); |
duke@435 | 305 | } |
duke@435 | 306 | |
duke@435 | 307 | /////////////////////////////// |
duke@435 | 308 | // YieldingFlexibleGangWorker |
duke@435 | 309 | /////////////////////////////// |
duke@435 | 310 | void YieldingFlexibleGangWorker::loop() { |
duke@435 | 311 | int previous_sequence_number = 0; |
duke@435 | 312 | Monitor* gang_monitor = gang()->monitor(); |
duke@435 | 313 | MutexLockerEx ml(gang_monitor, Mutex::_no_safepoint_check_flag); |
duke@435 | 314 | WorkData data; |
duke@435 | 315 | int id; |
duke@435 | 316 | while (true) { |
duke@435 | 317 | // Check if there is work to do or if we have been asked |
duke@435 | 318 | // to terminate |
duke@435 | 319 | gang()->internal_worker_poll(&data); |
duke@435 | 320 | if (data.terminate()) { |
duke@435 | 321 | // We have been asked to terminate. |
duke@435 | 322 | assert(gang()->task() == NULL, "No task binding"); |
duke@435 | 323 | // set_status(TERMINATED); |
duke@435 | 324 | return; |
duke@435 | 325 | } else if (data.task() != NULL && |
duke@435 | 326 | data.sequence_number() != previous_sequence_number) { |
duke@435 | 327 | // There is work to be done. |
duke@435 | 328 | // First check if we need to become active or if there |
duke@435 | 329 | // are already the requisite number of workers |
duke@435 | 330 | if (gang()->started_workers() == yf_gang()->active_workers()) { |
duke@435 | 331 | // There are already enough workers, we do not need to |
duke@435 | 332 | // to run; fall through and wait on monitor. |
duke@435 | 333 | } else { |
duke@435 | 334 | // We need to pitch in and do the work. |
duke@435 | 335 | assert(gang()->started_workers() < yf_gang()->active_workers(), |
duke@435 | 336 | "Unexpected state"); |
duke@435 | 337 | id = gang()->started_workers(); |
duke@435 | 338 | gang()->internal_note_start(); |
duke@435 | 339 | // Now, release the gang mutex and do the work. |
duke@435 | 340 | { |
duke@435 | 341 | MutexUnlockerEx mul(gang_monitor, Mutex::_no_safepoint_check_flag); |
duke@435 | 342 | data.task()->work(id); // This might include yielding |
duke@435 | 343 | } |
duke@435 | 344 | // Reacquire monitor and note completion of this worker |
duke@435 | 345 | gang()->internal_note_finish(); |
duke@435 | 346 | // Update status of task based on whether all workers have |
duke@435 | 347 | // finished or some have yielded |
duke@435 | 348 | assert(data.task() == gang()->task(), "Confused task binding"); |
duke@435 | 349 | if (gang()->finished_workers() == yf_gang()->active_workers()) { |
duke@435 | 350 | switch (data.yf_task()->status()) { |
duke@435 | 351 | case ABORTING: { |
duke@435 | 352 | data.yf_task()->set_status(ABORTED); |
duke@435 | 353 | break; |
duke@435 | 354 | } |
duke@435 | 355 | case ACTIVE: |
duke@435 | 356 | case COMPLETING: { |
duke@435 | 357 | data.yf_task()->set_status(COMPLETED); |
duke@435 | 358 | break; |
duke@435 | 359 | } |
duke@435 | 360 | default: |
duke@435 | 361 | ShouldNotReachHere(); |
duke@435 | 362 | } |
duke@435 | 363 | gang_monitor->notify_all(); // Notify overseer |
duke@435 | 364 | } else { // at least one worker is still working or yielded |
duke@435 | 365 | assert(gang()->finished_workers() < yf_gang()->active_workers(), |
duke@435 | 366 | "Counts inconsistent"); |
duke@435 | 367 | switch (data.yf_task()->status()) { |
duke@435 | 368 | case ACTIVE: { |
duke@435 | 369 | // first, but not only thread to complete |
duke@435 | 370 | data.yf_task()->set_status(COMPLETING); |
duke@435 | 371 | break; |
duke@435 | 372 | } |
duke@435 | 373 | case YIELDING: { |
duke@435 | 374 | if (gang()->finished_workers() + yf_gang()->yielded_workers() |
duke@435 | 375 | == yf_gang()->active_workers()) { |
duke@435 | 376 | data.yf_task()->set_status(YIELDED); |
duke@435 | 377 | gang_monitor->notify_all(); // notify overseer |
duke@435 | 378 | } |
duke@435 | 379 | break; |
duke@435 | 380 | } |
duke@435 | 381 | case ABORTING: |
duke@435 | 382 | case COMPLETING: { |
duke@435 | 383 | break; // nothing to do |
duke@435 | 384 | } |
duke@435 | 385 | default: // everything else: INACTIVE, YIELDED, ABORTED, COMPLETED |
duke@435 | 386 | ShouldNotReachHere(); |
duke@435 | 387 | } |
duke@435 | 388 | } |
duke@435 | 389 | } |
duke@435 | 390 | } |
duke@435 | 391 | // Remember the sequence number |
duke@435 | 392 | previous_sequence_number = data.sequence_number(); |
duke@435 | 393 | // Wait for more work |
duke@435 | 394 | gang_monitor->wait(Mutex::_no_safepoint_check_flag); |
duke@435 | 395 | } |
duke@435 | 396 | } |