ext/pool_fileconflicts.c

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