2 * Copyright (c) 2009-2013, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
14 #include "repo_rpmdb.h"
15 #include "pool_fileconflicts.h"
21 Queue lookat; /* conflict candidates */
22 Queue lookat_dir; /* not yet conflicting directories */
26 unsigned int cflmapused;
30 unsigned int dirmapused;
35 unsigned int lastdiridx; /* last diridx we have seen */
36 unsigned int lastdirhash; /* strhash of last dir we have seen */
38 Id idx; /* index of package we're looking at */
39 Id hx; /* used in findfileconflicts2_cb, limit to files matching hx */
42 unsigned char *filesspace;
43 unsigned int filesspacen;
46 #define FILESSPACE_BLOCK 255
49 growhash(Hashtable map, Hashval *mapnp)
51 Hashval mapn = *mapnp;
52 Hashval newn = (mapn + 1) * 2 - 1;
57 m = solv_calloc(newn + 1, 2 * sizeof(Id));
58 for (i = 0; i <= mapn; i++)
70 h = HASHCHAIN_NEXT(h, hh, newn);
73 m[2 * h + 1] = map[2 * i + 1];
81 finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
83 struct cbdata *cbdata = cbdatav;
86 Id oidx, idx = cbdata->idx;
91 h = hx & cbdata->dirmapn;
95 qx = cbdata->dirmap[2 * h];
100 h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
107 cbdata->dirmap[2 * h] = hx;
108 cbdata->dirmap[2 * h + 1] = idx;
109 cbdata->dirmapused++;
110 if (cbdata->dirmapused * 2 > cbdata->dirmapn)
111 cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
114 oidx = cbdata->dirmap[2 * h + 1];
117 /* found a conflict, this dir may be used in multiple packages */
120 MAPSET(&cbdata->idxmap, oidx);
121 cbdata->dirmap[2 * h + 1] = -1;
122 cbdata->dirconflicts++;
124 MAPSET(&cbdata->idxmap, idx);
128 isindirmap(struct cbdata *cbdata, Id hx)
133 h = hx & cbdata->dirmapn;
134 hh = HASHCHAIN_START;
137 qx = cbdata->dirmap[2 * h];
141 return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
142 h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
147 findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
149 struct cbdata *cbdata = cbdatav;
150 int isdir = S_ISDIR(info->mode);
160 dp = fn + info->dirlen;
161 if (info->diridx != cbdata->lastdiridx)
163 cbdata->lastdiridx = info->diridx;
164 cbdata->lastdirhash = strnhash(fn, dp - fn);
166 dhx = cbdata->lastdirhash;
168 /* this mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
169 if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
172 hx = strhash_cont(dp, dhx);
176 h = hx & cbdata->cflmapn;
177 hh = HASHCHAIN_START;
180 qx = cbdata->cflmap[2 * h];
185 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
192 cbdata->cflmap[2 * h] = hx;
193 cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
194 cbdata->cflmapused++;
195 if (cbdata->cflmapused * 2 > cbdata->cflmapn)
196 cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
199 oidx = cbdata->cflmap[2 * h + 1];
205 /* both are directories. delay the conflict, keep oidx in slot */
206 queue_push2(&cbdata->lookat_dir, hx, idx);
210 /* now have file, had directories before. */
211 cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
212 /* dump all delayed directory hits for hx */
213 for (i = 0; i < cbdata->lookat_dir.count; i += 2)
214 if (cbdata->lookat_dir.elements[i] == hx)
215 queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
217 else if (oidx == idx)
218 return; /* no conflicts with ourself, please */
219 queue_push2(&cbdata->lookat, hx, oidx);
220 queue_push2(&cbdata->lookat, hx, idx);
224 addfilesspace(struct cbdata *cbdata, unsigned char *data, int len)
226 cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
227 memcpy(cbdata->filesspace + cbdata->filesspacen, data, len);
228 cbdata->filesspacen += len;
232 findfileconflicts2_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
234 struct cbdata *cbdata = cbdatav;
241 dp = fn + info->dirlen;
242 if (info->diridx != cbdata->lastdiridx)
244 cbdata->lastdiridx = info->diridx;
245 cbdata->lastdirhash = strnhash(fn, dp - fn);
247 hx = cbdata->lastdirhash;
248 hx = strhash_cont(dp, hx);
251 if ((Id)hx != cbdata->hx)
253 strncpy(md5padded, info->digest, 32);
255 md5padded[33] = info->color;
256 /* printf("%d, hx %x -> %s %d %s\n", cbdata->idx, hx, fn, fmode, md5); */
257 queue_push(&cbdata->files, cbdata->filesspacen);
258 addfilesspace(cbdata, (unsigned char *)md5padded, 34);
259 addfilesspace(cbdata, (unsigned char *)fn, strlen(fn) + 1);
263 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
267 unsigned int ahx = (unsigned int)a[0]; /* a[0] can be < 0 */
268 unsigned int bhx = (unsigned int)b[0];
269 return ahx < bhx ? -1 : ahx > bhx ? 1 : a[1] - b[1];
273 conflicts_cmp(const void *ap, const void *bp, void *dp)
278 if (a[0] != b[0]) /* filename1 */
279 return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
280 if (a[3] != b[3]) /* filename2 */
281 return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
282 if (a[1] != b[1]) /* pkgid1 */
284 if (a[4] != b[4]) /* pkgid2 */
290 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
292 Repodata *lastdata = 0;
296 dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
297 while (dataiterator_step(&di))
299 if (di.data == lastdata && di.kv.id == lastdirid)
302 lastdirid = di.kv.id;
303 cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
305 dataiterator_free(&di);
310 iterate_solvable_files(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
315 Repodata *lastdata = 0;
318 struct filelistinfo info;
319 const char *tmpdir = 0;
322 dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
323 memset(&info, 0, sizeof(info));
324 while (dataiterator_step(&di))
326 if (di.data != lastdata || di.kv.id != lastdirid)
329 lastdirid = di.kv.id;
330 tmpdir = repodata_dir2str(di.data, di.kv.id, "");
331 dirl = strlen(tmpdir);
335 l = dirl + strlen(di.kv.str) + 1;
339 space = solv_realloc(space, spacen);
343 strcpy(space, tmpdir);
346 strcpy(space + dirl, di.kv.str);
347 cb(cbdata, space, &info);
349 dataiterator_free(&di);
355 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
357 int i, j, cflmapn, idxmapset;
358 struct cbdata cbdata;
359 unsigned int now, start;
361 Repo *installed = pool->installed;
363 int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
365 queue_empty(conflicts);
369 now = start = solv_timems(0);
370 POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
371 POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
373 memset(&cbdata, 0, sizeof(cbdata));
375 queue_init(&cbdata.lookat);
376 queue_init(&cbdata.lookat_dir);
377 queue_init(&cbdata.files);
378 map_init(&cbdata.idxmap, pkgs->count);
381 cutoff = pkgs->count;
383 /* avarage file list size: 200 files per package */
384 /* avarage dir count: 20 dirs per package */
386 /* first pass: scan dirs */
387 cflmapn = (cutoff + 3) * 64;
388 while ((cflmapn & (cflmapn - 1)) != 0)
389 cflmapn = cflmapn & (cflmapn - 1);
390 cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
391 cbdata.dirmapn = cflmapn - 1; /* make it a mask */
394 for (i = 0; i < pkgs->count; i++)
396 p = pkgs->elements[i];
400 if ((flags & FINDFILECONFLICTS_USESOLVABLEFILELIST) != 0 && installed)
402 if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
404 iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
405 if (MAPTST(&cbdata.idxmap, i))
410 handle = (*handle_cb)(pool, p, handle_cbdata);
413 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
414 if (MAPTST(&cbdata.idxmap, i))
418 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
419 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
420 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
421 POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
423 /* second pass: scan files */
424 now = solv_timems(0);
425 cflmapn = (cutoff + 3) * 128;
426 while ((cflmapn & (cflmapn - 1)) != 0)
427 cflmapn = cflmapn & (cflmapn - 1);
428 cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
429 cbdata.cflmapn = cflmapn - 1; /* make it a mask */
431 for (i = 0; i < pkgs->count; i++)
433 if (!MAPTST(&cbdata.idxmap, i))
435 p = pkgs->elements[i];
439 /* can't use FINDFILECONFLICTS_USESOLVABLEFILELIST because we have to know if
440 * the file is a directory or not */
441 handle = (*handle_cb)(pool, p, handle_cbdata);
444 cbdata.lastdiridx = -1;
445 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_cb, &cbdata);
448 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
449 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
450 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
452 cbdata.dirmap = solv_free(cbdata.dirmap);
454 cbdata.dirmapused = 0;
455 cbdata.cflmap = solv_free(cbdata.cflmap);
457 cbdata.cflmapused = 0;
458 map_free(&cbdata.idxmap);
460 now = solv_timems(0);
461 POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
462 queue_free(&cbdata.lookat_dir);
465 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 2, sizeof(Id) * 2, &lookat_hx_cmp, pool);
466 for (i = j = 0; i < cbdata.lookat.count; i += 2)
468 Id hx = cbdata.lookat.elements[i];
469 Id idx = cbdata.lookat.elements[i + 1];
470 if (j && hx == cbdata.lookat.elements[j - 2] && idx == cbdata.lookat.elements[j - 1])
472 cbdata.lookat.elements[j++] = hx;
473 cbdata.lookat.elements[j++] = idx;
475 queue_truncate(&cbdata.lookat, j);
476 POOL_DEBUG(SOLV_DEBUG_STATS, "candidates: %d\n", cbdata.lookat.count / 2);
478 /* third pass: scan candidates */
479 for (i = 0; i < cbdata.lookat.count - 2; i += 2)
483 Id hx = cbdata.lookat.elements[i];
484 Id pidx = cbdata.lookat.elements[i + 1];
486 iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
487 if (obsoleteusescolors)
488 iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
489 if (cbdata.lookat.elements[i + 2] != hx)
490 continue; /* no package left */
491 queue_empty(&cbdata.files);
492 cbdata.filesspace = solv_free(cbdata.filesspace);
493 cbdata.filesspacen = 0;
495 p = pkgs->elements[pidx];
497 cbdata.hx = cbdata.lookat.elements[i];
498 handle = (*handle_cb)(pool, p, handle_cbdata);
501 cbdata.lastdiridx = -1;
502 rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
504 pend = cbdata.files.count;
505 for (j = i + 2; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx; j += 2)
507 Id q, qidx = cbdata.lookat.elements[j + 1];
508 if (pidx >= cutoff && qidx >= cutoff)
509 continue; /* no conflicts between packages with idx >= cutoff */
510 q = pkgs->elements[qidx];
512 handle = (*handle_cb)(pool, q, handle_cbdata);
515 cbdata.lastdiridx = -1;
516 rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
517 for (ii = 0; ii < pend; ii++)
518 for (jj = pend; jj < cbdata.files.count; jj++)
520 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
521 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
522 if (strcmp(fsi + 34, fsj + 34))
523 continue; /* different file names */
524 if (!strcmp(fsi, fsj))
525 continue; /* md5 sum matches */
526 if (obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
527 continue; /* colors do not conflict */
528 queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
529 queue_push(conflicts, p);
530 queue_push(conflicts, pool_str2id(pool, fsi, 1));
531 queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
532 queue_push(conflicts, q);
533 queue_push(conflicts, pool_str2id(pool, fsj, 1));
535 queue_truncate(&cbdata.files, pend);
538 cbdata.filesspace = solv_free(cbdata.filesspace);
539 cbdata.filesspacen = 0;
540 queue_free(&cbdata.lookat);
541 queue_free(&cbdata.files);
542 POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
543 if (conflicts->count > 6)
544 solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
545 POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
546 POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
547 return conflicts->count;