[Tarantool-patches] [PATCH 1/2] bit: fix unaligned memory access and UB bit shift
Timur Safin
tsafin at tarantool.org
Thu May 21 17:37:31 MSK 2020
LGTM, also
: -----Original Message-----
: From: Vladislav Shpilevoy <v.shpilevoy at tarantool.org>
: Sent: Saturday, May 16, 2020 2:04 AM
: To: tarantool-patches at dev.tarantool.org; tsafin at tarantool.org;
: gorcunov at gmail.com; alyapunov at tarantool.org
: Subject: [PATCH 1/2] bit: fix unaligned memory access and UB bit shift
:
: 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