ext/pool_fileconflicts.c

   1 /*
   2  * Copyright (c) 2009-2013, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 #include <stdio.h>
   9 #include <sys/stat.h>
  10
  11 #include "pool.h"
  12 #include "repo.h"
  13 #include "hash.h"
  14 #include "repo_rpmdb.h"
  15 #include "pool_fileconflicts.h"
  16
  17 struct cbdata {
  18   Pool *pool;
  19   int create;
  20
  21   Queue lookat;         /* conflict candidates */
  22   Queue lookat_dir;     /* not yet conflicting directories */
  23
  24   Hashtable cflmap;
  25   Hashval cflmapn;
  26   unsigned int cflmapused;
  27
  28   Hashtable dirmap;
  29   Hashval dirmapn;
  30   unsigned int dirmapused;
  31   int dirconflicts;
  32
  33   Map idxmap;
  34
  35   unsigned int lastdiridx;      /* last diridx we have seen */
  36   unsigned int lastdirhash;     /* strhash of last dir we have seen */
  37
  38   Id idx;       /* index of package we're looking at */
  39   Id hx;        /* used in findfileconflicts2_cb, limit to files matching hx */
  40
  41   Queue files;
  42   unsigned char *filesspace;
  43   unsigned int filesspacen;
  44 };
  45
  46 #define FILESSPACE_BLOCK 255
  47
  48 static Hashtable
  49 growhash(Hashtable map, Hashval *mapnp)
  50 {
  51   Hashval mapn = *mapnp;
  52   Hashval newn = (mapn + 1) * 2 - 1;
  53   Hashval i, h, hh;
  54   Hashtable m;
  55   Id hx, qx;
  56
  57   m = solv_calloc(newn + 1, 2 * sizeof(Id));
  58   for (i = 0; i <= mapn; i++)
  59     {
  60       hx = map[2 * i];
  61       if (!hx)
  62         continue;
  63       h = hx & newn;
  64       hh = HASHCHAIN_START;
  65       for (;;)
  66         {
  67           qx = m[2 * h];
  68           if (!qx)
  69             break;
  70           h = HASHCHAIN_NEXT(h, hh, newn);
  71         }
  72       m[2 * h] = hx;
  73       m[2 * h + 1] = map[2 * i + 1];
  74     }
  75   solv_free(map);
  76   *mapnp = newn;
  77   return m;
  78 }
  79
  80 static void
  81 finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
  82 {
  83   struct cbdata *cbdata = cbdatav;
  84   Hashval h, hh;
  85   Id hx, qx;
  86   Id oidx, idx = cbdata->idx;
  87
  88   hx = strhash(fn);
  89   if (!hx)
  90     hx = strlen(fn) + 1;
  91   h = hx & cbdata->dirmapn;
  92   hh = HASHCHAIN_START;
  93   for (;;)
  94     {
  95       qx = cbdata->dirmap[2 * h];
  96       if (!qx)
  97         break;
  98       if (qx == hx)
  99         break;
 100       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 101     }
 102   if (!qx)
 103     {
 104       /* a miss */
 105       if (!cbdata->create)
 106         return;
 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);
 112       return;
 113     }
 114   oidx = cbdata->dirmap[2 * h + 1];
 115   if (oidx == idx)
 116     return;
 117   /* found a conflict, this dir may be used in multiple packages */
 118   if (oidx != -1)
 119     {
 120       MAPSET(&cbdata->idxmap, oidx);
 121       cbdata->dirmap[2 * h + 1] = -1;
 122       cbdata->dirconflicts++;
 123     }
 124   MAPSET(&cbdata->idxmap, idx);
 125 }
 126
 127 static inline int
 128 isindirmap(struct cbdata *cbdata, Id hx)
 129 {
 130   Hashval h, hh;
 131   Id qx;
 132
 133   h = hx & cbdata->dirmapn;
 134   hh = HASHCHAIN_START;
 135   for (;;)
 136     {
 137       qx = cbdata->dirmap[2 * h];
 138       if (!qx)
 139         return 0;
 140       if (qx == hx)
 141         return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
 142       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 143     }
 144 }
 145
 146 static void
 147 findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 148 {
 149   struct cbdata *cbdata = cbdatav;
 150   int isdir = S_ISDIR(info->mode);
 151   const char *dp;
 152   Id idx, oidx;
 153   Id hx, qx;
 154   Hashval h, hh, dhx;
 155
 156   idx = cbdata->idx;
 157
 158   if (!info->dirlen)
 159     return;
 160   dp = fn + info->dirlen;
 161   if (info->diridx != cbdata->lastdiridx)
 162     {
 163       cbdata->lastdiridx = info->diridx;
 164       cbdata->lastdirhash = strnhash(fn, dp - fn);
 165     }
 166   dhx = cbdata->lastdirhash;
 167 #if 1
 168   /* this mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
 169   if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
 170     return;
 171 #endif
 172   hx = strhash_cont(dp, dhx);
 173   if (!hx)
 174     hx = strlen(fn) + 1;
 175
 176   h = hx & cbdata->cflmapn;
 177   hh = HASHCHAIN_START;
 178   for (;;)
 179     {
 180       qx = cbdata->cflmap[2 * h];
 181       if (!qx)
 182         break;
 183       if (qx == hx)
 184         break;
 185       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 186     }
 187   if (!qx)
 188     {
 189       /* a miss */
 190       if (!cbdata->create)
 191         return;
 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);
 197       return;
 198     }
 199   oidx = cbdata->cflmap[2 * h + 1];
 200   if (oidx < 0)
 201     {
 202       int i;
 203       if (isdir)
 204         {
 205           /* both are directories. delay the conflict, keep oidx in slot */
 206           queue_push2(&cbdata->lookat_dir, hx, idx);
 207           return;
 208         }
 209       oidx = ~oidx;
 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]);
 216     }
 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);
 221 }
 222
 223 static inline void
 224 addfilesspace(struct cbdata *cbdata, unsigned char *data, int len)
 225 {
 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;
 229 }
 230
 231 static void
 232 findfileconflicts2_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 233 {
 234   struct cbdata *cbdata = cbdatav;
 235   Hashval hx;
 236   const char *dp;
 237   char md5padded[34];
 238
 239   if (!info->dirlen)
 240     return;
 241   dp = fn + info->dirlen;
 242   if (info->diridx != cbdata->lastdiridx)
 243     {
 244       cbdata->lastdiridx = info->diridx;
 245       cbdata->lastdirhash = strnhash(fn, dp - fn);
 246     }
 247   hx = cbdata->lastdirhash;
 248   hx = strhash_cont(dp, hx);
 249   if (!hx)
 250     hx = strlen(fn) + 1;
 251   if ((Id)hx != cbdata->hx)
 252     return;
 253   strncpy(md5padded, info->digest, 32);
 254   md5padded[32] = 0;
 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);
 260 }
 261
 262 static int
 263 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
 264 {
 265   const Id *a = ap;
 266   const Id *b = bp;
 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];
 270 }
 271
 272 static int
 273 conflicts_cmp(const void *ap, const void *bp, void *dp)
 274 {
 275   Pool *pool = dp;
 276   const Id *a = ap;
 277   const Id *b = bp;
 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 */
 283     return a[1] - b[1];
 284   if (a[4] != b[4])     /* pkgid2 */
 285     return a[4] - b[4];
 286   return 0;
 287 }
 288
 289 static void
 290 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
 291 {
 292   Repodata *lastdata = 0;
 293   Id lastdirid = -1;
 294   Dataiterator di;
 295
 296   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 297   while (dataiterator_step(&di))
 298     {
 299       if (di.data == lastdata && di.kv.id == lastdirid)
 300         continue;
 301       lastdata = di.data;
 302       lastdirid = di.kv.id;
 303       cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
 304     }
 305   dataiterator_free(&di);
 306 }
 307
 308 #if 0
 309 static void
 310 iterate_solvable_files(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
 311 {
 312   Dataiterator di;
 313   char *space = 0;
 314   int spacen = 0;
 315   Repodata *lastdata = 0;
 316   Id lastdirid = -1;
 317   int dirl = 0, l;
 318   struct filelistinfo info;
 319   const char *tmpdir = 0;
 320   unsigned int diridx;
 321
 322   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 323   memset(&info, 0, sizeof(info));
 324   while (dataiterator_step(&di))
 325     {
 326       if (di.data != lastdata || di.kv.id != lastdirid)
 327         {
 328           lastdata = di.data;
 329           lastdirid = di.kv.id;
 330           tmpdir = repodata_dir2str(di.data, di.kv.id, "");
 331           dirl = strlen(tmpdir);
 332           info.diridx++;
 333           info.dirlen = dirl;
 334         }
 335       l = dirl + strlen(di.kv.str) + 1;
 336       if (l > spacen)
 337         {
 338           spacen = l + 16;
 339           space = solv_realloc(space, spacen);
 340         }
 341       if (tmpdir)
 342         {
 343           strcpy(space, tmpdir);
 344           tmpdir = 0;
 345         }
 346       strcpy(space + dirl, di.kv.str);
 347       cb(cbdata, space, &info);
 348     }
 349   dataiterator_free(&di);
 350   solv_free(space);
 351 }
 352 #endif
 353
 354 int
 355 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
 356 {
 357   int i, j, cflmapn, idxmapset;
 358   struct cbdata cbdata;
 359   unsigned int now, start;
 360   void *handle;
 361   Repo *installed = pool->installed;
 362   Id p;
 363   int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
 364
 365   queue_empty(conflicts);
 366   if (!pkgs->count)
 367     return 0;
 368
 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);
 372
 373   memset(&cbdata, 0, sizeof(cbdata));
 374   cbdata.pool = pool;
 375   queue_init(&cbdata.lookat);
 376   queue_init(&cbdata.lookat_dir);
 377   queue_init(&cbdata.files);
 378   map_init(&cbdata.idxmap, pkgs->count);
 379
 380   if (cutoff <= 0)
 381     cutoff = pkgs->count;
 382
 383   /* avarage file list size: 200 files per package */
 384   /* avarage dir count: 20 dirs per package */
 385
 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 */
 392   cbdata.create = 1;
 393   idxmapset = 0;
 394   for (i = 0; i < pkgs->count; i++)
 395     {
 396       p = pkgs->elements[i];
 397       cbdata.idx = i;
 398       if (i == cutoff)
 399         cbdata.create = 0;
 400       if ((flags & FINDFILECONFLICTS_USESOLVABLEFILELIST) != 0 && installed)
 401         {
 402           if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 403             {
 404               iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
 405               if (MAPTST(&cbdata.idxmap, i))
 406                 idxmapset++;
 407               continue;
 408             }
 409         }
 410       handle = (*handle_cb)(pool, p, handle_cbdata);
 411       if (!handle)
 412         continue;
 413       rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 414       if (MAPTST(&cbdata.idxmap, i))
 415         idxmapset++;
 416     }
 417
 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);
 422
 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 */
 430   cbdata.create = 1;
 431   for (i = 0; i < pkgs->count; i++)
 432     {
 433       if (!MAPTST(&cbdata.idxmap, i))
 434         continue;
 435       p = pkgs->elements[i];
 436       cbdata.idx = i;
 437       if (i == cutoff)
 438         cbdata.create = 0;
 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);
 442       if (!handle)
 443         continue;
 444       cbdata.lastdiridx = -1;
 445       rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_cb, &cbdata);
 446     }
 447
 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));
 451
 452   cbdata.dirmap = solv_free(cbdata.dirmap);
 453   cbdata.dirmapn = 0;
 454   cbdata.dirmapused = 0;
 455   cbdata.cflmap = solv_free(cbdata.cflmap);
 456   cbdata.cflmapn = 0;
 457   cbdata.cflmapused = 0;
 458   map_free(&cbdata.idxmap);
 459
 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);
 463
 464   /* sort and unify */
 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)
 467     {
 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])
 471         continue;
 472       cbdata.lookat.elements[j++] = hx;
 473       cbdata.lookat.elements[j++] = idx;
 474     }
 475   queue_truncate(&cbdata.lookat, j);
 476   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates: %d\n", cbdata.lookat.count / 2);
 477
 478   /* third pass: scan candidates */
 479   for (i = 0; i < cbdata.lookat.count - 2; i += 2)
 480     {
 481       int pend, ii, jj;
 482       int iterflags;
 483       Id hx = cbdata.lookat.elements[i];
 484       Id pidx = cbdata.lookat.elements[i + 1];
 485
 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;
 494
 495       p = pkgs->elements[pidx];
 496       cbdata.idx = p;
 497       cbdata.hx = cbdata.lookat.elements[i];
 498       handle = (*handle_cb)(pool, p, handle_cbdata);
 499       if (!handle)
 500         continue;
 501       cbdata.lastdiridx = -1;
 502       rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
 503
 504       pend = cbdata.files.count;
 505       for (j = i + 2; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx; j += 2)
 506         {
 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];
 511           cbdata.idx = q;
 512           handle = (*handle_cb)(pool, q, handle_cbdata);
 513           if (!handle)
 514             continue;
 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++)
 519               {
 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));
 534               }
 535           queue_truncate(&cbdata.files, pend);
 536         }
 537     }
 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;
 548 }
 549