1 /*
   2  * Copyright (c) 2015, 2020, 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 package java.lang;
  26 
  27 import jdk.internal.reflect.MethodAccessor;
  28 import jdk.internal.reflect.ConstructorAccessor;
  29 import java.lang.StackWalker.Option;
  30 import java.lang.StackWalker.StackFrame;
  31 
  32 import java.lang.annotation.Native;
  33 import java.lang.reflect.Method;
  34 import java.lang.reflect.Constructor;
  35 import java.security.AccessController;
  36 import java.security.PrivilegedAction;
  37 import java.util.HashSet;
  38 import java.util.NoSuchElementException;
  39 import java.util.Objects;
  40 import java.util.Set;
  41 import java.util.Spliterator;
  42 import java.util.function.Consumer;
  43 import java.util.function.Function;
  44 import java.util.stream.Stream;
  45 import java.util.stream.StreamSupport;
  46 import jdk.internal.vm.Continuation;
  47 import jdk.internal.vm.ContinuationScope;
  48 import sun.security.action.GetPropertyAction;
  49 
  50 import static java.lang.StackStreamFactory.WalkerState.*;
  51 
  52 /**
  53  * StackStreamFactory class provides static factory methods
  54  * to get different kinds of stack walker/traverser.
  55  *
  56  * AbstractStackWalker provides the basic stack walking support
  57  * fetching stack frames from VM in batches.
  58  *
  59  * AbstractStackWalker subclass is specialized for a specific kind of stack traversal
  60  * to avoid overhead of Stream/Lambda
  61  * 1. Support traversing Stream<StackFrame>
  62  * 2. StackWalker::getCallerClass
  63  * 3. AccessControlContext getting ProtectionDomain
  64  */
  65 final class StackStreamFactory {
  66     private StackStreamFactory() {}
  67 
  68     // Stack walk implementation classes to be excluded during stack walking
  69     // lazily add subclasses when they are loaded.
  70     private static final Set<Class<?>> stackWalkImplClasses = init();
  71 
  72     private static final int SMALL_BATCH       = 8;
  73     private static final int BATCH_SIZE        = 32;
  74     private static final int LARGE_BATCH_SIZE  = 256;
  75     private static final int MIN_BATCH_SIZE    = SMALL_BATCH;
  76 
  77     // These flags must match the values maintained in the VM
  78     @Native private static final int DEFAULT_MODE              = 0x0;
  79     @Native private static final int FILL_CLASS_REFS_ONLY      = 0x2;
  80     @Native private static final int GET_CALLER_CLASS          = 0x4;
  81     @Native private static final int SHOW_HIDDEN_FRAMES        = 0x20;  // LambdaForms are hidden by the VM
  82     @Native private static final int FILL_LIVE_STACK_FRAMES    = 0x100;
  83     /*
  84      * For Throwable to use StackWalker, set useNewThrowable to true.
  85      * Performance work and extensive testing is needed to replace the
  86      * VM built-in backtrace filled in Throwable with the StackWalker.
  87      */
  88     static final boolean isDebug =
  89             "true".equals(GetPropertyAction.privilegedGetProperty("stackwalk.debug"));
  90     
  91     static <T> StackFrameTraverser<T>
  92         makeStackTraverser(StackWalker walker, Function<? super Stream<StackFrame>, ? extends T> function)
  93     {
  94         if (walker.hasLocalsOperandsOption())
  95             return new LiveStackInfoTraverser<>(walker, function);
  96         else
  97             return new StackFrameTraverser<>(walker, function);
  98     }
  99 
 100     /**
 101      * Gets a stack stream to find caller class.
 102      */
 103     static CallerClassFinder makeCallerFinder(StackWalker walker) {
 104         return new CallerClassFinder(walker);
 105     }
 106 
 107     enum WalkerState {
 108         NEW,     // the stream is new and stack walking has not started
 109         OPEN,    // the stream is open when it is being traversed.
 110         CLOSED;  // the stream is closed when the stack walking is done
 111     }
 112 
 113     /**
 114      * Subclass of AbstractStackWalker implements a specific stack walking logic.
 115      * It needs to set up the frame buffer and stack walking mode.
 116      *
 117      * It initiates the VM stack walking via the callStackWalk method that serves
 118      * as the anchored frame and VM will call up to AbstractStackWalker::doStackWalk.
 119      *
 120      * @param <R> the type of the result returned from stack walking
 121      * @param <T> the type of the data gathered for each frame.
 122      *            For example, StackFrameInfo for StackWalker::walk or
 123      *            Class<?> for StackWalker::getCallerClass
 124      */
 125     static abstract class AbstractStackWalker<R, T> {
 126         protected final StackWalker walker;
 127         protected final Thread thread;
 128         protected final int maxDepth;
 129         protected final long mode;
 130         protected int depth;    // traversed stack depth
 131         protected FrameBuffer<? extends T> frameBuffer;
 132         protected long anchor;
 133         protected final ContinuationScope contScope;
 134         protected Continuation continuation;
 135 
 136         // buffers to fill in stack frame information
 137         protected AbstractStackWalker(StackWalker walker, int mode) {
 138             this(walker, mode, Integer.MAX_VALUE);
 139         }
 140         protected AbstractStackWalker(StackWalker walker, int mode, int maxDepth) {
 141             this.thread = Thread.currentThread();
 142             this.mode = toStackWalkMode(walker, mode);
 143             this.walker = walker;
 144             this.maxDepth = maxDepth;
 145             this.depth = 0;
 146             ContinuationScope scope = walker.getContScope();
 147             if (scope == null && thread.isVirtual()) {
 148                 this.contScope = VirtualThread.continuationScope();
 149                 this.continuation = null;
 150             } else {
 151                 this.contScope = walker.getContScope();
 152                 this.continuation = walker.getContinuation();
 153             }
 154         }
 155 
 156         private int toStackWalkMode(StackWalker walker, int mode) {
 157             int newMode = mode;
 158             if (walker.hasOption(Option.SHOW_HIDDEN_FRAMES) &&
 159                     (mode & FILL_CLASS_REFS_ONLY) != FILL_CLASS_REFS_ONLY)
 160                 newMode |= SHOW_HIDDEN_FRAMES;
 161             if (walker.hasLocalsOperandsOption())
 162                 newMode |= FILL_LIVE_STACK_FRAMES;
 163             return newMode;
 164         }
 165 
 166         /**
 167          * A callback method to consume the stack frames.  This method is invoked
 168          * once stack walking begins (i.e. it is only invoked when walkFrames is called).
 169          *
 170          * Each specialized AbstractStackWalker subclass implements the consumeFrames method
 171          * to control the following:
 172          * 1. fetch the subsequent batches of stack frames
 173          * 2. reuse or expand the allocated buffers
 174          * 3. create specialized StackFrame objects
 175          *
 176          * @return the number of consumed frames
 177          */
 178          protected abstract R consumeFrames();
 179 
 180         /**
 181          * Initialize FrameBuffer.  Subclass should implement this method to
 182          * create its custom frame buffers.
 183          */
 184          protected abstract void initFrameBuffer();
 185 
 186         /**
 187          * Returns the suggested next batch size.
 188          *
 189          * Subclass should override this method to change the batch size
 190          *
 191          * @param lastBatchFrameCount number of frames in the last batch; or zero
 192          * @return suggested batch size
 193          */
 194         protected abstract int batchSize(int lastBatchFrameCount);
 195 
 196         /*
 197          * Returns the next batch size, always >= minimum batch size (32)
 198          *
 199          * Subclass may override this method if the minimum batch size is different.
 200          */
 201         protected int getNextBatchSize() {
 202             int lastBatchSize = depth == 0 ? 0 : frameBuffer.curBatchFrameCount();
 203             int nextBatchSize = batchSize(lastBatchSize);
 204             if (isDebug) {
 205                 System.err.println("last batch size = " + lastBatchSize +
 206                                    " next batch size = " + nextBatchSize);
 207             }
 208             return nextBatchSize >= MIN_BATCH_SIZE ? nextBatchSize : MIN_BATCH_SIZE;
 209         }
 210 
 211         /*
 212          * Checks if this stream is in the given state. Otherwise, throws IllegalStateException.
 213          *
 214          * VM also validates this stream if it's anchored for stack walking
 215          * when stack frames are fetched for each batch.
 216          */
 217         final void checkState(WalkerState state) {
 218             if (thread != Thread.currentThread()) {
 219                 throw new IllegalStateException("Invalid thread walking this stack stream: " +
 220                         Thread.currentThread().getName() + " " + thread.getName());
 221             }
 222             switch (state) {
 223                 case NEW:
 224                     if (anchor != 0) {
 225                         throw new IllegalStateException("This stack stream is being reused.");
 226                     }
 227                     break;
 228                 case OPEN:
 229                     if (anchor == 0 || anchor == -1L) {
 230                         throw new IllegalStateException("This stack stream is not valid for walking.");
 231                     }
 232                     break;
 233                 case CLOSED:
 234                     if (anchor != -1L) {
 235                         throw new IllegalStateException("This stack stream is not closed.");
 236                     }
 237             }
 238         }
 239 
 240         /*
 241          * Close this stream.  This stream becomes invalid to walk.
 242          */
 243         private void close() {
 244             this.anchor = -1L;
 245         }
 246 
 247         /*
 248          * Walks stack frames until {@link #consumeFrames} is done consuming
 249          * the frames it is interested in.
 250          */
 251         final R walk() {
 252             checkState(NEW);
 253             return continuation != null
 254                 ? Continuation.wrapWalk(continuation, contScope, this::walkHelper)
 255                 : walkHelper();
 256         }
 257 
 258         private final R walkHelper() {
 259             try {
 260                 // VM will need to stabilize the stack before walking.  It will invoke
 261                 // the AbstractStackWalker::doStackWalk method once it fetches the first batch.
 262                 // the callback will be invoked within the scope of the callStackWalk frame.
 263                 return beginStackWalk();
 264             } finally {
 265                 close();  // done traversal; close the stream
 266             }
 267         }
 268 
 269         private boolean skipReflectionFrames() {
 270             return !walker.hasOption(Option.SHOW_REFLECT_FRAMES) &&
 271                        !walker.hasOption(Option.SHOW_HIDDEN_FRAMES);
 272         }
 273 
 274         /*
 275          * Returns {@code Class} object at the current frame;
 276          * or {@code null} if no more frame. If advanceToNextBatch is true,
 277          * it will only fetch the next batch.
 278          */
 279         final Class<?> peekFrame() {
 280             while (frameBuffer.isActive() && depth < maxDepth) {
 281                 if (frameBuffer.isEmpty()) {
 282                     // fetch another batch of stack frames
 283                     getNextBatch();
 284                 } else {
 285                     Class<?> c = frameBuffer.get();
 286                     if (skipReflectionFrames() && isReflectionFrame(c)) {
 287                         if (isDebug)
 288                             System.err.println("  skip: frame " + frameBuffer.getIndex() + " " + c);
 289 
 290                         frameBuffer.next();
 291                         depth++;
 292                         continue;
 293                     } else {
 294                         return c;
 295                     }
 296                 }
 297             }
 298             return null;
 299         }
 300 
 301         /*
 302          * This method is only invoked by VM.
 303          *
 304          * It will invoke the consumeFrames method to start the stack walking
 305          * with the first batch of stack frames.  Each specialized AbstractStackWalker
 306          * subclass implements the consumeFrames method to control the following:
 307          * 1. fetch the subsequent batches of stack frames
 308          * 2. reuse or expand the allocated buffers
 309          * 3. create specialized StackFrame objects
 310          */
 311         private Object doStackWalk(long anchor, int skipFrames, int batchSize,
 312                                                 int bufStartIndex, int bufEndIndex) {
 313             checkState(NEW);
 314 
 315             frameBuffer.check(skipFrames);
 316 
 317             if (isDebug) {
 318                 System.err.format("doStackWalk: skip %d start %d end %d%n",
 319                         skipFrames, bufStartIndex, bufEndIndex);
 320             }
 321 
 322             this.anchor = anchor;  // set anchor for this bulk stack frame traversal
 323 
 324             int numFrames = bufEndIndex - bufStartIndex;
 325             frameBuffer.setBatch(depth, bufStartIndex, bufEndIndex);
 326 
 327             // traverse all frames and perform the action on the stack frames, if specified
 328             return consumeFrames();
 329         }
 330 
 331         /*
 332          * Get next batch of stack frames.
 333          */
 334         private int getNextBatch() {
 335             int nextBatchSize = Math.min(maxDepth - depth, getNextBatchSize());
 336 
 337             if (!frameBuffer.isActive() || nextBatchSize <= 0 || (frameBuffer.isAtBottom() && !hasMoreContinuations())) {
 338                 if (isDebug) {
 339                     System.out.format("  more stack walk done%n");
 340                 }
 341                 frameBuffer.freeze();   // stack walk done
 342                 return 0;
 343             }
 344 
 345             if (frameBuffer.isAtBottom() && hasMoreContinuations()) {
 346                 setContinuation(continuation.getParent());
 347             }
 348 
 349             int numFrames = fetchStackFrames(nextBatchSize);
 350             if (numFrames == 0 && !hasMoreContinuations()) {
 351                 frameBuffer.freeze(); // done stack walking
 352             }
 353             return numFrames;
 354         }
 355 
 356         private boolean hasMoreContinuations() {
 357             return continuation != null && continuation.getScope() != contScope && continuation.getParent() != null;
 358         }
 359 
 360         private void setContinuation(Continuation cont) {
 361             this.continuation = cont;
 362             setContinuation(anchor, frameBuffer.frames(), cont);
 363         }
 364 
 365         /*
 366          * This method traverses the next stack frame and returns the Class
 367          * invoking that stack frame.
 368          *
 369          * This method can only be called during the walk method.  This is intended
 370          * to be used to walk the stack frames in one single invocation and
 371          * this stack stream will be invalidated once walk is done.
 372          *
 373          * @see #tryNextFrame
 374          */
 375         final Class<?> nextFrame() {
 376             if (!hasNext()) {
 377                 return null;
 378             }
 379 
 380             Class<?> c = frameBuffer.next();
 381             depth++;
 382             return c;
 383         }
 384 
 385         /*
 386          * Returns true if there is next frame to be traversed.
 387          * This skips hidden frames unless this StackWalker has
 388          * {@link Option#SHOW_REFLECT_FRAMES}
 389          */
 390         final boolean hasNext() {
 391             return peekFrame() != null;
 392         }
 393 
 394         /**
 395          * Begin stack walking - pass the allocated arrays to the VM to fill in
 396          * stack frame information.
 397          *
 398          * VM first anchors the frame of the current thread.  A traversable stream
 399          * on this thread's stack will be opened.  The VM will fetch the first batch
 400          * of stack frames and call AbstractStackWalker::doStackWalk to invoke the
 401          * stack walking function on each stack frame.
 402          *
 403          * If all fetched stack frames are traversed, AbstractStackWalker::fetchStackFrames will
 404          * fetch the next batch of stack frames to continue.
 405          */
 406         private R beginStackWalk() {
 407             // initialize buffers for VM to fill the stack frame info
 408             initFrameBuffer();
 409 
 410             return callStackWalk(mode, 0, 
 411                                  contScope, continuation,
 412                                  frameBuffer.curBatchFrameCount(),
 413                                  frameBuffer.startIndex(),
 414                                  frameBuffer.frames());
 415         }
 416 
 417         /*
 418          * Fetches stack frames.
 419          *
 420          * @params batchSize number of elements of the frame  buffers for this batch
 421          * @returns number of frames fetched in this batch
 422          */
 423         private int fetchStackFrames(int batchSize) {
 424             int startIndex = frameBuffer.startIndex();
 425             frameBuffer.resize(startIndex, batchSize);
 426 
 427             int endIndex = fetchStackFrames(mode, anchor, batchSize,
 428                                             startIndex,
 429                                             frameBuffer.frames());
 430             if (isDebug) {
 431                 System.out.format("  more stack walk requesting %d got %d to %d frames%n",
 432                                   batchSize, frameBuffer.startIndex(), endIndex);
 433             }
 434 
 435             int numFrames = endIndex - startIndex;
 436 
 437             if (numFrames > 0) {
 438                 frameBuffer.setBatch(depth, startIndex, endIndex);
 439             }
 440             return numFrames;
 441         }
 442 
 443         /**
 444          * Begins stack walking.  This method anchors this frame and invokes
 445          * AbstractStackWalker::doStackWalk after fetching the first batch of stack frames.
 446          *
 447          * @param mode        mode of stack walking
 448          * @param skipframes  number of frames to be skipped before filling the frame buffer.
 449          * @param contScope   the continuation scope to walk.
 450          * @param continuation the continuation to walk, or {@code null} if walking a thread.
 451          * @param batchSize   the batch size, max. number of elements to be filled in the frame buffers.
 452          * @param startIndex  start index of the frame buffers to be filled.
 453          * @param frames      Either a Class<?> array, if mode is {@link #FILL_CLASS_REFS_ONLY}
 454          *                    or a {@link StackFrameInfo} (or derivative) array otherwise.
 455          * @return            Result of AbstractStackWalker::doStackWalk
 456          */
 457         private native R callStackWalk(long mode, int skipframes, 
 458                                        ContinuationScope contScope, Continuation continuation,
 459                                        int batchSize, int startIndex,
 460                                        T[] frames);
 461 
 462         /**
 463          * Fetch the next batch of stack frames.
 464          *
 465          * @param mode        mode of stack walking
 466          * @param anchor
 467          * @param batchSize   the batch size, max. number of elements to be filled in the frame buffers.
 468          * @param startIndex  start index of the frame buffers to be filled.
 469          * @param frames      Either a Class<?> array, if mode is {@link #FILL_CLASS_REFS_ONLY}
 470          *                    or a {@link StackFrameInfo} (or derivative) array otherwise.
 471          *
 472          * @return the end index to the frame buffers
 473          */
 474         private native int fetchStackFrames(long mode, long anchor,
 475                                             int batchSize, int startIndex,
 476                                             T[] frames);
 477 
 478         private native void setContinuation(long anchor, T[] frames, Continuation cont);
 479     }
 480 
 481     /*
 482      * This StackFrameTraverser supports {@link Stream} traversal.
 483      *
 484      * This class implements Spliterator::forEachRemaining and Spliterator::tryAdvance.
 485      */
 486     static class StackFrameTraverser<T> extends AbstractStackWalker<T, StackFrameInfo>
 487             implements Spliterator<StackFrame>
 488     {
 489         static {
 490             stackWalkImplClasses.add(StackFrameTraverser.class);
 491         }
 492         private static final int CHARACTERISTICS = Spliterator.ORDERED | Spliterator.IMMUTABLE;
 493 
 494         final class StackFrameBuffer extends FrameBuffer<StackFrameInfo> {
 495             private StackFrameInfo[] stackFrames;
 496             StackFrameBuffer(int initialBatchSize) {
 497                 super(initialBatchSize);
 498 
 499                 this.stackFrames = new StackFrameInfo[initialBatchSize];
 500                 for (int i = START_POS; i < initialBatchSize; i++) {
 501                     stackFrames[i] = new StackFrameInfo(walker);
 502                 }
 503             }
 504 
 505             @Override
 506             StackFrameInfo[] frames() {
 507                 return stackFrames;
 508             }
 509 
 510             @Override
 511             void resize(int startIndex, int elements) {
 512                 if (!isActive())
 513                     throw new IllegalStateException("inactive frame buffer can't be resized");
 514 
 515                 assert startIndex == START_POS :
 516                        "bad start index " + startIndex + " expected " + START_POS;
 517 
 518                 int size = startIndex+elements;
 519                 if (stackFrames.length < size) {
 520                     StackFrameInfo[] newFrames = new StackFrameInfo[size];
 521                     // copy initial magic...
 522                     System.arraycopy(stackFrames, 0, newFrames, 0, startIndex);
 523                     stackFrames = newFrames;
 524                 }
 525                 for (int i = startIndex; i < size; i++) {
 526                     stackFrames[i] = new StackFrameInfo(walker);
 527                 }
 528                 currentBatchSize = size;
 529             }
 530 
 531             @Override
 532             StackFrameInfo nextStackFrame() {
 533                 if (isEmpty()) {
 534                     throw new NoSuchElementException("origin=" + origin + " fence=" + fence);
 535                 }
 536 
 537                 StackFrameInfo frame = stackFrames[origin];
 538                 origin++;
 539                 return frame;
 540             }
 541 
 542             @Override
 543             final Class<?> at(int index) {
 544                 return stackFrames[index].declaringClass();
 545             }
 546 
 547             @Override
 548             final boolean filter(int index) {
 549                 return stackFrames[index].declaringClass() == Continuation.class && "yield0".equals(stackFrames[index].getMethodName());
 550             }
 551         }
 552 
 553         final Function<? super Stream<StackFrame>, ? extends T> function;  // callback
 554 
 555         StackFrameTraverser(StackWalker walker,
 556                             Function<? super Stream<StackFrame>, ? extends T> function) {
 557             this(walker, function, DEFAULT_MODE);
 558         }
 559         StackFrameTraverser(StackWalker walker,
 560                             Function<? super Stream<StackFrame>, ? extends T> function,
 561                             int mode) {
 562             super(walker, mode);
 563             this.function = function;
 564         }
 565 
 566         /**
 567          * Returns next StackFrame object in the current batch of stack frames;
 568          * or null if no more stack frame.
 569          */
 570         StackFrame nextStackFrame() {
 571             if (!hasNext()) {
 572                 return null;
 573             }
 574 
 575             StackFrameInfo frame = frameBuffer.nextStackFrame();
 576             depth++;
 577             return frame;
 578         }
 579 
 580         @Override
 581         protected T consumeFrames() {
 582             checkState(OPEN);
 583             Stream<StackFrame> stream = StreamSupport.stream(this, false);
 584             if (function != null) {
 585                 return function.apply(stream);
 586             } else
 587                 throw new UnsupportedOperationException();
 588         }
 589 
 590         @Override
 591         protected void initFrameBuffer() {
 592             this.frameBuffer = new StackFrameBuffer(getNextBatchSize());
 593         }
 594 
 595         @Override
 596         protected int batchSize(int lastBatchFrameCount) {
 597             if (lastBatchFrameCount == 0) {
 598                 // First batch, use estimateDepth if not exceed the large batch size
 599                 // and not too small
 600                 int initialBatchSize = Math.max(walker.estimateDepth(), SMALL_BATCH);
 601                 return Math.min(initialBatchSize, LARGE_BATCH_SIZE);
 602             } else {
 603                 if (lastBatchFrameCount > BATCH_SIZE) {
 604                     return lastBatchFrameCount;
 605                 } else {
 606                     return Math.min(lastBatchFrameCount*2, BATCH_SIZE);
 607                 }
 608             }
 609         }
 610 
 611         // ------- Implementation of Spliterator
 612 
 613         @Override
 614         public Spliterator<StackFrame> trySplit() {
 615             return null;   // ordered stream and do not allow to split
 616         }
 617 
 618         @Override
 619         public long estimateSize() {
 620             return maxDepth;
 621         }
 622 
 623         @Override
 624         public int characteristics() {
 625             return CHARACTERISTICS;
 626         }
 627 
 628         @Override
 629         public void forEachRemaining(Consumer<? super StackFrame> action) {
 630             checkState(OPEN);
 631             for (int n = 0; n < maxDepth; n++) {
 632                 StackFrame frame = nextStackFrame();
 633                 if (frame == null) break;
 634 
 635                 action.accept(frame);
 636             }
 637         }
 638 
 639         @Override
 640         public boolean tryAdvance(Consumer<? super StackFrame> action) {
 641             checkState(OPEN);
 642 
 643             int index = frameBuffer.getIndex();
 644             if (hasNext()) {
 645                 StackFrame frame = nextStackFrame();
 646                 action.accept(frame);
 647                 if (isDebug) {
 648                     System.err.println("tryAdvance: " + index + " " + frame);
 649                 }
 650                 return true;
 651             }
 652             if (isDebug) {
 653                 System.err.println("tryAdvance: " + index + " NO element");
 654             }
 655             return false;
 656         }
 657     }
 658 
 659     /*
 660      * CallerClassFinder is specialized to return Class<?> for each stack frame.
 661      * StackFrame is not requested.
 662      */
 663     static final class CallerClassFinder extends AbstractStackWalker<Integer, Class<?>> {
 664         static {
 665             stackWalkImplClasses.add(CallerClassFinder.class);
 666         }
 667 
 668         private Class<?> caller;
 669 
 670         CallerClassFinder(StackWalker walker) {
 671             super(walker, FILL_CLASS_REFS_ONLY|GET_CALLER_CLASS);
 672         }
 673 
 674         static final class ClassBuffer extends FrameBuffer<Class<?>> {
 675             Class<?>[] classes;      // caller class for fast path
 676             ClassBuffer(int batchSize) {
 677                 super(batchSize);
 678                 classes = new Class<?>[batchSize];
 679             }
 680 
 681             @Override
 682             Class<?>[] frames() { return classes;}
 683 
 684             @Override
 685             final Class<?> at(int index) { return classes[index];}
 686 
 687             @Override
 688             final boolean filter(int index) { return false; }
 689 
 690 
 691             // ------ subclass may override the following methods -------
 692             /**
 693              * Resizes the buffers for VM to fill in the next batch of stack frames.
 694              * The next batch will start at the given startIndex with the maximum number
 695              * of elements.
 696              *
 697              * <p> Subclass may override this method to manage the allocated buffers.
 698              *
 699              * @param startIndex the start index for the first frame of the next batch to fill in.
 700              * @param elements the number of elements for the next batch to fill in.
 701              *
 702              */
 703             @Override
 704             void resize(int startIndex, int elements) {
 705                 if (!isActive())
 706                     throw new IllegalStateException("inactive frame buffer can't be resized");
 707 
 708                 assert startIndex == START_POS :
 709                        "bad start index " + startIndex + " expected " + START_POS;
 710 
 711                 int size = startIndex+elements;
 712                 if (classes.length < size) {
 713                     // copy the elements in classes array to the newly allocated one.
 714                     // classes[0] is a Thread object
 715                     Class<?>[] prev = classes;
 716                     classes = new Class<?>[size];
 717                     System.arraycopy(prev, 0, classes, 0, startIndex);
 718                 }
 719                 currentBatchSize = size;
 720             }
 721         }
 722 
 723         Class<?> findCaller() {
 724             walk();
 725             return caller;
 726         }
 727 
 728         @Override
 729         protected Integer consumeFrames() {
 730             checkState(OPEN);
 731             int n = 0;
 732             Class<?>[] frames = new Class<?>[2];
 733             // skip the API calling this getCallerClass method
 734             // 0: StackWalker::getCallerClass
 735             // 1: caller-sensitive method
 736             // 2: caller class
 737             while (n < 2 && (caller = nextFrame()) != null) {
 738                 if (isMethodHandleFrame(caller)) { continue; }
 739                 if (isReflectionFrame(caller)) { continue; }
 740                 frames[n++] = caller;
 741             }
 742             if (frames[1] == null) {
 743                 throw new IllegalCallerException("no caller frame");
 744             }
 745             return n;
 746         }
 747 
 748         @Override
 749         protected void initFrameBuffer() {
 750             this.frameBuffer = new ClassBuffer(getNextBatchSize());
 751         }
 752 
 753         @Override
 754         protected int batchSize(int lastBatchFrameCount) {
 755             return MIN_BATCH_SIZE;
 756         }
 757 
 758         @Override
 759         protected int getNextBatchSize() {
 760             return MIN_BATCH_SIZE;
 761         }
 762     }
 763 
 764     static final class LiveStackInfoTraverser<T> extends StackFrameTraverser<T> {
 765         static {
 766             stackWalkImplClasses.add(LiveStackInfoTraverser.class);
 767         }
 768         // VM will fill in all method info and live stack info directly in StackFrameInfo
 769         final class LiveStackFrameBuffer extends FrameBuffer<LiveStackFrameInfo> {
 770             private LiveStackFrameInfo[] stackFrames;
 771             LiveStackFrameBuffer(int initialBatchSize) {
 772                 super(initialBatchSize);
 773                 this.stackFrames = new LiveStackFrameInfo[initialBatchSize];
 774                 for (int i = START_POS; i < initialBatchSize; i++) {
 775                     stackFrames[i] = new LiveStackFrameInfo(walker);
 776                 }
 777             }
 778 
 779             @Override
 780             LiveStackFrameInfo[] frames() {
 781                 return stackFrames;
 782             }
 783 
 784             @Override
 785             void resize(int startIndex, int elements) {
 786                 if (!isActive()) {
 787                     throw new IllegalStateException("inactive frame buffer can't be resized");
 788                 }
 789                 assert startIndex == START_POS :
 790                        "bad start index " + startIndex + " expected " + START_POS;
 791 
 792                 int size = startIndex + elements;
 793                 if (stackFrames.length < size) {
 794                     LiveStackFrameInfo[] newFrames = new LiveStackFrameInfo[size];
 795                     // copy initial magic...
 796                     System.arraycopy(stackFrames, 0, newFrames, 0, startIndex);
 797                     stackFrames = newFrames;
 798                 }
 799 
 800                 for (int i = startIndex(); i < size; i++) {
 801                     stackFrames[i] = new LiveStackFrameInfo(walker);
 802                 }
 803 
 804                 currentBatchSize = size;
 805             }
 806 
 807             @Override
 808             LiveStackFrameInfo nextStackFrame() {
 809                 if (isEmpty()) {
 810                     throw new NoSuchElementException("origin=" + origin + " fence=" + fence);
 811                 }
 812 
 813                 LiveStackFrameInfo frame = stackFrames[origin];
 814                 origin++;
 815                 return frame;
 816             }
 817 
 818             @Override
 819             final Class<?> at(int index) {
 820                 return stackFrames[index].declaringClass();
 821             }
 822 
 823             @Override
 824             final boolean filter(int index) {
 825                 return stackFrames[index].declaringClass() == Continuation.class && "yield0".equals(stackFrames[index].getMethodName());
 826             }
 827         }
 828 
 829         LiveStackInfoTraverser(StackWalker walker,
 830                                Function<? super Stream<StackFrame>, ? extends T> function) {
 831             super(walker, function, DEFAULT_MODE);
 832         }
 833 
 834         @Override
 835         protected void initFrameBuffer() {
 836             this.frameBuffer = new LiveStackFrameBuffer(getNextBatchSize());
 837         }
 838     }
 839 
 840     /*
 841      * Frame buffer
 842      *
 843      * Each specialized AbstractStackWalker subclass may subclass the FrameBuffer.
 844      */
 845     static abstract class FrameBuffer<F> {
 846         static final int START_POS = 2;     // 0th and 1st elements are reserved
 847 
 848         // buffers for VM to fill stack frame info
 849         int currentBatchSize;    // current batch size
 850         int origin;         // index to the current traversed stack frame
 851         int fence;          // index to the last frame in the current batch
 852 
 853         FrameBuffer(int initialBatchSize) {
 854             if (initialBatchSize < MIN_BATCH_SIZE) {
 855                 throw new IllegalArgumentException(initialBatchSize +
 856                         " < minimum batch size: " + MIN_BATCH_SIZE);
 857             }
 858             this.origin = START_POS;
 859             this.fence = 0;
 860             this.currentBatchSize = initialBatchSize;
 861         }
 862 
 863         /**
 864          * Returns an array of frames that may be used to store frame objects
 865          * when walking the stack.
 866          *
 867          * May be an array of {@code Class<?>} if the {@code AbstractStackWalker}
 868          * mode is {@link #FILL_CLASS_REFS_ONLY}, or an array of
 869          * {@link StackFrameInfo} (or derivative) array otherwise.
 870          *
 871          * @return An array of frames that may be used to store frame objects
 872          * when walking the stack. Must not be null.
 873          */
 874         abstract F[] frames(); // must not return null
 875 
 876         /**
 877          * Resizes the buffers for VM to fill in the next batch of stack frames.
 878          * The next batch will start at the given startIndex with the maximum number
 879          * of elements.
 880          *
 881          * <p> Subclass may override this method to manage the allocated buffers.
 882          *
 883          * @param startIndex the start index for the first frame of the next batch to fill in.
 884          * @param elements the number of elements for the next batch to fill in.
 885          *
 886          */
 887         abstract void resize(int startIndex, int elements);
 888 
 889         /**
 890          * Return the class at the given position in the current batch.
 891          * @param index the position of the frame.
 892          * @return the class at the given position in the current batch.
 893          */
 894         abstract Class<?> at(int index);
 895 
 896         /**
 897          * Filter out frames at the top of a batch
 898          * @param index the position of the frame.
 899          * @return true if the frame should be skipped
 900          */
 901         abstract boolean filter(int index);
 902 
 903         // ------ subclass may override the following methods -------
 904 
 905         /*
 906          * Returns the start index for this frame buffer is refilled.
 907          *
 908          * This implementation reuses the allocated buffer for the next batch
 909          * of stack frames.  For subclass to retain the fetched stack frames,
 910          * it should override this method to return the index at which the frame
 911          * should be filled in for the next batch.
 912          */
 913         int startIndex() {
 914             return START_POS;
 915         }
 916 
 917         /**
 918          * Returns next StackFrame object in the current batch of stack frames
 919          */
 920         F nextStackFrame() {
 921             throw new InternalError("should not reach here");
 922         }
 923 
 924         // ------ FrameBuffer implementation ------
 925 
 926         final int curBatchFrameCount() {
 927             return currentBatchSize-START_POS;
 928         }
 929 
 930         /*
 931          * Tests if this frame buffer is empty.  All frames are fetched.
 932          */
 933         final boolean isEmpty() {
 934             return origin >= fence || (origin == START_POS && fence == 0);
 935         }
 936 
 937         /*
 938          * Freezes this frame buffer.  The stack stream source is done fetching.
 939          */
 940         final void freeze() {
 941             origin = 0;
 942             fence = 0;
 943         }
 944 
 945         /*
 946          * Tests if this frame buffer is active.  It is inactive when
 947          * it is done for traversal.  All stack frames have been traversed.
 948          */
 949         final boolean isActive() {
 950             return origin > 0; //  && (fence == 0 || origin < fence || fence == currentBatchSize);
 951         }
 952 
 953         /*
 954          * Tests if this frame buffer is at the end of the stack
 955          * and all frames have been traversed.
 956          */
 957         final boolean isAtBottom() {
 958             return origin > 0 && origin >= fence && fence < currentBatchSize;
 959         }
 960 
 961         /**
 962          * Gets the class at the current frame and move to the next frame.
 963          */
 964         final Class<?> next() {
 965             if (isEmpty()) {
 966                 throw new NoSuchElementException("origin=" + origin + " fence=" + fence);
 967             }
 968             Class<?> c = at(origin);
 969             origin++;
 970             if (isDebug) {
 971                 int index = origin-1;
 972                 System.out.format("  next frame at %d: %s (origin %d fence %d)%n", index,
 973                         Objects.toString(c), index, fence);
 974             }
 975             return c;
 976         }
 977 
 978         /**
 979          * Gets the class at the current frame.
 980          */
 981         final Class<?> get() {
 982             if (isEmpty()) {
 983                 throw new NoSuchElementException("origin=" + origin + " fence=" + fence);
 984             }
 985             return at(origin);
 986         }
 987 
 988         /*
 989          * Returns the index of the current frame.
 990          */
 991         final int getIndex() {
 992             return origin;
 993         }
 994 
 995         /*
 996          * Set the start and end index of a new batch of stack frames that have
 997          * been filled in this frame buffer.
 998          */
 999         final void setBatch(int depth, int startIndex, int endIndex) {
1000             if (startIndex <= 0 || endIndex <= 0)
1001                 throw new IllegalArgumentException("startIndex=" + startIndex
1002                         + " endIndex=" + endIndex);
1003 
1004             this.origin = startIndex;
1005             this.fence = endIndex;
1006             for (int i = START_POS; i < fence; i++) {
1007                 if (isDebug) System.err.format("  frame %d: %s%n", i, at(i));
1008                 if ((depth == 0 && filterStackWalkImpl(at(i))) // filter the frames due to the stack stream implementation
1009                         || filter(i)) {
1010                     origin++;
1011                 } else {
1012                     break;
1013                 }
1014             }
1015         }
1016 
1017         /*
1018          * Checks if the origin is the expected start index.
1019          */
1020         final void check(int skipFrames) {
1021             int index = skipFrames + START_POS;
1022             if (origin != index) {
1023                 // stack walk must continue with the previous frame depth
1024                 throw new IllegalStateException("origin " + origin + " != " + index);
1025             }
1026         }
1027     }
1028 
1029     private static native boolean checkStackWalkModes();
1030 
1031     // avoid loading other subclasses as they may not be used
1032     private static Set<Class<?>> init() {
1033         if (!checkStackWalkModes()) {
1034             throw new InternalError("StackWalker mode values do not match with JVM");
1035         }
1036 
1037         Set<Class<?>> classes = new HashSet<>();
1038         classes.add(StackWalker.class);
1039         classes.add(StackStreamFactory.class);
1040         classes.add(AbstractStackWalker.class);
1041         return classes;
1042     }
1043 
1044     private static boolean filterStackWalkImpl(Class<?> c) {
1045         return stackWalkImplClasses.contains(c) ||
1046                 c.getName().startsWith("java.util.stream.");
1047     }
1048 
1049     // MethodHandle frames are not hidden and CallerClassFinder has
1050     // to filter them out
1051     private static boolean isMethodHandleFrame(Class<?> c) {
1052         return c.getName().startsWith("java.lang.invoke.");
1053     }
1054 
1055     private static boolean isReflectionFrame(Class<?> c) {
1056         // ## should filter all @Hidden frames?
1057         return c == Method.class ||
1058                c == Constructor.class ||
1059                MethodAccessor.class.isAssignableFrom(c) ||
1060                ConstructorAccessor.class.isAssignableFrom(c) ||
1061                c.getName().startsWith("java.lang.invoke.LambdaForm");
1062     }
1063 
1064 }