From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp46.i.mail.ru (smtp46.i.mail.ru [94.100.177.106]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 22B07469711 for ; Sat, 16 May 2020 02:03:53 +0300 (MSK) From: Vladislav Shpilevoy Date: Sat, 16 May 2020 01:03:49 +0200 Message-Id: In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH 1/2] bit: fix unaligned memory access and UB bit shift List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: tarantool-patches@dev.tarantool.org, tsafin@tarantool.org, gorcunov@gmail.com, alyapunov@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)