[Tarantool-patches] [PATCH 1/2] bit: fix unaligned memory access and UB bit shift
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Sat May 16 02:03:49 MSK 2020
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)
More information about the Tarantool-patches
mailing list