ifcfg-rh: add index for O(1) access of variables in shvarFileth/ifcfg-unset-well-known-keys

Previously, setting or getting a variable required to scan all lines.

Note that frequently we would look up variables that didn't actually
exist, which we could only determine after searching the entire list.

Also, since we needed to handle having the same variable specified
multiple times (where the last occurrence wins), we always had to search
all keys and couldn't stop when finding the first key. Well, technically
we could have searched in reverse order for the getter, but that wasn't
done. For the setter we wanted to delete all but the last occurrences,
so to find them, we really had to search them all.

We want to support profiles with hundreds or thousands of addresses and routes.
This does not scale well.

Add an hash table to find the variables in constant time.

Test this commit and the parent commit:

   $ git clean -fdx &&
     CFLAGS=-O2 ./autogen.sh --with-more-asserts=0 &&
     ./tools/run-nm-test.sh -m src/settings/plugins/ifcfg-rh/tests/test-ifcfg-rh &&
     perf stat -r 50 -B src/settings/plugins/ifcfg-rh/tests/test-ifcfg-rh 1>/dev/null

Before:

 Performance counter stats for 'src/settings/plugins/ifcfg-rh/tests/test-ifcfg-rh' (50 runs):

            330.94 msec task-clock:u              #    0.961 CPUs utilized            ( +-  0.33% )
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
             1,081      page-faults:u             #    0.003 M/sec                    ( +-  0.07% )
     1,035,923,116      cycles:u                  #    3.130 GHz                      ( +-  0.29% )
     1,800,084,022      instructions:u            #    1.74  insn per cycle           ( +-  0.01% )
       362,313,301      branches:u                # 1094.784 M/sec                    ( +-  0.02% )
         6,259,421      branch-misses:u           #    1.73% of all branches          ( +-  0.13% )

           0.34454 +- 0.00116 seconds time elapsed  ( +-  0.34% )

Now:

 Performance counter stats for 'src/settings/plugins/ifcfg-rh/tests/test-ifcfg-rh' (50 runs):

            329.78 msec task-clock:u              #    0.962 CPUs utilized            ( +-  0.39% )
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
             1,084      page-faults:u             #    0.003 M/sec                    ( +-  0.05% )
     1,036,130,698      cycles:u                  #    3.142 GHz                      ( +-  0.13% )
     1,799,851,979      instructions:u            #    1.74  insn per cycle           ( +-  0.01% )
       360,374,338      branches:u                # 1092.756 M/sec                    ( +-  0.01% )
         6,160,796      branch-misses:u           #    1.71% of all branches          ( +-  0.08% )

           0.34287 +- 0.00133 seconds time elapsed  ( +-  0.39% )

So, not much difference. But this is not surprising, because test-ifcfg-rh loads and
writes predominantly ifcfg files with few variables. The difference should be visible
when having large files.

1 files changed, 88 insertions, 48 deletions

diff --git a/src/settings/plugins/ifcfg-rh/shvar.c b/src/settings/plugins/ifcfg-rh/shvar.c
index cb0eebcc3a..f9f3550909 100644
--- a/src/settings/plugins/ifcfg-rh/shvar.c
+++ b/src/settings/plugins/ifcfg-rh/shvar.c
@@ -25,8 +25,17 @@
 
 struct _shvarLine {
 
+	const char *key;
+
 	CList lst;
 
+	/* We index variables by their key in shvarFile.lst_idx. One shell variable might
+	 * occur multiple times in a file (in which case the last occurrence wins).
+	 * Hence, we need to keep a list of all the same keys.
+	 *
+	 * This is a pointer to the next shadowed line. */
+	struct _shvarLine *next_shadowed;
+
 	/* There are three cases:
 	 *
 	 * 1) the line is not a valid variable assignment (that is, it doesn't
@@ -44,7 +53,6 @@ struct _shvarLine {
 	 *   @key/@key_with_prefix.
 	 * */
 	char *line;
-	const char *key;
 	char *key_with_prefix;
 
 	/* svSetValue() will clear the dirty flag. */
@@ -54,10 +62,11 @@ struct _shvarLine {
 typedef struct _shvarLine shvarLine;
 
 struct _shvarFile {
-	char      *fileName;
-	int        fd;
-	CList      lst_head;
-	gboolean   modified;
+	char *fileName;
+	CList lst_head;
+	GHashTable *lst_idx;
+	int fd;
+	bool modified:1;
 };
 
 /*****************************************************************************/
@@ -629,6 +638,7 @@ svFile_new (const char *name)
 	s->fd = -1;
 	s->fileName = g_strdup (name);
 	c_list_init (&s->lst_head);
+	s->lst_idx = g_hash_table_new (nm_pstr_hash, nm_pstr_equal);
 	return s;
 }
 
@@ -690,8 +700,8 @@ line_new_parse (const char *value, gsize len)
 
 	line = g_slice_new (shvarLine);
 	*line = (shvarLine) {
-		.lst   = C_LIST_INIT (line->lst),
-		.dirty = TRUE,
+		.lst      = C_LIST_INIT (line->lst),
+		.dirty    = TRUE,
 	};
 
 	for (k = 0; k < len; k++) {
@@ -780,14 +790,49 @@ static void
 line_free (shvarLine *line)
 {
 	ASSERT_shvarLine (line);
+	c_list_unlink_stale (&line->lst);
 	g_free (line->line);
 	g_free (line->key_with_prefix);
-	c_list_unlink_stale (&line->lst);
 	g_slice_free (shvarLine, line);
 }
 
 /*****************************************************************************/
 
+static void
+_line_link_parse (shvarFile *s, const char *value, gsize len)
+{
+	shvarLine *line;
+
+	line = line_new_parse (value, len);
+	if (!line->key) {
+		c_list_link_tail (&s->lst_head, &line->lst);
+		return;
+	}
+
+	if (G_UNLIKELY (!g_hash_table_insert (s->lst_idx, line, line))) {
+		shvarLine *existing_key;
+		shvarLine *existing_val;
+
+		/* Slow-path: we have duplicate keys. Fix the mess we created.
+		 * Unfortunately, g_hash_table_insert() now had to allocate a special
+		 * array to track the keys/values differently. I wish there was an
+		 * API to add a key only if it does not exist yet. */
+
+		if (!g_hash_table_lookup_extended (s->lst_idx, line, (gpointer *) &existing_key, (gpointer *) &existing_val))
+			nm_assert_not_reached ();
+
+		nm_assert (existing_val == line);
+		nm_assert (existing_key != line);
+		line->next_shadowed = existing_key;
+		g_hash_table_replace (s->lst_idx, line, line);
+	}
+
+	c_list_link_tail (&s->lst_head, &line->lst);
+}
+
+/*****************************************************************************/
+
+
 /* Open the file <name>, returning a shvarFile on success and NULL on failure.
  * Add a wrinkle to let the caller specify whether or not to create the file
  * (actually, return a structure anyway) if it doesn't exist.
@@ -845,9 +890,9 @@ svOpenFileInternal (const char *name, gboolean create, GError **error)
 	s = svFile_new (name);
 
 	for (p = arena; (q = strchr (p, '\n')) != NULL; p = q + 1)
-		c_list_link_tail (&s->lst_head, &line_new_parse (p, q - p)->lst);
+		_line_link_parse (s, p, q - p);
 	if (p[0])
-		c_list_link_tail (&s->lst_head, &line_new_parse (p, strlen (p))->lst);
+		_line_link_parse (s, p, strlen (p));
 
 	/* closefd is set if we opened the file read-only, so go ahead and
 	 * close it, because we can't write to it anyway */
@@ -1000,16 +1045,16 @@ svGetKeysSorted (shvarFile *s,
 const char *
 svFindFirstNumberedKey (shvarFile *s, const char *key_prefix)
 {
-	const shvarLine *l;
+	const shvarLine *line;
 
 	g_return_val_if_fail (s, NULL);
 	g_return_val_if_fail (key_prefix, NULL);
 
-	c_list_for_each_entry (l, &s->lst_head, lst) {
-		if (   l->key
-		    && l->line
-		    && nms_ifcfg_rh_util_is_numbered_tag (l->key, key_prefix, NULL))
-			return l->key;
+	c_list_for_each_entry (line, &s->lst_head, lst) {
+		if (   line->key
+		    && line->line
+		    && nms_ifcfg_rh_util_is_numbered_tag (line->key, key_prefix, NULL))
+			return line->key;
 	}
 
 	return NULL;
@@ -1020,8 +1065,7 @@ svFindFirstNumberedKey (shvarFile *s, const char *key_prefix)
 static const char *
 _svGetValue (shvarFile *s, const char *key, char **to_free)
 {
-	CList *current;
-	const shvarLine *line, *l;
+	const shvarLine *line;
 	const char *v;
 
 	nm_assert (s);
@@ -1030,12 +1074,7 @@ _svGetValue (shvarFile *s, const char *key, char **to_free)
 
 	ASSERT_key_is_well_known (key);
 
-	line = NULL;
-	c_list_for_each (current, &s->lst_head) {
-		l = c_list_entry (current, shvarLine, lst);
-		if (l->key && nm_streq (l->key, key))
-			line = l;
-	}
+	line = g_hash_table_lookup (s->lst_idx, &key);
 
 	if (line && line->line) {
 		v = svUnescape (line->line, to_free);
@@ -1226,19 +1265,15 @@ svGetValueEnum (shvarFile *s, const char *key,
 gboolean
 svUnsetAll (shvarFile *s, SvKeyType match_key_type)
 {
-	CList *current;
 	shvarLine *line;
 	gboolean changed = FALSE;
 
 	g_return_val_if_fail (s, FALSE);
 
-	c_list_for_each (current, &s->lst_head) {
-		line = c_list_entry (current, shvarLine, lst);
+	c_list_for_each_entry (line, &s->lst_head, lst) {
 		ASSERT_shvarLine (line);
-		if (!line->key)
-			continue;
-
-		if (_svKeyMatchesType (line->key, match_key_type)) {
+		if (   line->key
+		    && _svKeyMatchesType (line->key, match_key_type)) {
 			if (nm_clear_g_free (&line->line)) {
 				ASSERT_shvarLine (line);
 				changed = TRUE;
@@ -1289,8 +1324,7 @@ svUnsetDirtyWellknown (shvarFile *s, NMTernary new_dirty_value)
 gboolean
 svSetValue (shvarFile *s, const char *key, const char *value)
 {
-	CList *current;
-	shvarLine *line, *l;
+	shvarLine *line;
 	gboolean changed = FALSE;
 
 	g_return_val_if_fail (s, FALSE);
@@ -1300,17 +1334,19 @@ svSetValue (shvarFile *s, const char *key, const char *value)
 
 	ASSERT_key_is_well_known (key);
 
-	line = NULL;
-	c_list_for_each (current, &s->lst_head) {
-		l = c_list_entry (current, shvarLine, lst);
-		if (l->key && nm_streq (l->key, key)) {
-			if (line) {
-				/* if we find multiple entries for the same key, we can
-				 * delete all but the last. */
-				line_free (line);
-				changed = TRUE;
-			}
-			line = l;
+	line = g_hash_table_lookup (s->lst_idx, &key);
+	if (line) {
+		shvarLine *l_curr;
+
+		/* if we find multiple entries for the same key, we can
+		 * delete all but the last. */
+		l_curr = g_steal_pointer (&line->next_shadowed);
+		while (l_curr) {
+			shvarLine *l = l_curr;
+
+			l_curr = l_curr->next_shadowed;
+			line_free (l);
+			changed = TRUE;
 		}
 	}
 
@@ -1324,7 +1360,10 @@ svSetValue (shvarFile *s, const char *key, const char *value)
 		}
 	} else {
 		if (!line) {
-			c_list_link_tail (&s->lst_head, &line_new_build (key, value)->lst);
+			line = line_new_build (key, value);
+			if (!g_hash_table_add (s->lst_idx, line))
+				nm_assert_not_reached ();
+			c_list_link_tail (&s->lst_head, &line->lst);
 			changed = TRUE;
 		} else {
 			if (line_set (line, value))
@@ -1476,14 +1515,15 @@ svWriteFile (shvarFile *s, int mode, GError **error)
 void
 svCloseFile (shvarFile *s)
 {
-	CList *current, *safe;
+	shvarLine *line;
 
 	g_return_if_fail (s != NULL);
 
 	if (s->fd >= 0)
 		nm_close (s->fd);
 	g_free (s->fileName);
-	c_list_for_each_safe (current, safe, &s->lst_head)
-		line_free (c_list_entry (current, shvarLine, lst));
+	g_hash_table_destroy (s->lst_idx);
+	while ((line = c_list_first_entry (&s->lst_head, shvarLine, lst)))
+		line_free (line);
 	g_slice_free (shvarFile, s);
 }