From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp56.i.mail.ru (smtp56.i.mail.ru [217.69.128.36]) (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 E702E469710 for ; Thu, 21 May 2020 17:37:32 +0300 (MSK) From: "Timur Safin" References: In-Reply-To: Date: Thu, 21 May 2020 17:37:31 +0300 Message-ID: <402201d62f7d$5c64b690$152e23b0$@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Language: ru Subject: Re: [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: 'Vladislav Shpilevoy' , tarantool-patches@dev.tarantool.org, gorcunov@gmail.com, alyapunov@tarantool.org LGTM, also : -----Original Message----- : From: Vladislav Shpilevoy : Sent: Saturday, May 16, 2020 2:04 AM : To: tarantool-patches@dev.tarantool.org; tsafin@tarantool.org; : gorcunov@gmail.com; alyapunov@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)