Griffon26's Blog

Since last time I posted, the libgda-3 work has been finished and checked in. The final patch turned out to be 81K in size. =)

For this post I will describe what I’ve been doing to fix bug #382548. This bug allows you to create dependency loops in tasks.

The simplest type of loop that can be created is this one:

You could create this by first setting task2 as a predecessor of task1 and then indenting task2 to become a child of task1. Planner does not allow you to do it the other way around, first indenting task2 and then adding it as a predecessor of task1.

To see how Planner tries to detect these loops, we’ll have to take a look at libplanner/mrp-task-manager.c.

There are basically two operations you can perform on a task: moving and setting predecessors. All other actions are mapped to these two. Indenting a task for instance is implemented as moving it under a new parent. To check if these operations can be performed without creating loops, two functions named mrp_task_manager_check_move() and mrp_task_manager_check_predecessor() are used. Both of these functions have the following structure:

1. perform the operation in the dependency graph
2. traverse the graph to detect loops
3. undo the operation in the dependency graph
4. return a boolean indicating whether or not the operation can be done without creating loops

The dependency graph that these functions refer to is a directed acyclic (or at least it should be ) graph. The tasks will be nodes in this graph and the edges are either predecessor relationships or child-to-parent relationships. Think of this graph as showing the order in which tasks can be scheduled; a predecessor must be scheduled before its successor and children should be scheduled before you are able to tell the duration of the parent. Note that adding a predecessor to a parent task has to result in adding this predecessor to (certain) children of the task as well, otherwise it would not be clear from the graph that none of the children can be scheduled before the predecessor has been scheduled.

The above is implemented as follows for adding a predecessor. mrp_task_manager_check_predecessor() calls add_predecessor_to_dependency_graph(), which connects the predecessor node with the parent node and then calls add_predecessor_to_dependency_graph_recursive() that loops over all children, connects the predecessor node to them and calls itself for the children’s children. If the predecessor link in the above image had been created when task2 was already a child of task1, then this recursive adding of predecessors would have connected task2 to task2, thereby creating a loop.

When a task that is already a predecessor of another is indented, the process is a bit different. mrp_task_manager_check_move() calls remove_task_from_dependency_graph() to remove the task node from its current position in the graph followed by add_task_to_dependency_graph() to add it at the new position. add_task_to_dependency_graph() reconnects the task to all of its predecessors and finally connects it to its new parent. Keen readers may have noticed that planner has not done anything yet about the predecessor relationships of the new parent. If the task that is being indented is a predecessor of its new parent, Planner would happily indent and create the situation seen in the image above.

What should be done when a task is moved under a new parent is to add all predecessors from the parent as predecessors to the task and all of its children. This is part 1 of the fix for #382548.

Unfortunately even with this fix, the following is still possible.

The reason for this is that loop detection is only started at the task that is indented (task2 in this case). Take a look at the “before” and “after” pictures of the dependency graph for indenting task 2. The dotted lines indicate predecessor relations and the normal lines child-to-parent relations. As you can see starting traversal at task2 will not go through the loop that was created.

Ok, so how about starting loop detection at the indented task and each of its children individually?

Let’s take a look at the loop detection function check_predecessor_traverse():

static gboolean
check_predecessor_traverse (MrpTaskManager *manager,
                            MrpTask        *task,
                            MrpTask        *end,
                            gint            length)
{
        MrpTaskGraphNode *node;
        GList            *l;

        if (length > 1 && task == end) {
                return FALSE;
        }

        /* Avoid endless loop. */
        if (imrp_task_get_visited (task)) {
                return TRUE;
        }

        imrp_task_set_visited (task, TRUE);

        node = imrp_task_get_graph_node (task);
        for (l = node->next; l; l = l->next) {
                if (!check_predecessor_traverse (manager, l->data, end, length + 1)) {
                        return FALSE;
                }
        }

        return TRUE;
}

This is first called as check_predecessor_traverse (manager, predecessor, predecessor, 1);.
First it returns FALSE (i.e. reports a loop) if the current task is the same as the one passed in ‘end’ and this is not the first call. Then it aborts searching down a path if it has been there before. Next it marks the current task as visited so it will not continue searching when it comes here the next time through another path. And finally it will go on to all tasks that follow the current one in the graph.

What I wanted to know before implementing the proposed solution of starting loop detection at the indented task and each of its children is if I could get away with calling check_predecessor_traverse() multiple times without marking all nodes ‘unvisited’ in between. As you can see the function only detects loops that include the task that it starts at and only if none of the nodes in the loop have been visited before.

I think the answer is no and here’s why:

1. assume we start with a graph without cycles
2. now if adding a predecessor to a child results in a loop, this means there is a forward path from the child to the predecessor
3. this forward path either goes through visited nodes or it doesn’t
4. if it doesn’t, the check_predecessor_traverse() function will detect a loop when it is called on this child
5. if it does go through visited nodes, then there was already a forward path from the visited node to the predecessor
6. because the visited node has been visited before, there must already be a forward path from a node that the traverse function started at to the visited node
7. because we only call the traverse function on nodes that the predecessor is added to (the indented task and all its children), there must also be a forward path from predecessor to the node the traverse started at
8. this means that there is a loop that would have been detected in the earlier check_predecessor_traverse() call

This is part 2 of the fix. I just committed these fixes in libplanner/mrp-task-manager.c (revision 894).

It would have been fun to use a model checker to formally verify the last part, but in the end looking for one took too much time. If anyone has a suggestion, please let me know.

Posted by Griffon26 on Saturday, March 15th, 2008 at 14:26.