1# Copyright 2014 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5"""This module owns the logic for classifying and aggregating data in buckets.
6
7This complements the structure defined in the rules module. Symmetrically, the
8aggregated results are organized in a bucket tree, which structure is identical
9to the one of the corresponding rule tree.
10The logic for aggregation is the following:
11- The client loads a "rule tree" defined by the end-user (e.g., in a file) which
12  defines the final "shape" of the results.
13- The rules define how to "match" a trace_record (e.g., a mmap line or a native
14  allocation) given some of its properties (e.g. the mapped file or the prot.
15  flags).
16- The concrete classifier (which will use this module) knows how to count the
17  values for each trace_record (e.g. [Dirty KB, Clean KB, RSS KB] for mmaps).
18  Hence it decides the cardinality of the result nodes.
19- The responsibility of this module is simply doing the math.
20
21In the very essence this module adds up the counters of each node whereas the
22trace_record being pushed in the tree (through the AddToMatchingNodes method)
23matches a rule.
24It just does this math in a hierarchical fashion following the shape the tree.
25
26A typical result tree looks like this (each node has two values in the example):
27                          +----------------------+
28                          |        Total         |
29                          |----------------------|
30       +------------------+     (100, 1000)      +--------------------+
31       |                  +----------+-----------+                    |
32       |                             |                                |
33 +-----v-----+                 +-----v-----+                   +------v----+
34 |    Foo    |                 |    Bar    |                   |Total-other|
35 |-----------|                 |-----------|                   |-----------|
36 | (15, 100) |             +---+ (80, 200) +-----+             | (5, 700)  |
37 +-----------+             |   +-----------+     |             +-----------+
38                           |                     |
39                    +------v------+       +------v-----+
40                    | Bar::Coffee |       | Bar-other  |
41                    |-------------|       |------------|
42                    |  (30, 120)  |       |  (50, 80)  |
43                    +-------------+       +------------+
44"""
45
46from memory_inspector.classification import rules
47
48
49class AggreatedResults(object):
50  """A tree of results, where each node is a bucket (root: 'Total' bucket)."""
51
52  def __init__(self, rule_tree, keys):
53    """Initializes the bucket tree using the structure of the rules tree.
54
55    Each node of the bucket tree is initialized with a list of len(keys) zeros.
56    """
57    assert(isinstance(rule_tree, rules.Rule))
58    assert(isinstance(keys, list))
59    self.keys = keys
60    self.total = AggreatedResults._MakeBucketNodeFromRule(rule_tree, len(keys))
61
62  def AddToMatchingNodes(self, trace_record, values):
63    """Adds the provided |values| to the nodes that match the |trace_record|.
64
65    Tree traversal logic: at any level, one and only one node will match the
66    |trace_record| (in the worst case it will be the catchall *-other rule).
67    When a node is matched, the traversal continues in its children and no
68    further siblings in the upper levels are visited anymore.
69    This is to guarantee that at any level the values of one node are equal to
70    the sum of the values of all its children.
71
72    Args:
73      trace_record: any kind of object which can be matched by the Match method
74          of the Rule object.
75      values: a list of int(s) which represent the value associated to the
76          matched trace_record. The cardinality of the list must be equal to the
77          cardinality of the initial keys.
78    """
79    assert(len(values) == len(self.keys))
80    AggreatedResults._AddToMatchingNodes(
81        trace_record, values, self.total, len(self.keys))
82
83  @staticmethod
84  def _AddToMatchingNodes(trace_record, values, bucket, num_keys):
85    if not bucket.rule.Match(trace_record):
86      return False
87    for i in xrange(num_keys):
88      bucket.values[i] += values[i]
89    for child_bucket in bucket.children:
90      if AggreatedResults._AddToMatchingNodes(
91          trace_record, values, child_bucket, num_keys):
92        break
93    return True
94
95  @staticmethod
96  def _MakeBucketNodeFromRule(rule, num_keys):
97    assert(isinstance(rule, rules.Rule))
98    bucket = Bucket(rule, num_keys)
99    for child_rule in rule.children:
100      bucket.children.append(
101          AggreatedResults._MakeBucketNodeFromRule(child_rule, num_keys))
102    return bucket
103
104
105class Bucket(object):
106  """A bucket is a node in the results tree. """
107  def __init__(self, rule, num_keys):
108    self.rule = rule
109    self.values = [0] * num_keys
110    self.children = []
111
112  @property
113  def name(self):
114    return self.rule.name