Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

x/vuln: optimization opportunities #57357

Closed
adonovan opened this issue Dec 16, 2022 · 10 comments
Closed

x/vuln: optimization opportunities #57357

adonovan opened this issue Dec 16, 2022 · 10 comments
Assignees
@timothy-king @zpavlinovic
Labels
vulncheck or vulndb Issues for the x/vuln or x/vulndb repo
Milestone
vuln/unplanned

Comments

@adonovan
Copy link
Member

adonovan commented Dec 16, 2022 •
edited
Loading

Some ways we could make govulncheck faster, based on observations of a CPU profile:

  1. request the vulns from the db in parallel with SSA construction. If the vulns set is empty, return without waiting for SSA construction to finish.
  2. change VTA to build the CHA callgraph internally. Use a different representation to avoid the duplication of edges. e.g. every io.Reader.Read callsite has an edge to every concrete Read method, but all sites have the same set of edges and callees. They could be factored.
  3. Don't use three maps in the implementation of Tarjan's algorithm, use fields in the node itself. The single vtaGraph map could provide both the connectivity relation and the state of Tarjan for each node.
@adonovan adonovan added the vulncheck or vulndb Issues for the x/vuln or x/vulndb repo label Dec 16, 2022
@gopherbot gopherbot modified the milestones: Unreleased, vuln/unplanned Dec 16, 2022
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/460435 mentions this issue: go/callgraph/vta: optimize scc computation

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/460420 mentions this issue: vulncheck: build callgraph in parallel with fetching db

@timothy-king
Copy link
Contributor

change VTA to build the CHA callgraph internally. Use a different representation to avoid the duplication of edges. e.g. every io.Reader.Read callsite has an edge to every concrete Read method, but all sites have the same set of edges and callees.

This idea is currently blocked on VTA using both incoming and outgoing edges from the callgraph.Graph. If it only uses outgoing edges, we can benefit from only constructing the outgoing CHA edges, which is roughly what this suggestion is. In particular, rtrn needs to be updated.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/460758 mentions this issue: go/callgraph/cha: refactor callee construction

gopherbot pushed a commit to golang/tools that referenced this issue Jan 9, 2023
@timothy-king
go/callgraph/vta: optimize scc computation
67baca6 
Optimizes how sccs are internally computed by reducing the
amount of maps created and map lookups performed. Between
4-10% faster on benchmarks of callgraph construction.

Updates golang/go#57357

Change-Id: I0ecd92c32358a56d1cae67beb352ec15b7b4367e
Reviewed-on: https://go-review.googlesource.com/c/tools/+/460435
Run-TryBot: Tim King <[email protected]>
TryBot-Result: Gopher Robot <[email protected]>
gopls-CI: kokoro <[email protected]>
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
gopherbot pushed a commit to golang/vuln that referenced this issue Jan 9, 2023
@timothy-king
vulncheck: build callgraph in parallel with fetching db
975d4c7 
Source(...) now builds the *ssa.Program and callgraph from
the *ssa.Program in parallel with fetching vulnerabilities.
Returns as soon as the vuln set is empty.

Updates golang/go#57357

Change-Id: I310b93f7125b5edcc2a5744db9f9f595c70aa5d4
Reviewed-on: https://go-review.googlesource.com/c/vuln/+/460420
TryBot-Result: Gopher Robot <[email protected]>
Reviewed-by: Alan Donovan <[email protected]>
Run-TryBot: Tim King <[email protected]>
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
@zpavlinovic
Copy link
Contributor

change VTA to build the CHA callgraph internally. Use a different representation to avoid the duplication of edges. e.g. every io.Reader.Read callsite has an edge to every concrete Read method, but all sites have the same set of edges and callees.

This idea is currently blocked on VTA using both incoming and outgoing edges from the callgraph.Graph. If it only uses outgoing edges, we can benefit from only constructing the outgoing CHA edges, which is roughly what this suggestion is. In particular, rtrn needs to be updated.

In principle, we can construct the incoming edges from outgoing, so I believe the VTA can be refactored to account for this. This construction would only be done for this different representation. I suspect it would be rather inexpensive.

@timothy-king
Copy link
Contributor

Another possible option would maybe be to have nodes for return values? Return statement values could flow into those nodes and when the calls happen we can connect the results to the return nodes. More nodes for doing fewer edges like a likely minor win.

@zpavlinovic
Copy link
Contributor

We could do that as well. I think this is also what naturally pops up when implementing invoke-group optimization.

gopherbot pushed a commit to golang/tools that referenced this issue Jan 10, 2023
@timothy-king
go/callgraph/cha: refactor callee construction
6e9a35d 
Refactors callee construction to create a function mapping
a callsite to its callees. This consumes 4x less memory and
is 37% faster than fully constructing a callgraph.Graph on
a benchmark for a net/http server. If made public, this could
be used to optimize the performance of vulncheck.

Updates golang/go#57357

Change-Id: I42faa859d10f30361d3d497a81245af7f61e8a01
Reviewed-on: https://go-review.googlesource.com/c/tools/+/460758
gopls-CI: kokoro <[email protected]>
Run-TryBot: Tim King <[email protected]>
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
TryBot-Result: Gopher Robot <[email protected]>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/461417 mentions this issue: gopls: update golang.org/x/vuln@6ad3e3d

gopherbot pushed a commit to golang/tools that referenced this issue Jan 12, 2023
@hyangah
gopls: update golang.org/x/vuln@6ad3e3d
e81af27 
govulncheck.DefaultCache interface was changed to return error.
Update callsites.

Notable changes:
  vulncheck performance improvements (golang/go#57357)
   https://go-review.googlesource.com/c/vuln/+/460422
   https://go-review.googlesource.com/c/vuln/+/460420
  store the vuln info cache under module cache directory
   https://go-review.googlesource.com/c/vuln/+/459036
   https://go-review.googlesource.com/c/vuln/+/460421

Change-Id: Ie3816f31b4e1178bb2067cb09c1c726dd37fad55
Reviewed-on: https://go-review.googlesource.com/c/tools/+/461417
Run-TryBot: Hyang-Ah Hana Kim <[email protected]>
TryBot-Result: Gopher Robot <[email protected]>
gopls-CI: kokoro <[email protected]>
Reviewed-by: Robert Findley <[email protected]>
softdev050 added a commit to softdev050/Golangvuln that referenced this issue Apr 5, 2023
@softdev050
vulncheck: build callgraph in parallel with fetching db
3586935 
Source(...) now builds the *ssa.Program and callgraph from
the *ssa.Program in parallel with fetching vulnerabilities.
Returns as soon as the vuln set is empty.

Updates golang/go#57357

Change-Id: I310b93f7125b5edcc2a5744db9f9f595c70aa5d4
Reviewed-on: https://go-review.googlesource.com/c/vuln/+/460420
TryBot-Result: Gopher Robot <[email protected]>
Reviewed-by: Alan Donovan <[email protected]>
Run-TryBot: Tim King <[email protected]>
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
sayjun0505 added a commit to sayjun0505/Golangvuln that referenced this issue Apr 8, 2023
@sayjun0505
vulncheck: build callgraph in parallel with fetching db
8d077a0 
Source(...) now builds the *ssa.Program and callgraph from
the *ssa.Program in parallel with fetching vulnerabilities.
Returns as soon as the vuln set is empty.

Updates golang/go#57357

Change-Id: I310b93f7125b5edcc2a5744db9f9f595c70aa5d4
Reviewed-on: https://go-review.googlesource.com/c/vuln/+/460420
TryBot-Result: Gopher Robot <[email protected]>
Reviewed-by: Alan Donovan <[email protected]>
Run-TryBot: Tim King <[email protected]>
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
stanislavkononiuk added a commit to stanislavkononiuk/Golangvuln that referenced this issue Jun 26, 2023
@stanislavkononiuk
vulncheck: build callgraph in parallel with fetching db
6f5a767 
Source(...) now builds the *ssa.Program and callgraph from
the *ssa.Program in parallel with fetching vulnerabilities.
Returns as soon as the vuln set is empty.

Updates golang/go#57357

Change-Id: I310b93f7125b5edcc2a5744db9f9f595c70aa5d4
Reviewed-on: https://go-review.googlesource.com/c/vuln/+/460420
TryBot-Result: Gopher Robot <[email protected]>
Reviewed-by: Alan Donovan <[email protected]>
Run-TryBot: Tim King <[email protected]>
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/609978 mentions this issue: go/callgraph/vta: allow nil initial call graph

gopherbot pushed a commit to golang/tools that referenced this issue Sep 3, 2024
@zpavlinovic
go/callgraph/vta: allow nil initial call graph
09886e0 
When nil is passed as the initial call graph, vta will use a more
performant version of CHA. For this purpose, lazyCallees function of CHA
is exposed to VTA.

This change reduces the time and memory footprint for ~10%, measured on
several large real world Go projects.

Updates golang/go#57357

Change-Id: Ib5c5edca0026e6902e453fa10fc14f2b763849db
Reviewed-on: https://go-review.googlesource.com/c/tools/+/609978
LUCI-TryBot-Result: Go LUCI <[email protected]>
Reviewed-by: Alan Donovan <[email protected]>
@zpavlinovic
Copy link
Contributor

All three mentioned optimizations are now done so I am marking this complete.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@timothy-king timothy-king

@zpavlinovic zpavlinovic

Labels
vulncheck or vulndb Issues for the x/vuln or x/vulndb repo
Projects
None yet
Milestone
vuln/unplanned
Development

No branches or pull requests
4 participants
@timothy-king @zpavlinovic @adonovan @gopherbot