2 * Copyright (c) 2009-2013, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
15 #include "repo_rpmdb.h"
16 #include "pool_fileconflicts.h"
23 Queue lookat; /* conflict candidates */
24 Queue lookat_dir; /* not yet conflicting directories */
28 unsigned int cflmapused;
32 unsigned int dirmapused;
37 unsigned int lastdiridx; /* last diridx we have seen */
38 unsigned int lastdirhash; /* strhash of last dir we have seen */
40 Id idx; /* index of package we're looking at */
41 Id hx; /* used in findfileconflicts2_cb, limit to files matching hx */
43 Id dirid; /* used in findfileconflicts2_cb, limit to dirs matching dirid */
44 Id dirhash; /* used in findfileconflicts2_cb, limit to dirs matching dirhash */
47 unsigned char *filesspace;
48 unsigned int filesspacen;
52 unsigned int normapused;
57 unsigned int statmapused;
69 #define FILESSPACE_BLOCK 255
72 growhash(Hashtable map, Hashval *mapnp)
74 Hashval mapn = *mapnp;
75 Hashval newn = (mapn + 1) * 2 - 1;
80 m = solv_calloc(newn + 1, 2 * sizeof(Id));
81 for (i = 0; i <= mapn; i++)
93 h = HASHCHAIN_NEXT(h, hh, newn);
96 m[2 * h + 1] = map[2 * i + 1];
104 finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
106 struct cbdata *cbdata = cbdatav;
109 Id oidx, idx = cbdata->idx;
114 h = hx & cbdata->dirmapn;
115 hh = HASHCHAIN_START;
118 qx = cbdata->dirmap[2 * h];
123 h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
130 cbdata->dirmap[2 * h] = hx;
131 cbdata->dirmap[2 * h + 1] = idx;
132 if (++cbdata->dirmapused * 2 > cbdata->dirmapn)
133 cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
136 oidx = cbdata->dirmap[2 * h + 1];
139 /* found a conflict, this dir may be used in multiple packages */
142 MAPSET(&cbdata->idxmap, oidx);
143 cbdata->dirmap[2 * h + 1] = -1;
144 cbdata->dirconflicts++;
146 MAPSET(&cbdata->idxmap, idx);
150 isindirmap(struct cbdata *cbdata, Id hx)
155 h = hx & cbdata->dirmapn;
156 hh = HASHCHAIN_START;
159 qx = cbdata->dirmap[2 * h];
163 return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
164 h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
169 findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
171 struct cbdata *cbdata = cbdatav;
172 int isdir = S_ISDIR(info->mode);
182 dp = fn + info->dirlen;
183 if (info->diridx != cbdata->lastdiridx)
185 cbdata->lastdiridx = info->diridx;
186 cbdata->lastdirhash = strnhash(fn, dp - fn);
188 dhx = cbdata->lastdirhash;
189 /* this mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
190 if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
192 hx = strhash_cont(dp, dhx);
196 h = hx & cbdata->cflmapn;
197 hh = HASHCHAIN_START;
200 qx = cbdata->cflmap[2 * h];
205 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
212 cbdata->cflmap[2 * h] = hx;
213 cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
214 if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
215 cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
218 oidx = cbdata->cflmap[2 * h + 1];
224 /* both are directories. delay the conflict, keep oidx in slot */
225 queue_push2(&cbdata->lookat_dir, hx, idx);
229 /* now have file, had directories before. */
230 cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
231 /* dump all delayed directory hits for hx */
232 for (i = 0; i < cbdata->lookat_dir.count; i += 2)
233 if (cbdata->lookat_dir.elements[i] == hx)
235 queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
236 queue_push2(&cbdata->lookat, 0, 0);
239 else if (oidx == idx)
240 return; /* no conflicts with ourself, please */
241 queue_push2(&cbdata->lookat, hx, oidx);
242 queue_push2(&cbdata->lookat, 0, 0);
243 queue_push2(&cbdata->lookat, hx, idx);
244 queue_push2(&cbdata->lookat, 0, 0);
247 /* same as findfileconflicts_cb, but
248 * - hashes with just the basename
249 * - sets idx in a map instead of pushing to lookat
250 * - sets the hash element to -1 if there may be a conflict
253 findfileconflicts_basename_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
255 struct cbdata *cbdata = cbdatav;
256 int isdir = S_ISDIR(info->mode);
266 dp = fn + info->dirlen;
271 h = hx & cbdata->cflmapn;
272 hh = HASHCHAIN_START;
275 qx = cbdata->cflmap[2 * h];
280 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
287 cbdata->cflmap[2 * h] = hx;
288 cbdata->cflmap[2 * h + 1] = (isdir ? -idx - 2 : idx);
289 if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
290 cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
293 oidx = cbdata->cflmap[2 * h + 1];
299 /* both are directories. delay the conflict, keep oidx in slot */
300 queue_push2(&cbdata->lookat_dir, hx, idx);
304 /* now have file, had directories before. */
305 cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
306 /* dump all delayed directory hits for hx */
307 for (i = 0; i < cbdata->lookat_dir.count; i += 2)
308 if (cbdata->lookat_dir.elements[i] == hx)
309 MAPSET(&cbdata->idxmap, cbdata->lookat_dir.elements[i + 1]);
311 else if (oidx == idx)
312 return; /* no conflicts with ourself, please */
314 MAPSET(&cbdata->idxmap, oidx);
315 MAPSET(&cbdata->idxmap, idx);
317 cbdata->cflmap[2 * h + 1] = -1;
321 addfilesspace(struct cbdata *cbdata, int len)
323 unsigned int off = cbdata->filesspacen;
324 cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
325 cbdata->filesspacen += len;
330 unifywithstat(struct cbdata *cbdata, Id diroff, int dirl)
337 unsigned char statdata[16 + sizeof(stb.st_dev) + sizeof(stb.st_ino)];
339 if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == '/')
340 cbdata->filesspace[diroff + dirl - 1] = 0;
342 i = stat((char *)cbdata->filesspace + diroff, &stb);
343 if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == 0)
344 cbdata->filesspace[diroff + dirl - 1] = '/';
347 memset(statdata, 0, 16);
348 memcpy(statdata + 8, &stb.st_dev, sizeof(stb.st_dev));
349 memcpy(statdata, &stb.st_ino, sizeof(stb.st_ino));
351 for (i = 15; i >= 0; i--)
352 hx = (unsigned int)hx * 13 + statdata[i];
353 h = hx & cbdata->statmapn;
354 hh = HASHCHAIN_START;
357 qx = cbdata->statmap[2 * h];
362 Id off = cbdata->statmap[2 * h + 1];
363 char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
364 if (!memcmp(dp, statdata, 16))
365 return cbdata->norq.elements[off + 1];
367 h = HASHCHAIN_NEXT(h, hh, cbdata->statmapn);
369 /* new stat result. work. */
370 nspaceoff = addfilesspace(cbdata, 16);
371 memcpy(cbdata->filesspace + nspaceoff, statdata, 16);
372 queue_push2(&cbdata->norq, nspaceoff, nspaceoff);
373 cbdata->statmap[2 * h] = hx;
374 cbdata->statmap[2 * h + 1] = cbdata->norq.count - 2;
375 if (++cbdata->statmapused * 2 > cbdata->statmapn)
376 cbdata->statmap = growhash(cbdata->statmap, &cbdata->statmapn);
380 /* forward declaration */
381 static Id normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create);
384 unifywithcanon(struct cbdata *cbdata, Id diroff, int dirl)
391 printf("UNIFY %.*s\n", dirl, (char *)cbdata->filesspace + diroff);
393 if (!dirl || cbdata->filesspace[diroff] != '/')
396 while (dirl && cbdata->filesspace[diroff + dirl - 1] == '/')
402 for (i = dirl - 1; i > 0; i--)
403 if (cbdata->filesspace[diroff + i] == '/')
405 i++; /* include trailing / */
407 /* normalize dirname */
408 dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, i, strnhash((char *)cbdata->filesspace + diroff, i), 1);
410 return diroff; /* hit "in progress" marker, some cyclic link */
412 /* sanity check result */
413 if (cbdata->filesspace[dirnameid] != '/')
414 return diroff; /* hmm */
415 l = strlen((char *)cbdata->filesspace + dirnameid);
416 if (l && cbdata->filesspace[dirnameid + l - 1] != '/')
417 return diroff; /* hmm */
419 /* special handling for "." and ".." basename */
420 if (cbdata->filesspace[diroff + i] == '.')
424 if (dirl - i == 2 && cbdata->filesspace[diroff + i + 1] == '.')
427 return dirnameid; /* we hit our root */
428 for (i = l - 2; i > 0; i--)
429 if (cbdata->filesspace[dirnameid + i] == '/')
431 i++; /* include trailing / */
432 dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + dirnameid, i, strnhash((char *)cbdata->filesspace + dirnameid, i), 1);
433 return dirnameid == -1 ? diroff : dirnameid;
437 /* append basename to normalized dirname */
438 if (cbdata->rootdirl + l + dirl - i + 1 > cbdata->canonspacen)
440 cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + 20;
441 cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
442 strcpy(cbdata->canonspace, cbdata->rootdir);
444 strcpy(cbdata->canonspace + cbdata->rootdirl, (char *)cbdata->filesspace + dirnameid);
445 strncpy(cbdata->canonspace + cbdata->rootdirl + l, (char *)cbdata->filesspace + diroff + i, dirl - i);
446 cbdata->canonspace[cbdata->rootdirl + l + dirl - i] = 0;
449 printf("stat()ing %s\n", cbdata->canonspace);
452 if (lstat(cbdata->canonspace, &stb) != 0 || !S_ISLNK(stb.st_mode))
454 /* not a symlink or stat failed, have new canon entry */
455 diroff = addfilesspace(cbdata, l + dirl - i + 2);
456 strcpy((char *)cbdata->filesspace + diroff, cbdata->canonspace + cbdata->rootdirl);
459 if (cbdata->filesspace[diroff + l - 1] != '/')
461 cbdata->filesspace[diroff + l++] = '/';
462 cbdata->filesspace[diroff + l] = 0;
464 /* call normalizedir on new entry for unification purposes */
465 dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, l, strnhash((char *)cbdata->filesspace + diroff, l), 1);
466 return dirnameid == -1 ? diroff : dirnameid;
468 /* oh no, a symlink! follow */
469 lo = cbdata->rootdirl + l + dirl - i + 1;
470 if (lo + stb.st_size + 2 > cbdata->canonspacen)
472 cbdata->canonspacen = lo + stb.st_size + 20;
473 cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
475 ll = readlink(cbdata->canonspace, cbdata->canonspace + lo, stb.st_size);
476 if (ll < 0 || ll > stb.st_size)
477 return diroff; /* hmm */
479 return dirnameid; /* empty means current dir */
480 if (cbdata->canonspace[lo + ll - 1] != '/')
481 cbdata->canonspace[lo + ll++] = '/'; /* add trailing / */
482 cbdata->canonspace[lo + ll] = 0; /* zero terminate */
483 if (cbdata->canonspace[lo] != '/')
485 /* relative link, concatenate to dirname */
486 memmove(cbdata->canonspace + cbdata->rootdirl + l, cbdata->canonspace + lo, ll + 1);
487 lo = cbdata->rootdirl;
490 dirnameid = normalizedir(cbdata, cbdata->canonspace + lo, ll, strnhash(cbdata->canonspace + lo, ll), 1);
491 return dirnameid == -1 ? diroff : dirnameid;
495 * map a directory (containing a trailing /) into a number.
496 * for unifywithstat this is the offset to the 16 byte stat result.
497 * for unifywithcanon this is the offset to the normailzed dir.
500 normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create)
509 h = hx & cbdata->normapn;
510 hh = HASHCHAIN_START;
513 qx = cbdata->normap[2 * h];
518 Id off = cbdata->normap[2 * h + 1];
519 char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
520 if (!strncmp(dp, dir, dirl) && dp[dirl] == 0)
521 return cbdata->norq.elements[off + 1];
523 h = HASHCHAIN_NEXT(h, hh, cbdata->normapn);
528 if (dir >= (const char *)cbdata->filesspace && dir < (const char *)cbdata->filesspace + cbdata->filesspacen)
530 /* can happen when called from unifywithcanon */
531 Id off = dir - (const char *)cbdata->filesspace;
532 nspaceoff = addfilesspace(cbdata, dirl + 1);
533 dir = (const char *)cbdata->filesspace + off;
536 nspaceoff = addfilesspace(cbdata, dirl + 1);
538 memcpy(cbdata->filesspace + nspaceoff, dir, dirl);
539 cbdata->filesspace[nspaceoff + dirl] = 0;
540 mycnt = cbdata->norq.count;
541 queue_push2(&cbdata->norq, nspaceoff, -1); /* -1: in progress */
542 cbdata->normap[2 * h] = hx;
543 cbdata->normap[2 * h + 1] = mycnt;
544 if (++cbdata->normapused * 2 > cbdata->normapn)
545 cbdata->normap = growhash(cbdata->normap, &cbdata->normapn);
548 nspaceoff = unifywithstat(cbdata, nspaceoff, dirl);
550 nspaceoff = unifywithcanon(cbdata, nspaceoff, dirl);
551 cbdata->norq.elements[mycnt + 1] = nspaceoff; /* patch in result */
553 if (!cbdata->usestat)
554 printf("%s normalized to %d: %s\n", cbdata->filesspace + cbdata->norq.elements[mycnt], nspaceoff, cbdata->filesspace + nspaceoff);
560 findfileconflicts_alias_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
562 int isdir = S_ISDIR(info->mode);
563 struct cbdata *cbdata = cbdatav;
573 dp = fn + info->dirlen;
574 if (info->diridx != cbdata->lastdiridx)
576 cbdata->lastdiridx = info->diridx;
577 cbdata->lastdirhash = 0;
579 dp = fn + info->dirlen;
584 h = hx & cbdata->cflmapn;
585 hh = HASHCHAIN_START;
588 qx = cbdata->cflmap[2 * h];
593 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
595 if (!qx || cbdata->cflmap[2 * h + 1] != -1)
597 if (!cbdata->lastdirhash)
598 cbdata->lastdirhash = strnhash(fn, dp - fn);
599 dirid = normalizedir(cbdata, fn, dp - fn, cbdata->lastdirhash, 1);
600 queue_push2(&cbdata->lookat, hx, idx);
601 queue_push2(&cbdata->lookat, cbdata->lastdirhash, isdir ? -dirid : dirid);
605 findfileconflicts2_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
607 struct cbdata *cbdata = cbdatav;
615 dp = fn + info->dirlen;
616 if (info->diridx != cbdata->lastdiridx)
618 cbdata->lastdiridx = info->diridx;
619 cbdata->lastdirhash = strnhash(fn, dp - fn);
623 if (cbdata->lastdirhash != cbdata->dirhash)
629 hx = cbdata->lastdirhash;
630 hx = strhash_cont(dp, hx);
634 if ((Id)hx != cbdata->hx)
636 if (cbdata->dirid && cbdata->dirid != normalizedir(cbdata, fn, dp - fn, cbdata->dirhash, 0))
638 strncpy(md5padded, info->digest, 32);
640 md5padded[33] = info->color;
641 /* printf("%d, hx %x -> %s %d %s %d\n", cbdata->idx, hx, fn, info->mode, info->digest, info->color); */
642 off = addfilesspace(cbdata, strlen(fn) + (34 + 1));
643 memcpy(cbdata->filesspace + off, (unsigned char *)md5padded, 34);
644 strcpy((char *)cbdata->filesspace + off + 34, fn);
645 queue_push(&cbdata->files, off);
649 lookat_idx_cmp(const void *ap, const void *bp, void *dp)
651 const Id *a = ap, *b = bp;
652 unsigned int ahx, bhx;
653 if (a[1] - b[1] != 0) /* idx */
655 if (a[3] - b[3] != 0) /* dirid */
657 ahx = (unsigned int)a[0]; /* can be < 0 */
658 bhx = (unsigned int)b[0];
660 return ahx < bhx ? -1 : 1;
661 ahx = (unsigned int)a[2]; /* dhx */
662 bhx = (unsigned int)b[2];
664 return ahx < bhx ? -1 : 1;
669 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
671 const Id *a = ap, *b = bp;
672 unsigned int ahx, bhx;
674 ahx = (unsigned int)a[0]; /* can be < 0 */
675 bhx = (unsigned int)b[0];
677 return ahx < bhx ? -1 : 1;
678 adirid = a[3] < 0 ? -a[3] : a[3];
679 bdirid = b[3] < 0 ? -b[3] : b[3];
680 if (adirid - bdirid != 0) /* dirid */
681 return adirid - bdirid;
683 return a[3] > 0 ? -1 : 1; /* bring positive dirids to front */
684 if (a[1] - b[1] != 0) /* idx */
686 ahx = (unsigned int)a[2]; /* dhx */
687 bhx = (unsigned int)b[2];
689 return ahx < bhx ? -1 : 1;
694 conflicts_cmp(const void *ap, const void *bp, void *dp)
699 if (a[0] != b[0]) /* filename1 */
700 return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
701 if (a[3] != b[3]) /* filename2 */
702 return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
703 if (a[1] != b[1]) /* pkgid1 */
705 if (a[4] != b[4]) /* pkgid2 */
711 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
713 Repodata *lastdata = 0;
717 dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
718 while (dataiterator_step(&di))
720 if (di.data == lastdata && di.kv.id == lastdirid)
723 lastdirid = di.kv.id;
724 cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
726 dataiterator_free(&di);
729 /* before calling the expensive findfileconflicts_cb we check if any of
730 * the files match. This only makes sense when cbdata->create is off.
733 precheck_solvable_files(struct cbdata *cbdata, Pool *pool, Id p)
739 int aliases = cbdata->aliases;
740 unsigned int lastdirid = -1;
741 Hashval lastdirhash = 0;
743 int checkthisdir = 0;
744 Repodata *lastrepodata = 0;
746 dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
747 while (dataiterator_step(&di))
751 /* hash just the basename */
752 hx = strhash(di.kv.str);
754 hx = strlen(di.kv.str) + 1;
758 /* hash the full path */
759 if (di.data != lastrepodata || di.kv.id != lastdirid)
762 lastrepodata = di.data;
763 lastdirid = di.kv.id;
764 dir = repodata_dir2str(lastrepodata, lastdirid, "");
765 lastdirlen = strlen(dir);
766 lastdirhash = strhash(dir);
767 checkthisdir = isindirmap(cbdata, lastdirhash ? lastdirhash : lastdirlen + 1);
771 hx = strhash_cont(di.kv.str, lastdirhash);
773 hx = lastdirlen + strlen(di.kv.str) + 1;
775 h = hx & cbdata->cflmapn;
776 hh = HASHCHAIN_START;
779 qx = cbdata->cflmap[2 * h];
787 h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
792 dataiterator_free(&di);
798 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
800 int i, j, cflmapn, idxmapset;
801 struct cbdata cbdata;
802 unsigned int now, start;
804 Repo *installed = pool->installed;
809 queue_empty(conflicts);
813 now = start = solv_timems(0);
814 /* Hmm, should we have a different flag for this? */
815 usefilecolors = pool_get_flag(pool, POOL_FLAG_IMPLICITOBSOLETEUSESCOLORS);
816 POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
817 POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d, usefilecolors %d\n", pkgs->count, cutoff, usefilecolors);
819 memset(&cbdata, 0, sizeof(cbdata));
820 cbdata.aliases = flags & FINDFILECONFLICTS_CHECK_DIRALIASING;
822 if (cbdata.aliases && (flags & FINDFILECONFLICTS_USE_ROOTDIR) != 0)
824 cbdata.rootdir = pool_get_rootdir(pool);
825 if (cbdata.rootdir && !strcmp(cbdata.rootdir, "/"))
828 cbdata.rootdirl = strlen(cbdata.rootdir);
832 queue_init(&cbdata.lookat);
833 queue_init(&cbdata.lookat_dir);
834 map_init(&cbdata.idxmap, pkgs->count);
837 cutoff = pkgs->count;
839 /* avarage file list size: 200 files per package */
840 /* avarage dir count: 20 dirs per package */
842 /* first pass: scan dirs */
846 cflmapn = (cutoff + 3) * 64;
847 while ((cflmapn & (cflmapn - 1)) != 0)
848 cflmapn = cflmapn & (cflmapn - 1);
849 cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
850 cbdata.dirmapn = cflmapn - 1; /* make it a mask */
853 for (i = 0; i < pkgs->count; i++)
858 p = pkgs->elements[i];
859 if ((flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
861 if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
863 iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
864 if (MAPTST(&cbdata.idxmap, i))
869 handle = (*handle_cb)(pool, p, handle_cbdata);
873 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
874 if (MAPTST(&cbdata.idxmap, i))
877 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
878 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
879 POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
880 POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
881 POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
884 /* second pass: scan files */
885 now = solv_timems(0);
886 cflmapn = (cutoff + 3) * 128;
887 while ((cflmapn & (cflmapn - 1)) != 0)
888 cflmapn = cflmapn & (cflmapn - 1);
889 cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
890 cbdata.cflmapn = cflmapn - 1; /* make it a mask */
893 for (i = 0; i < pkgs->count; i++)
897 if (!cbdata.aliases && !MAPTST(&cbdata.idxmap, i))
900 p = pkgs->elements[i];
901 if (!cbdata.create && (flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
903 if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
904 if (!precheck_solvable_files(&cbdata, pool, p))
907 /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
908 * the file is a directory or not */
909 handle = (*handle_cb)(pool, p, handle_cbdata);
913 cbdata.lastdiridx = -1;
914 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, cbdata.aliases ? findfileconflicts_basename_cb : findfileconflicts_cb, &cbdata);
917 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
918 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
919 POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
920 POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
921 POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
922 queue_free(&cbdata.lookat_dir);
924 /* we need another pass for aliases */
927 now = solv_timems(0);
928 /* make sure the first offset is not zero */
929 addfilesspace(&cbdata, 1);
930 cflmapn = (cutoff + 3) * 16;
931 while ((cflmapn & (cflmapn - 1)) != 0)
932 cflmapn = cflmapn & (cflmapn - 1);
933 cbdata.normap = solv_calloc(cflmapn, 2 * sizeof(Id));
934 cbdata.normapn = cflmapn - 1; /* make it a mask */
937 cbdata.statmap = solv_calloc(cflmapn, 2 * sizeof(Id));
938 cbdata.statmapn = cflmapn - 1; /* make it a mask */
942 for (i = 0; i < pkgs->count; i++)
944 if (!MAPTST(&cbdata.idxmap, i))
946 p = pkgs->elements[i];
948 /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
949 * the file is a directory or not */
950 handle = (*handle_cb)(pool, p, handle_cbdata);
954 cbdata.lastdiridx = -1;
955 rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_alias_cb, &cbdata);
957 POOL_DEBUG(SOLV_DEBUG_STATS, "normap size: %d, used %d\n", cbdata.normapn + 1, cbdata.normapused);
958 POOL_DEBUG(SOLV_DEBUG_STATS, "normap memory usage: %d K\n", (cbdata.normapn + 1) * 2 * (int)sizeof(Id) / 1024);
959 POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
960 POOL_DEBUG(SOLV_DEBUG_STATS, "stats made: %d\n", cbdata.statsmade);
963 POOL_DEBUG(SOLV_DEBUG_STATS, "statmap size: %d, used %d\n", cbdata.statmapn + 1, cbdata.statmapused);
964 POOL_DEBUG(SOLV_DEBUG_STATS, "statmap memory usage: %d K\n", (cbdata.statmapn + 1) * 2 * (int)sizeof(Id) / 1024);
966 cbdata.statmap = solv_free(cbdata.statmap);
968 cbdata.canonspace = solv_free(cbdata.canonspace);
969 cbdata.canonspacen = 0;
970 POOL_DEBUG(SOLV_DEBUG_STATS, "alias processing took %d ms\n", solv_timems(now));
973 cbdata.dirmap = solv_free(cbdata.dirmap);
975 cbdata.dirmapused = 0;
976 cbdata.cflmap = solv_free(cbdata.cflmap);
978 cbdata.cflmapused = 0;
980 map_free(&cbdata.idxmap);
982 /* sort and unify/prune */
983 now = solv_timems(0);
984 POOL_DEBUG(SOLV_DEBUG_STATS, "raw candidates: %d, pruning\n", cbdata.lookat.count / 4);
985 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
986 for (i = j = 0; i < cbdata.lookat.count; )
989 Id hx = cbdata.lookat.elements[i];
990 Id idx = cbdata.lookat.elements[i + 1];
991 Id dhx = cbdata.lookat.elements[i + 2];
992 Id dirid = cbdata.lookat.elements[i + 3];
994 for (; i < cbdata.lookat.count && hx == cbdata.lookat.elements[i] && (dirid == cbdata.lookat.elements[i + 3] || dirid == -cbdata.lookat.elements[i + 3]); i += 4)
996 if (idx == cbdata.lookat.elements[i + 1] && dhx == cbdata.lookat.elements[i + 2])
997 continue; /* ignore duplicates */
1001 continue; /* all have a neg dirid */
1002 cbdata.lookat.elements[j++] = hx;
1003 cbdata.lookat.elements[j++] = idx;
1004 cbdata.lookat.elements[j++] = dhx;
1005 cbdata.lookat.elements[j++] = dirid;
1008 idx = cbdata.lookat.elements[i + 1];
1009 dhx = cbdata.lookat.elements[i + 2];
1010 cbdata.lookat.elements[j++] = hx;
1011 cbdata.lookat.elements[j++] = idx;
1012 cbdata.lookat.elements[j++] = dhx;
1013 cbdata.lookat.elements[j++] = dirid;
1016 queue_truncate(&cbdata.lookat, j);
1017 POOL_DEBUG(SOLV_DEBUG_STATS, "candidates now: %d\n", cbdata.lookat.count / 4);
1018 POOL_DEBUG(SOLV_DEBUG_STATS, "pruning took %d ms\n", solv_timems(now));
1020 /* third pass: collect file info for all files that match a hx */
1021 now = solv_timems(0);
1022 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_idx_cmp, pool);
1023 queue_init(&cbdata.files);
1025 for (i = 0; i < cbdata.lookat.count; i += 4)
1027 Id idx = cbdata.lookat.elements[i + 1];
1028 int iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
1030 iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
1031 p = pkgs->elements[idx];
1032 handle = (*handle_cb)(pool, p, handle_cbdata);
1037 int fstart = cbdata.files.count;
1038 queue_push(&cbdata.files, idx);
1039 queue_push(&cbdata.files, 0);
1041 cbdata.hx = cbdata.lookat.elements[i];
1042 cbdata.dirhash = cbdata.lookat.elements[i + 2];
1043 cbdata.dirid = cbdata.lookat.elements[i + 3];
1044 cbdata.lastdiridx = -1;
1046 rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
1047 cbdata.files.elements[fstart + 1] = cbdata.files.count;
1048 cbdata.lookat.elements[i + 1] = fstart;
1049 if (i + 4 >= cbdata.lookat.count || cbdata.lookat.elements[i + 4 + 1] != idx)
1053 POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
1054 POOL_DEBUG(SOLV_DEBUG_STATS, "file info fetching took %d ms\n", solv_timems(now));
1056 cbdata.normap = solv_free(cbdata.normap);
1059 /* forth pass: for each hx we have, compare all matching files against all other matching files */
1060 now = solv_timems(0);
1061 solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
1062 for (i = 0; i < cbdata.lookat.count - 4; i += 4)
1064 Id hx = cbdata.lookat.elements[i];
1065 Id pstart = cbdata.lookat.elements[i + 1];
1066 Id dirid = cbdata.lookat.elements[i + 3];
1067 Id pidx = cbdata.files.elements[pstart];
1068 Id pend = cbdata.files.elements[pstart + 1];
1069 if (cbdata.lookat.elements[i + 4] != hx)
1070 continue; /* no package left with that hx */
1071 for (j = i + 4; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx && cbdata.lookat.elements[j + 3] == dirid; j += 4)
1073 Id qstart = cbdata.lookat.elements[j + 1];
1074 Id qidx = cbdata.files.elements[qstart];
1075 Id qend = cbdata.files.elements[qstart + 1];
1077 if (pidx >= cutoff && qidx >= cutoff)
1078 continue; /* no conflicts between packages with idx >= cutoff */
1079 for (ii = pstart + 2; ii < pend; ii++)
1080 for (jj = qstart + 2; jj < qend; jj++)
1082 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
1083 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
1086 /* compare just the basenames, the dirs match because of the dirid */
1087 char *bsi = strrchr(fsi + 34, '/');
1088 char *bsj = strrchr(fsj + 34, '/');
1091 if (strcmp(bsi, bsj))
1092 continue; /* different base names */
1096 if (strcmp(fsi + 34, fsj + 34))
1097 continue; /* different file names */
1099 if (!strcmp(fsi, fsj))
1100 continue; /* file digests match, no conflict */
1101 if (usefilecolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
1102 continue; /* colors do not conflict */
1103 queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
1104 queue_push(conflicts, pkgs->elements[pidx]);
1105 queue_push(conflicts, pool_str2id(pool, fsi, 1));
1106 queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
1107 queue_push(conflicts, pkgs->elements[qidx]);
1108 queue_push(conflicts, pool_str2id(pool, fsj, 1));
1112 POOL_DEBUG(SOLV_DEBUG_STATS, "filespace size: %d K\n", cbdata.filesspacen / 1024);
1113 POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
1114 cbdata.filesspace = solv_free(cbdata.filesspace);
1115 cbdata.filesspacen = 0;
1116 queue_free(&cbdata.lookat);
1117 queue_free(&cbdata.files);
1118 if (conflicts->count > 6)
1119 solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
1120 POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
1121 POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
1123 return conflicts->count / 6;