runqueue.py: Switch to check_stamp code since its simpler than check_stamps and accou...
[bitbake.git] / lib / bb / runqueue.py
1 #!/usr/bin/env python
2 # ex:ts=4:sw=4:sts=4:et
3 # -*- tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
4 """
5 BitBake 'RunQueue' implementation
6
7 Handles preparation and execution of a queue of tasks
8 """
9
10 # Copyright (C) 2006-2007  Richard Purdie
11 #
12 # This program is free software; you can redistribute it and/or modify
13 # it under the terms of the GNU General Public License version 2 as
14 # published by the Free Software Foundation.
15 #
16 # This program is distributed in the hope that it will be useful,
17 # but WITHOUT ANY WARRANTY; without even the implied warranty of
18 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19 # GNU General Public License for more details.
20 #
21 # You should have received a copy of the GNU General Public License along
22 # with this program; if not, write to the Free Software Foundation, Inc.,
23 # 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24
25 from bb import msg, data, event, mkdirhier, utils
26 from sets import Set 
27 import bb, os, sys
28 import signal
29 import stat
30
31 class TaskFailure(Exception):
32     """Exception raised when a task in a runqueue fails"""
33     def __init__(self, x): 
34         self.args = x
35
36
37 class RunQueueStats:
38     """
39     Holds statistics on the tasks handled by the associated runQueue
40     """
41     def __init__(self):
42         self.completed = 0
43         self.skipped = 0
44         self.failed = 0
45
46     def taskFailed(self):
47         self.failed = self.failed + 1
48
49     def taskCompleted(self, number = 1):
50         self.completed = self.completed + number
51
52     def taskSkipped(self, number = 1):
53         self.skipped = self.skipped + number
54
55 class RunQueueScheduler:
56     """
57     Control the order tasks are scheduled in.
58     """
59     def __init__(self, runqueue):
60         """
61         The default scheduler just returns the first buildable task (the 
62         priority map is sorted by task numer)
63         """
64         self.rq = runqueue
65         numTasks = len(self.rq.runq_fnid)
66
67         self.prio_map = []
68         self.prio_map.extend(range(numTasks))
69
70     def next(self):
71         """
72         Return the id of the first task we find that is buildable
73         """
74         for task1 in range(len(self.rq.runq_fnid)):
75             task = self.prio_map[task1]
76             if self.rq.runq_running[task] == 1:
77                 continue
78             if self.rq.runq_buildable[task] == 1:
79                 return task
80
81 class RunQueueSchedulerSpeed(RunQueueScheduler):
82     """
83     A scheduler optimised for speed. The priority map is sorted by task weight,
84     heavier weighted tasks (tasks needed by the most other tasks) are run first.
85     """
86     def __init__(self, runqueue):
87         """
88         The priority map is sorted by task weight.
89         """
90         from copy import deepcopy
91
92         self.rq = runqueue
93
94         sortweight = deepcopy(self.rq.runq_weight)
95         sortweight.sort()
96         copyweight = deepcopy(self.rq.runq_weight)
97         self.prio_map = []
98
99         for weight in sortweight:
100             idx = copyweight.index(weight)
101             self.prio_map.append(idx)
102             copyweight[idx] = -1
103
104         self.prio_map.reverse()
105
106 class RunQueueSchedulerCompletion(RunQueueSchedulerSpeed):
107     """
108     A scheduler optimised to complete .bb files are quickly as possible. The 
109     priority map is sorted by task weight, but then reordered so once a given 
110     .bb file starts to build, its completed as quickly as possible. This works
111     well where disk space is at a premium and classes like OE's rm_work are in 
112     force.
113     """
114     def __init__(self, runqueue):
115         RunQueueSchedulerSpeed.__init__(self, runqueue)
116         from copy import deepcopy
117
118         #FIXME - whilst this groups all fnids together it does not reorder the
119         #fnid groups optimally.
120  
121         basemap = deepcopy(self.prio_map)
122         self.prio_map = []
123         while (len(basemap) > 0):
124             entry = basemap.pop(0)
125             self.prio_map.append(entry)
126             fnid = self.rq.runq_fnid[entry]
127             todel = []
128             for entry in basemap:
129                 entry_fnid = self.rq.runq_fnid[entry]
130                 if entry_fnid == fnid:
131                     todel.append(basemap.index(entry))
132                     self.prio_map.append(entry)
133             todel.reverse()
134             for idx in todel:
135                 del basemap[idx]
136
137 class RunQueue:
138     """
139     BitBake Run Queue implementation
140     """
141     def __init__(self, cooker, cfgData, dataCache, taskData, targets):
142         self.reset_runqueue()
143         self.cooker = cooker
144         self.dataCache = dataCache
145         self.taskData = taskData
146         self.targets = targets
147
148         self.cfgdata = cfgData
149         self.number_tasks = int(bb.data.getVar("BB_NUMBER_THREADS", cfgData, 1) or 1)
150         self.multi_provider_whitelist = (bb.data.getVar("MULTI_PROVIDER_WHITELIST", cfgData, 1) or "").split()
151         self.scheduler = bb.data.getVar("BB_SCHEDULER", cfgData, 1) or "speed"
152         self.stamppolicy = bb.data.getVar("BB_STAMP_POLICY", cfgData, 1) or "perfile"
153
154     def reset_runqueue(self):
155
156         self.runq_fnid = []
157         self.runq_task = []
158         self.runq_depends = []
159         self.runq_revdeps = []
160
161     def get_user_idstring(self, task):
162         fn = self.taskData.fn_index[self.runq_fnid[task]]
163         taskname = self.runq_task[task]
164         return "%s, %s" % (fn, taskname)
165
166     def circular_depchains_handler(self, tasks):
167         """
168         Some tasks aren't buildable, likely due to circular dependency issues.
169         Identify the circular dependencies and print them in a user readable format.
170         """
171         from copy import deepcopy
172
173         valid_chains = []
174         explored_deps = {}
175         msgs = []
176
177         def chain_reorder(chain):
178             """
179             Reorder a dependency chain so the lowest task id is first
180             """
181             lowest = 0
182             new_chain = []
183             for entry in range(len(chain)):
184                 if chain[entry] < chain[lowest]:
185                     lowest = entry
186             new_chain.extend(chain[lowest:])
187             new_chain.extend(chain[:lowest])
188             return new_chain
189
190         def chain_compare_equal(chain1, chain2):
191             """
192             Compare two dependency chains and see if they're the same
193             """
194             if len(chain1) != len(chain2):
195                 return False
196             for index in range(len(chain1)):
197                 if chain1[index] != chain2[index]:
198                     return False
199             return True
200             
201         def chain_array_contains(chain, chain_array):
202             """
203             Return True if chain_array contains chain
204             """
205             for ch in chain_array:
206                 if chain_compare_equal(ch, chain):
207                     return True
208             return False
209
210         def find_chains(taskid, prev_chain):
211             prev_chain.append(taskid)
212             total_deps = []
213             total_deps.extend(self.runq_revdeps[taskid])
214             for revdep in self.runq_revdeps[taskid]:
215                 if revdep in prev_chain:
216                     idx = prev_chain.index(revdep)
217                     # To prevent duplicates, reorder the chain to start with the lowest taskid
218                     # and search through an array of those we've already printed
219                     chain = prev_chain[idx:]
220                     new_chain = chain_reorder(chain)
221                     if not chain_array_contains(new_chain, valid_chains):
222                         valid_chains.append(new_chain)
223                         msgs.append("Dependency loop #%d found:\n" % len(valid_chains))
224                         for dep in new_chain:
225                             msgs.append("  Task %s (%s) (depends: %s)\n" % (dep, self.get_user_idstring(dep), self.runq_depends[dep]))
226                         msgs.append("\n")
227                     if len(valid_chains) > 10:
228                         msgs.append("Aborted dependency loops search after 10 matches.\n")
229                         return msgs
230                     continue
231                 scan = False
232                 if revdep not in explored_deps:
233                     scan = True
234                 elif revdep in explored_deps[revdep]:
235                     scan = True
236                 else:
237                     for dep in prev_chain:
238                         if dep in explored_deps[revdep]:
239                             scan = True
240                 if scan:
241                     find_chains(revdep, deepcopy(prev_chain))
242                 for dep in explored_deps[revdep]:
243                     if dep not in total_deps:
244                         total_deps.append(dep)
245
246             explored_deps[taskid] = total_deps
247
248         for task in tasks:
249             find_chains(task, [])
250
251         return msgs
252
253     def calculate_task_weights(self, endpoints):
254         """
255         Calculate a number representing the "weight" of each task. Heavier weighted tasks 
256         have more dependencies and hence should be executed sooner for maximum speed.
257
258         This function also sanity checks the task list finding tasks that its not
259         possible to execute due to circular dependencies.
260         """
261
262         numTasks = len(self.runq_fnid)
263         weight = []
264         deps_left = []
265         task_done = []
266
267         for listid in range(numTasks):
268             task_done.append(False)
269             weight.append(0)
270             deps_left.append(len(self.runq_revdeps[listid]))
271
272         for listid in endpoints:
273             weight[listid] = 1
274             task_done[listid] = True
275
276         while 1:
277             next_points = []
278             for listid in endpoints:
279                 for revdep in self.runq_depends[listid]:
280                     weight[revdep] = weight[revdep] + weight[listid]
281                     deps_left[revdep] = deps_left[revdep] - 1
282                     if deps_left[revdep] == 0:
283                         next_points.append(revdep)
284                         task_done[revdep] = True
285             endpoints = next_points
286             if len(next_points) == 0:
287                 break      
288
289         # Circular dependency sanity check
290         problem_tasks = []
291         for task in range(numTasks):
292             if task_done[task] is False or deps_left[task] != 0:
293                 problem_tasks.append(task)
294                 bb.msg.debug(2, bb.msg.domain.RunQueue, "Task %s (%s) is not buildable\n" % (task, self.get_user_idstring(task)))
295                 bb.msg.debug(2, bb.msg.domain.RunQueue, "(Complete marker was %s and the remaining dependency count was %s)\n\n" % (task_done[task], deps_left[task]))
296
297         if problem_tasks:
298             message = "Unbuildable tasks were found.\n"
299             message = message + "These are usually caused by circular dependencies and any circular dependency chains found will be printed below. Increase the debug level to see a list of unbuildable tasks.\n\n"
300             message = message + "Identifying dependency loops (this may take a short while)...\n"
301             bb.msg.error(bb.msg.domain.RunQueue, message)
302
303             msgs = self.circular_depchains_handler(problem_tasks)
304
305             message = "\n"
306             for msg in msgs:
307                 message = message + msg
308             bb.msg.fatal(bb.msg.domain.RunQueue, message)
309
310         return weight
311
312     def prepare_runqueue(self):
313         """
314         Turn a set of taskData into a RunQueue and compute data needed 
315         to optimise the execution order.
316         """
317
318         depends = []
319         runq_build = []
320
321         taskData = self.taskData
322
323         if len(taskData.tasks_name) == 0:
324             # Nothing to do
325             return
326
327         bb.msg.note(1, bb.msg.domain.RunQueue, "Preparing runqueue")
328
329         # Step A - Work out a list of tasks to run
330         #
331         # Taskdata gives us a list of possible providers for a every target 
332         # ordered by priority (build_targets, run_targets). It also gives
333         # information on each of those providers.
334         #
335         # To create the actual list of tasks to execute we fix the list of 
336         # providers and then resolve the dependencies into task IDs. This 
337         # process is repeated for each type of dependency (tdepends, deptask, 
338         # rdeptast, recrdeptask, idepends).
339
340         for task in range(len(taskData.tasks_name)):
341             fnid = taskData.tasks_fnid[task]
342             fn = taskData.fn_index[fnid]
343             task_deps = self.dataCache.task_deps[fn]
344
345             if fnid not in taskData.failed_fnids:
346
347                 # Resolve task internal dependencies 
348                 #
349                 # e.g. addtask before X after Y
350                 depends = taskData.tasks_tdepends[task]
351
352                 # Resolve 'deptask' dependencies 
353                 #
354                 # e.g. do_sometask[deptask] = "do_someothertask"
355                 # (makes sure sometask runs after someothertask of all DEPENDS)
356                 if 'deptask' in task_deps and taskData.tasks_name[task] in task_deps['deptask']:
357                     tasknames = task_deps['deptask'][taskData.tasks_name[task]].split()
358                     for depid in taskData.depids[fnid]:
359                         # Won't be in build_targets if ASSUME_PROVIDED
360                         if depid in taskData.build_targets:
361                             depdata = taskData.build_targets[depid][0]
362                             if depdata is not None:
363                                 dep = taskData.fn_index[depdata]
364                                 for taskname in tasknames:
365                                     depends.append(taskData.gettask_id(dep, taskname))
366
367                 # Resolve 'rdeptask' dependencies 
368                 #
369                 # e.g. do_sometask[rdeptask] = "do_someothertask"
370                 # (makes sure sometask runs after someothertask of all RDEPENDS)
371                 if 'rdeptask' in task_deps and taskData.tasks_name[task] in task_deps['rdeptask']:
372                     taskname = task_deps['rdeptask'][taskData.tasks_name[task]]
373                     for depid in taskData.rdepids[fnid]:
374                         if depid in taskData.run_targets:
375                             depdata = taskData.run_targets[depid][0]
376                             if depdata is not None:
377                                 dep = taskData.fn_index[depdata]
378                                 depends.append(taskData.gettask_id(dep, taskname))
379
380                 # Resolve inter-task dependencies 
381                 #
382                 # e.g. do_sometask[depends] = "targetname:do_someothertask"
383                 # (makes sure sometask runs after targetname's someothertask)
384                 idepends = taskData.tasks_idepends[task]
385                 for (depid, idependtask) in idepends:
386                     if depid in taskData.build_targets:
387                         # Won't be in build_targets if ASSUME_PROVIDED
388                         depdata = taskData.build_targets[depid][0]
389                         if depdata is not None:
390                             dep = taskData.fn_index[depdata]
391                             depends.append(taskData.gettask_id(dep, idependtask))
392
393                 def add_recursive_build(depid, depfnid):
394                     """
395                     Add build depends of depid to depends
396                     (if we've not see it before)
397                     (calls itself recursively)
398                     """
399                     if str(depid) in dep_seen:
400                         return
401                     dep_seen.append(depid)
402                     if depid in taskData.build_targets:
403                         depdata = taskData.build_targets[depid][0]
404                         if depdata is not None:
405                             dep = taskData.fn_index[depdata]
406                             idepends = []
407                             # Need to avoid creating new tasks here
408                             taskid = taskData.gettask_id(dep, taskname, False)
409                             if taskid is not None:
410                                 depends.append(taskid)
411                                 fnid = taskData.tasks_fnid[taskid]
412                                 idepends = taskData.tasks_idepends[taskid]
413                                 #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
414                             else:
415                                 fnid = taskData.getfn_id(dep)
416                             for nextdepid in taskData.depids[fnid]:
417                                 if nextdepid not in dep_seen:
418                                     add_recursive_build(nextdepid, fnid)
419                             for nextdepid in taskData.rdepids[fnid]:
420                                 if nextdepid not in rdep_seen:
421                                     add_recursive_run(nextdepid, fnid)
422                             for (idependid, idependtask) in idepends:
423                                 if idependid not in dep_seen:
424                                     add_recursive_build(idependid, fnid)
425
426                 def add_recursive_run(rdepid, depfnid):
427                     """
428                     Add runtime depends of rdepid to depends
429                     (if we've not see it before)
430                     (calls itself recursively)
431                     """
432                     if str(rdepid) in rdep_seen:
433                         return
434                     rdep_seen.append(rdepid)
435                     if rdepid in taskData.run_targets:
436                         depdata = taskData.run_targets[rdepid][0]
437                         if depdata is not None:
438                             dep = taskData.fn_index[depdata]
439                             idepends = []
440                             # Need to avoid creating new tasks here
441                             taskid = taskData.gettask_id(dep, taskname, False)
442                             if taskid is not None:
443                                 depends.append(taskid)
444                                 fnid = taskData.tasks_fnid[taskid]
445                                 idepends = taskData.tasks_idepends[taskid]
446                                 #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
447                             else:
448                                 fnid = taskData.getfn_id(dep)
449                             for nextdepid in taskData.depids[fnid]:
450                                 if nextdepid not in dep_seen:
451                                     add_recursive_build(nextdepid, fnid)
452                             for nextdepid in taskData.rdepids[fnid]:
453                                 if nextdepid not in rdep_seen:
454                                     add_recursive_run(nextdepid, fnid)
455                             for (idependid, idependtask) in idepends:
456                                 if idependid not in dep_seen:
457                                     add_recursive_build(idependid, fnid)
458
459                 # Resolve recursive 'recrdeptask' dependencies 
460                 #
461                 # e.g. do_sometask[recrdeptask] = "do_someothertask"
462                 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
463                 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']:
464                     for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split():
465                         dep_seen = []
466                         rdep_seen = []
467                         idep_seen = []
468                         for depid in taskData.depids[fnid]:
469                             add_recursive_build(depid, fnid)
470                         for rdepid in taskData.rdepids[fnid]:
471                             add_recursive_run(rdepid, fnid)
472                         for (idependid, idependtask) in idepends:
473                             add_recursive_build(idependid, fnid)
474
475                 # Rmove all self references
476                 if task in depends:
477                     newdep = []
478                     bb.msg.debug(2, bb.msg.domain.RunQueue, "Task %s (%s %s) contains self reference! %s" % (task, taskData.fn_index[taskData.tasks_fnid[task]], taskData.tasks_name[task], depends))
479                     for dep in depends:
480                        if task != dep:
481                           newdep.append(dep)
482                     depends = newdep
483
484
485             self.runq_fnid.append(taskData.tasks_fnid[task])
486             self.runq_task.append(taskData.tasks_name[task])
487             self.runq_depends.append(Set(depends))
488             self.runq_revdeps.append(Set())
489
490             runq_build.append(0)
491
492         # Step B - Mark all active tasks
493         #
494         # Start with the tasks we were asked to run and mark all dependencies
495         # as active too. If the task is to be 'forced', clear its stamp. Once
496         # all active tasks are marked, prune the ones we don't need.
497
498         bb.msg.note(2, bb.msg.domain.RunQueue, "Marking Active Tasks")
499
500         def mark_active(listid, depth):
501             """
502             Mark an item as active along with its depends
503             (calls itself recursively)
504             """
505
506             if runq_build[listid] == 1:
507                 return
508
509             runq_build[listid] = 1
510
511             depends = self.runq_depends[listid]
512             for depend in depends:
513                 mark_active(depend, depth+1)
514
515         self.target_pairs = []
516         for target in self.targets:
517             targetid = taskData.getbuild_id(target[0])
518
519             if targetid not in taskData.build_targets:
520                 continue
521
522             if targetid in taskData.failed_deps:
523                 continue
524
525             fnid = taskData.build_targets[targetid][0]
526             fn = taskData.fn_index[fnid]
527             self.target_pairs.append((fn, target[1]))
528
529             # Remove stamps for targets if force mode active
530             if self.cooker.configuration.force:
531                 bb.msg.note(2, bb.msg.domain.RunQueue, "Remove stamp %s, %s" % (target[1], fn))
532                 bb.build.del_stamp(target[1], self.dataCache, fn)
533
534             if fnid in taskData.failed_fnids:
535                 continue
536
537             if target[1] not in taskData.tasks_lookup[fnid]:
538                 bb.msg.fatal(bb.msg.domain.RunQueue, "Task %s does not exist for target %s" % (target[1], target[0]))
539
540             listid = taskData.tasks_lookup[fnid][target[1]]
541
542             mark_active(listid, 1)
543
544         # Step C - Prune all inactive tasks
545         #
546         # Once all active tasks are marked, prune the ones we don't need.
547
548         maps = []
549         delcount = 0
550         for listid in range(len(self.runq_fnid)):
551             if runq_build[listid-delcount] == 1:
552                 maps.append(listid-delcount)
553             else:
554                 del self.runq_fnid[listid-delcount]
555                 del self.runq_task[listid-delcount]
556                 del self.runq_depends[listid-delcount]
557                 del runq_build[listid-delcount]
558                 del self.runq_revdeps[listid-delcount]
559                 delcount = delcount + 1
560                 maps.append(-1)
561
562         #
563         # Step D - Sanity checks and computation
564         #
565
566         # Check to make sure we still have tasks to run
567         if len(self.runq_fnid) == 0:
568             if not taskData.abort:
569                 bb.msg.fatal(bb.msg.domain.RunQueue, "All buildable tasks have been run but the build is incomplete (--continue mode). Errors for the tasks that failed will have been printed above.")
570             else:               
571                 bb.msg.fatal(bb.msg.domain.RunQueue, "No active tasks and not in --continue mode?! Please report this bug.")
572
573         bb.msg.note(2, bb.msg.domain.RunQueue, "Pruned %s inactive tasks, %s left" % (delcount, len(self.runq_fnid)))
574
575         # Remap the dependencies to account for the deleted tasks
576         # Check we didn't delete a task we depend on
577         for listid in range(len(self.runq_fnid)):
578             newdeps = []
579             origdeps = self.runq_depends[listid]
580             for origdep in origdeps:
581                 if maps[origdep] == -1:
582                     bb.msg.fatal(bb.msg.domain.RunQueue, "Invalid mapping - Should never happen!")
583                 newdeps.append(maps[origdep])
584             self.runq_depends[listid] = Set(newdeps)
585
586         bb.msg.note(2, bb.msg.domain.RunQueue, "Assign Weightings")
587
588         # Generate a list of reverse dependencies to ease future calculations
589         for listid in range(len(self.runq_fnid)):
590             for dep in self.runq_depends[listid]:
591                 self.runq_revdeps[dep].add(listid)
592
593         # Identify tasks at the end of dependency chains
594         # Error on circular dependency loops (length two)
595         endpoints = []
596         for listid in range(len(self.runq_fnid)):
597             revdeps = self.runq_revdeps[listid]
598             if len(revdeps) == 0:
599                 endpoints.append(listid)
600             for dep in revdeps:
601                 if dep in self.runq_depends[listid]:
602                     #self.dump_data(taskData)
603                     bb.msg.fatal(bb.msg.domain.RunQueue, "Task %s (%s) has circular dependency on %s (%s)" % (taskData.fn_index[self.runq_fnid[dep]], self.runq_task[dep] , taskData.fn_index[self.runq_fnid[listid]], self.runq_task[listid]))
604
605         bb.msg.note(2, bb.msg.domain.RunQueue, "Compute totals (have %s endpoint(s))" % len(endpoints))
606
607
608         # Calculate task weights 
609         # Check of higher length circular dependencies
610         self.runq_weight = self.calculate_task_weights(endpoints)
611
612         # Decide what order to execute the tasks in, pick a scheduler
613         #self.sched = RunQueueScheduler(self)
614         if self.scheduler == "completion":
615             self.sched = RunQueueSchedulerCompletion(self)
616         else:
617             self.sched = RunQueueSchedulerSpeed(self)
618
619         # Sanity Check - Check for multiple tasks building the same provider
620         prov_list = {}
621         seen_fn = []
622         for task in range(len(self.runq_fnid)):
623             fn = taskData.fn_index[self.runq_fnid[task]]
624             if fn in seen_fn:
625                 continue
626             seen_fn.append(fn)
627             for prov in self.dataCache.fn_provides[fn]:
628                 if prov not in prov_list:
629                     prov_list[prov] = [fn]
630                 elif fn not in prov_list[prov]: 
631                     prov_list[prov].append(fn)
632         error = False
633         for prov in prov_list:
634             if len(prov_list[prov]) > 1 and prov not in self.multi_provider_whitelist:
635                 error = True
636                 bb.msg.error(bb.msg.domain.RunQueue, "Multiple .bb files are due to be built which each provide %s (%s).\n This usually means one provides something the other doesn't and should." % (prov, " ".join(prov_list[prov])))
637         #if error:
638         #    bb.msg.fatal(bb.msg.domain.RunQueue, "Corrupted metadata configuration detected, aborting...")
639
640         #self.dump_data(taskData)
641
642     def check_stamps(self):
643         unchecked = {}
644         current = []
645         notcurrent = []
646         buildable = []
647
648         if self.stamppolicy == "perfile":
649             fulldeptree = False
650         else:
651             fulldeptree = True
652
653         for task in range(len(self.runq_fnid)):
654             unchecked[task] = ""
655             if len(self.runq_depends[task]) == 0:
656                 buildable.append(task)
657
658         def check_buildable(self, task, buildable):
659              for revdep in self.runq_revdeps[task]:
660                 alldeps = 1
661                 for dep in self.runq_depends[revdep]:
662                     if dep in unchecked:
663                         alldeps = 0
664                 if alldeps == 1:
665                     if revdep in unchecked:
666                         buildable.append(revdep)
667
668         for task in range(len(self.runq_fnid)):
669             if task not in unchecked:
670                 continue
671             fn = self.taskData.fn_index[self.runq_fnid[task]]
672             taskname = self.runq_task[task]
673             stampfile = "%s.%s" % (self.dataCache.stamp[fn], taskname)
674             # If the stamp is missing its not current
675             if not os.access(stampfile, os.F_OK):
676                 del unchecked[task]
677                 notcurrent.append(task)
678                 check_buildable(self, task, buildable)
679                 continue
680             # If its a 'nostamp' task, it's not current
681             taskdep = self.dataCache.task_deps[fn]
682             if 'nostamp' in taskdep and task in taskdep['nostamp']:
683                 del unchecked[task]
684                 notcurrent.append(task)
685                 check_buildable(self, task, buildable)
686                 continue
687
688         while (len(buildable) > 0):
689             nextbuildable = []
690             for task in buildable:
691                 if task in unchecked:
692                     fn = self.taskData.fn_index[self.runq_fnid[task]]
693                     taskname = self.runq_task[task]
694                     stampfile = "%s.%s" % (self.dataCache.stamp[fn], taskname)
695                     iscurrent = True
696
697                     t1 = os.stat(stampfile)[stat.ST_MTIME]
698                     for dep in self.runq_depends[task]:
699                         if iscurrent:
700                             fn2 = self.taskData.fn_index[self.runq_fnid[dep]]
701                             taskname2 = self.runq_task[dep]
702                             stampfile2 = "%s.%s" % (self.dataCache.stamp[fn2], taskname2)
703                             if fulldeptree or fn == fn2:
704                                 if dep in notcurrent:
705                                     iscurrent = False
706                                 else:
707                                     t2 = os.stat(stampfile2)[stat.ST_MTIME]
708                                     if t1 < t2:
709                                         iscurrent = False
710                     del unchecked[task]
711                     if iscurrent:
712                         current.append(task)
713                     else:
714                         notcurrent.append(task)
715
716                 check_buildable(self, task, nextbuildable)
717
718             buildable = nextbuildable
719
720         #for task in range(len(self.runq_fnid)):
721         #    fn = self.taskData.fn_index[self.runq_fnid[task]]
722         #    taskname = self.runq_task[task]
723         #    print "%s %s.%s" % (task, taskname, fn)
724
725         #print "Unchecked: %s" % unchecked
726         #print "Current: %s" % current
727         #print "Not current: %s" % notcurrent
728
729         if len(unchecked) > 0:
730             bb.fatal("check_stamps fatal internal error")
731         return current
732
733     def check_stamp(self, task):
734
735         if self.stamppolicy == "perfile":
736             fulldeptree = False
737         else:
738             fulldeptree = True
739
740         fn = self.taskData.fn_index[self.runq_fnid[task]]
741         taskname = self.runq_task[task]
742         stampfile = "%s.%s" % (self.dataCache.stamp[fn], taskname)
743         # If the stamp is missing its not current
744         if not os.access(stampfile, os.F_OK):
745             return False
746         # If its a 'nostamp' task, it's not current
747         taskdep = self.dataCache.task_deps[fn]
748         if 'nostamp' in taskdep and task in taskdep['nostamp']:
749             return False
750
751         iscurrent = True
752         t1 =  os.stat(stampfile)[stat.ST_MTIME]
753         for dep in self.runq_depends[task]:
754             if iscurrent:
755                 fn2 = self.taskData.fn_index[self.runq_fnid[dep]]
756                 taskname2 = self.runq_task[dep]
757                 stampfile2 = "%s.%s" % (self.dataCache.stamp[fn2], taskname2)
758                 if fulldeptree or fn == fn2:
759                     try:
760                         t2 = os.stat(stampfile2)[stat.ST_MTIME]
761                         if t1 < t2:
762                             iscurrent = False
763                     except:
764                         iscurrent = False
765
766         return iscurrent
767
768     def execute_runqueue(self):
769         """
770         Run the tasks in a queue prepared by prepare_runqueue
771         Upon failure, optionally try to recover the build using any alternate providers
772         (if the abort on failure configuration option isn't set)
773         """
774
775         failures = 0
776         while 1:
777             failed_fnids = []
778             try:
779                 self.execute_runqueue_internal()
780             finally:
781                 if self.master_process:
782                     failed_fnids = self.finish_runqueue()
783             if len(failed_fnids) == 0:
784                 return failures
785             if self.taskData.abort:
786                 raise bb.runqueue.TaskFailure(failed_fnids)
787             for fnid in failed_fnids:
788                 #print "Failure: %s %s %s" % (fnid, self.taskData.fn_index[fnid],  self.runq_task[fnid])
789                 self.taskData.fail_fnid(fnid)
790                 failures = failures + 1
791             self.reset_runqueue()
792             self.prepare_runqueue()
793
794     def execute_runqueue_initVars(self):
795
796         self.stats = RunQueueStats()
797
798         self.active_builds = 0
799         self.runq_buildable = []
800         self.runq_running = []
801         self.runq_complete = []
802         self.build_pids = {}
803         self.failed_fnids = []
804         self.master_process = True
805
806         # Mark initial buildable tasks
807         for task in range(len(self.runq_fnid)):
808             self.runq_running.append(0)
809             self.runq_complete.append(0)
810             if len(self.runq_depends[task]) == 0:
811                 self.runq_buildable.append(1)
812             else:
813                 self.runq_buildable.append(0)
814
815     def task_complete(self, task):
816         """
817         Mark a task as completed
818         Look at the reverse dependencies and mark any task with 
819         completed dependencies as buildable
820         """
821         self.runq_complete[task] = 1
822         for revdep in self.runq_revdeps[task]:
823             if self.runq_running[revdep] == 1:
824                 continue
825             if self.runq_buildable[revdep] == 1:
826                 continue
827             alldeps = 1
828             for dep in self.runq_depends[revdep]:
829                 if self.runq_complete[dep] != 1:
830                     alldeps = 0
831             if alldeps == 1:
832                 self.runq_buildable[revdep] = 1
833                 fn = self.taskData.fn_index[self.runq_fnid[revdep]]
834                 taskname = self.runq_task[revdep]
835                 bb.msg.debug(1, bb.msg.domain.RunQueue, "Marking task %s (%s, %s) as buildable" % (revdep, fn, taskname))
836
837     def execute_runqueue_internal(self):
838         """
839         Run the tasks in a queue prepared by prepare_runqueue
840         """
841
842         bb.msg.note(1, bb.msg.domain.RunQueue, "Executing runqueue")
843
844         self.execute_runqueue_initVars()
845
846         if len(self.runq_fnid) == 0:
847             # nothing to do
848             return []
849
850         def sigint_handler(signum, frame):
851             raise KeyboardInterrupt
852
853         event.fire(bb.event.StampUpdate(self.target_pairs, self.dataCache.stamp, self.cfgdata))
854
855         while True:
856             task = self.sched.next()
857             if task is not None:
858                 fn = self.taskData.fn_index[self.runq_fnid[task]]
859
860                 taskname = self.runq_task[task]
861                 if self.check_stamp(task):
862                     bb.msg.debug(2, bb.msg.domain.RunQueue, "Stamp current task %s (%s)" % (task, self.get_user_idstring(task)))
863                     self.runq_running[task] = 1
864                     self.task_complete(task)
865                     self.stats.taskCompleted()
866                     self.stats.taskSkipped()
867                     continue
868
869                 bb.msg.note(1, bb.msg.domain.RunQueue, "Running task %d of %d (ID: %s, %s)" % (self.stats.completed + self.active_builds + 1, len(self.runq_fnid), task, self.get_user_idstring(task)))
870                 try: 
871                     pid = os.fork() 
872                 except OSError, e: 
873                     bb.msg.fatal(bb.msg.domain.RunQueue, "fork failed: %d (%s)" % (e.errno, e.strerror))
874                 if pid == 0:
875                     # Bypass master process' handling
876                     self.master_process = False
877                     # Stop Ctrl+C being sent to children
878                     # signal.signal(signal.SIGINT, signal.SIG_IGN)
879                     # Make the child the process group leader
880                     os.setpgid(0, 0)
881                     newsi = os.open('/dev/null', os.O_RDWR)
882                     os.dup2(newsi, sys.stdin.fileno())
883                     self.cooker.configuration.cmd = taskname[3:]
884                     try: 
885                         self.cooker.tryBuild(fn)
886                     except bb.build.EventException:
887                         bb.msg.error(bb.msg.domain.Build, "Build of " + fn + " " + taskname + " failed")
888                         sys.exit(1)
889                     except:
890                         bb.msg.error(bb.msg.domain.Build, "Build of " + fn + " " + taskname + " failed")
891                         raise
892                     sys.exit(0)
893                 self.build_pids[pid] = task
894                 self.runq_running[task] = 1
895                 self.active_builds = self.active_builds + 1
896                 if self.active_builds < self.number_tasks:
897                     continue
898             if self.active_builds > 0:
899                 result = os.waitpid(-1, 0)
900                 self.active_builds = self.active_builds - 1
901                 task = self.build_pids[result[0]]
902                 if result[1] != 0:
903                     del self.build_pids[result[0]]
904                     bb.msg.error(bb.msg.domain.RunQueue, "Task %s (%s) failed" % (task, self.get_user_idstring(task)))
905                     self.failed_fnids.append(self.runq_fnid[task])
906                     self.stats.taskFailed()
907                     break
908                 self.task_complete(task)
909                 self.stats.taskCompleted()
910                 del self.build_pids[result[0]]
911                 continue
912             return
913
914     def finish_runqueue(self):
915         try:
916             while self.active_builds > 0:
917                 bb.msg.note(1, bb.msg.domain.RunQueue, "Waiting for %s active tasks to finish" % self.active_builds)
918                 tasknum = 1
919                 for k, v in self.build_pids.iteritems():
920                      bb.msg.note(1, bb.msg.domain.RunQueue, "%s: %s (%s)" % (tasknum, self.get_user_idstring(v), k))
921                      tasknum = tasknum + 1
922                 result = os.waitpid(-1, 0)
923                 task = self.build_pids[result[0]]
924                 if result[1] != 0:
925                      bb.msg.error(bb.msg.domain.RunQueue, "Task %s (%s) failed" % (task, self.get_user_idstring(task)))
926                      self.failed_fnids.append(self.runq_fnid[task])
927                      self.stats.taskFailed()
928                 del self.build_pids[result[0]]
929                 self.active_builds = self.active_builds - 1
930             bb.msg.note(1, bb.msg.domain.RunQueue, "Tasks Summary: Attempted %d tasks of which %d didn't need to be rerun and %d failed." % (self.stats.completed, self.stats.skipped, self.stats.failed))
931             return self.failed_fnids
932         except KeyboardInterrupt:
933             bb.msg.note(1, bb.msg.domain.RunQueue, "Sending SIGINT to remaining %s tasks" % self.active_builds)
934             for k, v in self.build_pids.iteritems():
935                  try:
936                      os.kill(-k, signal.SIGINT)
937                  except:
938                      pass
939             raise
940
941         # Sanity Checks
942         for task in range(len(self.runq_fnid)):
943             if self.runq_buildable[task] == 0:
944                 bb.msg.error(bb.msg.domain.RunQueue, "Task %s never buildable!" % task)
945             if self.runq_running[task] == 0:
946                 bb.msg.error(bb.msg.domain.RunQueue, "Task %s never ran!" % task)
947             if self.runq_complete[task] == 0:
948                 bb.msg.error(bb.msg.domain.RunQueue, "Task %s never completed!" % task)
949
950         bb.msg.note(1, bb.msg.domain.RunQueue, "Tasks Summary: Attempted %d tasks of which %d didn't need to be rerun and %d failed." % (self.stats.completed, self.stats.skipped, self.stats.failed))
951
952         return self.failed_fnids
953
954     def dump_data(self, taskQueue):
955         """
956         Dump some debug information on the internal data structures
957         """
958         bb.msg.debug(3, bb.msg.domain.RunQueue, "run_tasks:")
959         for task in range(len(self.runq_fnid)):
960                 bb.msg.debug(3, bb.msg.domain.RunQueue, " (%s)%s - %s: %s   Deps %s RevDeps %s" % (task, 
961                         taskQueue.fn_index[self.runq_fnid[task]], 
962                         self.runq_task[task], 
963                         self.runq_weight[task], 
964                         self.runq_depends[task], 
965                         self.runq_revdeps[task]))
966
967         bb.msg.debug(3, bb.msg.domain.RunQueue, "sorted_tasks:")
968         for task1 in range(len(self.runq_fnid)):
969             if task1 in self.prio_map:
970                 task = self.prio_map[task1]
971                 bb.msg.debug(3, bb.msg.domain.RunQueue, " (%s)%s - %s: %s   Deps %s RevDeps %s" % (task, 
972                         taskQueue.fn_index[self.runq_fnid[task]], 
973                         self.runq_task[task], 
974                         self.runq_weight[task], 
975                         self.runq_depends[task], 
976                         self.runq_revdeps[task]))