Please note:The SCons wiki is in read-only mode due to ongoing spam/DoS issues. Also, new account creation is currently disabled. We are looking into alternative wiki hosts.

The current Taskmaster algorithm

This page is very preliminary.

The idea is that there are four operation that occur to a node when a DAG is being run. The operations are Setup(), Visit(), Build(), and Scan(). The first three happen exactly once; the last one occurs once for each distinct scan context applied to the node.

Unlike the typical DAG bush, this tree grows downward, so the children must be evaluated before the parents.

Data Values

For the purposes of this discussion, these are the contents of the node; items marked with a "*" are not manipulated (but are used) by this algorithm: (TODO: correct the names to the ones actually used)

Algorithm

There are four stages in a node's evaluation (along with the essential steps in each stage):

  1. Initialize(). The node is initialized for use by the DAG runner. This is done when the node is instantiated.
    1. status = 'unvisited'
    2. pending is set to empty list
    3. implicits set to empty list
    4. implicit_sources is set to empty list
    5. implicit_targets is set to empty list
  2. Visit(). The first time a node is visited, it performs a series of actions. This includes attaching parent dependencies (which visits the parent nodes). Note that a hook in this stage is effectively done when going "up" the DAG, the reverse direction of the usual dependency direction. If we have no parents (or if all parents are already resolved), this node is placed on the work queue.
    1. if status != 'unvisited': return
    2. set ref count to one
    3. run any pre-visit hooks
    4. for parent in parents: self.Pending(parent)
    5. run any post-visit hooks
    6. set status to 'visited'
    7. try to add ourself to the work queue
  3. Build(). All ancestors have been evaluated; evaluate this node, running the action if there is one and running the scanner if there is one. This includes attaching implicit dependencies on children.
    1. if node is up-to-date: return
    2. run any pre-action hooks
    3. execute action, if any
    4. run any post-action hooks
    5. calculate signature
    6. set status to 'built'
    7. for child in targets+implicit_targets: child.Implicit(self)
    8. for child in pending: try to add child to the work queue
  4. Scan(context). The node has been built; run a scanner (which is part of the context) to get any implicit dependencies.
    1. if there is a scan result for this context, return it
    2. run any pre-scanner hooks
    3. run scanner, producing a scan result
    4. run any post-scanner hooks
    5. return the new scan result

There are two functions that provide glue so that nodes are evaluated correctly.

The DAG runner needs these functions to run the DAG:

Then a (single-threaded) implementation of the DAG runner has these steps:

  1. for node in targets: node.Visit()
  2. while work_queue: remove first node in work_queue; node.Work()

(The multi-threaded implementation is more complex, but every time a node is added to the work queue or when a worker thread reports back the results of an action, an attempt is made to run the head of the queue.)

Each node executes the Visit() logic exactly once, is moved into the work queue exactly once, and executes the Work() logic exactly once. (Well, modulo loops in the DAG, in which case the nodes never get into the work queue.)

GregNoel/RunDAG1 (last edited 2008-03-12 02:47:12 by localhost)