libnm: rework verify/normalize of "ovs-port.trunks" propertyth/ovs-port-verify-without-hash

Since normalize already sorts the array, and verify needs to check
whether the array is sorted, we can implement verify() more efficiently.

In the usual case (where the property is normalized), we can just
iterate over the list and check that the ranges are increasing and
non-overlapping.

Only if that fails, do a shallow-copy of the array, sort it, and check
again. If it's still invalid after sorting, verification fails.

We don't need to create a GHashTable which adds all elements in between
the ranges. While the algorithm with hash table is O(n), the new version
with sorting is O(n*ln(n)). But of course, since the overall number of
range elements is limited to 4096, they are really both O(1). But more
importantly, it's just faster to iterate over the list and sort it, than
to fill a hash table.

---

Test with -O2, more-asserts=0:

  diff --git c/src/libnm-core-impl/tests/test-setting.c w/src/libnm-core-impl/tests/test-setting.c
  index 00fc838d1794..a0991b36d9d7 100644
  --- c/src/libnm-core-impl/tests/test-setting.c
  +++ w/src/libnm-core-impl/tests/test-setting.c
  @@ -5266,5 +5266,5 @@ static void
   test_ovs_port_trunks(void)
   {
  -    const guint                   N_RUN = 10;
  +    const guint                   N_RUN = 10000;
       guint                         i_run;
       gs_unref_object NMConnection *con = NULL;

  $ make -j src/libnm-core-impl/tests/test-setting && \
  libtool --mode=execute \
    perf stat -r 5 -B \
      src/libnm-core-impl/tests/test-setting -p /libnm/test_ovs_port_trunks

Before:

          8,114.55 msec task-clock:u                     #    0.998 CPUs utilized            ( +-  0.20% )
                 0      context-switches:u               #    0.000 /sec
                 0      cpu-migrations:u                 #    0.000 /sec
               341      page-faults:u                    #   41.980 /sec                     ( +-  0.16% )
    25,172,559,932      cycles:u                         #    3.099 GHz                      ( +-  0.12% )
    39,221,096,221      instructions:u                   #    1.56  insn per cycle           ( +-  0.04% )
     5,721,519,798      branches:u                       #  704.373 M/sec                    ( +-  0.07% )
       230,728,395      branch-misses:u                  #    4.04% of all branches          ( +-  0.28% )

            8.1340 +- 0.0179 seconds time elapsed  ( +-  0.22% )

After:

          4,300.62 msec task-clock:u                     #    0.999 CPUs utilized            ( +-  0.34% )
                 0      context-switches:u               #    0.000 /sec
                 0      cpu-migrations:u                 #    0.000 /sec
               342      page-faults:u                    #   79.435 /sec                     ( +-  0.20% )
    13,231,554,996      cycles:u                         #    3.073 GHz                      ( +-  0.27% )
    20,676,554,955      instructions:u                   #    1.55  insn per cycle           ( +-  0.07% )
     3,101,429,604      branches:u                       #  720.354 M/sec                    ( +-  0.11% )
       118,808,950      branch-misses:u                  #    3.83% of all branches          ( +-  0.34% )

            4.3068 +- 0.0143 seconds time elapsed  ( +-  0.33% )

1 files changed, 62 insertions, 102 deletions

diff --git a/src/libnm-core-impl/nm-setting-ovs-port.c b/src/libnm-core-impl/nm-setting-ovs-port.c
index 671eb101d1..cd000686a6 100644
--- a/src/libnm-core-impl/nm-setting-ovs-port.c
+++ b/src/libnm-core-impl/nm-setting-ovs-port.c
@@ -299,114 +299,28 @@ nm_setting_ovs_port_get_bond_downdelay(NMSettingOvsPort *self)
 
 /*****************************************************************************/
 
-static int
-range_cmp(gconstpointer a, gconstpointer b)
-{
-    const NMRange *range_a = *(const NMRange **) a;
-    const NMRange *range_b = *(const NMRange **) b;
-
-    return nm_range_cmp(range_a, range_b);
-}
-
 gboolean
 _nm_setting_ovs_port_sort_trunks(NMSettingOvsPort *self)
 {
-    gboolean need_sort = FALSE;
-    guint    i;
-
-    if (!self->trunks)
+    if (nm_g_ptr_array_len(self->trunks) <= 1)
         return FALSE;
 
-    for (i = 1; i < self->trunks->len; i++) {
-        NMRange *range_prev = self->trunks->pdata[i - 1];
-        NMRange *range      = self->trunks->pdata[i];
-
-        if (nm_range_cmp(range_prev, range) > 0) {
-            need_sort = TRUE;
-            break;
-        }
-    }
-
-    if (need_sort) {
-        g_ptr_array_sort(self->trunks, range_cmp);
-        _notify(self, PROP_TRUNKS);
-    }
-
-    return need_sort;
-}
-
-static gboolean
-verify_trunks(GPtrArray *ranges, GError **error)
-{
-    gs_unref_hashtable GHashTable *h = NULL;
-    NMRange                       *range;
-    guint                          i;
-    guint                          vlan;
-
-    if (!ranges)
-        return TRUE;
-
-    h = g_hash_table_new(nm_direct_hash, NULL);
-
-    for (i = 0; i < ranges->len; i++) {
-        range = ranges->pdata[i];
-        nm_assert(range->start <= range->end);
-
-        if (range->start > 4095 || range->end > 4095) {
-            g_set_error_literal(error,
-                                NM_CONNECTION_ERROR,
-                                NM_CONNECTION_ERROR_INVALID_PROPERTY,
-                                _("VLANs must be between 0 and 4095"));
-            return FALSE;
-        }
-
-        for (vlan = range->start; vlan <= range->end; vlan++) {
-            if (!nm_g_hash_table_add(h, GUINT_TO_POINTER(vlan))) {
-                g_set_error(error,
-                            NM_CONNECTION_ERROR,
-                            NM_CONNECTION_ERROR_INVALID_PROPERTY,
-                            _("duplicate VLAN %u"),
-                            vlan);
-                return FALSE;
-            }
-        }
-    }
+    if (_nm_range_list_is_sorted_and_non_overlapping((const NMRange *const *) self->trunks->pdata,
+                                                     self->trunks->len))
+        return FALSE;
 
+    _nm_range_list_sort((const NMRange **) self->trunks->pdata, self->trunks->len);
+    _notify(self, PROP_TRUNKS);
     return TRUE;
 }
 
-static gboolean
-verify_trunks_normalizable(GPtrArray *ranges, GError **error)
-{
-    guint i;
-
-    nm_assert(verify_trunks(ranges, NULL));
-
-    if (!ranges || ranges->len <= 1)
-        return TRUE;
-
-    for (i = 1; i < ranges->len; i++) {
-        NMRange *range_prev = ranges->pdata[i - 1];
-        NMRange *range      = ranges->pdata[i];
-
-        if (nm_range_cmp(range_prev, range) > 0) {
-            g_set_error(error,
-                        NM_CONNECTION_ERROR,
-                        NM_CONNECTION_ERROR_INVALID_PROPERTY,
-                        _("VLANs %u and %u are not sorted in ascending order"),
-                        (guint) range_prev->start,
-                        (guint) range->start);
-            return FALSE;
-        }
-    }
-
-    return TRUE;
-}
+/*****************************************************************************/
 
 static int
 verify(NMSetting *setting, NMConnection *connection, GError **error)
 {
-    NMSettingOvsPort *self = NM_SETTING_OVS_PORT(setting);
+    NMSettingOvsPort *self                       = NM_SETTING_OVS_PORT(setting);
+    gboolean          trunks_needs_normalization = FALSE;
 
     if (!_nm_connection_verify_required_interface_name(connection, error))
         return FALSE;
@@ -511,15 +425,61 @@ verify(NMSetting *setting, NMConnection *connection, GError **error)
         return FALSE;
     }
 
-    if (!verify_trunks(self->trunks, error)) {
-        g_prefix_error(error,
-                       "%s.%s: ",
-                       NM_SETTING_OVS_PORT_SETTING_NAME,
-                       NM_SETTING_OVS_PORT_TRUNKS);
-        return FALSE;
+    if (nm_g_ptr_array_len(self->trunks) > 0) {
+        guint i;
+
+        for (i = 0; i < self->trunks->len; i++) {
+            const NMRange *range = self->trunks->pdata[i];
+
+            nm_assert(range->start <= range->end);
+
+            if (range->end > 4095) {
+                g_set_error_literal(error,
+                                    NM_CONNECTION_ERROR,
+                                    NM_CONNECTION_ERROR_INVALID_PROPERTY,
+                                    _("VLANs must be between 0 and 4095"));
+                g_prefix_error(error,
+                               "%s.%s: ",
+                               NM_SETTING_OVS_PORT_SETTING_NAME,
+                               NM_SETTING_OVS_PORT_TRUNKS);
+                return FALSE;
+            }
+        }
+
+        if (!_nm_range_list_is_sorted_and_non_overlapping(
+                (const NMRange *const *) self->trunks->pdata,
+                self->trunks->len)) {
+            gs_free const NMRange **ranges_to_free = NULL;
+            const NMRange         **ranges;
+
+            ranges = nm_memdup_maybe_a(500,
+                                       self->trunks->pdata,
+                                       sizeof(NMRange *) * self->trunks->len,
+                                       &ranges_to_free);
+
+            _nm_range_list_sort(ranges, self->trunks->len);
+
+            if (!_nm_range_list_is_sorted_and_non_overlapping(ranges, self->trunks->len)) {
+                g_set_error(error,
+                            NM_CONNECTION_ERROR,
+                            NM_CONNECTION_ERROR_INVALID_PROPERTY,
+                            _("duplicate or overlapping VLANs"));
+                g_prefix_error(error,
+                               "%s.%s: ",
+                               NM_SETTING_OVS_PORT_SETTING_NAME,
+                               NM_SETTING_OVS_PORT_TRUNKS);
+                return FALSE;
+            }
+
+            trunks_needs_normalization = TRUE;
+        }
     }
 
-    if (!verify_trunks_normalizable(self->trunks, error)) {
+    if (trunks_needs_normalization) {
+        g_set_error(error,
+                    NM_CONNECTION_ERROR,
+                    NM_CONNECTION_ERROR_INVALID_PROPERTY,
+                    _("VLANs are not sorted in ascending order"));
         g_prefix_error(error,
                        "%s.%s: ",
                        NM_SETTING_OVS_PORT_SETTING_NAME,