[lttng-dev] [PATCH lttng-ust 1/2] Fix: bitfield: shift undefined/implementation defined behaviors
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Tue May 14 16:36:28 EDT 2019
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 <mathieu.desnoyers at efficios.com>
---
include/lttng/bitfield.h | 288 ++++++++++++++++++++++++++++++++---------------
1 file changed, 195 insertions(+), 93 deletions(-)
diff --git a/include/lttng/bitfield.h b/include/lttng/bitfield.h
index ef5453c2..35b382b2 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 <mathieu.desnoyers at efficios.com>
+ * Copyright 2010-2019 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
*
* 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,145 @@
#include <limits.h> /* C99 5.2.4.2 Numerical limits */
#include <lttng/ust-endian.h> /* Non-standard BIG_ENDIAN, LITTLE_ENDIAN, BYTE_ORDER */
-/* We can't shift a int from 32 bit, >> 32 and << 32 on int is undefined */
+/*
+ * 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)
+
+/*
+ * 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.
+ */
+#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.
+ */
+#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.
+ */
#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); \
+do { \
+ 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; \
-})
+ for (; _sb; _sb--) \
+ (_v) = _bt_rshift(_v, sizeof(_v) * CHAR_BIT - 1); \
+ (_v) = _bt_rshift(_v, _final); \
+} while (0)
+/*
+ * Left shift a signed or unsigned integer with `_shift` value being an
+ * arbitrary number of bits. `_v` is modified by this macro.
+ */
#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); \
+do { \
+ 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_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); \
-})
+ for (; _sb; _sb--) \
+ (_v) = _bt_lshift(_v, sizeof(_v) * CHAR_BIT - 1); \
+ (_v) = _bt_lshift(_v, _final); \
+} while (0)
/*
* bt_bitfield_write - write integer to a bitfield in native endianness
@@ -85,7 +187,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 +204,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 +220,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_piecewise_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_piecewise_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 +246,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 +263,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 +279,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_piecewise_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_piecewise_rshift(__v, ts); \
end -= ts; \
} \
if (__start % ts) { \
- mask = (~(type) 0) << (ts - (__start % ts)); \
+ mask = _bt_make_mask(type, ts - (__start % ts)); \
cmask = (type) __v; \
cmask &= ~mask; \
__ptr[this_unit] &= mask; \
@@ -214,7 +316,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 +327,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 +340,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 +359,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_piecewise_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_piecewise_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_piecewise_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_piecewise_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_piecewise_lshift(__v, ts); \
+ __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), __ptr[this_unit]); \
} \
*__vptr = __v; \
} while (0)
@@ -305,7 +407,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 +426,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_piecewise_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_piecewise_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_piecewise_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_piecewise_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_piecewise_lshift(__v, ts); \
+ __v |= _bt_cast_value_to_unsigned_type(__typeof__(__v), __ptr[this_unit]); \
} \
*__vptr = __v; \
} while (0)
@@ -382,7 +484,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 +495,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.11.0
More information about the lttng-dev
mailing list