GenerateStatsPhases.py (12268B)
1 # This Source Code Form is subject to the terms of the Mozilla Public 2 # License, v. 2.0. If a copy of the MPL was not distributed with this 3 # file, You can obtain one at http://mozilla.org/MPL/2.0/. 4 5 # flake8: noqa: F821 6 7 # Generate graph structures for GC statistics recording. 8 # 9 # Stats phases are nested and form a directed acyclic graph starting 10 # from a set of root phases. Importantly, a phase may appear under more 11 # than one parent phase. 12 # 13 # For example, the following arrangement is possible: 14 # 15 # +---+ 16 # | A | 17 # +---+ 18 # | 19 # +-------+-------+ 20 # | | | 21 # v v v 22 # +---+ +---+ +---+ 23 # | B | | C | | D | 24 # +---+ +---+ +---+ 25 # | | 26 # +---+---+ 27 # | 28 # v 29 # +---+ 30 # | E | 31 # +---+ 32 # 33 # This graph is expanded into a tree (or really a forest) and phases 34 # with multiple parents are duplicated. 35 # 36 # For example, the input example above would be expanded to: 37 # 38 # +---+ 39 # | A | 40 # +---+ 41 # | 42 # +-------+-------+ 43 # | | | 44 # v v v 45 # +---+ +---+ +---+ 46 # | B | | C | | D | 47 # +---+ +---+ +---+ 48 # | | 49 # v v 50 # +---+ +---+ 51 # | E | | E'| 52 # +---+ +---+ 53 54 # NOTE: If you add new phases here the current next phase kind number can be 55 # found at the end of js/src/gc/StatsPhasesGenerated.inc 56 57 import collections 58 import re 59 60 61 class PhaseKind: 62 def __init__(self, name, descr, children=[]): 63 self.name = name 64 self.descr = descr 65 # For telemetry 66 self.children = children 67 68 69 AllPhaseKinds = [] 70 PhaseKindsByName = dict() 71 72 73 def addPhaseKind(name, descr, children=[]): 74 assert name not in PhaseKindsByName 75 phaseKind = PhaseKind(name, descr, children) 76 AllPhaseKinds.append(phaseKind) 77 PhaseKindsByName[name] = phaseKind 78 return phaseKind 79 80 81 def getPhaseKind(name): 82 return PhaseKindsByName[name] 83 84 85 PhaseKindGraphRoots = [ 86 addPhaseKind("MUTATOR", "Mutator Running"), 87 addPhaseKind("GC_BEGIN", "Begin Callback"), 88 addPhaseKind( 89 "EVICT_NURSERY_FOR_MAJOR_GC", 90 "Evict Nursery For Major GC", 91 [ 92 addPhaseKind( 93 "MARK_ROOTS", 94 "Mark Roots", 95 [ 96 addPhaseKind("MARK_CCWS", "Mark Cross Compartment Wrappers"), 97 addPhaseKind("MARK_STACK", "Mark C and JS stacks"), 98 addPhaseKind("MARK_RUNTIME_DATA", "Mark Runtime-wide Data"), 99 addPhaseKind("MARK_EMBEDDING", "Mark Embedding"), 100 ], 101 ) 102 ], 103 ), 104 addPhaseKind("WAIT_BACKGROUND_THREAD", "Wait Background Thread"), 105 addPhaseKind( 106 "PREPARE", 107 "Prepare For Collection", 108 [ 109 addPhaseKind("UNMARK", "Unmark"), 110 addPhaseKind("UNMARK_WEAKMAPS", "Unmark WeakMaps"), 111 addPhaseKind("MARK_DISCARD_CODE", "Mark Discard Code"), 112 addPhaseKind("RELAZIFY_FUNCTIONS", "Relazify Functions"), 113 addPhaseKind("PURGE", "Purge"), 114 addPhaseKind("PURGE_PROP_MAP_TABLES", "Purge PropMapTables"), 115 addPhaseKind("PURGE_SOURCE_URLS", "Purge Source URLs"), 116 addPhaseKind( 117 "PURGE_WRAPPER_PRESERVATION", "Purge Wrapper Preservation buffers" 118 ), 119 addPhaseKind("JOIN_PARALLEL_TASKS", "Join Parallel Tasks"), 120 ], 121 ), 122 addPhaseKind( 123 "MARK", 124 "Mark", 125 [ 126 getPhaseKind("MARK_ROOTS"), 127 addPhaseKind("MARK_DELAYED", "Mark Delayed"), 128 addPhaseKind( 129 "MARK_WEAK", 130 "Mark Weak", 131 [ 132 getPhaseKind("MARK_DELAYED"), 133 addPhaseKind("MARK_GRAY_WEAK", "Mark Gray and Weak"), 134 ], 135 ), 136 addPhaseKind("MARK_INCOMING_GRAY", "Mark Incoming Gray Pointers"), 137 addPhaseKind("MARK_GRAY", "Mark Gray"), 138 addPhaseKind( 139 "PARALLEL_MARK", 140 "Parallel marking", 141 [ 142 getPhaseKind("JOIN_PARALLEL_TASKS"), 143 # The following are only used for parallel phase times: 144 addPhaseKind("PARALLEL_MARK_MARK", "Parallel marking work"), 145 addPhaseKind("PARALLEL_MARK_WAIT", "Waiting for work"), 146 addPhaseKind("PARALLEL_MARK_OTHER", "Parallel marking overhead"), 147 ], 148 ), 149 ], 150 ), 151 addPhaseKind( 152 "SWEEP", 153 "Sweep", 154 [ 155 getPhaseKind("MARK"), 156 addPhaseKind( 157 "FINALIZE_START", 158 "Finalize Start Callbacks", 159 [ 160 addPhaseKind("WEAK_ZONES_CALLBACK", "Per-Slice Weak Callback"), 161 addPhaseKind( 162 "WEAK_COMPARTMENT_CALLBACK", "Per-Compartment Weak Callback" 163 ), 164 ], 165 ), 166 addPhaseKind("UPDATE_ATOMS_BITMAP", "Sweep Atoms Bitmap"), 167 addPhaseKind("SWEEP_ATOMS_TABLE", "Sweep Atoms Table"), 168 addPhaseKind( 169 "SWEEP_COMPARTMENTS", 170 "Sweep Compartments", 171 [ 172 addPhaseKind("SWEEP_JIT_SCRIPTS", "Sweep JitScripts"), 173 addPhaseKind("SWEEP_INNER_VIEWS", "Sweep Inner Views"), 174 addPhaseKind( 175 "SWEEP_CC_WRAPPER", "Sweep Cross Compartment Wrappers" 176 ), 177 addPhaseKind("SWEEP_BASE_SHAPE", "Sweep Base Shapes"), 178 addPhaseKind("SWEEP_INITIAL_SHAPE", "Sweep Initial Shapes"), 179 addPhaseKind("SWEEP_REGEXP", "Sweep Regexps"), 180 addPhaseKind("SWEEP_COMPRESSION", "Sweep Compression Tasks"), 181 addPhaseKind("SWEEP_WEAKMAPS", "Sweep WeakMaps"), 182 addPhaseKind("SWEEP_UNIQUEIDS", "Sweep Unique IDs"), 183 addPhaseKind("SWEEP_WEAK_POINTERS", "Sweep Weak Pointers"), 184 addPhaseKind( 185 "SWEEP_FINALIZATION_OBSERVERS", 186 "Sweep FinalizationRegistries and WeakRefs", 187 ), 188 addPhaseKind("SWEEP_JIT_DATA", "Sweep JIT Data"), 189 addPhaseKind("SWEEP_WEAK_CACHES", "Sweep Weak Caches"), 190 addPhaseKind("SWEEP_MISC", "Sweep Miscellaneous"), 191 getPhaseKind("JOIN_PARALLEL_TASKS"), 192 ], 193 ), 194 addPhaseKind("SWEEP_PROP_MAP", "Sweep PropMap Tree"), 195 addPhaseKind("FINALIZE_END", "Finalize End Callback"), 196 addPhaseKind("DESTROY", "Deallocate"), 197 getPhaseKind("JOIN_PARALLEL_TASKS"), 198 addPhaseKind("FIND_DEAD_COMPARTMENTS", "Find Dead Compartments"), 199 ], 200 ), 201 addPhaseKind( 202 "COMPACT", 203 "Compact", 204 [ 205 addPhaseKind("COMPACT_MOVE", "Compact Move"), 206 addPhaseKind( 207 "COMPACT_UPDATE", 208 "Compact Update", 209 [ 210 getPhaseKind("MARK_ROOTS"), 211 addPhaseKind("COMPACT_UPDATE_CELLS", "Compact Update Cells"), 212 getPhaseKind("JOIN_PARALLEL_TASKS"), 213 ], 214 ), 215 ], 216 ), 217 addPhaseKind("DECOMMIT", "Decommit"), 218 addPhaseKind("GC_END", "End Callback"), 219 addPhaseKind( 220 "MINOR_GC", 221 "All Minor GCs", 222 [ 223 getPhaseKind("MARK_ROOTS"), 224 ], 225 ), 226 addPhaseKind( 227 "EVICT_NURSERY", 228 "Minor GCs to Evict Nursery", 229 [ 230 getPhaseKind("MARK_ROOTS"), 231 ], 232 ), 233 addPhaseKind( 234 "TRACE_HEAP", 235 "Trace Heap", 236 [ 237 getPhaseKind("MARK_ROOTS"), 238 ], 239 ), 240 ] 241 242 243 class Phase: 244 # Expand the DAG into a tree, duplicating phases which have more than 245 # one parent. 246 def __init__(self, phaseKind, parent): 247 self.phaseKind = phaseKind 248 self.parent = parent 249 self.depth = parent.depth + 1 if parent else 0 250 self.children = [] 251 self.nextSibling = None 252 self.nextInPhaseKind = None 253 254 self.path = re.sub(r"\W+", "_", phaseKind.name.lower()) 255 if parent is not None: 256 self.path = parent.path + "." + self.path 257 258 259 def expandPhases(): 260 phases = [] 261 phasesForKind = collections.defaultdict(list) 262 263 def traverse(phaseKind, parent): 264 ep = Phase(phaseKind, parent) 265 phases.append(ep) 266 267 # Update list of expanded phases for this phase kind. 268 if phasesForKind[phaseKind]: 269 phasesForKind[phaseKind][-1].nextInPhaseKind = ep 270 phasesForKind[phaseKind].append(ep) 271 272 # Recurse over children. 273 for child in phaseKind.children: 274 child_ep = traverse(child, ep) 275 if ep.children: 276 ep.children[-1].nextSibling = child_ep 277 ep.children.append(child_ep) 278 return ep 279 280 for phaseKind in PhaseKindGraphRoots: 281 traverse(phaseKind, None) 282 283 return phases, phasesForKind 284 285 286 AllPhases, PhasesForPhaseKind = expandPhases() 287 288 # Name phases based on phase kind name and index if there are multiple phases 289 # corresponding to a single phase kind. 290 291 for phaseKind in AllPhaseKinds: 292 phases = PhasesForPhaseKind[phaseKind] 293 if len(phases) == 1: 294 phases[0].name = "%s" % phaseKind.name 295 else: 296 for index, phase in enumerate(phases): 297 phase.name = "%s_%d" % (phaseKind.name, index + 1) 298 299 # Find the maximum phase nesting. 300 MaxPhaseNesting = max(phase.depth for phase in AllPhases) + 1 301 302 # Generate code. 303 304 305 def writeList(out, items): 306 if items: 307 out.write(",\n".join(" " + item for item in items) + "\n") 308 309 310 def writeEnumClass(out, name, type, items, extraItems): 311 items = ["FIRST"] + list(items) + ["LIMIT"] + list(extraItems) 312 items[1] += " = " + items[0] 313 out.write("enum class %s : %s {\n" % (name, type)) 314 writeList(out, items) 315 out.write("};\n") 316 317 318 def generateHeader(out): 319 # 320 # Generate PhaseKind enum. 321 # 322 phaseKindNames = map(lambda phaseKind: phaseKind.name, AllPhaseKinds) 323 extraPhaseKinds = [ 324 "NONE = LIMIT", 325 "EXPLICIT_SUSPENSION = LIMIT", 326 "IMPLICIT_SUSPENSION", 327 ] 328 writeEnumClass(out, "PhaseKind", "uint8_t", phaseKindNames, extraPhaseKinds) 329 out.write("\n") 330 331 # 332 # Generate Phase enum. 333 # 334 phaseNames = map(lambda phase: phase.name, AllPhases) 335 extraPhases = ["NONE = LIMIT", "EXPLICIT_SUSPENSION = LIMIT", "IMPLICIT_SUSPENSION"] 336 writeEnumClass(out, "Phase", "uint8_t", phaseNames, extraPhases) 337 out.write("\n") 338 339 # 340 # Generate MAX_PHASE_NESTING constant. 341 # 342 out.write("static const size_t MAX_PHASE_NESTING = %d;\n" % MaxPhaseNesting) 343 344 345 def generateCpp(out): 346 # 347 # Generate the PhaseKindInfo table. 348 # 349 out.write("static constexpr PhaseKindTable phaseKinds = {\n") 350 for phaseKind in AllPhaseKinds: 351 phase = PhasesForPhaseKind[phaseKind][0] 352 out.write( 353 ' /* PhaseKind::%s */ PhaseKindInfo { Phase::%s, "%s" },\n' 354 % (phaseKind.name, phase.name, phaseKind.name) 355 ) 356 out.write("};\n") 357 out.write("\n") 358 359 # 360 # Generate the PhaseInfo tree. 361 # 362 def name(phase): 363 return "Phase::" + phase.name if phase else "Phase::NONE" 364 365 out.write("static constexpr PhaseTable phases = {\n") 366 for phase in AllPhases: 367 firstChild = phase.children[0] if phase.children else None 368 phaseKind = phase.phaseKind 369 out.write( 370 ' /* %s */ PhaseInfo { %s, %s, %s, %s, PhaseKind::%s, %d, "%s", "%s" },\n' 371 % ( # NOQA: E501 372 name(phase), 373 name(phase.parent), 374 name(firstChild), 375 name(phase.nextSibling), 376 name(phase.nextInPhaseKind), 377 phaseKind.name, 378 phase.depth, 379 phaseKind.descr, 380 phase.path, 381 ) 382 ) 383 out.write("};\n")