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   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   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 Hashtable
  46 growhash(Hashtable map, Hashval *mapnp)
  47 {
  48   Hashval mapn = *mapnp;
  49   Hashval i, hx, qx, h, hh;
  50   Hashval nn = (mapn + 1) * 2 - 1;
  51   Hashtable 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   Hashval 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 = growhash(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, Hashval hx)
 123 {
 124   Hashval 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   Hashval 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 = dp + 1 - fn + 1;      /* mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
 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 = growhash(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   int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
 277
 278   queue_empty(conflicts);
 279   if (!pkgs->count)
 280     return 0;
 281
 282   now = start = solv_timems(0);
 283   POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
 284   POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
 285
 286   memset(&cbdata, 0, sizeof(cbdata));
 287   cbdata.pool = pool;
 288   queue_init(&cbdata.lookat);
 289   queue_init(&cbdata.lookat_dir);
 290   queue_init(&cbdata.files);
 291   map_init(&cbdata.idxmap, pkgs->count);
 292
 293   if (cutoff <= 0)
 294     cutoff = pkgs->count;
 295
 296   /* avarage file list size: 200 files per package */
 297   /* avarage dir count: 20 dirs per package */
 298
 299   /* first pass: scan dirs */
 300   cflmapn = (cutoff + 3) * 64;
 301   while ((cflmapn & (cflmapn - 1)) != 0)
 302     cflmapn = cflmapn & (cflmapn - 1);
 303   cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 304   cbdata.dirmapn = cflmapn - 1; /* make it a mask */
 305   cbdata.create = 1;
 306   idxmapset = 0;
 307   for (i = 0; i < pkgs->count; i++)
 308     {
 309       p = pkgs->elements[i];
 310       cbdata.idx = i;
 311       if (i == cutoff)
 312         cbdata.create = 0;
 313       handle = (*handle_cb)(pool, p, handle_cbdata);
 314       if (handle)
 315         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 316       if (MAPTST(&cbdata.idxmap, i))
 317         idxmapset++;
 318     }
 319
 320   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
 321   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 322   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
 323   POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
 324
 325   /* second pass: scan files */
 326   now = solv_timems(0);
 327   cflmapn = (cutoff + 3) * 128;
 328   while ((cflmapn & (cflmapn - 1)) != 0)
 329     cflmapn = cflmapn & (cflmapn - 1);
 330   cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 331   cbdata.cflmapn = cflmapn - 1; /* make it a mask */
 332   cbdata.create = 1;
 333   for (i = 0; i < pkgs->count; i++)
 334     {
 335       if (!MAPTST(&cbdata.idxmap, i))
 336         continue;
 337       p = pkgs->elements[i];
 338       cbdata.idx = i;
 339       if (i == cutoff)
 340         cbdata.create = 0;
 341       handle = (*handle_cb)(pool, p, handle_cbdata);
 342       if (handle)
 343         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_cb, &cbdata);
 344     }
 345
 346   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
 347   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 348   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
 349
 350   cbdata.dirmap = solv_free(cbdata.dirmap);
 351   cbdata.dirmapn = 0;
 352   cbdata.dirmapused = 0;
 353   cbdata.cflmap = solv_free(cbdata.cflmap);
 354   cbdata.cflmapn = 0;
 355   cbdata.cflmapused = 0;
 356   map_free(&cbdata.idxmap);
 357
 358   now = solv_timems(0);
 359   POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
 360   queue_free(&cbdata.lookat_dir);
 361   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 2, sizeof(Id) * 2, &cand_sort, pool);
 362   /* unify */
 363   for (i = j = 0; i < cbdata.lookat.count; i += 2)
 364     {
 365       Id idx;
 366       hx = cbdata.lookat.elements[i];
 367       idx = cbdata.lookat.elements[i + 1];
 368       if (j && hx == cbdata.lookat.elements[j - 2] && idx == cbdata.lookat.elements[j - 1])
 369         continue;
 370       cbdata.lookat.elements[j++] = hx;
 371       cbdata.lookat.elements[j++] = idx;
 372     }
 373   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates: %d\n", cbdata.lookat.count / 2);
 374
 375   /* third pass: scan candidates */
 376   for (i = 0; i < cbdata.lookat.count - 2; i += 2)
 377     {
 378       int pend, ii, jj;
 379       int pidx = cbdata.lookat.elements[i + 1];
 380       int iterflags;
 381
 382       iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
 383       if (obsoleteusescolors)
 384         iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
 385       p = pkgs->elements[pidx];
 386       hx = cbdata.lookat.elements[i];
 387       if (cbdata.lookat.elements[i + 2] != hx)
 388         continue;       /* no package left */
 389       queue_empty(&cbdata.files);
 390       cbdata.filesspace = solv_free(cbdata.filesspace);
 391       cbdata.filesspacen = 0;
 392
 393       cbdata.idx = p;
 394       cbdata.hx = cbdata.lookat.elements[i];
 395       handle = (*handle_cb)(pool, p, handle_cbdata);
 396       if (!handle)
 397         continue;
 398       rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
 399
 400       pend = cbdata.files.count;
 401       for (j = i + 2; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx; j++)
 402         {
 403           int qidx = cbdata.lookat.elements[j + 1];
 404           Id q = pkgs->elements[qidx];
 405           if (pidx >= cutoff && qidx >= cutoff)
 406             continue;   /* no conflicts between packages with idx >= cutoff */
 407           cbdata.idx = q;
 408           handle = (*handle_cb)(pool, q, handle_cbdata);
 409           if (!handle)
 410             continue;
 411           rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
 412           for (ii = 0; ii < pend; ii++)
 413             for (jj = pend; jj < cbdata.files.count; jj++)
 414               {
 415                 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
 416                 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
 417                 if (strcmp(fsi + 34, fsj + 34))
 418                   continue;     /* different file names */
 419                 if (!strcmp(fsi, fsj))
 420                   continue;     /* md5 sum matches */
 421                 if (obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
 422                   continue;     /* colors do not conflict */
 423                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii] + 34, 1));
 424                 queue_push(conflicts, p);
 425                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii], 1));
 426                 queue_push(conflicts, q);
 427                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[jj], 1));
 428               }
 429         }
 430     }
 431   cbdata.filesspace = solv_free(cbdata.filesspace);
 432   cbdata.filesspacen = 0;
 433   queue_free(&cbdata.lookat);
 434   queue_free(&cbdata.files);
 435   POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
 436   if (conflicts->count > 5)
 437     solv_sort(conflicts->elements, conflicts->count / 5, 5 * sizeof(Id), conflicts_cmp, pool);
 438   (*handle_cb)(pool, 0, handle_cbdata);
 439   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 5);
 440   POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
 441   return conflicts->count;
 442 }
 443