1#!/usr/bin/env vpython 2# Copyright 2018 The Chromium Authors. All rights reserved. 3# Use of this source code is governed by a BSD-style license that can be 4# found in the LICENSE file. 5 6"""Tests for cluster.py.""" 7 8import unittest 9import json 10 11import cluster 12import process_profiles 13from test_utils import (ProfileFile, 14 SimpleTestSymbol, 15 TestProfileManager, 16 TestSymbolOffsetProcessor) 17 18 19class ClusteringTestCase(unittest.TestCase): 20 def testClusterOf(self): 21 clstr = cluster.Clustering() 22 c = clstr.ClusterOf('a') 23 self.assertEqual(['a'], c.syms) 24 c = clstr._MakeCluster(['a', 'b', 'c']) 25 self.assertEqual(c, clstr.ClusterOf('a')) 26 self.assertEqual(c, clstr.ClusterOf('b')) 27 self.assertEqual(c, clstr.ClusterOf('c')) 28 29 def testClusterCombine(self): 30 clstr = cluster.Clustering() 31 x = clstr._MakeCluster(['a', 'b']) 32 self.assertEqual(x, clstr.ClusterOf('a')) 33 self.assertEqual(x, clstr.ClusterOf('b')) 34 35 y = clstr._MakeCluster(['c']) 36 self.assertEqual(y, clstr.ClusterOf('c')) 37 38 z = clstr.Combine(y, x) 39 self.assertEqual(['c', 'a', 'b'], z.syms) 40 self.assertEqual(z, clstr.ClusterOf('a')) 41 self.assertEqual(z, clstr.ClusterOf('b')) 42 self.assertEqual(z, clstr.ClusterOf('c')) 43 44 def testClusteringDistances(self): 45 c = cluster.Clustering() 46 c.NEIGHBOR_DISTANCE = 3 47 c.AddSymbolLists([list('abcd'), list('acbe'), list('bacf'), 48 list('badf'), list('baef')]) 49 distances = {} 50 for n in c._neighbors: 51 self.assertFalse((n.src, n.dst) in distances) 52 distances[(n.src, n.dst)] = n.dist 53 self.assertEqual(13, len(distances)) 54 self.assertEqual((2 + 1 + 1 + 2000) / 5., distances[('a', 'c')]) 55 self.assertEqual((1 + 4000) / 5., distances[('a', 'd')]) 56 self.assertEqual((1 + 4000) / 5., distances[('a', 'e')]) 57 self.assertEqual((2 + 2 + 2 + 2000) / 5., distances[('a', 'f')]) 58 self.assertEqual(0, distances[('b', 'a')]) 59 self.assertEqual((1 + -1 + 2 + 2000) / 5., distances[('b', 'c')]) 60 self.assertTrue(('b', 'd') in distances) 61 self.assertTrue(('b', 'e') in distances) 62 self.assertTrue(('c', 'd') in distances) 63 self.assertTrue(('c', 'e') in distances) 64 self.assertTrue(('c', 'f') in distances) 65 self.assertTrue(('d', 'f') in distances) 66 self.assertTrue(('e', 'f') in distances) 67 68 def testClusterToList(self): 69 c = cluster.Clustering() 70 c.NEIGHBOR_DISTANCE = 3 71 c.AddSymbolLists([list('abcd'), list('acbe'), list('bacf'), 72 list('badf'), list('baef')]) 73 self.assertEqual(list('bacfed'), c.ClusterToList()) 74 75 def testClusterOneList(self): 76 c = cluster.Clustering() 77 c.NEIGHBOR_DISTANCE = 3 78 c.AddSymbolLists([list('fedcba')]) 79 self.assertEqual(list('fedcba'), c.ClusterToList()) 80 81 def testClusterShortList(self): 82 c = cluster.Clustering() 83 c.NEIGHBOR_DISTANCE = 3 84 c.AddSymbolLists([list('ab')]) 85 self.assertEqual(list('ab'), c.ClusterToList()) 86 87 def testClusterReallyShortList(self): 88 c = cluster.Clustering() 89 c.NEIGHBOR_DISTANCE = 3 90 c.AddSymbolLists([list('a')]) 91 self.assertEqual([], c.ClusterToList()) 92 93 def testSizedClusterToList(self): 94 c = cluster.Clustering() 95 c.NEIGHBOR_DISTANCE = 3 96 c.MAX_CLUSTER_SIZE = 1 # Will supress all clusters 97 size_map = {'a': 3, 98 'b': 4, 99 'c': 5, 100 'd': 6, 101 'e': 7, 102 'f': 8} 103 c.AddSymbolLists([list('abcd'), list('acbe'), list('bacf'), 104 list('badf'), list('baef')]) 105 self.assertEqual(list('fedcba'), c.ClusterToList(size_map)) 106 107 def testClusterOffsets(self): 108 processor = TestSymbolOffsetProcessor([ 109 SimpleTestSymbol('linker_script_start_of_text', 0, 0), 110 SimpleTestSymbol('1', 1000, 999), 111 SimpleTestSymbol('2', 2000, 999), 112 SimpleTestSymbol('3', 3000, 999), 113 SimpleTestSymbol('4', 4000, 16), 114 SimpleTestSymbol('5', 5000, 16), 115 SimpleTestSymbol('6', 6000, 999), 116 SimpleTestSymbol('7', 7000, 16), 117 SimpleTestSymbol('8', 8000, 999), 118 SimpleTestSymbol('9', 9000, 16), 119 ]) 120 mgr = TestProfileManager({ 121 ProfileFile(40, 0, ''): [1000, 2000, 3000], 122 ProfileFile(50, 1, ''): [3000, 4000, 5000], 123 ProfileFile(51, 0, 'renderer'): [2000, 3000, 6000], 124 ProfileFile(51, 1, 'gpu-process'): [6000, 7000], 125 ProfileFile(70, 0, ''): [1000, 2000, 6000, 8000, 9000], 126 ProfileFile(70, 1, ''): [9000, 5000, 3000]}) 127 syms = cluster.ClusterOffsets(mgr, processor, limit_cluster_size=False) 128 self.assertListEqual(list('236148957'), syms) 129 130 syms = cluster.ClusterOffsets(mgr, processor, limit_cluster_size=True) 131 self.assertListEqual(list('236489517'), syms) 132 133 def testClusteringDistancesForCallGraph(self): 134 c = cluster.Clustering() 135 callerA = cluster.CallerInfo(caller_symbol='a', count=1) 136 callerB = cluster.CallerInfo(caller_symbol='b', count=2) 137 callerC = cluster.CallerInfo(caller_symbol='c', count=3) 138 callerD = cluster.CallerInfo(caller_symbol='d', count=100) 139 callerE = cluster.CallerInfo(caller_symbol='e', count=200) 140 141 calleeA = cluster.CalleeInfo(index=4, callee_symbol='a', misses=0, 142 caller_and_count=[]) 143 calleeB = cluster.CalleeInfo(index=8, callee_symbol='b', misses=1, 144 caller_and_count=[callerA]) 145 calleeC = cluster.CalleeInfo(index=12, callee_symbol='c', misses=1, 146 caller_and_count=[callerA, callerE]) 147 calleeD = cluster.CalleeInfo(index=20, callee_symbol='d', misses=1, 148 caller_and_count=[callerB, callerC, callerE]) 149 calleeF = cluster.CalleeInfo(index=28, callee_symbol='f', misses=10, 150 caller_and_count=[callerD]) 151 process1 = [calleeA, calleeB, calleeC, calleeD] 152 process2 = [calleeA, calleeB, calleeC, calleeD, calleeF] 153 call_graph = [process1, process2] 154 whitelist = ['e', 'g', 'h', 'k', 'l'] 155 c.AddSymbolCallGraph(call_graph, whitelist) 156 distances = {} 157 for n in c._neighbors: 158 self.assertFalse((n.src, n.dst) in distances) 159 distances[(n.src, n.dst)] = n.dist 160 self.assertEqual(5, len(distances)) 161 self.assertEquals(-2, distances[('a', 'b')]) 162 self.assertEquals(-2, distances[('a', 'c')]) 163 self.assertEquals(-4, distances[('b', 'd')]) 164 self.assertEquals(-6, distances[('c', 'd')]) 165 self.assertEquals(-100, distances[('d', 'f')]) 166 self.assertEquals(list('abcdf'), c.ClusterToList()) 167 168 def testClusterOffsetsFromCallGraph(self): 169 process1 = ('{"call_graph": [ {' 170 '"callee_offset": "1000",' 171 '"caller_and_count": [ {' 172 '"caller_offset": "0",' 173 '"count": "2"' 174 '} ],' 175 '"index": "61496"' 176 '}, {' 177 '"callee_offset": "7000",' 178 '"caller_and_count": [ {' 179 '"caller_offset": "1000",' 180 '"count": "2"' 181 '}, {' 182 '"caller_offset": "7500",' 183 '"count": "100"' 184 '} ],' 185 '"index": "61500"' 186 '}, {' 187 '"callee_offset": "6000",' 188 '"caller_and_count": [ {' 189 '"caller_offset": "1000",' 190 '"count": "4"' 191 '}, {' 192 '"caller_offset": "7000",' 193 '"count": "3"' 194 '}, {' 195 '"caller_offset": "7500",' 196 '"count": "2"' 197 '}, {' 198 '"caller_offset": "0",' 199 '"count": "3"' 200 '} ],' 201 '"index": "47860"' 202 '}, {' 203 '"callee_offset": "3000",' 204 '"caller_and_count": [ {' 205 '"caller_offset": "6000",' 206 '"count": "11"' 207 '} ],' 208 '"index": "47900"' 209 '} ],' 210 '"total_calls_count": "127"' 211 '}') 212 213 process2 = ('{"call_graph": [ {' 214 '"callee_offset": "1000",' 215 '"caller_and_count": [ {' 216 '"caller_offset": "0",' 217 '"count": "2"' 218 '} ],' 219 '"index": "61496"' 220 '}, {' 221 '"callee_offset": "5000",' 222 '"caller_and_count": [ {' 223 '"caller_offset": "1000",' 224 '"count": "20"' 225 '}, {' 226 '"caller_offset": "5000",' 227 '"count": "100"' 228 '}, {' 229 '"caller_offset": "3000",' 230 '"count": "40"' 231 '} ],' 232 '"index": "61500"' 233 '}, {' 234 '"callee_offset": "3000",' 235 '"caller_and_count": [ {' 236 '"caller_offset": "5000",' 237 '"count": "10"' 238 '}, {' 239 '"caller_offset": "0",' 240 '"count": "10"' 241 '} ],' 242 '"index": "47860"' 243 '} ],' 244 '"total_calls_count": "182"' 245 '}') 246 247 process3 = ('{"call_graph": [ {' 248 '"callee_offset": "8000",' 249 '"caller_and_count": [ {' 250 '"caller_offset": "0",' 251 '"count": "5"' 252 '} ],' 253 '"index": "61496"' 254 '}, {' 255 '"callee_offset": "2000",' 256 '"caller_and_count": [ {' 257 '"caller_offset": "8000",' 258 '"count": "100"' 259 '} ],' 260 '"index": "61500"' 261 '}, {' 262 '"callee_offset": "4000",' 263 '"caller_and_count": [ {' 264 '"caller_offset": "8000",' 265 '"count": "20"' 266 '} ],' 267 '"index": "61504"' 268 '}, {' 269 '"callee_offset": "9000",' 270 '"caller_and_count": [ {' 271 '"caller_offset": "8000",' 272 '"count": "50"' 273 '} ],' 274 '"index": "61512"' 275 '}, {' 276 '"callee_offset": "7000",' 277 '"caller_and_count": [ {' 278 '"caller_offset": "2000",' 279 '"count": "15"' 280 '}, {' 281 '"caller_offset": "4000",' 282 '"count": "20"' 283 '}, {' 284 '"caller_offset": "9000",' 285 '"count": "80"' 286 '}, {' 287 '"caller_offset": "0",' 288 '"count": "400"' 289 '} ],' 290 '"index": "61516"' 291 '} ],' 292 '"total_calls_count": "690"' 293 '}') 294 295 process4 = ('{"call_graph": [ {' 296 '"callee_offset": "8000",' 297 '"caller_and_count": [ {' 298 '"caller_offset": "0",' 299 '"count": "10"' 300 '} ],' 301 '"index": "61496"' 302 '}, {' 303 '"callee_offset": "2000",' 304 '"caller_and_count": [ {' 305 '"caller_offset": "8000",' 306 '"count": "100"' 307 '} ],' 308 '"index": "61500"' 309 '}, {' 310 '"callee_offset": "6000",' 311 '"caller_and_count": [ {' 312 '"caller_offset": "7000",' 313 '"count": "10"' 314 '} , {' 315 '"caller_offset": "7500",' 316 '"count": "2"' 317 '} ],' 318 '"index": "61504"' 319 '}, {' 320 '"callee_offset": "7000",' 321 '"caller_and_count": [ {' 322 '"caller_offset": "8000",' 323 '"count": "300"' 324 '}, {' 325 '"caller_offset": "7500",' 326 '"count": "100"' 327 '}, {' 328 '"caller_offset": "2000",' 329 '"count": "15"' 330 '}, {' 331 '"caller_offset": "0",' 332 '"count": "50"' 333 '} ],' 334 '"index": "61516"' 335 '} ],' 336 '"total_calls_count": "587"' 337 '}') 338 339 processor = TestSymbolOffsetProcessor([ 340 SimpleTestSymbol('linker_script_start_of_text', 0, 0), 341 SimpleTestSymbol('1', 1000, 999), 342 SimpleTestSymbol('2', 2000, 999), 343 SimpleTestSymbol('3', 3000, 999), 344 SimpleTestSymbol('4', 4000, 16), 345 SimpleTestSymbol('5', 5000, 16), 346 SimpleTestSymbol('6', 6000, 999), 347 SimpleTestSymbol('7', 7000, 16), 348 SimpleTestSymbol('8', 7100, 0), # whitelist 349 SimpleTestSymbol('9', 8000, 999), 350 SimpleTestSymbol('10', 9000, 16)]) 351 mgr = TestProfileManager({ 352 ProfileFile(40, 0, 'renderer'): json.loads(process1), 353 ProfileFile(50, 1, 'renderer'): json.loads(process2), 354 ProfileFile(51, 0, 'browser'): json.loads(process3), 355 ProfileFile(51, 1, 'gpu-process'): json.loads(process4)}) 356 syms = cluster.ClusterOffsets(mgr, processor, limit_cluster_size=False, 357 call_graph=True) 358 self.assertListEqual(['7', '6', '1', '5', '3', '9', '2', '10', '4'], syms) 359 360 361 362if __name__ == "__main__": 363 unittest.main() 364