1 /* 2 * Copyright 2019 Google LLC 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package io.perfmark.tracewriter; 18 19 import io.perfmark.impl.Mark; 20 import io.perfmark.impl.MarkList; 21 import java.util.ArrayDeque; 22 import java.util.ArrayList; 23 import java.util.Collection; 24 import java.util.Collections; 25 import java.util.Deque; 26 import java.util.IdentityHashMap; 27 import java.util.List; 28 import java.util.Map; 29 import java.util.Set; 30 import java.util.TreeMap; 31 32 class MarkListWalker { MarkListWalker()33 MarkListWalker() {} 34 35 static final String UNKNOWN_TASK_NAME = "(unknown)"; 36 37 // TODO: make sure the generations dont have any timestamp overlap walk(List<? extends MarkList> markLists, long nowNanoTime)38 final void walk(List<? extends MarkList> markLists, long nowNanoTime) { 39 Map<Long, List<MarkList>> generationToMarkLists = groupMarkListsByGeneration(markLists); 40 for (Map.Entry<Long, List<MarkList>> entry : generationToMarkLists.entrySet()) { 41 enterGeneration(entry.getKey()); 42 for (MarkList markList : entry.getValue()) { 43 enterMarkList(markList.getThreadName(), markList.getThreadId(), markList.getMarkListId()); 44 Deque<Mark> fakeStarts = new ArrayDeque<>(); 45 Deque<Mark> fakeEnds = new ArrayDeque<>(); 46 Set<Mark> unmatchedPairMarks = 47 Collections.newSetFromMap(new IdentityHashMap<Mark, Boolean>()); 48 createFakes(fakeStarts, fakeEnds, unmatchedPairMarks, markList, nowNanoTime); 49 for (Mark mark : fakeStarts) { 50 onTaskStart(mark, true, false); 51 } 52 for (Mark mark : markList) { 53 onRealMark(mark, unmatchedPairMarks); 54 } 55 for (Mark mark : fakeEnds) { 56 onTaskEnd(mark, false, true); 57 } 58 exitMarkList(); 59 } 60 exitGeneration(); 61 } 62 } 63 enterGeneration(long generation)64 protected void enterGeneration(long generation) {} 65 exitGeneration()66 protected void exitGeneration() {} 67 enterMarkList(String threadName, long threadId, long markListId)68 protected void enterMarkList(String threadName, long threadId, long markListId) {} 69 exitMarkList()70 protected void exitMarkList() {} 71 onRealMark(Mark mark, Collection<Mark> unmatchedPairMarks)72 private void onRealMark(Mark mark, Collection<Mark> unmatchedPairMarks) { 73 switch (mark.getOperation().getOpType()) { 74 case TASK_START: 75 onTaskStart(mark, false, unmatchedPairMarks.contains(mark)); 76 return; 77 case TASK_END: 78 onTaskEnd(mark, unmatchedPairMarks.contains(mark), false); 79 return; 80 case TAG: 81 onAttachTag(mark); 82 return; 83 case EVENT: 84 onEvent(mark); 85 return; 86 case LINK: 87 onLink(mark); 88 return; 89 case NONE: 90 break; 91 } 92 throw new AssertionError(); 93 } 94 onTaskStart(Mark mark, boolean unmatchedStart, boolean unmatchedEnd)95 protected void onTaskStart(Mark mark, boolean unmatchedStart, boolean unmatchedEnd) {} 96 onTaskEnd(Mark mark, boolean unmatchedStart, boolean unmatchedEnd)97 protected void onTaskEnd(Mark mark, boolean unmatchedStart, boolean unmatchedEnd) {} 98 onLink(Mark mark)99 protected void onLink(Mark mark) {} 100 onEvent(Mark mark)101 protected void onEvent(Mark mark) {} 102 onAttachTag(Mark mark)103 protected void onAttachTag(Mark mark) {} 104 groupMarkListsByGeneration( List<? extends MarkList> markLists)105 private static Map<Long, List<MarkList>> groupMarkListsByGeneration( 106 List<? extends MarkList> markLists) { 107 Map<Long, List<MarkList>> generationToMarkLists = new TreeMap<>(); 108 for (MarkList markList : markLists) { 109 if (markList.isEmpty()) { 110 continue; 111 } 112 Map<Long, List<Mark>> generationToMarks = new TreeMap<>(); 113 for (Mark mark : markList) { 114 List<Mark> groupedMarks = generationToMarks.get(mark.getGeneration()); 115 if (groupedMarks == null) { 116 generationToMarks.put(mark.getGeneration(), groupedMarks = new ArrayList<>()); 117 } 118 groupedMarks.add(mark); 119 } 120 // note: marklists without any marks are lost here, since they have no generation. 121 for (Map.Entry<Long, List<Mark>> entry : generationToMarks.entrySet()) { 122 List<MarkList> groupedMarkLists = generationToMarkLists.get(entry.getKey()); 123 if (groupedMarkLists == null) { 124 generationToMarkLists.put(entry.getKey(), groupedMarkLists = new ArrayList<>()); 125 } 126 groupedMarkLists.add(markList.toBuilder().setMarks(entry.getValue()).build()); 127 } 128 } 129 // TODO: make a defensive copy of this and the sublists 130 return generationToMarkLists; 131 } 132 createFakes( Deque<? super Mark> fakeStarts, Deque<? super Mark> fakeEnds, Set<? super Mark> unmatchedPairMarks, List<Mark> marks, long nowNanoTime)133 private static void createFakes( 134 Deque<? super Mark> fakeStarts, 135 Deque<? super Mark> fakeEnds, 136 Set<? super Mark> unmatchedPairMarks, 137 List<Mark> marks, 138 long nowNanoTime) { 139 final Deque<Mark> unmatchedMarks = new ArrayDeque<>(); 140 long[] nanoTimeBounds = new long[2]; // first, last 141 nanoTimeBounds[0] = nowNanoTime; // forces each subsequent overwrite to succeed. 142 nanoTimeBounds[1] = nowNanoTime; 143 144 loop: 145 for (Mark mark : marks) { 146 setNanoTimeBounds(nanoTimeBounds, mark); 147 switch (mark.getOperation().getOpType()) { 148 case TASK_START: 149 unmatchedMarks.addLast(mark); 150 continue loop; 151 case TASK_END: 152 if (!unmatchedMarks.isEmpty()) { 153 // TODO: maybe double check the tags and task names match 154 unmatchedMarks.removeLast(); 155 } else { 156 fakeStarts.addFirst(createFakeStart(mark, nanoTimeBounds[0])); 157 unmatchedPairMarks.add(mark); 158 } 159 continue loop; 160 case EVENT: 161 case LINK: 162 case TAG: 163 continue loop; 164 case NONE: 165 break; 166 } 167 throw new AssertionError(); 168 } 169 for (Mark unmatchedMark : unmatchedMarks) { 170 fakeEnds.addFirst(createFakeEnd(unmatchedMark, nanoTimeBounds[1])); 171 unmatchedPairMarks.add(unmatchedMark); 172 } 173 unmatchedMarks.clear(); 174 } 175 setNanoTimeBounds(long[] nanoTimeBounds, Mark mark)176 private static void setNanoTimeBounds(long[] nanoTimeBounds, Mark mark) { 177 switch (mark.getOperation().getOpType()) { 178 case TASK_START: 179 case TASK_END: 180 case EVENT: 181 if (mark.getNanoTime() - nanoTimeBounds[0] < 0) { 182 nanoTimeBounds[0] = mark.getNanoTime(); 183 } 184 if (mark.getNanoTime() - nanoTimeBounds[1] > 0) { 185 nanoTimeBounds[1] = mark.getNanoTime(); 186 } 187 return; 188 case LINK: 189 case TAG: 190 return; 191 case NONE: 192 break; 193 } 194 throw new AssertionError(); 195 } 196 createFakeEnd(Mark start, long lastNanoTime)197 private static Mark createFakeEnd(Mark start, long lastNanoTime) { 198 switch (start.getOperation()) { 199 case TASK_START_N1S1: 200 return Mark.taskEnd(start.getGeneration(), lastNanoTime, start.getTaskName()); 201 case TASK_START_N1S2: 202 return Mark.taskEnd( 203 start.getGeneration(), lastNanoTime, start.getTaskName(), start.getSubTaskName()); 204 case TASK_END_N1S0: 205 case TASK_END_N1S1: 206 case TASK_END_N1S2: 207 case EVENT_N1S1: 208 case EVENT_N1S2: 209 case EVENT_N2S2: 210 case EVENT_N2S3: 211 case LINK: 212 case TAG_N0S1: 213 case TAG_KEYED_N0S2: 214 case TAG_KEYED_N2S1: 215 case TAG_KEYED_N1S1: 216 case TAG_N1S0: 217 case TAG_N1S1: 218 case NONE: 219 break; 220 } 221 throw new AssertionError(start.getOperation()); 222 } 223 createFakeStart(Mark end, long firstNanoTime)224 private static Mark createFakeStart(Mark end, long firstNanoTime) { 225 switch (end.getOperation()) { 226 case TASK_END_N1S0: 227 return Mark.taskStart(end.getGeneration(), firstNanoTime, UNKNOWN_TASK_NAME); 228 case TASK_END_N1S1: 229 return Mark.taskStart(end.getGeneration(), firstNanoTime, end.getTaskName()); 230 case TASK_END_N1S2: 231 return Mark.taskStart( 232 end.getGeneration(), firstNanoTime, end.getTaskName(), end.getSubTaskName()); 233 case NONE: 234 case TASK_START_N1S1: 235 case TASK_START_N1S2: 236 case EVENT_N1S1: 237 case EVENT_N1S2: 238 case EVENT_N2S2: 239 case EVENT_N2S3: 240 case LINK: 241 case TAG_N0S1: 242 case TAG_KEYED_N0S2: 243 case TAG_KEYED_N2S1: 244 case TAG_KEYED_N1S1: 245 case TAG_N1S0: 246 case TAG_N1S1: 247 break; 248 } 249 throw new AssertionError(end.getOperation()); 250 } 251 } 252