From 30f3df060048ab516aa29a220505987829deb086 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 14 May 2019 10:48:15 -0400 Subject: [PATCH] Fix: bitfield: shift undefined/implementation defined behaviors MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit bitfield.h uses the left shift operator with a left operand which may be negative. The C99 standard states that shifting a negative value is undefined. When building with -Wshift-negative-value, we get this gcc warning: In file included from /home/smarchi/src/babeltrace/include/babeltrace/ctfser-internal.h:44:0, from /home/smarchi/src/babeltrace/ctfser/ctfser.c:42: /home/smarchi/src/babeltrace/include/babeltrace/ctfser-internal.h: In function ‘bt_ctfser_write_unsigned_int’: /home/smarchi/src/babeltrace/include/babeltrace/bitfield-internal.h:116:24: error: left shift of negative value [-Werror=shift-negative-value] mask = ~((~(type) 0) << (__start % ts)); \ ^ /home/smarchi/src/babeltrace/include/babeltrace/bitfield-internal.h:222:2: note: in expansion of macro ‘_bt_bitfield_write_le’ _bt_bitfield_write_le(ptr, type, _start, _length, _v) ^~~~~~~~~~~~~~~~~~~~~ /home/smarchi/src/babeltrace/include/babeltrace/ctfser-internal.h:418:3: note: in expansion of macro ‘bt_bitfield_write_le’ bt_bitfield_write_le(mmap_align_addr(ctfser->base_mma) + ^~~~~~~~~~~~~~~~~~~~ This boils down to the fact that the expression ~((uint8_t)0) has type "signed int", which is used as an operand of the left shift. This is due to the integer promotion rules of C99 (6.3.3.1): If an int can represent all values of the original type, the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. All other types are unchanged by the integer promotions. We also need to cast the result explicitly into the left hand side type to deal with: warning: large integer implicitly truncated to unsigned type [-Woverflow] The C99 standard states that a right shift has implementation-defined behavior when shifting a signed negative value. Add a preprocessor check that the compiler provides the expected behavior, else provide an alternative implementation which guarantees the intended behavior. A preprocessor check is also added to ensure that the compiler representation for signed values is two's complement, which is expected by this header. Document that this header strictly respects the C99 standard, with the exception of its use of __typeof__. Signed-off-by: Mathieu Desnoyers --- include/lttng/bitfield.h | 304 +++++++++++++++++++++++++++------------ 1 file changed, 209 insertions(+), 95 deletions(-) diff --git a/include/lttng/bitfield.h b/include/lttng/bitfield.h index ef5453c2..fe07824d 100644 --- a/include/lttng/bitfield.h +++ b/include/lttng/bitfield.h @@ -2,11 +2,7 @@ #define _BABELTRACE_BITFIELD_H /* - * BabelTrace - * - * Bitfields read/write functions. - * - * Copyright 2010 - Mathieu Desnoyers + * Copyright 2010-2019 - Mathieu Desnoyers * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -31,39 +27,157 @@ #include /* C99 5.2.4.2 Numerical limits */ #include /* Non-standard BIG_ENDIAN, LITTLE_ENDIAN, BYTE_ORDER */ -/* We can't shift a int from 32 bit, >> 32 and << 32 on int is undefined */ -#define _bt_piecewise_rshift(_v, _shift) \ -({ \ - __typeof__(_v) ___v = (_v); \ - __typeof__(_shift) ___shift = (_shift); \ - unsigned long sb = (___shift) / (sizeof(___v) * CHAR_BIT - 1); \ - unsigned long final = (___shift) % (sizeof(___v) * CHAR_BIT - 1); \ - \ - for (; sb; sb--) \ - ___v >>= sizeof(___v) * CHAR_BIT - 1; \ - ___v >>= final; \ -}) - -#define _bt_piecewise_lshift(_v, _shift) \ -({ \ - __typeof__(_v) ___v = (_v); \ - __typeof__(_shift) ___shift = (_shift); \ - unsigned long sb = (___shift) / (sizeof(___v) * CHAR_BIT - 1); \ - unsigned long final = (___shift) % (sizeof(___v) * CHAR_BIT - 1); \ - \ - for (; sb; sb--) \ - ___v <<= sizeof(___v) * CHAR_BIT - 1; \ - ___v <<= final; \ -}) +/* + * This header strictly follows the C99 standard, except for use of the + * compiler-specific __typeof__. + */ + +/* + * This bitfield header requires the compiler representation of signed + * integers to be two's complement. + */ +#if (-1 != ~0) +#error "bitfield.h requires the compiler representation of signed integers to be two's complement." +#endif #define _bt_is_signed_type(type) ((type) -1 < (type) 0) -#define _bt_unsigned_cast(type, v) \ -({ \ - (sizeof(v) < sizeof(type)) ? \ - ((type) (v)) & (~(~(type) 0 << (sizeof(v) * CHAR_BIT))) : \ - (type) (v); \ -}) +/* + * Produce a build-time error if the condition `cond` is non-zero. + * Evaluates as a size_t expression. + */ +#define _BT_BUILD_ASSERT(cond) \ + sizeof(struct { int f:(2 * !!(cond) - 1); }) + +/* + * Cast value `v` to an unsigned integer of the same size as `v`. + */ +#define _bt_cast_value_to_unsigned(v) \ + (sizeof(v) == sizeof(uint8_t) ? (uint8_t) (v) : \ + sizeof(v) == sizeof(uint16_t) ? (uint16_t) (v) : \ + sizeof(v) == sizeof(uint32_t) ? (uint32_t) (v) : \ + sizeof(v) == sizeof(uint64_t) ? (uint64_t) (v) : \ + _BT_BUILD_ASSERT(sizeof(v) <= sizeof(uint64_t))) + +/* + * Cast value `v` to an unsigned integer type of the size of type `type` + * *without* sign-extension. + * + * The unsigned cast ensures that we're not shifting a negative value, + * which is undefined in C. However, this limits the maximum type size + * of `type` to 64-bit. Generate a compile-time error if the size of + * `type` is larger than 64-bit. + */ +#define _bt_cast_value_to_unsigned_type(type, v) \ + (sizeof(type) == sizeof(uint8_t) ? \ + (uint8_t) _bt_cast_value_to_unsigned(v) : \ + sizeof(type) == sizeof(uint16_t) ? \ + (uint16_t) _bt_cast_value_to_unsigned(v) : \ + sizeof(type) == sizeof(uint32_t) ? \ + (uint32_t) _bt_cast_value_to_unsigned(v) : \ + sizeof(type) == sizeof(uint64_t) ? \ + (uint64_t) _bt_cast_value_to_unsigned(v) : \ + _BT_BUILD_ASSERT(sizeof(v) <= sizeof(uint64_t))) + +/* + * _bt_fill_mask evaluates to a "type" integer with all bits set. + */ +#define _bt_fill_mask(type) ((type) ~(type) 0) + +/* + * Left shift a value `v` of `shift` bits. + * + * The type of `v` can be signed or unsigned integer. + * The value of `shift` must be less than the size of `v` (in bits), + * otherwise the behavior is undefined. + * Evaluates to the result of the shift operation. + * + * According to the C99 standard, left shift of a left hand-side signed + * type is undefined if it has a negative value or if the result cannot + * be represented in the result type. This bitfield header discards the + * bits that are left-shifted beyond the result type representation, + * which is the behavior of an unsigned type left shift operation. + * Therefore, always perform left shift on an unsigned type. + * + * This macro should not be used if `shift` can be greater or equal than + * the bitwidth of `v`. See `_bt_safe_lshift`. + */ +#define _bt_lshift(v, shift) \ + ((__typeof__(v)) (_bt_cast_value_to_unsigned(v) << (shift))) + +/* + * Generate a mask of type `type` with the `length` least significant bits + * cleared, and the most significant bits set. + */ +#define _bt_make_mask_complement(type, length) \ + _bt_lshift(_bt_fill_mask(type), length) + +/* + * Generate a mask of type `type` with the `length` least significant bits + * set, and the most significant bits cleared. + */ +#define _bt_make_mask(type, length) \ + ((type) ~_bt_make_mask_complement(type, length)) + +/* + * Right shift a value `v` of `shift` bits. + * + * The type of `v` can be signed or unsigned integer. + * The value of `shift` must be less than the size of `v` (in bits), + * otherwise the behavior is undefined. + * Evaluates to the result of the shift operation. + * + * According to the C99 standard, right shift of a left hand-side signed + * type which has a negative value is implementation defined. This + * bitfield header relies on the right shift implementation carrying the + * sign bit. If the compiler implementation has a different behavior, + * emulate carrying the sign bit. + * + * This macro should not be used if `shift` can be greater or equal than + * the bitwidth of `v`. See `_bt_safe_rshift`. + */ +#if ((-1 >> 1) == -1) +#define _bt_rshift(v, shift) ((v) >> (shift)) +#else +#define _bt_rshift(v, shift) \ + ((__typeof__(v)) ((_bt_cast_value_to_unsigned(v) >> (shift)) | \ + ((v) < 0 ? _bt_make_mask_complement(__typeof__(v), \ + sizeof(v) * CHAR_BIT - (shift)) : 0))) +#endif + +/* + * Right shift a signed or unsigned integer with `shift` value being an + * arbitrary number of bits. `v` is modified by this macro. The shift + * is transformed into a sequence of `_nr_partial_shifts` consecutive + * shift operations, each of a number of bits smaller than the bitwidth + * of `v`, ending with a shift of the number of left over bits. + */ +#define _bt_safe_rshift(v, shift) \ +do { \ + unsigned long _nr_partial_shifts = (shift) / (sizeof(v) * CHAR_BIT - 1); \ + unsigned long _leftover_bits = (shift) % (sizeof(v) * CHAR_BIT - 1); \ + \ + for (; _nr_partial_shifts; _nr_partial_shifts--) \ + (v) = _bt_rshift(v, sizeof(v) * CHAR_BIT - 1); \ + (v) = _bt_rshift(v, _leftover_bits); \ +} while (0) + +/* + * Left shift a signed or unsigned integer with `shift` value being an + * arbitrary number of bits. `v` is modified by this macro. The shift + * is transformed into a sequence of `_nr_partial_shifts` consecutive + * shift operations, each of a number of bits smaller than the bitwidth + * of `v`, ending with a shift of the number of left over bits. + */ +#define _bt_safe_lshift(v, shift) \ +do { \ + unsigned long _nr_partial_shifts = (shift) / (sizeof(v) * CHAR_BIT - 1); \ + unsigned long _leftover_bits = (shift) % (sizeof(v) * CHAR_BIT - 1); \ + \ + for (; _nr_partial_shifts; _nr_partial_shifts--) \ + (v) = _bt_lshift(v, sizeof(v) * CHAR_BIT - 1); \ + (v) = _bt_lshift(v, _leftover_bits); \ +} while (0) /* * bt_bitfield_write - write integer to a bitfield in native endianness @@ -85,7 +199,7 @@ #define _bt_bitfield_write_le(_ptr, type, _start, _length, _v) \ do { \ - __typeof__(_v) __v = (_v); \ + __typeof__(_v) __v = (_v); \ type *__ptr = (void *) (_ptr); \ unsigned long __start = (_start), __length = (_length); \ type mask, cmask; \ @@ -102,15 +216,15 @@ do { \ \ /* Trim v high bits */ \ if (__length < sizeof(__v) * CHAR_BIT) \ - __v &= ~((~(__typeof__(__v)) 0) << __length); \ + __v &= _bt_make_mask(__typeof__(__v), __length); \ \ /* We can now append v with a simple "or", shift it piece-wise */ \ this_unit = start_unit; \ if (start_unit == end_unit - 1) { \ - mask = ~((~(type) 0) << (__start % ts)); \ + mask = _bt_make_mask(type, __start % ts); \ if (end % ts) \ - mask |= (~(type) 0) << (end % ts); \ - cmask = (type) __v << (__start % ts); \ + mask |= _bt_make_mask_complement(type, end % ts); \ + cmask = _bt_lshift((type) (__v), __start % ts); \ cmask &= ~mask; \ __ptr[this_unit] &= mask; \ __ptr[this_unit] |= cmask; \ @@ -118,22 +232,22 @@ do { \ } \ if (__start % ts) { \ cshift = __start % ts; \ - mask = ~((~(type) 0) << cshift); \ - cmask = (type) __v << cshift; \ + mask = _bt_make_mask(type, cshift); \ + cmask = _bt_lshift((type) (__v), cshift); \ cmask &= ~mask; \ __ptr[this_unit] &= mask; \ __ptr[this_unit] |= cmask; \ - __v = _bt_piecewise_rshift(__v, ts - cshift); \ + _bt_safe_rshift(__v, ts - cshift); \ __start += ts - cshift; \ this_unit++; \ } \ for (; this_unit < end_unit - 1; this_unit++) { \ __ptr[this_unit] = (type) __v; \ - __v = _bt_piecewise_rshift(__v, ts); \ + _bt_safe_rshift(__v, ts); \ __start += ts; \ } \ if (end % ts) { \ - mask = (~(type) 0) << (end % ts); \ + mask = _bt_make_mask_complement(type, end % ts); \ cmask = (type) __v; \ cmask &= ~mask; \ __ptr[this_unit] &= mask; \ @@ -144,7 +258,7 @@ do { \ #define _bt_bitfield_write_be(_ptr, type, _start, _length, _v) \ do { \ - __typeof__(_v) __v = (_v); \ + __typeof__(_v) __v = (_v); \ type *__ptr = (void *) (_ptr); \ unsigned long __start = (_start), __length = (_length); \ type mask, cmask; \ @@ -161,15 +275,15 @@ do { \ \ /* Trim v high bits */ \ if (__length < sizeof(__v) * CHAR_BIT) \ - __v &= ~((~(__typeof__(__v)) 0) << __length); \ + __v &= _bt_make_mask(__typeof__(__v), __length); \ \ /* We can now append v with a simple "or", shift it piece-wise */ \ this_unit = end_unit - 1; \ if (start_unit == end_unit - 1) { \ - mask = ~((~(type) 0) << ((ts - (end % ts)) % ts)); \ + mask = _bt_make_mask(type, (ts - (end % ts)) % ts); \ if (__start % ts) \ - mask |= (~((type) 0)) << (ts - (__start % ts)); \ - cmask = (type) __v << ((ts - (end % ts)) % ts); \ + mask |= _bt_make_mask_complement(type, ts - (__start % ts)); \ + cmask = _bt_lshift((type) (__v), (ts - (end % ts)) % ts); \ cmask &= ~mask; \ __ptr[this_unit] &= mask; \ __ptr[this_unit] |= cmask; \ @@ -177,22 +291,22 @@ do { \ } \ if (end % ts) { \ cshift = end % ts; \ - mask = ~((~(type) 0) << (ts - cshift)); \ - cmask = (type) __v << (ts - cshift); \ + mask = _bt_make_mask(type, ts - cshift); \ + cmask = _bt_lshift((type) (__v), ts - cshift); \ cmask &= ~mask; \ __ptr[this_unit] &= mask; \ __ptr[this_unit] |= cmask; \ - __v = _bt_piecewise_rshift(__v, cshift); \ + _bt_safe_rshift(__v, cshift); \ end -= cshift; \ this_unit--; \ } \ for (; (long) this_unit >= (long) start_unit + 1; this_unit--) { \ __ptr[this_unit] = (type) __v; \ - __v = _bt_piecewise_rshift(__v, ts); \ + _bt_safe_rshift(__v, ts); \ end -= ts; \ } \ if (__start % ts) { \ - mask = (~(type) 0) << (ts - (__start % ts)); \ + mask = _bt_make_mask_complement(type, ts - (__start % ts)); \ cmask = (type) __v; \ cmask &= ~mask; \ __ptr[this_unit] &= mask; \ @@ -214,7 +328,7 @@ do { \ #define bt_bitfield_write_le(ptr, type, _start, _length, _v) \ _bt_bitfield_write_le(ptr, type, _start, _length, _v) - + #define bt_bitfield_write_be(ptr, type, _start, _length, _v) \ _bt_bitfield_write_be(ptr, unsigned char, _start, _length, _v) @@ -225,7 +339,7 @@ do { \ #define bt_bitfield_write_le(ptr, type, _start, _length, _v) \ _bt_bitfield_write_le(ptr, unsigned char, _start, _length, _v) - + #define bt_bitfield_write_be(ptr, type, _start, _length, _v) \ _bt_bitfield_write_be(ptr, type, _start, _length, _v) @@ -238,7 +352,7 @@ do { \ #define _bt_bitfield_read_le(_ptr, type, _start, _length, _vptr) \ do { \ __typeof__(*(_vptr)) *__vptr = (_vptr); \ - __typeof__(*__vptr) __v; \ + __typeof__(*__vptr) __v; \ type *__ptr = (void *) (_ptr); \ unsigned long __start = (_start), __length = (_length); \ type mask, cmask; \ @@ -257,47 +371,47 @@ do { \ \ this_unit = end_unit - 1; \ if (_bt_is_signed_type(__typeof__(__v)) \ - && (__ptr[this_unit] & ((type) 1 << ((end % ts ? : ts) - 1)))) \ - __v = ~(__typeof__(__v)) 0; \ + && (__ptr[this_unit] & _bt_lshift((type) 1, (end % ts ? end % ts : ts) - 1))) \ + __v = ~(__typeof__(__v)) 0; \ else \ __v = 0; \ if (start_unit == end_unit - 1) { \ cmask = __ptr[this_unit]; \ - cmask >>= (__start % ts); \ + cmask = _bt_rshift(cmask, __start % ts); \ if ((end - __start) % ts) { \ - mask = ~((~(type) 0) << (end - __start)); \ + mask = _bt_make_mask(type, end - __start); \ cmask &= mask; \ } \ - __v = _bt_piecewise_lshift(__v, end - __start); \ - __v |= _bt_unsigned_cast(__typeof__(__v), cmask); \ + _bt_safe_lshift(__v, end - __start); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), cmask); \ *__vptr = __v; \ break; \ } \ if (end % ts) { \ cshift = end % ts; \ - mask = ~((~(type) 0) << cshift); \ + mask = _bt_make_mask(type, cshift); \ cmask = __ptr[this_unit]; \ cmask &= mask; \ - __v = _bt_piecewise_lshift(__v, cshift); \ - __v |= _bt_unsigned_cast(__typeof__(__v), cmask); \ + _bt_safe_lshift(__v, cshift); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), cmask); \ end -= cshift; \ this_unit--; \ } \ for (; (long) this_unit >= (long) start_unit + 1; this_unit--) { \ - __v = _bt_piecewise_lshift(__v, ts); \ - __v |= _bt_unsigned_cast(__typeof__(__v), __ptr[this_unit]);\ + _bt_safe_lshift(__v, ts); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), __ptr[this_unit]); \ end -= ts; \ } \ if (__start % ts) { \ - mask = ~((~(type) 0) << (ts - (__start % ts))); \ + mask = _bt_make_mask(type, ts - (__start % ts)); \ cmask = __ptr[this_unit]; \ - cmask >>= (__start % ts); \ + cmask = _bt_rshift(cmask, __start % ts); \ cmask &= mask; \ - __v = _bt_piecewise_lshift(__v, ts - (__start % ts)); \ - __v |= _bt_unsigned_cast(__typeof__(__v), cmask); \ + _bt_safe_lshift(__v, ts - (__start % ts)); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), cmask); \ } else { \ - __v = _bt_piecewise_lshift(__v, ts); \ - __v |= _bt_unsigned_cast(__typeof__(__v), __ptr[this_unit]);\ + _bt_safe_lshift(__v, ts); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), __ptr[this_unit]); \ } \ *__vptr = __v; \ } while (0) @@ -305,7 +419,7 @@ do { \ #define _bt_bitfield_read_be(_ptr, type, _start, _length, _vptr) \ do { \ __typeof__(*(_vptr)) *__vptr = (_vptr); \ - __typeof__(*__vptr) __v; \ + __typeof__(*__vptr) __v; \ type *__ptr = (void *) (_ptr); \ unsigned long __start = (_start), __length = (_length); \ type mask, cmask; \ @@ -324,47 +438,47 @@ do { \ \ this_unit = start_unit; \ if (_bt_is_signed_type(__typeof__(__v)) \ - && (__ptr[this_unit] & ((type) 1 << (ts - (__start % ts) - 1)))) \ - __v = ~(__typeof__(__v)) 0; \ + && (__ptr[this_unit] & _bt_lshift((type) 1, ts - (__start % ts) - 1))) \ + __v = ~(__typeof__(__v)) 0; \ else \ __v = 0; \ if (start_unit == end_unit - 1) { \ cmask = __ptr[this_unit]; \ - cmask >>= (ts - (end % ts)) % ts; \ + cmask = _bt_rshift(cmask, (ts - (end % ts)) % ts); \ if ((end - __start) % ts) { \ - mask = ~((~(type) 0) << (end - __start)); \ + mask = _bt_make_mask(type, end - __start); \ cmask &= mask; \ } \ - __v = _bt_piecewise_lshift(__v, end - __start); \ - __v |= _bt_unsigned_cast(__typeof__(__v), cmask); \ + _bt_safe_lshift(__v, end - __start); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), cmask); \ *__vptr = __v; \ break; \ } \ if (__start % ts) { \ cshift = __start % ts; \ - mask = ~((~(type) 0) << (ts - cshift)); \ + mask = _bt_make_mask(type, ts - cshift); \ cmask = __ptr[this_unit]; \ cmask &= mask; \ - __v = _bt_piecewise_lshift(__v, ts - cshift); \ - __v |= _bt_unsigned_cast(__typeof__(__v), cmask); \ + _bt_safe_lshift(__v, ts - cshift); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), cmask); \ __start += ts - cshift; \ this_unit++; \ } \ for (; this_unit < end_unit - 1; this_unit++) { \ - __v = _bt_piecewise_lshift(__v, ts); \ - __v |= _bt_unsigned_cast(__typeof__(__v), __ptr[this_unit]);\ + _bt_safe_lshift(__v, ts); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), __ptr[this_unit]); \ __start += ts; \ } \ if (end % ts) { \ - mask = ~((~(type) 0) << (end % ts)); \ + mask = _bt_make_mask(type, end % ts); \ cmask = __ptr[this_unit]; \ - cmask >>= ts - (end % ts); \ + cmask = _bt_rshift(cmask, ts - (end % ts)); \ cmask &= mask; \ - __v = _bt_piecewise_lshift(__v, end % ts); \ - __v |= _bt_unsigned_cast(__typeof__(__v), cmask); \ + _bt_safe_lshift(__v, end % ts); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), cmask); \ } else { \ - __v = _bt_piecewise_lshift(__v, ts); \ - __v |= _bt_unsigned_cast(__typeof__(__v), __ptr[this_unit]);\ + _bt_safe_lshift(__v, ts); \ + __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), __ptr[this_unit]); \ } \ *__vptr = __v; \ } while (0) @@ -382,7 +496,7 @@ do { \ #define bt_bitfield_read_le(_ptr, type, _start, _length, _vptr) \ _bt_bitfield_read_le(_ptr, type, _start, _length, _vptr) - + #define bt_bitfield_read_be(_ptr, type, _start, _length, _vptr) \ _bt_bitfield_read_be(_ptr, unsigned char, _start, _length, _vptr) @@ -393,7 +507,7 @@ do { \ #define bt_bitfield_read_le(_ptr, type, _start, _length, _vptr) \ _bt_bitfield_read_le(_ptr, unsigned char, _start, _length, _vptr) - + #define bt_bitfield_read_be(_ptr, type, _start, _length, _vptr) \ _bt_bitfield_read_be(_ptr, type, _start, _length, _vptr) -- 2.34.1