blob: 7fbeec62b80bcac92251c2822b36a41a1f92d396 [file] [log] [blame]
Shinichiro Hamajib69bf8a2015-06-10 14:52:06 +09001// Copyright 2015 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
Fumitoshi Ukai744bb2b2015-06-25 00:10:52 +090015package kati
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090016
17import (
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +090018 "container/heap"
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +090019 "errors"
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090020 "fmt"
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +090021 "os"
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090022 "os/exec"
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090023 "syscall"
24 "time"
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +090025
26 "github.com/golang/glog"
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090027)
28
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +090029var (
30 errNothingDone = errors.New("nothing done")
31)
32
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090033type job struct {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090034 n *DepNode
35 ex *Executor
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090036 parents []*job
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090037 outputTs int64
38 numDeps int
39 depsTs int64
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090040 id int
Shinichiro Hamajia6808422015-05-13 18:00:50 +090041
42 runners []runner
Shinichiro Hamaji74a66002015-04-27 16:42:30 +090043}
44
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090045type jobResult struct {
Fumitoshi Ukai65c72332015-06-26 21:32:50 +090046 j *job
47 w *worker
48 err error
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090049}
50
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090051type newDep struct {
52 j *job
53 neededBy *job
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090054}
55
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090056type worker struct {
57 wm *workerManager
58 jobChan chan *job
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090059 waitChan chan bool
60 doneChan chan bool
61}
62
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090063type jobQueue []*job
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +090064
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090065func (jq jobQueue) Len() int { return len(jq) }
66func (jq jobQueue) Swap(i, j int) { jq[i], jq[j] = jq[j], jq[i] }
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +090067
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090068func (jq jobQueue) Less(i, j int) bool {
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +090069 // First come, first serve, for GNU make compatibility.
70 return jq[i].id < jq[j].id
71}
72
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090073func (jq *jobQueue) Push(x interface{}) {
74 item := x.(*job)
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +090075 *jq = append(*jq, item)
76}
77
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090078func (jq *jobQueue) Pop() interface{} {
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +090079 old := *jq
80 n := len(old)
81 item := old[n-1]
82 *jq = old[0 : n-1]
83 return item
84}
85
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090086func newWorker(wm *workerManager) *worker {
87 w := &worker{
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090088 wm: wm,
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090089 jobChan: make(chan *job),
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090090 waitChan: make(chan bool),
91 doneChan: make(chan bool),
92 }
93 return w
94}
95
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +090096func (w *worker) Run() {
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +090097 done := false
98 for !done {
99 select {
100 case j := <-w.jobChan:
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900101 err := j.build()
102 w.wm.ReportResult(w, j, err)
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900103 case done = <-w.waitChan:
104 }
105 }
106 w.doneChan <- true
107}
108
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900109func (w *worker) PostJob(j *job) {
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900110 w.jobChan <- j
111}
112
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900113func (w *worker) Wait() {
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900114 w.waitChan <- true
115 <-w.doneChan
116}
117
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900118func (j *job) createRunners() ([]runner, error) {
Fumitoshi Ukaia70b4ea2015-06-30 15:31:49 +0900119 runners, _, err := createRunners(j.ex.ctx, j.n)
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900120 return runners, err
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900121}
122
Shinichiro Hamaji71fae4c2015-05-25 17:48:34 +0900123// TODO(ukai): use time.Time?
124func getTimestamp(filename string) int64 {
125 st, err := os.Stat(filename)
126 if err != nil {
127 return -2
128 }
129 return st.ModTime().Unix()
130}
131
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900132func (j *job) build() error {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900133 if j.n.IsPhony {
134 j.outputTs = -2 // trigger cmd even if all inputs don't exist.
135 } else {
136 j.outputTs = getTimestamp(j.n.Output)
137 }
138
139 if !j.n.HasRule {
140 if j.outputTs >= 0 || j.n.IsPhony {
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +0900141 return errNothingDone
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900142 }
143 if len(j.parents) == 0 {
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900144 return fmt.Errorf("*** No rule to make target %q.", j.n.Output)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900145 }
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900146 return fmt.Errorf("*** No rule to make target %q, needed by %q.", j.n.Output, j.parents[0].n.Output)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900147 }
148
149 if j.outputTs >= j.depsTs {
150 // TODO: stats.
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +0900151 return errNothingDone
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900152 }
153
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900154 rr, err := j.createRunners()
155 if err != nil {
156 return err
157 }
158 for _, r := range rr {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900159 err := r.run(j.n.Output)
Fumitoshi Ukai60f92c02015-07-29 10:09:36 +0900160 glog.Warningf("cmd result for %q: %v", j.n.Output, err)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900161 if err != nil {
162 exit := exitStatus(err)
Fumitoshi Ukai08c1e942015-07-15 16:38:07 +0900163 return fmt.Errorf("*** [%s] Error %d", j.n.Output, exit)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900164 }
165 }
166
167 if j.n.IsPhony {
168 j.outputTs = time.Now().Unix()
169 } else {
170 j.outputTs = getTimestamp(j.n.Output)
171 if j.outputTs < 0 {
172 j.outputTs = time.Now().Unix()
173 }
174 }
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900175 return nil
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900176}
177
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900178func (wm *workerManager) handleJobs() error {
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900179 for {
Shinichiro Hamaji18287f02015-07-06 14:48:48 +0900180 if len(wm.freeWorkers) == 0 {
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900181 return nil
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900182 }
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900183 if wm.readyQueue.Len() == 0 {
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900184 return nil
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900185 }
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900186 j := heap.Pop(&wm.readyQueue).(*job)
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900187 glog.V(1).Infof("run: %s", j.n.Output)
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +0900188
Shinichiro Hamaji18287f02015-07-06 14:48:48 +0900189 j.numDeps = -1 // Do not let other workers pick this.
190 w := wm.freeWorkers[0]
191 wm.freeWorkers = wm.freeWorkers[1:]
192 wm.busyWorkers[w] = true
193 w.jobChan <- j
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900194 }
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900195}
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900196
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900197func (wm *workerManager) updateParents(j *job) {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900198 for _, p := range j.parents {
199 p.numDeps--
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900200 glog.V(1).Infof("child: %s (%d)", p.n.Output, p.numDeps)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900201 if p.depsTs < j.outputTs {
202 p.depsTs = j.outputTs
203 }
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900204 wm.maybePushToReadyQueue(p)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900205 }
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900206}
207
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900208type workerManager struct {
Fumitoshi Ukai744bb2b2015-06-25 00:10:52 +0900209 maxJobs int
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900210 jobs []*job
211 readyQueue jobQueue
212 jobChan chan *job
213 resultChan chan jobResult
214 newDepChan chan newDep
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900215 stopChan chan bool
Shinichiro Hamaji55c50bd2015-04-27 21:05:47 +0900216 waitChan chan bool
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900217 doneChan chan error
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900218 freeWorkers []*worker
219 busyWorkers map[*worker]bool
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +0900220 ex *Executor
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900221 runnings map[string]*job
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900222
223 finishCnt int
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +0900224 skipCnt int
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900225}
226
Shinichiro Hamaji18287f02015-07-06 14:48:48 +0900227func newWorkerManager(numJobs int) (*workerManager, error) {
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900228 wm := &workerManager{
Fumitoshi Ukai744bb2b2015-06-25 00:10:52 +0900229 maxJobs: numJobs,
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900230 jobChan: make(chan *job),
231 resultChan: make(chan jobResult),
232 newDepChan: make(chan newDep),
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900233 stopChan: make(chan bool),
Shinichiro Hamaji55c50bd2015-04-27 21:05:47 +0900234 waitChan: make(chan bool),
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900235 doneChan: make(chan error),
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900236 busyWorkers: make(map[*worker]bool),
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900237 }
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +0900238
Shinichiro Hamaji18287f02015-07-06 14:48:48 +0900239 wm.busyWorkers = make(map[*worker]bool)
240 for i := 0; i < numJobs; i++ {
241 w := newWorker(wm)
242 wm.freeWorkers = append(wm.freeWorkers, w)
243 go w.Run()
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900244 }
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +0900245 heap.Init(&wm.readyQueue)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900246 go wm.Run()
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900247 return wm, nil
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900248}
249
250func exitStatus(err error) int {
251 if err == nil {
252 return 0
253 }
254 exit := 1
255 if err, ok := err.(*exec.ExitError); ok {
256 if w, ok := err.ProcessState.Sys().(syscall.WaitStatus); ok {
257 return w.ExitStatus()
258 }
259 }
260 return exit
261}
262
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900263func (wm *workerManager) hasTodo() bool {
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900264 return wm.finishCnt != len(wm.jobs)
265}
266
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900267func (wm *workerManager) maybePushToReadyQueue(j *job) {
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900268 if j.numDeps != 0 {
269 return
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900270 }
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900271 heap.Push(&wm.readyQueue, j)
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900272 glog.V(1).Infof("ready: %s", j.n.Output)
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900273}
274
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900275func (wm *workerManager) handleNewDep(j *job, neededBy *job) {
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900276 if j.numDeps < 0 {
277 neededBy.numDeps--
Shinichiro Hamaji5180c972015-04-28 20:14:38 +0900278 if neededBy.id > 0 {
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900279 panic("FIXME: already in WM... can this happen?")
Shinichiro Hamaji5180c972015-04-28 20:14:38 +0900280 }
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900281 } else {
282 j.parents = append(j.parents, neededBy)
283 }
284}
285
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900286func (wm *workerManager) Run() {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900287 done := false
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900288 var err error
289Loop:
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +0900290 for wm.hasTodo() || len(wm.busyWorkers) > 0 || len(wm.runnings) > 0 || !done {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900291 select {
292 case j := <-wm.jobChan:
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900293 glog.V(1).Infof("wait: %s (%d)", j.n.Output, j.numDeps)
Shinichiro Hamaji5180c972015-04-28 20:14:38 +0900294 j.id = len(wm.jobs) + 1
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900295 wm.jobs = append(wm.jobs, j)
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900296 wm.maybePushToReadyQueue(j)
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900297 case jr := <-wm.resultChan:
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900298 glog.V(1).Infof("done: %s", jr.j.n.Output)
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900299 delete(wm.busyWorkers, jr.w)
300 wm.freeWorkers = append(wm.freeWorkers, jr.w)
301 wm.updateParents(jr.j)
Shinichiro Hamajidbc6c132015-04-28 18:26:36 +0900302 wm.finishCnt++
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +0900303 if jr.err == errNothingDone {
304 wm.skipCnt++
305 jr.err = nil
306 }
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900307 if jr.err != nil {
308 err = jr.err
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900309 close(wm.stopChan)
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900310 break Loop
311 }
Shinichiro Hamaji55c50bd2015-04-27 21:05:47 +0900312 case af := <-wm.newDepChan:
313 wm.handleNewDep(af.j, af.neededBy)
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900314 glog.V(1).Infof("dep: %s (%d) %s", af.neededBy.n.Output, af.neededBy.numDeps, af.j.n.Output)
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900315 case done = <-wm.waitChan:
316 }
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900317 err = wm.handleJobs()
318 if err != nil {
319 break Loop
320 }
Shinichiro Hamajicedc5c82015-05-13 17:03:20 +0900321
Fumitoshi Ukai6450d0f2015-07-10 16:34:06 +0900322 glog.V(1).Infof("job=%d ready=%d free=%d busy=%d", len(wm.jobs)-wm.finishCnt, wm.readyQueue.Len(), len(wm.freeWorkers), len(wm.busyWorkers))
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900323 }
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900324 if !done {
325 <-wm.waitChan
326 }
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900327
Shinichiro Hamaji18287f02015-07-06 14:48:48 +0900328 for _, w := range wm.freeWorkers {
329 w.Wait()
330 }
331 for w := range wm.busyWorkers {
332 w.Wait()
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900333 }
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900334 wm.doneChan <- err
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900335}
336
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900337func (wm *workerManager) PostJob(j *job) error {
338 select {
339 case wm.jobChan <- j:
340 return nil
341 case <-wm.stopChan:
342 return errors.New("worker manager stopped")
343 }
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900344}
345
Fumitoshi Ukai65c72332015-06-26 21:32:50 +0900346func (wm *workerManager) ReportResult(w *worker, j *job, err error) {
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900347 select {
348 case wm.resultChan <- jobResult{w: w, j: j, err: err}:
349 case <-wm.stopChan:
350 }
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900351}
352
Fumitoshi Ukaidfb518b2015-06-25 13:19:55 +0900353func (wm *workerManager) ReportNewDep(j *job, neededBy *job) {
Fumitoshi Ukai531c5d22015-06-27 00:58:56 +0900354 select {
355 case wm.newDepChan <- newDep{j: j, neededBy: neededBy}:
356 case <-wm.stopChan:
357 }
Shinichiro Hamaji69bb7e42015-04-27 17:54:42 +0900358}
359
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +0900360func (wm *workerManager) Wait() (int, error) {
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900361 wm.waitChan <- true
Fumitoshi Ukaia43b96f2015-07-17 19:54:21 +0900362 err := <-wm.doneChan
363 return wm.finishCnt - wm.skipCnt, err
Shinichiro Hamaji74a66002015-04-27 16:42:30 +0900364}