1 /* Copyright (c) 2014, Vsevolod Stakhov
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above copyright
9 * notice, this list of conditions and the following disclaimer in the
10 * documentation and/or other materials provided with the distribution.
11 *
12 * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY
13 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
14 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
15 * DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY
16 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
17 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
18 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
19 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
20 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 */
23
24 #ifdef HAVE_CONFIG_H
25 #include "pkg_config.h"
26 #endif
27
28 #include <sys/param.h>
29 #include <sys/types.h>
30
31 #include <assert.h>
32 #include <errno.h>
33 #ifdef HAVE_LIBUTIL_H
34 #include <libutil.h>
35 #endif
36 #include <stdbool.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <ctype.h>
40
41 #include "pkg.h"
42 #include "private/event.h"
43 #include "private/pkg.h"
44 #include "private/pkgdb.h"
45 #include "private/pkg_jobs.h"
46 #include "kvec.h"
47
48 #define IS_DELETE(j) ((j)->type == PKG_JOBS_DEINSTALL || (j)->type == PKG_JOBS_AUTOREMOVE)
49
50 typedef kvec_t(struct pkg *) pkg_chain_t;
51
52 struct pkg *
pkg_jobs_universe_get_local(struct pkg_jobs_universe * universe,const char * uid,unsigned flag)53 pkg_jobs_universe_get_local(struct pkg_jobs_universe *universe,
54 const char *uid, unsigned flag)
55 {
56 struct pkg *pkg = NULL;
57 struct pkgdb_it *it;
58 struct pkg_job_universe_item *unit, *cur, *found;
59
60 if (flag == 0) {
61 if (!IS_DELETE(universe->j))
62 flag = PKG_LOAD_BASIC|PKG_LOAD_DEPS|PKG_LOAD_RDEPS|PKG_LOAD_OPTIONS|
63 PKG_LOAD_REQUIRES|PKG_LOAD_PROVIDES|
64 PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|PKG_LOAD_ANNOTATIONS|
65 PKG_LOAD_CONFLICTS;
66 else
67 flag = PKG_LOAD_BASIC|PKG_LOAD_RDEPS|PKG_LOAD_DEPS|PKG_LOAD_ANNOTATIONS;
68 }
69
70 HASH_FIND(hh, universe->items, uid, strlen(uid), unit);
71 if (unit != NULL) {
72 /* Search local in a universe chain */
73 cur = unit;
74 found = NULL;
75 do {
76 if (cur->pkg->type == PKG_INSTALLED) {
77 found = cur;
78 break;
79 }
80 cur = cur->prev;
81 } while (cur != unit);
82
83 if (found) {
84 pkgdb_ensure_loaded(universe->j->db, unit->pkg, flag);
85 return (unit->pkg);
86 }
87 }
88
89 if ((it = pkgdb_query(universe->j->db, uid, MATCH_EXACT)) == NULL)
90 return (NULL);
91
92 if (pkgdb_it_next(it, &pkg, flag) != EPKG_OK)
93 pkg = NULL;
94
95 pkgdb_it_free(it);
96
97 return (pkg);
98 }
99
100 static pkg_chain_t *
pkg_jobs_universe_get_remote(struct pkg_jobs_universe * universe,const char * uid,unsigned flag)101 pkg_jobs_universe_get_remote(struct pkg_jobs_universe *universe,
102 const char *uid, unsigned flag)
103 {
104 struct pkg *pkg = NULL;
105 pkg_chain_t *result = NULL;
106 struct pkgdb_it *it;
107 struct pkg_job_universe_item *unit, *cur, *found;
108
109 if (flag == 0) {
110 flag = PKG_LOAD_BASIC|PKG_LOAD_DEPS|PKG_LOAD_OPTIONS|
111 PKG_LOAD_PROVIDES|PKG_LOAD_REQUIRES|
112 PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
113 PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;
114 }
115
116 HASH_FIND(hh, universe->items, uid, strlen(uid), unit);
117 if (unit != NULL && unit->pkg->type != PKG_INSTALLED) {
118 /* Search local in a universe chain */
119 cur = unit;
120 found = NULL;
121 do {
122 if (cur->pkg->type != PKG_INSTALLED) {
123 found = cur;
124 break;
125 }
126 cur = cur->prev;
127 } while (cur != unit);
128
129 if (found) {
130 /* Assume processed */
131 return (NULL);
132 }
133 }
134
135 if ((it = pkgdb_repo_query(universe->j->db, uid, MATCH_EXACT,
136 universe->j->reponame)) == NULL)
137 return (NULL);
138
139 while (pkgdb_it_next(it, &pkg, flag) == EPKG_OK) {
140 if (result == NULL)
141 result = xcalloc(1, sizeof(pkg_chain_t));
142 kv_prepend(typeof(pkg), *result, pkg);
143 pkg = NULL;
144 }
145
146 pkgdb_it_free(it);
147
148 return (result);
149 }
150
151 /**
152 * Check whether a package is in the universe already or add it
153 * @return item or NULL
154 */
155 int
pkg_jobs_universe_add_pkg(struct pkg_jobs_universe * universe,struct pkg * pkg,bool force __unused,struct pkg_job_universe_item ** found)156 pkg_jobs_universe_add_pkg(struct pkg_jobs_universe *universe, struct pkg *pkg,
157 bool force __unused, struct pkg_job_universe_item **found)
158 {
159 struct pkg_job_universe_item *item, *seen, *tmp = NULL;
160
161 pkg_validate(pkg, universe->j->db);
162
163 if (pkg->digest == NULL) {
164 pkg_debug(3, "no digest found for package %s (%s-%s)",
165 pkg->uid, pkg->name, pkg->version);
166 if (pkg_checksum_calculate(pkg, universe->j->db, false, true, false) != EPKG_OK) {
167 *found = NULL;
168 return (EPKG_FATAL);
169 }
170 }
171
172 kh_find(pkg_jobs_seen, universe->seen, pkg->digest, seen);
173 if (seen) {
174 bool same_package = false;
175
176 DL_FOREACH(seen, tmp) {
177 if (tmp->pkg == pkg || (tmp->pkg->type == pkg->type &&
178 strcmp(tmp->pkg->digest, pkg->digest) == 0)) {
179 if (tmp->pkg->reponame != NULL) {
180 if (strcmp(tmp->pkg->reponame, pkg->reponame) == 0) {
181 same_package = true;
182 break;
183 }
184 } else {
185 same_package = true;
186 break;
187 }
188 }
189 }
190
191 if (same_package) {
192 if (found != NULL) {
193 *found = seen;
194 }
195
196 return (EPKG_END);
197 }
198 }
199
200 if (pkg_is_locked(pkg)) {
201 return (EPKG_LOCKED);
202 }
203
204 pkg_debug(2, "universe: add new %s pkg: %s, (%s-%s:%s)",
205 (pkg->type == PKG_INSTALLED ? "local" : "remote"), pkg->uid,
206 pkg->name, pkg->version, pkg->digest);
207
208 item = xcalloc(1, sizeof (struct pkg_job_universe_item));
209 item->pkg = pkg;
210
211
212 HASH_FIND_STR(universe->items, pkg->uid, tmp);
213 if (tmp == NULL)
214 HASH_ADD_KEYPTR(hh, universe->items, pkg->uid, strlen(pkg->uid), item);
215
216 DL_APPEND(tmp, item);
217
218 if (seen == NULL)
219 kh_safe_add(pkg_jobs_seen, universe->seen, item, item->pkg->digest);
220
221 universe->nitems++;
222
223 if (found != NULL)
224 *found = item;
225
226 return (EPKG_OK);
227 }
228
229 #define DEPS_FLAG_REVERSE 0x1 << 1
230 #define DEPS_FLAG_MIRROR 0x1 << 2
231 #define DEPS_FLAG_FORCE_LOCAL 0x1 << 3
232 #define DEPS_FLAG_FORCE_MISSING 0x1 << 4
233 #define DEPS_FLAG_FORCE_UPGRADE 0x1 << 5
234
235 static int
pkg_jobs_universe_process_deps(struct pkg_jobs_universe * universe,struct pkg * pkg,unsigned flags)236 pkg_jobs_universe_process_deps(struct pkg_jobs_universe *universe,
237 struct pkg *pkg, unsigned flags)
238 {
239 struct pkg_dep *d = NULL;
240 int (*deps_func)(const struct pkg *pkg, struct pkg_dep **d);
241 int rc;
242 struct pkg_job_universe_item *unit;
243 struct pkg *npkg, *rpkg, *lpkg;
244 pkg_chain_t *rpkgs = NULL;
245 bool found = false;
246
247 rpkg = NULL;
248
249 if (flags & DEPS_FLAG_REVERSE) {
250 pkg_debug(4, "Processing rdeps for %s (%s)", pkg->uid, pkg->type == PKG_INSTALLED ? "installed" : "remote");
251 if (pkg->type != PKG_INSTALLED) {
252 lpkg = pkg_jobs_universe_get_local(universe, pkg->uid, 0);
253 if (lpkg != NULL && lpkg != pkg)
254 return (pkg_jobs_universe_process_deps(universe, lpkg, flags));
255 }
256 deps_func = pkg_rdeps;
257 }
258 else {
259 pkg_debug(4, "Processing deps for %s", pkg->uid);
260 deps_func = pkg_deps;
261 }
262
263 while (deps_func(pkg, &d) == EPKG_OK) {
264 pkg_debug(4, "Processing *deps for %s: %s", pkg->uid, d->uid);
265 HASH_FIND_STR(universe->items, d->uid, unit);
266 if (unit != NULL) {
267 continue;
268 }
269
270 rpkgs = NULL;
271 npkg = NULL;
272 if (!(flags & DEPS_FLAG_MIRROR)) {
273 npkg = pkg_jobs_universe_get_local(universe, d->uid, 0);
274 }
275
276 if (!(flags & DEPS_FLAG_FORCE_LOCAL)) {
277
278 /* Check for remote dependencies */
279 rpkgs = pkg_jobs_universe_get_remote(universe, d->uid, 0);
280 }
281
282 if (npkg == NULL && rpkgs == NULL) {
283 pkg_emit_error("%s has a missing dependency: %s",
284 pkg->name, d->name);
285
286 if (flags & DEPS_FLAG_FORCE_MISSING) {
287 continue;
288 }
289
290 return (EPKG_FATAL);
291 }
292
293 if (npkg != NULL) {
294 if (pkg_jobs_universe_process_item(universe, npkg, &unit) != EPKG_OK) {
295 continue;
296 }
297 }
298
299 if (rpkgs == NULL)
300 continue;
301 /*
302 * When processing deps, we should first try to select a dependency
303 * from the same repo.
304 * Otherwise, we would have ping-pong of dependencies instead of
305 * the situation when this behaviour is handled by
306 * CONSERVATIVE_UPGRADES.
307 *
308 * Important notes here:
309 * 1. We are looking for packages that are dependencies of a package
310 * `pkg`
311 * 2. Now if `pkg` belongs to repo `r` and `rpkg` belongs to repo
312 * `r` then we just select it.
313 * 3. If `rpkg` is not found in `r` we just scan all packages
314 */
315
316 /*
317 * XXX: this is the proper place to expand flexible dependencies
318 */
319
320 found = false;
321 /* Iteration one */
322 for (int i = 0; i < kv_size(*rpkgs); i++) {
323 rpkg = kv_A(*rpkgs, i);
324
325 if (pkg->reponame && rpkg->reponame &&
326 strcmp (pkg->reponame, rpkg->reponame) == 0) {
327 found = true;
328 break;
329 }
330 }
331
332 /* Fallback if a dependency is not found in the same repo */
333 if (!found) {
334 for (int i = 0; i < kv_size(*rpkgs); i++) {
335 rpkg = kv_A(*rpkgs, i);
336
337 if (npkg != NULL) {
338 /* Set reason for upgrades */
339 if (!pkg_jobs_need_upgrade(rpkg, npkg))
340 continue;
341 /* Save automatic flag */
342 rpkg->automatic = npkg->automatic;
343 }
344
345 rc = pkg_jobs_universe_process_item(universe, rpkg, NULL);
346
347 /* Special case if we cannot find any package */
348 if (npkg == NULL && rc != EPKG_OK) {
349 kv_destroy(*rpkgs);
350 free(rpkgs);
351 return (rc);
352 }
353 }
354 }
355 else {
356 assert (rpkg != NULL);
357
358 if (npkg != NULL) {
359 /* Set reason for upgrades */
360 if (!pkg_jobs_need_upgrade(rpkg, npkg))
361 continue;
362 /* Save automatic flag */
363 rpkg->automatic = npkg->automatic;
364 }
365
366 rc = pkg_jobs_universe_process_item(universe, rpkg, NULL);
367 if (npkg == NULL && rc != EPKG_OK) {
368 kv_destroy(*rpkgs);
369 free(rpkgs);
370 return (rc);
371 }
372 }
373
374 kv_destroy(*rpkgs);
375 free(rpkgs);
376 }
377
378 return (EPKG_OK);
379 }
380
381 static int
pkg_jobs_universe_handle_provide(struct pkg_jobs_universe * universe,struct pkgdb_it * it,const char * name,bool is_shlib,struct pkg * parent __unused)382 pkg_jobs_universe_handle_provide(struct pkg_jobs_universe *universe,
383 struct pkgdb_it *it, const char *name, bool is_shlib, struct pkg *parent __unused)
384 {
385 struct pkg_job_universe_item *unit;
386 struct pkg_job_provide *pr, *prhead;
387 struct pkg *npkg, *rpkg;
388 int rc;
389 unsigned flags = PKG_LOAD_BASIC|PKG_LOAD_OPTIONS|PKG_LOAD_DEPS|
390 PKG_LOAD_REQUIRES|PKG_LOAD_PROVIDES|
391 PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
392 PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;
393
394 rpkg = NULL;
395
396 HASH_FIND_STR(universe->provides, name, prhead);
397
398 while (pkgdb_it_next(it, &rpkg, flags) == EPKG_OK) {
399 /* Check for local packages */
400 HASH_FIND_STR(universe->items, rpkg->uid, unit);
401 if (unit != NULL) {
402 /* Remote provide is newer, so we can add it */
403 if (pkg_jobs_universe_process_item(universe, rpkg,
404 &unit) != EPKG_OK) {
405 continue;
406 }
407
408 rpkg = NULL;
409 }
410 else {
411 /* Maybe local package has just been not added */
412 npkg = pkg_jobs_universe_get_local(universe, rpkg->uid, 0);
413 if (npkg != NULL) {
414 if (pkg_jobs_universe_process_item(universe, npkg,
415 &unit) != EPKG_OK) {
416 return (EPKG_FATAL);
417 }
418 if (pkg_jobs_universe_process_item(universe, rpkg,
419 &unit) != EPKG_OK) {
420 continue;
421 }
422 if (unit != NULL)
423 rpkg = NULL;
424 }
425 }
426
427 /* Skip seen packages */
428 if (unit == NULL) {
429 if (rpkg->digest == NULL) {
430 pkg_debug(3, "no digest found for package %s", rpkg->uid);
431 if (pkg_checksum_calculate(rpkg,
432 universe->j->db, false, true, false) != EPKG_OK) {
433 return (EPKG_FATAL);
434 }
435 }
436 rc = pkg_jobs_universe_process_item(universe, rpkg,
437 &unit);
438
439 if (rc != EPKG_OK) {
440 return (rc);
441 }
442
443 /* Reset package to avoid freeing */
444 rpkg = NULL;
445 }
446
447 pr = xcalloc (1, sizeof (*pr));
448 pr->un = unit;
449 pr->provide = name;
450 pr->is_shlib = is_shlib;
451
452 if (prhead == NULL) {
453 DL_APPEND(prhead, pr);
454 HASH_ADD_KEYPTR(hh, universe->provides, pr->provide,
455 strlen(pr->provide), prhead);
456 pkg_debug (4, "universe: add new provide %s-%s(%s) for require %s",
457 pr->un->pkg->name, pr->un->pkg->version,
458 pr->un->pkg->type == PKG_INSTALLED ? "l" : "r",
459 pr->provide);
460 }
461 else {
462 DL_APPEND(prhead, pr);
463 pkg_debug (4, "universe: append provide %s-%s(%s) for require %s",
464 pr->un->pkg->name, pr->un->pkg->version,
465 pr->un->pkg->type == PKG_INSTALLED ? "l" : "r",
466 pr->provide);
467 }
468 }
469
470 return (EPKG_OK);
471 }
472
473 static int
pkg_jobs_universe_process_shlibs(struct pkg_jobs_universe * universe,struct pkg * pkg)474 pkg_jobs_universe_process_shlibs(struct pkg_jobs_universe *universe,
475 struct pkg *pkg)
476 {
477 struct pkg_job_provide *pr;
478 struct pkgdb_it *it;
479 char *buf = NULL;
480 int rc;
481
482 while (pkg_shlibs_required(pkg, &buf) == EPKG_OK) {
483 HASH_FIND_STR(universe->provides, buf, pr);
484 if (pr != NULL)
485 continue;
486
487 /* Check for local provides */
488 it = pkgdb_query_shlib_provide(universe->j->db, buf);
489 if (it != NULL) {
490 rc = pkg_jobs_universe_handle_provide(universe, it,
491 buf, true, pkg);
492 pkgdb_it_free(it);
493
494 if (rc != EPKG_OK) {
495 pkg_debug(1, "cannot find local packages that provide library %s "
496 "required for %s",
497 buf, pkg->name);
498 }
499 }
500 /* Not found, search in the repos */
501 it = pkgdb_repo_shlib_provide(universe->j->db,
502 buf, universe->j->reponame);
503
504 if (it != NULL) {
505 rc = pkg_jobs_universe_handle_provide(universe, it, buf, true, pkg);
506 pkgdb_it_free(it);
507
508 if (rc != EPKG_OK) {
509 pkg_debug(1, "cannot find remote packages that provide library %s "
510 "required for %s",
511 buf, pkg->name);
512 }
513 }
514 }
515
516 return (EPKG_OK);
517 }
518
519 static int
pkg_jobs_universe_process_provides_requires(struct pkg_jobs_universe * universe,struct pkg * pkg)520 pkg_jobs_universe_process_provides_requires(struct pkg_jobs_universe *universe,
521 struct pkg *pkg)
522 {
523 struct pkg_job_provide *pr;
524 struct pkgdb_it *it;
525 char *buf = NULL;
526 int rc;
527
528 while (pkg_requires(pkg, &buf) == EPKG_OK) {
529 HASH_FIND_STR(universe->provides, buf, pr);
530 if (pr != NULL)
531 continue;
532
533 /* Check for local provides */
534 it = pkgdb_query_provide(universe->j->db, buf);
535 if (it != NULL) {
536 rc = pkg_jobs_universe_handle_provide(universe, it, buf, false, pkg);
537 pkgdb_it_free(it);
538
539 if (rc != EPKG_OK) {
540 pkg_debug(1, "cannot find local packages that provide %s "
541 "required for %s",
542 buf, pkg->name);
543 }
544 }
545
546 /* Not found, search in the repos */
547 it = pkgdb_repo_provide(universe->j->db,
548 buf, universe->j->reponame);
549
550 if (it != NULL) {
551 rc = pkg_jobs_universe_handle_provide(universe, it, buf, false, pkg);
552 pkgdb_it_free(it);
553
554 if (rc != EPKG_OK) {
555 pkg_debug(1, "cannot find remote packages that provide %s "
556 "required for %s",
557 buf, pkg->name);
558 return (rc);
559 }
560 }
561 }
562
563 return (EPKG_OK);
564 }
565
566 int
pkg_jobs_universe_process_item(struct pkg_jobs_universe * universe,struct pkg * pkg,struct pkg_job_universe_item ** result)567 pkg_jobs_universe_process_item(struct pkg_jobs_universe *universe, struct pkg *pkg,
568 struct pkg_job_universe_item **result)
569 {
570 unsigned flags = 0, job_flags;
571 int rc = EPKG_OK;
572 pkg_jobs_t type = universe->j->type;
573 struct pkg_job_universe_item *found;
574
575 pkg_debug(4, "Processing item %s\n", pkg->uid);
576
577 job_flags = universe->j->flags;
578
579 /*
580 * Add pkg itself. If package is already seen then we check the `processed`
581 * flag that means that we have already tried to check our universe
582 */
583 rc = pkg_jobs_universe_add_pkg(universe, pkg, false, &found);
584 if (rc == EPKG_CONFLICT)
585 return (rc);
586
587 if (result)
588 *result = found;
589
590 if (rc == EPKG_END) {
591 if (found->processed)
592 return (EPKG_OK);
593 }
594 else if (rc != EPKG_OK) {
595 return (rc);
596 }
597
598 found->processed = true;
599
600 /* Convert jobs flags to dependency logical flags */
601 if (job_flags & PKG_FLAG_FORCE_MISSING)
602 flags |= DEPS_FLAG_FORCE_MISSING;
603
604 switch(type) {
605 case PKG_JOBS_FETCH:
606 if (job_flags & PKG_FLAG_RECURSIVE) {
607 flags |= DEPS_FLAG_MIRROR;
608 /* For fetch jobs we worry about depends only */
609 rc = pkg_jobs_universe_process_deps(universe, pkg, flags);
610 }
611 break;
612 case PKG_JOBS_INSTALL:
613 case PKG_JOBS_UPGRADE:
614 /* Handle depends */
615 rc = pkg_jobs_universe_process_deps(universe, pkg, flags);
616 if (rc != EPKG_OK)
617 return (rc);
618 /* Handle reverse depends */
619 rc = pkg_jobs_universe_process_deps(universe, pkg,
620 flags|DEPS_FLAG_REVERSE);
621 if (rc != EPKG_OK)
622 return (rc);
623 /* Provides/requires */
624 rc = pkg_jobs_universe_process_shlibs(universe, pkg);
625 if (rc != EPKG_OK)
626 return (rc);
627 rc = pkg_jobs_universe_process_provides_requires(universe, pkg);
628 if (rc != EPKG_OK)
629 return (rc);
630 break;
631 case PKG_JOBS_AUTOREMOVE:
632 /* XXX */
633 break;
634 case PKG_JOBS_DEINSTALL:
635 /* For delete jobs we worry only about local reverse deps */
636 flags |= DEPS_FLAG_REVERSE|DEPS_FLAG_FORCE_LOCAL;
637 if (job_flags & PKG_FLAG_RECURSIVE)
638 rc = pkg_jobs_universe_process_deps(universe, pkg, flags);
639 break;
640 }
641
642 return (rc);
643 }
644
645 int
pkg_jobs_universe_process(struct pkg_jobs_universe * universe,struct pkg * pkg)646 pkg_jobs_universe_process(struct pkg_jobs_universe *universe,
647 struct pkg *pkg)
648 {
649 return (pkg_jobs_universe_process_item(universe, pkg, NULL));
650 }
651
652 #define RECURSION_LIMIT 1024
653
654 static void
pkg_jobs_update_universe_item_priority(struct pkg_jobs_universe * universe,struct pkg_job_universe_item * item,int priority,enum pkg_priority_update_type type)655 pkg_jobs_update_universe_item_priority(struct pkg_jobs_universe *universe,
656 struct pkg_job_universe_item *item, int priority,
657 enum pkg_priority_update_type type)
658 {
659 struct pkg_dep *d = NULL;
660 struct pkg_conflict *c = NULL;
661 struct pkg_job_universe_item *found, *cur, *it;
662 const char *is_local;
663 int maxpri;
664
665 int (*deps_func)(const struct pkg *pkg, struct pkg_dep **d);
666 int (*rdeps_func)(const struct pkg *pkg, struct pkg_dep **d);
667
668 if (priority > RECURSION_LIMIT) {
669 pkg_debug(1, "recursion limit has been reached, something is bad"
670 " with dependencies/conflicts graph");
671 return;
672 }
673 else if (priority + 10 > RECURSION_LIMIT) {
674 pkg_debug(2, "approaching recursion limit at %d, while processing of"
675 " package %s", priority, item->pkg->uid);
676 }
677
678 LL_FOREACH(item, it) {
679 if ((item->next != NULL || item->prev != NULL) &&
680 it->pkg->type != PKG_INSTALLED &&
681 (type == PKG_PRIORITY_UPDATE_CONFLICT ||
682 type == PKG_PRIORITY_UPDATE_DELETE)) {
683 /*
684 * We do not update priority of a remote part of conflict, as we know
685 * that remote packages should not contain conflicts (they should be
686 * resolved in request prior to calling of this function)
687 */
688 pkg_debug(4, "skip update priority for %s-%s",
689 it->pkg->uid, it->pkg->digest);
690 continue;
691 }
692 if (it->priority > priority)
693 continue;
694
695 is_local = it->pkg->type == PKG_INSTALLED ? "local" : "remote";
696 pkg_debug(2, "universe: update %s priority of %s(%s): %d -> %d, reason: %d",
697 is_local, it->pkg->uid, it->pkg->digest, it->priority, priority, type);
698 it->priority = priority;
699
700 if (type == PKG_PRIORITY_UPDATE_DELETE) {
701 /*
702 * For delete requests we inverse deps and rdeps logic
703 */
704 deps_func = pkg_rdeps;
705 rdeps_func = pkg_deps;
706 }
707 else {
708 deps_func = pkg_deps;
709 rdeps_func = pkg_rdeps;
710 }
711
712 while (deps_func(it->pkg, &d) == EPKG_OK) {
713 HASH_FIND_STR(universe->items, d->uid, found);
714 if (found == NULL)
715 continue;
716 LL_FOREACH(found, cur) {
717 if (cur->priority < priority + 1)
718 pkg_jobs_update_universe_item_priority(universe, cur,
719 priority + 1, type);
720 }
721 }
722
723 d = NULL;
724 maxpri = priority;
725 while (rdeps_func(it->pkg, &d) == EPKG_OK) {
726 HASH_FIND_STR(universe->items, d->uid, found);
727 if (found == NULL)
728 continue;
729 LL_FOREACH(found, cur) {
730 if (cur->priority >= maxpri) {
731 maxpri = cur->priority + 1;
732 }
733 }
734 }
735 if (maxpri != priority) {
736 pkg_jobs_update_universe_item_priority(universe, it,
737 maxpri, type);
738 return;
739 }
740 if (it->pkg->type == PKG_INSTALLED)
741 continue;
742
743 while (pkg_conflicts(it->pkg, &c) == EPKG_OK) {
744 HASH_FIND_STR(universe->items, c->uid, found);
745 if (found == NULL)
746 continue;
747 LL_FOREACH(found, cur) {
748 if (cur->pkg->type != PKG_INSTALLED)
749 continue;
750 /*
751 * Move delete requests to be done before installing
752 */
753 if (cur->priority <= it->priority)
754 pkg_jobs_update_universe_item_priority(universe, cur,
755 it->priority + 1, PKG_PRIORITY_UPDATE_CONFLICT);
756 }
757 }
758 }
759 }
760
761 void
pkg_jobs_update_conflict_priority(struct pkg_jobs_universe * universe,struct pkg_solved * req)762 pkg_jobs_update_conflict_priority(struct pkg_jobs_universe *universe,
763 struct pkg_solved *req)
764 {
765 struct pkg_conflict *c = NULL;
766 struct pkg *lp = req->items[1]->pkg;
767 struct pkg_job_universe_item *found, *cur, *rit = NULL;
768
769 while (pkg_conflicts(lp, &c) == EPKG_OK) {
770 rit = NULL;
771 HASH_FIND_STR(universe->items, c->uid, found);
772 assert(found != NULL);
773
774 LL_FOREACH(found, cur) {
775 if (cur->pkg->type != PKG_INSTALLED) {
776 rit = cur;
777 break;
778 }
779 }
780
781 assert(rit != NULL);
782 if (rit->priority >= req->items[1]->priority) {
783 pkg_jobs_update_universe_item_priority(universe, req->items[1],
784 rit->priority + 1, PKG_PRIORITY_UPDATE_CONFLICT);
785 /*
786 * Update priorities for a remote part as well
787 */
788 pkg_jobs_update_universe_item_priority(universe, req->items[0],
789 req->items[0]->priority, PKG_PRIORITY_UPDATE_REQUEST);
790 }
791 }
792 }
793
794
795 void
pkg_jobs_update_universe_priority(struct pkg_jobs_universe * universe,struct pkg_job_universe_item * it,enum pkg_priority_update_type type)796 pkg_jobs_update_universe_priority(struct pkg_jobs_universe *universe,
797 struct pkg_job_universe_item *it, enum pkg_priority_update_type type)
798 {
799 pkg_jobs_update_universe_item_priority(universe, it, 0, type);
800 }
801
802 static void
pkg_jobs_universe_provide_free(struct pkg_job_provide * pr)803 pkg_jobs_universe_provide_free(struct pkg_job_provide *pr)
804 {
805 struct pkg_job_provide *cur, *tmp;
806
807 DL_FOREACH_SAFE(pr, cur, tmp) {
808 free (cur);
809 }
810 }
811
812 static void
pkg_jobs_universe_replacement_free(struct pkg_job_replace * r)813 pkg_jobs_universe_replacement_free(struct pkg_job_replace *r)
814 {
815 free(r->new_uid);
816 free(r->old_uid);
817 free(r);
818 }
819
820 void
pkg_jobs_universe_free(struct pkg_jobs_universe * universe)821 pkg_jobs_universe_free(struct pkg_jobs_universe *universe)
822 {
823 struct pkg_job_universe_item *un, *untmp, *cur, *curtmp;
824
825 HASH_ITER(hh, universe->items, un, untmp) {
826 HASH_DEL(universe->items, un);
827
828 LL_FOREACH_SAFE(un, cur, curtmp) {
829 pkg_free(cur->pkg);
830 free(cur);
831 }
832 }
833 kh_destroy_pkg_jobs_seen(universe->seen);
834 HASH_FREE(universe->provides, pkg_jobs_universe_provide_free);
835 LL_FREE(universe->uid_replaces, pkg_jobs_universe_replacement_free);
836 }
837
838 struct pkg_jobs_universe *
pkg_jobs_universe_new(struct pkg_jobs * j)839 pkg_jobs_universe_new(struct pkg_jobs *j)
840 {
841 struct pkg_jobs_universe *universe;
842
843 universe = xcalloc(1, sizeof(struct pkg_jobs_universe));
844 universe->j = j;
845
846 return (universe);
847 }
848
849 struct pkg_job_universe_item *
pkg_jobs_universe_find(struct pkg_jobs_universe * universe,const char * uid)850 pkg_jobs_universe_find(struct pkg_jobs_universe *universe, const char *uid)
851 {
852 struct pkg_job_universe_item *unit;
853
854 HASH_FIND_STR(universe->items, uid, unit);
855
856 return (unit);
857 }
858
859 void
pkg_jobs_universe_change_uid(struct pkg_jobs_universe * universe,struct pkg_job_universe_item * unit,const char * new_uid,size_t uidlen,bool update_rdeps)860 pkg_jobs_universe_change_uid(struct pkg_jobs_universe *universe,
861 struct pkg_job_universe_item *unit,
862 const char *new_uid, size_t uidlen, bool update_rdeps)
863 {
864 struct pkg_dep *rd = NULL, *d = NULL;
865 struct pkg_job_universe_item *found;
866
867 struct pkg *lp;
868 struct pkg_job_replace *replacement;
869
870 if (update_rdeps) {
871 /* For all rdeps update deps accordingly */
872 while (pkg_rdeps(unit->pkg, &rd) == EPKG_OK) {
873 found = pkg_jobs_universe_find(universe, rd->uid);
874 if (found == NULL) {
875 lp = pkg_jobs_universe_get_local(universe, rd->uid, 0);
876 /* XXX */
877 assert(lp != NULL);
878 pkg_jobs_universe_process_item(universe, lp, &found);
879 }
880
881 if (found != NULL) {
882 while (pkg_deps(found->pkg, &d) == EPKG_OK) {
883 if (strcmp(d->uid, unit->pkg->uid) == 0) {
884 free(d->uid);
885 d->uid = xstrdup(new_uid);
886 }
887 }
888 }
889 }
890 }
891
892 replacement = xcalloc(1, sizeof(*replacement));
893 replacement->old_uid = xstrdup(unit->pkg->uid);
894 replacement->new_uid = xstrdup(new_uid);
895 LL_PREPEND(universe->uid_replaces, replacement);
896
897 HASH_DELETE(hh, universe->items, unit);
898 free(unit->pkg->uid);
899 unit->pkg->uid = xstrdup(new_uid);
900
901 HASH_FIND(hh, universe->items, new_uid, uidlen, found);
902 if (found != NULL)
903 DL_APPEND(found, unit);
904 else
905 HASH_ADD_KEYPTR(hh, universe->items, new_uid, uidlen, unit);
906
907 }
908
909 static struct pkg_job_universe_item *
pkg_jobs_universe_select_max_ver(struct pkg_job_universe_item * chain)910 pkg_jobs_universe_select_max_ver(struct pkg_job_universe_item *chain)
911 {
912 struct pkg_job_universe_item *cur, *res = NULL;
913 bool found = false;
914 int r;
915
916 LL_FOREACH(chain, cur) {
917 if (cur->pkg->type == PKG_INSTALLED)
918 continue;
919
920 if (res != NULL) {
921 r = pkg_version_change_between(cur->pkg, res->pkg);
922 if (r == PKG_UPGRADE) {
923 res = cur;
924 found = true;
925 }
926 else if (r != PKG_REINSTALL) {
927 /*
928 * Actually the selected package is newer than some other
929 * packages in the chain
930 */
931 found = true;
932 }
933 }
934 else {
935 res = cur;
936 }
937 }
938
939 return (found ? res : NULL);
940 }
941
942 static struct pkg_job_universe_item *
pkg_jobs_universe_select_max_prio(struct pkg_job_universe_item * chain)943 pkg_jobs_universe_select_max_prio(struct pkg_job_universe_item *chain)
944 {
945 struct pkg_repo *repo;
946 unsigned int max_pri = 0;
947 struct pkg_job_universe_item *cur, *res = NULL;
948
949 LL_FOREACH(chain, cur) {
950 if (cur->pkg->type == PKG_INSTALLED)
951 continue;
952
953 if (cur->pkg->reponame) {
954 repo = pkg_repo_find(cur->pkg->reponame);
955 if (repo && repo->priority > max_pri) {
956 res = cur;
957 max_pri = repo->priority;
958 }
959 }
960 }
961
962 return (res);
963 }
964
965 static struct pkg_job_universe_item *
pkg_jobs_universe_select_same_repo(struct pkg_job_universe_item * chain,struct pkg_job_universe_item * local,const char * assumed_reponame)966 pkg_jobs_universe_select_same_repo(struct pkg_job_universe_item *chain,
967 struct pkg_job_universe_item *local, const char *assumed_reponame)
968 {
969 struct pkg_repo *local_repo = NULL, *repo;
970 struct pkg_job_universe_item *cur, *res = NULL;
971
972 if (!local) {
973
974 if (assumed_reponame) {
975 local_repo = pkg_repo_find(assumed_reponame);
976 }
977 }
978 else {
979 if (local->pkg->reponame) {
980 local_repo = pkg_repo_find(local->pkg->reponame);
981 }
982 else {
983 const char *lrepo = pkg_kv_get(&local->pkg->annotations, "repository");
984 if (lrepo) {
985 local_repo = pkg_repo_find(lrepo);
986 }
987 }
988 }
989
990 if (local_repo == NULL) {
991 return (NULL);
992 }
993 else {
994 LL_FOREACH(chain, cur) {
995 if (cur->pkg->type == PKG_INSTALLED)
996 continue;
997
998 if (cur->pkg->reponame) {
999 repo = pkg_repo_find(cur->pkg->reponame);
1000 if (repo == local_repo) {
1001 res = cur;
1002 break;
1003 }
1004 }
1005 }
1006 }
1007
1008 return (res);
1009 }
1010
1011 struct pkg_job_universe_item *
pkg_jobs_universe_select_candidate(struct pkg_job_universe_item * chain,struct pkg_job_universe_item * local,bool conservative,const char * reponame,bool pinning)1012 pkg_jobs_universe_select_candidate(struct pkg_job_universe_item *chain,
1013 struct pkg_job_universe_item *local, bool conservative,
1014 const char *reponame, bool pinning)
1015 {
1016 struct pkg_job_universe_item *res = NULL;
1017
1018 if (local == NULL) {
1019 /* New package selection */
1020 if (conservative) {
1021 /* Check same repo */
1022 if (reponame && pinning) {
1023 res = pkg_jobs_universe_select_same_repo(chain, NULL, reponame);
1024 }
1025
1026 if (res == NULL) {
1027 /* Priority -> version */
1028 res = pkg_jobs_universe_select_max_prio(chain);
1029 if (res == NULL) {
1030 res = pkg_jobs_universe_select_max_ver(chain);
1031 }
1032 }
1033 }
1034 else {
1035 if (reponame && pinning) {
1036 res = pkg_jobs_universe_select_same_repo(chain, NULL, reponame);
1037 }
1038
1039 if (res == NULL) {
1040 /* Version -> priority */
1041 res = pkg_jobs_universe_select_max_ver(chain);
1042 if (res == NULL) {
1043 res = pkg_jobs_universe_select_max_prio(chain);
1044 }
1045 }
1046 }
1047 }
1048 else {
1049 if (conservative) {
1050 /* same -> prio -> version */
1051 if (pinning)
1052 res = pkg_jobs_universe_select_same_repo(chain, local, reponame);
1053 if (res == NULL) {
1054 res = pkg_jobs_universe_select_max_prio(chain);
1055 }
1056 if (res == NULL) {
1057 res = pkg_jobs_universe_select_max_ver(chain);
1058 }
1059 }
1060 else {
1061 /* same -> version -> prio */
1062 if (pinning)
1063 res = pkg_jobs_universe_select_same_repo(chain, local, reponame);
1064 if (res == NULL) {
1065 res = pkg_jobs_universe_select_max_ver(chain);
1066 }
1067 if (res == NULL) {
1068 res = pkg_jobs_universe_select_max_prio(chain);
1069 }
1070 }
1071 }
1072
1073 /* Fallback to any */
1074 return (res != NULL ? res : chain);
1075 }
1076
1077 void
pkg_jobs_universe_process_upgrade_chains(struct pkg_jobs * j)1078 pkg_jobs_universe_process_upgrade_chains(struct pkg_jobs *j)
1079 {
1080 struct pkg_job_universe_item *unit, *tmp, *cur, *local;
1081 struct pkg_job_request *req;
1082 struct pkg_job_request_item *rit, *rtmp;
1083
1084 HASH_ITER(hh, j->universe->items, unit, tmp) {
1085 unsigned vercnt = 0;
1086
1087 HASH_FIND_STR(j->request_add, unit->pkg->uid, req);
1088 if (req == NULL) {
1089 /* Not obviously requested */
1090 continue;
1091 }
1092
1093 local = NULL;
1094 LL_FOREACH(unit, cur) {
1095 if (cur->pkg->type == PKG_INSTALLED)
1096 local = cur;
1097 vercnt ++;
1098 }
1099
1100 if (local != NULL && local->pkg->locked) {
1101 pkg_debug(1, "removing %s from the request as it is locked",
1102 cur->pkg->uid);
1103 HASH_DEL(j->request_add, req);
1104 pkg_jobs_request_free(req);
1105 continue;
1106 }
1107
1108 if (vercnt <= 1)
1109 continue;
1110
1111 /*
1112 * Here we have more than one upgrade candidate,
1113 * if local == NULL, then we have two remote repos,
1114 * if local != NULL, then we have unspecified upgrade path
1115 */
1116
1117 if ((local == NULL && vercnt > 1) || (vercnt > 2)) {
1118 /* Select the most recent or one of packages */
1119 struct pkg_job_universe_item *selected;
1120
1121 selected = pkg_jobs_universe_select_candidate(unit, local,
1122 j->conservative, NULL, j->pinning);
1123 /*
1124 * Now remove all requests but selected from the requested
1125 * candidates
1126 */
1127 assert(selected != NULL);
1128 HASH_DEL(j->request_add, req);
1129
1130 /*
1131 * We also check if the selected package has different digest,
1132 * and if it has the same digest we proceed only if we have a
1133 * forced job
1134 */
1135 if (local != NULL && strcmp(local->pkg->digest,
1136 selected->pkg->digest) == 0 &&
1137 (j->flags & PKG_FLAG_FORCE) == 0) {
1138 pkg_debug (1, "removing %s from the request as it is the "
1139 "same as local", selected->pkg->uid);
1140 continue;
1141 }
1142
1143 LL_FOREACH(unit, cur) {
1144 if (cur == selected)
1145 continue;
1146
1147 DL_FOREACH_SAFE(req->item, rit, rtmp) {
1148 if (rit->unit == cur) {
1149 DL_DELETE(req->item, rit);
1150 free(rit);
1151 }
1152 }
1153 }
1154 if (req->item == NULL) {
1155 rit = xcalloc(1, sizeof(*rit));
1156 rit->pkg = selected->pkg;
1157 rit->unit = selected;
1158 DL_APPEND(req->item, rit);
1159 }
1160 HASH_ADD_KEYPTR(hh, j->request_add, selected->pkg->uid,
1161 strlen (selected->pkg->uid), req);
1162 }
1163 }
1164 }
1165
1166 struct pkg_job_universe_item*
pkg_jobs_universe_get_upgrade_candidates(struct pkg_jobs_universe * universe,const char * uid,struct pkg * lp,bool force,const char * version)1167 pkg_jobs_universe_get_upgrade_candidates(struct pkg_jobs_universe *universe,
1168 const char *uid, struct pkg *lp, bool force, const char *version)
1169 {
1170 struct pkg *pkg = NULL, *selected = lp;
1171 struct pkgdb_it *it;
1172 struct pkg_job_universe_item *unit, *ucur;
1173 int flag = PKG_LOAD_BASIC|PKG_LOAD_DEPS|PKG_LOAD_OPTIONS|
1174 PKG_LOAD_REQUIRES|PKG_LOAD_PROVIDES|
1175 PKG_LOAD_SHLIBS_REQUIRED|PKG_LOAD_SHLIBS_PROVIDED|
1176 PKG_LOAD_ANNOTATIONS|PKG_LOAD_CONFLICTS;
1177 kvec_t(struct pkg *) candidates;
1178
1179 HASH_FIND(hh, universe->items, uid, strlen(uid), unit);
1180 if (unit != NULL) {
1181 /*
1182 * If a unit has been found, we have already found the potential
1183 * upgrade chain for it
1184 */
1185 if (force) {
1186 /*
1187 * We also need to ensure that a chain contains remote packages
1188 * in case of forced upgrade
1189 */
1190 DL_FOREACH(unit, ucur) {
1191 if (ucur->pkg->type != PKG_INSTALLED) {
1192 return (unit);
1193 }
1194 }
1195 }
1196 else {
1197 return (unit);
1198 }
1199 }
1200
1201 if ((it = pkgdb_repo_query(universe->j->db, uid, MATCH_EXACT,
1202 universe->j->reponame)) == NULL)
1203 return (NULL);
1204
1205 kv_init(candidates);
1206 while (pkgdb_it_next(it, &pkg, flag) == EPKG_OK) {
1207
1208 if (version != NULL && strcmp(pkg->version, version) != 0)
1209 continue;
1210
1211 if (force) {
1212 /* Just add everything */
1213 selected = pkg;
1214 }
1215 else {
1216 if (selected == lp &&
1217 (lp == NULL || pkg_jobs_need_upgrade(pkg, lp)))
1218 selected = pkg;
1219 else if (pkg_version_change_between(pkg, selected) == PKG_UPGRADE)
1220 selected = pkg;
1221 }
1222 kv_prepend(typeof(pkg), candidates, pkg);
1223 pkg = NULL;
1224 }
1225
1226 pkgdb_it_free(it);
1227
1228 if (lp != NULL) {
1229 /* Add local package to the universe as well */
1230 pkg_jobs_universe_add_pkg(universe, lp, false, NULL);
1231 }
1232 if (selected != lp) {
1233 /* We need to add the whole chain of upgrade candidates */
1234 for (int i = 0; i < kv_size(candidates); i++) {
1235 pkg_jobs_universe_add_pkg(universe, kv_A(candidates, i), force, NULL);
1236 }
1237 }
1238 else {
1239 while (kv_size(candidates) > 0)
1240 pkg_free(kv_pop(candidates));
1241 kv_destroy(candidates);
1242
1243 return (NULL);
1244 }
1245
1246 HASH_FIND(hh, universe->items, uid, strlen(uid), unit);
1247 kv_destroy(candidates);
1248
1249 return (unit);
1250 }
1251