glib-aux,libnmc: merge branch 'th/setting-info-binsearch'

https://gitlab.freedesktop.org/NetworkManager/NetworkManager/-/merge_requests/1369

5 files changed, 265 insertions, 83 deletions

diff --git a/src/libnm-core-impl/nm-meta-setting-base-impl.c b/src/libnm-core-impl/nm-meta-setting-base-impl.c
index ebc04556a7..5e627cfc7d 100644
--- a/src/libnm-core-impl/nm-meta-setting-base-impl.c
+++ b/src/libnm-core-impl/nm-meta-setting-base-impl.c
@@ -3,6 +3,8 @@
  * Copyright (C) 2017 - 2018 Red Hat, Inc.
  */
 
+#define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE
+
 #include "libnm-glib-aux/nm-default-glib-i18n-lib.h"
 
 #include "nm-meta-setting-base.h"
@@ -703,19 +705,21 @@ nm_meta_setting_infos_by_name(const char *name)
     return idx >= 0 ? &nm_meta_setting_infos[idx] : NULL;
 }
 
-const NMMetaSettingInfo *
-nm_meta_setting_infos_by_gtype(GType gtype)
-{
+/*****************************************************************************/
+
 #if _NM_META_SETTING_BASE_IMPL_LIBNM
+static const NMMetaSettingInfo *
+_infos_by_gtype_from_class(GType gtype)
+{
     nm_auto_unref_gtypeclass GTypeClass *gtypeclass_unref = NULL;
     GTypeClass                          *gtypeclass;
     NMSettingClass                      *klass;
 
     if (!g_type_is_a(gtype, NM_TYPE_SETTING))
-        goto out_none;
+        return NULL;
 
     gtypeclass = g_type_class_peek(gtype);
-    if (!gtypeclass)
+    if (G_UNLIKELY(!gtypeclass))
         gtypeclass = gtypeclass_unref = g_type_class_ref(gtype);
 
     nm_assert(NM_IS_SETTING_CLASS(gtypeclass));
@@ -723,38 +727,112 @@ nm_meta_setting_infos_by_gtype(GType gtype)
     klass = (NMSettingClass *) gtypeclass;
 
     if (!klass->setting_info)
-        goto out_none;
+        return NULL;
 
     nm_assert(klass->setting_info->get_setting_gtype);
     nm_assert(klass->setting_info->get_setting_gtype() == gtype);
-
     return klass->setting_info;
+}
+#endif
 
-out_none:
-
-    if (NM_MORE_ASSERTS > 10) {
-        int i;
-
-        /* this might hint to a bug, but it would be expected for NM_TYPE_SETTING
-         * and NM_TYPE_SETTING_IP_CONFIG.
-         *
-         * Assert that we didn't lookup for a gtype, which we would expect to find.
-         * An assertion failure here, hints to a bug in nm_setting_*_class_init().
-         */
-        for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++)
-            nm_assert(nm_meta_setting_infos[i].get_setting_gtype() != gtype);
-    }
-
-    return NULL;
-#else
-    guint i;
+static const NMMetaSettingInfo *
+_infos_by_gtype_search(GType gtype)
+{
+    int i;
 
-    for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++) {
+    for (i = 0; i < (int) _NM_META_SETTING_TYPE_NUM; i++) {
         if (nm_meta_setting_infos[i].get_setting_gtype() == gtype)
             return &nm_meta_setting_infos[i];
     }
     return NULL;
+}
+
+typedef struct {
+    GType                    gtype;
+    const NMMetaSettingInfo *setting_info;
+} LookupData;
+
+_nm_always_inline static inline int
+_lookup_data_cmp(gconstpointer ptr_a, gconstpointer ptr_b, gpointer user_data)
+{
+    const GType *const a = ptr_a;
+    const GType *const b = ptr_b;
+
+    nm_assert(a);
+    nm_assert(b);
+    nm_assert(a != b);
+
+    NM_CMP_DIRECT(*a, *b);
+    return 0;
+}
+
+static const NMMetaSettingInfo *
+_infos_by_gtype_binary_search(GType gtype)
+{
+    static LookupData        static_array[_NM_META_SETTING_TYPE_NUM];
+    static const LookupData *static_ptr = NULL;
+    const LookupData        *ptr;
+    gssize                   idx;
+
+again:
+    ptr = g_atomic_pointer_get(&static_ptr);
+    if (G_UNLIKELY(!ptr)) {
+        static gsize g_lock = 0;
+        int          i;
+
+        if (!g_once_init_enter(&g_lock))
+            goto again;
+
+        for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++) {
+            const NMMetaSettingInfo *m = &nm_meta_setting_infos[i];
+
+            static_array[i] = (LookupData){
+                .gtype        = m->get_setting_gtype(),
+                .setting_info = m,
+            };
+        }
+
+        g_qsort_with_data(static_array,
+                          _NM_META_SETTING_TYPE_NUM,
+                          sizeof(static_array[0]),
+                          _lookup_data_cmp,
+                          NULL);
+
+        ptr = static_array;
+        g_atomic_pointer_set(&static_ptr, ptr);
+
+        g_once_init_leave(&g_lock, 1);
+    }
+
+    idx = nm_array_find_bsearch_inline(ptr,
+                                       _NM_META_SETTING_TYPE_NUM,
+                                       sizeof(ptr[0]),
+                                       &gtype,
+                                       _lookup_data_cmp,
+                                       NULL);
+    if (idx < 0)
+        return NULL;
+
+    return ptr[idx].setting_info;
+}
+
+const NMMetaSettingInfo *
+nm_meta_setting_infos_by_gtype(GType gtype)
+{
+    const NMMetaSettingInfo *setting_info;
+
+#if _NM_META_SETTING_BASE_IMPL_LIBNM
+    setting_info = _infos_by_gtype_from_class(gtype);
+#else
+    setting_info = _infos_by_gtype_binary_search(gtype);
 #endif
+
+    if (NM_MORE_ASSERTS > 20) {
+        nm_assert(setting_info == _infos_by_gtype_search(gtype));
+        nm_assert(setting_info == _infos_by_gtype_binary_search(gtype));
+    }
+
+    return setting_info;
 }
 
 /*****************************************************************************/
diff --git a/src/libnm-glib-aux/nm-shared-utils.c b/src/libnm-glib-aux/nm-shared-utils.c
index f60ae1f2d6..66eb17e709 100644
--- a/src/libnm-glib-aux/nm-shared-utils.c
+++ b/src/libnm-glib-aux/nm-shared-utils.c
@@ -3,6 +3,8 @@
  * Copyright (C) 2016 Red Hat, Inc.
  */
 
+#define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE
+
 #include "libnm-glib-aux/nm-default-glib-i18n-lib.h"
 
 #include "nm-shared-utils.h"
@@ -3943,37 +3945,7 @@ nm_array_find_bsearch(gconstpointer    list,
                       GCompareDataFunc cmpfcn,
                       gpointer         user_data)
 {
-    gssize imax;
-    gssize imid;
-    gssize imin;
-    int    cmp;
-
-    nm_assert(list || len == 0);
-    nm_assert(cmpfcn);
-    nm_assert(elem_size > 0);
-
-    imin = 0;
-    if (len == 0)
-        return ~imin;
-
-    imax = len - 1;
-
-    while (imin <= imax) {
-        imid = imin + (imax - imin) / 2;
-
-        cmp = cmpfcn(&((const char *) list)[elem_size * imid], needle, user_data);
-        if (cmp == 0)
-            return imid;
-
-        if (cmp < 0)
-            imin = imid + 1;
-        else
-            imax = imid - 1;
-    }
-
-    /* return the inverse of @imin. This is a negative number, but
-     * also is ~imin the position where the value should be inserted. */
-    return ~imin;
+    return nm_array_find_bsearch_inline(list, len, elem_size, needle, cmpfcn, user_data);
 }
 
 /*****************************************************************************/
diff --git a/src/libnm-glib-aux/nm-shared-utils.h b/src/libnm-glib-aux/nm-shared-utils.h
index 3383e6d03f..c1325a8c41 100644
--- a/src/libnm-glib-aux/nm-shared-utils.h
+++ b/src/libnm-glib-aux/nm-shared-utils.h
@@ -2135,6 +2135,57 @@ gssize nm_ptrarray_find_bsearch_range(gconstpointer   *list,
                                  NULL);                           \
     })
 
+/*****************************************************************************/
+
+#ifdef NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE
+/**
+ * nm_array_find_bsearch_inline:
+ *
+ * An inlined version of nm_array_find_bsearch(). See there.
+ * Define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE to get it.
+ */
+_nm_always_inline static inline gssize
+nm_array_find_bsearch_inline(gconstpointer    list,
+                             gsize            len,
+                             gsize            elem_size,
+                             gconstpointer    needle,
+                             GCompareDataFunc cmpfcn,
+                             gpointer         user_data)
+{
+    gssize imax;
+    gssize imid;
+    gssize imin;
+    int    cmp;
+
+    nm_assert(list || len == 0);
+    nm_assert(cmpfcn);
+    nm_assert(elem_size > 0);
+
+    imin = 0;
+    if (len == 0)
+        return ~imin;
+
+    imax = len - 1;
+
+    while (imin <= imax) {
+        imid = imin + (imax - imin) / 2;
+
+        cmp = cmpfcn(&((const char *) list)[elem_size * imid], needle, user_data);
+        if (cmp == 0)
+            return imid;
+
+        if (cmp < 0)
+            imin = imid + 1;
+        else
+            imax = imid - 1;
+    }
+
+    /* return the inverse of @imin. This is a negative number, but
+     * also is ~imin the position where the value should be inserted. */
+    return ~imin;
+}
+#endif
+
 gssize nm_array_find_bsearch(gconstpointer    list,
                              gsize            len,
                              gsize            elem_size,
@@ -2142,6 +2193,8 @@ gssize nm_array_find_bsearch(gconstpointer    list,
                              GCompareDataFunc cmpfcn,
                              gpointer         user_data);
 
+/*****************************************************************************/
+
 gssize nm_utils_ptrarray_find_first(gconstpointer *list, gssize len, gconstpointer needle);
 
 /*****************************************************************************/
diff --git a/src/libnm-std-aux/nm-std-aux.h b/src/libnm-std-aux/nm-std-aux.h
index b404b835c5..1ff547d5dd 100644
--- a/src/libnm-std-aux/nm-std-aux.h
+++ b/src/libnm-std-aux/nm-std-aux.h
@@ -16,6 +16,7 @@
 
 #define _nm_packed             __attribute__((__packed__))
 #define _nm_unused             __attribute__((__unused__))
+#define _nm_always_inline      __attribute__((__always_inline__))
 #define _nm_used               __attribute__((__used__))
 #define _nm_pure               __attribute__((__pure__))
 #define _nm_const              __attribute__((__const__))
diff --git a/src/libnmc-setting/nm-meta-setting-base-impl.c b/src/libnmc-setting/nm-meta-setting-base-impl.c
index ebc04556a7..5e627cfc7d 100644
--- a/src/libnmc-setting/nm-meta-setting-base-impl.c
+++ b/src/libnmc-setting/nm-meta-setting-base-impl.c
@@ -3,6 +3,8 @@
  * Copyright (C) 2017 - 2018 Red Hat, Inc.
  */
 
+#define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE
+
 #include "libnm-glib-aux/nm-default-glib-i18n-lib.h"
 
 #include "nm-meta-setting-base.h"
@@ -703,19 +705,21 @@ nm_meta_setting_infos_by_name(const char *name)
     return idx >= 0 ? &nm_meta_setting_infos[idx] : NULL;
 }
 
-const NMMetaSettingInfo *
-nm_meta_setting_infos_by_gtype(GType gtype)
-{
+/*****************************************************************************/
+
 #if _NM_META_SETTING_BASE_IMPL_LIBNM
+static const NMMetaSettingInfo *
+_infos_by_gtype_from_class(GType gtype)
+{
     nm_auto_unref_gtypeclass GTypeClass *gtypeclass_unref = NULL;
     GTypeClass                          *gtypeclass;
     NMSettingClass                      *klass;
 
     if (!g_type_is_a(gtype, NM_TYPE_SETTING))
-        goto out_none;
+        return NULL;
 
     gtypeclass = g_type_class_peek(gtype);
-    if (!gtypeclass)
+    if (G_UNLIKELY(!gtypeclass))
         gtypeclass = gtypeclass_unref = g_type_class_ref(gtype);
 
     nm_assert(NM_IS_SETTING_CLASS(gtypeclass));
@@ -723,38 +727,112 @@ nm_meta_setting_infos_by_gtype(GType gtype)
     klass = (NMSettingClass *) gtypeclass;
 
     if (!klass->setting_info)
-        goto out_none;
+        return NULL;
 
     nm_assert(klass->setting_info->get_setting_gtype);
     nm_assert(klass->setting_info->get_setting_gtype() == gtype);
-
     return klass->setting_info;
+}
+#endif
 
-out_none:
-
-    if (NM_MORE_ASSERTS > 10) {
-        int i;
-
-        /* this might hint to a bug, but it would be expected for NM_TYPE_SETTING
-         * and NM_TYPE_SETTING_IP_CONFIG.
-         *
-         * Assert that we didn't lookup for a gtype, which we would expect to find.
-         * An assertion failure here, hints to a bug in nm_setting_*_class_init().
-         */
-        for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++)
-            nm_assert(nm_meta_setting_infos[i].get_setting_gtype() != gtype);
-    }
-
-    return NULL;
-#else
-    guint i;
+static const NMMetaSettingInfo *
+_infos_by_gtype_search(GType gtype)
+{
+    int i;
 
-    for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++) {
+    for (i = 0; i < (int) _NM_META_SETTING_TYPE_NUM; i++) {
         if (nm_meta_setting_infos[i].get_setting_gtype() == gtype)
             return &nm_meta_setting_infos[i];
     }
     return NULL;
+}
+
+typedef struct {
+    GType                    gtype;
+    const NMMetaSettingInfo *setting_info;
+} LookupData;
+
+_nm_always_inline static inline int
+_lookup_data_cmp(gconstpointer ptr_a, gconstpointer ptr_b, gpointer user_data)
+{
+    const GType *const a = ptr_a;
+    const GType *const b = ptr_b;
+
+    nm_assert(a);
+    nm_assert(b);
+    nm_assert(a != b);
+
+    NM_CMP_DIRECT(*a, *b);
+    return 0;
+}
+
+static const NMMetaSettingInfo *
+_infos_by_gtype_binary_search(GType gtype)
+{
+    static LookupData        static_array[_NM_META_SETTING_TYPE_NUM];
+    static const LookupData *static_ptr = NULL;
+    const LookupData        *ptr;
+    gssize                   idx;
+
+again:
+    ptr = g_atomic_pointer_get(&static_ptr);
+    if (G_UNLIKELY(!ptr)) {
+        static gsize g_lock = 0;
+        int          i;
+
+        if (!g_once_init_enter(&g_lock))
+            goto again;
+
+        for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++) {
+            const NMMetaSettingInfo *m = &nm_meta_setting_infos[i];
+
+            static_array[i] = (LookupData){
+                .gtype        = m->get_setting_gtype(),
+                .setting_info = m,
+            };
+        }
+
+        g_qsort_with_data(static_array,
+                          _NM_META_SETTING_TYPE_NUM,
+                          sizeof(static_array[0]),
+                          _lookup_data_cmp,
+                          NULL);
+
+        ptr = static_array;
+        g_atomic_pointer_set(&static_ptr, ptr);
+
+        g_once_init_leave(&g_lock, 1);
+    }
+
+    idx = nm_array_find_bsearch_inline(ptr,
+                                       _NM_META_SETTING_TYPE_NUM,
+                                       sizeof(ptr[0]),
+                                       &gtype,
+                                       _lookup_data_cmp,
+                                       NULL);
+    if (idx < 0)
+        return NULL;
+
+    return ptr[idx].setting_info;
+}
+
+const NMMetaSettingInfo *
+nm_meta_setting_infos_by_gtype(GType gtype)
+{
+    const NMMetaSettingInfo *setting_info;
+
+#if _NM_META_SETTING_BASE_IMPL_LIBNM
+    setting_info = _infos_by_gtype_from_class(gtype);
+#else
+    setting_info = _infos_by_gtype_binary_search(gtype);
 #endif
+
+    if (NM_MORE_ASSERTS > 20) {
+        nm_assert(setting_info == _infos_by_gtype_search(gtype));
+        nm_assert(setting_info == _infos_by_gtype_binary_search(gtype));
+    }
+
+    return setting_info;
 }
 
 /*****************************************************************************/