[ovs-dev,v2,00/16] Fix undefined behavior in loop macros

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.

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.

[1] https://bugzilla.redhat.com/show_bug.cgi?id=2014942
[2] https://patchwork.ozlabs.org/project/openvswitch/list/?series=277900


Adrian Moreno (16):
  util: add multi-variable loop iterator macros
  util: add safe multi-variable iterators
  list: use multi-variable helpers for list loops
  list: ensure iterator is NULL after pop loop
  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
  vtep: use _SAFE iterator if freeing the iterator
  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              | 115 +++++++++++++--------
 include/openvswitch/list.h              | 100 +++++++++++++------
 include/openvswitch/shash.h             |  16 ++-
 include/openvswitch/util.h              | 126 ++++++++++++++++++++++++
 lib/cfm.c                               |   4 +-
 lib/classifier.c                        |   4 +-
 lib/cmap.h                              |  24 +++--
 lib/conntrack.c                         |   8 +-
 lib/dns-resolve.c                       |   4 +-
 lib/dpif-netdev.c                       |  19 ++--
 lib/fat-rwlock.c                        |   4 +-
 lib/hindex.h                            |  72 ++++++++++----
 lib/hmapx.c                             |   4 +-
 lib/hmapx.h                             |  15 ++-
 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                           |  79 +++++++++------
 lib/seq.c                               |   8 +-
 lib/shash.c                             |   8 +-
 lib/simap.c                             |   4 +-
 lib/simap.h                             |  17 +++-
 lib/smap.c                              |   4 +-
 lib/smap.h                              |  16 ++-
 lib/sset.c                              |   8 +-
 lib/sset.h                              |  16 ++-
 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                     |  23 ++++-
 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                       |  52 +++++++++-
 utilities/ovs-ofctl.c                   |   4 +-
 utilities/ovs-vsctl.c                   |  48 ++++-----
 vswitchd/bridge.c                       |  72 +++++++-------
 vtep/vtep-ctl.c                         |  20 ++--
 86 files changed, 995 insertions(+), 546 deletions(-)