Branch data 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 : :
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 : : typedef tll(struct pkg_job_request *) conflict_chain_t;
41 : :
42 [ + + + + : 599 : TREE_DEFINE(pkg_jobs_conflict_item, entry);
+ + + + +
+ + + + +
+ - - + +
- + + + +
+ + + + +
+ + + + +
+ + + + #
# # # # #
# # # # #
# ]
43 : :
44 : : static struct sipkey *
45 : 145 : pkg_conflicts_sipkey_init(void)
46 : : {
47 : : static struct sipkey *kinit;
48 : :
49 [ + + ]: 145 : if (kinit == NULL) {
50 : 36 : kinit = xmalloc(sizeof(*kinit));
51 : 36 : arc4random_buf((unsigned char*)kinit, sizeof(*kinit));
52 : 36 : }
53 : :
54 : 145 : return (kinit);
55 : : }
56 : :
57 : : static int
58 : 4 : pkg_conflicts_chain_cmp_cb(struct pkg_job_request *a, struct pkg_job_request *b)
59 : : {
60 : : const char *vera, *verb;
61 : :
62 [ + - - + ]: 4 : if (a->skip || b->skip) {
63 : 0 : return (a->skip - b->skip);
64 : : }
65 : :
66 : 4 : vera = a->item->pkg->version;
67 : 4 : verb = b->item->pkg->version;
68 : :
69 : : /* Inverse sort to get the maximum version as the first element */
70 : 4 : return (pkg_version_cmp(vera, verb));
71 : 4 : }
72 : :
73 : : static int
74 : 4 : pkg_conflicts_request_resolve_chain(struct pkg *req, conflict_chain_t *chain)
75 : : {
76 : 4 : struct pkg_job_request *selected = NULL;
77 : : const char *slash_pos;
78 : :
79 : : /*
80 : : * First of all prefer pure origins, where the last element of
81 : : * an origin is pkg name
82 : : */
83 [ + - + + : 12 : tll_foreach(*chain, e) {
+ + ]
84 : 8 : slash_pos = strrchr(e->item->item->pkg->origin, '/');
85 [ + - ]: 8 : if (slash_pos != NULL) {
86 [ # # ]: 0 : if (STREQ(slash_pos + 1, req->name)) {
87 : 0 : selected = e->item;
88 : 0 : break;
89 : : }
90 : 0 : }
91 : 8 : }
92 : :
93 [ - + ]: 4 : if (selected == NULL) {
94 : : /* XXX: add manual selection here */
95 : : /* Sort list by version of package */
96 [ + - + + : 20 : tll_sort(*chain, pkg_conflicts_chain_cmp_cb);
+ + - + +
+ + + - +
+ + + + +
- - + + -
+ + - + ]
97 : 4 : selected = tll_front(*chain);
98 : 4 : }
99 : :
100 : 4 : pkg_debug(2, "select %s in the chain of conflicts for %s",
101 : 4 : selected->item->pkg->name, req->name);
102 : : /* Disable conflicts from a request */
103 [ + - + + : 12 : tll_foreach(*chain, e) {
+ + ]
104 [ + + ]: 8 : if (e->item != selected)
105 : 4 : e->item->skip = true;
106 : 8 : }
107 : :
108 : 4 : return (EPKG_OK);
109 : : }
110 : :
111 : : int
112 : 139 : pkg_conflicts_request_resolve(struct pkg_jobs *j)
113 : : {
114 : : struct pkg_job_request *req, *found;
115 : : struct pkg_conflict *c;
116 : : struct pkg_job_universe_item *unit;
117 : : pkghash_it it;
118 : :
119 : 139 : it = pkghash_iterator(j->request_add);
120 [ + + ]: 298 : while (pkghash_next(&it)) {
121 : 159 : req = it.value;
122 : 159 : conflict_chain_t chain = tll_init();
123 [ + + ]: 159 : if (req->skip)
124 : 3 : continue;
125 : :
126 [ + + ]: 166 : LL_FOREACH(req->item->pkg->conflicts, c) {
127 : 10 : unit = pkg_jobs_universe_find(j->universe, c->uid);
128 [ - + ]: 10 : if (unit != NULL) {
129 : 10 : found = pkghash_get_value(j->request_add, unit->pkg->uid);
130 [ + + - + ]: 10 : if (found != NULL && !found->skip) {
131 [ - + + - : 4 : tll_push_front(chain, found);
# # - + -
+ ]
132 : 4 : }
133 : 10 : }
134 : 10 : }
135 [ + + ]: 156 : if (tll_length(chain) > 0) {
136 : : /* Add package itself */
137 [ + - - + : 4 : tll_push_front(chain, req);
+ - - + +
- ]
138 : :
139 [ + - ]: 4 : if (pkg_conflicts_request_resolve_chain(req->item->pkg, &chain) != EPKG_OK) {
140 [ # # # # : 0 : tll_free(chain);
# # ]
141 : 0 : return (EPKG_FATAL);
142 : : }
143 : 4 : }
144 [ + + + + : 164 : tll_free(chain);
+ + ]
145 : : }
146 : :
147 : 139 : return (EPKG_OK);
148 : 139 : }
149 : :
150 : : static int
151 : 380 : pkg_conflicts_item_cmp(struct pkg_jobs_conflict_item *a,
152 : : struct pkg_jobs_conflict_item *b)
153 : : {
154 : 380 : return (b->hash - a->hash);
155 : : }
156 : :
157 : : /*
158 : : * Checks whether we need to add a conflict between two packages
159 : : */
160 : : static bool
161 : 48 : pkg_conflicts_need_conflict(struct pkg_jobs *j, struct pkg *p1, struct pkg *p2)
162 : : {
163 : : struct pkg_file *fcur;
164 : :
165 [ + - - + ]: 48 : if (pkgdb_ensure_loaded(j->db, p1, PKG_LOAD_FILES|PKG_LOAD_DIRS) != EPKG_OK ||
166 : 48 : pkgdb_ensure_loaded(j->db, p2, PKG_LOAD_FILES|PKG_LOAD_DIRS)
167 : 48 : != EPKG_OK) {
168 : : /*
169 : : * If some of packages are not loaded we could silently and safely
170 : : * ignore them
171 : : */
172 : 0 : pkg_debug(1, "cannot load files from %s and %s to check conflicts",
173 : 0 : p1->name, p2->name);
174 : :
175 : 0 : return (false);
176 : : }
177 : :
178 : : /*
179 : : * Check if we already have this conflict registered
180 : : */
181 [ + + + - ]: 48 : if (pkghash_get(p1->conflictshash, p2->uid) != NULL &&
182 : 11 : pkghash_get(p2->conflictshash, p1->uid) != NULL)
183 : 0 : return false;
184 : :
185 : : /*
186 : : * We need to check all files and dirs and find the similar ones
187 : : */
188 [ + + ]: 82 : LL_FOREACH(p1->files, fcur) {
189 [ + + ]: 57 : if (pkg_has_file(p2, fcur->path))
190 : 23 : return (true);
191 [ - + ]: 34 : if (pkg_has_dir(p2, fcur->path))
192 : 0 : return (true);
193 : 34 : }
194 : : /* XXX pkg dirs are terribly broken */
195 : :
196 : : /* No common paths are found in p1 and p2 */
197 : 25 : return (false);
198 : 48 : }
199 : :
200 : : static void
201 : 46 : pkg_conflicts_register_one(struct pkg *p, struct pkg *op,
202 : : enum pkg_conflict_type type)
203 : : {
204 : : struct pkg_conflict *conflict;
205 : :
206 : 46 : conflict = pkghash_get_value(p->conflictshash, op->uid);
207 [ + + ]: 46 : if (conflict != NULL)
208 : 6 : return;
209 : :
210 : 40 : conflict = xcalloc(1, sizeof(*conflict));
211 : 40 : conflict->type = type;
212 : 40 : conflict->uid = xstrdup(op->uid);
213 : 40 : conflict->digest = xstrdup(op->digest);
214 : :
215 [ + + - + ]: 43 : pkghash_safe_add(p->conflictshash, op->uid, conflict, NULL);
216 [ + + ]: 40 : DL_APPEND(p->conflicts, conflict);
217 : 46 : }
218 : :
219 : : /*
220 : : * Record the existence of a file conflict between a pair of packages.
221 : : */
222 : : static void
223 : 23 : pkg_conflicts_register(struct pkg *p1, struct pkg *p2, const char *path,
224 : : enum pkg_conflict_type type)
225 : : {
226 : 23 : pkg_conflicts_register_one(p1, p2, type);
227 : 23 : pkg_conflicts_register_one(p2, p1, type);
228 : :
229 : 23 : pkg_debug(2, "registering conflict between %s(%s) and %s(%s) on path %s",
230 : 23 : p1->uid, p1->type == PKG_INSTALLED ? "local" : "remote",
231 : 23 : p2->uid, p2->type == PKG_INSTALLED ? "local" : "remote", path);
232 : 23 : }
233 : :
234 : : /*
235 : : * Register conflicts between packages in the universe chains
236 : : */
237 : : static bool
238 : 16 : pkg_conflicts_register_chain(struct pkg_jobs *j, struct pkg_job_universe_item *u1,
239 : : struct pkg_job_universe_item *u2, const char *path)
240 : : {
241 : : struct pkg_job_universe_item *cur1, *cur2;
242 : : enum pkg_conflict_type type;
243 : 16 : bool ret = false;
244 : :
245 : 16 : cur1 = u1;
246 : 29 : do {
247 : 29 : cur2 = u2;
248 : 56 : do {
249 : 56 : struct pkg *p1 = cur1->pkg, *p2 = cur2->pkg;
250 : :
251 [ + + + + ]: 56 : if (p1->type == PKG_INSTALLED && p2->type == PKG_INSTALLED)
252 : 8 : type = PKG_CONFLICT_LOCAL_LOCAL;
253 [ + + + + ]: 48 : else if (p1->type == PKG_INSTALLED || p2->type == PKG_INSTALLED)
254 : 29 : type = PKG_CONFLICT_REMOTE_LOCAL;
255 : : else
256 : 19 : type = PKG_CONFLICT_REMOTE_REMOTE;
257 : :
258 : : /* A pair of installed packages cannot conflict. */
259 [ + + + + ]: 56 : if (type != PKG_CONFLICT_LOCAL_LOCAL &&
260 : 48 : pkg_conflicts_need_conflict(j, p1, p2)) {
261 : 23 : pkg_emit_conflicts(p1, p2, path);
262 : 23 : pkg_conflicts_register(p1, p2, path, type);
263 : 23 : j->conflicts_registered++;
264 : 23 : ret = true;
265 : 23 : }
266 : 56 : cur2 = cur2->prev;
267 [ + + ]: 56 : } while (cur2 != u2);
268 : 29 : cur1 = cur1->prev;
269 [ + + ]: 29 : } while (cur1 != u1);
270 : :
271 : 16 : return (ret);
272 : : }
273 : :
274 : : /*
275 : : * Check whether the specified path is registered locally and returns
276 : : * the package that contains that path or NULL if no conflict was found
277 : : */
278 : : static struct pkg *
279 : 77 : pkg_conflicts_check_local_path(const char *path, const char *uid,
280 : : struct pkg_jobs *j)
281 : : {
282 : 77 : const char sql_local_conflict[] = ""
283 : : "SELECT p.name as uniqueid FROM packages AS p "
284 : : "INNER JOIN files AS f "
285 : : "ON p.id = f.package_id "
286 : : "WHERE f.path = ?1;";
287 : : sqlite3_stmt *stmt;
288 : : int ret;
289 : 77 : struct pkg *p = NULL;
290 : :
291 : 77 : ret = sqlite3_prepare_v2(j->db->sqlite, sql_local_conflict, -1,
292 : : &stmt, NULL);
293 [ - + ]: 77 : if (ret != SQLITE_OK) {
294 : 0 : ERROR_SQLITE(j->db->sqlite, sql_local_conflict);
295 : 0 : return (NULL);
296 : : }
297 : :
298 : 154 : sqlite3_bind_text(stmt, 1,
299 : 77 : path, -1, SQLITE_STATIC);
300 : 154 : sqlite3_bind_text(stmt, 2,
301 : 77 : uid, -1, SQLITE_STATIC);
302 : 77 : pkgdb_debug(4, stmt);
303 : :
304 [ + + ]: 77 : if (sqlite3_step(stmt) == SQLITE_ROW) {
305 : : /*
306 : : * We have found the conflict with some other chain, so find that chain
307 : : * or update the universe
308 : : */
309 : 34 : const char *uid_local = sqlite3_column_text(stmt, 0);
310 : :
311 : 68 : p = pkg_jobs_universe_get_local(j->universe,
312 : 34 : uid_local, 0);
313 [ + - ]: 34 : assert(p != NULL);
314 : :
315 [ + - ]: 34 : assert(!STREQ(uid, p->uid));
316 : :
317 [ + + ]: 34 : if (pkghash_get(p->conflictshash, uid) == NULL) {
318 : : /* We need to register the conflict between two universe chains */
319 : 15 : sqlite3_finalize(stmt);
320 : 15 : return (p);
321 : : }
322 : 19 : }
323 : :
324 : 62 : sqlite3_finalize(stmt);
325 : 62 : return (NULL);
326 : 77 : }
327 : :
328 : : static struct pkg_job_universe_item *
329 : 155 : pkg_conflicts_check_all_paths(struct pkg_jobs *j, const char *path,
330 : : struct pkg_job_universe_item *it, struct sipkey *k)
331 : : {
332 : : const char *uid1, *uid2;
333 : : struct pkg_jobs_conflict_item *cit, test;
334 : : struct pkg_conflict *c;
335 : : uint64_t hv;
336 : :
337 : 155 : hv = siphash24(path, strlen(path), k);
338 : 155 : test.hash = hv;
339 : 155 : cit = TREE_FIND(j->conflict_items, pkg_jobs_conflict_item, entry, &test);
340 : :
341 [ + + ]: 155 : if (cit == NULL) {
342 : : /* New entry */
343 : 88 : cit = xcalloc(1, sizeof(*cit));
344 : 88 : cit->hash = hv;
345 : 88 : cit->item = it;
346 : 88 : TREE_INSERT(j->conflict_items, pkg_jobs_conflict_item, entry, cit);
347 : 88 : }
348 : : else {
349 : : /* Check the same package */
350 [ + + ]: 67 : if (cit->item == it)
351 : 28 : return (NULL);
352 : :
353 : 39 : uid1 = it->pkg->uid;
354 : 39 : uid2 = cit->item->pkg->uid;
355 [ + + ]: 39 : if (STREQ(uid1, uid2)) {
356 : : /* The same upgrade chain, just upgrade item for speed */
357 : 28 : cit->item = it;
358 : 28 : return (NULL);
359 : : }
360 : :
361 : : /* Here we can have either collision or a real conflict */
362 : 11 : c = pkghash_get_value(it->pkg->conflictshash, uid2);
363 [ + + - + ]: 11 : if (c != NULL || !pkg_conflicts_register_chain(j, it, cit->item, path)) {
364 : : /*
365 : : * Collision found, change the key following the
366 : : * Cuckoo principle
367 : : */
368 : : struct sipkey nk;
369 : :
370 : 10 : pkg_debug(2, "found a collision on path %s between %s and %s, key: %lu",
371 : 10 : path, uid1, uid2, (unsigned long)k->k[0]);
372 : :
373 : 10 : nk = *k;
374 : 10 : nk.k[0] ++;
375 : 10 : return (pkg_conflicts_check_all_paths(j, path, it, &nk));
376 : : }
377 : :
378 : 1 : return (cit->item);
379 : : }
380 : :
381 : 88 : return (NULL);
382 : 155 : }
383 : :
384 : : static void
385 : 172 : pkg_conflicts_check_chain_conflict(struct pkg_job_universe_item *it,
386 : : struct pkg_job_universe_item *local, struct pkg_jobs *j)
387 : : {
388 : : struct pkg_file *fcur;
389 : : struct pkg *p;
390 : : struct pkg_job_universe_item *cun;
391 : : struct sipkey *k;
392 : :
393 [ + + ]: 317 : LL_FOREACH(it->pkg->files, fcur) {
394 : 145 : k = pkg_conflicts_sipkey_init();
395 : : /* Check in hash tree */
396 : 145 : cun = pkg_conflicts_check_all_paths(j, fcur->path, it, k);
397 : :
398 [ + + ]: 145 : if (local != NULL) {
399 : : /* Filter only new files for remote packages */
400 [ + + ]: 86 : if (pkg_has_file(local->pkg, fcur->path))
401 : 68 : continue;
402 : 18 : }
403 : : /* Check for local conflict in db */
404 : 77 : p = pkg_conflicts_check_local_path(fcur->path, it->pkg->uid, j);
405 : 154 : pkg_debug(4, "integrity: check path %s of package %s", fcur->path,
406 : 77 : it->pkg->uid);
407 : :
408 [ + + ]: 77 : if (p != NULL) {
409 [ - + ]: 15 : if (pkg_jobs_universe_process_item(j->universe, p, &cun))
410 : 0 : continue;
411 [ - + ]: 15 : assert(cun != NULL);
412 : 15 : pkg_conflicts_register_chain(j, it, cun, fcur->path);
413 : 15 : }
414 : 77 : }
415 : : /* XXX: dirs are currently broken terribly */
416 : : #if 0
417 : : struct pkg_dir *dcur, *dtmp, *df;
418 : : HASH_ITER(hh, it->pkg->dirs, dcur, dtmp) {
419 : : memset(&k, 0, sizeof(k));
420 : : cun = pkg_conflicts_check_all_paths(j, dcur->path, it, &k);
421 : :
422 : : if (local != NULL) {
423 : : HASH_FIND_STR(local->pkg->dirs, dcur->path, df);
424 : : if (df != NULL)
425 : : continue;
426 : : }
427 : : /* Check for local conflict in db */
428 : : p = pkg_conflicts_check_local_path(dcur->path, uid, j);
429 : : if (p != NULL) {
430 : : pkg_jobs_universe_process_item(j->universe, p, &cun);
431 : : assert(cun != NULL);
432 : : pkg_conflicts_register_chain(j, it, cun, dcur->path);
433 : : }
434 : : }
435 : : #endif
436 : 172 : }
437 : :
438 : : int
439 : 202 : pkg_conflicts_append_chain(struct pkg_job_universe_item *it,
440 : : struct pkg_jobs *j)
441 : : {
442 : 202 : struct pkg_job_universe_item *lp = NULL, *cur;
443 : :
444 : : /* Ensure that we have a tree initialized */
445 [ + + ]: 202 : if (j->conflict_items == NULL) {
446 : 123 : j->conflict_items = xmalloc(sizeof(*j->conflict_items));
447 : 123 : TREE_INIT(j->conflict_items, pkg_conflicts_item_cmp);
448 : 123 : }
449 : :
450 : : /* Find local package */
451 : 202 : cur = it->prev;
452 [ + + ]: 207 : while (cur != it) {
453 [ + + ]: 79 : if (cur->pkg->type == PKG_INSTALLED) {
454 : 74 : lp = cur;
455 [ - + - + ]: 148 : if (pkgdb_ensure_loaded(j->db, cur->pkg, PKG_LOAD_FILES|PKG_LOAD_DIRS)
456 : 74 : != EPKG_OK)
457 : 0 : return (EPKG_FATAL);
458 : :
459 : : /* Local package is found */
460 : 74 : break;
461 : : }
462 : 5 : cur = cur->prev;
463 : : }
464 : :
465 : : /*
466 : : * Now we go through the all packages in the chain and check them against
467 : : * conflicts with the locally installed files
468 : : */
469 : 202 : cur = it;
470 : 308 : do {
471 [ + + ]: 308 : if (cur != lp) {
472 [ + + + + ]: 468 : if (pkgdb_ensure_loaded(j->db, cur->pkg, PKG_LOAD_FILES|PKG_LOAD_DIRS)
473 : 234 : != EPKG_OK) {
474 : : /*
475 : : * This means that a package was not downloaded, so we can safely
476 : : * ignore this conflict, since we are not going to install it
477 : : * anyway
478 : : */
479 : 62 : pkg_debug (3, "cannot load files from %s to check integrity",
480 : 62 : cur->pkg->name);
481 : 62 : }
482 : : else {
483 : 172 : pkg_conflicts_check_chain_conflict(cur, lp, j);
484 : : }
485 : 234 : }
486 : :
487 : 308 : cur = cur->prev;
488 [ + + ]: 308 : } while (cur != it);
489 : :
490 : 202 : return (EPKG_OK);
491 : 202 : }
|
