1 /*
  2  * Copyright (c) 2018, 2019, 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.  Oracle designates this
  8  * particular file as subject to the "Classpath" exception as provided
  9  * by Oracle in the LICENSE file that accompanied this code.
 10  *
 11  * This code is distributed in the hope that it will be useful, but WITHOUT
 12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 14  * version 2 for more details (a copy is included in the LICENSE file that
 15  * accompanied this code).
 16  *
 17  * You should have received a copy of the GNU General Public License version
 18  * 2 along with this work; if not, write to the Free Software Foundation,
 19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 20  *
 21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 22  * or visit www.oracle.com if you need additional information or have any
 23  * questions.
 24  */
 25 
 26 package jdk.internal.vm;
 27 
 28 import jdk.internal.vm.annotation.DontInline;
 29 import jdk.internal.vm.annotation.IntrinsicCandidate;
 30 import sun.security.action.GetPropertyAction;
 31 
 32 import java.lang.invoke.MethodHandles;
 33 import java.lang.invoke.VarHandle;
 34 import java.util.Arrays;
 35 import java.util.EnumSet;
 36 import java.util.Map;
 37 import java.util.Objects;
 38 import java.util.Set;
 39 import java.util.concurrent.ConcurrentHashMap;
 40 import java.util.function.Supplier;
 41 import jdk.internal.access.JavaLangAccess;
 42 import jdk.internal.access.SharedSecrets;
 43 
 44 /**
 45  * TBD
 46  */
 47 public class Continuation {
 48     private static final JavaLangAccess JLA = SharedSecrets.getJavaLangAccess();
 49     static {
 50         StackChunk.init(); // ensure StackChunk class is initialized
 51     }
 52 
 53     // private static final WhiteBox WB = sun.hotspot.WhiteBox.WhiteBox.getWhiteBox();
 54     private static final jdk.internal.misc.Unsafe unsafe = jdk.internal.misc.Unsafe.getUnsafe();
 55 
 56     private static final boolean TRACE = isEmptyOrTrue("jdk.internal.vm.Continuation.trace");
 57     private static final boolean DEBUG = TRACE | isEmptyOrTrue("jdk.internal.vm.Continuation.debug");
 58 
 59     private static final VarHandle MOUNTED;
 60 
 61     /** Reason for pinning */
 62     public enum Pinned { 
 63         /** Native frame on stack */ NATIVE,
 64         /** Monitor held */          MONITOR,
 65         /** In critical section */   CRITICAL_SECTION }
 66     /** Preemption attempt result */
 67     public enum PreemptStatus { 
 68         /** Success */                                                      SUCCESS(null), 
 69         /** Permanent failure */                                            PERM_FAIL_UNSUPPORTED(null), 
 70         /** Permanent failure: continuation alreay yielding */              PERM_FAIL_YIELDING(null), 
 71         /** Permanent failure: continuation not mounted on the thread */    PERM_FAIL_NOT_MOUNTED(null), 
 72         /** Transient failure: continuation pinned due to a held CS */      TRANSIENT_FAIL_PINNED_CRITICAL_SECTION(Pinned.CRITICAL_SECTION),
 73         /** Transient failure: continuation pinned due to native frame */   TRANSIENT_FAIL_PINNED_NATIVE(Pinned.NATIVE), 
 74         /** Transient failure: continuation pinned due to a held monitor */ TRANSIENT_FAIL_PINNED_MONITOR(Pinned.MONITOR);
 75 
 76         final Pinned pinned;
 77         private PreemptStatus(Pinned reason) { this.pinned = reason; }
 78         /** 
 79          * TBD
 80          * @return TBD
 81          **/
 82         public Pinned pinned() { return pinned; }
 83     }
 84 
 85     private static PreemptStatus preemptStatus(int status) {
 86         switch (status) {
 87             case -5: return PreemptStatus.PERM_FAIL_UNSUPPORTED;
 88             case  0: return PreemptStatus.SUCCESS;
 89             case -1: return PreemptStatus.PERM_FAIL_NOT_MOUNTED;
 90             case -2: return PreemptStatus.PERM_FAIL_YIELDING;
 91             case  2: return PreemptStatus.TRANSIENT_FAIL_PINNED_CRITICAL_SECTION;
 92             case  3: return PreemptStatus.TRANSIENT_FAIL_PINNED_NATIVE;
 93             case  4: return PreemptStatus.TRANSIENT_FAIL_PINNED_MONITOR;
 94             default: throw new AssertionError("Unknown status: " + status);
 95         }
 96     }
 97 
 98     private static Pinned pinnedReason(int reason) {
 99         switch (reason) {
100             case 2: return Pinned.CRITICAL_SECTION;
101             case 3: return Pinned.NATIVE;
102             case 4: return Pinned.MONITOR;
103             default:
104                 throw new AssertionError("Unknown pinned reason: " + reason);
105         }
106     }
107 
108     private static Thread currentCarrierThread() {
109         return JLA.currentCarrierThread();
110     }
111 
112     static {
113         try {
114             registerNatives();
115 
116             MethodHandles.Lookup l = MethodHandles.lookup();
117             MOUNTED = l.findVarHandle(Continuation.class, "mounted", boolean.class);
118         } catch (Exception e) {
119             throw new InternalError(e);
120         }
121     }
122 
123     private Runnable target;
124 
125     /* While the native JVM code is aware that every continuation has a scope, it is, for the most part,
126      * oblivious to the continuation hierarchy. The only time this hierarchy is traversed in native code
127      * is when a hierarchy of continuations is mounted on the native stack.
128      */
129     private final ContinuationScope scope;
130     private Continuation parent; // null for native stack
131     private Continuation child; // non-null when we're yielded in a child continuation
132 
133     private StackChunk tail;
134 
135     private boolean done;
136     private volatile boolean mounted = false;
137     private Object yieldInfo;
138     private boolean preempted;
139 
140     private short cs; // critical section semaphore
141 
142     private boolean reset = false; // perftest only
143 
144     private Object[] scopeLocalCache;
145 
146     // private long[] nmethods = null; // grows up
147     // private int numNmethods = 0;
148 
149     /**
150      * TBD
151      * @param scope TBD
152      * @param target TBD
153      */
154     public Continuation(ContinuationScope scope, Runnable target) {
155         this.scope = scope;
156         this.target = target;
157     }
158 
159     @Override
160     public String toString() {
161         return super.toString() + " scope: " + scope;
162     }
163 
164     public ContinuationScope getScope() {
165         return scope;
166     }
167 
168     public Continuation getParent() {
169         return parent;
170     }
171 
172     /**
173      * TBD
174      * @param scope TBD
175      * @return TBD
176      */
177     public static Continuation getCurrentContinuation(ContinuationScope scope) {
178         Continuation cont = JLA.getContinuation(currentCarrierThread());
179         while (cont != null && cont.scope != scope)
180             cont = cont.parent;
181         return cont;
182     }
183 
184     /**
185      * TBD
186      * @return TBD
187      */
188     public StackWalker stackWalker() {
189         return stackWalker(EnumSet.noneOf(StackWalker.Option.class));
190     }
191 
192     /**
193      * TBD
194      * @param option TBD
195      * @return TBD
196      */
197     public StackWalker stackWalker(StackWalker.Option option) {
198         return stackWalker(EnumSet.of(Objects.requireNonNull(option)));
199     }
200 
201     /**
202      * TBD
203      * @param options TBD
204      * @return TBD
205      */
206     public StackWalker stackWalker(Set<StackWalker.Option> options) {
207         return stackWalker(options, this.scope);
208     }
209 
210     /**
211      * TBD
212      * @param options TBD
213      * @param scope TBD
214      * @return TBD
215      */
216     public StackWalker stackWalker(Set<StackWalker.Option> options, ContinuationScope scope) {
217         // if (scope != null) {
218         //     // verify the given scope exists in this continuation
219         //     Continuation c;
220         //     for (c = innermost(); c != null; c = c.parent) {
221         //         if (c.scope == scope)
222         //             break;
223         //     }
224         //     if (c.scope != scope)
225         //         scope = this.scope; // throw new IllegalArgumentException("Continuation " + this + " not in scope " + scope); -- don't throw exception to have the same behavior as no continuation
226         // } else {
227         //     scope = this.scope;
228         // }
229         return JLA.newStackWalkerInstance(options, scope, innermost());
230     }
231 
232     /**
233      * TBD
234      * @return TBD
235      * @throws IllegalStateException if the continuation is mounted
236      */
237     public StackTraceElement[] getStackTrace() {
238         return stackWalker(StackWalker.Option.SHOW_REFLECT_FRAMES)
239             .walk(s -> s.map(StackWalker.StackFrame::toStackTraceElement)
240             .toArray(StackTraceElement[]::new));
241     }
242 
243     /// Support for StackWalker
244     public static <R> R wrapWalk(Continuation inner, ContinuationScope scope, Supplier<R> walk) {
245         try {
246             for (Continuation c = inner; c != null && c.scope != scope; c = c.parent)
247                 c.mount();
248 
249             // if (!inner.isStarted())
250             //     throw new IllegalStateException("Continuation not started");
251                 
252             return walk.get();
253         } finally {
254             for (Continuation c = inner; c != null && c.scope != scope; c = c.parent)
255                 c.unmount();
256         }
257     }
258 
259     private Continuation innermost() {
260         Continuation c = this;
261         while (c.child != null)
262             c = c.child;
263         return c;
264     }
265 
266     private void mount() {
267         if (!compareAndSetMounted(false, true))
268             throw new IllegalStateException("Mounted!!!!");
269         JLA.setScopeLocalCache(scopeLocalCache);
270     }
271 
272     private void unmount() {
273         scopeLocalCache = JLA.scopeLocalCache();
274         JLA.setScopeLocalCache(null);
275         setMounted(false);
276     }
277     
278     /**
279      * TBD
280      */
281     public final void run() {
282         while (true) {
283             if (TRACE) System.out.println("\n++++++++++++++++++++++++++++++");
284 
285             mount();
286 
287             if (done)
288                 throw new IllegalStateException("Continuation terminated");
289 
290             Thread t = currentCarrierThread();
291             if (parent != null) {
292                 if (parent != JLA.getContinuation(t))
293                     throw new IllegalStateException();
294             } else
295                 this.parent = JLA.getContinuation(t);
296             JLA.setContinuation(t, this);
297 
298             try {
299                 if (!isStarted()) { // is this the first run? (at this point we know !done)
300                     if (TRACE) System.out.println("ENTERING " + id());
301                     if (TRACE) System.out.println("start done: " + done);
302                     enterSpecial(this, false);
303                 } else {
304                     assert !isEmpty();
305                     if (TRACE) System.out.println("continue done: " + done);
306                     enterSpecial(this, true);
307                 }
308             } finally {
309                 fence();
310                 StackChunk c = tail;
311 
312                 try {
313                 if (TRACE) System.out.println("run (after): preemted: " + preempted);
314 
315                 assert isEmpty() == done : "empty: " + isEmpty() + " done: " + done + " cont: " + Integer.toHexString(System.identityHashCode(this));
316                 JLA.setContinuation(currentCarrierThread(), this.parent);
317                 if (parent != null)
318                     parent.child = null;
319 
320                 postYieldCleanup();
321 
322                 unmount();
323                 } catch (Throwable e) { e.printStackTrace(); System.exit(1); }
324             }
325             // we're now in the parent continuation
326 
327             assert yieldInfo == null || yieldInfo instanceof ContinuationScope;
328             if (yieldInfo == null || yieldInfo == scope) {
329                 this.parent = null;
330                 this.yieldInfo = null;
331                 return;
332             } else {
333                 parent.child = this;
334                 parent.yield0((ContinuationScope)yieldInfo, this);
335                 parent.child = null;
336             }
337         }
338     }
339 
340     private void postYieldCleanup() {
341         if (done) {
342             this.tail = null;
343         }
344     }
345 
346     private void finish() {
347         done = true;
348         // assert doneX;
349         // System.out.println("-- done!  " + id());
350         if (TRACE) System.out.println(">>>>>>>> DONE <<<<<<<<<<<<< " + id());
351         assert isEmpty();
352     }
353 
354     @IntrinsicCandidate
355     private static int doYield() { throw new Error("Intrinsic not installed"); };
356 
357     @IntrinsicCandidate
358     private native static void enterSpecial(Continuation c, boolean isContinue);
359 
360 
361     @DontInline
362     @IntrinsicCandidate
363     private static void enter(Continuation c, boolean isContinue) {
364       // This method runs in the "entry frame".
365       // A yield jumps to this method's caller as if returning from this method.
366       try {
367         c.enter0();
368       } finally {
369         c.finish();
370       }
371     }
372 
373     private void enter0() {
374       target.run();
375     }
376 
377     private boolean isStarted() {
378         return tail != null;
379     }
380 
381     private boolean isEmpty() {
382         for (StackChunk c = tail; c != null; c = c.parent()) {
383             if (!c.isEmpty())
384                 return false;
385         }
386         return true;
387     }
388 
389     /**
390      * TBD
391      * 
392      * @param scope The {@link ContinuationScope} to yield
393      * @return {@code true} for success; {@code false} for failure
394      * @throws IllegalStateException if not currently in the given {@code scope},
395      */
396     public static boolean yield(ContinuationScope scope) {
397         Continuation cont = JLA.getContinuation(currentCarrierThread());
398         Continuation c;
399         for (c = cont; c != null && c.scope != scope; c = c.parent)
400             ;
401         if (c == null)
402             throw new IllegalStateException("Not in scope " + scope);
403 
404         return cont.yield0(scope, null);
405     }
406 
407     private boolean yield0(ContinuationScope scope, Continuation child) {
408         if (TRACE) System.out.println(this + " yielding on scope " + scope + ". child: " + child);
409 
410         preempted = false;
411 
412         if (scope != this.scope)
413             this.yieldInfo = scope;
414         int res = doYield();
415         unsafe.storeFence(); // needed to prevent certain transformations by the compiler
416         
417         if (TRACE) System.out.println(this + " awake on scope " + scope + " child: " + child + " res: " + res + " yieldInfo: " + yieldInfo);
418 
419         try {
420         assert scope != this.scope || yieldInfo == null : "scope: " + scope + " this.scope: " + this.scope + " yieldInfo: " + yieldInfo + " res: " + res;
421         assert yieldInfo == null || scope == this.scope || yieldInfo instanceof Integer : "scope: " + scope + " this.scope: " + this.scope + " yieldInfo: " + yieldInfo + " res: " + res;
422 
423         if (child != null) { // TODO: ugly
424             if (res != 0) {
425                 child.yieldInfo = res;
426             } else if (yieldInfo != null) {
427                 assert yieldInfo instanceof Integer;
428                 child.yieldInfo = yieldInfo;
429             } else {
430                 child.yieldInfo = res;
431             }
432             this.yieldInfo = null;
433 
434             if (TRACE) System.out.println(this + " child.yieldInfo = " + child.yieldInfo);
435         } else {
436             if (res == 0 && yieldInfo != null) {
437                 res = (Integer)yieldInfo;
438             }
439             this.yieldInfo = null;
440 
441             if (res == 0)
442                 onContinue();
443             else
444                 onPinned0(res);
445 
446             if (TRACE) System.out.println(this + " res: " + res);
447         }
448         assert yieldInfo == null;
449 
450         return res == 0;
451         } catch (Throwable t) {
452             t.printStackTrace();
453             throw t;
454         }
455     }
456 
457     private void onPinned0(int reason) {
458         if (TRACE) System.out.println("PINNED " + this + " reason: " + reason);
459         onPinned(pinnedReason(reason));
460     }
461 
462     /**
463      * TBD
464      * @param reason TBD
465      */
466     protected void onPinned(Pinned reason) {
467         if (DEBUG)
468             System.out.println("PINNED! " + reason);
469         throw new IllegalStateException("Pinned: " + reason);
470     }
471 
472     /**
473      * TBD
474      */
475     protected void onContinue() {
476         if (TRACE)
477             System.out.println("On continue");
478     }
479 
480     /**
481      * TBD
482      * @return TBD
483      */
484     public boolean isDone() {
485         return done;
486     }
487 
488     /**
489      * TBD
490      * @return TBD
491      */
492     public boolean isPreempted() {
493         return preempted;
494     }
495 
496     /**
497      * Pins the current continuation (enters a critical section).
498      * This increments an internal semaphore that, when greater than 0, pins the continuation.
499      */
500     public static void pin() {
501         Continuation cont = JLA.getContinuation(currentCarrierThread());
502         if (cont != null) {
503             assert cont.cs >= 0;
504             if (cont.cs == Short.MAX_VALUE)
505                 throw new IllegalStateException("Too many pins");
506             cont.cs++;
507         }
508     }
509 
510     /**
511      * Unpins the current continuation (exits a critical section).
512      * This decrements an internal semaphore that, when equal 0, unpins the current continuation
513      * if pinne with {@link #pin()}.
514      */
515     public static void unpin() {
516         Continuation cont = JLA.getContinuation(currentCarrierThread());
517         if (cont != null) {
518             assert cont.cs >= 0;
519             if (cont.cs == 0)
520                 throw new IllegalStateException("Not pinned");
521             cont.cs--;
522         }
523     }
524 
525     /**
526      * Tests whether the given scope is pinned. 
527      * This method is slow.
528      * 
529      * @param scope the continuation scope
530      * @return {@code} true if we're in the give scope and are pinned; {@code false otherwise}
531      */
532     public static boolean isPinned(ContinuationScope scope) {
533         int res = isPinned0(scope);
534         return res != 0;
535     }
536 
537     static private native int isPinned0(ContinuationScope scope);
538 
539     private void clean() {
540         // if (!isStackEmpty())
541         //     clean0();
542     }
543 
544     private boolean fence() {
545         unsafe.storeFence(); // needed to prevent certain transformations by the compiler
546         return true;
547     }
548 
549     // /**
550     //  * TBD
551     //  */
552     // public void doneX() {
553     //     // System.out.println("DONEX");
554     //     this.doneX = true;
555     // }
556 
557 
558     /**
559      * temporary testing
560      */
561     public void something_something_1() {
562         this.done = false;
563 
564         setMounted(false);
565     }
566 
567     /**
568      * temporary testing
569      */
570     public void something_something_2() {
571         reset = true;
572     }
573 
574     /**
575      * temporary testing
576      */
577     public void something_something_3() {
578         this.done = false;
579     }
580 
581     // private void pushNmethod(long nmethod) {
582     //     if (nmethods == null) {
583     //         nmethods = new long[8];
584     //     } else {
585     //         if (numNmethods == nmethods.length) {
586     //             long[] newNmethods = new long[nmethods.length * 2];
587     //             System.arraycopy(nmethods, 0, newNmethods, 0, numNmethods);
588     //             this.nmethods = newNmethods;
589     //         }
590     //     }
591     //     nmethods[numNmethods++] = nmethod;
592     // }
593 
594     // private void popNmethod() {
595     //     numNmethods--;
596     // }
597 
598     private static Map<Long, Integer> liveNmethods = new ConcurrentHashMap<>();
599 
600     private void processNmethods(int before, int after) {
601 
602     }
603 
604     private boolean compareAndSetMounted(boolean expectedValue, boolean newValue) {
605        boolean res = MOUNTED.compareAndSet(this, expectedValue, newValue);
606     //    System.out.println("-- compareAndSetMounted:  ex: " + expectedValue + " -> " + newValue + " " + res + " " + id());
607        return res;
608      }
609 
610     private void setMounted(boolean newValue) {
611         // System.out.println("-- setMounted:  " + newValue + " " + id());
612         mounted = newValue;
613         // MOUNTED.setVolatile(this, newValue);
614     }
615 
616     private String id() {
617         return Integer.toHexString(System.identityHashCode(this)) + " [" + currentCarrierThread().getId() + "]";
618     }
619 
620     // private native void clean0();
621 
622     /**
623      * TBD
624      * Subclasses may throw an {@link UnsupportedOperationException}, but this does not prevent
625      * the continuation from being preempted on a parent scope.
626      * 
627      * @param thread TBD
628      * @return TBD
629      * @throws UnsupportedOperationException if this continuation does not support preemption
630      */
631     public PreemptStatus tryPreempt(Thread thread) {
632         PreemptStatus res = preemptStatus(tryForceYield0(thread));
633         if (res == PreemptStatus.PERM_FAIL_UNSUPPORTED) {
634             throw new UnsupportedOperationException("Thread-local handshakes disabled");
635         }
636         return res;
637     }
638 
639     private native int tryForceYield0(Thread thread);
640 
641     // native methods
642     private static native void registerNatives();
643 
644     private void dump() {
645         System.out.println("Continuation@" + Long.toHexString(System.identityHashCode(this)));
646         System.out.println("\tparent: " + parent);
647         int i = 0;
648         for (StackChunk c = tail; c != null; c = c.parent()) {
649             System.out.println("\tChunk " + i);
650             System.out.println(c);
651         }
652     }
653 
654     private static boolean isEmptyOrTrue(String property) {
655         String value = GetPropertyAction.privilegedGetProperty(property);
656         if (value == null)
657             return false;
658         return value.isEmpty() || Boolean.parseBoolean(value);
659     }
660 }