ext/pool_fileconflicts.c

   1 /*
   2  * Copyright (c) 2009-2013, 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 #include <sys/stat.h>
  11 #include <fcntl.h>
  12 #include <unistd.h>
  13
  14 #include "pool.h"
  15 #include "repo.h"
  16 #include "hash.h"
  17 #include "repo_rpmdb.h"
  18 #include "pool_fileconflicts.h"
  19
  20 struct cbdata {
  21   Pool *pool;
  22   int create;
  23   int aliases;
  24
  25   Queue lookat;         /* conflict candidates */
  26   Queue lookat_dir;     /* not yet conflicting directories */
  27
  28   Hashtable cflmap;
  29   Hashval cflmapn;
  30   unsigned int cflmapused;
  31
  32   Hashtable dirmap;
  33   Hashval dirmapn;
  34   unsigned int dirmapused;
  35   int dirconflicts;
  36
  37   Map idxmap;
  38
  39   unsigned int lastdiridx;      /* last diridx we have seen */
  40   unsigned int lastdirhash;     /* strhash of last dir we have seen */
  41
  42   Id idx;       /* index of package we're looking at */
  43   Id hx;        /* used in findfileconflicts2_cb, limit to files matching hx */
  44
  45   Id dirid;     /* used in findfileconflicts2_cb, limit to dirs matching dirid */
  46   Id dirhash;   /* used in findfileconflicts2_cb, limit to dirs matching dirhash */
  47
  48   Queue files;
  49   unsigned char *filesspace;
  50   unsigned int filesspacen;
  51
  52   Hashtable normap;
  53   Hashval normapn;
  54   unsigned int normapused;
  55   Queue norq;
  56
  57   Hashtable statmap;
  58   Hashval statmapn;
  59   unsigned int statmapused;
  60
  61   int usestat;
  62   int statsmade;
  63
  64   const char *rootdir;
  65   int rootdirl;
  66
  67   char *canonspace;
  68   int canonspacen;
  69 };
  70
  71 #define FILESSPACE_BLOCK 255
  72
  73 static Hashtable
  74 growhash(Hashtable map, Hashval *mapnp)
  75 {
  76   Hashval mapn = *mapnp;
  77   Hashval newn = (mapn + 1) * 2 - 1;
  78   Hashval i, h, hh;
  79   Hashtable m;
  80   Id hx, qx;
  81
  82   m = solv_calloc(newn + 1, 2 * sizeof(Id));
  83   for (i = 0; i <= mapn; i++)
  84     {
  85       hx = map[2 * i];
  86       if (!hx)
  87         continue;
  88       h = hx & newn;
  89       hh = HASHCHAIN_START;
  90       for (;;)
  91         {
  92           qx = m[2 * h];
  93           if (!qx)
  94             break;
  95           h = HASHCHAIN_NEXT(h, hh, newn);
  96         }
  97       m[2 * h] = hx;
  98       m[2 * h + 1] = map[2 * i + 1];
  99     }
 100   solv_free(map);
 101   *mapnp = newn;
 102   return m;
 103 }
 104
 105 static void
 106 finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 107 {
 108   struct cbdata *cbdata = cbdatav;
 109   Hashval h, hh;
 110   Id hx, qx;
 111   Id oidx, idx = cbdata->idx;
 112
 113   hx = strhash(fn);
 114   if (!hx)
 115     hx = strlen(fn) + 1;
 116   h = hx & cbdata->dirmapn;
 117   hh = HASHCHAIN_START;
 118   for (;;)
 119     {
 120       qx = cbdata->dirmap[2 * h];
 121       if (!qx)
 122         break;
 123       if (qx == hx)
 124         break;
 125       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 126     }
 127   if (!qx)
 128     {
 129       /* a miss */
 130       if (!cbdata->create)
 131         return;
 132       cbdata->dirmap[2 * h] = hx;
 133       cbdata->dirmap[2 * h + 1] = idx;
 134       if (++cbdata->dirmapused * 2 > cbdata->dirmapn)
 135         cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
 136       return;
 137     }
 138   oidx = cbdata->dirmap[2 * h + 1];
 139   if (oidx == idx)
 140     return;
 141   /* found a conflict, this dir may be used in multiple packages */
 142   if (oidx != -1)
 143     {
 144       MAPSET(&cbdata->idxmap, oidx);
 145       cbdata->dirmap[2 * h + 1] = -1;
 146       cbdata->dirconflicts++;
 147     }
 148   MAPSET(&cbdata->idxmap, idx);
 149 }
 150
 151 static inline int
 152 isindirmap(struct cbdata *cbdata, Id hx)
 153 {
 154   Hashval h, hh;
 155   Id qx;
 156
 157   h = hx & cbdata->dirmapn;
 158   hh = HASHCHAIN_START;
 159   for (;;)
 160     {
 161       qx = cbdata->dirmap[2 * h];
 162       if (!qx)
 163         return 0;
 164       if (qx == hx)
 165         return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
 166       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 167     }
 168 }
 169
 170 static void
 171 findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 172 {
 173   struct cbdata *cbdata = cbdatav;
 174   int isdir = S_ISDIR(info->mode);
 175   const char *dp;
 176   Id idx, oidx;
 177   Id hx, qx;
 178   Hashval h, hh, dhx;
 179
 180   idx = cbdata->idx;
 181
 182   if (!info->dirlen)
 183     return;
 184   dp = fn + info->dirlen;
 185   if (info->diridx != cbdata->lastdiridx)
 186     {
 187       cbdata->lastdiridx = info->diridx;
 188       cbdata->lastdirhash = strnhash(fn, dp - fn);
 189     }
 190   dhx = cbdata->lastdirhash;
 191   /* this mirrors the "if (!hx) hx = strlen(fn) + 1" in finddirs_cb */
 192   if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
 193     return;
 194   hx = strhash_cont(dp, dhx);
 195   if (!hx)
 196     hx = strlen(fn) + 1;
 197
 198   h = hx & cbdata->cflmapn;
 199   hh = HASHCHAIN_START;
 200   for (;;)
 201     {
 202       qx = cbdata->cflmap[2 * h];
 203       if (!qx)
 204         break;
 205       if (qx == hx)
 206         break;
 207       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 208     }
 209   if (!qx)
 210     {
 211       /* a miss */
 212       if (!cbdata->create)
 213         return;
 214       cbdata->cflmap[2 * h] = hx;
 215       cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
 216       if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
 217         cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
 218       return;
 219     }
 220   oidx = cbdata->cflmap[2 * h + 1];
 221   if (oidx < 0)
 222     {
 223       int i;
 224       if (isdir)
 225         {
 226           /* both are directories. delay the conflict, keep oidx in slot */
 227           queue_push2(&cbdata->lookat_dir, hx, idx);
 228           return;
 229         }
 230       oidx = ~oidx;
 231       /* now have file, had directories before. */
 232       cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
 233       /* dump all delayed directory hits for hx */
 234       for (i = 0; i < cbdata->lookat_dir.count; i += 2)
 235         if (cbdata->lookat_dir.elements[i] == hx)
 236           {
 237             queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
 238             queue_push2(&cbdata->lookat, 0, 0);
 239           }
 240     }
 241   else if (oidx == idx)
 242     return;     /* no conflicts with ourself, please */
 243   queue_push2(&cbdata->lookat, hx, oidx);
 244   queue_push2(&cbdata->lookat, 0, 0);
 245   queue_push2(&cbdata->lookat, hx, idx);
 246   queue_push2(&cbdata->lookat, 0, 0);
 247 }
 248
 249 /* same as findfileconflicts_cb, but
 250  * - hashes with just the basename
 251  * - sets idx in a map instead of pushing to lookat
 252  * - sets the hash element to -1 if there may be a conflict
 253  */
 254 static void
 255 findfileconflicts_basename_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 256 {
 257   struct cbdata *cbdata = cbdatav;
 258   int isdir = S_ISDIR(info->mode);
 259   const char *dp;
 260   Id idx, oidx;
 261   Id hx, qx;
 262   Hashval h, hh;
 263
 264   idx = cbdata->idx;
 265
 266   if (!info->dirlen)
 267     return;
 268   dp = fn + info->dirlen;
 269   hx = strhash(dp);
 270   if (!hx)
 271     hx = strlen(fn) + 1;
 272
 273   h = hx & cbdata->cflmapn;
 274   hh = HASHCHAIN_START;
 275   for (;;)
 276     {
 277       qx = cbdata->cflmap[2 * h];
 278       if (!qx)
 279         break;
 280       if (qx == hx)
 281         break;
 282       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 283     }
 284   if (!qx)
 285     {
 286       /* a miss */
 287       if (!cbdata->create)
 288         return;
 289       cbdata->cflmap[2 * h] = hx;
 290       cbdata->cflmap[2 * h + 1] = (isdir ? -idx - 2 : idx);
 291       if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
 292         cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
 293       return;
 294     }
 295   oidx = cbdata->cflmap[2 * h + 1];
 296   if (oidx < -1)
 297     {
 298       int i;
 299       if (isdir)
 300         {
 301           /* both are directories. delay the conflict, keep oidx in slot */
 302           queue_push2(&cbdata->lookat_dir, hx, idx);
 303           return;
 304         }
 305       oidx = -idx - 2;
 306       /* now have file, had directories before. */
 307       cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
 308       /* dump all delayed directory hits for hx */
 309       for (i = 0; i < cbdata->lookat_dir.count; i += 2)
 310         if (cbdata->lookat_dir.elements[i] == hx)
 311           MAPSET(&cbdata->idxmap, cbdata->lookat_dir.elements[i + 1]);
 312     }
 313   else if (oidx == idx)
 314     return;     /* no conflicts with ourself, please */
 315   if (oidx >= 0)
 316     MAPSET(&cbdata->idxmap, oidx);
 317   MAPSET(&cbdata->idxmap, idx);
 318   if (oidx != -1)
 319     cbdata->cflmap[2 * h + 1] = -1;
 320 }
 321
 322 static inline Id
 323 addfilesspace(struct cbdata *cbdata, int len)
 324 {
 325   unsigned int off = cbdata->filesspacen;
 326   cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
 327   cbdata->filesspacen += len;
 328   return off;
 329 }
 330
 331 static Id
 332 unifywithstat(struct cbdata *cbdata, Id diroff, int dirl)
 333 {
 334   struct stat stb;
 335   int i;
 336   Hashval h, hh;
 337   Id hx, qx;
 338   Id nspaceoff;
 339   unsigned char statdata[16 + sizeof(stb.st_dev) + sizeof(stb.st_ino)];
 340
 341   if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == '/')
 342     cbdata->filesspace[diroff + dirl - 1] = 0;
 343   cbdata->statsmade++;
 344   i = stat((char *)cbdata->filesspace + diroff, &stb);
 345   if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == 0)
 346     cbdata->filesspace[diroff + dirl - 1] = '/';
 347   if (i)
 348     return diroff;
 349   memset(statdata, 0, 16);
 350   memcpy(statdata + 8, &stb.st_dev, sizeof(stb.st_dev));
 351   memcpy(statdata, &stb.st_ino, sizeof(stb.st_ino));
 352   hx = 0;
 353   for (i = 15; i >= 0; i--)
 354     hx = (unsigned int)hx * 13 + statdata[i];
 355   h = hx & cbdata->statmapn;
 356   hh = HASHCHAIN_START;
 357   for (;;)
 358     {
 359       qx = cbdata->statmap[2 * h];
 360       if (!qx)
 361         break;
 362       if (qx == hx)
 363         {
 364           Id off = cbdata->statmap[2 * h + 1];
 365           char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
 366           if (!memcmp(dp, statdata, 16))
 367             return cbdata->norq.elements[off + 1];
 368         }
 369       h = HASHCHAIN_NEXT(h, hh, cbdata->statmapn);
 370     }
 371   /* new stat result. work. */
 372   nspaceoff = addfilesspace(cbdata, 16);
 373   memcpy(cbdata->filesspace + nspaceoff, statdata, 16);
 374   queue_push2(&cbdata->norq, nspaceoff, nspaceoff);
 375   cbdata->statmap[2 * h] = hx;
 376   cbdata->statmap[2 * h + 1] = cbdata->norq.count - 2;
 377   if (++cbdata->statmapused * 2 > cbdata->statmapn)
 378     cbdata->statmap = growhash(cbdata->statmap, &cbdata->statmapn);
 379   return nspaceoff;
 380 }
 381
 382 /* forward declaration */
 383 static Id normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create);
 384
 385 static Id
 386 unifywithcanon(struct cbdata *cbdata, Id diroff, int dirl)
 387 {
 388   Id dirnameid;
 389   int i, l, ll, lo;
 390   struct stat stb;
 391
 392 #if 0
 393   printf("UNIFY %.*s\n", dirl, (char *)cbdata->filesspace + diroff);
 394 #endif
 395   if (!dirl || cbdata->filesspace[diroff] != '/')
 396     return diroff;
 397   /* strip / at end*/
 398   while (dirl && cbdata->filesspace[diroff + dirl - 1] == '/')
 399     dirl--;
 400   if (!dirl)
 401     return diroff;
 402   /* find dirname */
 403   for (i = dirl - 1; i > 0; i--)
 404     if (cbdata->filesspace[diroff + i] == '/')
 405       break;
 406   i++;                          /* include trailing / */
 407
 408   /* normalize dirname */
 409   dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, i, strnhash((char *)cbdata->filesspace + diroff, i), 1);
 410   if (dirnameid == -1)
 411     return diroff;              /* hit "in progress" marker, some cyclic link */
 412
 413   /* sanity check result */
 414   if (cbdata->filesspace[dirnameid] != '/')
 415     return diroff;              /* hmm */
 416   l = strlen((char *)cbdata->filesspace + dirnameid);
 417   if (l && cbdata->filesspace[dirnameid + l - 1] != '/')
 418     return diroff;              /* hmm */
 419
 420   /* special handling for "." and ".." basename */
 421   if (cbdata->filesspace[diroff + i] == '.')
 422     {
 423       if (dirl - i == 1)
 424         return dirnameid;
 425       if (dirl - i == 2 && cbdata->filesspace[diroff + i + 1] == '.')
 426         {
 427           if (l <= 2)
 428             return dirnameid;   /* we hit our root */
 429           for (i = l - 2; i > 0; i--)
 430             if (cbdata->filesspace[dirnameid + i] == '/')
 431               break;
 432           i++;  /* include trailing / */
 433           dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + dirnameid, i, strnhash((char *)cbdata->filesspace + dirnameid, i), 1);
 434           return dirnameid == -1 ? diroff : dirnameid;
 435         }
 436     }
 437
 438   /* append basename to normalized dirname */
 439   if (cbdata->rootdirl + l + dirl - i + 1 > cbdata->canonspacen)
 440     {
 441       cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + 20;
 442       cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
 443       strcpy(cbdata->canonspace, cbdata->rootdir);
 444     }
 445   strcpy(cbdata->canonspace + cbdata->rootdirl, (char *)cbdata->filesspace + dirnameid);
 446   strncpy(cbdata->canonspace + cbdata->rootdirl + l, (char *)cbdata->filesspace + diroff + i, dirl - i);
 447   cbdata->canonspace[cbdata->rootdirl + l + dirl - i] = 0;
 448
 449 #if 0
 450   printf("stat()ing %s\n", cbdata->canonspace);
 451 #endif
 452   cbdata->statsmade++;
 453   if (lstat(cbdata->canonspace, &stb))
 454     return diroff;              /* hmm */
 455   if (!S_ISLNK(stb.st_mode))
 456     {
 457       /* not a symlink, have new canon entry */
 458       diroff = addfilesspace(cbdata, l + dirl - i + 2);
 459       strcpy((char *)cbdata->filesspace + diroff, cbdata->canonspace + cbdata->rootdirl);
 460       l += dirl - i;
 461       /* add trailing / */
 462       if (cbdata->filesspace[diroff + l - 1] != '/')
 463         {
 464           cbdata->filesspace[diroff + l++] = '/';
 465           cbdata->filesspace[diroff + l] = 0;
 466         }
 467       /* call normalizedir on new entry for unification purposes */
 468       dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, l, strnhash((char *)cbdata->filesspace + diroff, l), 1);
 469       return dirnameid == -1 ? diroff : dirnameid;
 470     }
 471   /* oh no, a symlink! follow */
 472   lo = cbdata->rootdirl + l + dirl - i + 1;
 473   if (lo + stb.st_size + 2 > cbdata->canonspacen)
 474     {
 475       cbdata->canonspacen = lo + stb.st_size + 20;
 476       cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
 477     }
 478   ll = readlink(cbdata->canonspace, cbdata->canonspace + lo, stb.st_size);
 479   if (ll < 0 || ll > stb.st_size)
 480     return diroff;              /* hmm */
 481   if (ll == 0)
 482     return dirnameid;           /* empty means current dir */
 483   if (cbdata->canonspace[lo + ll - 1] != '/')
 484     cbdata->canonspace[lo + ll++] = '/';        /* add trailing / */
 485   cbdata->canonspace[lo + ll] = 0;              /* zero terminate */
 486   if (cbdata->canonspace[lo] != '/')
 487     {
 488       /* relative link, concatenate to dirname */
 489       memmove(cbdata->canonspace + cbdata->rootdirl + l, cbdata->canonspace + lo, ll + 1);
 490       lo = cbdata->rootdirl;
 491       ll += l;
 492     }
 493   dirnameid = normalizedir(cbdata, cbdata->canonspace + lo, ll, strnhash(cbdata->canonspace + lo, ll), 1);
 494   return dirnameid == -1 ? diroff : dirnameid;
 495 }
 496
 497 /*
 498  * map a directory (containing a trailing /) into a number.
 499  * for unifywithstat this is the offset to the 16 byte stat result.
 500  * for unifywithcanon this is the offset to the normailzed dir.
 501  */
 502 static Id
 503 normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create)
 504 {
 505   Hashval h, hh;
 506   Id qx;
 507   Id nspaceoff;
 508   int mycnt;
 509
 510   if (!hx)
 511     hx = dirl + 1;
 512   h = hx & cbdata->normapn;
 513   hh = HASHCHAIN_START;
 514   for (;;)
 515     {
 516       qx = cbdata->normap[2 * h];
 517       if (!qx)
 518         break;
 519       if (qx == hx)
 520         {
 521           Id off = cbdata->normap[2 * h + 1];
 522           char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
 523           if (!strncmp(dp, dir, dirl) && dp[dirl] == 0)
 524             return cbdata->norq.elements[off + 1];
 525         }
 526       h = HASHCHAIN_NEXT(h, hh, cbdata->normapn);
 527     }
 528   if (!create)
 529     return 0;
 530   /* new dir. work. */
 531   if (dir >= (const char *)cbdata->filesspace && dir < (const char *)cbdata->filesspace + cbdata->filesspacen)
 532     {
 533       /* can happen when called from unifywithcanon */
 534       Id off = dir - (const char *)cbdata->filesspace;
 535       nspaceoff = addfilesspace(cbdata, dirl + 1);
 536       dir = (const char *)cbdata->filesspace + off;
 537     }
 538   else
 539     nspaceoff = addfilesspace(cbdata, dirl + 1);
 540   if (dirl)
 541     memcpy(cbdata->filesspace + nspaceoff, dir, dirl);
 542   cbdata->filesspace[nspaceoff + dirl] = 0;
 543   mycnt = cbdata->norq.count;
 544   queue_push2(&cbdata->norq, nspaceoff, -1);    /* -1: in progress */
 545   cbdata->normap[2 * h] = hx;
 546   cbdata->normap[2 * h + 1] = mycnt;
 547   if (++cbdata->normapused * 2 > cbdata->normapn)
 548     cbdata->normap = growhash(cbdata->normap, &cbdata->normapn);
 549   /* unify */
 550   if (cbdata->usestat)
 551     nspaceoff = unifywithstat(cbdata, nspaceoff, dirl);
 552   else
 553     nspaceoff = unifywithcanon(cbdata, nspaceoff, dirl);
 554   cbdata->norq.elements[mycnt + 1] = nspaceoff; /* patch in result */
 555 #if 0
 556   if (!cbdata->usestat)
 557     printf("%s normalized to %d: %s\n", cbdata->filesspace + cbdata->norq.elements[mycnt], nspaceoff, cbdata->filesspace + nspaceoff);
 558 #endif
 559   return nspaceoff;
 560 }
 561
 562 static void
 563 findfileconflicts_alias_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 564 {
 565   int isdir = S_ISDIR(info->mode);
 566   struct cbdata *cbdata = cbdatav;
 567   const char *dp;
 568   Id idx, dirid;
 569   Id hx, qx;
 570   Hashval h, hh;
 571
 572   idx = cbdata->idx;
 573
 574   if (!info->dirlen)
 575     return;
 576   dp = fn + info->dirlen;
 577   if (info->diridx != cbdata->lastdiridx)
 578     {
 579       cbdata->lastdiridx = info->diridx;
 580       cbdata->lastdirhash = 0;
 581     }
 582   dp = fn + info->dirlen;
 583   hx = strhash(dp);
 584   if (!hx)
 585     hx = strlen(fn) + 1;
 586
 587   h = hx & cbdata->cflmapn;
 588   hh = HASHCHAIN_START;
 589   for (;;)
 590     {
 591       qx = cbdata->cflmap[2 * h];
 592       if (!qx)
 593         break;
 594       if (qx == hx)
 595         break;
 596       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 597     }
 598   if (!qx || cbdata->cflmap[2 * h + 1] != -1)
 599     return;
 600   if (!cbdata->lastdirhash)
 601     cbdata->lastdirhash = strnhash(fn, dp - fn);
 602   dirid = normalizedir(cbdata, fn, dp - fn, cbdata->lastdirhash, 1);
 603   queue_push2(&cbdata->lookat, hx, idx);
 604   queue_push2(&cbdata->lookat, cbdata->lastdirhash, isdir ? -dirid : dirid);
 605 }
 606
 607 static void
 608 findfileconflicts2_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 609 {
 610   struct cbdata *cbdata = cbdatav;
 611   Hashval hx;
 612   const char *dp;
 613   char md5padded[34];
 614   Id off;
 615
 616   if (!info->dirlen)
 617     return;
 618   dp = fn + info->dirlen;
 619   if (info->diridx != cbdata->lastdiridx)
 620     {
 621       cbdata->lastdiridx = info->diridx;
 622       cbdata->lastdirhash = strnhash(fn, dp - fn);
 623     }
 624   if (cbdata->aliases)
 625     {
 626       if (cbdata->lastdirhash != cbdata->dirhash)
 627         return;
 628       hx = strhash(dp);
 629     }
 630   else
 631     {
 632       hx = cbdata->lastdirhash;
 633       hx = strhash_cont(dp, hx);
 634     }
 635   if (!hx)
 636     hx = strlen(fn) + 1;
 637   if ((Id)hx != cbdata->hx)
 638     return;
 639   if (cbdata->dirid && cbdata->dirid != normalizedir(cbdata, fn, dp - fn, cbdata->dirhash, 0))
 640     return;
 641   strncpy(md5padded, info->digest, 32);
 642   md5padded[32] = 0;
 643   md5padded[33] = info->color;
 644   /* printf("%d, hx %x -> %s   %d %s\n", cbdata->idx, hx, fn, info->mode, info->digest); */
 645   off = addfilesspace(cbdata, strlen(fn) + (34 + 1));
 646   memcpy(cbdata->filesspace + off, (unsigned char *)md5padded, 34);
 647   strcpy((char *)cbdata->filesspace + off + 34, fn);
 648   queue_push(&cbdata->files, off);
 649 }
 650
 651 static int
 652 lookat_idx_cmp(const void *ap, const void *bp, void *dp)
 653 {
 654   const Id *a = ap, *b = bp;
 655   unsigned int ahx, bhx;
 656   if (a[1] - b[1] != 0)         /* idx */
 657     return a[1] - b[1];
 658   if (a[3] - b[3] != 0)         /* dirid */
 659     return a[3] - b[3];
 660   ahx = (unsigned int)a[0];     /* can be < 0 */
 661   bhx = (unsigned int)b[0];
 662   if (ahx != bhx)
 663     return ahx < bhx ? -1 : 1;
 664   ahx = (unsigned int)a[2];     /* dhx */
 665   bhx = (unsigned int)b[2];
 666   if (ahx != bhx)
 667     return ahx < bhx ? -1 : 1;
 668   return 0;
 669 }
 670
 671 static int
 672 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
 673 {
 674   const Id *a = ap, *b = bp;
 675   unsigned int ahx, bhx;
 676   Id adirid, bdirid;
 677   ahx = (unsigned int)a[0];     /* can be < 0 */
 678   bhx = (unsigned int)b[0];
 679   if (ahx != bhx)
 680     return ahx < bhx ? -1 : 1;
 681   adirid = a[3] < 0 ? -a[3] : a[3];
 682   bdirid = b[3] < 0 ? -b[3] : b[3];
 683   if (adirid - bdirid != 0)     /* dirid */
 684     return adirid - bdirid;
 685   if (a[3] != b[3])
 686     return a[3] > 0 ? -1 : 1;   /* bring positive dirids to front */
 687   if (a[1] - b[1] != 0)         /* idx */
 688     return a[1] - b[1];
 689   ahx = (unsigned int)a[2];     /* dhx */
 690   bhx = (unsigned int)b[2];
 691   if (ahx != bhx)
 692     return ahx < bhx ? -1 : 1;
 693   return 0;
 694 }
 695
 696 static int
 697 conflicts_cmp(const void *ap, const void *bp, void *dp)
 698 {
 699   Pool *pool = dp;
 700   const Id *a = ap;
 701   const Id *b = bp;
 702   if (a[0] != b[0])     /* filename1 */
 703     return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
 704   if (a[3] != b[3])     /* filename2 */
 705     return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
 706   if (a[1] != b[1])     /* pkgid1 */
 707     return a[1] - b[1];
 708   if (a[4] != b[4])     /* pkgid2 */
 709     return a[4] - b[4];
 710   return 0;
 711 }
 712
 713 static void
 714 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
 715 {
 716   Repodata *lastdata = 0;
 717   Id lastdirid = -1;
 718   Dataiterator di;
 719
 720   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 721   while (dataiterator_step(&di))
 722     {
 723       if (di.data == lastdata && di.kv.id == lastdirid)
 724         continue;
 725       lastdata = di.data;
 726       lastdirid = di.kv.id;
 727       cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
 728     }
 729   dataiterator_free(&di);
 730 }
 731
 732 /* before calling the expensive findfileconflicts_basename_cb we check if any of
 733  * the basenames match. This only makes sense when cbdata->create is off.
 734  */
 735 static int
 736 precheck_solvable_files(struct cbdata *cbdata, Pool *pool, Id p)
 737 {
 738   Dataiterator di;
 739   Id hx, qx;
 740   Hashval h, hh;
 741   int found = 0;
 742
 743   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 744   while (dataiterator_step(&di))
 745     {
 746       hx = strhash(di.kv.str);
 747       if (!hx)
 748         hx = strlen(di.kv.str) + 1;
 749       h = hx & cbdata->cflmapn;
 750       hh = HASHCHAIN_START;
 751       for (;;)
 752         {
 753           qx = cbdata->cflmap[2 * h];
 754           if (!qx)
 755             break;
 756           if (qx == hx)
 757             {
 758               found = 1;
 759               break;
 760             }
 761           h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 762         }
 763       if (found)
 764         break;
 765     }
 766   dataiterator_free(&di);
 767   return found;
 768 }
 769
 770
 771 int
 772 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
 773 {
 774   int i, j, cflmapn, idxmapset;
 775   struct cbdata cbdata;
 776   unsigned int now, start;
 777   void *handle;
 778   Repo *installed = pool->installed;
 779   Id p;
 780   int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
 781
 782   queue_empty(conflicts);
 783   if (!pkgs->count)
 784     return 0;
 785
 786   now = start = solv_timems(0);
 787   POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
 788   POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
 789
 790   memset(&cbdata, 0, sizeof(cbdata));
 791   cbdata.aliases = flags & FINDFILECONFLICTS_CHECK_DIRALIASING;
 792   cbdata.pool = pool;
 793   if (cbdata.aliases && (flags & FINDFILECONFLICTS_USE_ROOTDIR) != 0)
 794     {
 795       cbdata.rootdir = pool_get_rootdir(pool);
 796       if (cbdata.rootdir && !strcmp(cbdata.rootdir, "/"))
 797         cbdata.rootdir = 0;
 798       if (cbdata.rootdir)
 799         cbdata.rootdirl = strlen(cbdata.rootdir);
 800       if (!cbdata.rootdir)
 801         cbdata.usestat = 1;
 802     }
 803   queue_init(&cbdata.lookat);
 804   queue_init(&cbdata.lookat_dir);
 805   map_init(&cbdata.idxmap, pkgs->count);
 806
 807   if (cutoff <= 0)
 808     cutoff = pkgs->count;
 809
 810   /* avarage file list size: 200 files per package */
 811   /* avarage dir count: 20 dirs per package */
 812
 813   /* first pass: scan dirs */
 814   if (!cbdata.aliases)
 815     {
 816       cflmapn = (cutoff + 3) * 64;
 817       while ((cflmapn & (cflmapn - 1)) != 0)
 818         cflmapn = cflmapn & (cflmapn - 1);
 819       cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 820       cbdata.dirmapn = cflmapn - 1;     /* make it a mask */
 821       cbdata.create = 1;
 822       idxmapset = 0;
 823       for (i = 0; i < pkgs->count; i++)
 824         {
 825           p = pkgs->elements[i];
 826           cbdata.idx = i;
 827           if (i == cutoff)
 828             cbdata.create = 0;
 829           if ((flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
 830             {
 831               if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 832                 {
 833                   iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
 834                   if (MAPTST(&cbdata.idxmap, i))
 835                     idxmapset++;
 836                   continue;
 837                 }
 838             }
 839           handle = (*handle_cb)(pool, p, handle_cbdata);
 840           if (!handle)
 841             continue;
 842           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 843           if (MAPTST(&cbdata.idxmap, i))
 844             idxmapset++;
 845         }
 846       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
 847       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 848       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
 849       POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
 850     }
 851
 852   /* second pass: scan files */
 853   now = solv_timems(0);
 854   cflmapn = (cutoff + 3) * 128;
 855   while ((cflmapn & (cflmapn - 1)) != 0)
 856     cflmapn = cflmapn & (cflmapn - 1);
 857   cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 858   cbdata.cflmapn = cflmapn - 1; /* make it a mask */
 859   cbdata.create = 1;
 860   for (i = 0; i < pkgs->count; i++)
 861     {
 862       if (!cbdata.aliases && !MAPTST(&cbdata.idxmap, i))
 863         continue;
 864       p = pkgs->elements[i];
 865       cbdata.idx = i;
 866       if (i == cutoff)
 867         cbdata.create = 0;
 868       if (cbdata.aliases && !cbdata.create && FINDFILECONFLICTS_USE_SOLVABLEFILELIST)
 869         {
 870           if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 871             if (!precheck_solvable_files(&cbdata, pool, p))
 872               continue;
 873         }
 874       /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
 875        * the file is a directory or not */
 876       handle = (*handle_cb)(pool, p, handle_cbdata);
 877       if (!handle)
 878         continue;
 879       cbdata.lastdiridx = -1;
 880       rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, cbdata.aliases ? findfileconflicts_basename_cb : findfileconflicts_cb, &cbdata);
 881     }
 882
 883   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
 884   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 885   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
 886   POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
 887   queue_free(&cbdata.lookat_dir);
 888
 889   /* we need another pass for aliases */
 890   if (cbdata.aliases)
 891     {
 892       now = solv_timems(0);
 893       /* make sure the first offset is not zero */
 894       addfilesspace(&cbdata, 1);
 895       cflmapn = (cutoff + 3) * 16;
 896       while ((cflmapn & (cflmapn - 1)) != 0)
 897         cflmapn = cflmapn & (cflmapn - 1);
 898       cbdata.normap = solv_calloc(cflmapn, 2 * sizeof(Id));
 899       cbdata.normapn = cflmapn - 1;     /* make it a mask */
 900       if (cbdata.usestat)
 901         {
 902           cbdata.statmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 903           cbdata.statmapn = cflmapn - 1;        /* make it a mask */
 904         }
 905       cbdata.create = 0;
 906       for (i = 0; i < pkgs->count; i++)
 907         {
 908           if (!MAPTST(&cbdata.idxmap, i))
 909             continue;
 910           p = pkgs->elements[i];
 911           cbdata.idx = i;
 912           /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
 913            * the file is a directory or not */
 914           handle = (*handle_cb)(pool, p, handle_cbdata);
 915           if (!handle)
 916             continue;
 917           cbdata.lastdiridx = -1;
 918           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_alias_cb, &cbdata);
 919         }
 920       POOL_DEBUG(SOLV_DEBUG_STATS, "normap size: %d, used %d\n", cbdata.normapn + 1, cbdata.normapused);
 921       POOL_DEBUG(SOLV_DEBUG_STATS, "normap memory usage: %d K\n", (cbdata.normapn + 1) * 2 * (int)sizeof(Id) / 1024);
 922       POOL_DEBUG(SOLV_DEBUG_STATS, "stats made: %d\n", cbdata.statsmade);
 923       if (cbdata.usestat)
 924         {
 925           POOL_DEBUG(SOLV_DEBUG_STATS, "statmap size: %d, used %d\n", cbdata.statmapn + 1, cbdata.statmapused);
 926           POOL_DEBUG(SOLV_DEBUG_STATS, "statmap memory usage: %d K\n", (cbdata.statmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 927         }
 928       cbdata.statmap = solv_free(cbdata.statmap);
 929       cbdata.statmapn = 0;
 930       cbdata.canonspace = solv_free(cbdata.canonspace);
 931       cbdata.canonspacen = 0;
 932       POOL_DEBUG(SOLV_DEBUG_STATS, "alias processing took %d ms\n", solv_timems(now));
 933     }
 934
 935   cbdata.dirmap = solv_free(cbdata.dirmap);
 936   cbdata.dirmapn = 0;
 937   cbdata.dirmapused = 0;
 938   cbdata.cflmap = solv_free(cbdata.cflmap);
 939   cbdata.cflmapn = 0;
 940   cbdata.cflmapused = 0;
 941
 942   now = solv_timems(0);
 943
 944   map_free(&cbdata.idxmap);
 945
 946   /* sort and unify/prune */
 947   POOL_DEBUG(SOLV_DEBUG_STATS, "raw candidates: %d, pruning\n", cbdata.lookat.count / 4);
 948   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
 949   for (i = j = 0; i < cbdata.lookat.count; )
 950     {
 951       int first = 1;
 952       Id hx = cbdata.lookat.elements[i];
 953       Id idx = cbdata.lookat.elements[i + 1];
 954       Id dhx = cbdata.lookat.elements[i + 2];
 955       Id dirid = cbdata.lookat.elements[i + 3];
 956       i += 4;
 957       for (; i < cbdata.lookat.count && hx == cbdata.lookat.elements[i] && (dirid == cbdata.lookat.elements[i + 3] || dirid == -cbdata.lookat.elements[i + 3]); i += 4)
 958         {
 959           if (idx == cbdata.lookat.elements[i + 1] && dhx == cbdata.lookat.elements[i + 2])
 960             continue;   /* ignore duplicates */
 961           if (first)
 962             {
 963               if (dirid < 0)
 964                 continue;       /* all have a neg dirid */
 965               cbdata.lookat.elements[j++] = hx;
 966               cbdata.lookat.elements[j++] = idx;
 967               cbdata.lookat.elements[j++] = dhx;
 968               cbdata.lookat.elements[j++] = dirid;
 969               first = 0;
 970             }
 971           idx = cbdata.lookat.elements[i + 1];
 972           dhx = cbdata.lookat.elements[i + 2];
 973           cbdata.lookat.elements[j++] = hx;
 974           cbdata.lookat.elements[j++] = idx;
 975           cbdata.lookat.elements[j++] = dhx;
 976           cbdata.lookat.elements[j++] = dirid;
 977         }
 978     }
 979   queue_truncate(&cbdata.lookat, j);
 980   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates now: %d\n", cbdata.lookat.count / 4);
 981
 982   /* third pass: collect file info for all files that match a hx */
 983   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_idx_cmp, pool);
 984   queue_init(&cbdata.files);
 985   for (i = 0; i < cbdata.lookat.count; i += 4)
 986     {
 987       Id idx = cbdata.lookat.elements[i + 1];
 988       int iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
 989       if (obsoleteusescolors)
 990         iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
 991       p = pkgs->elements[idx];
 992       handle = (*handle_cb)(pool, p, handle_cbdata);
 993       for (;; i += 4)
 994         {
 995           int fstart = cbdata.files.count;
 996           queue_push(&cbdata.files, idx);
 997           queue_push(&cbdata.files, 0);
 998           cbdata.idx = idx;
 999           cbdata.hx = cbdata.lookat.elements[i];
1000           cbdata.dirhash = cbdata.lookat.elements[i + 2];
1001           cbdata.dirid = cbdata.lookat.elements[i + 3];
1002           cbdata.lastdiridx = -1;
1003           if (handle)
1004             rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
1005           cbdata.files.elements[fstart + 1] = cbdata.files.count;
1006           cbdata.lookat.elements[i + 1] = fstart;
1007           if (i + 4 >= cbdata.lookat.count || cbdata.lookat.elements[i + 4 + 1] != idx)
1008             break;
1009         }
1010     }
1011
1012   cbdata.normap = solv_free(cbdata.normap);
1013   cbdata.normapn = 0;
1014
1015   /* forth pass: for each hx we have, compare all matching files against all other matching files */
1016   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
1017   for (i = 0; i < cbdata.lookat.count - 4; i += 4)
1018     {
1019       Id hx = cbdata.lookat.elements[i];
1020       Id pstart = cbdata.lookat.elements[i + 1];
1021       Id dirid = cbdata.lookat.elements[i + 3];
1022       Id pidx = cbdata.files.elements[pstart];
1023       Id pend = cbdata.files.elements[pstart + 1];
1024       if (cbdata.lookat.elements[i + 4] != hx)
1025         continue;       /* no package left with that hx */
1026       for (j = i + 4; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx && cbdata.lookat.elements[j + 3] == dirid; j += 4)
1027         {
1028           Id qstart = cbdata.lookat.elements[j + 1];
1029           Id qidx = cbdata.files.elements[qstart];
1030           Id qend = cbdata.files.elements[qstart + 1];
1031           int ii, jj;
1032           if (pidx >= cutoff && qidx >= cutoff)
1033             continue;   /* no conflicts between packages with idx >= cutoff */
1034           for (ii = pstart + 2; ii < pend; ii++)
1035             for (jj = qstart + 2; jj < qend; jj++)
1036               {
1037                 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
1038                 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
1039                 if (cbdata.aliases)
1040                   {
1041                     /* compare just the basenames, the dirs match */
1042                     char *bsi = strrchr(fsi + 34, '/');
1043                     char *bsj = strrchr(fsj + 34, '/');
1044                     if ((!bsi || !bsj) && bsi != bsj)
1045                       continue;
1046                     if (strcmp(bsi, bsj))
1047                       continue; /* different file names */
1048                   }
1049                 else
1050                   {
1051                     if (strcmp(fsi + 34, fsj + 34))
1052                       continue; /* different file names */
1053                   }
1054                 if (!strcmp(fsi, fsj))
1055                   continue;     /* md5 sum matches */
1056                 if (obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
1057                   continue;     /* colors do not conflict */
1058                 queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
1059                 queue_push(conflicts, pkgs->elements[pidx]);
1060                 queue_push(conflicts, pool_str2id(pool, fsi, 1));
1061                 queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
1062                 queue_push(conflicts, pkgs->elements[qidx]);
1063                 queue_push(conflicts, pool_str2id(pool, fsj, 1));
1064               }
1065         }
1066     }
1067   POOL_DEBUG(SOLV_DEBUG_STATS, "filespace size: %d K\n", cbdata.filesspacen / 1024);
1068   POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
1069   cbdata.filesspace = solv_free(cbdata.filesspace);
1070   cbdata.filesspacen = 0;
1071   queue_free(&cbdata.lookat);
1072   queue_free(&cbdata.files);
1073   if (conflicts->count > 6)
1074     solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
1075   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
1076   POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
1077
1078   return conflicts->count;
1079 }
1080