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[33];
 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   // printf("%d, hx %x -> %s   %d %s\n", cbdata->idx, hx, fn, fmode, md5);
 226   queue_push(&cbdata->files, cbdata->filesspacen);
 227   addfilesspace(cbdata, (unsigned char *)md5padded, 33);
 228   addfilesspace(cbdata, (unsigned char *)fn, strlen(fn) + 1);
 229 }
 230
 231 static int cand_sort(const void *ap, const void *bp, void *dp)
 232 {
 233   const Id *a = ap;
 234   const Id *b = bp;
 235
 236   unsigned int ax = (unsigned int)a[0];
 237   unsigned int bx = (unsigned int)b[0];
 238   if (ax < bx)
 239     return -1;
 240   if (ax > bx)
 241     return 1;
 242   return (a[1] < 0 ? -a[1] : a[1]) - (b[1] < 0 ? -b[1] : b[1]);
 243 }
 244
 245 static int conflicts_cmp(const void *ap, const void *bp, void *dp)
 246 {
 247   Pool *pool = dp;
 248   const Id *a = ap;
 249   const Id *b = bp;
 250   if (a[0] != b[0])
 251     return strcmp(id2str(pool, a[0]), id2str(pool, b[0]));
 252   if (a[1] != b[1])
 253     return a[1] - b[1];
 254   if (a[3] != b[3])
 255     return a[3] - b[3];
 256   return 0;
 257 }
 258
 259 int
 260 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
 261 {
 262   int i, j, cflmapn, idxmapset;
 263   unsigned int hx;
 264   struct cbdata cbdata;
 265   unsigned int now, start;
 266   void *handle;
 267   Id p;
 268
 269   queue_empty(conflicts);
 270   if (!pkgs->count)
 271     return 0;
 272
 273   now = start = sat_timems(0);
 274   POOL_DEBUG(SAT_DEBUG_STATS, "searching for file conflicts\n");
 275   POOL_DEBUG(SAT_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
 276
 277   memset(&cbdata, 0, sizeof(cbdata));
 278   cbdata.pool = pool;
 279   queue_init(&cbdata.lookat);
 280   queue_init(&cbdata.lookat_dir);
 281   queue_init(&cbdata.files);
 282   map_init(&cbdata.idxmap, pkgs->count);
 283
 284   if (cutoff <= 0)
 285     cutoff = pkgs->count;
 286
 287   /* avarage file list size: 200 files per package */
 288   /* avarage dir count: 20 dirs per package */
 289
 290   /* first pass: scan dirs */
 291   cflmapn = (cutoff + 3) * 64;
 292   while ((cflmapn & (cflmapn - 1)) != 0)
 293     cflmapn = cflmapn & (cflmapn - 1);
 294   cbdata.dirmap = sat_calloc(cflmapn, 2 * sizeof(Id));
 295   cbdata.dirmapn = cflmapn - 1; /* make it a mask */
 296   cbdata.create = 1;
 297   idxmapset = 0;
 298   for (i = 0; i < pkgs->count; i++)
 299     {
 300       p = pkgs->elements[i];
 301       cbdata.idx = i;
 302       if (i == cutoff)
 303         cbdata.create = 0;
 304       handle = (*handle_cb)(pool, p, handle_cbdata);
 305       if (handle)
 306         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 307       if (MAPTST(&cbdata.idxmap, i))
 308         idxmapset++;
 309     }
 310
 311   POOL_DEBUG(SAT_DEBUG_STATS, "dirmap size: %d used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
 312   POOL_DEBUG(SAT_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 313   POOL_DEBUG(SAT_DEBUG_STATS, "dirmap creation took %d ms\n", sat_timems(now));
 314   POOL_DEBUG(SAT_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
 315
 316   /* second pass: scan files */
 317   now = sat_timems(0);
 318   cflmapn = (cutoff + 3) * 128;
 319   while ((cflmapn & (cflmapn - 1)) != 0)
 320     cflmapn = cflmapn & (cflmapn - 1);
 321   cbdata.cflmap = sat_calloc(cflmapn, 2 * sizeof(Id));
 322   cbdata.cflmapn = cflmapn - 1; /* make it a mask */
 323   cbdata.create = 1;
 324   for (i = 0; i < pkgs->count; i++)
 325     {
 326       if (!MAPTST(&cbdata.idxmap, i))
 327         continue;
 328       p = pkgs->elements[i];
 329       cbdata.idx = i;
 330       if (i == cutoff)
 331         cbdata.create = 0;
 332       handle = (*handle_cb)(pool, p, handle_cbdata);
 333       if (handle)
 334         rpm_iterate_filelist(handle, 0, findfileconflicts_cb, &cbdata);
 335     }
 336
 337   POOL_DEBUG(SAT_DEBUG_STATS, "filemap size: %d used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
 338   POOL_DEBUG(SAT_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 339   POOL_DEBUG(SAT_DEBUG_STATS, "filemap creation took %d ms\n", sat_timems(now));
 340
 341   cbdata.dirmap = sat_free(cbdata.dirmap);
 342   cbdata.dirmapn = 0;
 343   cbdata.dirmapused = 0;
 344   cbdata.cflmap = sat_free(cbdata.cflmap);
 345   cbdata.cflmapn = 0;
 346   cbdata.cflmapused = 0;
 347   map_free(&cbdata.idxmap);
 348
 349   now = sat_timems(0);
 350   POOL_DEBUG(SAT_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
 351   queue_free(&cbdata.lookat_dir);
 352   sat_sort(cbdata.lookat.elements, cbdata.lookat.count / 2, sizeof(Id) * 2, &cand_sort, pool);
 353   /* unify */
 354   for (i = j = 0; i < cbdata.lookat.count; i += 2)
 355     {
 356       hx = cbdata.lookat.elements[i];
 357       Id idx = cbdata.lookat.elements[i + 1];
 358       if (j && hx == cbdata.lookat.elements[j - 2] && idx == cbdata.lookat.elements[j - 1])
 359         continue;
 360       cbdata.lookat.elements[j++] = hx;
 361       cbdata.lookat.elements[j++] = idx;
 362     }
 363   POOL_DEBUG(SAT_DEBUG_STATS, "candidates: %d\n", cbdata.lookat.count / 2);
 364
 365   /* third pass: scan candidates */
 366   for (i = 0; i < cbdata.lookat.count - 2; i += 2)
 367     {
 368       int pend, ii, jj;
 369       int pidx = cbdata.lookat.elements[i + 1];
 370       p = pkgs->elements[pidx];
 371       hx = cbdata.lookat.elements[i];
 372       if (cbdata.lookat.elements[i + 2] != hx)
 373         continue;       /* no package left */
 374       queue_empty(&cbdata.files);
 375       cbdata.filesspace = sat_free(cbdata.filesspace);
 376       cbdata.filesspacen = 0;
 377
 378       cbdata.idx = p;
 379       cbdata.hx = cbdata.lookat.elements[i];
 380       handle = (*handle_cb)(pool, p, handle_cbdata);
 381       if (!handle)
 382         continue;
 383       rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_WITHMD5, findfileconflicts2_cb, &cbdata);
 384
 385       pend = cbdata.files.count;
 386       for (j = i + 2; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx; j++)
 387         {
 388           int qidx = cbdata.lookat.elements[j + 1];
 389           Id q = pkgs->elements[qidx];
 390           if (pidx >= cutoff && qidx >= cutoff)
 391             continue;   /* no conflicts between packages with idx >= cutoff */
 392           cbdata.idx = q;
 393           handle = (*handle_cb)(pool, q, handle_cbdata);
 394           if (!handle)
 395             continue;
 396           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_WITHMD5, findfileconflicts2_cb, &cbdata);
 397           for (ii = 0; ii < pend; ii++)
 398             for (jj = pend; jj < cbdata.files.count; jj++)
 399               {
 400                 if (strcmp((char *)cbdata.filesspace + cbdata.files.elements[ii] + 33, (char *)cbdata.filesspace + cbdata.files.elements[jj] + 33))
 401                   continue;
 402                 if (!strcmp((char *)cbdata.filesspace + cbdata.files.elements[ii], (char *)cbdata.filesspace + cbdata.files.elements[jj]))
 403                   continue;
 404                 queue_push(conflicts, str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii] + 33, 1));
 405                 queue_push(conflicts, p);
 406                 queue_push(conflicts, str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii], 1));
 407                 queue_push(conflicts, q);
 408                 queue_push(conflicts, str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[jj], 1));
 409               }
 410         }
 411     }
 412   cbdata.filesspace = sat_free(cbdata.filesspace);
 413   cbdata.filesspacen = 0;
 414   queue_free(&cbdata.lookat);
 415   queue_free(&cbdata.files);
 416   POOL_DEBUG(SAT_DEBUG_STATS, "candidate check took %d ms\n", sat_timems(now));
 417   if (conflicts->count > 5)
 418     sat_sort(conflicts->elements, conflicts->count / 5, 5 * sizeof(Id), conflicts_cmp, pool);
 419   (*handle_cb)(pool, 0, handle_cbdata);
 420   POOL_DEBUG(SAT_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 5);
 421   POOL_DEBUG(SAT_DEBUG_STATS, "file conflict detection took %d ms\n", sat_timems(start));
 422   return conflicts->count;
 423 }
 424