From f2b7bc23df842c3f6cd6a477a500590076a3839e Mon Sep 17 00:00:00 2001
From: Ralph Boehme <slow@samba.org>
Date: Sat, 1 Jul 2017 22:21:26 +0200
Subject: [PATCH] tbd: BUCKET(-1) returns wrong offset because tdb->hash_size
 is an unsigned int

The following C program demonstrates the issue:

  #include <stdio.h>
  #include <stdlib.h>
  #include <stdarg.h>
  #include <stdbool.h>
  #include <string.h>
  #include <unistd.h>
  #include <errno.h>
  #include <dirent.h>
  #include <sys/types.h>

  int main(int argc, char **argv)
  {
      int hash = -1;
      int tsize_signed = 10;
      unsigned int tsize_unsigned = 10;
      int bucket;

  #define BUCKET(hash, tsize) ((hash) % (tsize))

      bucket = BUCKET(hash, tsize_unsigned);
      printf("hash [%d] tsize [%d] bucket [%d]\n", hash, tsize_unsigned, bucket);

      bucket = BUCKET(hash, tsize_signed);
      printf("hash [%d] tsize [%d] bucket [%d]\n", hash, tsize_signed, bucket);

      return 0;
  }

Output:

$ ./tmp
hash [-1] tsize [10] bucket [5]
hash [-1] tsize [10] bucket [-1]

The first version is what the current BUCKET() macro does. As a result
we lock the hashtable chain in bucket 5, NOT the freelist.

-1 is sign converted to an unsigned int 4294967295 and

  4294967295 % 10 = 5.

As all callers will lock the same wrong list consistently locking is
still consistent.

Stumpled across this when looking at the output of `tdbtool DB list`
which always printed some other hashchain and not the freelist.

The freelist bucket offset computation doesn't use the BUCKET macro in
freelist.c (directly or indirectly) when working on the freelist, it
just directly uses the FREELIST_TOP define, so this problem only affects
tdbtool list.

Signed-off-by: Ralph Boehme <slow@samba.org>
Reviewed-by: Jeremy Allison <jra@samba.org>
---
 lib/tdb/common/tdb_private.h | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/lib/tdb/common/tdb_private.h b/lib/tdb/common/tdb_private.h
index e549af207ab..eeac10a49ad 100644
--- a/lib/tdb/common/tdb_private.h
+++ b/lib/tdb/common/tdb_private.h
@@ -126,6 +126,22 @@ void tdb_trace_2rec_retrec(struct tdb_context *tdb, const char *op,
 #define SAFE_FREE(x) do { if ((x) != NULL) {free(x); (x)=NULL;} } while(0)
 #endif
 
+/*
+ * Note: the BUCKET macro is broken as it returns an unexpected result when
+ * called as BUCKET(-1) for the freelist:
+ *
+ * -1 is sign converted to an unsigned int 4294967295 and then the modulo
+ * tdb->hashtable_size is computed. So with a hashtable_size of 10 the result
+ * is
+ *
+ *   4294967295 % hashtable_size = 5.
+ *
+ * where it should be -1 (C uses symmetric modulo).
+ *
+ * As all callers will lock the same wrong list consistently locking is still
+ * consistent. We can not change this without an incompatible on-disk format
+ * change, otherwise different tdb versions would use incompatible locking.
+ */
 #define BUCKET(hash) ((hash) % tdb->hash_size)
 
 #define DOCONV() (tdb->flags & TDB_CONVERT)
-- 
2.34.1