[Bug 259785] pkgbase installation order is underspecified

https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=259785

Isaac Freund <ifreund@freebsdfoundation.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ifreund@freebsdfoundation.o
                   |                            |rg

--- Comment #7 from Isaac Freund <ifreund@freebsdfoundation.org> ---
I've been looking into this problem and am of the opinion that the approach
currently used by pkg to order jobs should be considered for total replacement.
I find it exceptionally hard to reason about and highly suspect that it has
bugs in edge cases. Extending it to improve the handling of split upgrades does
not seem feasible to me.

I'd like to propose the following model for jobs and how to order them:

Jobs are nodes in a directed graph. Edges represent job execution ordering
requirements.

There is a directed edge from node A to B if and only if one of the following
conditions holds:

1. A and B are install jobs and B depends on A
2. A and B are deletion jobs and A depends on B
3. A and B are upgrade jobs and B depends on A
4. A and B are upgrade jobs and A's old package conflicts with B's new package
5. A is an upgrade job and B is an install job and A's old package conflicts
with B's package
6. A is a deletion job and B is an upgrade job and A's package conflicts with
B's new package

Given this graph, an upgrade job needs to be split exactly when there is a
cycle in the graph.

Job ordering is obtained by a topological sort on the graph, which can only
succeed if there are no cycles in the graph.

To minimize the distance between the parts of a split upgrade job in the final
scheduling order, we can add a priority value to the nodes in the graph and use
this to influence the topological sort order in the absence of hard
dependencies between nodes. I think it would be sufficient to give the deletion
half of a split upgrade negative priority, the install half of a split upgrade
positive priority, and everything else 0 priority.

Any thoughts? I'd be happy to work on an implementation of this if the approach
seems reasonable.

-- 
You are receiving this mail because:
You are on the CC list for the bug.