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