1 /*-
2 * Copyright (c) 2014 Vsevolod Stakhov <vsevolod@FreeBSD.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer
10 * in this position and unchanged.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #include <sys/param.h>
28 #include <sys/types.h>
29 #include <stdbool.h>
30 #include <stdlib.h>
31 #include <string.h>
32
33 #include "pkg.h"
34 #include "private/event.h"
35 #include "private/pkg.h"
36 #include "private/pkgdb.h"
37 #include "private/pkg_jobs.h"
38 #include "siphash.h"
39
40 struct pkg_conflict_chain {
41 struct pkg_job_request *req;
42 struct pkg_conflict_chain *next;
43 };
44
45
46 TREE_DEFINE(pkg_jobs_conflict_item, entry);
47
48 static struct sipkey *
pkg_conflicts_sipkey_init(void)49 pkg_conflicts_sipkey_init(void)
50 {
51 static struct sipkey *kinit;
52
53 if (kinit == NULL) {
54 kinit = xmalloc(sizeof(*kinit));
55 arc4random_buf((unsigned char*)kinit, sizeof(*kinit));
56 }
57
58 return (kinit);
59 }
60
61 static int
pkg_conflicts_chain_cmp_cb(struct pkg_conflict_chain * a,struct pkg_conflict_chain * b)62 pkg_conflicts_chain_cmp_cb(struct pkg_conflict_chain *a, struct pkg_conflict_chain *b)
63 {
64 const char *vera, *verb;
65
66 if (a->req->skip || b->req->skip) {
67 return (a->req->skip - b->req->skip);
68 }
69
70 vera = a->req->item->pkg->version;
71 verb = b->req->item->pkg->version;
72
73 /* Inverse sort to get the maximum version as the first element */
74 return (pkg_version_cmp(vera, verb));
75 }
76
77 static int
pkg_conflicts_request_resolve_chain(struct pkg * req,struct pkg_conflict_chain * chain)78 pkg_conflicts_request_resolve_chain(struct pkg *req, struct pkg_conflict_chain *chain)
79 {
80 struct pkg_conflict_chain *elt, *selected = NULL;
81 const char *slash_pos;
82
83 /*
84 * First of all prefer pure origins, where the last element of
85 * an origin is pkg name
86 */
87 LL_FOREACH(chain, elt) {
88 slash_pos = strrchr(elt->req->item->pkg->origin, '/');
89 if (slash_pos != NULL) {
90 if (strcmp(slash_pos + 1, req->name) == 0) {
91 selected = elt;
92 break;
93 }
94 }
95 }
96
97 if (selected == NULL) {
98 /* XXX: add manual selection here */
99 /* Sort list by version of package */
100 LL_SORT(chain, pkg_conflicts_chain_cmp_cb);
101 selected = chain;
102 }
103
104 pkg_debug(2, "select %s in the chain of conflicts for %s",
105 selected->req->item->pkg->name, req->name);
106 /* Disable conflicts from a request */
107 LL_FOREACH(chain, elt) {
108 if (elt != selected)
109 elt->req->skip = true;
110 }
111
112 return (EPKG_OK);
113 }
114
115 static void
pkg_conflicts_request_add_chain(struct pkg_conflict_chain ** chain,struct pkg_job_request * req)116 pkg_conflicts_request_add_chain(struct pkg_conflict_chain **chain, struct pkg_job_request *req)
117 {
118 struct pkg_conflict_chain *elt;
119
120 elt = xcalloc(1, sizeof(struct pkg_conflict_chain));
121 elt->req = req;
122 LL_PREPEND(*chain, elt);
123 }
124
125 int
pkg_conflicts_request_resolve(struct pkg_jobs * j)126 pkg_conflicts_request_resolve(struct pkg_jobs *j)
127 {
128 struct pkg_job_request *req, *rtmp, *found;
129 struct pkg_conflict *c;
130 struct pkg_conflict_chain *chain;
131 struct pkg_job_universe_item *unit;
132
133 HASH_ITER(hh, j->request_add, req, rtmp) {
134 chain = NULL;
135 if (req->skip)
136 continue;
137
138 LL_FOREACH(req->item->pkg->conflicts, c) {
139 unit = pkg_jobs_universe_find(j->universe, c->uid);
140 if (unit != NULL) {
141 HASH_FIND_STR(j->request_add, unit->pkg->uid, found);
142 if (found && !found->skip) {
143 pkg_conflicts_request_add_chain(&chain, found);
144 }
145 }
146 }
147 if (chain != NULL) {
148 /* Add package itself */
149 pkg_conflicts_request_add_chain(&chain, req);
150
151 if (pkg_conflicts_request_resolve_chain(req->item->pkg, chain) != EPKG_OK) {
152 LL_FREE(chain, free);
153 return (EPKG_FATAL);
154 }
155 LL_FREE(chain, free);
156 }
157 }
158
159 return (EPKG_OK);
160 }
161
162 void
pkg_conflicts_register(struct pkg * p1,struct pkg * p2,enum pkg_conflict_type type)163 pkg_conflicts_register(struct pkg *p1, struct pkg *p2, enum pkg_conflict_type type)
164 {
165 struct pkg_conflict *c1, *c2;
166
167 c1 = xcalloc(1, sizeof(*c1));
168 c2 = xcalloc(1, sizeof(*c2));
169
170 c1->type = c2->type = type;
171 if (!kh_contains(pkg_conflicts, p1->conflictshash, p2->uid)) {
172 c1->uid = xstrdup(p2->uid);
173 kh_safe_add(pkg_conflicts, p1->conflictshash, c1, c1->uid);
174 DL_APPEND(p1->conflicts, c1);
175 pkg_debug(2, "registering conflict between %s(%s) and %s(%s)",
176 p1->uid, p1->type == PKG_INSTALLED ? "l" : "r",
177 p2->uid, p2->type == PKG_INSTALLED ? "l" : "r");
178 } else {
179 pkg_conflict_free(c1);
180 }
181
182 if (!kh_contains(pkg_conflicts, p2->conflictshash, p1->uid)) {
183 c2->uid = xstrdup(p1->uid);
184 kh_safe_add(pkg_conflicts, p2->conflictshash, c2, c2->uid);
185 DL_APPEND(p2->conflicts, c2);
186 pkg_debug(2, "registering conflict between %s(%s) and %s(%s)",
187 p2->uid, p2->type == PKG_INSTALLED ? "l" : "r",
188 p1->uid, p1->type == PKG_INSTALLED ? "l" : "r");
189 } else {
190 pkg_conflict_free(c2);
191 }
192 }
193
194
195
196 static int
pkg_conflicts_item_cmp(struct pkg_jobs_conflict_item * a,struct pkg_jobs_conflict_item * b)197 pkg_conflicts_item_cmp(struct pkg_jobs_conflict_item *a,
198 struct pkg_jobs_conflict_item *b)
199 {
200 return (b->hash - a->hash);
201 }
202
203 /*
204 * Checks whether we need to add a conflict between two packages
205 */
206 static bool
pkg_conflicts_need_conflict(struct pkg_jobs * j,struct pkg * p1,struct pkg * p2)207 pkg_conflicts_need_conflict(struct pkg_jobs *j, struct pkg *p1, struct pkg *p2)
208 {
209 struct pkg_file *fcur;
210
211 if (pkgdb_ensure_loaded(j->db, p1, PKG_LOAD_FILES|PKG_LOAD_DIRS) != EPKG_OK ||
212 pkgdb_ensure_loaded(j->db, p2, PKG_LOAD_FILES|PKG_LOAD_DIRS)
213 != EPKG_OK) {
214 /*
215 * If some of packages are not loaded we could silently and safely
216 * ignore them
217 */
218 pkg_debug(1, "cannot load files from %s and %s to check conflicts",
219 p1->name, p2->name);
220
221 return (false);
222 }
223
224 /*
225 * Check if we already have this conflict registered
226 */
227 if (kh_contains(pkg_conflicts, p1->conflictshash, p2->uid) &&
228 kh_contains(pkg_conflicts, p2->conflictshash, p1->uid))
229 return false;
230
231 /*
232 * We need to check all files and dirs and find the similar ones
233 */
234 LL_FOREACH(p1->files, fcur) {
235 if (pkg_has_file(p2, fcur->path))
236 return (true);
237 if (pkg_has_dir(p2, fcur->path))
238 return (true);
239 }
240 /* XXX pkg dirs are terribly broken */
241
242 /* No common paths are found in p1 and p2 */
243 return (false);
244 }
245
246 /*
247 * Just insert new conflicts items to the packages
248 */
249 static void
pkg_conflicts_register_unsafe(struct pkg * p1,struct pkg * p2,const char * path,enum pkg_conflict_type type,bool use_digest)250 pkg_conflicts_register_unsafe(struct pkg *p1, struct pkg *p2,
251 const char *path,
252 enum pkg_conflict_type type,
253 bool use_digest)
254 {
255 struct pkg_conflict *c1, *c2;
256
257 kh_find(pkg_conflicts, p1->conflictshash, p2->uid, c1);
258 kh_find(pkg_conflicts, p2->conflictshash, p1->uid, c2);
259 if (c1 == NULL) {
260 c1 = xcalloc(1, sizeof(*c1));
261 c1->type = type;
262 c1->uid = xstrdup(p2->uid);
263
264 if (use_digest) {
265 c1->digest = xstrdup(p2->digest);
266 }
267
268 kh_safe_add(pkg_conflicts, p1->conflictshash, c1, c1->uid);
269 DL_APPEND(p1->conflicts, c1);
270 }
271
272 if (c2 == NULL) {
273 c2 = xcalloc(1, sizeof(*c2));
274 c2->type = type;
275
276 c2->uid = xstrdup(p1->uid);
277
278 if (use_digest) {
279 /* We also add digest information into account */
280
281 c2->digest = xstrdup(p1->digest);
282 }
283
284 kh_safe_add(pkg_conflicts, p2->conflictshash, c2, c2->uid);
285 DL_APPEND(p2->conflicts, c2);
286 }
287
288 pkg_debug(2, "registering conflict between %s(%s) and %s(%s) on path %s",
289 p1->uid, p1->type == PKG_INSTALLED ? "l" : "r",
290 p2->uid, p2->type == PKG_INSTALLED ? "l" : "r", path);
291 }
292
293 /*
294 * Register conflicts between packages in the universe chains
295 */
296 static bool
pkg_conflicts_register_chain(struct pkg_jobs * j,struct pkg_job_universe_item * u1,struct pkg_job_universe_item * u2,const char * path)297 pkg_conflicts_register_chain(struct pkg_jobs *j, struct pkg_job_universe_item *u1,
298 struct pkg_job_universe_item *u2, const char *path)
299 {
300 struct pkg_job_universe_item *cur1, *cur2;
301 bool ret = false;
302
303 cur1 = u1;
304
305 do {
306
307 cur2 = u2;
308 do {
309 struct pkg *p1 = cur1->pkg, *p2 = cur2->pkg;
310
311 if (p1->type == PKG_INSTALLED && p2->type == PKG_INSTALLED) {
312 /* Local and local packages cannot conflict */
313 cur2 = cur2->prev;
314 continue;
315 }
316 else if (p1->type == PKG_INSTALLED || p2->type == PKG_INSTALLED) {
317 /* local <-> remote conflict */
318 if (pkg_conflicts_need_conflict(j, p1, p2)) {
319 pkg_emit_conflicts(p1, p2, path);
320 pkg_conflicts_register_unsafe(p1, p2, path,
321 PKG_CONFLICT_REMOTE_LOCAL, true);
322 j->conflicts_registered ++;
323 ret = true;
324 }
325 }
326 else {
327 /* two remote packages */
328 if (pkg_conflicts_need_conflict(j, p1, p2)) {
329 pkg_emit_conflicts(p1, p2, path);
330 pkg_conflicts_register_unsafe(p1, p2, path,
331 PKG_CONFLICT_REMOTE_REMOTE, true);
332 j->conflicts_registered ++;
333 ret = true;
334 }
335 }
336 cur2 = cur2->prev;
337 } while (cur2 != u2);
338
339 cur1 = cur1->prev;
340 } while (cur1 != u1);
341
342 return (ret);
343 }
344
345 /*
346 * Check whether the specified path is registered locally and returns
347 * the package that contains that path or NULL if no conflict was found
348 */
349 static struct pkg *
pkg_conflicts_check_local_path(const char * path,const char * uid,struct pkg_jobs * j)350 pkg_conflicts_check_local_path(const char *path, const char *uid,
351 struct pkg_jobs *j)
352 {
353 const char sql_local_conflict[] = ""
354 "SELECT p.name as uniqueid FROM packages AS p "
355 "INNER JOIN files AS f "
356 "ON p.id = f.package_id "
357 "WHERE f.path = ?1;";
358 sqlite3_stmt *stmt;
359 int ret;
360 struct pkg *p = NULL;
361
362 pkg_debug(4, "Pkgdb: running '%s'", sql_local_conflict);
363 ret = sqlite3_prepare_v2(j->db->sqlite, sql_local_conflict, -1,
364 &stmt, NULL);
365 if (ret != SQLITE_OK) {
366 ERROR_SQLITE(j->db->sqlite, sql_local_conflict);
367 return (NULL);
368 }
369
370 sqlite3_bind_text(stmt, 1,
371 path, -1, SQLITE_STATIC);
372 sqlite3_bind_text(stmt, 2,
373 uid, -1, SQLITE_STATIC);
374
375 if (sqlite3_step(stmt) == SQLITE_ROW) {
376 /*
377 * We have found the conflict with some other chain, so find that chain
378 * or update the universe
379 */
380 const char *uid_local = sqlite3_column_text(stmt, 0);
381
382 p = pkg_jobs_universe_get_local(j->universe,
383 uid_local, 0);
384 assert(p != NULL);
385
386 assert(strcmp(uid, p->uid) != 0);
387
388 if (!kh_contains(pkg_conflicts, p->conflictshash, uid)) {
389 /* We need to register the conflict between two universe chains */
390 sqlite3_finalize(stmt);
391 return (p);
392 }
393 }
394
395 sqlite3_finalize(stmt);
396 return (NULL);
397 }
398
399 static struct pkg_job_universe_item *
pkg_conflicts_check_all_paths(struct pkg_jobs * j,const char * path,struct pkg_job_universe_item * it,struct sipkey * k)400 pkg_conflicts_check_all_paths(struct pkg_jobs *j, const char *path,
401 struct pkg_job_universe_item *it, struct sipkey *k)
402 {
403 const char *uid1, *uid2;
404 struct pkg_jobs_conflict_item *cit, test;
405 struct pkg_conflict *c;
406 uint64_t hv;
407
408 hv = siphash24(path, strlen(path), k);
409 test.hash = hv;
410 cit = TREE_FIND(j->conflict_items, pkg_jobs_conflict_item, entry, &test);
411
412 if (cit == NULL) {
413 /* New entry */
414 cit = xcalloc(1, sizeof(*cit));
415 cit->hash = hv;
416 cit->item = it;
417 TREE_INSERT(j->conflict_items, pkg_jobs_conflict_item, entry, cit);
418 }
419 else {
420 /* Check the same package */
421 if (cit->item == it)
422 return (NULL);
423
424 uid1 = it->pkg->uid;
425 uid2 = cit->item->pkg->uid;
426 if (strcmp(uid1, uid2) == 0) {
427 /* The same upgrade chain, just upgrade item for speed */
428 cit->item = it;
429 return (NULL);
430 }
431
432 /* Here we can have either collision or a real conflict */
433 kh_find(pkg_conflicts, it->pkg->conflictshash, uid2, c);
434 if (c != NULL || !pkg_conflicts_register_chain(j, it, cit->item, path)) {
435 /*
436 * Collision found, change the key following the
437 * Cuckoo principle
438 */
439 struct sipkey nk;
440
441 pkg_debug(2, "found a collision on path %s between %s and %s, key: %lu",
442 path, uid1, uid2, (unsigned long)k->k[0]);
443
444 nk = *k;
445 nk.k[0] ++;
446 return (pkg_conflicts_check_all_paths(j, path, it, &nk));
447 }
448
449 return (cit->item);
450 }
451
452 return (NULL);
453 }
454
455 static void
pkg_conflicts_check_chain_conflict(struct pkg_job_universe_item * it,struct pkg_job_universe_item * local,struct pkg_jobs * j)456 pkg_conflicts_check_chain_conflict(struct pkg_job_universe_item *it,
457 struct pkg_job_universe_item *local, struct pkg_jobs *j)
458 {
459 struct pkg_file *fcur;
460 struct pkg *p;
461 struct pkg_job_universe_item *cun;
462 struct sipkey *k;
463
464 LL_FOREACH(it->pkg->files, fcur) {
465 k = pkg_conflicts_sipkey_init();
466 /* Check in hash tree */
467 cun = pkg_conflicts_check_all_paths(j, fcur->path, it, k);
468
469 if (local != NULL) {
470 /* Filter only new files for remote packages */
471 if (pkg_has_file(local->pkg, fcur->path))
472 continue;
473 }
474 /* Check for local conflict in db */
475 p = pkg_conflicts_check_local_path(fcur->path, it->pkg->uid, j);
476 pkg_debug(4, "integrity: check path %s of package %s", fcur->path,
477 it->pkg->uid);
478
479 if (p != NULL) {
480 if (pkg_jobs_universe_process_item(j->universe, p, &cun))
481 continue;
482 assert(cun != NULL);
483 pkg_conflicts_register_chain(j, it, cun, fcur->path);
484 }
485 }
486 /* XXX: dirs are currently broken terribly */
487 #if 0
488 struct pkg_dir *dcur, *dtmp, *df;
489 HASH_ITER(hh, it->pkg->dirs, dcur, dtmp) {
490 memset(&k, 0, sizeof(k));
491 cun = pkg_conflicts_check_all_paths(j, dcur->path, it, &k);
492
493 if (local != NULL) {
494 HASH_FIND_STR(local->pkg->dirs, dcur->path, df);
495 if (df != NULL)
496 continue;
497 }
498 /* Check for local conflict in db */
499 p = pkg_conflicts_check_local_path(dcur->path, uid, j);
500 if (p != NULL) {
501 pkg_jobs_universe_process_item(j->universe, p, &cun);
502 assert(cun != NULL);
503 pkg_conflicts_register_chain(j, it, cun, dcur->path);
504 }
505 }
506 #endif
507 }
508
509 int
pkg_conflicts_append_chain(struct pkg_job_universe_item * it,struct pkg_jobs * j)510 pkg_conflicts_append_chain(struct pkg_job_universe_item *it,
511 struct pkg_jobs *j)
512 {
513 struct pkg_job_universe_item *lp = NULL, *cur;
514
515 /* Ensure that we have a tree initialized */
516 if (j->conflict_items == NULL) {
517 j->conflict_items = xmalloc(sizeof(*j->conflict_items));
518 TREE_INIT(j->conflict_items, pkg_conflicts_item_cmp);
519 }
520
521 /* Find local package */
522 cur = it->prev;
523 while (cur != it) {
524 if (cur->pkg->type == PKG_INSTALLED) {
525 lp = cur;
526 if (pkgdb_ensure_loaded(j->db, cur->pkg, PKG_LOAD_FILES|PKG_LOAD_DIRS)
527 != EPKG_OK)
528 return (EPKG_FATAL);
529
530 /* Local package is found */
531 break;
532 }
533 cur = cur->prev;
534 }
535
536 /*
537 * Now we go through the all packages in the chain and check them against
538 * conflicts with the locally installed files
539 */
540 cur = it;
541 do {
542 if (cur != lp) {
543 if (pkgdb_ensure_loaded(j->db, cur->pkg, PKG_LOAD_FILES|PKG_LOAD_DIRS)
544 != EPKG_OK) {
545 /*
546 * This means that a package was not downloaded, so we can safely
547 * ignore this conflict, since we are not going to install it
548 * anyway
549 */
550 pkg_debug (3, "cannot load files from %s to check integrity",
551 cur->pkg->name);
552 }
553 else {
554 pkg_conflicts_check_chain_conflict(cur, lp, j);
555 }
556 }
557
558 cur = cur->prev;
559 } while (cur != it);
560
561 return (EPKG_OK);
562 }
563