lib/fprint.c

   1 /**
   2  * \file lib/fprint.c
   3  */
   4
   5 #include "system.h"
   6
   7 #include <rpm/rpmfileutil.h>    /* for rpmCleanPath */
   8 #include <rpm/rpmts.h>
   9 #include <rpm/rpmdb.h>
  10
  11 #include "lib/rpmdb_internal.h"
  12 #include "lib/rpmfi_internal.h"
  13 #include "lib/rpmte_internal.h"
  14 #include "lib/fprint.h"
  15 #include "lib/misc.h"
  16 #include "debug.h"
  17 #include <libgen.h>
  18
  19 /* Create new hash table type rpmFpEntryHash */
  20 #undef HASHTYPE
  21 #undef HTKEYTYPE
  22 #undef HTDATATYPE
  23 #define HASHTYPE rpmFpEntryHash
  24 #define HTKEYTYPE rpmsid
  25 #define HTDATATYPE const struct fprintCacheEntry_s *
  26 #include "lib/rpmhash.H"
  27 #include "lib/rpmhash.C"
  28
  29 /* Create by-fingerprint hash table */
  30 #undef HASHTYPE
  31 #undef HTKEYTYPE
  32 #undef HTDATATYPE
  33 #define HASHTYPE rpmFpHash
  34 #define HTKEYTYPE const fingerPrint *
  35 #define HTDATATYPE struct rpmffi_s
  36 #include "lib/rpmhash.H"
  37 #include "lib/rpmhash.C"
  38 #undef HASHTYPE
  39 #undef HTKEYTYPE
  40 #undef HTDATATYPE
  41
  42 static unsigned int sidHash(rpmsid sid)
  43 {
  44     return sid;
  45 }
  46
  47 static int sidCmp(rpmsid a, rpmsid b)
  48 {
  49     return (a != b);
  50 }
  51
  52 /**
  53  * Finger print cache entry.
  54  * This is really a directory and symlink cache. We don't differentiate between
  55  * the two. We can prepopulate it, which allows us to easily conduct "fake"
  56  * installs of a system w/o actually mounting filesystems.
  57  */
  58 struct fprintCacheEntry_s {
  59     rpmsid dirId;                       /*!< path to existing directory */
  60     dev_t dev;                          /*!< stat(2) device number */
  61     ino_t ino;                          /*!< stat(2) inode number */
  62 };
  63
  64 /**
  65  * Associates a trailing sub-directory and final base name with an existing
  66  * directory finger print.
  67  */
  68 struct fingerPrint_s {
  69     /*! directory finger print entry (the directory path is stat(2)-able */
  70     const struct fprintCacheEntry_s * entry;
  71     /*! trailing sub-directory path (directories that are not stat(2)-able */
  72     rpmsid subDirId;
  73     rpmsid baseNameId;  /*!< file base name id */
  74 };
  75
  76 #define FP_ENTRY_EQUAL(a, b) (((a)->dev == (b)->dev) && ((a)->ino == (b)->ino))
  77
  78 #define FP_EQUAL(a, b) ( \
  79         FP_ENTRY_EQUAL((a).entry, (b).entry) && \
  80             ((a).baseNameId == (b).baseNameId) && \
  81             ((a).subDirId == (b).subDirId) \
  82     )
  83
  84 /**
  85  * Finger print cache.
  86  */
  87 struct fprintCache_s {
  88     rpmFpEntryHash ht;                  /*!< hashed by dirName */
  89     rpmFpHash fp;                       /*!< hashed by fingerprint */
  90     rpmstrPool pool;                    /*!< string pool */
  91 };
  92
  93 fingerPrintCache fpCacheCreate(int sizeHint, rpmstrPool pool)
  94 {
  95     fingerPrintCache fpc;
  96
  97     fpc = xcalloc(1, sizeof(*fpc));
  98     fpc->ht = rpmFpEntryHashCreate(sizeHint, sidHash, sidCmp,
  99                                    NULL, (rpmFpEntryHashFreeData)free);
 100     fpc->pool = (pool != NULL) ? rpmstrPoolLink(pool) : rpmstrPoolCreate();
 101     return fpc;
 102 }
 103
 104 fingerPrintCache fpCacheFree(fingerPrintCache cache)
 105 {
 106     if (cache) {
 107         cache->ht = rpmFpEntryHashFree(cache->ht);
 108         cache->fp = rpmFpHashFree(cache->fp);
 109         cache->pool = rpmstrPoolFree(cache->pool);
 110         free(cache);
 111     }
 112     return NULL;
 113 }
 114
 115 /**
 116  * Find directory name entry in cache.
 117  * @param cache         pointer to fingerprint cache
 118  * @param dirId         string id to locate in cache
 119  * @return pointer to directory name entry (or NULL if not found).
 120  */
 121 static const struct fprintCacheEntry_s * cacheContainsDirectory(
 122                             fingerPrintCache cache, rpmsid dirId)
 123 {
 124     const struct fprintCacheEntry_s ** data;
 125
 126     if (rpmFpEntryHashGetEntry(cache->ht, dirId, &data, NULL, NULL))
 127         return data[0];
 128     return NULL;
 129 }
 130
 131 static char * canonDir(rpmstrPool pool, rpmsid dirNameId)
 132 {
 133     const char * dirName = rpmstrPoolStr(pool, dirNameId);
 134     size_t cdnl = rpmstrPoolStrlen(pool, dirNameId);;
 135     char *cdnbuf = NULL;
 136
 137     if (*dirName == '/') {
 138         cdnbuf = xstrdup(dirName);
 139         cdnbuf = rpmCleanPath(cdnbuf);
 140         /* leave my trailing slashes along you b**** */
 141         if (cdnl > 1)
 142             cdnbuf = rstrcat(&cdnbuf, "/");
 143     } else {
 144         /* Using realpath on the arg isn't correct if the arg is a symlink,
 145          * especially if the symlink is a dangling link.  What we
 146          * do instead is use realpath() on `.' and then append arg to
 147          * the result.
 148          */
 149
 150         /* if the current directory doesn't exist, we might fail.
 151            oh well. likewise if it's too long.  */
 152
 153         /* XXX we should let realpath() allocate if it can */
 154         cdnbuf = xmalloc(PATH_MAX);
 155         cdnbuf[0] = '\0';
 156         if (realpath(".", cdnbuf) != NULL) {
 157             char *end = cdnbuf + strlen(cdnbuf);
 158             if (end[-1] != '/') *end++ = '/';
 159             end = stpncpy(end, dirName, PATH_MAX - (end - cdnbuf));
 160             *end = '\0';
 161             (void)rpmCleanPath(cdnbuf); /* XXX possible /../ from concatenation */
 162             end = cdnbuf + strlen(cdnbuf);
 163             if (end[-1] != '/') *end++ = '/';
 164             *end = '\0';
 165         } else {
 166             cdnbuf = _free(cdnbuf);
 167         }
 168     }
 169     return cdnbuf;
 170 }
 171
 172
 173 static int doLookupId(fingerPrintCache cache,
 174              rpmsid dirNameId, rpmsid baseNameId,
 175              fingerPrint *fp)
 176 {
 177     struct stat sb;
 178     const struct fprintCacheEntry_s * cacheHit;
 179     char *cdn = canonDir(cache->pool, dirNameId);
 180     rpmsid fpId;
 181     size_t fpLen;
 182
 183     if (cdn == NULL) goto exit; /* XXX only if realpath() above fails */
 184
 185     memset(fp, 0, sizeof(*fp));
 186     fpId = rpmstrPoolId(cache->pool, cdn, 1);
 187     fpLen = rpmstrPoolStrlen(cache->pool, fpId);;
 188
 189     while (1) {
 190         /* as we're stating paths here, we want to follow symlinks */
 191         cacheHit = cacheContainsDirectory(cache, fpId);
 192         if (cacheHit != NULL) {
 193             fp->entry = cacheHit;
 194         } else if (!stat(rpmstrPoolStr(cache->pool, fpId), &sb)) {
 195             struct fprintCacheEntry_s * newEntry = xmalloc(sizeof(* newEntry));
 196
 197             newEntry->ino = sb.st_ino;
 198             newEntry->dev = sb.st_dev;
 199             newEntry->dirId = fpId;
 200             fp->entry = newEntry;
 201
 202             rpmFpEntryHashAddEntry(cache->ht, fpId, fp->entry);
 203         }
 204
 205         if (fp->entry) {
 206             const char * subDir = cdn + fpLen - 1;
 207             /* XXX don't bother saving '/' as subdir */
 208             if (subDir[0] == '\0' || (subDir[0] == '/' && subDir[1] == '\0'))
 209                 subDir = NULL;
 210             fp->baseNameId = baseNameId;
 211             if (subDir != NULL)
 212                 fp->subDirId = rpmstrPoolId(cache->pool, subDir, 1);
 213             goto exit;
 214         }
 215
 216         /* stat of '/' just failed! */
 217         if (fpLen == 1)
 218             abort();
 219
 220         /* Find the parent directory and its id for the next round */
 221         fpLen--;
 222         while (fpLen > 1 && cdn[fpLen-1] != '/')
 223             fpLen--;
 224         fpId = rpmstrPoolIdn(cache->pool, cdn, fpLen, 1);
 225     }
 226
 227 exit:
 228     free(cdn);
 229     /* XXX TODO: failure from eg realpath() should be returned and handled */
 230     return 0;
 231 }
 232
 233 static int doLookup(fingerPrintCache cache,
 234                     const char * dirName, const char * baseName,
 235                     fingerPrint *fp)
 236 {
 237     rpmsid dirNameId = rpmstrPoolId(cache->pool, dirName, 1);
 238     rpmsid baseNameId = rpmstrPoolId(cache->pool, baseName, 1);
 239     return doLookupId(cache, dirNameId, baseNameId, fp);
 240 }
 241
 242 int fpLookup(fingerPrintCache cache,
 243              const char * dirName, const char * baseName,
 244              fingerPrint **fp)
 245 {
 246     if (*fp == NULL)
 247         *fp = xcalloc(1, sizeof(**fp));
 248     return doLookup(cache, dirName, baseName, *fp);
 249 }
 250
 251 /**
 252  * Return hash value for a finger print.
 253  * Hash based on dev and inode only!
 254  * @param key           pointer to finger print entry
 255  * @return hash value
 256  */
 257 static unsigned int fpHashFunction(const fingerPrint * fp)
 258 {
 259     unsigned int hash = 0;
 260     int j;
 261
 262     hash = sidHash(fp->baseNameId);
 263     if (fp->subDirId) hash ^= sidHash(fp->subDirId);
 264
 265     hash ^= ((unsigned)fp->entry->dev);
 266     for (j=0; j<4; j++) hash ^= ((fp->entry->ino >> (8*j)) & 0xFF) << ((3-j)*8);
 267
 268     return hash;
 269 }
 270
 271 int fpEqual(const fingerPrint * k1, const fingerPrint * k2)
 272 {
 273     /* If the addresses are the same, so are the values. */
 274     if (k1 == k2)
 275         return 0;
 276
 277     /* Otherwise, compare fingerprints by value. */
 278     if (FP_EQUAL(*k1, *k2))
 279         return 0;
 280     return 1;
 281
 282 }
 283
 284 const char * fpEntryDir(fingerPrintCache cache, fingerPrint *fp)
 285 {
 286     const char * dn = NULL;
 287     if (fp && fp->entry)
 288         dn = rpmstrPoolStr(cache->pool, fp->entry->dirId);
 289     return dn;
 290 }
 291
 292 dev_t fpEntryDev(fingerPrintCache cache, fingerPrint *fp)
 293 {
 294     return (fp && fp->entry) ? fp->entry->dev : 0;
 295 }
 296
 297 int fpLookupEquals(fingerPrintCache cache, fingerPrint *fp,
 298                   const char * dirName, const char * baseName)
 299 {
 300     struct fingerPrint_s ofp;
 301     doLookup(cache, dirName, baseName, &ofp);
 302     return FP_EQUAL(*fp, ofp);
 303 }
 304
 305 fingerPrint * fpLookupList(fingerPrintCache cache, rpmstrPool pool,
 306                   rpmsid * dirNames, rpmsid * baseNames,
 307                   const uint32_t * dirIndexes,
 308                   int fileCount)
 309 {
 310     fingerPrint * fps = xmalloc(fileCount * sizeof(*fps));
 311     int i;
 312
 313     /*
 314      * We could handle different pools easily enough, but there should be
 315      * no need for that. Make sure we catch any oddball cases there might be
 316      * lurking about.
 317      */
 318     assert(cache->pool == pool);
 319
 320     for (i = 0; i < fileCount; i++) {
 321         /* If this is in the same directory as the last file, don't bother
 322            redoing all of this work */
 323         if (i > 0 && dirIndexes[i - 1] == dirIndexes[i]) {
 324             fps[i].entry = fps[i - 1].entry;
 325             fps[i].subDirId = fps[i - 1].subDirId;
 326             /* XXX if the pools are different, copy would be needed */
 327             fps[i].baseNameId = baseNames[i];
 328         } else {
 329             doLookupId(cache, dirNames[dirIndexes[i]], baseNames[i], &fps[i]);
 330         }
 331     }
 332     return fps;
 333 }
 334
 335 /* Check file for to be installed symlinks in their path and correct their fp */
 336 static void fpLookupSubdir(rpmFpHash symlinks, fingerPrintCache fpc, rpmte p, int filenr)
 337 {
 338     rpmfi fi = rpmteFI(p);
 339     struct fingerPrint_s current_fp;
 340     const char *currentsubdir;
 341     size_t lensubDir, bnStart, bnEnd;
 342
 343     struct rpmffi_s * recs;
 344     int numRecs;
 345     int i;
 346     fingerPrint *fp = rpmfiFps(fi) + filenr;
 347     int symlinkcount = 0;
 348     struct rpmffi_s ffi = { p, filenr};
 349
 350     if (fp->subDirId == 0) {
 351          rpmFpHashAddEntry(fpc->fp, fp, ffi);
 352          return;
 353     }
 354
 355     currentsubdir = rpmstrPoolStr(fpc->pool, fp->subDirId);
 356     lensubDir = rpmstrPoolStrlen(fpc->pool, fp->subDirId);
 357     current_fp = *fp;
 358
 359     /* Set baseName to the upper most dir */
 360     bnStart = bnEnd = 1;
 361     while (bnEnd < lensubDir && currentsubdir[bnEnd] != '/')
 362         bnEnd++;
 363     /* no subDir for now */
 364     current_fp.subDirId = 0;
 365
 366     while (bnEnd < lensubDir) {
 367          char found = 0;
 368
 369          current_fp.baseNameId = rpmstrPoolIdn(fpc->pool,
 370                                                 currentsubdir + bnStart,
 371                                                 bnEnd - bnStart, 1);
 372
 373          rpmFpHashGetEntry(symlinks, &current_fp, &recs, &numRecs, NULL);
 374
 375          for (i=0; i<numRecs; i++) {
 376               rpmfi foundfi = rpmteFI(recs[i].p);
 377               char const *linktarget = rpmfiFLinkIndex(foundfi, recs[i].fileno);
 378               char *link;
 379
 380               if (linktarget && *linktarget != '\0') {
 381                    const char *bn;
 382                    /* this "directory" is a symlink */
 383                    link = NULL;
 384                    if (*linktarget != '/') {
 385                         const char *dn, *subDir = NULL;
 386                         dn = rpmstrPoolStr(fpc->pool, current_fp.entry->dirId);
 387                         if (current_fp.subDirId) {
 388                             subDir = rpmstrPoolStr(fpc->pool,
 389                                                    current_fp.subDirId);
 390                         }
 391                         rstrscat(&link, dn,
 392                                  subDir ? subDir : "",
 393                                  "/", NULL);
 394                    }
 395                    rstrscat(&link, linktarget, "/", NULL);
 396                    if (strlen(currentsubdir + bnEnd)) {
 397                         rstrscat(&link, currentsubdir + bnEnd, NULL);
 398                    }
 399
 400                    bn = rpmstrPoolStr(fpc->pool, fp->baseNameId);
 401                    doLookup(fpc, link, bn, fp);
 402
 403                    free(link);
 404                    symlinkcount++;
 405
 406                    /* setup current_fp for the new path */
 407                    found = 1;
 408                    current_fp = *fp;
 409                    if (fp->subDirId == 0) {
 410                      /* directory exists - no need to look for symlinks */
 411                      rpmFpHashAddEntry(fpc->fp, fp, ffi);
 412                      return;
 413                    }
 414                    currentsubdir = rpmstrPoolStr(fpc->pool, fp->subDirId);
 415                    lensubDir = rpmstrPoolStrlen(fpc->pool, fp->subDirId);
 416                    /* no subDir for now */
 417                    current_fp.subDirId = 0;
 418
 419                    /* Set baseName to the upper most dir */
 420                    bnStart = bnEnd = 1;
 421                    while (bnEnd < lensubDir && currentsubdir[bnEnd] != '/')
 422                         bnEnd++;
 423                    break;
 424
 425               }
 426          }
 427          if (symlinkcount>50) {
 428               // found too many symlinks in the path
 429               // most likley a symlink cicle
 430               // giving up
 431               // TODO warning/error
 432               break;
 433          }
 434          if (found) {
 435               continue; // restart loop after symlink
 436          }
 437
 438           /* Set former baseName as subDir */
 439          bnEnd++;
 440          current_fp.subDirId = rpmstrPoolIdn(fpc->pool, currentsubdir, bnEnd, 1);
 441
 442          /* set baseName to the next lower dir */
 443          bnStart = bnEnd;
 444          while (bnEnd < lensubDir && currentsubdir[bnEnd] != '/')
 445             bnEnd++;
 446     }
 447     rpmFpHashAddEntry(fpc->fp, fp, ffi);
 448
 449 }
 450
 451 fingerPrint * fpCacheGetByFp(fingerPrintCache cache,
 452                              struct fingerPrint_s * fp, int ix,
 453                              struct rpmffi_s ** recs, int * numRecs)
 454 {
 455     if (rpmFpHashGetEntry(cache->fp, fp + ix, recs, numRecs, NULL))
 456         return fp + ix;
 457     else
 458         return NULL;
 459 }
 460
 461 void fpCachePopulate(fingerPrintCache fpc, rpmts ts, int fileCount)
 462 {
 463     rpmtsi pi;
 464     rpmte p;
 465     rpmfs fs;
 466     rpmfi fi;
 467     int i, fc;
 468
 469     if (fpc->fp == NULL)
 470         fpc->fp = rpmFpHashCreate(fileCount/2 + 10001, fpHashFunction, fpEqual,
 471                                   NULL, NULL);
 472
 473     rpmFpHash symlinks = rpmFpHashCreate(fileCount/16+16, fpHashFunction, fpEqual, NULL, NULL);
 474
 475     pi = rpmtsiInit(ts);
 476     while ((p = rpmtsiNext(pi, 0)) != NULL) {
 477         fingerPrint *fpList;
 478         (void) rpmdbCheckSignals();
 479
 480         if ((fi = rpmteFI(p)) == NULL)
 481             continue;   /* XXX can't happen */
 482
 483         (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), 0);
 484         rpmfiFpLookup(fi, fpc);
 485         fs = rpmteGetFileStates(p);
 486         fc = rpmfsFC(fs);
 487         fpList = rpmfiFps(fi);
 488         /* collect symbolic links */
 489         for (i = 0; i < fc; i++) {
 490             struct rpmffi_s ffi;
 491             char const *linktarget;
 492             if (XFA_SKIPPING(rpmfsGetAction(fs, i)))
 493                 continue;
 494             linktarget = rpmfiFLinkIndex(fi, i);
 495             if (!(linktarget && *linktarget != '\0'))
 496                 continue;
 497             ffi.p = p;
 498             ffi.fileno = i;
 499             rpmFpHashAddEntry(symlinks, fpList + i, ffi);
 500         }
 501         (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), fc);
 502
 503     }
 504     rpmtsiFree(pi);
 505
 506     /* ===============================================
 507      * Check fingerprints if they contain symlinks
 508      * and add them to the hash table
 509      */
 510
 511     pi = rpmtsiInit(ts);
 512     while ((p = rpmtsiNext(pi, 0)) != NULL) {
 513         (void) rpmdbCheckSignals();
 514
 515         fs = rpmteGetFileStates(p);
 516         fc = rpmfsFC(fs);
 517         (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), 0);
 518         for (i = 0; i < fc; i++) {
 519             if (XFA_SKIPPING(rpmfsGetAction(fs, i)))
 520                 continue;
 521             fpLookupSubdir(symlinks, fpc, p, i);
 522         }
 523         (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), 0);
 524     }
 525     rpmtsiFree(pi);
 526
 527     rpmFpHashFree(symlinks);
 528 }
 529