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