ext/pool_fileconflicts.c

   1 /*
   2  * Copyright (c) 2009-2012, 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   Id idx;       /* index of package we're looking at */
  36   Id hx;        /* used in findfileconflicts2_cb, limit to files matching hx */
  37
  38   Queue files;
  39   unsigned char *filesspace;
  40   unsigned int filesspacen;
  41 };
  42
  43 #define FILESSPACE_BLOCK 255
  44
  45 static Hashtable
  46 growhash(Hashtable map, Hashval *mapnp)
  47 {
  48   Hashval mapn = *mapnp;
  49   Hashval newn = (mapn + 1) * 2 - 1;
  50   Hashval i, h, hh;
  51   Hashtable m;
  52   Id hx, qx;
  53
  54   m = solv_calloc(newn + 1, 2 * sizeof(Id));
  55   for (i = 0; i <= mapn; i++)
  56     {
  57       hx = map[2 * i];
  58       if (!hx)
  59         continue;
  60       h = hx & newn;
  61       hh = HASHCHAIN_START;
  62       for (;;)
  63         {
  64           qx = m[2 * h];
  65           if (!qx)
  66             break;
  67           h = HASHCHAIN_NEXT(h, hh, newn);
  68         }
  69       m[2 * h] = hx;
  70       m[2 * h + 1] = map[2 * i + 1];
  71     }
  72   solv_free(map);
  73   *mapnp = newn;
  74   return m;
  75 }
  76
  77 static void
  78 finddirs_cb(void *cbdatav, const char *fn, int fmode, const char *md5)
  79 {
  80   struct cbdata *cbdata = cbdatav;
  81   Hashval h, hh;
  82   Id hx, qx;
  83   Id oidx, idx = cbdata->idx;
  84
  85   hx = strhash(fn);
  86   if (!hx)
  87     hx = strlen(fn) + 1;
  88   h = hx & cbdata->dirmapn;
  89   hh = HASHCHAIN_START;
  90   for (;;)
  91     {
  92       qx = cbdata->dirmap[2 * h];
  93       if (!qx)
  94         break;
  95       if (qx == hx)
  96         break;
  97       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
  98     }
  99   if (!qx)
 100     {
 101       /* a miss */
 102       if (!cbdata->create)
 103         return;
 104       cbdata->dirmap[2 * h] = hx;
 105       cbdata->dirmap[2 * h + 1] = idx;
 106       cbdata->dirmapused++;
 107       if (cbdata->dirmapused * 2 > cbdata->dirmapn)
 108         cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
 109       return;
 110     }
 111   oidx = cbdata->dirmap[2 * h + 1];
 112   if (oidx == idx)
 113     return;
 114   /* found a conflict, this dir may be used in multiple packages */
 115   if (oidx != -1)
 116     {
 117       MAPSET(&cbdata->idxmap, oidx);
 118       cbdata->dirmap[2 * h + 1] = -1;
 119       cbdata->dirconflicts++;
 120     }
 121   MAPSET(&cbdata->idxmap, idx);
 122 }
 123
 124 static inline int
 125 isindirmap(struct cbdata *cbdata, Id hx)
 126 {
 127   Hashval h, hh;
 128   Id qx;
 129
 130   h = hx & cbdata->dirmapn;
 131   hh = HASHCHAIN_START;
 132   for (;;)
 133     {
 134       qx = cbdata->dirmap[2 * h];
 135       if (!qx)
 136         return 0;
 137       if (qx == hx)
 138         return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
 139       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 140     }
 141 }
 142
 143 static void
 144 findfileconflicts_cb(void *cbdatav, const char *fn, int fmode, const char *md5)
 145 {
 146   struct cbdata *cbdata = cbdatav;
 147   int isdir = S_ISDIR(fmode);
 148   char *dp;
 149   Id idx, oidx;
 150   Id hx, qx;
 151   Hashval h, hh, dhx;
 152
 153   idx = cbdata->idx;
 154
 155   dp = strrchr(fn, '/');
 156   if (!dp)
 157     return;
 158   dhx = strnhash(fn, dp + 1 - fn);
 159 #if 1
 160   /* this mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
 161   if (!isindirmap(cbdata, dhx ? dhx : dp + 1 - fn + 1))
 162     return;
 163 #endif
 164   hx = strhash_cont(dp + 1, dhx);
 165   if (!hx)
 166     hx = strlen(fn) + 1;
 167
 168   h = hx & cbdata->cflmapn;
 169   hh = HASHCHAIN_START;
 170   for (;;)
 171     {
 172       qx = cbdata->cflmap[2 * h];
 173       if (!qx)
 174         break;
 175       if (qx == hx)
 176         break;
 177       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 178     }
 179   if (!qx)
 180     {
 181       /* a miss */
 182       if (!cbdata->create)
 183         return;
 184       cbdata->cflmap[2 * h] = hx;
 185       cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
 186       cbdata->cflmapused++;
 187       if (cbdata->cflmapused * 2 > cbdata->cflmapn)
 188         cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
 189       return;
 190     }
 191   oidx = cbdata->cflmap[2 * h + 1];
 192   if (oidx < 0)
 193     {
 194       int i;
 195       if (isdir)
 196         {
 197           /* both are directories. delay the conflict, keep oidx in slot */
 198           queue_push2(&cbdata->lookat_dir, hx, idx);
 199           return;
 200         }
 201       oidx = ~oidx;
 202       /* now have file, had directories before. */
 203       cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
 204       /* dump all delayed directory hits for hx */
 205       for (i = 0; i < cbdata->lookat_dir.count; i += 2)
 206         if (cbdata->lookat_dir.elements[i] == hx)
 207           queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
 208     }
 209   else if (oidx == idx)
 210     return;     /* no conflicts with ourself, please */
 211   queue_push2(&cbdata->lookat, hx, oidx);
 212   queue_push2(&cbdata->lookat, hx, idx);
 213 }
 214
 215 static inline void
 216 addfilesspace(struct cbdata *cbdata, unsigned char *data, int len)
 217 {
 218   cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
 219   memcpy(cbdata->filesspace + cbdata->filesspacen, data, len);
 220   cbdata->filesspacen += len;
 221 }
 222
 223 static void
 224 findfileconflicts2_cb(void *cbdatav, const char *fn, int fmode, const char *md5)
 225 {
 226   struct cbdata *cbdata = cbdatav;
 227   Hashval hx = strhash(fn);
 228   char md5padded[34];
 229
 230   if (!hx)
 231     hx = strlen(fn) + 1;
 232   if ((Id)hx != cbdata->hx)
 233     return;
 234   strncpy(md5padded, md5, 32);
 235   md5padded[32] = 0;
 236   md5padded[33] = fmode >> 24;
 237   /* printf("%d, hx %x -> %s   %d %s\n", cbdata->idx, hx, fn, fmode, md5); */
 238   queue_push(&cbdata->files, cbdata->filesspacen);
 239   addfilesspace(cbdata, (unsigned char *)md5padded, 34);
 240   addfilesspace(cbdata, (unsigned char *)fn, strlen(fn) + 1);
 241 }
 242
 243 static int lookat_sort(const void *ap, const void *bp, void *dp)
 244 {
 245   const Id *a = ap;
 246   const Id *b = bp;
 247   unsigned int ahx = (unsigned int)a[0];        /* a[0] can be < 0 */
 248   unsigned int bhx = (unsigned int)b[0];
 249   if (ahx < bhx)
 250     return -1;
 251   if (ahx > bhx)
 252     return 1;
 253   return a[1] - b[1];
 254 }
 255
 256 static int conflicts_cmp(const void *ap, const void *bp, void *dp)
 257 {
 258   Pool *pool = dp;
 259   const Id *a = ap;
 260   const Id *b = bp;
 261   if (a[0] != b[0])     /* filename */
 262     return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
 263   if (a[1] != b[1])     /* idx1 */
 264     return a[1] - b[1];
 265   if (a[3] != b[3])     /* idx2 */
 266     return a[3] - b[3];
 267   return 0;
 268 }
 269
 270 int
 271 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
 272 {
 273   int i, j, cflmapn, idxmapset;
 274   struct cbdata cbdata;
 275   unsigned int now, start;
 276   void *handle;
 277   Id p;
 278   int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
 279
 280   queue_empty(conflicts);
 281   if (!pkgs->count)
 282     return 0;
 283
 284   now = start = solv_timems(0);
 285   POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
 286   POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
 287
 288   memset(&cbdata, 0, sizeof(cbdata));
 289   cbdata.pool = pool;
 290   queue_init(&cbdata.lookat);
 291   queue_init(&cbdata.lookat_dir);
 292   queue_init(&cbdata.files);
 293   map_init(&cbdata.idxmap, pkgs->count);
 294
 295   if (cutoff <= 0)
 296     cutoff = pkgs->count;
 297
 298   /* avarage file list size: 200 files per package */
 299   /* avarage dir count: 20 dirs per package */
 300
 301   /* first pass: scan dirs */
 302   cflmapn = (cutoff + 3) * 64;
 303   while ((cflmapn & (cflmapn - 1)) != 0)
 304     cflmapn = cflmapn & (cflmapn - 1);
 305   cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 306   cbdata.dirmapn = cflmapn - 1; /* make it a mask */
 307   cbdata.create = 1;
 308   idxmapset = 0;
 309   for (i = 0; i < pkgs->count; i++)
 310     {
 311       p = pkgs->elements[i];
 312       cbdata.idx = i;
 313       if (i == cutoff)
 314         cbdata.create = 0;
 315       handle = (*handle_cb)(pool, p, handle_cbdata);
 316       if (handle)
 317         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 318       if (MAPTST(&cbdata.idxmap, i))
 319         idxmapset++;
 320     }
 321
 322   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
 323   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 324   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
 325   POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
 326
 327   /* second pass: scan files */
 328   now = solv_timems(0);
 329   cflmapn = (cutoff + 3) * 128;
 330   while ((cflmapn & (cflmapn - 1)) != 0)
 331     cflmapn = cflmapn & (cflmapn - 1);
 332   cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 333   cbdata.cflmapn = cflmapn - 1; /* make it a mask */
 334   cbdata.create = 1;
 335   for (i = 0; i < pkgs->count; i++)
 336     {
 337       if (!MAPTST(&cbdata.idxmap, i))
 338         continue;
 339       p = pkgs->elements[i];
 340       cbdata.idx = i;
 341       if (i == cutoff)
 342         cbdata.create = 0;
 343       handle = (*handle_cb)(pool, p, handle_cbdata);
 344       if (handle)
 345         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_cb, &cbdata);
 346     }
 347
 348   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
 349   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 350   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
 351
 352   cbdata.dirmap = solv_free(cbdata.dirmap);
 353   cbdata.dirmapn = 0;
 354   cbdata.dirmapused = 0;
 355   cbdata.cflmap = solv_free(cbdata.cflmap);
 356   cbdata.cflmapn = 0;
 357   cbdata.cflmapused = 0;
 358   map_free(&cbdata.idxmap);
 359
 360   now = solv_timems(0);
 361   POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
 362   queue_free(&cbdata.lookat_dir);
 363
 364   /* sort and unify */
 365   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 2, sizeof(Id) * 2, &lookat_sort, pool);
 366   for (i = j = 0; i < cbdata.lookat.count; i += 2)
 367     {
 368       Id hx = cbdata.lookat.elements[i];
 369       Id idx = cbdata.lookat.elements[i + 1];
 370       if (j && hx == cbdata.lookat.elements[j - 2] && idx == cbdata.lookat.elements[j - 1])
 371         continue;
 372       cbdata.lookat.elements[j++] = hx;
 373       cbdata.lookat.elements[j++] = idx;
 374     }
 375   queue_truncate(&cbdata.lookat, j);
 376   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates: %d\n", cbdata.lookat.count / 2);
 377
 378   /* third pass: scan candidates */
 379   for (i = 0; i < cbdata.lookat.count - 2; i += 2)
 380     {
 381       int pend, ii, jj;
 382       int iterflags;
 383       Id hx = cbdata.lookat.elements[i];
 384       Id pidx = cbdata.lookat.elements[i + 1];
 385
 386       iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
 387       if (obsoleteusescolors)
 388         iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
 389       p = pkgs->elements[pidx];
 390       if (cbdata.lookat.elements[i + 2] != hx)
 391         continue;       /* no package left */
 392       queue_empty(&cbdata.files);
 393       cbdata.filesspace = solv_free(cbdata.filesspace);
 394       cbdata.filesspacen = 0;
 395
 396       cbdata.idx = p;
 397       cbdata.hx = cbdata.lookat.elements[i];
 398       handle = (*handle_cb)(pool, p, handle_cbdata);
 399       if (!handle)
 400         continue;
 401       rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
 402
 403       pend = cbdata.files.count;
 404       for (j = i + 2; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx; j++)
 405         {
 406           Id qidx = cbdata.lookat.elements[j + 1];
 407           Id q = pkgs->elements[qidx];
 408           if (pidx >= cutoff && qidx >= cutoff)
 409             continue;   /* no conflicts between packages with idx >= cutoff */
 410           cbdata.idx = q;
 411           handle = (*handle_cb)(pool, q, handle_cbdata);
 412           if (!handle)
 413             continue;
 414           rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
 415           for (ii = 0; ii < pend; ii++)
 416             for (jj = pend; jj < cbdata.files.count; jj++)
 417               {
 418                 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
 419                 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
 420                 if (strcmp(fsi + 34, fsj + 34))
 421                   continue;     /* different file names */
 422                 if (!strcmp(fsi, fsj))
 423                   continue;     /* md5 sum matches */
 424                 if (obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
 425                   continue;     /* colors do not conflict */
 426                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii] + 34, 1));
 427                 queue_push(conflicts, p);
 428                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii], 1));
 429                 queue_push(conflicts, q);
 430                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[jj], 1));
 431               }
 432         }
 433     }
 434   cbdata.filesspace = solv_free(cbdata.filesspace);
 435   cbdata.filesspacen = 0;
 436   queue_free(&cbdata.lookat);
 437   queue_free(&cbdata.files);
 438   POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
 439   if (conflicts->count > 5)
 440     solv_sort(conflicts->elements, conflicts->count / 5, 5 * sizeof(Id), conflicts_cmp, pool);
 441   (*handle_cb)(pool, 0, handle_cbdata);
 442   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 5);
 443   POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
 444   return conflicts->count;
 445 }
 446