graph_test.go

Documentation: github.com/google/pprof/internal/graph

     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  
    15  package graph
    16  
    17  import (
    18  	"fmt"
    19  	"testing"
    20  
    21  	"github.com/google/pprof/profile"
    22  )
    23  
    24  func 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  
    34  func 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  
    49  func 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  
    63  func 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.
    78  func 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.
    91  func 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.
    97  func 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  
   115  type expectedNode struct {
   116  	node    *Node
   117  	in, out EdgeMap
   118  }
   119  
   120  type trimTreeTestcase struct {
   121  	initial  *Graph
   122  	expected []expectedNode
   123  	keep     NodePtrSet
   124  }
   125  
   126  // makeExpectedEdgeResidual makes the edge from parent to child residual.
   127  func makeExpectedEdgeResidual(parent, child expectedNode) {
   128  	parent.out[child.node].Residual = true
   129  	child.in[parent.node].Residual = true
   130  }
   131  
   132  func makeEdgeInline(edgeMap EdgeMap, node *Node) {
   133  	edgeMap[node].Inline = true
   134  }
   135  
   136  func 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.
   141  func 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.
   153  func 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.
   161  func 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.
   179  func 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  //
   192  //	    0
   193  //	    |(5)
   194  //	    1
   195  //	(3)/ \(4)
   196  //	  2   3.
   197  //
   198  // After keeping 0, 2, and 3, it expects the graph:
   199  //
   200  //	    0
   201  //	(3)/ \(4)
   202  //	  2   3.
   203  func createTestCase1() trimTreeTestcase {
   204  	// Create initial graph
   205  	graph := &Graph{make(Nodes, 4)}
   206  	nodes := graph.Nodes
   207  	for i := range nodes {
   208  		nodes[i] = createEmptyNode()
   209  	}
   210  	createEdges(nodes[0], nodes[1])
   211  	createEdges(nodes[1], nodes[2], nodes[3])
   212  	makeEdgeInline(nodes[0].Out, nodes[1])
   213  	makeEdgeInline(nodes[1].Out, nodes[2])
   214  	setEdgeWeight(nodes[0].Out, nodes[1], 5)
   215  	setEdgeWeight(nodes[1].Out, nodes[2], 3)
   216  	setEdgeWeight(nodes[1].Out, nodes[3], 4)
   217  
   218  	// Create expected graph
   219  	expected, keep := createExpectedNodes(nodes[0], nodes[2], nodes[3])
   220  	createExpectedEdges(expected[0], expected[1], expected[2])
   221  	makeEdgeInline(expected[0].out, expected[1].node)
   222  	makeExpectedEdgeResidual(expected[0], expected[1])
   223  	makeExpectedEdgeResidual(expected[0], expected[2])
   224  	setEdgeWeight(expected[0].out, expected[1].node, 3)
   225  	setEdgeWeight(expected[0].out, expected[2].node, 4)
   226  	return trimTreeTestcase{
   227  		initial:  graph,
   228  		expected: expected,
   229  		keep:     keep,
   230  	}
   231  }
   232  
   233  // createTestCase2 creates a test case that initially looks like:
   234  //
   235  //	3
   236  //	| (12)
   237  //	1
   238  //	| (8)
   239  //	2
   240  //	| (15)
   241  //	0
   242  //	| (10)
   243  //	4.
   244  //
   245  // After keeping 3 and 4, it expects the graph:
   246  //
   247  //	3
   248  //	| (10)
   249  //	4.
   250  func createTestCase2() trimTreeTestcase {
   251  	// Create initial graph
   252  	graph := &Graph{make(Nodes, 5)}
   253  	nodes := graph.Nodes
   254  	for i := range nodes {
   255  		nodes[i] = createEmptyNode()
   256  	}
   257  	createEdges(nodes[3], nodes[1])
   258  	createEdges(nodes[1], nodes[2])
   259  	createEdges(nodes[2], nodes[0])
   260  	createEdges(nodes[0], nodes[4])
   261  	setEdgeWeight(nodes[3].Out, nodes[1], 12)
   262  	setEdgeWeight(nodes[1].Out, nodes[2], 8)
   263  	setEdgeWeight(nodes[2].Out, nodes[0], 15)
   264  	setEdgeWeight(nodes[0].Out, nodes[4], 10)
   265  
   266  	// Create expected graph
   267  	expected, keep := createExpectedNodes(nodes[3], nodes[4])
   268  	createExpectedEdges(expected[0], expected[1])
   269  	makeExpectedEdgeResidual(expected[0], expected[1])
   270  	setEdgeWeight(expected[0].out, expected[1].node, 10)
   271  	return trimTreeTestcase{
   272  		initial:  graph,
   273  		expected: expected,
   274  		keep:     keep,
   275  	}
   276  }
   277  
   278  // createTestCase3 creates an initially empty graph and expects an empty graph
   279  // after trimming.
   280  func createTestCase3() trimTreeTestcase {
   281  	graph := &Graph{make(Nodes, 0)}
   282  	expected, keep := createExpectedNodes()
   283  	return trimTreeTestcase{
   284  		initial:  graph,
   285  		expected: expected,
   286  		keep:     keep,
   287  	}
   288  }
   289  
   290  // createTestCase4 creates a test case that initially looks like:
   291  //
   292  //	0.
   293  //
   294  // After keeping 0, it expects the graph:
   295  //
   296  //	0.
   297  func createTestCase4() trimTreeTestcase {
   298  	graph := &Graph{make(Nodes, 1)}
   299  	nodes := graph.Nodes
   300  	for i := range nodes {
   301  		nodes[i] = createEmptyNode()
   302  	}
   303  	expected, keep := createExpectedNodes(nodes[0])
   304  	return trimTreeTestcase{
   305  		initial:  graph,
   306  		expected: expected,
   307  		keep:     keep,
   308  	}
   309  }
   310  
   311  func createTrimTreeTestCases() []trimTreeTestcase {
   312  	caseGenerators := []func() trimTreeTestcase{
   313  		createTestCase1,
   314  		createTestCase2,
   315  		createTestCase3,
   316  		createTestCase4,
   317  	}
   318  	cases := make([]trimTreeTestcase, len(caseGenerators))
   319  	for i, gen := range caseGenerators {
   320  		cases[i] = gen()
   321  	}
   322  	return cases
   323  }
   324  
   325  func TestTrimTree(t *testing.T) {
   326  	tests := createTrimTreeTestCases()
   327  	for _, test := range tests {
   328  		graph := test.initial
   329  		graph.TrimTree(test.keep)
   330  		if !graphsEqual(graph, test.expected) {
   331  			t.Fatalf("Graphs do not match.\nExpected: %s\nFound: %s\n",
   332  				expectedNodesDebugString(test.expected),
   333  				graphDebugString(graph))
   334  		}
   335  	}
   336  }
   337  
   338  func nodeTestProfile() *profile.Profile {
   339  	mappings := []*profile.Mapping{
   340  		{
   341  			ID:   1,
   342  			File: "symbolized_binary",
   343  		},
   344  		{
   345  			ID:   2,
   346  			File: "unsymbolized_library_1",
   347  		},
   348  		{
   349  			ID:   3,
   350  			File: "unsymbolized_library_2",
   351  		},
   352  	}
   353  	functions := []*profile.Function{
   354  		{ID: 1, Name: "symname"},
   355  		{ID: 2},
   356  	}
   357  	locations := []*profile.Location{
   358  		{
   359  			ID:      1,
   360  			Mapping: mappings[0],
   361  			Line: []profile.Line{
   362  				{Function: functions[0]},
   363  			},
   364  		},
   365  		{
   366  			ID:      2,
   367  			Mapping: mappings[1],
   368  			Line: []profile.Line{
   369  				{Function: functions[1]},
   370  			},
   371  		},
   372  		{
   373  			ID:      3,
   374  			Mapping: mappings[2],
   375  		},
   376  	}
   377  	return &profile.Profile{
   378  		PeriodType: &profile.ValueType{Type: "cpu", Unit: "milliseconds"},
   379  		SampleType: []*profile.ValueType{
   380  			{Type: "type", Unit: "unit"},
   381  		},
   382  		Sample: []*profile.Sample{
   383  			{
   384  				Location: []*profile.Location{locations[0]},
   385  				Value:    []int64{1},
   386  			},
   387  			{
   388  				Location: []*profile.Location{locations[1]},
   389  				Value:    []int64{1},
   390  			},
   391  			{
   392  				Location: []*profile.Location{locations[2]},
   393  				Value:    []int64{1},
   394  			},
   395  		},
   396  		Location: locations,
   397  		Function: functions,
   398  		Mapping:  mappings,
   399  	}
   400  }
   401  
   402  // TestCreateNodes checks that nodes are properly created for a simple profile.
   403  func TestCreateNodes(t *testing.T) {
   404  	testProfile := nodeTestProfile()
   405  	wantNodeSet := NodeSet{
   406  		{Name: "symname"}:                   true,
   407  		{Objfile: "unsymbolized_library_1"}: true,
   408  		{Objfile: "unsymbolized_library_2"}: true,
   409  	}
   410  
   411  	nodes, _ := CreateNodes(testProfile, &Options{})
   412  	if len(nodes) != len(wantNodeSet) {
   413  		t.Errorf("got %d nodes, want %d", len(nodes), len(wantNodeSet))
   414  	}
   415  	for _, node := range nodes {
   416  		if !wantNodeSet[node.Info] {
   417  			t.Errorf("unexpected node %v", node.Info)
   418  		}
   419  	}
   420  }
   421  
   422  func TestShortenFunctionName(t *testing.T) {
   423  	type testCase struct {
   424  		name string
   425  		want string
   426  	}
   427  	testcases := []testCase{
   428  		{
   429  			"root",
   430  			"root",
   431  		},
   432  		{
   433  			"syscall.Syscall",
   434  			"syscall.Syscall",
   435  		},
   436  		{
   437  			"net/http.(*conn).serve",
   438  			"http.(*conn).serve",
   439  		},
   440  		{
   441  			"github.com/blahBlah/foo.Foo",
   442  			"foo.Foo",
   443  		},
   444  		{
   445  			"github.com/BlahBlah/foo.Foo",
   446  			"foo.Foo",
   447  		},
   448  		{
   449  			"github.com/BlahBlah/foo.Foo[...]",
   450  			"foo.Foo[...]",
   451  		},
   452  		{
   453  			"github.com/blah-blah/foo_bar.(*FooBar).Foo",
   454  			"foo_bar.(*FooBar).Foo",
   455  		},
   456  		{
   457  			"encoding/json.(*structEncoder).(encoding/json.encode)-fm",
   458  			"json.(*structEncoder).(encoding/json.encode)-fm",
   459  		},
   460  		{
   461  			"github.com/blah/blah/vendor/gopkg.in/redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm",
   462  			"redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm",
   463  		},
   464  		{
   465  			"github.com/foo/bar/v4.(*Foo).Bar",
   466  			"bar.(*Foo).Bar",
   467  		},
   468  		{
   469  			"github.com/foo/bar/v4/baz.Foo.Bar",
   470  			"baz.Foo.Bar",
   471  		},
   472  		{
   473  			"github.com/foo/bar/v123.(*Foo).Bar",
   474  			"bar.(*Foo).Bar",
   475  		},
   476  		{
   477  			"github.com/foobar/v0.(*Foo).Bar",
   478  			"v0.(*Foo).Bar",
   479  		},
   480  		{
   481  			"github.com/foobar/v1.(*Foo).Bar",
   482  			"v1.(*Foo).Bar",
   483  		},
   484  		{
   485  			"example.org/v2xyz.Foo",
   486  			"v2xyz.Foo",
   487  		},
   488  		{
   489  			"github.com/foo/bar/v4/v4.(*Foo).Bar",
   490  			"v4.(*Foo).Bar",
   491  		},
   492  		{
   493  			"github.com/foo/bar/v4/foo/bar/v4.(*Foo).Bar",
   494  			"v4.(*Foo).Bar",
   495  		},
   496  		{
   497  			"java.util.concurrent.ThreadPoolExecutor$Worker.run",
   498  			"ThreadPoolExecutor$Worker.run",
   499  		},
   500  		{
   501  			"java.bar.foo.FooBar.run(java.lang.Runnable)",
   502  			"FooBar.run",
   503  		},
   504  		{
   505  			"(anonymous namespace)::Bar::Foo",
   506  			"Bar::Foo",
   507  		},
   508  		{
   509  			"(anonymous namespace)::foo",
   510  			"foo",
   511  		},
   512  		{
   513  			"cpp::namespace::Class::method()::$_100::operator()",
   514  			"Class::method",
   515  		},
   516  		{
   517  			"foo_bar::Foo::bar",
   518  			"Foo::bar",
   519  		},
   520  		{
   521  			"cpp::namespace::Class::method<float, long, int>()",
   522  			"Class::method<float, long, int>",
   523  		},
   524  		{
   525  			"foo",
   526  			"foo",
   527  		},
   528  		{
   529  			"foo/xyz",
   530  			"foo/xyz",
   531  		},
   532  		{
   533  			"com.google.perftools.gwp.benchmark.FloatBench.lambda$run$0",
   534  			"FloatBench.lambda$run$0",
   535  		},
   536  		{
   537  			"java.bar.foo.FooBar.run$0",
   538  			"FooBar.run$0",
   539  		},
   540  	}
   541  	for _, tc := range testcases {
   542  		name := ShortenFunctionName(tc.name)
   543  		if got, want := name, tc.want; got != want {
   544  			t.Errorf("ShortenFunctionName(%q) = %q, want %q", tc.name, got, want)
   545  		}
   546  	}
   547  }
   548
View as plain text