From 6cdfde50d3dd81e241cd6270057ac0757464f0e0 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Tue, 7 Nov 2017 20:09:04 -0800 Subject: [PATCH] fix handling of 64-bit ino_t The dev/inode hashing code used only four bytes of each inode number, and thus could malfunction: mkid: warning: `f1' and `f1' are the same file, but yield different scans! * libidu/walker.c (dev_ino_hash_1, dev_ino_hash_2): Adjust to use all bytes of device and inode numbers. * NEWS (Bugs): Mention it. Reported by Curt McDowell in https://bugs.gnu.org/29092 --- NEWS | 4 ++++ libidu/walker.c | 45 +++++++++++++++++++++++++++++---------------- 2 files changed, 33 insertions(+), 16 deletions(-) diff --git a/NEWS b/NEWS index 81d19b1..5a8e979 100644 --- a/NEWS +++ b/NEWS @@ -6,6 +6,10 @@ GNU idutils NEWS -*- outline -*- lid is no longer susceptible to a buffer overrun + mkid no longer mistakenly warns that different files are the same but + with "different scans" for files with colliding 64-bit inode numbers + [the bug dates back to the initial implementation] + * Noteworthy changes in release 4.6 (2012-02-03) [stable] diff --git a/libidu/walker.c b/libidu/walker.c index e332305..82a2392 100644 --- a/libidu/walker.c +++ b/libidu/walker.c @@ -1107,23 +1107,36 @@ links_depth (struct file_link const *flink) /****************************************************************************/ /* Hash stuff for `struct dev_ino'. */ -static unsigned long -dev_ino_hash_1 (void const *key) -{ - unsigned long result = 0; - INTEGER_HASH_1 (((struct dev_ino const *) key)->di_dev, result); - INTEGER_HASH_1 (((struct dev_ino const *) key)->di_ino, result); - return result; -} - -static unsigned long -dev_ino_hash_2 (void const *key) -{ - unsigned long result = 0; - INTEGER_HASH_2 (((struct dev_ino const *) key)->di_dev, result); - INTEGER_HASH_2 (((struct dev_ino const *) key)->di_ino, result); - return result; +/* FIXME: consider dumping all of this in favor of gnulib's di-set module. */ +/* Expand to the definition of a function that hashes a dev+inode pair, + with application of XFORM. */ +#define DEV_INO_HASH_DEFUN(FN_NAME, XFORM) \ +static size_t _GL_ATTRIBUTE_PURE \ +FN_NAME (void const *x) \ +{ \ + struct dev_ino const *p = x; \ + ino_t ino = p->di_ino; \ + \ + /* When INO is wider than size_t, XOR the words of INO into H. \ + This avoids loss of info, without applying % to the wider type, \ + which could be quite slow on some systems. */ \ + size_t h = XFORM (ino); \ + unsigned int n_words = sizeof ino / sizeof h + (sizeof ino % sizeof h != 0); \ + for (unsigned int i = 1; i < n_words; i++) \ + h ^= XFORM (ino >> CHAR_BIT * sizeof h * i); \ + \ + dev_t dev = p->di_dev; \ + h ^= XFORM (dev); \ + n_words = sizeof dev / sizeof h + (sizeof dev % sizeof h != 0); \ + for (unsigned int i = 1; i < n_words; i++) \ + h ^= XFORM (dev >> CHAR_BIT * sizeof h * i); \ + \ + return h; \ } +static inline size_t xform_NOP (size_t k) { return k; } +static inline size_t xform_NOT (size_t k) { return ~k; } +DEV_INO_HASH_DEFUN(dev_ino_hash_1, xform_NOP) +DEV_INO_HASH_DEFUN(dev_ino_hash_2, xform_NOT) static int dev_ino_hash_compare (void const *x, void const *y) -- 2.15.1.354.g95ec6b1b3