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