When running builds with UBSan, some undefined behavior was detected in the
iteration of common data data structures in OVS.
Coincidentally, a bug was reported [1] whose root cause whas another, this time
undetected, undefined behavior in the iteration macros.
>From both cases, we conclude that the way we're currently iterating the data
>structures is prone to errors and UB. This series is an attempt to rewrite
>those macros in a UB-safe manner.
The core problem is that #define OBJECT_CONTAINING(POINTER, OBJECT, MEMBER)
macro is being used on invalid POINTER values. In some cases we use NULL to
compute the end-of-loop condition. In others, we allow it to point to
non-contained objects (e.g: a non-contained stack allocated "struct ovs_list"
as in [1]).
In order to systematically solve this in all cases this series introduces a new
set of macros that implement a multi-variable loop iteration. They declare a
hidden iterator variable inside the loop, used to iterate and evaluate the loop
condition and only compute its OBJECT_CONTAINING if it satisfies the loop
condition. One consequence of this safety guard is that the pointer provided by
the user is set to NULL after the loop (if not exited via "break;").
Apart from normal iteration, many OVS data structures have a _SAFE version of
the loop which require the user to declare an extra variable to hold the next
value of the iterator.
The use of internal iterator variables makes the declaration variable not
necessary. However, some users might still need that extra variable. For that
reason, this series introduces two versions of _SAFE iteration loops:
- The _LONG version keeps using the external variable but avoids calling
OBJECT_CONTAINING on invalid values. Note that alghough this version still uses
an external variable, it's behavior changes slightly as the "next" variable
could be NULL if it's not safe to calculate the OBJECT_CONTAINING of its
internal iterator value.
- The _SHORT version removes the use of the external variable alltogether.
On relevant data structures, an initial patch rewrites the macros using the
_LONG, backwards-compatible helpers. A second patch adds the _SHORT version and
removes the unneeded variable from the callers. In order to be even more
flexible, the original macro name is overloaded and the right version is
selected depending on the number of arguments provided by the user. The first
patch would be easy to backport and the second would make code cleaner for the
master branch.
* Testing / reviewing notes *
In order to verify this series removes all the loop-related UB, I've tested it
on top of Dumitru's series [2] (without patch 1/11, which can hide some still
invalid use of OBJECT_CONTAINING).
I've also verified no extra errors are reported through clang-analyzer or ASan.
There are a number of checkpatch.py errors:
- ERROR: Inappropriate bracing around statement: Seems a limitation in
checkpatch.py that only happens when a FOR_EACH* macro calls another FOR_EACH*
macro. I don't think it's worth modifying checkpatch.py for this.
- ERROR: Use ovs_assert() in place of assert(): On tests/*, I'll send an
independent patch to exclude the "tests" directory from this check.
Note this series changes some potential undefined behavior with some potential
NULL pointer dereferencing, which should be easier to catch by the static and
dynamic analyzers.
* Limitations *
The proposed approach benefits code readability, therefore the name of the
iterator variable is derived from the name of the object pointer given by the
caller. This means that in an unlikely but still possible case in which a
caller wants to nest two loops with the same iterating pointer object, the
inner loop iterator variable will hide the one declared in the outer loop. This
limitation is easy to spot (the compiler will warn) and easy to work around
(just declaring another object pointer variable). I found no such code in the
OvS or OVN tree.
V3 -> V4
- Sligthly changed UPDATE_MULTIVAR:
- Do not set VAR to NULL, it was redundant
- Accept the next value of the iterator instead of an updating
expression, it makes callers sligthly cleaner.
- Add Dumitru's Acked-by.
- Squashed patches 5 and 4
- Dropped patch 14
V2 -> V3
- Added ITER_TYPE to MULTIVAR_INIT macro to avoid depending on typeof
(missing in MVSC).
- Added macro overloading helpers that work around MVSC issues.
V1 -> V2
- Added LONG and SHORT versions of _SAFE macros with macro name overloading.
- Rebased on top of latest master.
- Added Dumitru's patch to fix sparse header inclusion and version
recommendation.
- Homogenize argument order in helper macros: VAR and MEMBER always first.
- Added SHORT version of _SAFE loops to SSET and idlc.
Adrian Moreno (15):
util: add multi-variable loop iterator macros
util: add safe multi-variable iterators
util: add helpers to overload SAFE macro
list: use multi-variable helpers for list loops
list: use short version of safe loops if possible
hmap: use multi-variable helpers for hmap loops
hmap: implement UB-safe hmap pop iterator
hmap: use short version of safe loops if possible
cmap: use multi-variable iterators
hindex: use multi-variable iterators
hindex: remove the next variable in safe loops
rculist: use multi-variable helpers for loop macros
idlc: support short version of SAFE macros
sparse: bump recommended version and include headers
sset: add SHORT version of SAFE loop macros
Documentation/intro/install/general.rst | 2 +-
acinclude.m4 | 2 +-
include/openvswitch/hmap.h | 112 +++++++++++-------
include/openvswitch/list.h | 99 +++++++++++-----
include/openvswitch/shash.h | 15 ++-
include/openvswitch/util.h | 144 ++++++++++++++++++++++++
lib/cfm.c | 4 +-
lib/classifier.c | 4 +-
lib/cmap.h | 22 ++--
lib/conntrack.c | 8 +-
lib/dns-resolve.c | 4 +-
lib/dpif-netdev.c | 19 ++--
lib/fat-rwlock.c | 4 +-
lib/hindex.h | 75 ++++++++----
lib/hmapx.c | 4 +-
lib/hmapx.h | 14 ++-
lib/id-fpool.c | 3 +-
lib/ipf.c | 22 ++--
lib/json.c | 4 +-
lib/lacp.c | 4 +-
lib/lldp/lldpd-structs.c | 7 +-
lib/lldp/lldpd.c | 8 +-
lib/mac-learning.c | 4 +-
lib/mcast-snooping.c | 12 +-
lib/namemap.c | 4 +-
lib/netdev-afxdp.c | 4 +-
lib/netdev-dpdk.c | 8 +-
lib/netdev-linux.c | 4 +-
lib/netdev-offload-tc.c | 4 +-
lib/ofp-msgs.c | 8 +-
lib/ovs-lldp.c | 12 +-
lib/ovs-numa.h | 4 +-
lib/ovsdb-cs.c | 12 +-
lib/ovsdb-idl.c | 46 ++++----
lib/ovsdb-map-op.c | 4 +-
lib/ovsdb-set-op.c | 4 +-
lib/pcap-file.c | 4 +-
lib/perf-counter.c | 4 +-
lib/poll-loop.c | 4 +-
lib/rculist.h | 82 +++++++++-----
lib/seq.c | 8 +-
lib/shash.c | 8 +-
lib/simap.c | 4 +-
lib/simap.h | 16 ++-
lib/smap.c | 4 +-
lib/smap.h | 15 ++-
lib/sset.c | 8 +-
lib/sset.h | 15 ++-
lib/stopwatch.c | 4 +-
lib/tnl-ports.c | 16 +--
lib/unixctl.c | 8 +-
lib/vconn.c | 4 +-
ofproto/bond.c | 6 +-
ofproto/connmgr.c | 28 ++---
ofproto/in-band.c | 4 +-
ofproto/netflow.c | 8 +-
ofproto/ofproto-dpif-ipfix.c | 12 +-
ofproto/ofproto-dpif-sflow.c | 4 +-
ofproto/ofproto-dpif-trace.c | 4 +-
ofproto/ofproto-dpif-xlate.c | 12 +-
ofproto/ofproto-dpif.c | 28 +++--
ofproto/ofproto.c | 16 +--
ovsdb/condition.c | 8 +-
ovsdb/jsonrpc-server.c | 40 +++----
ovsdb/monitor.c | 36 +++---
ovsdb/ovsdb-idlc.in | 19 +++-
ovsdb/ovsdb-server.c | 11 +-
ovsdb/ovsdb-tool.c | 7 +-
ovsdb/ovsdb.c | 4 +-
ovsdb/query.c | 4 +-
ovsdb/raft-private.c | 4 +-
ovsdb/raft.c | 33 +++---
ovsdb/relay.c | 4 +-
ovsdb/replication.c | 8 +-
ovsdb/table.c | 4 +-
ovsdb/transaction-forward.c | 10 +-
ovsdb/transaction.c | 36 +++---
ovsdb/trigger.c | 4 +-
tests/test-cmap.c | 7 +-
tests/test-hindex.c | 37 ++++++
tests/test-hmap.c | 42 +++++++
tests/test-list.c | 43 ++++++-
utilities/ovs-ofctl.c | 4 +-
utilities/ovs-vsctl.c | 48 ++++----
vswitchd/bridge.c | 72 ++++++------
vtep/vtep-ctl.c | 18 +--
86 files changed, 994 insertions(+), 545 deletions(-)
--
2.34.1
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
