diff options
author | George Burgess IV <gbiv@google.com> | 2018-12-06 16:16:11 -0800 |
---|---|---|
committer | chrome-bot <chrome-bot@chromium.org> | 2018-12-08 16:49:50 -0800 |
commit | b0ffeed84e6f3b49482259cdf0ed94baf46209df (patch) | |
tree | 575e2d2657524c1621851b0c37c354219958cfc9 /afdo_redaction | |
parent | c1baa8ddb3ef0e674bf6634f4522fe338bee5fa8 (diff) | |
download | toolchain-utils-b0ffeed84e6f3b49482259cdf0ed94baf46209df.tar.gz |
[toolchain-utils] Add AFDO profile redaction script
This adds our AFDO profile redaction script, and a test for it.
Explanation of what this does/etc. is in the script.
BUG=None
TEST=Script itself has been used for many experiments; newly-added tests
pass.
Change-Id: I4bb02a7db2df1733b7f8a550661aab61b7cad29b
Reviewed-on: https://chromium-review.googlesource.com/1366448
Commit-Ready: George Burgess <gbiv@chromium.org>
Tested-by: George Burgess <gbiv@chromium.org>
Reviewed-by: Manoj Gupta <manojgupta@chromium.org>
Diffstat (limited to 'afdo_redaction')
-rwxr-xr-x | afdo_redaction/redact_profile.py | 236 | ||||
-rwxr-xr-x | afdo_redaction/redact_profile_test.py | 134 |
2 files changed, 370 insertions, 0 deletions
diff --git a/afdo_redaction/redact_profile.py b/afdo_redaction/redact_profile.py new file mode 100755 index 00000000..96375fee --- /dev/null +++ b/afdo_redaction/redact_profile.py @@ -0,0 +1,236 @@ +#!/usr/bin/env python2 +# -*- coding: utf-8 -*- +# Copyright 2018 The Chromium OS Authors. All rights reserved. +# Use of this source code is governed by a BSD-style license that can be +# found in the LICENSE file. + +"""Script to redact apparent ICF'ed symbolsfrom textual AFDO profiles. + +AFDO sampling and ICF have an unfortunate interaction that causes a huge +inflation in sample counts. Essentially, if you have N functions ICF'ed to the +same location, one AFDO sample in any of those N functions will count as one +sample in *each* of those N functions. + +In practice, there are a few forms of function bodies that are very heavily +ICF'ed (e.g. `ret`, `xor %eax, %eax; ret`, destructors for widely-used types +like std::map...). Recording 28,000 samples across all N thousand logical +functions that point to the same body really hurts our AFDO numbers, given that +our actual sample count across all of Chrome is something around 10,000,000. +(No, really, these are actual numbers. In practice, at the time of writing, +this script eliminates >90% of our AFDO samples by count. Sometimes as high as +98%.) + +It reads a textual AFDO profile from stdin, and prints a 'fixed' version of it +to stdout. A summary of what the script actually did is printed to stderr. +""" + +from __future__ import division, print_function + +import collections +import re +import sys + +def _count_samples(samples): + """Count the total number of samples in a function.""" + line_re = re.compile(r'^(\s*)\d+(?:\.\d+)?: (\d+)\s*$') + + top_level_samples = 0 + all_samples = 0 + for line in samples: + m = line_re.match(line) + if not m: + continue + + spaces, n = m.groups() + n = int(n) + all_samples += n + if len(spaces) == 1: + top_level_samples += n + + return top_level_samples, all_samples + + +# A ProfileRecord is a set of samples for a top-level symbol in a textual AFDO +# profile. function_line is the top line of said function, and `samples` is +# a list of all of the sample lines below that. +# +# We rely on the format of these strings in some places in this script. For +# reference, a full function sample will look something like: +# +# _ZNK5blink10PaintLayer19GetCompositingStateEv:4530:185 +# 6: 83 +# 15: 126 +# 62832: 126 +# 6: _ZNK5blink10PaintLayer14GroupedMappingEv:2349 +# 1: 206 +# 1: _ZNK5blink10PaintLayer14GroupedMappersEv:2060 +# 1: 206 +# 11: _ZNK5blink10PaintLayer25GetCompositedLayerMappingEv:800 +# 2.1: 80 +# +# +# In that case, function_line is +# '_ZNK5blink10PaintLayer19GetCompositingStateEv:4530:185', and samples will be +# every line below that. +# +# Function lines look like; +# function_symbol:entry_count:dont_care +# +# And samples look like one of: +# arbitrary_number: sample_count +# arbitrary_number: inlined_function_symbol:inlined_entry_count +ProfileRecord = collections.namedtuple('ProfileRecord', + ['function_line', 'samples']) + + +def _normalize_samples(samples): + """Normalizes the samples in the given function body. + + Normalization just means that we redact inlined function names. This is + done so that a bit of templating doesn't make two function bodies look + distinct. Namely: + + template <typename T> + __attribute__((noinline)) + int getNumber() { return 1; } + + template <typename T> + __attribute__((noinline)) + int getNumberIndirectly() { return getNumber<T>(); } + + int main() { + return getNumber<int>() + getNumber<float>(); + } + + If the profile has the mangled name for getNumber<float> in + getNumberIndirectly<float> (and similar for <int>), we'll consider them to + be distinct when they're not. + """ + + # I'm not actually sure if this ends up being an issue in practice, but it's + # simple enough to guard against. + inlined_re = re.compile(r'(^\s*\d+): [^:]+:(\s*\d+)\s*$') + result = [] + for s in samples: + m = inlined_re.match(s) + if m: + result.append('%s: __REDACTED__:%s' % m.groups()) + else: + result.append(s) + return tuple(result) + + +def _read_textual_afdo_profile(stream): + """Parses an AFDO profile from a line stream into ProfileRecords.""" + # ProfileRecords are actually nested, due to inlining. For the purpose of + # this script, that doesn't matter. + lines = (line.rstrip() for line in stream) + function_line = None + samples = [] + for line in lines: + if not line: + continue + + if line[0].isspace(): + assert function_line is not None, "sample exists outside of a function?" + samples.append(line) + continue + + if function_line is not None: + yield ProfileRecord(function_line=function_line, samples=tuple(samples)) + function_line = line + samples = [] + + if function_line is not None: + yield ProfileRecord(function_line=function_line, samples=tuple(samples)) + + +# The default of 100 is arbitrarily selected, but it does make the overwhelming +# majority of obvious sample duplication disappear. +# +# We experimented shortly with an nm-powered version of this script (rather +# than structural matching, we'd see which functions mapped to the same literal +# address). Running this with a high value (100) for max_repeats produced +# results basically indistinguishable from nm, so ... +# +# Non-nm based approaches are superior because they don't require any prior +# build artifacts; just an AFDO profile. +def dedup_records(profile_records, summary_file, max_repeats=100): + """Removes heavily duplicated records from profile_records. + + profile_records is expected to be an iterable of ProfileRecord. + max_repeats ia how many functions must share identical bodies for us to + consider it 'heavily duplicated' and remove the results. + """ + + # Build a mapping of function structure -> list of functions with identical + # structure and sample counts + counts = collections.defaultdict(list) + for record in profile_records: + counts[_normalize_samples(record.samples)].append(record) + + # Be sure that we didn't see any duplicate functions, since that's bad... + total_functions_recorded = sum(len(records) + for records in counts.itervalues()) + + unique_function_names = set(record.function_line.split(':')[0] + for records in counts.itervalues() + for record in records) + + assert len(unique_function_names) == total_functions_recorded, \ + 'duplicate function names?' + + num_kept = 0 + num_samples_kept = 0 + num_top_samples_kept = 0 + num_total = 0 + num_samples_total = 0 + num_top_samples_total = 0 + + for normalized_samples, records in counts.iteritems(): + top_sample_count, all_sample_count = _count_samples(normalized_samples) + top_sample_count *= len(records) + all_sample_count *= len(records) + + num_total += len(records) + num_samples_total += all_sample_count + num_top_samples_total += top_sample_count + + if len(records) >= max_repeats: + continue + + num_kept += len(records) + num_samples_kept += all_sample_count + num_top_samples_kept += top_sample_count + for record in records: + yield record + + print('Retained {:,}/{:,} functions'.format(num_kept, num_total), + file=summary_file) + print('Retained {:,}/{:,} samples, total'.format(num_samples_kept, + num_samples_total), + file=summary_file) + print('Retained {:,}/{:,} top-level samples' \ + .format(num_top_samples_kept, num_top_samples_total), + file=summary_file) + + +def run(profile_input_file, summary_output_file, profile_output_file): + profile_records = _read_textual_afdo_profile(profile_input_file) + + # Sort this so we get deterministic output. AFDO doesn't care what order it's + # in. + deduped = sorted(dedup_records(profile_records, summary_output_file), + key=lambda r: r.function_line) + for function_line, samples in deduped: + print(function_line, file=profile_output_file) + print('\n'.join(samples), file=profile_output_file) + + +def _main(): + run(profile_input_file=sys.stdin, summary_output_file=sys.stderr, + profile_output_file=sys.stdout) + + +if __name__ == '__main__': + _main() diff --git a/afdo_redaction/redact_profile_test.py b/afdo_redaction/redact_profile_test.py new file mode 100755 index 00000000..5ccde3e4 --- /dev/null +++ b/afdo_redaction/redact_profile_test.py @@ -0,0 +1,134 @@ +#!/usr/bin/env python2 +# -*- coding: utf-8 -*- +# Copyright 2018 The Chromium OS Authors. All rights reserved. +# Use of this source code is governed by a BSD-style license that can be +# found in the LICENSE file. + +"""Tests for redact_profile.py.""" + +from __future__ import division, print_function + +import StringIO +import unittest + +import redact_profile + +_redact_limit = redact_profile.dedup_records.func_defaults[0] + + +def _redact(input_lines, summary_to=None): + if isinstance(input_lines, str): + input_lines = input_lines.splitlines() + + if summary_to is None: + summary_to = StringIO.StringIO() + + output_to = StringIO.StringIO() + redact_profile.run(profile_input_file=input_lines, + summary_output_file=summary_to, + profile_output_file=output_to) + return output_to.getvalue() + + +def _redact_with_summary(input_lines): + summary = StringIO.StringIO() + result = _redact(input_lines, summary_to=summary) + return result, summary.getvalue() + + +def _generate_repeated_function_body(repeats, fn_name='_some_name'): + # Arbitrary function body ripped from a textual AFDO profile. + function_header = fn_name + ':1234:185' + function_body = [ + ' 6: 83', + ' 15: 126', + ' 62832: 126', + ' 6: _ZNK5blink10PaintLayer14GroupedMappingEv:2349', + ' 1: 206', + ' 1: _ZNK5blink10PaintLayer14GroupedMappersEv:2060', + ' 1: 206', + ' 11: _ZNK5blink10PaintLayer25GetCompositedLayerMappingEv:800', + ' 2.1: 80', + ] + + # Be sure to zfill this, so the functions are output in sorted order. + num_width = len(str(repeats)) + + lines = [] + for i in xrange(repeats): + num = str(i).zfill(num_width) + lines.append(num + function_header) + lines.extend(function_body) + return lines + + +class Tests(unittest.TestCase): + """All of our tests for redact_profile.""" + def test_no_input_works(self): + self.assertEqual(_redact(''), '') + + def test_single_function_works(self): + lines = _generate_repeated_function_body(1) + result_file = '\n'.join(lines) + '\n' + self.assertEqual(_redact(lines), result_file) + + def test_duplicate_of_single_function_works(self): + lines = _generate_repeated_function_body(2) + result_file = '\n'.join(lines) + '\n' + self.assertEqual(_redact(lines), result_file) + + def test_not_too_many_duplicates_of_single_function_redacts_none(self): + lines = _generate_repeated_function_body(_redact_limit - 1) + result_file = '\n'.join(lines) + '\n' + self.assertEqual(_redact(lines), result_file) + + def test_many_duplicates_of_single_function_redacts_them_all(self): + lines = _generate_repeated_function_body(_redact_limit) + self.assertEqual(_redact(lines), '') + + def test_many_duplicates_of_single_function_leaves_other_functions(self): + kept_lines = _generate_repeated_function_body(1, fn_name='_keep_me') + # Something to distinguish us from the rest. Just bump a random counter. + kept_lines[1] += '1' + + result_file = '\n'.join(kept_lines) + '\n' + + lines = _generate_repeated_function_body(_redact_limit, + fn_name='_discard_me') + self.assertEqual(_redact(kept_lines + lines), result_file) + self.assertEqual(_redact(lines + kept_lines), result_file) + + more_lines = _generate_repeated_function_body(_redact_limit, + fn_name='_and_discard_me') + self.assertEqual(_redact(lines + kept_lines + more_lines), result_file) + self.assertEqual(_redact(lines + more_lines), '') + + def test_correct_summary_is_printed_when_nothing_is_redacted(self): + lines = _generate_repeated_function_body(1) + _, summary = _redact_with_summary(lines) + self.assertIn('Retained 1/1 functions', summary) + self.assertIn('Retained 827/827 samples, total', summary) + # Note that top-level samples == "samples without inlining taken into + # account," not "sum(entry_counts)" + self.assertIn('Retained 335/335 top-level samples', summary) + + def test_correct_summary_is_printed_when_everything_is_redacted(self): + lines = _generate_repeated_function_body(_redact_limit) + _, summary = _redact_with_summary(lines) + self.assertIn('Retained 0/100 functions', summary) + self.assertIn('Retained 0/82,700 samples, total', summary) + self.assertIn('Retained 0/33,500 top-level samples', summary) + + def test_correct_summary_is_printed_when_most_everything_is_redacted(self): + kept_lines = _generate_repeated_function_body(1, fn_name='_keep_me') + kept_lines[1] += '1' + + lines = _generate_repeated_function_body(_redact_limit) + _, summary = _redact_with_summary(kept_lines + lines) + self.assertIn('Retained 1/101 functions', summary) + self.assertIn('Retained 1,575/84,275 samples, total', summary) + self.assertIn('Retained 1,083/34,583 top-level samples', summary) + + +if __name__ == '__main__': + unittest.main() |