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