Date: Tue, 29 Oct 2024 14:00:14 +0000 From: bugzilla-noreply@freebsd.org To: pkgbase@FreeBSD.org Subject: [Bug 259785] pkgbase installation order is underspecified Message-ID: <bug-259785-36141-9Q91QrwiiZ@https.bugs.freebsd.org/bugzilla/> In-Reply-To: <bug-259785-36141@https.bugs.freebsd.org/bugzilla/> References: <bug-259785-36141@https.bugs.freebsd.org/bugzilla/>
next in thread | previous in thread | raw e-mail | index | archive | help
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D259785 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 replacem= ent. 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 followi= ng 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 pack= age 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 wi= th 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 fi= nal 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 dele= tion half of a split upgrade negative priority, the install half of a split upgr= ade positive priority, and everything else 0 priority. Any thoughts? I'd be happy to work on an implementation of this if the appr= oach seems reasonable. --=20 You are receiving this mail because: You are on the CC list for the bug.=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?bug-259785-36141-9Q91QrwiiZ>