1// Copyright 2016 Google Inc. All Rights Reserved. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package graph 16 17import ( 18 "fmt" 19 "testing" 20 21 "github.com/google/pprof/profile" 22) 23 24func edgeDebugString(edge *Edge) string { 25 debug := "" 26 debug += fmt.Sprintf("\t\tSrc: %p\n", edge.Src) 27 debug += fmt.Sprintf("\t\tDest: %p\n", edge.Dest) 28 debug += fmt.Sprintf("\t\tWeight: %d\n", edge.Weight) 29 debug += fmt.Sprintf("\t\tResidual: %t\n", edge.Residual) 30 debug += fmt.Sprintf("\t\tInline: %t\n", edge.Inline) 31 return debug 32} 33 34func edgeMapsDebugString(in, out EdgeMap) string { 35 debug := "" 36 debug += "In Edges:\n" 37 for parent, edge := range in { 38 debug += fmt.Sprintf("\tParent: %p\n", parent) 39 debug += edgeDebugString(edge) 40 } 41 debug += "Out Edges:\n" 42 for child, edge := range out { 43 debug += fmt.Sprintf("\tChild: %p\n", child) 44 debug += edgeDebugString(edge) 45 } 46 return debug 47} 48 49func graphDebugString(graph *Graph) string { 50 debug := "" 51 for i, node := range graph.Nodes { 52 debug += fmt.Sprintf("Node %d: %p\n", i, node) 53 } 54 55 for i, node := range graph.Nodes { 56 debug += "\n" 57 debug += fmt.Sprintf("=== Node %d: %p ===\n", i, node) 58 debug += edgeMapsDebugString(node.In, node.Out) 59 } 60 return debug 61} 62 63func expectedNodesDebugString(expected []expectedNode) string { 64 debug := "" 65 for i, node := range expected { 66 debug += fmt.Sprintf("Node %d: %p\n", i, node.node) 67 } 68 69 for i, node := range expected { 70 debug += "\n" 71 debug += fmt.Sprintf("=== Node %d: %p ===\n", i, node.node) 72 debug += edgeMapsDebugString(node.in, node.out) 73 } 74 return debug 75} 76 77// edgeMapsEqual checks if all the edges in this equal all the edges in that. 78func edgeMapsEqual(this, that EdgeMap) bool { 79 if len(this) != len(that) { 80 return false 81 } 82 for node, thisEdge := range this { 83 if *thisEdge != *that[node] { 84 return false 85 } 86 } 87 return true 88} 89 90// nodesEqual checks if node is equal to expected. 91func nodesEqual(node *Node, expected expectedNode) bool { 92 return node == expected.node && edgeMapsEqual(node.In, expected.in) && 93 edgeMapsEqual(node.Out, expected.out) 94} 95 96// graphsEqual checks if graph is equivalent to the graph templated by expected. 97func graphsEqual(graph *Graph, expected []expectedNode) bool { 98 if len(graph.Nodes) != len(expected) { 99 return false 100 } 101 expectedSet := make(map[*Node]expectedNode) 102 for i := range expected { 103 expectedSet[expected[i].node] = expected[i] 104 } 105 106 for _, node := range graph.Nodes { 107 expectedNode, found := expectedSet[node] 108 if !found || !nodesEqual(node, expectedNode) { 109 return false 110 } 111 } 112 return true 113} 114 115type expectedNode struct { 116 node *Node 117 in, out EdgeMap 118} 119 120type trimTreeTestcase struct { 121 initial *Graph 122 expected []expectedNode 123 keep NodePtrSet 124} 125 126// makeExpectedEdgeResidual makes the edge from parent to child residual. 127func makeExpectedEdgeResidual(parent, child expectedNode) { 128 parent.out[child.node].Residual = true 129 child.in[parent.node].Residual = true 130} 131 132func makeEdgeInline(edgeMap EdgeMap, node *Node) { 133 edgeMap[node].Inline = true 134} 135 136func setEdgeWeight(edgeMap EdgeMap, node *Node, weight int64) { 137 edgeMap[node].Weight = weight 138} 139 140// createEdges creates directed edges from the parent to each of the children. 141func createEdges(parent *Node, children ...*Node) { 142 for _, child := range children { 143 edge := &Edge{ 144 Src: parent, 145 Dest: child, 146 } 147 parent.Out[child] = edge 148 child.In[parent] = edge 149 } 150} 151 152// createEmptyNode creates a node without any edges. 153func createEmptyNode() *Node { 154 return &Node{ 155 In: make(EdgeMap), 156 Out: make(EdgeMap), 157 } 158} 159 160// createExpectedNodes creates a slice of expectedNodes from nodes. 161func createExpectedNodes(nodes ...*Node) ([]expectedNode, NodePtrSet) { 162 expected := make([]expectedNode, len(nodes)) 163 keep := make(NodePtrSet, len(nodes)) 164 165 for i, node := range nodes { 166 expected[i] = expectedNode{ 167 node: node, 168 in: make(EdgeMap), 169 out: make(EdgeMap), 170 } 171 keep[node] = true 172 } 173 174 return expected, keep 175} 176 177// createExpectedEdges creates directed edges from the parent to each of the 178// children. 179func createExpectedEdges(parent expectedNode, children ...expectedNode) { 180 for _, child := range children { 181 edge := &Edge{ 182 Src: parent.node, 183 Dest: child.node, 184 } 185 parent.out[child.node] = edge 186 child.in[parent.node] = edge 187 } 188} 189 190// createTestCase1 creates a test case that initially looks like: 191// 0 192// |(5) 193// 1 194// (3)/ \(4) 195// 2 3. 196// 197// After keeping 0, 2, and 3, it expects the graph: 198// 0 199// (3)/ \(4) 200// 2 3. 201func createTestCase1() trimTreeTestcase { 202 // Create initial graph 203 graph := &Graph{make(Nodes, 4)} 204 nodes := graph.Nodes 205 for i := range nodes { 206 nodes[i] = createEmptyNode() 207 } 208 createEdges(nodes[0], nodes[1]) 209 createEdges(nodes[1], nodes[2], nodes[3]) 210 makeEdgeInline(nodes[0].Out, nodes[1]) 211 makeEdgeInline(nodes[1].Out, nodes[2]) 212 setEdgeWeight(nodes[0].Out, nodes[1], 5) 213 setEdgeWeight(nodes[1].Out, nodes[2], 3) 214 setEdgeWeight(nodes[1].Out, nodes[3], 4) 215 216 // Create expected graph 217 expected, keep := createExpectedNodes(nodes[0], nodes[2], nodes[3]) 218 createExpectedEdges(expected[0], expected[1], expected[2]) 219 makeEdgeInline(expected[0].out, expected[1].node) 220 makeExpectedEdgeResidual(expected[0], expected[1]) 221 makeExpectedEdgeResidual(expected[0], expected[2]) 222 setEdgeWeight(expected[0].out, expected[1].node, 3) 223 setEdgeWeight(expected[0].out, expected[2].node, 4) 224 return trimTreeTestcase{ 225 initial: graph, 226 expected: expected, 227 keep: keep, 228 } 229} 230 231// createTestCase2 creates a test case that initially looks like: 232// 3 233// | (12) 234// 1 235// | (8) 236// 2 237// | (15) 238// 0 239// | (10) 240// 4. 241// 242// After keeping 3 and 4, it expects the graph: 243// 3 244// | (10) 245// 4. 246func createTestCase2() trimTreeTestcase { 247 // Create initial graph 248 graph := &Graph{make(Nodes, 5)} 249 nodes := graph.Nodes 250 for i := range nodes { 251 nodes[i] = createEmptyNode() 252 } 253 createEdges(nodes[3], nodes[1]) 254 createEdges(nodes[1], nodes[2]) 255 createEdges(nodes[2], nodes[0]) 256 createEdges(nodes[0], nodes[4]) 257 setEdgeWeight(nodes[3].Out, nodes[1], 12) 258 setEdgeWeight(nodes[1].Out, nodes[2], 8) 259 setEdgeWeight(nodes[2].Out, nodes[0], 15) 260 setEdgeWeight(nodes[0].Out, nodes[4], 10) 261 262 // Create expected graph 263 expected, keep := createExpectedNodes(nodes[3], nodes[4]) 264 createExpectedEdges(expected[0], expected[1]) 265 makeExpectedEdgeResidual(expected[0], expected[1]) 266 setEdgeWeight(expected[0].out, expected[1].node, 10) 267 return trimTreeTestcase{ 268 initial: graph, 269 expected: expected, 270 keep: keep, 271 } 272} 273 274// createTestCase3 creates an initially empty graph and expects an empty graph 275// after trimming. 276func createTestCase3() trimTreeTestcase { 277 graph := &Graph{make(Nodes, 0)} 278 expected, keep := createExpectedNodes() 279 return trimTreeTestcase{ 280 initial: graph, 281 expected: expected, 282 keep: keep, 283 } 284} 285 286// createTestCase4 creates a test case that initially looks like: 287// 0. 288// 289// After keeping 0, it expects the graph: 290// 0. 291func createTestCase4() trimTreeTestcase { 292 graph := &Graph{make(Nodes, 1)} 293 nodes := graph.Nodes 294 for i := range nodes { 295 nodes[i] = createEmptyNode() 296 } 297 expected, keep := createExpectedNodes(nodes[0]) 298 return trimTreeTestcase{ 299 initial: graph, 300 expected: expected, 301 keep: keep, 302 } 303} 304 305func createTrimTreeTestCases() []trimTreeTestcase { 306 caseGenerators := []func() trimTreeTestcase{ 307 createTestCase1, 308 createTestCase2, 309 createTestCase3, 310 createTestCase4, 311 } 312 cases := make([]trimTreeTestcase, len(caseGenerators)) 313 for i, gen := range caseGenerators { 314 cases[i] = gen() 315 } 316 return cases 317} 318 319func TestTrimTree(t *testing.T) { 320 tests := createTrimTreeTestCases() 321 for _, test := range tests { 322 graph := test.initial 323 graph.TrimTree(test.keep) 324 if !graphsEqual(graph, test.expected) { 325 t.Fatalf("Graphs do not match.\nExpected: %s\nFound: %s\n", 326 expectedNodesDebugString(test.expected), 327 graphDebugString(graph)) 328 } 329 } 330} 331 332func nodeTestProfile() *profile.Profile { 333 mappings := []*profile.Mapping{ 334 { 335 ID: 1, 336 File: "symbolized_binary", 337 }, 338 { 339 ID: 2, 340 File: "unsymbolized_library_1", 341 }, 342 { 343 ID: 3, 344 File: "unsymbolized_library_2", 345 }, 346 } 347 functions := []*profile.Function{ 348 {ID: 1, Name: "symname"}, 349 {ID: 2}, 350 } 351 locations := []*profile.Location{ 352 { 353 ID: 1, 354 Mapping: mappings[0], 355 Line: []profile.Line{ 356 {Function: functions[0]}, 357 }, 358 }, 359 { 360 ID: 2, 361 Mapping: mappings[1], 362 Line: []profile.Line{ 363 {Function: functions[1]}, 364 }, 365 }, 366 { 367 ID: 3, 368 Mapping: mappings[2], 369 }, 370 } 371 return &profile.Profile{ 372 PeriodType: &profile.ValueType{Type: "cpu", Unit: "milliseconds"}, 373 SampleType: []*profile.ValueType{ 374 {Type: "type", Unit: "unit"}, 375 }, 376 Sample: []*profile.Sample{ 377 { 378 Location: []*profile.Location{locations[0]}, 379 Value: []int64{1}, 380 }, 381 { 382 Location: []*profile.Location{locations[1]}, 383 Value: []int64{1}, 384 }, 385 { 386 Location: []*profile.Location{locations[2]}, 387 Value: []int64{1}, 388 }, 389 }, 390 Location: locations, 391 Function: functions, 392 Mapping: mappings, 393 } 394} 395 396// TestCreateNodes checks that nodes are properly created for a simple profile. 397func TestCreateNodes(t *testing.T) { 398 testProfile := nodeTestProfile() 399 wantNodeSet := NodeSet{ 400 {Name: "symname"}: true, 401 {Objfile: "unsymbolized_library_1"}: true, 402 {Objfile: "unsymbolized_library_2"}: true, 403 } 404 405 nodes, _ := CreateNodes(testProfile, &Options{}) 406 if len(nodes) != len(wantNodeSet) { 407 t.Errorf("got %d nodes, want %d", len(nodes), len(wantNodeSet)) 408 } 409 for _, node := range nodes { 410 if !wantNodeSet[node.Info] { 411 t.Errorf("unexpected node %v", node.Info) 412 } 413 } 414} 415 416func TestShortenFunctionName(t *testing.T) { 417 type testCase struct { 418 name string 419 want string 420 } 421 testcases := []testCase{ 422 { 423 "root", 424 "root", 425 }, 426 { 427 "syscall.Syscall", 428 "syscall.Syscall", 429 }, 430 { 431 "net/http.(*conn).serve", 432 "http.(*conn).serve", 433 }, 434 { 435 "github.com/blahBlah/foo.Foo", 436 "foo.Foo", 437 }, 438 { 439 "github.com/BlahBlah/foo.Foo", 440 "foo.Foo", 441 }, 442 { 443 "github.com/blah-blah/foo_bar.(*FooBar).Foo", 444 "foo_bar.(*FooBar).Foo", 445 }, 446 { 447 "encoding/json.(*structEncoder).(encoding/json.encode)-fm", 448 "json.(*structEncoder).(encoding/json.encode)-fm", 449 }, 450 { 451 "github.com/blah/blah/vendor/gopkg.in/redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm", 452 "redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm", 453 }, 454 { 455 "github.com/foo/bar/v4.(*Foo).Bar", 456 "bar.(*Foo).Bar", 457 }, 458 { 459 "github.com/foo/bar/v4/baz.Foo.Bar", 460 "baz.Foo.Bar", 461 }, 462 { 463 "github.com/foo/bar/v123.(*Foo).Bar", 464 "bar.(*Foo).Bar", 465 }, 466 { 467 "github.com/foobar/v0.(*Foo).Bar", 468 "v0.(*Foo).Bar", 469 }, 470 { 471 "github.com/foobar/v1.(*Foo).Bar", 472 "v1.(*Foo).Bar", 473 }, 474 { 475 "example.org/v2xyz.Foo", 476 "v2xyz.Foo", 477 }, 478 { 479 "github.com/foo/bar/v4/v4.(*Foo).Bar", 480 "v4.(*Foo).Bar", 481 }, 482 { 483 "github.com/foo/bar/v4/foo/bar/v4.(*Foo).Bar", 484 "v4.(*Foo).Bar", 485 }, 486 { 487 "java.util.concurrent.ThreadPoolExecutor$Worker.run", 488 "ThreadPoolExecutor$Worker.run", 489 }, 490 { 491 "java.bar.foo.FooBar.run(java.lang.Runnable)", 492 "FooBar.run", 493 }, 494 { 495 "(anonymous namespace)::Bar::Foo", 496 "Bar::Foo", 497 }, 498 { 499 "(anonymous namespace)::foo", 500 "foo", 501 }, 502 { 503 "cpp::namespace::Class::method()::$_100::operator()", 504 "Class::method", 505 }, 506 { 507 "foo_bar::Foo::bar", 508 "Foo::bar", 509 }, 510 { 511 "cpp::namespace::Class::method<float, long, int>()", 512 "Class::method<float, long, int>", 513 }, 514 { 515 "foo", 516 "foo", 517 }, 518 { 519 "com.google.perftools.gwp.benchmark.FloatBench.lambda$run$0", 520 "FloatBench.lambda$run$0", 521 }, 522 { 523 "java.bar.foo.FooBar.run$0", 524 "FooBar.run$0", 525 }, 526 } 527 for _, tc := range testcases { 528 name := ShortenFunctionName(tc.name) 529 if got, want := name, tc.want; got != want { 530 t.Errorf("ShortenFunctionName(%q) = %q, want %q", tc.name, got, want) 531 } 532 } 533} 534