1// Copyright 2019 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 status
16
17import (
18	"android/soong/ui/metrics"
19
20	soong_metrics_proto "android/soong/ui/metrics/metrics_proto"
21	"time"
22
23	"google.golang.org/protobuf/proto"
24)
25
26func NewCriticalPath() *CriticalPath {
27	return &CriticalPath{
28		running: make(map[*Action]time.Time),
29		nodes:   make(map[string]*node),
30		clock:   osClock{},
31	}
32}
33
34type CriticalPath struct {
35	nodes   map[string]*node
36	running map[*Action]time.Time
37
38	start, end time.Time
39
40	clock clock
41}
42
43type clock interface {
44	Now() time.Time
45}
46
47type osClock struct{}
48
49func (osClock) Now() time.Time { return time.Now() }
50
51// A critical path node stores the critical path (the minimum time to build the node and all of its dependencies given
52// perfect parallelism) for an node.
53type node struct {
54	action             *Action
55	cumulativeDuration time.Duration
56	duration           time.Duration
57	input              *node
58}
59
60func (cp *CriticalPath) StartAction(action *Action) {
61	start := cp.clock.Now()
62	if cp.start.IsZero() {
63		cp.start = start
64	}
65	cp.running[action] = start
66}
67
68func (cp *CriticalPath) FinishAction(action *Action) {
69	if start, ok := cp.running[action]; ok {
70		delete(cp.running, action)
71
72		// Determine the input to this edge with the longest cumulative duration
73		var criticalPathInput *node
74		for _, input := range action.Inputs {
75			if x := cp.nodes[input]; x != nil {
76				if criticalPathInput == nil || x.cumulativeDuration > criticalPathInput.cumulativeDuration {
77					criticalPathInput = x
78				}
79			}
80		}
81
82		end := cp.clock.Now()
83		duration := end.Sub(start)
84
85		cumulativeDuration := duration
86		if criticalPathInput != nil {
87			cumulativeDuration += criticalPathInput.cumulativeDuration
88		}
89
90		node := &node{
91			action:             action,
92			cumulativeDuration: cumulativeDuration,
93			duration:           duration,
94			input:              criticalPathInput,
95		}
96
97		for _, output := range action.Outputs {
98			cp.nodes[output] = node
99		}
100
101		cp.end = end
102	}
103}
104
105func (cp *CriticalPath) criticalPath() (path []*node, elapsedTime time.Duration, criticalTime time.Duration) {
106	var max *node
107
108	// Find the node with the longest critical path
109	for _, node := range cp.nodes {
110		if max == nil || node.cumulativeDuration > max.cumulativeDuration {
111			max = node
112		}
113	}
114
115	node := max
116	for node != nil {
117		path = append(path, node)
118		node = node.input
119	}
120	if len(path) > 0 {
121		// Log the critical path to the verbose log
122		criticalTime = path[0].cumulativeDuration
123		if !cp.start.IsZero() {
124			elapsedTime = cp.end.Sub(cp.start)
125		}
126	}
127	return
128}
129
130func (cp *CriticalPath) longRunningJobs() (nodes []*node) {
131	threshold := time.Second * 30
132	for _, node := range cp.nodes {
133		if node != nil && node.duration > threshold {
134			nodes = append(nodes, node)
135		}
136	}
137	return
138}
139
140func addJobInfos(jobInfos *[]*soong_metrics_proto.JobInfo, sources []*node) {
141	for _, job := range sources {
142		jobInfo := soong_metrics_proto.JobInfo{}
143		jobInfo.ElapsedTimeMicros = proto.Uint64(uint64(job.duration.Microseconds()))
144		jobInfo.JobDescription = &job.action.Description
145		*jobInfos = append(*jobInfos, &jobInfo)
146	}
147}
148
149func (cp *CriticalPath) WriteToMetrics(met *metrics.Metrics) {
150	criticalPathInfo := soong_metrics_proto.CriticalPathInfo{}
151	path, elapsedTime, criticalTime := cp.criticalPath()
152	criticalPathInfo.ElapsedTimeMicros = proto.Uint64(uint64(elapsedTime.Microseconds()))
153	criticalPathInfo.CriticalPathTimeMicros = proto.Uint64(uint64(criticalTime.Microseconds()))
154	addJobInfos(&criticalPathInfo.LongRunningJobs, cp.longRunningJobs())
155	addJobInfos(&criticalPathInfo.CriticalPath, path)
156	met.SetCriticalPathInfo(criticalPathInfo)
157}
158