critical_path.go 3.7 KB

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