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           const char *dp = (const char *)cbdata->filesspace + cbdata->norq.elements[off];
 366           if (!memcmp(dp, (const char *)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   dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, i, strnhash((char *)cbdata->filesspace + diroff, i), 1);
 408   if (dirnameid == -1)
 409     return diroff;              /* some cyclic link */
 410   if (cbdata->filesspace[dirnameid] != '/')
 411     return diroff;              /* hmm */
 412   l = strlen((char *)cbdata->filesspace + dirnameid);
 413   if (l && cbdata->filesspace[dirnameid + l - 1] != '/')
 414     return diroff;
 415   /* special handling for '.', '..', '' */
 416   if (cbdata->filesspace[diroff + i] == '.')
 417     {
 418       if (dirl - i == 1)
 419         return dirnameid;
 420       if (dirl - i == 2 && cbdata->filesspace[diroff + i + 1] == '.')
 421         {
 422           dirl = strlen((char *)cbdata->filesspace + dirnameid);
 423           if (dirl <= 2)
 424             return dirnameid;
 425           for (i = dirl - 2; i > 0; i--)
 426             if (cbdata->filesspace[diroff + i] == '/')
 427               break;
 428           dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + dirnameid, i + 1, strnhash((char *)cbdata->filesspace + dirnameid, i + 1), 1);
 429           return dirnameid == -1 ? diroff : dirnameid;
 430         }
 431     }
 432   if (cbdata->rootdirl + l + dirl - i + 1 > cbdata->canonspacen)
 433     {
 434       cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + 20;
 435       cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
 436       strcpy(cbdata->canonspace, cbdata->rootdir);
 437     }
 438   strcpy(cbdata->canonspace + cbdata->rootdirl, (char *)cbdata->filesspace + dirnameid);
 439   strncpy(cbdata->canonspace + cbdata->rootdirl + l, (char *)cbdata->filesspace + diroff + i, dirl - i);
 440   cbdata->canonspace[cbdata->rootdirl + l + dirl - i] = 0;
 441   cbdata->statsmade++;
 442 #if 0
 443   printf("stat()ing %s\n", cbdata->canonspace);
 444 #endif
 445   if (lstat(cbdata->canonspace, &stb))
 446     return diroff;              /* hmm */
 447   if (!S_ISLNK(stb.st_mode))
 448     {
 449       /* not a symlink, have canon entry */
 450       diroff = addfilesspace(cbdata, l + dirl - i + 2);
 451       strcpy((char *)cbdata->filesspace + diroff, cbdata->canonspace + cbdata->rootdirl);
 452       l += dirl - i;
 453       /* add trailing / */
 454       if (cbdata->filesspace[diroff + l - 1] != '/')
 455         {
 456           cbdata->filesspace[diroff + l++] = '/';
 457           cbdata->filesspace[diroff + l] = 0;
 458         }
 459       dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, l, strnhash((char *)cbdata->filesspace + diroff, l), 1);
 460       return dirnameid == -1 ? diroff : dirnameid;
 461     }
 462   /* oh no, a symlink! follow */
 463   if (cbdata->rootdirl + l + dirl - i + stb.st_size + 2 > cbdata->canonspacen)
 464     {
 465       cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + stb.st_size + 20;
 466       cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
 467     }
 468   lo = cbdata->rootdirl + l + dirl - i + 1;
 469   ll = readlink(cbdata->canonspace, cbdata->canonspace + lo, stb.st_size);
 470   if (ll < 0 || ll > stb.st_size)
 471     return diroff;              /* hmm */
 472   if (ll == 0)
 473     return dirnameid;
 474   if (cbdata->canonspace[lo + ll - 1] != '/')
 475     cbdata->canonspace[lo + ll++] = '/';        /* add trailing / */
 476   cbdata->canonspace[lo + ll] = 0;
 477   if (cbdata->canonspace[lo] != '/')
 478     {
 479       /* relative link, concatenate */
 480       memmove(cbdata->canonspace + cbdata->rootdirl + l, cbdata->canonspace + lo, ll + 1);
 481       lo = cbdata->rootdirl;
 482       ll += l;
 483     }
 484   dirnameid = normalizedir(cbdata, (char *)cbdata->canonspace + lo, ll, strnhash((char *)cbdata->canonspace + lo, ll), 1);
 485   return dirnameid == -1 ? diroff : dirnameid;
 486 }
 487
 488 /*
 489  * map a directory (containing a trailing /) into a number.
 490  * for unifywithstat this is the offset to the 16 byte stat result.
 491  * for unifywithcanon this is the offset to the normailzed dir.
 492  */
 493 static Id
 494 normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create)
 495 {
 496   Hashval h, hh;
 497   Id qx;
 498   Id nspaceoff;
 499   int mycnt;
 500
 501   if (!hx)
 502     hx = dirl + 1;
 503   h = hx & cbdata->normapn;
 504   hh = HASHCHAIN_START;
 505   for (;;)
 506     {
 507       qx = cbdata->normap[2 * h];
 508       if (!qx)
 509         break;
 510       if (qx == hx)
 511         {
 512           Id off = cbdata->normap[2 * h + 1];
 513           const char *dp = (const char *)cbdata->filesspace + cbdata->norq.elements[off];
 514           if (!strncmp(dp, dir, dirl) && dp[dirl] == 0)
 515             return cbdata->norq.elements[off + 1];
 516         }
 517       h = HASHCHAIN_NEXT(h, hh, cbdata->normapn);
 518     }
 519   if (!create)
 520     return 0;
 521   /* new dir. work. */
 522   if (dir >= (const char *)cbdata->filesspace && dir < (const char *)cbdata->filesspace + cbdata->filesspacen)
 523     {
 524       /* can happen when called from unifywithcanon */
 525       Id off = dir - (const char *)cbdata->filesspace;
 526       nspaceoff = addfilesspace(cbdata, dirl + 1);
 527       dir = (const char *)cbdata->filesspace + off;
 528     }
 529   else
 530     nspaceoff = addfilesspace(cbdata, dirl + 1);
 531   if (dirl)
 532     memcpy(cbdata->filesspace + nspaceoff, dir, dirl);
 533   cbdata->filesspace[nspaceoff + dirl] = 0;
 534   mycnt = cbdata->norq.count;
 535   queue_push2(&cbdata->norq, nspaceoff, -1);
 536   cbdata->normap[2 * h] = hx;
 537   cbdata->normap[2 * h + 1] = cbdata->norq.count - 2;
 538   /* unify */
 539   if (cbdata->usestat)
 540     nspaceoff = unifywithstat(cbdata, nspaceoff, dirl);
 541   else
 542     nspaceoff = unifywithcanon(cbdata, nspaceoff, dirl);
 543   /* update */
 544   cbdata->norq.elements[mycnt + 1] = nspaceoff;
 545 #if 0
 546   if (!cbdata->usestat)
 547     printf("%s normalized to %d: %s\n", cbdata->filesspace + cbdata->norq.elements[mycnt], nspaceoff, cbdata->filesspace + nspaceoff);
 548 #endif
 549   if (++cbdata->normapused * 2 > cbdata->normapn)
 550     cbdata->normap = growhash(cbdata->normap, &cbdata->normapn);
 551   return nspaceoff;
 552 }
 553
 554 static void
 555 findfileconflicts_alias_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 556 {
 557   int isdir = S_ISDIR(info->mode);
 558   struct cbdata *cbdata = cbdatav;
 559   const char *dp;
 560   Id idx, dirid;
 561   Id hx, qx;
 562   Hashval h, hh;
 563
 564   idx = cbdata->idx;
 565
 566   if (!info->dirlen)
 567     return;
 568   dp = fn + info->dirlen;
 569   if (info->diridx != cbdata->lastdiridx)
 570     {
 571       cbdata->lastdiridx = info->diridx;
 572       cbdata->lastdirhash = 0;
 573     }
 574   dp = fn + info->dirlen;
 575   hx = strhash(dp);
 576   if (!hx)
 577     hx = strlen(fn) + 1;
 578
 579   h = hx & cbdata->cflmapn;
 580   hh = HASHCHAIN_START;
 581   for (;;)
 582     {
 583       qx = cbdata->cflmap[2 * h];
 584       if (!qx)
 585         break;
 586       if (qx == hx)
 587         break;
 588       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 589     }
 590   if (!qx || cbdata->cflmap[2 * h + 1] != -1)
 591     return;
 592   if (!cbdata->lastdirhash)
 593     cbdata->lastdirhash = strnhash(fn, dp - fn);
 594   dirid = normalizedir(cbdata, fn, dp - fn, cbdata->lastdirhash, 1);
 595   queue_push2(&cbdata->lookat, hx, idx);
 596   queue_push2(&cbdata->lookat, cbdata->lastdirhash, isdir ? -dirid : dirid);
 597 }
 598
 599 static void
 600 findfileconflicts2_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 601 {
 602   struct cbdata *cbdata = cbdatav;
 603   Hashval hx;
 604   const char *dp;
 605   char md5padded[34];
 606   Id off;
 607
 608   if (!info->dirlen)
 609     return;
 610   dp = fn + info->dirlen;
 611   if (info->diridx != cbdata->lastdiridx)
 612     {
 613       cbdata->lastdiridx = info->diridx;
 614       cbdata->lastdirhash = strnhash(fn, dp - fn);
 615     }
 616   if (cbdata->aliases)
 617     {
 618       if (cbdata->lastdirhash != cbdata->dirhash)
 619         return;
 620       hx = strhash(dp);
 621     }
 622   else
 623     {
 624       hx = cbdata->lastdirhash;
 625       hx = strhash_cont(dp, hx);
 626     }
 627   if (!hx)
 628     hx = strlen(fn) + 1;
 629   if ((Id)hx != cbdata->hx)
 630     return;
 631   if (cbdata->dirid && cbdata->dirid != normalizedir(cbdata, fn, dp - fn, cbdata->dirhash, 0))
 632     return;
 633   strncpy(md5padded, info->digest, 32);
 634   md5padded[32] = 0;
 635   md5padded[33] = info->color;
 636   /* printf("%d, hx %x -> %s   %d %s\n", cbdata->idx, hx, fn, info->mode, info->digest); */
 637   off = addfilesspace(cbdata, strlen(fn) + (34 + 1));
 638   memcpy(cbdata->filesspace + off, (unsigned char *)md5padded, 34);
 639   strcpy((char *)cbdata->filesspace + off + 34, fn);
 640   queue_push(&cbdata->files, off);
 641 }
 642
 643 static int
 644 lookat_idx_cmp(const void *ap, const void *bp, void *dp)
 645 {
 646   const Id *a = ap, *b = bp;
 647   unsigned int ahx, bhx;
 648   if (a[1] - b[1] != 0)         /* idx */
 649     return a[1] - b[1];
 650   if (a[3] - b[3] != 0)         /* dirid */
 651     return a[3] - b[3];
 652   ahx = (unsigned int)a[0];     /* can be < 0 */
 653   bhx = (unsigned int)b[0];
 654   if (ahx != bhx)
 655     return ahx < bhx ? -1 : 1;
 656   ahx = (unsigned int)a[2];     /* dhx */
 657   bhx = (unsigned int)b[2];
 658   if (ahx != bhx)
 659     return ahx < bhx ? -1 : 1;
 660   return 0;
 661 }
 662
 663 static int
 664 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
 665 {
 666   const Id *a = ap, *b = bp;
 667   unsigned int ahx, bhx;
 668   Id adirid, bdirid;
 669   ahx = (unsigned int)a[0];     /* can be < 0 */
 670   bhx = (unsigned int)b[0];
 671   if (ahx != bhx)
 672     return ahx < bhx ? -1 : 1;
 673   adirid = a[3] < 0 ? -a[3] : a[3];
 674   bdirid = b[3] < 0 ? -b[3] : b[3];
 675   if (adirid - bdirid != 0)     /* dirid */
 676     return adirid - bdirid;
 677   if (a[3] != b[3])
 678     return a[3] > 0 ? -1 : 1;   /* bring positive dirids to front */
 679   if (a[1] - b[1] != 0)         /* idx */
 680     return a[1] - b[1];
 681   ahx = (unsigned int)a[2];     /* dhx */
 682   bhx = (unsigned int)b[2];
 683   if (ahx != bhx)
 684     return ahx < bhx ? -1 : 1;
 685   return 0;
 686 }
 687
 688 static int
 689 conflicts_cmp(const void *ap, const void *bp, void *dp)
 690 {
 691   Pool *pool = dp;
 692   const Id *a = ap;
 693   const Id *b = bp;
 694   if (a[0] != b[0])     /* filename1 */
 695     return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
 696   if (a[3] != b[3])     /* filename2 */
 697     return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
 698   if (a[1] != b[1])     /* pkgid1 */
 699     return a[1] - b[1];
 700   if (a[4] != b[4])     /* pkgid2 */
 701     return a[4] - b[4];
 702   return 0;
 703 }
 704
 705 static void
 706 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
 707 {
 708   Repodata *lastdata = 0;
 709   Id lastdirid = -1;
 710   Dataiterator di;
 711
 712   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 713   while (dataiterator_step(&di))
 714     {
 715       if (di.data == lastdata && di.kv.id == lastdirid)
 716         continue;
 717       lastdata = di.data;
 718       lastdirid = di.kv.id;
 719       cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
 720     }
 721   dataiterator_free(&di);
 722 }
 723
 724 /* before calling the expensive findfileconflicts_basename_cb we check if any of
 725  * the basenames match. This only makes sense when cbdata->create is off.
 726  */
 727 static int
 728 precheck_solvable_files(struct cbdata *cbdata, Pool *pool, Id p)
 729 {
 730   Dataiterator di;
 731   Id hx, qx;
 732   Hashval h, hh;
 733   int found = 0;
 734
 735   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 736   while (dataiterator_step(&di))
 737     {
 738       hx = strhash(di.kv.str);
 739       if (!hx)
 740         hx = strlen(di.kv.str) + 1;
 741       h = hx & cbdata->cflmapn;
 742       hh = HASHCHAIN_START;
 743       for (;;)
 744         {
 745           qx = cbdata->cflmap[2 * h];
 746           if (!qx)
 747             break;
 748           if (qx == hx)
 749             {
 750               found = 1;
 751               break;
 752             }
 753           h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 754         }
 755       if (found)
 756         break;
 757     }
 758   dataiterator_free(&di);
 759   return found;
 760 }
 761
 762
 763 int
 764 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
 765 {
 766   int i, j, cflmapn, idxmapset;
 767   struct cbdata cbdata;
 768   unsigned int now, start;
 769   void *handle;
 770   Repo *installed = pool->installed;
 771   Id p;
 772   int obsoleteusescolors = pool_get_flag(pool, POOL_FLAG_OBSOLETEUSESCOLORS);
 773
 774   queue_empty(conflicts);
 775   if (!pkgs->count)
 776     return 0;
 777
 778   now = start = solv_timems(0);
 779   POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
 780   POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
 781
 782   memset(&cbdata, 0, sizeof(cbdata));
 783   cbdata.aliases = flags & FINDFILECONFLICTS_CHECK_DIRALIASING;
 784   cbdata.pool = pool;
 785   if (cbdata.aliases && (flags & FINDFILECONFLICTS_USE_ROOTDIR) != 0)
 786     {
 787       cbdata.rootdir = pool_get_rootdir(pool);
 788       if (cbdata.rootdir && !strcmp(cbdata.rootdir, "/"))
 789         cbdata.rootdir = 0;
 790       if (cbdata.rootdir)
 791         cbdata.rootdirl = strlen(cbdata.rootdir);
 792       if (!cbdata.rootdir)
 793         cbdata.usestat = 1;
 794     }
 795   queue_init(&cbdata.lookat);
 796   queue_init(&cbdata.lookat_dir);
 797   map_init(&cbdata.idxmap, pkgs->count);
 798
 799   if (cutoff <= 0)
 800     cutoff = pkgs->count;
 801
 802   /* avarage file list size: 200 files per package */
 803   /* avarage dir count: 20 dirs per package */
 804
 805   /* first pass: scan dirs */
 806   if (!cbdata.aliases)
 807     {
 808       cflmapn = (cutoff + 3) * 64;
 809       while ((cflmapn & (cflmapn - 1)) != 0)
 810         cflmapn = cflmapn & (cflmapn - 1);
 811       cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 812       cbdata.dirmapn = cflmapn - 1;     /* make it a mask */
 813       cbdata.create = 1;
 814       idxmapset = 0;
 815       for (i = 0; i < pkgs->count; i++)
 816         {
 817           p = pkgs->elements[i];
 818           cbdata.idx = i;
 819           if (i == cutoff)
 820             cbdata.create = 0;
 821           if ((flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
 822             {
 823               if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 824                 {
 825                   iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
 826                   if (MAPTST(&cbdata.idxmap, i))
 827                     idxmapset++;
 828                   continue;
 829                 }
 830             }
 831           handle = (*handle_cb)(pool, p, handle_cbdata);
 832           if (!handle)
 833             continue;
 834           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 835           if (MAPTST(&cbdata.idxmap, i))
 836             idxmapset++;
 837         }
 838       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
 839       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 840       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
 841       POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
 842     }
 843
 844   /* second pass: scan files */
 845   now = solv_timems(0);
 846   cflmapn = (cutoff + 3) * 128;
 847   while ((cflmapn & (cflmapn - 1)) != 0)
 848     cflmapn = cflmapn & (cflmapn - 1);
 849   cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 850   cbdata.cflmapn = cflmapn - 1; /* make it a mask */
 851   cbdata.create = 1;
 852   for (i = 0; i < pkgs->count; i++)
 853     {
 854       if (!cbdata.aliases && !MAPTST(&cbdata.idxmap, i))
 855         continue;
 856       p = pkgs->elements[i];
 857       cbdata.idx = i;
 858       if (i == cutoff)
 859         cbdata.create = 0;
 860       if (cbdata.aliases && !cbdata.create && FINDFILECONFLICTS_USE_SOLVABLEFILELIST)
 861         {
 862           if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 863             if (!precheck_solvable_files(&cbdata, pool, p))
 864               continue;
 865         }
 866       /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
 867        * the file is a directory or not */
 868       handle = (*handle_cb)(pool, p, handle_cbdata);
 869       if (!handle)
 870         continue;
 871       cbdata.lastdiridx = -1;
 872       rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, cbdata.aliases ? findfileconflicts_basename_cb : findfileconflicts_cb, &cbdata);
 873     }
 874
 875   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
 876   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 877   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
 878   POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
 879   queue_free(&cbdata.lookat_dir);
 880
 881   /* we need another pass for aliases */
 882   if (cbdata.aliases)
 883     {
 884       now = solv_timems(0);
 885       /* make sure the first offset is not zero */
 886       addfilesspace(&cbdata, 1);
 887       cflmapn = (cutoff + 3) * 16;
 888       while ((cflmapn & (cflmapn - 1)) != 0)
 889         cflmapn = cflmapn & (cflmapn - 1);
 890       cbdata.normap = solv_calloc(cflmapn, 2 * sizeof(Id));
 891       cbdata.normapn = cflmapn - 1;     /* make it a mask */
 892       if (cbdata.usestat)
 893         {
 894           cbdata.statmap = solv_calloc(cflmapn, 2 * sizeof(Id));
 895           cbdata.statmapn = cflmapn - 1;        /* make it a mask */
 896         }
 897       cbdata.create = 0;
 898       for (i = 0; i < pkgs->count; i++)
 899         {
 900           if (!MAPTST(&cbdata.idxmap, i))
 901             continue;
 902           p = pkgs->elements[i];
 903           cbdata.idx = i;
 904           /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
 905            * the file is a directory or not */
 906           handle = (*handle_cb)(pool, p, handle_cbdata);
 907           if (!handle)
 908             continue;
 909           cbdata.lastdiridx = -1;
 910           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_alias_cb, &cbdata);
 911         }
 912       POOL_DEBUG(SOLV_DEBUG_STATS, "normap size: %d, used %d\n", cbdata.normapn + 1, cbdata.normapused);
 913       POOL_DEBUG(SOLV_DEBUG_STATS, "normap memory usage: %d K\n", (cbdata.normapn + 1) * 2 * (int)sizeof(Id) / 1024);
 914       POOL_DEBUG(SOLV_DEBUG_STATS, "stats made: %d\n", cbdata.statsmade);
 915       if (cbdata.usestat)
 916         {
 917           POOL_DEBUG(SOLV_DEBUG_STATS, "statmap size: %d, used %d\n", cbdata.statmapn + 1, cbdata.statmapused);
 918           POOL_DEBUG(SOLV_DEBUG_STATS, "statmap memory usage: %d K\n", (cbdata.statmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 919         }
 920       cbdata.statmap = solv_free(cbdata.statmap);
 921       cbdata.statmapn = 0;
 922       cbdata.canonspace = solv_free(cbdata.canonspace);
 923       cbdata.canonspacen = 0;
 924       POOL_DEBUG(SOLV_DEBUG_STATS, "alias processing took %d ms\n", solv_timems(now));
 925     }
 926
 927   cbdata.dirmap = solv_free(cbdata.dirmap);
 928   cbdata.dirmapn = 0;
 929   cbdata.dirmapused = 0;
 930   cbdata.cflmap = solv_free(cbdata.cflmap);
 931   cbdata.cflmapn = 0;
 932   cbdata.cflmapused = 0;
 933
 934   now = solv_timems(0);
 935
 936   map_free(&cbdata.idxmap);
 937
 938   /* sort and unify/prune */
 939   POOL_DEBUG(SOLV_DEBUG_STATS, "raw candidates: %d, pruning\n", cbdata.lookat.count / 4);
 940   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
 941   for (i = j = 0; i < cbdata.lookat.count; )
 942     {
 943       int first = 1;
 944       Id hx = cbdata.lookat.elements[i];
 945       Id idx = cbdata.lookat.elements[i + 1];
 946       Id dhx = cbdata.lookat.elements[i + 2];
 947       Id dirid = cbdata.lookat.elements[i + 3];
 948       i += 4;
 949       for (; i < cbdata.lookat.count && hx == cbdata.lookat.elements[i] && (dirid == cbdata.lookat.elements[i + 3] || dirid == -cbdata.lookat.elements[i + 3]); i += 4)
 950         {
 951           if (idx == cbdata.lookat.elements[i + 1] && dhx == cbdata.lookat.elements[i + 2])
 952             continue;   /* ignore duplicates */
 953           if (first)
 954             {
 955               if (dirid < 0)
 956                 continue;       /* all have a neg dirid */
 957               cbdata.lookat.elements[j++] = hx;
 958               cbdata.lookat.elements[j++] = idx;
 959               cbdata.lookat.elements[j++] = dhx;
 960               cbdata.lookat.elements[j++] = dirid;
 961               first = 0;
 962             }
 963           idx = cbdata.lookat.elements[i + 1];
 964           dhx = cbdata.lookat.elements[i + 2];
 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         }
 970     }
 971   queue_truncate(&cbdata.lookat, j);
 972   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates now: %d\n", cbdata.lookat.count / 4);
 973
 974   /* third pass: collect file info for all files that match a hx */
 975   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_idx_cmp, pool);
 976   queue_init(&cbdata.files);
 977   for (i = 0; i < cbdata.lookat.count; i += 4)
 978     {
 979       Id idx = cbdata.lookat.elements[i + 1];
 980       int iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
 981       if (obsoleteusescolors)
 982         iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
 983       p = pkgs->elements[idx];
 984       handle = (*handle_cb)(pool, p, handle_cbdata);
 985       for (;; i += 4)
 986         {
 987           int fstart = cbdata.files.count;
 988           queue_push(&cbdata.files, idx);
 989           queue_push(&cbdata.files, 0);
 990           cbdata.idx = idx;
 991           cbdata.hx = cbdata.lookat.elements[i];
 992           cbdata.dirhash = cbdata.lookat.elements[i + 2];
 993           cbdata.dirid = cbdata.lookat.elements[i + 3];
 994           cbdata.lastdiridx = -1;
 995           if (handle)
 996             rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
 997           cbdata.files.elements[fstart + 1] = cbdata.files.count;
 998           cbdata.lookat.elements[i + 1] = fstart;
 999           if (i + 4 >= cbdata.lookat.count || cbdata.lookat.elements[i + 4 + 1] != idx)
1000             break;
1001         }
1002     }
1003
1004   cbdata.normap = solv_free(cbdata.normap);
1005   cbdata.normapn = 0;
1006
1007   /* forth pass: for each hx we have, compare all matching files against all other matching files */
1008   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
1009   for (i = 0; i < cbdata.lookat.count - 4; i += 4)
1010     {
1011       Id hx = cbdata.lookat.elements[i];
1012       Id pstart = cbdata.lookat.elements[i + 1];
1013       Id dirid = cbdata.lookat.elements[i + 3];
1014       Id pidx = cbdata.files.elements[pstart];
1015       Id pend = cbdata.files.elements[pstart + 1];
1016       if (cbdata.lookat.elements[i + 4] != hx)
1017         continue;       /* no package left with that hx */
1018       for (j = i + 4; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx && cbdata.lookat.elements[j + 3] == dirid; j += 4)
1019         {
1020           Id qstart = cbdata.lookat.elements[j + 1];
1021           Id qidx = cbdata.files.elements[qstart];
1022           Id qend = cbdata.files.elements[qstart + 1];
1023           int ii, jj;
1024           if (pidx >= cutoff && qidx >= cutoff)
1025             continue;   /* no conflicts between packages with idx >= cutoff */
1026           for (ii = pstart + 2; ii < pend; ii++)
1027             for (jj = qstart + 2; jj < qend; jj++)
1028               {
1029                 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
1030                 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
1031                 if (cbdata.aliases)
1032                   {
1033                     /* compare just the basenames, the dirs match */
1034                     char *bsi = strrchr(fsi + 34, '/');
1035                     char *bsj = strrchr(fsj + 34, '/');
1036                     if ((!bsi || !bsj) && bsi != bsj)
1037                       continue;
1038                     if (strcmp(bsi, bsj))
1039                       continue; /* different file names */
1040                   }
1041                 else
1042                   {
1043                     if (strcmp(fsi + 34, fsj + 34))
1044                       continue; /* different file names */
1045                   }
1046                 if (!strcmp(fsi, fsj))
1047                   continue;     /* md5 sum matches */
1048                 if (obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
1049                   continue;     /* colors do not conflict */
1050                 queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
1051                 queue_push(conflicts, pkgs->elements[pidx]);
1052                 queue_push(conflicts, pool_str2id(pool, fsi, 1));
1053                 queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
1054                 queue_push(conflicts, pkgs->elements[qidx]);
1055                 queue_push(conflicts, pool_str2id(pool, fsj, 1));
1056               }
1057         }
1058     }
1059   POOL_DEBUG(SOLV_DEBUG_STATS, "filespace size: %d K\n", cbdata.filesspacen / 1024);
1060   POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
1061   cbdata.filesspace = solv_free(cbdata.filesspace);
1062   cbdata.filesspacen = 0;
1063   queue_free(&cbdata.lookat);
1064   queue_free(&cbdata.files);
1065   if (conflicts->count > 6)
1066     solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
1067   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
1068   POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
1069
1070   return conflicts->count;
1071 }
1072