[Tarantool-patches] [PATCH 1/2] bit: fix unaligned memory access and UB bit shift

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

Lib/bit library in some functions dereferenced a byte array as a
pointer at uint64 or uint32. It led to unaligned memory access,
when the array didn't have the needed alignment. That made clang
'alignment' sanitizer crazy.

Also there were places, where bitwise shift was done for the type
size. For example, a uint32 number was allowed to make 32 bit
shift in both sides. This is undefined behaviour.

The patch fixes these UBs. Bitwise shift of too long size is
banned. Unaligned access is fixed in some places by changing
uint64 to uint8, when it is possible without perf loss. And in the
others by using explicitly specified unaligned load. So it works
the same, but the sanitizer is aware of that.

Part of #4609
---
 src/lib/bit/bit.h    |  30 +++++---
 test/unit/bit.c      |   4 +-
 test/unit/bit.result | 180 -------------------------------------------
 3 files changed, 21 insertions(+), 193 deletions(-)

diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
index b11034cb9..eb392b820 100644
--- a/src/lib/bit/bit.h
+++ b/src/lib/bit/bit.h
@@ -202,10 +202,10 @@ bitmap_size(size_t bit_count)
 inline bool
 bit_test(const void *data, size_t pos)
 {
-	size_t chunk = pos / (CHAR_BIT * sizeof(unsigned long));
-	size_t offset = pos % (CHAR_BIT * sizeof(unsigned long));
+	size_t chunk = pos / CHAR_BIT;
+	size_t offset = pos % CHAR_BIT;
 
-	const unsigned long *ldata = (const unsigned long  *) data;
+	const uint8_t *ldata = (const uint8_t *)data;
 	return (ldata[chunk] >> offset) & 0x1;
 }
 
@@ -222,10 +222,10 @@ bit_test(const void *data, size_t pos)
 inline bool
 bit_set(void *data, size_t pos)
 {
-	size_t chunk = pos / (CHAR_BIT * sizeof(unsigned long));
-	size_t offset = pos % (CHAR_BIT * sizeof(unsigned long));
+	size_t chunk = pos / CHAR_BIT;
+	size_t offset = pos % CHAR_BIT;
 
-	unsigned long *ldata = (unsigned long  *) data;
+	uint8_t *ldata = (uint8_t *)data;
 	bool prev = (ldata[chunk] >> offset) & 0x1;
 	ldata[chunk] |= (1UL << offset);
 	return prev;
@@ -244,10 +244,10 @@ bit_set(void *data, size_t pos)
 inline bool
 bit_clear(void *data, size_t pos)
 {
-	size_t chunk = pos / (CHAR_BIT * sizeof(unsigned long));
-	size_t offset = pos % (CHAR_BIT * sizeof(unsigned long));
+	size_t chunk = pos / CHAR_BIT;
+	size_t offset = pos % CHAR_BIT;
 
-	unsigned long *ldata = (unsigned long *) data;
+	uint8_t *ldata = (uint8_t *)data;
 	bool prev = (ldata[chunk] >> offset) & 0x1;
 	ldata[chunk] &= ~(1UL << offset);
 	return prev;
@@ -413,6 +413,7 @@ bit_count_u64(uint64_t x)
 inline uint32_t
 bit_rotl_u32(uint32_t x, int r)
 {
+	assert(r > 0 && r < 32);
 	/* gcc recognises this code and generates a rotate instruction */
 	return ((x << r) | (x >> (32 - r)));
 }
@@ -423,6 +424,7 @@ bit_rotl_u32(uint32_t x, int r)
 inline uint64_t
 bit_rotl_u64(uint64_t x, int r)
 {
+	assert(r > 0 && r < 64);
 	/* gcc recognises this code and generates a rotate instruction */
 	return ((x << r) | (x >> (64 - r)));
 }
@@ -433,6 +435,7 @@ bit_rotl_u64(uint64_t x, int r)
 __attribute__ ((const)) inline uintmax_t
 bit_rotl_umax(uintmax_t x, int r)
 {
+	assert(r > 0 && r < (int)(sizeof(uintmax_t) * CHAR_BIT));
 	/* gcc recognises this code and generates a rotate instruction */
 	return ((x << r) | (x >> (sizeof(uintmax_t) * CHAR_BIT - r)));
 }
@@ -446,6 +449,7 @@ bit_rotl_umax(uintmax_t x, int r)
 inline uint32_t
 bit_rotr_u32(uint32_t x, int r)
 {
+	assert(r > 0 && r < 32);
 	/* gcc recognises this code and generates a rotate instruction */
 	return ((x >> r) | (x << (32 - r)));
 }
@@ -456,6 +460,7 @@ bit_rotr_u32(uint32_t x, int r)
 inline uint64_t
 bit_rotr_u64(uint64_t x, int r)
 {
+	assert(r > 0 && r < 64);
 	/* gcc recognises this code and generates a rotate instruction */
 	return ((x >> r) | (x << (64 - r)));
 }
@@ -538,9 +543,11 @@ bit_index_u64(uint64_t x, int *indexes, int offset);
 /* Use bigger words on x86_64 */
 #define ITER_UINT uint64_t
 #define ITER_CTZ bit_ctz_u64
+#define ITER_LOAD load_u64
 #else
 #define ITER_UINT uint32_t
 #define ITER_CTZ bit_ctz_u32
+#define ITER_LOAD load_u32
 #endif
 /** @endcond **/
 
@@ -589,7 +596,7 @@ bit_iterator_init(struct bit_iterator *it, const void *data, size_t size,
 	/* Check if size is a multiple of sizeof(ITER_UINT) */
 	const char *e = it->next + size % sizeof(ITER_UINT);
 	if (bit_likely(it->next == e)) {
-		it->word = *(ITER_UINT *) it->next;
+		it->word = ITER_LOAD(it->next);
 		it->next += sizeof(ITER_UINT);
 	} else {
 		it->word = it->word_xor;
@@ -615,7 +622,7 @@ bit_iterator_next(struct bit_iterator *it)
 			return SIZE_MAX;
 
 		/* Extract the next word from memory */
-		it->word = *(ITER_UINT *) it->next;
+		it->word = ITER_LOAD(it->next);
 		it->word ^= it->word_xor;
 		it->word_base = (it->next - it->start) * CHAR_BIT;
 		it->next += sizeof(ITER_UINT);
@@ -629,6 +636,7 @@ bit_iterator_next(struct bit_iterator *it)
 	return it->word_base + bit;
 }
 
+#undef ITER_LOAD
 #undef ITER_CTZ
 #undef ITER_UINT
 
diff --git a/test/unit/bit.c b/test/unit/bit.c
index da514484d..1dae3671c 100644
--- a/test/unit/bit.c
+++ b/test/unit/bit.c
@@ -80,7 +80,7 @@ test_rotl_rotr_one(int rot)
 		printf("bit_rotr_u64(%" PRIu64 ", %d) => %" PRIu64 "\n",
 		       val64, rot, bit_rotr_u64(val64, rot));
 
-		if (vals[i] > UINT32_MAX || rot > 32)
+		if (vals[i] > UINT32_MAX || rot >= 32)
 			continue;
 
 		printf("bit_rotl_u32(%" PRIu32 ", %d) => %" PRIu32 "\n",
@@ -95,7 +95,7 @@ test_rotl_rotr(void)
 {
 	header();
 
-	int rots[] = { 0, 1, 15, 16, 31, 32, 63, 64 };
+	int rots[] = { 1, 15, 16, 31, 32, 63 };
 	for (unsigned r = 0; r < sizeof(rots) / sizeof(rots[0]); r++) {
 		test_rotl_rotr_one(rots[r]);
 	}
diff --git a/test/unit/bit.result b/test/unit/bit.result
index 2d4ccc6f4..cfce9f532 100644
--- a/test/unit/bit.result
+++ b/test/unit/bit.result
@@ -134,96 +134,6 @@ bit_count_u64(15984546468465238145) => 25
 bit_count_u64(18446744073709551615) => 64
 	*** test_count: done ***
 	*** test_rotl_rotr ***
-bit_rotl_u64(0, 0) => 0
-bit_rotr_u64(0, 0) => 0
-bit_rotl_u32(0, 0) => 0
-bit_rotr_u32(0, 0) => 0
-bit_rotl_u64(1, 0) => 1
-bit_rotr_u64(1, 0) => 1
-bit_rotl_u32(1, 0) => 1
-bit_rotr_u32(1, 0) => 1
-bit_rotl_u64(2, 0) => 2
-bit_rotr_u64(2, 0) => 2
-bit_rotl_u32(2, 0) => 2
-bit_rotr_u32(2, 0) => 2
-bit_rotl_u64(32768, 0) => 32768
-bit_rotr_u64(32768, 0) => 32768
-bit_rotl_u32(32768, 0) => 32768
-bit_rotr_u32(32768, 0) => 32768
-bit_rotl_u64(65535, 0) => 65535
-bit_rotr_u64(65535, 0) => 65535
-bit_rotl_u32(65535, 0) => 65535
-bit_rotr_u32(65535, 0) => 65535
-bit_rotl_u64(65536, 0) => 65536
-bit_rotr_u64(65536, 0) => 65536
-bit_rotl_u32(65536, 0) => 65536
-bit_rotr_u32(65536, 0) => 65536
-bit_rotl_u64(726075912, 0) => 726075912
-bit_rotr_u64(726075912, 0) => 726075912
-bit_rotl_u32(726075912, 0) => 726075912
-bit_rotr_u32(726075912, 0) => 726075912
-bit_rotl_u64(858993459, 0) => 858993459
-bit_rotr_u64(858993459, 0) => 858993459
-bit_rotl_u32(858993459, 0) => 858993459
-bit_rotr_u32(858993459, 0) => 858993459
-bit_rotl_u64(1073741824, 0) => 1073741824
-bit_rotr_u64(1073741824, 0) => 1073741824
-bit_rotl_u32(1073741824, 0) => 1073741824
-bit_rotr_u32(1073741824, 0) => 1073741824
-bit_rotl_u64(1245250552, 0) => 1245250552
-bit_rotr_u64(1245250552, 0) => 1245250552
-bit_rotl_u32(1245250552, 0) => 1245250552
-bit_rotr_u32(1245250552, 0) => 1245250552
-bit_rotl_u64(1431655765, 0) => 1431655765
-bit_rotr_u64(1431655765, 0) => 1431655765
-bit_rotl_u32(1431655765, 0) => 1431655765
-bit_rotr_u32(1431655765, 0) => 1431655765
-bit_rotl_u64(1656977767, 0) => 1656977767
-bit_rotr_u64(1656977767, 0) => 1656977767
-bit_rotl_u32(1656977767, 0) => 1656977767
-bit_rotr_u32(1656977767, 0) => 1656977767
-bit_rotl_u64(2147483648, 0) => 2147483648
-bit_rotr_u64(2147483648, 0) => 2147483648
-bit_rotl_u32(2147483648, 0) => 2147483648
-bit_rotr_u32(2147483648, 0) => 2147483648
-bit_rotl_u64(2283114629, 0) => 2283114629
-bit_rotr_u64(2283114629, 0) => 2283114629
-bit_rotl_u32(2283114629, 0) => 2283114629
-bit_rotr_u32(2283114629, 0) => 2283114629
-bit_rotl_u64(2502548245, 0) => 2502548245
-bit_rotr_u64(2502548245, 0) => 2502548245
-bit_rotl_u32(2502548245, 0) => 2502548245
-bit_rotr_u32(2502548245, 0) => 2502548245
-bit_rotl_u64(4294967295, 0) => 4294967295
-bit_rotr_u64(4294967295, 0) => 4294967295
-bit_rotl_u32(4294967295, 0) => 4294967295
-bit_rotr_u32(4294967295, 0) => 4294967295
-bit_rotl_u64(708915120906848425, 0) => 708915120906848425
-bit_rotr_u64(708915120906848425, 0) => 708915120906848425
-bit_rotl_u64(1960191741125985428, 0) => 1960191741125985428
-bit_rotr_u64(1960191741125985428, 0) => 1960191741125985428
-bit_rotl_u64(3689348814741910323, 0) => 3689348814741910323
-bit_rotr_u64(3689348814741910323, 0) => 3689348814741910323
-bit_rotl_u64(5578377670650038654, 0) => 5578377670650038654
-bit_rotr_u64(5578377670650038654, 0) => 5578377670650038654
-bit_rotl_u64(9223372036854775808, 0) => 9223372036854775808
-bit_rotr_u64(9223372036854775808, 0) => 9223372036854775808
-bit_rotl_u64(10755112315580060033, 0) => 10755112315580060033
-bit_rotr_u64(10755112315580060033, 0) => 10755112315580060033
-bit_rotl_u64(11163782031541429823, 0) => 11163782031541429823
-bit_rotr_u64(11163782031541429823, 0) => 11163782031541429823
-bit_rotl_u64(13903686156871869732, 0) => 13903686156871869732
-bit_rotr_u64(13903686156871869732, 0) => 13903686156871869732
-bit_rotl_u64(14237897302422917095, 0) => 14237897302422917095
-bit_rotr_u64(14237897302422917095, 0) => 14237897302422917095
-bit_rotl_u64(14302190498657618739, 0) => 14302190498657618739
-bit_rotr_u64(14302190498657618739, 0) => 14302190498657618739
-bit_rotl_u64(15766411510232741269, 0) => 15766411510232741269
-bit_rotr_u64(15766411510232741269, 0) => 15766411510232741269
-bit_rotl_u64(15984546468465238145, 0) => 15984546468465238145
-bit_rotr_u64(15984546468465238145, 0) => 15984546468465238145
-bit_rotl_u64(18446744073709551615, 0) => 18446744073709551615
-bit_rotr_u64(18446744073709551615, 0) => 18446744073709551615
 bit_rotl_u64(0, 1) => 0
 bit_rotr_u64(0, 1) => 0
 bit_rotl_u32(0, 1) => 0
@@ -586,68 +496,36 @@ bit_rotl_u64(18446744073709551615, 31) => 18446744073709551615
 bit_rotr_u64(18446744073709551615, 31) => 18446744073709551615
 bit_rotl_u64(0, 32) => 0
 bit_rotr_u64(0, 32) => 0
-bit_rotl_u32(0, 32) => 0
-bit_rotr_u32(0, 32) => 0
 bit_rotl_u64(1, 32) => 4294967296
 bit_rotr_u64(1, 32) => 4294967296
-bit_rotl_u32(1, 32) => 1
-bit_rotr_u32(1, 32) => 1
 bit_rotl_u64(2, 32) => 8589934592
 bit_rotr_u64(2, 32) => 8589934592
-bit_rotl_u32(2, 32) => 2
-bit_rotr_u32(2, 32) => 2
 bit_rotl_u64(32768, 32) => 140737488355328
 bit_rotr_u64(32768, 32) => 140737488355328
-bit_rotl_u32(32768, 32) => 32768
-bit_rotr_u32(32768, 32) => 32768
 bit_rotl_u64(65535, 32) => 281470681743360
 bit_rotr_u64(65535, 32) => 281470681743360
-bit_rotl_u32(65535, 32) => 65535
-bit_rotr_u32(65535, 32) => 65535
 bit_rotl_u64(65536, 32) => 281474976710656
 bit_rotr_u64(65536, 32) => 281474976710656
-bit_rotl_u32(65536, 32) => 65536
-bit_rotr_u32(65536, 32) => 65536
 bit_rotl_u64(726075912, 32) => 3118472296453373952
 bit_rotr_u64(726075912, 32) => 3118472296453373952
-bit_rotl_u32(726075912, 32) => 726075912
-bit_rotr_u32(726075912, 32) => 726075912
 bit_rotl_u64(858993459, 32) => 3689348813882916864
 bit_rotr_u64(858993459, 32) => 3689348813882916864
-bit_rotl_u32(858993459, 32) => 858993459
-bit_rotr_u32(858993459, 32) => 858993459
 bit_rotl_u64(1073741824, 32) => 4611686018427387904
 bit_rotr_u64(1073741824, 32) => 4611686018427387904
-bit_rotl_u32(1073741824, 32) => 1073741824
-bit_rotr_u32(1073741824, 32) => 1073741824
 bit_rotl_u64(1245250552, 32) => 5348310396165947392
 bit_rotr_u64(1245250552, 32) => 5348310396165947392
-bit_rotl_u32(1245250552, 32) => 1245250552
-bit_rotr_u32(1245250552, 32) => 1245250552
 bit_rotl_u64(1431655765, 32) => 6148914689804861440
 bit_rotr_u64(1431655765, 32) => 6148914689804861440
-bit_rotl_u32(1431655765, 32) => 1431655765
-bit_rotr_u32(1431655765, 32) => 1431655765
 bit_rotl_u64(1656977767, 32) => 7116665319464108032
 bit_rotr_u64(1656977767, 32) => 7116665319464108032
-bit_rotl_u32(1656977767, 32) => 1656977767
-bit_rotr_u32(1656977767, 32) => 1656977767
 bit_rotl_u64(2147483648, 32) => 9223372036854775808
 bit_rotr_u64(2147483648, 32) => 9223372036854775808
-bit_rotl_u32(2147483648, 32) => 2147483648
-bit_rotr_u32(2147483648, 32) => 2147483648
 bit_rotl_u64(2283114629, 32) => 9805902664574173184
 bit_rotr_u64(2283114629, 32) => 9805902664574173184
-bit_rotl_u32(2283114629, 32) => 2283114629
-bit_rotr_u32(2283114629, 32) => 2283114629
 bit_rotl_u64(2502548245, 32) => 10748362868937195520
 bit_rotr_u64(2502548245, 32) => 10748362868937195520
-bit_rotl_u32(2502548245, 32) => 2502548245
-bit_rotr_u32(2502548245, 32) => 2502548245
 bit_rotl_u64(4294967295, 32) => 18446744069414584320
 bit_rotr_u64(4294967295, 32) => 18446744069414584320
-bit_rotl_u32(4294967295, 32) => 4294967295
-bit_rotr_u32(4294967295, 32) => 4294967295
 bit_rotl_u64(708915120906848425, 32) => 16541238372230140555
 bit_rotr_u64(708915120906848425, 32) => 16541238372230140555
 bit_rotl_u64(1960191741125985428, 32) => 14229128056835145728
@@ -732,64 +610,6 @@ bit_rotl_u64(15984546468465238145, 63) => 17215645271087394880
 bit_rotr_u64(15984546468465238145, 63) => 13522348863220924675
 bit_rotl_u64(18446744073709551615, 63) => 18446744073709551615
 bit_rotr_u64(18446744073709551615, 63) => 18446744073709551615
-bit_rotl_u64(0, 64) => 0
-bit_rotr_u64(0, 64) => 0
-bit_rotl_u64(1, 64) => 1
-bit_rotr_u64(1, 64) => 1
-bit_rotl_u64(2, 64) => 2
-bit_rotr_u64(2, 64) => 2
-bit_rotl_u64(32768, 64) => 32768
-bit_rotr_u64(32768, 64) => 32768
-bit_rotl_u64(65535, 64) => 65535
-bit_rotr_u64(65535, 64) => 65535
-bit_rotl_u64(65536, 64) => 65536
-bit_rotr_u64(65536, 64) => 65536
-bit_rotl_u64(726075912, 64) => 726075912
-bit_rotr_u64(726075912, 64) => 726075912
-bit_rotl_u64(858993459, 64) => 858993459
-bit_rotr_u64(858993459, 64) => 858993459
-bit_rotl_u64(1073741824, 64) => 1073741824
-bit_rotr_u64(1073741824, 64) => 1073741824
-bit_rotl_u64(1245250552, 64) => 1245250552
-bit_rotr_u64(1245250552, 64) => 1245250552
-bit_rotl_u64(1431655765, 64) => 1431655765
-bit_rotr_u64(1431655765, 64) => 1431655765
-bit_rotl_u64(1656977767, 64) => 1656977767
-bit_rotr_u64(1656977767, 64) => 1656977767
-bit_rotl_u64(2147483648, 64) => 2147483648
-bit_rotr_u64(2147483648, 64) => 2147483648
-bit_rotl_u64(2283114629, 64) => 2283114629
-bit_rotr_u64(2283114629, 64) => 2283114629
-bit_rotl_u64(2502548245, 64) => 2502548245
-bit_rotr_u64(2502548245, 64) => 2502548245
-bit_rotl_u64(4294967295, 64) => 4294967295
-bit_rotr_u64(4294967295, 64) => 4294967295
-bit_rotl_u64(708915120906848425, 64) => 708915120906848425
-bit_rotr_u64(708915120906848425, 64) => 708915120906848425
-bit_rotl_u64(1960191741125985428, 64) => 1960191741125985428
-bit_rotr_u64(1960191741125985428, 64) => 1960191741125985428
-bit_rotl_u64(3689348814741910323, 64) => 3689348814741910323
-bit_rotr_u64(3689348814741910323, 64) => 3689348814741910323
-bit_rotl_u64(5578377670650038654, 64) => 5578377670650038654
-bit_rotr_u64(5578377670650038654, 64) => 5578377670650038654
-bit_rotl_u64(9223372036854775808, 64) => 9223372036854775808
-bit_rotr_u64(9223372036854775808, 64) => 9223372036854775808
-bit_rotl_u64(10755112315580060033, 64) => 10755112315580060033
-bit_rotr_u64(10755112315580060033, 64) => 10755112315580060033
-bit_rotl_u64(11163782031541429823, 64) => 11163782031541429823
-bit_rotr_u64(11163782031541429823, 64) => 11163782031541429823
-bit_rotl_u64(13903686156871869732, 64) => 13903686156871869732
-bit_rotr_u64(13903686156871869732, 64) => 13903686156871869732
-bit_rotl_u64(14237897302422917095, 64) => 14237897302422917095
-bit_rotr_u64(14237897302422917095, 64) => 14237897302422917095
-bit_rotl_u64(14302190498657618739, 64) => 14302190498657618739
-bit_rotr_u64(14302190498657618739, 64) => 14302190498657618739
-bit_rotl_u64(15766411510232741269, 64) => 15766411510232741269
-bit_rotr_u64(15766411510232741269, 64) => 15766411510232741269
-bit_rotl_u64(15984546468465238145, 64) => 15984546468465238145
-bit_rotr_u64(15984546468465238145, 64) => 15984546468465238145
-bit_rotl_u64(18446744073709551615, 64) => 18446744073709551615
-bit_rotr_u64(18446744073709551615, 64) => 18446744073709551615
 	*** test_rotl_rotr: done ***
 	*** test_bswap ***
 bswap_u64(0) => 0
-- 
2.21.1 (Apple Git-122.3)