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/rpmsq.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
sidHash(rpmsid sid)42 static unsigned int sidHash(rpmsid sid)
43 {
44 return sid;
45 }
46
sidCmp(rpmsid a,rpmsid b)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
fpCacheCreate(int sizeHint,rpmstrPool pool)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
fpCacheFree(fingerPrintCache cache)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 */
cacheContainsDirectory(fingerPrintCache cache,rpmsid dirId)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
canonDir(rpmstrPool pool,rpmsid dirNameId)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
doLookupId(fingerPrintCache cache,rpmsid dirNameId,rpmsid baseNameId,fingerPrint * fp)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
doLookup(fingerPrintCache cache,const char * dirName,const char * baseName,fingerPrint * fp)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
fpLookup(fingerPrintCache cache,const char * dirName,const char * baseName,fingerPrint ** fp)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
fpLookupId(fingerPrintCache cache,rpmsid dirNameId,rpmsid baseNameId,fingerPrint ** fp)251 int fpLookupId(fingerPrintCache cache,
252 rpmsid dirNameId, rpmsid baseNameId,
253 fingerPrint **fp)
254 {
255 if (*fp == NULL)
256 *fp = xcalloc(1, sizeof(**fp));
257 return doLookupId(cache, dirNameId, baseNameId, *fp);
258 }
259
260 /**
261 * Return hash value for a finger print.
262 * Hash based on dev and inode only!
263 * @param fp pointer to finger print entry
264 * @return hash value
265 */
fpHashFunction(const fingerPrint * fp)266 static unsigned int fpHashFunction(const fingerPrint * fp)
267 {
268 unsigned int hash = 0;
269 int j;
270
271 hash = sidHash(fp->baseNameId);
272 if (fp->subDirId) hash ^= sidHash(fp->subDirId);
273
274 hash ^= ((unsigned)fp->entry->dev);
275 for (j=0; j<4; j++) hash ^= ((fp->entry->ino >> (8*j)) & 0xFF) << ((3-j)*8);
276
277 return hash;
278 }
279
fpEqual(const fingerPrint * k1,const fingerPrint * k2)280 int fpEqual(const fingerPrint * k1, const fingerPrint * k2)
281 {
282 /* If the addresses are the same, so are the values. */
283 if (k1 == k2)
284 return 0;
285
286 /* Otherwise, compare fingerprints by value. */
287 if (FP_EQUAL(*k1, *k2))
288 return 0;
289 return 1;
290
291 }
292
fpEntryDir(fingerPrintCache cache,fingerPrint * fp)293 const char * fpEntryDir(fingerPrintCache cache, fingerPrint *fp)
294 {
295 const char * dn = NULL;
296 if (fp && fp->entry)
297 dn = rpmstrPoolStr(cache->pool, fp->entry->dirId);
298 return dn;
299 }
300
fpEntryDev(fingerPrintCache cache,fingerPrint * fp)301 dev_t fpEntryDev(fingerPrintCache cache, fingerPrint *fp)
302 {
303 return (fp && fp->entry) ? fp->entry->dev : 0;
304 }
305
fpLookupEquals(fingerPrintCache cache,fingerPrint * fp,const char * dirName,const char * baseName)306 int fpLookupEquals(fingerPrintCache cache, fingerPrint *fp,
307 const char * dirName, const char * baseName)
308 {
309 struct fingerPrint_s ofp;
310 doLookup(cache, dirName, baseName, &ofp);
311 return FP_EQUAL(*fp, ofp);
312 }
313
fpLookupEqualsId(fingerPrintCache cache,fingerPrint * fp,rpmsid dirNameId,rpmsid baseNameId)314 int fpLookupEqualsId(fingerPrintCache cache, fingerPrint *fp,
315 rpmsid dirNameId, rpmsid baseNameId)
316 {
317 struct fingerPrint_s ofp;
318 doLookupId(cache, dirNameId, baseNameId, &ofp);
319 return FP_EQUAL(*fp, ofp);
320 }
321
fpLookupList(fingerPrintCache cache,rpmstrPool pool,rpmsid * dirNames,rpmsid * baseNames,const uint32_t * dirIndexes,int fileCount)322 fingerPrint * fpLookupList(fingerPrintCache cache, rpmstrPool pool,
323 rpmsid * dirNames, rpmsid * baseNames,
324 const uint32_t * dirIndexes,
325 int fileCount)
326 {
327 fingerPrint * fps = xmalloc(fileCount * sizeof(*fps));
328 int i;
329
330 /*
331 * We could handle different pools easily enough, but there should be
332 * no need for that. Make sure we catch any oddball cases there might be
333 * lurking about.
334 */
335 assert(cache->pool == pool);
336
337 for (i = 0; i < fileCount; i++) {
338 /* If this is in the same directory as the last file, don't bother
339 redoing all of this work */
340 if (i > 0 && dirIndexes[i - 1] == dirIndexes[i]) {
341 fps[i].entry = fps[i - 1].entry;
342 fps[i].subDirId = fps[i - 1].subDirId;
343 /* XXX if the pools are different, copy would be needed */
344 fps[i].baseNameId = baseNames[i];
345 } else {
346 doLookupId(cache, dirNames[dirIndexes[i]], baseNames[i], &fps[i]);
347 }
348 }
349 return fps;
350 }
351
352 /* Check file for to be installed symlinks in their path and correct their fp */
fpLookupSubdir(rpmFpHash symlinks,fingerPrintCache fpc,fingerPrint * fp)353 static void fpLookupSubdir(rpmFpHash symlinks, fingerPrintCache fpc, fingerPrint *fp)
354 {
355 struct fingerPrint_s current_fp;
356 const char *currentsubdir;
357 size_t lensubDir, bnStart, bnEnd;
358
359 struct rpmffi_s * recs;
360 int numRecs;
361 int i;
362 int symlinkcount = 0;
363
364 for (;;) {
365 int found = 0;
366
367 if (fp->subDirId == 0)
368 break; /* directory exists - no need to look for symlinks */
369
370 currentsubdir = rpmstrPoolStr(fpc->pool, fp->subDirId);
371 lensubDir = rpmstrPoolStrlen(fpc->pool, fp->subDirId);
372 current_fp = *fp;
373
374 /* Set baseName to the upper most dir */
375 bnStart = bnEnd = 1;
376 while (bnEnd < lensubDir && currentsubdir[bnEnd] != '/')
377 bnEnd++;
378 /* no subDir for now */
379 current_fp.subDirId = 0;
380
381 while (bnEnd < lensubDir) {
382 current_fp.baseNameId = rpmstrPoolIdn(fpc->pool,
383 currentsubdir + bnStart,
384 bnEnd - bnStart, 1);
385
386 rpmFpHashGetEntry(symlinks, ¤t_fp, &recs, &numRecs, NULL);
387
388 for (i = 0; i < numRecs; i++) {
389 rpmfiles foundfi = rpmteFiles(recs[i].p);
390 char const *linktarget = rpmfilesFLink(foundfi, recs[i].fileno);
391 char *link;
392 rpmsid linkId;
393
394 foundfi = rpmfilesFree(foundfi);
395
396 if (!linktarget || *linktarget == '\0')
397 continue;
398
399 /* this "directory" will be symlink */
400 link = NULL;
401 if (*linktarget != '/') {
402 const char *dn, *subDir = NULL;
403 dn = rpmstrPoolStr(fpc->pool, current_fp.entry->dirId);
404 if (current_fp.subDirId) {
405 subDir = rpmstrPoolStr(fpc->pool, current_fp.subDirId);
406 }
407 rstrscat(&link, dn, subDir ? subDir : "", "/", NULL);
408 }
409 rstrscat(&link, linktarget, "/", NULL);
410 if (currentsubdir[bnEnd])
411 rstrscat(&link, currentsubdir + bnEnd, NULL);
412 linkId = rpmstrPoolId(fpc->pool, link, 1);
413 free(link);
414
415 /* this modifies the fingerprint! */
416 doLookupId(fpc, linkId, fp->baseNameId, fp);
417 found = 1;
418 break;
419 }
420
421 if (found)
422 break;
423
424 /* Set former baseName as subDir */
425 bnEnd++;
426 current_fp.subDirId = rpmstrPoolIdn(fpc->pool, currentsubdir, bnEnd, 1);
427
428 /* set baseName to the next lower dir */
429 bnStart = bnEnd;
430 while (bnEnd < lensubDir && currentsubdir[bnEnd] != '/')
431 bnEnd++;
432 }
433
434 if (!found)
435 break; /* no symlink found, we are done */
436
437 if (++symlinkcount > 50) {
438 /* we followed too many symlinks, there is most likely a cycle */
439 /* TODO: warning/error */
440 break;
441 }
442 }
443 }
444
fpCacheGetByFp(fingerPrintCache cache,struct fingerPrint_s * fp,int ix,struct rpmffi_s ** recs,int * numRecs)445 fingerPrint * fpCacheGetByFp(fingerPrintCache cache,
446 struct fingerPrint_s * fp, int ix,
447 struct rpmffi_s ** recs, int * numRecs)
448 {
449 if (rpmFpHashGetEntry(cache->fp, fp + ix, recs, numRecs, NULL))
450 return fp + ix;
451 else
452 return NULL;
453 }
454
fpCachePopulate(fingerPrintCache fpc,rpmts ts,int fileCount)455 void fpCachePopulate(fingerPrintCache fpc, rpmts ts, int fileCount)
456 {
457 rpmtsi pi;
458 rpmte p;
459 rpmfs fs;
460 rpmfiles fi;
461 int i, fc;
462 int havesymlinks = 0;
463
464 if (fpc->fp == NULL)
465 fpc->fp = rpmFpHashCreate(fileCount/2 + 10001, fpHashFunction, fpEqual,
466 NULL, NULL);
467
468 rpmFpHash symlinks = rpmFpHashCreate(fileCount/16+16, fpHashFunction, fpEqual, NULL, NULL);
469
470 /* populate the fingerprints of all packages in the transaction */
471 /* also create a hash of all symlinks in the new packages */
472 pi = rpmtsiInit(ts);
473 while ((p = rpmtsiNext(pi, 0)) != NULL) {
474 (void) rpmsqPoll();
475
476 if ((fi = rpmteFiles(p)) == NULL)
477 continue;
478
479 (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), 0);
480 rpmfilesFpLookup(fi, fpc);
481 fs = rpmteGetFileStates(p);
482 fc = rpmfsFC(fs);
483
484 if (rpmteType(p) != TR_REMOVED) {
485 fingerPrint *fpList = rpmfilesFps(fi);
486 /* collect symbolic links */
487 for (i = 0; i < fc; i++) {
488 struct rpmffi_s ffi;
489 char const *linktarget;
490 if (XFA_SKIPPING(rpmfsGetAction(fs, i)))
491 continue;
492 linktarget = rpmfilesFLink(fi, i);
493 if (!(linktarget && *linktarget != '\0'))
494 continue;
495 ffi.p = p;
496 ffi.fileno = i;
497 rpmFpHashAddEntry(symlinks, fpList + i, ffi);
498 havesymlinks = 1;
499 }
500 }
501
502 (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), fc);
503 rpmfilesFree(fi);
504 }
505 rpmtsiFree(pi);
506
507 /* ===============================================
508 * Create the fingerprint -> (p, fileno) hash table
509 * Also adapt the fingerprint if we have symlinks
510 */
511 pi = rpmtsiInit(ts);
512 while ((p = rpmtsiNext(pi, 0)) != NULL) {
513 fingerPrint *fpList, *lastfp = NULL;
514 (void) rpmsqPoll();
515
516 if ((fi = rpmteFiles(p)) == NULL)
517 continue;
518
519 fs = rpmteGetFileStates(p);
520 fc = rpmfsFC(fs);
521 fpList = rpmfilesFps(fi);
522 (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), 0);
523 for (i = 0; i < fc; i++) {
524 struct rpmffi_s ffi;
525 if (XFA_SKIPPING(rpmfsGetAction(fs, i)))
526 continue;
527 if (havesymlinks) {
528 /* if the entry/subdirid matches the one from the
529 * last entry we do not need to call fpLookupSubdir */
530 if (!lastfp || lastfp->entry != fpList[i].entry ||
531 lastfp->subDirId != fpList[i].subDirId)
532 fpLookupSubdir(symlinks, fpc, fpList + i);
533 }
534 ffi.p = p;
535 ffi.fileno = i;
536 rpmFpHashAddEntry(fpc->fp, fpList + i, ffi);
537 lastfp = fpList + i;
538 }
539 (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_FINGERPRINT), 0);
540 rpmfilesFree(fi);
541 }
542 rpmtsiFree(pi);
543
544 rpmFpHashFree(symlinks);
545 }
546
547