2 * Copyright (c) 2009-2013, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
17 #include "repo_rpmdb.h"
18 #include "pool_fileconflicts.h"
25 Queue lookat; /* conflict candidates */
26 Queue lookat_dir; /* not yet conflicting directories */
30 unsigned int cflmapused;
34 unsigned int dirmapused;
39 unsigned int lastdiridx; /* last diridx we have seen */
40 unsigned int lastdirhash; /* strhash of last dir we have seen */
42 Id idx; /* index of package we're looking at */
43 Id hx; /* used in findfileconflicts2_cb, limit to files matching hx */
45 Id dirid; /* used in findfileconflicts2_cb, limit to dirs matching dirid */
46 Id dirhash; /* used in findfileconflicts2_cb, limit to dirs matching dirhash */
49 unsigned char *filesspace;
50 unsigned int filesspacen;
54 unsigned int normapused;
59 unsigned int statmapused;
71 #define FILESSPACE_BLOCK 255
74 growhash(Hashtable map, Hashval *mapnp)
76 Hashval mapn = *mapnp;
77 Hashval newn = (mapn + 1) * 2 - 1;
82 m = solv_calloc(newn + 1, 2 * sizeof(Id));
83 for (i = 0; i <= mapn; i++)
95 h = HASHCHAIN_NEXT(h, hh, newn);
98 m[2 * h + 1] = map[2 * i + 1];
106 finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
108 struct cbdata *cbdata = cbdatav;
111 Id oidx, idx = cbdata->idx;
116 h = hx & cbdata->dirmapn;
117 hh = HASHCHAIN_START;
120 qx = cbdata->dirmap[2 * h];
125 h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
132 cbdata->dirmap[2 * h] = hx;
133 cbdata->dirmap[2 * h + 1] = idx;
134 if (++cbdata->dirmapused * 2 > cbdata->dirmapn)
135 cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
138 oidx = cbdata->dirmap[2 * h + 1];
141 /* found a conflict, this dir may be used in multiple packages */
144 MAPSET(&cbdata->idxmap, oidx);
145 cbdata->dirmap[2 * h + 1] = -1;
146 cbdata->dirconflicts++;
148 MAPSET(&cbdata->idxmap, idx);
152 isindirmap(struct cbdata *cbdata, Id hx)
157 h = hx & cbdata->dirmapn;
158 hh = HASHCHAIN_START;
161 qx = cbdata->dirmap[2 * h];
165 return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
166 h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
171 findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
173 struct cbdata *cbdata = cbdatav;
174 int isdir = S_ISDIR(info->mode);
184 dp = fn + info->dirlen;
185 if (info->diridx != cbdata->lastdiridx)
187 cbdata->lastdiridx = info->diridx;
188 cbdata->lastdirhash = strnhash(fn, dp - fn);
190 dhx = cbdata->lastdirhash;
191 /* this mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
192 if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
194 hx = strhash_cont(dp, dhx);
198 h = hx & cbdata->cflmapn;
199 hh = HASHCHAIN_START;
202 qx = cbdata->cflmap[2 * h];
207 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
214 cbdata->cflmap[2 * h] = hx;
215 cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
216 if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
217 cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
220 oidx = cbdata->cflmap[2 * h + 1];
226 /* both are directories. delay the conflict, keep oidx in slot */
227 queue_push2(&cbdata->lookat_dir, hx, idx);
231 /* now have file, had directories before. */
232 cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
233 /* dump all delayed directory hits for hx */
234 for (i = 0; i < cbdata->lookat_dir.count; i += 2)
235 if (cbdata->lookat_dir.elements[i] == hx)
237 queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
238 queue_push2(&cbdata->lookat, 0, 0);
241 else if (oidx == idx)
242 return; /* no conflicts with ourself, please */
243 queue_push2(&cbdata->lookat, hx, oidx);
244 queue_push2(&cbdata->lookat, 0, 0);
245 queue_push2(&cbdata->lookat, hx, idx);
246 queue_push2(&cbdata->lookat, 0, 0);
249 /* same as findfileconflicts_cb, but
250 * - hashes with just the basename
251 * - sets idx in a map instead of pushing to lookat
252 * - sets the hash element to -1 if there may be a conflict
255 findfileconflicts_basename_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
257 struct cbdata *cbdata = cbdatav;
258 int isdir = S_ISDIR(info->mode);
268 dp = fn + info->dirlen;
273 h = hx & cbdata->cflmapn;
274 hh = HASHCHAIN_START;
277 qx = cbdata->cflmap[2 * h];
282 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
289 cbdata->cflmap[2 * h] = hx;
290 cbdata->cflmap[2 * h + 1] = (isdir ? -idx - 2 : idx);
291 if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
292 cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
295 oidx = cbdata->cflmap[2 * h + 1];
301 /* both are directories. delay the conflict, keep oidx in slot */
302 queue_push2(&cbdata->lookat_dir, hx, idx);
306 /* now have file, had directories before. */
307 cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
308 /* dump all delayed directory hits for hx */
309 for (i = 0; i < cbdata->lookat_dir.count; i += 2)
310 if (cbdata->lookat_dir.elements[i] == hx)
311 MAPSET(&cbdata->idxmap, cbdata->lookat_dir.elements[i + 1]);
313 else if (oidx == idx)
314 return; /* no conflicts with ourself, please */
316 MAPSET(&cbdata->idxmap, oidx);
317 MAPSET(&cbdata->idxmap, idx);
319 cbdata->cflmap[2 * h + 1] = -1;
323 addfilesspace(struct cbdata *cbdata, int len)
325 unsigned int off = cbdata->filesspacen;
326 cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
327 cbdata->filesspacen += len;
332 unifywithstat(struct cbdata *cbdata, Id diroff, int dirl)
339 unsigned char statdata[16 + sizeof(stb.st_dev) + sizeof(stb.st_ino)];
341 if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == '/')
342 cbdata->filesspace[diroff + dirl - 1] = 0;
344 i = stat((char *)cbdata->filesspace + diroff, &stb);
345 if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == 0)
346 cbdata->filesspace[diroff + dirl - 1] = '/';
349 memset(statdata, 0, 16);
350 memcpy(statdata + 8, &stb.st_dev, sizeof(stb.st_dev));
351 memcpy(statdata, &stb.st_ino, sizeof(stb.st_ino));
353 for (i = 15; i >= 0; i--)
354 hx = (unsigned int)hx * 13 + statdata[i];
355 h = hx & cbdata->statmapn;
356 hh = HASHCHAIN_START;
359 qx = cbdata->statmap[2 * h];
364 Id off = cbdata->statmap[2 * h + 1];
365 char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
366 if (!memcmp(dp, statdata, 16))
367 return cbdata->norq.elements[off + 1];
369 h = HASHCHAIN_NEXT(h, hh, cbdata->statmapn);
371 /* new stat result. work. */
372 nspaceoff = addfilesspace(cbdata, 16);
373 memcpy(cbdata->filesspace + nspaceoff, statdata, 16);
374 queue_push2(&cbdata->norq, nspaceoff, nspaceoff);
375 cbdata->statmap[2 * h] = hx;
376 cbdata->statmap[2 * h + 1] = cbdata->norq.count - 2;
377 if (++cbdata->statmapused * 2 > cbdata->statmapn)
378 cbdata->statmap = growhash(cbdata->statmap, &cbdata->statmapn);
382 /* forward declaration */
383 static Id normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create);
386 unifywithcanon(struct cbdata *cbdata, Id diroff, int dirl)
393 printf("UNIFY %.*s\n", dirl, (char *)cbdata->filesspace + diroff);
395 if (!dirl || cbdata->filesspace[diroff] != '/')
398 while (dirl && cbdata->filesspace[diroff + dirl - 1] == '/')
404 for (i = dirl - 1; i > 0; i--)
405 if (cbdata->filesspace[diroff + i] == '/')
407 i++; /* include trailing / */
409 /* normalize dirname */
410 dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, i, strnhash((char *)cbdata->filesspace + diroff, i), 1);
412 return diroff; /* hit "in progress" marker, some cyclic link */
414 /* sanity check result */
415 if (cbdata->filesspace[dirnameid] != '/')
416 return diroff; /* hmm */
417 l = strlen((char *)cbdata->filesspace + dirnameid);
418 if (l && cbdata->filesspace[dirnameid + l - 1] != '/')
419 return diroff; /* hmm */
421 /* special handling for "." and ".." basename */
422 if (cbdata->filesspace[diroff + i] == '.')
426 if (dirl - i == 2 && cbdata->filesspace[diroff + i + 1] == '.')
429 return dirnameid; /* we hit our root */
430 for (i = l - 2; i > 0; i--)
431 if (cbdata->filesspace[dirnameid + i] == '/')
433 i++; /* include trailing / */
434 dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + dirnameid, i, strnhash((char *)cbdata->filesspace + dirnameid, i), 1);
435 return dirnameid == -1 ? diroff : dirnameid;
439 /* append basename to normalized dirname */
440 if (cbdata->rootdirl + l + dirl - i + 1 > cbdata->canonspacen)
442 cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + 20;
443 cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
444 strcpy(cbdata->canonspace, cbdata->rootdir);
446 strcpy(cbdata->canonspace + cbdata->rootdirl, (char *)cbdata->filesspace + dirnameid);
447 strncpy(cbdata->canonspace + cbdata->rootdirl + l, (char *)cbdata->filesspace + diroff + i, dirl - i);
448 cbdata->canonspace[cbdata->rootdirl + l + dirl - i] = 0;
451 printf("stat()ing %s\n", cbdata->canonspace);
454 if (lstat(cbdata->canonspace, &stb) != 0 || !S_ISLNK(stb.st_mode))
456 /* not a symlink or stat failed, have new canon entry */
457 diroff = addfilesspace(cbdata, l + dirl - i + 2);
458 strcpy((char *)cbdata->filesspace + diroff, cbdata->canonspace + cbdata->rootdirl);
461 if (cbdata->filesspace[diroff + l - 1] != '/')
463 cbdata->filesspace[diroff + l++] = '/';
464 cbdata->filesspace[diroff + l] = 0;
466 /* call normalizedir on new entry for unification purposes */
467 dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, l, strnhash((char *)cbdata->filesspace + diroff, l), 1);
468 return dirnameid == -1 ? diroff : dirnameid;
470 /* oh no, a symlink! follow */
471 lo = cbdata->rootdirl + l + dirl - i + 1;
472 if (lo + stb.st_size + 2 > cbdata->canonspacen)
474 cbdata->canonspacen = lo + stb.st_size + 20;
475 cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
477 ll = readlink(cbdata->canonspace, cbdata->canonspace + lo, stb.st_size);
478 if (ll < 0 || ll > stb.st_size)
479 return diroff; /* hmm */
481 return dirnameid; /* empty means current dir */
482 if (cbdata->canonspace[lo + ll - 1] != '/')
483 cbdata->canonspace[lo + ll++] = '/'; /* add trailing / */
484 cbdata->canonspace[lo + ll] = 0; /* zero terminate */
485 if (cbdata->canonspace[lo] != '/')
487 /* relative link, concatenate to dirname */
488 memmove(cbdata->canonspace + cbdata->rootdirl + l, cbdata->canonspace + lo, ll + 1);
489 lo = cbdata->rootdirl;
492 dirnameid = normalizedir(cbdata, cbdata->canonspace + lo, ll, strnhash(cbdata->canonspace + lo, ll), 1);
493 return dirnameid == -1 ? diroff : dirnameid;
497 * map a directory (containing a trailing /) into a number.
498 * for unifywithstat this is the offset to the 16 byte stat result.
499 * for unifywithcanon this is the offset to the normailzed dir.
502 normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create)
511 h = hx & cbdata->normapn;
512 hh = HASHCHAIN_START;
515 qx = cbdata->normap[2 * h];
520 Id off = cbdata->normap[2 * h + 1];
521 char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
522 if (!strncmp(dp, dir, dirl) && dp[dirl] == 0)
523 return cbdata->norq.elements[off + 1];
525 h = HASHCHAIN_NEXT(h, hh, cbdata->normapn);
530 if (dir >= (const char *)cbdata->filesspace && dir < (const char *)cbdata->filesspace + cbdata->filesspacen)
532 /* can happen when called from unifywithcanon */
533 Id off = dir - (const char *)cbdata->filesspace;
534 nspaceoff = addfilesspace(cbdata, dirl + 1);
535 dir = (const char *)cbdata->filesspace + off;
538 nspaceoff = addfilesspace(cbdata, dirl + 1);
540 memcpy(cbdata->filesspace + nspaceoff, dir, dirl);
541 cbdata->filesspace[nspaceoff + dirl] = 0;
542 mycnt = cbdata->norq.count;
543 queue_push2(&cbdata->norq, nspaceoff, -1); /* -1: in progress */
544 cbdata->normap[2 * h] = hx;
545 cbdata->normap[2 * h + 1] = mycnt;
546 if (++cbdata->normapused * 2 > cbdata->normapn)
547 cbdata->normap = growhash(cbdata->normap, &cbdata->normapn);
550 nspaceoff = unifywithstat(cbdata, nspaceoff, dirl);
552 nspaceoff = unifywithcanon(cbdata, nspaceoff, dirl);
553 cbdata->norq.elements[mycnt + 1] = nspaceoff; /* patch in result */
555 if (!cbdata->usestat)
556 printf("%s normalized to %d: %s\n", cbdata->filesspace + cbdata->norq.elements[mycnt], nspaceoff, cbdata->filesspace + nspaceoff);
562 findfileconflicts_alias_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
564 int isdir = S_ISDIR(info->mode);
565 struct cbdata *cbdata = cbdatav;
575 dp = fn + info->dirlen;
576 if (info->diridx != cbdata->lastdiridx)
578 cbdata->lastdiridx = info->diridx;
579 cbdata->lastdirhash = 0;
581 dp = fn + info->dirlen;
586 h = hx & cbdata->cflmapn;
587 hh = HASHCHAIN_START;
590 qx = cbdata->cflmap[2 * h];
595 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
597 if (!qx || cbdata->cflmap[2 * h + 1] != -1)
599 if (!cbdata->lastdirhash)
600 cbdata->lastdirhash = strnhash(fn, dp - fn);
601 dirid = normalizedir(cbdata, fn, dp - fn, cbdata->lastdirhash, 1);
602 queue_push2(&cbdata->lookat, hx, idx);
603 queue_push2(&cbdata->lookat, cbdata->lastdirhash, isdir ? -dirid : dirid);
607 findfileconflicts2_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
609 struct cbdata *cbdata = cbdatav;
617 dp = fn + info->dirlen;
618 if (info->diridx != cbdata->lastdiridx)
620 cbdata->lastdiridx = info->diridx;
621 cbdata->lastdirhash = strnhash(fn, dp - fn);
625 if (cbdata->lastdirhash != cbdata->dirhash)
631 hx = cbdata->lastdirhash;
632 hx = strhash_cont(dp, hx);
636 if ((Id)hx != cbdata->hx)
638 if (cbdata->dirid && cbdata->dirid != normalizedir(cbdata, fn, dp - fn, cbdata->dirhash, 0))
640 strncpy(md5padded, info->digest, 32);
642 md5padded[33] = info->color;
643 /* printf("%d, hx %x -> %s %d %s\n", cbdata->idx, hx, fn, info->mode, info->digest); */
644 off = addfilesspace(cbdata, strlen(fn) + (34 + 1));
645 memcpy(cbdata->filesspace + off, (unsigned char *)md5padded, 34);
646 strcpy((char *)cbdata->filesspace + off + 34, fn);
647 queue_push(&cbdata->files, off);
651 lookat_idx_cmp(const void *ap, const void *bp, void *dp)
653 const Id *a = ap, *b = bp;
654 unsigned int ahx, bhx;
655 if (a[1] - b[1] != 0) /* idx */
657 if (a[3] - b[3] != 0) /* dirid */
659 ahx = (unsigned int)a[0]; /* can be < 0 */
660 bhx = (unsigned int)b[0];
662 return ahx < bhx ? -1 : 1;
663 ahx = (unsigned int)a[2]; /* dhx */
664 bhx = (unsigned int)b[2];
666 return ahx < bhx ? -1 : 1;
671 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
673 const Id *a = ap, *b = bp;
674 unsigned int ahx, bhx;
676 ahx = (unsigned int)a[0]; /* can be < 0 */
677 bhx = (unsigned int)b[0];
679 return ahx < bhx ? -1 : 1;
680 adirid = a[3] < 0 ? -a[3] : a[3];
681 bdirid = b[3] < 0 ? -b[3] : b[3];
682 if (adirid - bdirid != 0) /* dirid */
683 return adirid - bdirid;
685 return a[3] > 0 ? -1 : 1; /* bring positive dirids to front */
686 if (a[1] - b[1] != 0) /* idx */
688 ahx = (unsigned int)a[2]; /* dhx */
689 bhx = (unsigned int)b[2];
691 return ahx < bhx ? -1 : 1;
696 conflicts_cmp(const void *ap, const void *bp, void *dp)
701 if (a[0] != b[0]) /* filename1 */
702 return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
703 if (a[3] != b[3]) /* filename2 */
704 return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
705 if (a[1] != b[1]) /* pkgid1 */
707 if (a[4] != b[4]) /* pkgid2 */
713 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
715 Repodata *lastdata = 0;
719 dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
720 while (dataiterator_step(&di))
722 if (di.data == lastdata && di.kv.id == lastdirid)
725 lastdirid = di.kv.id;
726 cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
728 dataiterator_free(&di);
731 /* before calling the expensive findfileconflicts_cb we check if any of
732 * the files match. This only makes sense when cbdata->create is off.
735 precheck_solvable_files(struct cbdata *cbdata, Pool *pool, Id p)
741 int aliases = cbdata->aliases;
742 unsigned int lastdirid = -1;
743 Hashval lastdirhash = 0;
745 int checkthisdir = 0;
746 Repodata *lastrepodata = 0;
748 dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
749 while (dataiterator_step(&di))
753 /* hash just the basename */
754 hx = strhash(di.kv.str);
756 hx = strlen(di.kv.str) + 1;
760 /* hash the full path */
761 if (di.data != lastrepodata || di.kv.id != lastdirid)
764 lastrepodata = di.data;
765 lastdirid = di.kv.id;
766 dir = repodata_dir2str(lastrepodata, lastdirid, "");
767 lastdirlen = strlen(dir);
768 lastdirhash = strhash(dir);
769 checkthisdir = isindirmap(cbdata, lastdirhash ? lastdirhash : lastdirlen + 1);
773 hx = strhash_cont(di.kv.str, lastdirhash);
775 hx = lastdirlen + strlen(di.kv.str) + 1;
777 h = hx & cbdata->cflmapn;
778 hh = HASHCHAIN_START;
781 qx = cbdata->cflmap[2 * h];
789 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
794 dataiterator_free(&di);
800 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
802 int i, j, cflmapn, idxmapset;
803 struct cbdata cbdata;
804 unsigned int now, start;
806 Repo *installed = pool->installed;
808 int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
810 queue_empty(conflicts);
814 now = start = solv_timems(0);
815 POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
816 POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
818 memset(&cbdata, 0, sizeof(cbdata));
819 cbdata.aliases = flags & FINDFILECONFLICTS_CHECK_DIRALIASING;
821 if (cbdata.aliases && (flags & FINDFILECONFLICTS_USE_ROOTDIR) != 0)
823 cbdata.rootdir = pool_get_rootdir(pool);
824 if (cbdata.rootdir && !strcmp(cbdata.rootdir, "/"))
827 cbdata.rootdirl = strlen(cbdata.rootdir);
831 queue_init(&cbdata.lookat);
832 queue_init(&cbdata.lookat_dir);
833 map_init(&cbdata.idxmap, pkgs->count);
836 cutoff = pkgs->count;
838 /* avarage file list size: 200 files per package */
839 /* avarage dir count: 20 dirs per package */
841 /* first pass: scan dirs */
844 cflmapn = (cutoff + 3) * 64;
845 while ((cflmapn & (cflmapn - 1)) != 0)
846 cflmapn = cflmapn & (cflmapn - 1);
847 cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
848 cbdata.dirmapn = cflmapn - 1; /* make it a mask */
851 for (i = 0; i < pkgs->count; i++)
856 p = pkgs->elements[i];
857 if ((flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
859 if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
861 iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
862 if (MAPTST(&cbdata.idxmap, i))
867 handle = (*handle_cb)(pool, p, handle_cbdata);
870 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
871 if (MAPTST(&cbdata.idxmap, i))
874 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
875 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
876 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
877 POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
880 /* second pass: scan files */
881 now = solv_timems(0);
882 cflmapn = (cutoff + 3) * 128;
883 while ((cflmapn & (cflmapn - 1)) != 0)
884 cflmapn = cflmapn & (cflmapn - 1);
885 cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
886 cbdata.cflmapn = cflmapn - 1; /* make it a mask */
888 for (i = 0; i < pkgs->count; i++)
892 if (!cbdata.aliases && !MAPTST(&cbdata.idxmap, i))
895 p = pkgs->elements[i];
896 if (!cbdata.create && (flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
898 if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
899 if (!precheck_solvable_files(&cbdata, pool, p))
902 /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
903 * the file is a directory or not */
904 handle = (*handle_cb)(pool, p, handle_cbdata);
907 cbdata.lastdiridx = -1;
908 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, cbdata.aliases ? findfileconflicts_basename_cb : findfileconflicts_cb, &cbdata);
911 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
912 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
913 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
914 POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
915 queue_free(&cbdata.lookat_dir);
917 /* we need another pass for aliases */
920 now = solv_timems(0);
921 /* make sure the first offset is not zero */
922 addfilesspace(&cbdata, 1);
923 cflmapn = (cutoff + 3) * 16;
924 while ((cflmapn & (cflmapn - 1)) != 0)
925 cflmapn = cflmapn & (cflmapn - 1);
926 cbdata.normap = solv_calloc(cflmapn, 2 * sizeof(Id));
927 cbdata.normapn = cflmapn - 1; /* make it a mask */
930 cbdata.statmap = solv_calloc(cflmapn, 2 * sizeof(Id));
931 cbdata.statmapn = cflmapn - 1; /* make it a mask */
934 for (i = 0; i < pkgs->count; i++)
936 if (!MAPTST(&cbdata.idxmap, i))
938 p = pkgs->elements[i];
940 /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
941 * the file is a directory or not */
942 handle = (*handle_cb)(pool, p, handle_cbdata);
945 cbdata.lastdiridx = -1;
946 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_alias_cb, &cbdata);
948 POOL_DEBUG(SOLV_DEBUG_STATS, "normap size: %d, used %d\n", cbdata.normapn + 1, cbdata.normapused);
949 POOL_DEBUG(SOLV_DEBUG_STATS, "normap memory usage: %d K\n", (cbdata.normapn + 1) * 2 * (int)sizeof(Id) / 1024);
950 POOL_DEBUG(SOLV_DEBUG_STATS, "stats made: %d\n", cbdata.statsmade);
953 POOL_DEBUG(SOLV_DEBUG_STATS, "statmap size: %d, used %d\n", cbdata.statmapn + 1, cbdata.statmapused);
954 POOL_DEBUG(SOLV_DEBUG_STATS, "statmap memory usage: %d K\n", (cbdata.statmapn + 1) * 2 * (int)sizeof(Id) / 1024);
956 cbdata.statmap = solv_free(cbdata.statmap);
958 cbdata.canonspace = solv_free(cbdata.canonspace);
959 cbdata.canonspacen = 0;
960 POOL_DEBUG(SOLV_DEBUG_STATS, "alias processing took %d ms\n", solv_timems(now));
963 cbdata.dirmap = solv_free(cbdata.dirmap);
965 cbdata.dirmapused = 0;
966 cbdata.cflmap = solv_free(cbdata.cflmap);
968 cbdata.cflmapused = 0;
970 now = solv_timems(0);
972 map_free(&cbdata.idxmap);
974 /* sort and unify/prune */
975 POOL_DEBUG(SOLV_DEBUG_STATS, "raw candidates: %d, pruning\n", cbdata.lookat.count / 4);
976 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
977 for (i = j = 0; i < cbdata.lookat.count; )
980 Id hx = cbdata.lookat.elements[i];
981 Id idx = cbdata.lookat.elements[i + 1];
982 Id dhx = cbdata.lookat.elements[i + 2];
983 Id dirid = cbdata.lookat.elements[i + 3];
985 for (; i < cbdata.lookat.count && hx == cbdata.lookat.elements[i] && (dirid == cbdata.lookat.elements[i + 3] || dirid == -cbdata.lookat.elements[i + 3]); i += 4)
987 if (idx == cbdata.lookat.elements[i + 1] && dhx == cbdata.lookat.elements[i + 2])
988 continue; /* ignore duplicates */
992 continue; /* all have a neg dirid */
993 cbdata.lookat.elements[j++] = hx;
994 cbdata.lookat.elements[j++] = idx;
995 cbdata.lookat.elements[j++] = dhx;
996 cbdata.lookat.elements[j++] = dirid;
999 idx = cbdata.lookat.elements[i + 1];
1000 dhx = cbdata.lookat.elements[i + 2];
1001 cbdata.lookat.elements[j++] = hx;
1002 cbdata.lookat.elements[j++] = idx;
1003 cbdata.lookat.elements[j++] = dhx;
1004 cbdata.lookat.elements[j++] = dirid;
1007 queue_truncate(&cbdata.lookat, j);
1008 POOL_DEBUG(SOLV_DEBUG_STATS, "candidates now: %d\n", cbdata.lookat.count / 4);
1010 /* third pass: collect file info for all files that match a hx */
1011 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_idx_cmp, pool);
1012 queue_init(&cbdata.files);
1013 for (i = 0; i < cbdata.lookat.count; i += 4)
1015 Id idx = cbdata.lookat.elements[i + 1];
1016 int iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
1017 if (obsoleteusescolors)
1018 iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
1019 p = pkgs->elements[idx];
1020 handle = (*handle_cb)(pool, p, handle_cbdata);
1023 int fstart = cbdata.files.count;
1024 queue_push(&cbdata.files, idx);
1025 queue_push(&cbdata.files, 0);
1027 cbdata.hx = cbdata.lookat.elements[i];
1028 cbdata.dirhash = cbdata.lookat.elements[i + 2];
1029 cbdata.dirid = cbdata.lookat.elements[i + 3];
1030 cbdata.lastdiridx = -1;
1032 rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
1033 cbdata.files.elements[fstart + 1] = cbdata.files.count;
1034 cbdata.lookat.elements[i + 1] = fstart;
1035 if (i + 4 >= cbdata.lookat.count || cbdata.lookat.elements[i + 4 + 1] != idx)
1040 cbdata.normap = solv_free(cbdata.normap);
1043 /* forth pass: for each hx we have, compare all matching files against all other matching files */
1044 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
1045 for (i = 0; i < cbdata.lookat.count - 4; i += 4)
1047 Id hx = cbdata.lookat.elements[i];
1048 Id pstart = cbdata.lookat.elements[i + 1];
1049 Id dirid = cbdata.lookat.elements[i + 3];
1050 Id pidx = cbdata.files.elements[pstart];
1051 Id pend = cbdata.files.elements[pstart + 1];
1052 if (cbdata.lookat.elements[i + 4] != hx)
1053 continue; /* no package left with that hx */
1054 for (j = i + 4; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx && cbdata.lookat.elements[j + 3] == dirid; j += 4)
1056 Id qstart = cbdata.lookat.elements[j + 1];
1057 Id qidx = cbdata.files.elements[qstart];
1058 Id qend = cbdata.files.elements[qstart + 1];
1060 if (pidx >= cutoff && qidx >= cutoff)
1061 continue; /* no conflicts between packages with idx >= cutoff */
1062 for (ii = pstart + 2; ii < pend; ii++)
1063 for (jj = qstart + 2; jj < qend; jj++)
1065 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
1066 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
1069 /* compare just the basenames, the dirs match because of the dirid */
1070 char *bsi = strrchr(fsi + 34, '/');
1071 char *bsj = strrchr(fsj + 34, '/');
1074 if (strcmp(bsi, bsj))
1075 continue; /* different base names */
1079 if (strcmp(fsi + 34, fsj + 34))
1080 continue; /* different file names */
1082 if (!strcmp(fsi, fsj))
1083 continue; /* file digests match, no conflict */
1084 if (obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
1085 continue; /* colors do not conflict */
1086 queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
1087 queue_push(conflicts, pkgs->elements[pidx]);
1088 queue_push(conflicts, pool_str2id(pool, fsi, 1));
1089 queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
1090 queue_push(conflicts, pkgs->elements[qidx]);
1091 queue_push(conflicts, pool_str2id(pool, fsj, 1));
1095 POOL_DEBUG(SOLV_DEBUG_STATS, "filespace size: %d K\n", cbdata.filesspacen / 1024);
1096 POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
1097 cbdata.filesspace = solv_free(cbdata.filesspace);
1098 cbdata.filesspacen = 0;
1099 queue_free(&cbdata.lookat);
1100 queue_free(&cbdata.files);
1101 if (conflicts->count > 6)
1102 solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
1103 POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
1104 POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
1106 return conflicts->count / 6;