Branch data Line data Source code
1 : : /*-
2 : : * Copyright (c) 2024 The FreeBSD Foundation
3 : : *
4 : : * This software was developed by Isaac Freund <ifreund@freebsdfoundation.org>
5 : : * under sponsorship from the FreeBSD Foundation.
6 : : *
7 : : * Redistribution and use in source and binary forms, with or without
8 : : * modification, are permitted provided that the following conditions
9 : : * are met:
10 : : * 1. Redistributions of source code must retain the above copyright
11 : : * notice, this list of conditions and the following disclaimer
12 : : * in this position and unchanged.
13 : : * 2. Redistributions in binary form must reproduce the above copyright
14 : : * notice, this list of conditions and the following disclaimer in the
15 : : * documentation and/or other materials provided with the distribution.
16 : : *
17 : : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
18 : : * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 : : * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 : : * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
21 : : * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 : : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 : : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 : : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 : : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 : : * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 : : */
28 : : #include <assert.h>
29 : : #include <tllist.h>
30 : :
31 : : #include "pkg.h"
32 : : #include "private/event.h"
33 : : #include "private/pkg.h"
34 : : #include "private/pkg_jobs.h"
35 : :
36 : : #define dbg(x, ...) pkg_dbg(PKG_DBG_SCHEDULER, x, __VA_ARGS__)
37 : :
38 : : extern struct pkg_ctx ctx;
39 : :
40 : : static const char *
41 : 0 : pkg_jobs_schedule_job_type_string(struct pkg_solved *job)
42 : : {
43 [ # # # # : 0 : switch (job->type) {
# # ]
44 : : case PKG_SOLVED_INSTALL:
45 : 0 : return "install";
46 : : case PKG_SOLVED_DELETE:
47 : 0 : return "delete";
48 : : case PKG_SOLVED_UPGRADE:
49 : 0 : return "upgrade";
50 : : case PKG_SOLVED_UPGRADE_INSTALL:
51 : 0 : return "split upgrade install";
52 : : case PKG_SOLVED_UPGRADE_REMOVE:
53 : 0 : return "split upgrade delete";
54 : : default:
55 : 0 : assert(false);
56 : : }
57 : 0 : }
58 : :
59 : : /*
60 : : * Returns true if pkg a directly depends on pkg b.
61 : : *
62 : : * Checking only direct dependencies is sufficient to define the edges in a
63 : : * graph that models indirect dependencies as well as long as all of the
64 : : * intermediate dependencies are also nodes in the graph.
65 : : */
66 : 483 : static bool pkg_jobs_schedule_direct_depends(struct pkg *a, struct pkg *b)
67 : : {
68 : 483 : struct pkg_dep *dep = NULL;
69 [ + + ]: 640 : while (pkg_deps(a, &dep) == EPKG_OK) {
70 [ + + ]: 311 : if (STREQ(b->uid, dep->uid)) {
71 : 154 : return (true);
72 : : }
73 : : }
74 : 329 : return (false);
75 : 483 : }
76 : :
77 : : /* Enable debug logging in pkg_jobs_schedule_graph_edge() */
78 : : static bool debug_edges = false;
79 : :
80 : : /*
81 : : * Jobs are nodes in a directed graph. Edges represent job scheduling order
82 : : * requirements. The existence of an edge from node A to node B indicates
83 : : * that job A must be executed before job B.
84 : : *
85 : : * There is a directed edge from node A to node B if and only if
86 : : * one of the following conditions holds:
87 : : *
88 : : * 1. B's new package depends on A's new package
89 : : * 2. A's old package depends on B's old package
90 : : * 3. A's old package conflicts with B's new package
91 : : * 4. A and B are the two halves of a split upgrade job
92 : : * and A is the delete half.
93 : : */
94 : : static bool
95 : 1130 : pkg_jobs_schedule_graph_edge(struct pkg_solved *a, struct pkg_solved *b)
96 : : {
97 [ + + ]: 1130 : if (a == b) {
98 : 469 : return (false);
99 : : }
100 : :
101 [ + + - + ]: 661 : if (a->xlink == b || b->xlink == a) {
102 [ + - ]: 36 : assert(a->xlink == b && b->xlink == a);
103 [ + + + - ]: 36 : assert(a->type == PKG_SOLVED_UPGRADE_INSTALL ||
104 : : a->type == PKG_SOLVED_UPGRADE_REMOVE);
105 [ + + + - ]: 36 : assert(b->type == PKG_SOLVED_UPGRADE_INSTALL ||
106 : : b->type == PKG_SOLVED_UPGRADE_REMOVE);
107 [ + - ]: 36 : assert(a->type != b->type);
108 : :
109 : 36 : bool edge = a->type == PKG_SOLVED_UPGRADE_REMOVE;
110 [ + + + - ]: 36 : if (edge && debug_edges) {
111 : 0 : dbg(4, " edge to %s %s, split upgrade",
112 : : pkg_jobs_schedule_job_type_string(b),
113 : : b->items[0]->pkg->uid);
114 : 0 : }
115 : 36 : return (edge);
116 : : }
117 : :
118 : : /* TODO: These switches would be unnecessary if delete jobs used
119 : : * items[1] rather than items[0]. I suspect other cleanups could
120 : : * be made as well. */
121 : 625 : struct pkg *a_new = NULL;
122 : 625 : struct pkg *a_old = NULL;
123 [ - + + + : 625 : switch (a->type) {
+ + ]
124 : : case PKG_SOLVED_INSTALL:
125 : : case PKG_SOLVED_UPGRADE_INSTALL:
126 : 374 : a_new = a->items[0]->pkg;
127 : 569 : break;
128 : : case PKG_SOLVED_DELETE:
129 : : case PKG_SOLVED_UPGRADE_REMOVE:
130 : 195 : a_old = a->items[0]->pkg;
131 : 195 : break;
132 : : case PKG_SOLVED_UPGRADE:
133 : 56 : a_new = a->items[0]->pkg;
134 : 56 : a_old = a->items[1]->pkg;
135 : 56 : break;
136 : : default:
137 : 0 : assert(false);
138 : : }
139 : :
140 : 625 : struct pkg *b_new = NULL;
141 : 625 : struct pkg *b_old = NULL;
142 [ - + + + : 625 : switch (b->type) {
+ + ]
143 : : case PKG_SOLVED_INSTALL:
144 : : case PKG_SOLVED_UPGRADE_INSTALL:
145 : 369 : b_new = b->items[0]->pkg;
146 : 569 : break;
147 : : case PKG_SOLVED_DELETE:
148 : : case PKG_SOLVED_UPGRADE_REMOVE:
149 : 200 : b_old = b->items[0]->pkg;
150 : 200 : break;
151 : : case PKG_SOLVED_UPGRADE:
152 : 56 : b_new = b->items[0]->pkg;
153 : 56 : b_old = b->items[1]->pkg;
154 : 56 : break;
155 : : default:
156 : 0 : assert(false);
157 : : }
158 : :
159 [ + + + + : 625 : if (a_new != NULL && b_new != NULL &&
+ + ]
160 : 330 : pkg_jobs_schedule_direct_depends(b_new, a_new)) {
161 [ + - ]: 117 : if (debug_edges) {
162 : 0 : dbg(4, " edge to %s %s, new depends on new",
163 : : pkg_jobs_schedule_job_type_string(b),
164 : : b->items[0]->pkg->uid);
165 : 0 : }
166 : 117 : return (true);
167 [ + + + + : 508 : } else if (a_old != NULL && b_old != NULL &&
+ + ]
168 : 153 : pkg_jobs_schedule_direct_depends(a_old, b_old)) {
169 [ + - ]: 37 : if (debug_edges) {
170 : 0 : dbg(4, " edge to %s %s, old depends on old",
171 : : pkg_jobs_schedule_job_type_string(b),
172 : : b->items[0]->pkg->uid);
173 : 0 : }
174 : 37 : return (true);
175 [ + + + + ]: 471 : } else if (a_old != NULL && b_new != NULL) {
176 : 123 : struct pkg_conflict *conflict = NULL;
177 [ + + ]: 151 : while (pkg_conflicts(a_old, &conflict) == EPKG_OK) {
178 [ + + ]: 85 : if (STREQ(b_new->uid, conflict->uid)) {
179 [ + - ]: 57 : if (debug_edges) {
180 : 0 : dbg(4, " edge to %s %s, old conflicts with new",
181 : : pkg_jobs_schedule_job_type_string(b),
182 : : b->items[0]->pkg->uid);
183 : 0 : }
184 : 57 : return (true);
185 : : }
186 : : }
187 : 66 : }
188 : :
189 : 414 : return (false);
190 : 1130 : }
191 : :
192 : : static void
193 : 236 : pkg_jobs_schedule_dbg_job(pkg_solved_list *jobs, struct pkg_solved *job)
194 : : {
195 [ + - ]: 236 : if (ctx.debug_level < 4) {
196 : 236 : return;
197 : : }
198 : :
199 : 0 : dbg(4, "job: %s %s", pkg_jobs_schedule_job_type_string(job),
200 : : job->items[0]->pkg->uid);
201 : :
202 : 0 : debug_edges = true;
203 [ # # # # : 0 : tll_foreach(*jobs, it) {
# # ]
204 : 0 : pkg_jobs_schedule_graph_edge(job, it->item);
205 : 0 : }
206 : 0 : debug_edges = false;
207 : 236 : }
208 : :
209 : : static bool
210 : 486 : pkg_jobs_schedule_has_incoming_edge(pkg_solved_list *nodes,
211 : : struct pkg_solved *node)
212 : : {
213 [ + + + + : 942 : tll_foreach(*nodes, it) {
+ + ]
214 [ + + ]: 524 : if (pkg_jobs_schedule_graph_edge(it->item, node)) {
215 : 68 : return (true);
216 : : }
217 : 456 : }
218 : 418 : return (false);
219 : 486 : }
220 : :
221 : : /*
222 : : * Prioritizing the install jobs and deprioritizing the delete jobs of split
223 : : * upgrades reduces the distance between the two halves of the split job in the
224 : : * final execution order.
225 : : */
226 : : static int
227 : 42 : pkg_jobs_schedule_priority(struct pkg_solved *node)
228 : : {
229 [ + + + ]: 42 : switch (node->type) {
230 : : case PKG_SOLVED_UPGRADE_INSTALL:
231 : 1 : return 1;
232 : : case PKG_SOLVED_UPGRADE_REMOVE:
233 : 7 : return -1;
234 : : default:
235 : 34 : return 0;
236 : : }
237 : 42 : }
238 : :
239 : : /* This comparison function is used as a tiebreaker in the topological sort. */
240 : : static int
241 : 21 : pkg_jobs_schedule_cmp_available(struct pkg_solved *a, struct pkg_solved *b)
242 : : {
243 : 21 : int ret = pkg_jobs_schedule_priority(b) - pkg_jobs_schedule_priority(a);
244 [ + + ]: 21 : if (ret == 0) {
245 : : /* Falling back to lexicographical ordering ensures that job execution
246 : : * order is always consistent and makes testing easier. */
247 : 15 : return strcmp(a->items[0]->pkg->uid, b->items[0]->pkg->uid);
248 : : } else {
249 : 6 : return ret;
250 : : }
251 : 21 : }
252 : :
253 : : /* Topological sort based on Kahn's algorithm with a tiebreaker */
254 : : static void
255 : 143 : pkg_jobs_schedule_topological_sort(pkg_solved_list *jobs)
256 : : {
257 : 143 : pkg_solved_list sorted = tll_init();
258 : 143 : pkg_solved_list available = tll_init();
259 : :
260 : : /* Place all job nodes with no incoming edges in available */
261 [ + - + + : 346 : tll_foreach(*jobs, it) {
+ + ]
262 [ + + + + ]: 203 : if (!pkg_jobs_schedule_has_incoming_edge(jobs, it->item) &&
263 : 159 : !pkg_jobs_schedule_has_incoming_edge(&available, it->item)) {
264 [ + + + + : 154 : tll_push_front(available, it->item);
+ - - + +
+ ]
265 [ - + + + : 154 : tll_remove(*jobs, it);
+ + ]
266 : 154 : }
267 : 203 : }
268 : :
269 [ + + ]: 346 : while (tll_length(available) > 0) {
270 : : /* Add the highest priority job from the set of available jobs
271 : : * to the sorted list */
272 [ + - + + : 661 : tll_sort(available, pkg_jobs_schedule_cmp_available);
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
273 [ + - - + : 203 : struct pkg_solved *node = tll_pop_front(available);
+ + ]
274 [ + + + + : 203 : tll_push_back(sorted, node);
+ - - + +
+ ]
275 : :
276 : : /* Again, place all job nodes with no incoming edges in the set
277 : : * of available jobs, ignoring any incoming edges from job nodes
278 : : * already added to the sorted list */
279 [ + + + + : 305 : tll_foreach(*jobs, it) {
+ + ]
280 [ + + ]: 102 : if (pkg_jobs_schedule_graph_edge(node, it->item)) {
281 [ + + + + ]: 68 : if (!pkg_jobs_schedule_has_incoming_edge(jobs, it->item) &&
282 : 56 : !pkg_jobs_schedule_has_incoming_edge(&available, it->item)) {
283 [ + + + + : 49 : tll_push_front(available, it->item);
+ - - + +
+ ]
284 [ - + + + : 49 : tll_remove(*jobs, it);
+ + ]
285 : 49 : }
286 : 68 : }
287 : 102 : }
288 : : }
289 : :
290 : : /* The jobs list will only be non-empty at this point if there is a
291 : : * cycle in the graph and all cycles must be eliminated by splitting
292 : : * upgrade jobs before calling this function. */
293 [ + - ]: 143 : assert(tll_length(*jobs) == 0);
294 : :
295 : 143 : *jobs = sorted;
296 : 143 : }
297 : :
298 : : /*
299 : : * This is a depth-first search that keeps track of the path taken to the
300 : : * current node in the graph. If a node on this path is encountered a
301 : : * second time a cycle has been found.
302 : : */
303 : : static struct pkg_solved *
304 : 228 : pkg_jobs_schedule_find_cycle(pkg_solved_list *jobs,
305 : : struct pkg_solved **path, struct pkg_solved *node)
306 : : {
307 : : /* Push node to path */
308 [ + - ]: 228 : assert(node->mark == PKG_SOLVED_CYCLE_MARK_NONE);
309 : 228 : node->mark = PKG_SOLVED_CYCLE_MARK_PATH;
310 [ + - ]: 228 : assert(node->path_next == NULL);
311 : 228 : node->path_next = *path;
312 : 228 : *path = node;
313 : :
314 [ - + + + : 708 : tll_foreach(*jobs, it) {
+ + ]
315 [ + + ]: 504 : if (pkg_jobs_schedule_graph_edge(node, it->item)) {
316 [ + + - + ]: 93 : switch (it->item->mark){
317 : : case PKG_SOLVED_CYCLE_MARK_NONE:;
318 : 37 : struct pkg_solved *cycle =
319 : 37 : pkg_jobs_schedule_find_cycle(jobs, path, it->item);
320 [ + + ]: 37 : if (cycle != NULL) {
321 : 15 : return (cycle);
322 : : }
323 : 22 : break;
324 : : case PKG_SOLVED_CYCLE_MARK_DONE:
325 : 47 : break;
326 : : case PKG_SOLVED_CYCLE_MARK_PATH:
327 : 9 : return (it->item); /* Found a cycle */
328 : : default:
329 : 0 : assert(false);
330 : : }
331 : 69 : }
332 : 480 : }
333 : :
334 : : /* Pop node from path */
335 [ + - ]: 204 : assert(node->mark == PKG_SOLVED_CYCLE_MARK_PATH);
336 : 204 : node->mark = PKG_SOLVED_CYCLE_MARK_DONE;
337 : 204 : *path = node->path_next;
338 : 204 : node->path_next = NULL;
339 : :
340 : 204 : return (NULL);
341 : 228 : }
342 : :
343 : 143 : int pkg_jobs_schedule(struct pkg_jobs *j)
344 : : {
345 : 152 : while (true) {
346 : 152 : dbg(3, "checking job scheduling graph for cycles...");
347 : :
348 [ + - + + : 388 : tll_foreach(j->jobs, it) {
+ + ]
349 : 236 : it->item->mark = PKG_SOLVED_CYCLE_MARK_NONE;
350 : 236 : it->item->path_next = NULL;
351 : :
352 : 236 : pkg_jobs_schedule_dbg_job(&j->jobs, it->item);
353 : 236 : }
354 : :
355 : : /* The graph may not be connected, in which case it is necessary to
356 : : * run multiple searches for cycles from different start nodes. */
357 : 152 : struct pkg_solved *path = NULL;
358 : 152 : struct pkg_solved *cycle = NULL;
359 [ + - + + : 356 : tll_foreach(j->jobs, it) {
+ + ]
360 [ + - - + ]: 213 : switch (it->item->mark) {
361 : : case PKG_SOLVED_CYCLE_MARK_NONE:
362 : 191 : cycle = pkg_jobs_schedule_find_cycle(&j->jobs, &path, it->item);
363 : 191 : break;
364 : : case PKG_SOLVED_CYCLE_MARK_DONE:
365 : 22 : break;
366 : 0 : case PKG_SOLVED_CYCLE_MARK_PATH:
367 : : default:
368 : 0 : assert(false);
369 : : }
370 [ + + ]: 213 : if (cycle != NULL) {
371 : 9 : break;
372 : : }
373 : 204 : }
374 : :
375 [ + + ]: 152 : if (cycle == NULL) {
376 : 143 : dbg(3, "no job scheduling graph cycles found");
377 [ + - ]: 143 : assert(path == NULL);
378 : 143 : break;
379 : : }
380 : :
381 : 9 : dbg(3, "job scheduling graph cycle found");
382 [ - + ]: 9 : assert(path != NULL);
383 [ - + ]: 9 : assert(path != cycle);
384 : :
385 : : /* Choose an arbitrary upgrade job in the cycle to split in order
386 : : * to break the cycle.
387 : : *
388 : : * TODO: Does it truly not matter which upgrade job in the cycle we
389 : : * choose to split? I'm relatively confident that splitting any upgrade job
390 : : * will break the given cycle but is it possible that one of the choices
391 : : * would break additional cycles as well?
392 : : */
393 [ + + ]: 16 : while (path->type != PKG_SOLVED_UPGRADE) {
394 [ - + ]: 7 : if (path == cycle) {
395 : 0 : pkg_emit_error("found job scheduling cycle without upgrade job");
396 : 0 : return (EPKG_FATAL);
397 : : }
398 : 7 : path = path->path_next;
399 [ + - ]: 7 : assert(path != NULL);
400 : : }
401 : :
402 : : /* path is now the upgrade job chosen to be split */
403 : 9 : dbg(2, "splitting upgrade %s job", path->items[0]->pkg->uid);
404 : :
405 : 9 : struct pkg_solved *new = xcalloc(1, sizeof(struct pkg_solved));
406 : 9 : new->type = PKG_SOLVED_UPGRADE_REMOVE;
407 : 9 : new->items[0] = path->items[1];
408 : 9 : new->xlink = path;
409 : 9 : path->type = PKG_SOLVED_UPGRADE_INSTALL;
410 : 9 : path->items[1] = NULL;
411 : 9 : path->xlink = new;
412 [ - + - + : 9 : tll_push_back(j->jobs, new);
- + + - -
+ ]
413 : : }
414 : :
415 : 143 : pkg_jobs_schedule_topological_sort(&j->jobs);
416 : :
417 : 143 : dbg(3, "finished job scheduling");
418 : :
419 : 143 : return (EPKG_OK);
420 : 143 : }
|
