Skip to contentSkip to conversation

Fix: bitfield: left shift undefined behavior

PATCH Simon Marchi 2 participants 2 messages May 7, 2019 – May 8, 2019 2 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 3 lines · Mathieu Desnoyers

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.

Please add a reference to the original problem that prompted you to do this change in the commit message. For example:

--- 8< ---

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.

--- >8 ---

Quoted 20 lines

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]

---
 include/babeltrace/bitfield-internal.h | 61 ++++++++++++++++++----------------
 1 file changed, 33 insertions(+), 28 deletions(-)
include/babeltrace/bitfield-internal.h +0 -1
index c5d5eccd..da56f089 100644
@@ -55,19 +55,24 @@
 #define _bt_is_signed_type(type)	((type) -1 < (type) 0)
 
 /*
- * NOTE: The cast to (uint64_t) below ensures that we're not casting a

include/babeltrace/bitfield-internal.h line 63

Quoted 10 lines
include/babeltrace/bitfield-internal.h +5 -4
- * negative value, which is undefined in C. However, this limits the
- * maximum type size of `type` and `v` to 64-bit. The
- * _bt_check_max_64bit() is used to check that the users of this header
- * do not use types with a size greater than 64-bit.
+ * NOTE: 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` and `v` to 64-bit. The _bt_check_max_64bit() is
+ * used to check that the users of this header do not use types with a
+ * size greater than 64-bit.
  */

The comment explains "why" this macro is needed, but doesn't explain what it does. I would suggest starting the comment with:

Cast value v to an unsigned integer type of the size of type type.

include/babeltrace/bitfield-internal.h line 71

Quoted 12 lines
include/babeltrace/bitfield-internal.h +5 -3
 #define _bt_unsigned_cast(type, v)					\
 ({									\
-	(sizeof(v) < sizeof(type)) ?					\
-		((type) (v)) & ((type) (~(~(uint64_t) 0 << (sizeof(v) * CHAR_BIT)))) : \
-		(type) (v);						\
+	__builtin_types_compatible_p(type, int8_t) ? (uint8_t) (v) :	\
+	__builtin_types_compatible_p(type, int16_t) ? (uint16_t) (v) :	\
+	__builtin_types_compatible_p(type, int32_t) ? (uint32_t) (v) :	\
+	__builtin_types_compatible_p(type, int64_t) ? (uint64_t) (v) :	\
+	(type) (v);							\
 })

What should we do in the "else" case. The macro claims to cast to an unsigned type, but in the case where the "else" branch would be taken, the value is cast to the original type (possible signed). I think this can be very misleading.

Knowing that all of this is supposed to get resolved at compiled time, would there be a way to generate compilation error in the "else" branch? If we ever reach it, it means we need to add something here.

include/babeltrace/bitfield-internal.h line 73

Quoted 3 lines
include/babeltrace/bitfield-internal.h +2 -0
+/* Unsigned bitwise complement. */
+#define _bt_bitwise_not(type, v)	_bt_unsigned_cast(type, ~(type) v)

I was trying to put words on what this macro does, to document it a bit better, but then realized it iss always used with v = 0. I don't know if you want to simplify and remove the v parameter to hard-code 0? In the end, all you want is something that yields a value of the same size as type, but unsigned, and filled with ones.

Since you said that you would change the code, I'll wait for the next version to look at the hairy details.

Simon
_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

A message that is not in the archive (sent off-list or not yet received): [email protected]

#3 lore raw
Quoted 4 lines · ----- On May 7, 2019, at 6:13 PM, Simon Marchi [email protected] wrote:
Quoted 3 lines · Mathieu Desnoyers

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.

Hi Simon,

Thanks a ton for your input! I've taken care of all your comments and will post an updated patch for babeltrace.

Once we all agree on the content, I'll work on porting this to lttng-ust, lttng-modules, and barectf.

Let's keep in mind that bitfield.h needs to stay ANSI-C compatible as much as possible so the barectf implementation don't diverge too much.

Thanks,

Mathieu

Quoted 110 lines

Please add a reference to the original problem that prompted you to do this change in the commit message. For example:

--- 8< ---

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.

--- >8 ---

Quoted 21 lines

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]

---
 include/babeltrace/bitfield-internal.h | 61 ++++++++++++++++++----------------
 1 file changed, 33 insertions(+), 28 deletions(-)
include/babeltrace/bitfield-internal.h +0 -1
index c5d5eccd..da56f089 100644
@@ -55,19 +55,24 @@
 #define _bt_is_signed_type(type)	((type) -1 < (type) 0)
 
 /*
- * NOTE: The cast to (uint64_t) below ensures that we're not casting a

include/babeltrace/bitfield-internal.h line 63

Quoted 10 lines
include/babeltrace/bitfield-internal.h +5 -4
- * negative value, which is undefined in C. However, this limits the
- * maximum type size of `type` and `v` to 64-bit. The
- * _bt_check_max_64bit() is used to check that the users of this header
- * do not use types with a size greater than 64-bit.
+ * NOTE: 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` and `v` to 64-bit. The _bt_check_max_64bit() is
+ * used to check that the users of this header do not use types with a
+ * size greater than 64-bit.
  */

The comment explains "why" this macro is needed, but doesn't explain what it does. I would suggest starting the comment with:

Cast value v to an unsigned integer type of the size of type type.

include/babeltrace/bitfield-internal.h line 71

Quoted 12 lines
include/babeltrace/bitfield-internal.h +5 -3
 #define _bt_unsigned_cast(type, v)					\
 ({									\
-	(sizeof(v) < sizeof(type)) ?					\
-		((type) (v)) & ((type) (~(~(uint64_t) 0 << (sizeof(v) * CHAR_BIT)))) : \
-		(type) (v);						\
+	__builtin_types_compatible_p(type, int8_t) ? (uint8_t) (v) :	\
+	__builtin_types_compatible_p(type, int16_t) ? (uint16_t) (v) :	\
+	__builtin_types_compatible_p(type, int32_t) ? (uint32_t) (v) :	\
+	__builtin_types_compatible_p(type, int64_t) ? (uint64_t) (v) :	\
+	(type) (v);							\
 })

What should we do in the "else" case. The macro claims to cast to an unsigned type, but in the case where the "else" branch would be taken, the value is cast to the original type (possible signed). I think this can be very misleading.

Knowing that all of this is supposed to get resolved at compiled time, would there be a way to generate compilation error in the "else" branch? If we ever reach it, it means we need to add something here.

include/babeltrace/bitfield-internal.h line 73

Quoted 3 lines
include/babeltrace/bitfield-internal.h +2 -0
+/* Unsigned bitwise complement. */
+#define _bt_bitwise_not(type, v)	_bt_unsigned_cast(type, ~(type) v)

I was trying to put words on what this macro does, to document it a bit better, but then realized it iss always used with v = 0. I don't know if you want to simplify and remove the v parameter to hard-code 0? In the end, all you want is something that yields a value of the same size as type, but unsigned, and filled with ones.

Since you said that you would change the code, I'll wait for the next version to look at the hairy details.

Simon

Signature · 7 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev