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