Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 1 | # This file is part of pybootchartgui. |
| 2 | |
| 3 | # pybootchartgui is free software: you can redistribute it and/or modify |
| 4 | # it under the terms of the GNU General Public License as published by |
| 5 | # the Free Software Foundation, either version 3 of the License, or |
| 6 | # (at your option) any later version. |
| 7 | |
| 8 | # pybootchartgui is distributed in the hope that it will be useful, |
| 9 | # but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 10 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 11 | # GNU General Public License for more details. |
| 12 | |
| 13 | # You should have received a copy of the GNU General Public License |
| 14 | # along with pybootchartgui. If not, see <http://www.gnu.org/licenses/>. |
| 15 | |
| 16 | class ProcessTree: |
| 17 | """ProcessTree encapsulates a process tree. The tree is built from log files |
| 18 | retrieved during the boot process. When building the process tree, it is |
| 19 | pruned and merged in order to be able to visualize it in a comprehensible |
| 20 | manner. |
| 21 | |
| 22 | The following pruning techniques are used: |
| 23 | |
| 24 | * idle processes that keep running during the last process sample |
| 25 | (which is a heuristic for a background processes) are removed, |
| 26 | * short-lived processes (i.e. processes that only live for the |
| 27 | duration of two samples or less) are removed, |
| 28 | * the processes used by the boot logger are removed, |
| 29 | * exploders (i.e. processes that are known to spawn huge meaningless |
| 30 | process subtrees) have their subtrees merged together, |
| 31 | * siblings (i.e. processes with the same command line living |
| 32 | concurrently -- thread heuristic) are merged together, |
| 33 | * process runs (unary trees with processes sharing the command line) |
| 34 | are merged together. |
| 35 | |
| 36 | """ |
| 37 | LOGGER_PROC = 'bootchart-colle' |
| 38 | EXPLODER_PROCESSES = set(['hwup']) |
| 39 | |
| 40 | def __init__(self, writer, kernel, psstats, sample_period, |
| 41 | monitoredApp, prune, idle, taskstats, |
| 42 | accurate_parentage, for_testing = False): |
| 43 | self.writer = writer |
| 44 | self.process_tree = [] |
| 45 | self.taskstats = taskstats |
| 46 | if psstats is None: |
| 47 | process_list = kernel |
| 48 | elif kernel is None: |
| 49 | process_list = psstats.process_map.values() |
| 50 | else: |
| 51 | process_list = list(kernel) + list(psstats.process_map.values()) |
| 52 | self.process_list = sorted(process_list, key = lambda p: p.pid) |
| 53 | self.sample_period = sample_period |
| 54 | |
| 55 | self.build() |
| 56 | if not accurate_parentage: |
| 57 | self.update_ppids_for_daemons(self.process_list) |
| 58 | |
| 59 | self.start_time = self.get_start_time(self.process_tree) |
| 60 | self.end_time = self.get_end_time(self.process_tree) |
| 61 | self.duration = self.end_time - self.start_time |
| 62 | self.idle = idle |
| 63 | |
| 64 | if for_testing: |
| 65 | return |
| 66 | |
| 67 | removed = self.merge_logger(self.process_tree, self.LOGGER_PROC, monitoredApp, False) |
| 68 | writer.status("merged %i logger processes" % removed) |
| 69 | |
| 70 | if prune: |
| 71 | p_processes = self.prune(self.process_tree, None) |
| 72 | p_exploders = self.merge_exploders(self.process_tree, self.EXPLODER_PROCESSES) |
| 73 | p_threads = self.merge_siblings(self.process_tree) |
| 74 | p_runs = self.merge_runs(self.process_tree) |
| 75 | writer.status("pruned %i process, %i exploders, %i threads, and %i runs" % (p_processes, p_exploders, p_threads, p_runs)) |
| 76 | |
| 77 | self.sort(self.process_tree) |
| 78 | |
| 79 | self.start_time = self.get_start_time(self.process_tree) |
| 80 | self.end_time = self.get_end_time(self.process_tree) |
| 81 | self.duration = self.end_time - self.start_time |
| 82 | |
| 83 | self.num_proc = self.num_nodes(self.process_tree) |
| 84 | |
| 85 | def build(self): |
| 86 | """Build the process tree from the list of top samples.""" |
| 87 | self.process_tree = [] |
| 88 | for proc in self.process_list: |
| 89 | if not proc.parent: |
| 90 | self.process_tree.append(proc) |
| 91 | else: |
| 92 | proc.parent.child_list.append(proc) |
| 93 | |
| 94 | def sort(self, process_subtree): |
| 95 | """Sort process tree.""" |
| 96 | for p in process_subtree: |
| 97 | p.child_list.sort(key = lambda p: p.pid) |
| 98 | self.sort(p.child_list) |
| 99 | |
| 100 | def num_nodes(self, process_list): |
| 101 | "Counts the number of nodes in the specified process tree.""" |
| 102 | nodes = 0 |
| 103 | for proc in process_list: |
| 104 | nodes = nodes + self.num_nodes(proc.child_list) |
| 105 | return nodes + len(process_list) |
| 106 | |
| 107 | def get_start_time(self, process_subtree): |
| 108 | """Returns the start time of the process subtree. This is the start |
| 109 | time of the earliest process. |
| 110 | |
| 111 | """ |
| 112 | if not process_subtree: |
| 113 | return 100000000 |
| 114 | return min( [min(proc.start_time, self.get_start_time(proc.child_list)) for proc in process_subtree] ) |
| 115 | |
| 116 | def get_end_time(self, process_subtree): |
| 117 | """Returns the end time of the process subtree. This is the end time |
| 118 | of the last collected sample. |
| 119 | |
| 120 | """ |
| 121 | if not process_subtree: |
| 122 | return -100000000 |
| 123 | return max( [max(proc.start_time + proc.duration, self.get_end_time(proc.child_list)) for proc in process_subtree] ) |
| 124 | |
| 125 | def get_max_pid(self, process_subtree): |
| 126 | """Returns the max PID found in the process tree.""" |
| 127 | if not process_subtree: |
| 128 | return -100000000 |
| 129 | return max( [max(proc.pid, self.get_max_pid(proc.child_list)) for proc in process_subtree] ) |
| 130 | |
| 131 | def update_ppids_for_daemons(self, process_list): |
| 132 | """Fedora hack: when loading the system services from rc, runuser(1) |
| 133 | is used. This sets the PPID of all daemons to 1, skewing |
| 134 | the process tree. Try to detect this and set the PPID of |
| 135 | these processes the PID of rc. |
| 136 | |
| 137 | """ |
| 138 | rcstartpid = -1 |
| 139 | rcendpid = -1 |
| 140 | rcproc = None |
| 141 | for p in process_list: |
| 142 | if p.cmd == "rc" and p.ppid // 1000 == 1: |
| 143 | rcproc = p |
| 144 | rcstartpid = p.pid |
| 145 | rcendpid = self.get_max_pid(p.child_list) |
| 146 | if rcstartpid != -1 and rcendpid != -1: |
| 147 | for p in process_list: |
| 148 | if p.pid > rcstartpid and p.pid < rcendpid and p.ppid // 1000 == 1: |
| 149 | p.ppid = rcstartpid |
| 150 | p.parent = rcproc |
| 151 | for p in process_list: |
| 152 | p.child_list = [] |
| 153 | self.build() |
| 154 | |
| 155 | def prune(self, process_subtree, parent): |
| 156 | """Prunes the process tree by removing idle processes and processes |
| 157 | that only live for the duration of a single top sample. Sibling |
| 158 | processes with the same command line (i.e. threads) are merged |
| 159 | together. This filters out sleepy background processes, short-lived |
| 160 | processes and bootcharts' analysis tools. |
| 161 | """ |
| 162 | def is_idle_background_process_without_children(p): |
| 163 | process_end = p.start_time + p.duration |
| 164 | return not p.active and \ |
| 165 | process_end >= self.start_time + self.duration and \ |
| 166 | p.start_time > self.start_time and \ |
| 167 | p.duration > 0.9 * self.duration and \ |
| 168 | self.num_nodes(p.child_list) == 0 |
| 169 | |
| 170 | num_removed = 0 |
| 171 | idx = 0 |
| 172 | while idx < len(process_subtree): |
| 173 | p = process_subtree[idx] |
| 174 | if parent != None or len(p.child_list) == 0: |
| 175 | |
| 176 | prune = False |
| 177 | if is_idle_background_process_without_children(p): |
| 178 | prune = True |
| 179 | elif p.duration <= 2 * self.sample_period: |
| 180 | # short-lived process |
| 181 | prune = True |
| 182 | |
| 183 | if prune: |
| 184 | process_subtree.pop(idx) |
| 185 | for c in p.child_list: |
| 186 | process_subtree.insert(idx, c) |
| 187 | num_removed += 1 |
| 188 | continue |
| 189 | else: |
| 190 | num_removed += self.prune(p.child_list, p) |
| 191 | else: |
| 192 | num_removed += self.prune(p.child_list, p) |
| 193 | idx += 1 |
| 194 | |
| 195 | return num_removed |
| 196 | |
| 197 | def merge_logger(self, process_subtree, logger_proc, monitored_app, app_tree): |
| 198 | """Merges the logger's process subtree. The logger will typically |
| 199 | spawn lots of sleep and cat processes, thus polluting the |
| 200 | process tree. |
| 201 | |
| 202 | """ |
| 203 | num_removed = 0 |
| 204 | for p in process_subtree: |
| 205 | is_app_tree = app_tree |
| 206 | if logger_proc == p.cmd and not app_tree: |
| 207 | is_app_tree = True |
| 208 | num_removed += self.merge_logger(p.child_list, logger_proc, monitored_app, is_app_tree) |
| 209 | # don't remove the logger itself |
| 210 | continue |
| 211 | |
| 212 | if app_tree and monitored_app != None and monitored_app == p.cmd: |
| 213 | is_app_tree = False |
| 214 | |
| 215 | if is_app_tree: |
| 216 | for child in p.child_list: |
| 217 | self.merge_processes(p, child) |
| 218 | num_removed += 1 |
| 219 | p.child_list = [] |
| 220 | else: |
| 221 | num_removed += self.merge_logger(p.child_list, logger_proc, monitored_app, is_app_tree) |
| 222 | return num_removed |
| 223 | |
| 224 | def merge_exploders(self, process_subtree, processes): |
| 225 | """Merges specific process subtrees (used for processes which usually |
| 226 | spawn huge meaningless process trees). |
| 227 | |
| 228 | """ |
| 229 | num_removed = 0 |
| 230 | for p in process_subtree: |
| 231 | if processes in processes and len(p.child_list) > 0: |
| 232 | subtreemap = self.getProcessMap(p.child_list) |
| 233 | for child in subtreemap.values(): |
| 234 | self.merge_processes(p, child) |
| 235 | num_removed += len(subtreemap) |
| 236 | p.child_list = [] |
| 237 | p.cmd += " (+)" |
| 238 | else: |
| 239 | num_removed += self.merge_exploders(p.child_list, processes) |
| 240 | return num_removed |
| 241 | |
| 242 | def merge_siblings(self, process_subtree): |
| 243 | """Merges thread processes. Sibling processes with the same command |
| 244 | line are merged together. |
| 245 | |
| 246 | """ |
| 247 | num_removed = 0 |
| 248 | idx = 0 |
| 249 | while idx < len(process_subtree)-1: |
| 250 | p = process_subtree[idx] |
| 251 | nextp = process_subtree[idx+1] |
| 252 | if nextp.cmd == p.cmd: |
| 253 | process_subtree.pop(idx+1) |
| 254 | idx -= 1 |
| 255 | num_removed += 1 |
| 256 | p.child_list.extend(nextp.child_list) |
| 257 | self.merge_processes(p, nextp) |
| 258 | num_removed += self.merge_siblings(p.child_list) |
| 259 | idx += 1 |
| 260 | if len(process_subtree) > 0: |
| 261 | p = process_subtree[-1] |
| 262 | num_removed += self.merge_siblings(p.child_list) |
| 263 | return num_removed |
| 264 | |
| 265 | def merge_runs(self, process_subtree): |
| 266 | """Merges process runs. Single child processes which share the same |
| 267 | command line with the parent are merged. |
| 268 | |
| 269 | """ |
| 270 | num_removed = 0 |
| 271 | idx = 0 |
| 272 | while idx < len(process_subtree): |
| 273 | p = process_subtree[idx] |
| 274 | if len(p.child_list) == 1 and p.child_list[0].cmd == p.cmd: |
| 275 | child = p.child_list[0] |
| 276 | p.child_list = list(child.child_list) |
| 277 | self.merge_processes(p, child) |
| 278 | num_removed += 1 |
| 279 | continue |
| 280 | num_removed += self.merge_runs(p.child_list) |
| 281 | idx += 1 |
| 282 | return num_removed |
| 283 | |
| 284 | def merge_processes(self, p1, p2): |
| 285 | """Merges two process' samples.""" |
| 286 | p1.samples.extend(p2.samples) |
| 287 | p1.samples.sort( key = lambda p: p.time ) |
| 288 | p1time = p1.start_time |
| 289 | p2time = p2.start_time |
| 290 | p1.start_time = min(p1time, p2time) |
| 291 | pendtime = max(p1time + p1.duration, p2time + p2.duration) |
| 292 | p1.duration = pendtime - p1.start_time |