001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.mmtk.plan;
014
015 import org.mmtk.utility.Constants;
016 import org.mmtk.utility.Log;
017 import org.mmtk.utility.options.Options;
018 import org.mmtk.utility.statistics.Timer;
019 import org.mmtk.vm.Collection;
020 import org.mmtk.vm.VM;
021
022 import org.vmmagic.pragma.*;
023
024 /**
025 * A garbage collection proceeds as a sequence of phases. Each
026 * phase is either simple (singular) or complex (an array).
027 *
028 * The context an individual phase executes in may be global, mutator,
029 * or collector.
030 *
031 * Phases are executed within a stack and all synchronization between
032 * parallel GC threads is managed from within this class.
033 *
034 * @see CollectorContext#collectionPhase
035 * @see MutatorContext#collectionPhase
036 * @see Plan#collectionPhase
037 */
038 @Uninterruptible
039 public abstract class Phase implements Constants {
040 /***********************************************************************
041 *
042 * Phase allocation and storage.
043 */
044
045 /** The maximum number of phases */
046 private static final int MAX_PHASES = 64;
047 /** The array of phase instances. Zero is unused. */
048 private static final Phase[] phases = new Phase[MAX_PHASES];
049 /** The id to be allocated for the next phase */
050 private static short nextPhaseId = 1;
051
052 /** Run the phase globally. */
053 protected static final short SCHEDULE_GLOBAL = 1;
054 /** Run the phase on collectors. */
055 protected static final short SCHEDULE_COLLECTOR = 2;
056 /** Run the phase on mutators. */
057 protected static final short SCHEDULE_MUTATOR = 3;
058 /** Don't run this phase. */
059 protected static final short SCHEDULE_PLACEHOLDER = 100;
060 /** This is a complex phase. */
061 protected static final short SCHEDULE_COMPLEX = 101;
062
063 /**
064 * Retrieve a phase by the unique phase identifier.
065 *
066 * @param id The phase identifier.
067 * @return The Phase instance.
068 */
069 public static Phase getPhase(short id) {
070 if (VM.VERIFY_ASSERTIONS) {
071 VM.assertions._assert(id < nextPhaseId, "Phase ID unknown");
072 VM.assertions._assert(phases[id] != null, "Uninitialised phase");
073 }
074 return phases[id];
075 }
076
077 /** Get the phase id component of an encoded phase */
078 protected static short getPhaseId(int scheduledPhase) {
079 short phaseId = (short)(scheduledPhase & 0x0000FFFF);
080 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(phaseId > 0);
081 return phaseId;
082 }
083
084 /**
085 * @param phaseId The unique phase identifier.
086 * @return The name of the phase.
087 */
088 public static String getName(short phaseId) {
089 return phases[phaseId].name;
090 }
091
092 /** Get the ordering component of an encoded phase */
093 protected static short getSchedule(int scheduledPhase) {
094 short ordering = (short)((scheduledPhase >> 16) & 0x0000FFFF);
095 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(ordering > 0);
096 return ordering;
097 }
098
099 /** Get the ordering component of an encoded phase */
100 protected static String getScheduleName(short ordering) {
101 switch (ordering) {
102 case SCHEDULE_GLOBAL: return "Global";
103 case SCHEDULE_COLLECTOR: return "Collector";
104 case SCHEDULE_MUTATOR: return "Mutator";
105 case SCHEDULE_PLACEHOLDER: return "Placeholder";
106 case SCHEDULE_COMPLEX: return "Complex";
107 default: return "UNKNOWN!";
108 }
109 }
110
111 /**
112 * Construct a phase.
113 *
114 * @param name Display name of the phase
115 */
116 @Interruptible
117 public static short createSimple(String name) {
118 return new SimplePhase(name).getId();
119 }
120
121 /**
122 * Construct a phase, re-using a specified timer.
123 *
124 * @param name Display name of the phase
125 */
126 @Interruptible
127 public static short createSimple(String name, Timer timer) {
128 return new SimplePhase(name, timer).getId();
129 }
130
131 /**
132 * Construct a complex phase.
133 *
134 * @param name Display name of the phase
135 * @param scheduledPhases The phases in this complex phase.
136 */
137 @Interruptible
138 public static short createComplex(String name,int... scheduledPhases) {
139 return new ComplexPhase(name, scheduledPhases).getId();
140 }
141
142 /**
143 * Construct a complex phase, re-using a specified timer.
144 *
145 * @param name Display name of the phase
146 * @param timer Timer for this phase to contribute to
147 * @param scheduledPhases The phases in this complex phase.
148 */
149 @Interruptible
150 public static short createComplex(String name, Timer timer, int... scheduledPhases) {
151 return new ComplexPhase(name, timer, scheduledPhases).getId();
152 }
153
154 /**
155 * Take the passed phase and return an encoded phase to
156 * run that phase as a complex phase.
157 *
158 * @param phaseId The phase to run as complex
159 * @return The encoded phase value.
160 */
161 public static int scheduleComplex(short phaseId) {
162 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Phase.getPhase(phaseId) instanceof ComplexPhase);
163 return (SCHEDULE_COMPLEX << 16) + phaseId;
164 }
165
166 /**
167 * Take the passed phase and return an encoded phase to
168 * run that phase in a global context;
169 *
170 * @param phaseId The phase to run globally
171 * @return The encoded phase value.
172 */
173 public static int scheduleGlobal(short phaseId) {
174 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Phase.getPhase(phaseId) instanceof SimplePhase);
175 return (SCHEDULE_GLOBAL << 16) + phaseId;
176 }
177
178 /**
179 * Take the passed phase and return an encoded phase to
180 * run that phase in a collector context;
181 *
182 * @param phaseId The phase to run on collectors
183 * @return The encoded phase value.
184 */
185 public static int scheduleCollector(short phaseId) {
186 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Phase.getPhase(phaseId) instanceof SimplePhase);
187 return (SCHEDULE_COLLECTOR << 16) + phaseId;
188 }
189
190 /**
191 * Take the passed phase and return an encoded phase to
192 * run that phase in a mutator context;
193 *
194 * @param phaseId The phase to run on mutators
195 * @return The encoded phase value.
196 */
197 public static int scheduleMutator(short phaseId) {
198 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Phase.getPhase(phaseId) instanceof SimplePhase);
199 return (SCHEDULE_MUTATOR << 16) + phaseId;
200 }
201
202 /**
203 * Take the passed phase and return an encoded phase to
204 * run that phase in a mutator context;
205 *
206 * @param phaseId The phase to run on mutators
207 * @return The encoded phase value.
208 */
209 public static int schedulePlaceholder(short phaseId) {
210 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Phase.getPhase(phaseId) instanceof SimplePhase);
211 return (SCHEDULE_PLACEHOLDER << 16) + phaseId;
212 }
213
214 /***********************************************************************
215 *
216 * Phase instance fields/methods.
217 */
218
219 /**
220 * The unique phase identifier.
221 */
222 protected final short id;
223
224 /**
225 * The name of the phase.
226 */
227 protected final String name;
228
229 /**
230 * The Timer that is started and stopped around the execution of this
231 * phase.
232 */
233 protected final Timer timer;
234
235 /**
236 * Create a new Phase. This involves creating a corresponding Timer
237 * instance, allocating a unique identifier, and registering the
238 * Phase.
239 *
240 * @param name The name for the phase.
241 */
242 protected Phase(String name) {
243 this(name, new Timer(name, false, true));
244 }
245
246 /**
247 * Create a new phase. This involves setting the corresponding Timer
248 * instance, allocating a unique identifier, and registering the Phase.
249 *
250 * @param name The name of the phase.
251 * @param timer The timer, or null if this is an untimed phase.
252 */
253 protected Phase(String name, Timer timer) {
254 this.name = name;
255 this.timer = timer;
256 this.id = nextPhaseId++;
257 phases[this.id] = this;
258 }
259
260 /**
261 * @return The unique identifier for this phase.
262 */
263 public final short getId() {
264 return this.id;
265 }
266
267 /**
268 * Display a phase for debugging purposes.
269 */
270 protected abstract void logPhase();
271
272 /***********************************************************************
273 *
274 * Phase stack
275 */
276
277 /** The maximum stack depth for the phase stack. */
278 private static final int MAX_PHASE_STACK_DEPTH = MAX_PHASES;
279
280 /** Stores the current sub phase for a complex phase. Each entry corresponds to a phase stack entry */
281 private static int[] complexPhaseCursor = new int[MAX_PHASE_STACK_DEPTH];
282
283 /** The phase stack. Stores the current nesting of phases */
284 private static int[] phaseStack = new int[MAX_PHASE_STACK_DEPTH];
285
286 /** The current stack pointer */
287 private static int phaseStackPointer = -1;
288
289 /**
290 * The current even (0 mod 2) scheduled phase.
291 * As we only sync at the end of a phase we need this to ensure that
292 * the primary thread setting the phase does not race with the other
293 * threads reading it.
294 */
295 private static int evenScheduledPhase;
296
297 /**
298 * The current odd (1 mod 2) scheduled phase.
299 * As we only sync at the end of a phase we need this to ensure that
300 * the primary thread setting the phase does not race with the other
301 * threads reading it.
302 */
303 private static int oddScheduledPhase;
304
305 /**
306 * Do we need to add a sync point to reset the mutator count. This
307 * is necessary for consecutive mutator phases and unneccessary
308 * otherwise. Again we separate in even and odd to ensure that there
309 * is no race between the primary thread setting and the helper
310 * threads reading.
311 */
312 private static boolean evenMutatorResetRendezvous;
313
314 /**
315 * Do we need to add a sync point to reset the mutator count. This
316 * is necessary for consecutive mutator phases and unneccessary
317 * otherwise. Again we separate in even and odd to ensure that there
318 * is no race between the primary thread setting and the helper
319 * threads reading.
320 */
321 private static boolean oddMutatorResetRendezvous;
322
323 /**
324 * The complex phase whose timer should be started after the next
325 * rendezvous. We can not start the timer at the point we determine
326 * the next complex phase as we determine the next phase at the
327 * end of the previous phase before the sync point.
328 */
329 private static short startComplexTimer;
330
331 /**
332 * The complex phase whose timer should be stopped after the next
333 * rendezvous. We can not start the timer at the point we determine
334 * the next complex phase as we determine the next phase at the
335 * end of the previous phase before the sync point.
336 */
337 private static short stopComplexTimer;
338
339 /**
340 * Place a phase on the phase stack and begin processing.
341 *
342 * @param scheduledPhase The phase to execute
343 * @return True if the phase stack is exhausted.
344 */
345 public static boolean beginNewPhaseStack(int scheduledPhase) {
346 int order = VM.collection.rendezvous(1001);
347
348 if (order == 1) {
349 pushScheduledPhase(scheduledPhase);
350 }
351 return processPhaseStack(false);
352 }
353
354 /**
355 * Process the phase stack. This method is called by multiple threads.
356 */
357 private static boolean processPhaseStack(boolean resume) {
358 int order = VM.collection.rendezvous(1001);
359 final boolean primary = order == 1;
360
361 boolean log = Options.verbose.getValue() >= 6;
362 boolean logDetails = Options.verbose.getValue() >= 7;
363
364 if (primary && resume) {
365 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!Phase.isPhaseStackEmpty());
366 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!Plan.gcInProgress());
367 Plan.setGCStatus(Plan.GC_PROPER);
368 }
369
370 /* In order to reduce the need for synchronization, we keep an odd or even
371 * counter for the number of phases processed. As each phase has a single
372 * rendezvous it is only possible to be out by one so the odd or even counter
373 * protects us. */
374 boolean isEvenPhase = true;
375
376 if (primary) {
377 /* First phase will be even, so we say we are odd here so that the next phase set is even*/
378 setNextPhase(false, getNextPhase(), false);
379 }
380
381 /* Make sure everyone sees the first phase */
382 VM.collection.rendezvous(1002);
383
384 /* Global and Collector instances used in phases */
385 Plan plan = VM.activePlan.global();
386 CollectorContext collector = VM.activePlan.collector();
387
388 /* The main phase execution loop */
389 int scheduledPhase;
390 while((scheduledPhase = getCurrentPhase(isEvenPhase)) > 0) {
391 short schedule = getSchedule(scheduledPhase);
392 short phaseId = getPhaseId(scheduledPhase);
393 Phase p = getPhase(phaseId);
394
395 /* Start the timer(s) */
396 if (primary) {
397 if (resume) {
398 resumeComplexTimers();
399 }
400 if (p.timer != null) p.timer.start();
401 if (startComplexTimer > 0) {
402 Phase.getPhase(startComplexTimer).timer.start();
403 startComplexTimer = 0;
404 }
405 }
406
407 if (log) {
408 Log.write("Execute ");
409 p.logPhase();
410 }
411
412 /* Execute a single simple scheduled phase */
413 switch (schedule) {
414 /* Global phase */
415 case SCHEDULE_GLOBAL: {
416 if (logDetails) Log.writeln(" as Global...");
417 if (primary) {
418 if (VM.DEBUG) VM.debugging.globalPhase(phaseId,true);
419 plan.collectionPhase(phaseId);
420 if (VM.DEBUG) VM.debugging.globalPhase(phaseId,false);
421 }
422 break;
423 }
424
425 /* Collector phase */
426 case SCHEDULE_COLLECTOR: {
427 if (logDetails) Log.writeln(" as Collector...");
428 if (VM.DEBUG) VM.debugging.collectorPhase(phaseId,order,true);
429 collector.collectionPhase(phaseId, primary);
430 if (VM.DEBUG) VM.debugging.collectorPhase(phaseId,order,false);
431 break;
432 }
433
434 /* Mutator phase */
435 case SCHEDULE_MUTATOR: {
436 if (logDetails) Log.writeln(" as Mutator...");
437 /* Iterate through all mutator contexts */
438 MutatorContext mutator;
439 while ((mutator = VM.activePlan.getNextMutator()) != null) {
440 if (VM.DEBUG) VM.debugging.mutatorPhase(phaseId,mutator.getId(),true);
441 mutator.collectionPhase(phaseId, primary);
442 if (VM.DEBUG) VM.debugging.mutatorPhase(phaseId,mutator.getId(),false);
443 }
444 break;
445 }
446
447 default: {
448 /* getNextPhase has done the wrong thing */
449 VM.assertions.fail("Invalid schedule in Phase.processPhaseStack");
450 break;
451 }
452 }
453
454 if (primary) {
455 /* Set the next phase by processing the stack */
456 int next = getNextPhase();
457 boolean needsResetRendezvous = (next > 0) && (schedule == SCHEDULE_MUTATOR && getSchedule(next) == SCHEDULE_MUTATOR);
458 setNextPhase(isEvenPhase, next, needsResetRendezvous);
459 }
460
461 /* Sync point after execution of a phase */
462 VM.collection.rendezvous(1004);
463
464 /* Mutator phase reset */
465 if (primary && schedule == SCHEDULE_MUTATOR) {
466 VM.activePlan.resetMutatorIterator();
467 }
468
469 /* At this point, in the case of consecutive phases with mutator
470 * scheduling, we have to double-synchronize to ensure all
471 * collector threads see the reset mutator counter. */
472 if (needsMutatorResetRendezvous(isEvenPhase)) {
473 VM.collection.rendezvous(1005);
474 }
475
476 /* Stop the timer(s) */
477 if (primary) {
478 if (p.timer != null) p.timer.stop();
479 if (stopComplexTimer > 0) {
480 Phase.getPhase(stopComplexTimer).timer.stop();
481 stopComplexTimer = 0;
482 }
483 }
484
485 /* Flip the even / odd phase sense */
486 isEvenPhase = !isEvenPhase;
487 resume = false;
488 }
489
490 /* Phase stack exhausted so we return true */
491 return true;
492 }
493
494 /**
495 * Get the next phase.
496 */
497 private static int getCurrentPhase(boolean isEvenPhase) {
498 return isEvenPhase ? evenScheduledPhase : oddScheduledPhase;
499 }
500
501 /**
502 * Do we need a mutator reset rendezvous in this phase?
503 */
504 private static boolean needsMutatorResetRendezvous(boolean isEvenPhase) {
505 return isEvenPhase ? evenMutatorResetRendezvous : oddMutatorResetRendezvous;
506 }
507 /**
508 * Set the next phase. If we are in an even phase the next phase is odd.
509 */
510 private static void setNextPhase(boolean isEvenPhase, int scheduledPhase, boolean needsResetRendezvous) {
511 if (isEvenPhase) {
512 oddScheduledPhase = scheduledPhase;
513 evenMutatorResetRendezvous = needsResetRendezvous;
514 } else {
515 evenScheduledPhase = scheduledPhase;
516 oddMutatorResetRendezvous = needsResetRendezvous;
517 }
518 }
519
520 /**
521 * Pull the next scheduled phase off the stack. This may involve
522 * processing several complex phases and skipping placeholders, etc.
523 *
524 * @return The next phase to run, or -1 if no phases are left.
525 */
526 private static int getNextPhase() {
527 boolean allowConcurrentPhase = Plan.collectionTrigger == Collection.INTERNAL_PHASE_GC_TRIGGER;
528
529 while (phaseStackPointer >= 0) {
530 int scheduledPhase = peekScheduledPhase();
531 short schedule = getSchedule(scheduledPhase);
532 short phaseId = getPhaseId(scheduledPhase);
533
534 switch(schedule) {
535 case SCHEDULE_PLACEHOLDER: {
536 /* Placeholders are ignored and we continue looking */
537 popScheduledPhase();
538 continue;
539 }
540
541 case SCHEDULE_GLOBAL:
542 case SCHEDULE_COLLECTOR:
543 case SCHEDULE_MUTATOR: {
544 /* Simple phases are just popped off the stack and executed */
545 popScheduledPhase();
546 return scheduledPhase;
547 }
548
549 case SCHEDULE_COMPLEX: {
550 /* A complex phase may either be a newly pushed complex phase,
551 * or a complex phase we are in the process of executing in
552 * which case we move to the next subphase. */
553 ComplexPhase p = (ComplexPhase)getPhase(phaseId);
554 int cursor = incrementComplexPhaseCursor();
555 if (cursor == 0 && p.timer != null) {
556 /* Tell the primary thread to start the timer after the next sync. */
557 startComplexTimer = phaseId;
558 }
559 if (cursor < p.count()) {
560 /* There are more entries, we push the next one and continue */
561 pushScheduledPhase(p.get(cursor));
562 continue;
563 }
564
565 /* We have finished this complex phase */
566 popScheduledPhase();
567 if (p.timer != null) {
568 /* Tell the primary thread to stop the timer after the next sync. */
569 stopComplexTimer = phaseId;
570 }
571 continue;
572 }
573
574 default: {
575 VM.assertions.fail("Invalid phase type encountered");
576 }
577 }
578 }
579 return -1;
580 }
581
582 /**
583 * Pause all of the timers for the complex phases sitting in the stack.
584 */
585 private static void pauseComplexTimers() {
586 for(int i=phaseStackPointer; i >=0; i--) {
587 Phase p = getPhase(getPhaseId(phaseStack[i]));
588 if (p.timer != null) p.timer.stop();
589 }
590 }
591
592 /**
593 * Resume all of the timers for the complex phases sitting in the stack.
594 */
595 private static void resumeComplexTimers() {
596 for(int i=phaseStackPointer; i >=0; i--) {
597 Phase p = getPhase(getPhaseId(phaseStack[i]));
598 if (p.timer != null) p.timer.start();
599 }
600 }
601
602 /**
603 * Return true if phase stack is empty, false otherwise.
604 *
605 * @return true if phase stack is empty, false otherwise.
606 */
607 @Inline
608 public static boolean isPhaseStackEmpty() {
609 return phaseStackPointer < 0;
610 }
611
612 /**
613 * Clears the scheduled phase stack.
614 */
615 @Inline
616 public static void resetPhaseStack() {
617 phaseStackPointer = -1;
618 }
619
620 /**
621 * Push a scheduled phase onto the top of the work stack.
622 *
623 * @param scheduledPhase The scheduled phase.
624 */
625 @Inline
626 public static void pushScheduledPhase(int scheduledPhase) {
627 phaseStack[++phaseStackPointer] = scheduledPhase;
628 complexPhaseCursor[phaseStackPointer] = 0;
629 }
630
631 /**
632 * Increment the cursor associated with the current phase
633 * stack entry. This is used to remember the current sub phase
634 * when executing a complex phase.
635 *
636 * @return The old value of the cursor.
637 */
638 @Inline
639 private static int incrementComplexPhaseCursor() {
640 return complexPhaseCursor[phaseStackPointer]++;
641 }
642
643 /**
644 * Pop off the scheduled phase at the top of the work stack.
645 */
646 @Inline
647 private static int popScheduledPhase() {
648 return phaseStack[phaseStackPointer--];
649 }
650
651 /**
652 * Peek the scheduled phase at the top of the work stack.
653 */
654 @Inline
655 private static int peekScheduledPhase() {
656 return phaseStack[phaseStackPointer];
657 }
658 }