[quagga-dev 12132] [PATCH] lib/cli: reduce strcmp in CLI hot paths

David Lamparter equinox at opensourcerouting.org
Mon Apr 13 09:08:13 BST 2015


Er, no idea how anyone could ever have thought that it would be a good
idea to have a zillion of strcmp() calls in the CLI's active paths, just
to compare against things like "A.B.C.D".

Reduces 40k prefix list load time from 1.65s to 1.23s (1.34:1).

Signed-off-by: David Lamparter <equinox at opensourcerouting.org>
---
 lib/command.c | 284 ++++++++++++++++++++++++++++++++--------------------------
 lib/command.h |  33 +++++--
 2 files changed, 183 insertions(+), 134 deletions(-)

diff --git a/lib/command.c b/lib/command.c
index 8317789..eb84350 100644
--- a/lib/command.c
+++ b/lib/command.c
@@ -506,6 +506,25 @@ format_parser_read_word(struct format_parser_state *state)
 
   token = XCALLOC(MTYPE_CMD_TOKENS, sizeof(*token));
   token->type = TOKEN_TERMINAL;
+  if (CMDS_OPTION (cmd))
+    token->terminal = TERMINAL_OPTION;
+  else if (CMDS_VARIABLE (cmd))
+    token->terminal = TERMINAL_VARIABLE;
+  else if (CMDS_VARARG (cmd))
+    token->terminal = TERMINAL_VARARG;
+  else if (CMDS_RANGE (cmd))
+    token->terminal = TERMINAL_RANGE;
+  else if (CMDS_IPV4 (cmd))
+    token->terminal = TERMINAL_IPV4;
+  else if (CMDS_IPV4_PREFIX (cmd))
+    token->terminal = TERMINAL_IPV4_PREFIX;
+  else if (CMDS_IPV6 (cmd))
+    token->terminal = TERMINAL_IPV6;
+  else if (CMDS_IPV6_PREFIX (cmd))
+    token->terminal = TERMINAL_IPV6_PREFIX;
+  else
+    token->terminal = TERMINAL_LITERAL;
+
   token->cmd = cmd;
   token->desc = format_parser_desc_str(state);
   vector_set(state->curvect, token);
@@ -1171,59 +1190,61 @@ cmd_word_match(struct cmd_token *token,
   if (!word)
     return no_match;
 
-  if (CMD_VARARG(str))
-    {
-      return vararg_match;
-    }
-  else if (CMD_RANGE(str))
-    {
-      if (cmd_range_match(str, word))
-        return range_match;
-    }
-#ifdef HAVE_IPV6
-  else if (CMD_IPV6(str))
-    {
-      match_type = cmd_ipv6_match(word);
-      if ((filter == FILTER_RELAXED && match_type != no_match)
-          || (filter == FILTER_STRICT && match_type == exact_match))
-        return ipv6_match;
-    }
-  else if (CMD_IPV6_PREFIX(str))
-    {
-      match_type = cmd_ipv6_prefix_match(word);
-      if ((filter == FILTER_RELAXED && match_type != no_match)
-          || (filter == FILTER_STRICT && match_type == exact_match))
-        return ipv6_prefix_match;
-    }
-#endif /* HAVE_IPV6 */
-  else if (CMD_IPV4(str))
-    {
-      match_type = cmd_ipv4_match(word);
-      if ((filter == FILTER_RELAXED && match_type != no_match)
-          || (filter == FILTER_STRICT && match_type == exact_match))
-        return ipv4_match;
-    }
-  else if (CMD_IPV4_PREFIX(str))
+  switch (token->terminal)
     {
-      match_type = cmd_ipv4_prefix_match(word);
-      if ((filter == FILTER_RELAXED && match_type != no_match)
+      case TERMINAL_VARARG:
+        return vararg_match;
+
+      case TERMINAL_RANGE:
+        if (cmd_range_match(str, word))
+          return range_match;
+        break;
+
+      case TERMINAL_IPV6:
+        match_type = cmd_ipv6_match(word);
+        if ((filter == FILTER_RELAXED && match_type != no_match)
           || (filter == FILTER_STRICT && match_type == exact_match))
-        return ipv4_prefix_match;
-    }
-  else if (CMD_OPTION(str) || CMD_VARIABLE(str))
-    {
-      return extend_match;
-    }
-  else
-    {
-      if (filter == FILTER_RELAXED && !strncmp(str, word, strlen(word)))
-        {
-          if (!strcmp(str, word))
-            return exact_match;
-          return partly_match;
-        }
-      if (filter == FILTER_STRICT && !strcmp(str, word))
-        return exact_match;
+          return ipv6_match;
+        break;
+
+      case TERMINAL_IPV6_PREFIX:
+        match_type = cmd_ipv6_prefix_match(word);
+        if ((filter == FILTER_RELAXED && match_type != no_match)
+            || (filter == FILTER_STRICT && match_type == exact_match))
+          return ipv6_prefix_match;
+        break;
+
+      case TERMINAL_IPV4:
+        match_type = cmd_ipv4_match(word);
+        if ((filter == FILTER_RELAXED && match_type != no_match)
+            || (filter == FILTER_STRICT && match_type == exact_match))
+          return ipv4_match;
+        break;
+
+      case TERMINAL_IPV4_PREFIX:
+        match_type = cmd_ipv4_prefix_match(word);
+        if ((filter == FILTER_RELAXED && match_type != no_match)
+            || (filter == FILTER_STRICT && match_type == exact_match))
+          return ipv4_prefix_match;
+        break;
+
+      case TERMINAL_OPTION:
+      case TERMINAL_VARIABLE:
+        return extend_match;
+
+      case TERMINAL_LITERAL:
+        if (filter == FILTER_RELAXED && !strncmp(str, word, strlen(word)))
+          {
+            if (!strcmp(str, word))
+              return exact_match;
+            return partly_match;
+          }
+        if (filter == FILTER_STRICT && !strcmp(str, word))
+          return exact_match;
+        break;
+
+      default:
+        assert (0);
     }
 
   return no_match;
@@ -1307,7 +1328,7 @@ cmd_matcher_match_terminal(struct cmd_matcher *matcher,
 
   if (!cmd_matcher_words_left(matcher))
     {
-      if (CMD_OPTION(token->cmd))
+      if (token->terminal == TERMINAL_OPTION)
         return MATCHER_OK; /* missing optional args are NOT pushed as NULL */
       else
         return MATCHER_INCOMPLETE;
@@ -1320,9 +1341,9 @@ cmd_matcher_match_terminal(struct cmd_matcher *matcher,
 
   /* We have to record the input word as argument if it matched
    * against a variable. */
-  if (CMD_VARARG(token->cmd)
-      || CMD_VARIABLE(token->cmd)
-      || CMD_OPTION(token->cmd))
+  if (token->terminal == TERMINAL_VARARG
+      || token->terminal == TERMINAL_VARIABLE
+      || token->terminal == TERMINAL_OPTION)
     {
       if (push_argument(argc, argv, word))
         return MATCHER_EXCEED_ARGC_MAX;
@@ -1333,7 +1354,7 @@ cmd_matcher_match_terminal(struct cmd_matcher *matcher,
   matcher->word_index++;
 
   /* A vararg token should consume all left over words as arguments */
-  if (CMD_VARARG(token->cmd))
+  if (token->terminal == TERMINAL_VARARG)
     while (cmd_matcher_words_left(matcher))
       {
         word = cmd_matcher_get_word(matcher);
@@ -1564,9 +1585,9 @@ cmd_matcher_build_keyword_args(struct cmd_matcher *matcher,
                 {
                   word_token = vector_slot(keyword_vector, j);
                   if ((word_token->type == TOKEN_TERMINAL
-                       && (CMD_VARARG(word_token->cmd)
-                           || CMD_VARIABLE(word_token->cmd)
-                           || CMD_OPTION(word_token->cmd)))
+                       && (word_token->terminal == TERMINAL_VARARG
+                           || word_token->terminal == TERMINAL_VARIABLE
+                           || word_token->terminal == TERMINAL_OPTION))
                       || word_token->type == TOKEN_MULTIPLE)
                     {
                       if (push_argument(argc, argv, NULL))
@@ -1852,12 +1873,14 @@ is_cmd_ambiguous (vector cmd_vector,
 	      switch (type)
 		{
 		case exact_match:
-		  if (!(CMD_OPTION (str) || CMD_VARIABLE (str))
+		  if (!(cmd_token->terminal == TERMINAL_OPTION
+                        || cmd_token->terminal == TERMINAL_VARIABLE)
 		      && strcmp (command, str) == 0)
 		    match++;
 		  break;
 		case partly_match:
-		  if (!(CMD_OPTION (str) || CMD_VARIABLE (str))
+		  if (!(cmd_token->terminal == TERMINAL_OPTION
+                        || cmd_token->terminal == TERMINAL_VARIABLE)
 		      && strncmp (command, str, strlen (command)) == 0)
 		    {
 		      if (matched && strcmp (matched, str) != 0)
@@ -1879,7 +1902,7 @@ is_cmd_ambiguous (vector cmd_vector,
 		  break;
 #ifdef HAVE_IPV6
 		case ipv6_match:
-		  if (CMD_IPV6 (str))
+		  if (cmd_token->terminal == TERMINAL_IPV6)
 		    match++;
 		  break;
 		case ipv6_prefix_match:
@@ -1893,7 +1916,7 @@ is_cmd_ambiguous (vector cmd_vector,
 		  break;
 #endif /* HAVE_IPV6 */
 		case ipv4_match:
-		  if (CMD_IPV4 (str))
+		  if (cmd_token->terminal == TERMINAL_IPV4)
 		    match++;
 		  break;
 		case ipv4_prefix_match:
@@ -1906,7 +1929,8 @@ is_cmd_ambiguous (vector cmd_vector,
 		    }
 		  break;
 		case extend_match:
-		  if (CMD_OPTION (str) || CMD_VARIABLE (str))
+		  if (cmd_token->terminal == TERMINAL_OPTION
+                      || cmd_token->terminal == TERMINAL_VARIABLE)
 		    match++;
 		  break;
 		case no_match:
@@ -1922,12 +1946,23 @@ is_cmd_ambiguous (vector cmd_vector,
 
 /* If src matches dst return dst string, otherwise return NULL */
 static const char *
-cmd_entry_function (const char *src, const char *dst)
+cmd_entry_function (const char *src, struct cmd_token *token)
 {
+  const char *dst = token->cmd;
+
   /* Skip variable arguments. */
-  if (CMD_OPTION (dst) || CMD_VARIABLE (dst) || CMD_VARARG (dst) ||
-      CMD_IPV4 (dst) || CMD_IPV4_PREFIX (dst) || CMD_RANGE (dst))
-    return NULL;
+  switch (token->terminal)
+    {
+      case TERMINAL_OPTION:
+      case TERMINAL_VARIABLE:
+      case TERMINAL_VARARG:
+      case TERMINAL_IPV4:
+      case TERMINAL_IPV4_PREFIX:
+      case TERMINAL_RANGE:
+        return NULL;
+      default:
+        break;
+    }
 
   /* In case of 'command \t', given src is NULL string. */
   if (src == NULL)
@@ -1944,65 +1979,63 @@ cmd_entry_function (const char *src, const char *dst)
 /* This version will return the dst string always if it is
    CMD_VARIABLE for '?' key processing */
 static const char *
-cmd_entry_function_desc (const char *src, const char *dst)
+cmd_entry_function_desc (const char *src, struct cmd_token *token)
 {
-  if (CMD_VARARG (dst))
-    return dst;
-
-  if (CMD_RANGE (dst))
-    {
-      if (cmd_range_match (dst, src))
-	return dst;
-      else
-	return NULL;
-    }
-
-#ifdef HAVE_IPV6
-  if (CMD_IPV6 (dst))
-    {
-      if (cmd_ipv6_match (src))
-	return dst;
-      else
-	return NULL;
-    }
-
-  if (CMD_IPV6_PREFIX (dst))
-    {
-      if (cmd_ipv6_prefix_match (src))
-	return dst;
-      else
-	return NULL;
-    }
-#endif /* HAVE_IPV6 */
+  const char *dst = token->cmd;
 
-  if (CMD_IPV4 (dst))
+  switch (token->terminal)
     {
-      if (cmd_ipv4_match (src))
-	return dst;
-      else
-	return NULL;
-    }
-
-  if (CMD_IPV4_PREFIX (dst))
-    {
-      if (cmd_ipv4_prefix_match (src))
-	return dst;
-      else
-	return NULL;
+      case TERMINAL_VARARG:
+        return dst;
+
+      case TERMINAL_RANGE:
+        if (cmd_range_match (dst, src))
+          return dst;
+        else
+          return NULL;
+
+      case TERMINAL_IPV6:
+        if (cmd_ipv6_match (src))
+          return dst;
+        else
+          return NULL;
+
+      case TERMINAL_IPV6_PREFIX:
+        if (cmd_ipv6_prefix_match (src))
+          return dst;
+        else
+          return NULL;
+
+      case TERMINAL_IPV4:
+        if (cmd_ipv4_match (src))
+          return dst;
+        else
+          return NULL;
+
+      case TERMINAL_IPV4_PREFIX:
+        if (cmd_ipv4_prefix_match (src))
+          return dst;
+        else
+          return NULL;
+
+      /* Optional or variable commands always match on '?' */
+      case TERMINAL_OPTION:
+      case TERMINAL_VARIABLE:
+        return dst;
+
+      case TERMINAL_LITERAL:
+        /* In case of 'command \t', given src is NULL string. */
+        if (src == NULL)
+          return dst;
+
+        if (strncmp (src, dst, strlen (src)) == 0)
+          return dst;
+        else
+          return NULL;
+
+      default:
+        assert(0);
     }
-
-  /* Optional or variable commands always match on '?' */
-  if (CMD_OPTION (dst) || CMD_VARIABLE (dst))
-    return dst;
-
-  /* In case of 'command \t', given src is NULL string. */
-  if (src == NULL)
-    return dst;
-
-  if (strncmp (src, dst, strlen (src)) == 0)
-    return dst;
-  else
-    return NULL;
 }
 
 /**
@@ -2217,7 +2250,7 @@ cmd_describe_command_real (vector vline, struct vty *vty, int *status)
               struct cmd_token *token = vector_slot(match_vector, j);
               const char *string;
 
-              string = cmd_entry_function_desc(command, token->cmd);
+              string = cmd_entry_function_desc(command, token);
               if (string && desc_unique_string(matchvec, string))
                 vector_set(matchvec, token);
             }
@@ -2419,7 +2452,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status)
 		{
 		  if ((string = 
 		       cmd_entry_function (vector_slot (vline, index),
-					   token->cmd)))
+					   token)))
 		    if (cmd_unique_string (matchvec, string))
 		      vector_set (matchvec, XSTRDUP (MTYPE_TMP, string));
 		}
@@ -4007,6 +4040,7 @@ cmd_init (int terminal)
 {
   command_cr = XSTRDUP(MTYPE_CMD_TOKENS, "<cr>");
   token_cr.type = TOKEN_TERMINAL;
+  token_cr.terminal = TERMINAL_LITERAL;
   token_cr.cmd = command_cr;
   token_cr.desc = XSTRDUP(MTYPE_CMD_TOKENS, "");
 
diff --git a/lib/command.h b/lib/command.h
index 8eb0cbd..2824f9e 100644
--- a/lib/command.h
+++ b/lib/command.h
@@ -151,10 +151,25 @@ enum cmd_token_type
   TOKEN_KEYWORD,
 };
 
+enum cmd_terminal_type
+{
+  _TERMINAL_BUG = 0,
+  TERMINAL_LITERAL,
+  TERMINAL_OPTION,
+  TERMINAL_VARIABLE,
+  TERMINAL_VARARG,
+  TERMINAL_RANGE,
+  TERMINAL_IPV4,
+  TERMINAL_IPV4_PREFIX,
+  TERMINAL_IPV6,
+  TERMINAL_IPV6_PREFIX,
+};
+
 /* Command description structure. */
 struct cmd_token
 {
   enum cmd_token_type type;
+  enum cmd_terminal_type terminal;
 
   /* Used for type == MULTIPLE */
   vector multiple; /* vector of cmd_token, type == FINAL */
@@ -438,15 +453,15 @@ struct cmd_token
 #endif /* VTYSH_EXTRACT_PL */
 
 /* Some macroes */
-#define CMD_OPTION(S)   ((S[0]) == '[')
-#define CMD_VARIABLE(S) (((S[0]) >= 'A' && (S[0]) <= 'Z') || ((S[0]) == '<'))
-#define CMD_VARARG(S)   ((S[0]) == '.')
-#define CMD_RANGE(S)	((S[0] == '<'))
-
-#define CMD_IPV4(S)	   ((strcmp ((S), "A.B.C.D") == 0))
-#define CMD_IPV4_PREFIX(S) ((strcmp ((S), "A.B.C.D/M") == 0))
-#define CMD_IPV6(S)        ((strcmp ((S), "X:X::X:X") == 0))
-#define CMD_IPV6_PREFIX(S) ((strcmp ((S), "X:X::X:X/M") == 0))
+#define CMDS_OPTION(S)   ((S[0]) == '[')
+#define CMDS_VARIABLE(S) (((S[0]) >= 'A' && (S[0]) <= 'Z') || ((S[0]) == '<'))
+#define CMDS_VARARG(S)   ((S[0]) == '.')
+#define CMDS_RANGE(S)    ((S[0] == '<'))
+
+#define CMDS_IPV4(S)        ((strcmp ((S), "A.B.C.D") == 0))
+#define CMDS_IPV4_PREFIX(S) ((strcmp ((S), "A.B.C.D/M") == 0))
+#define CMDS_IPV6(S)        ((strcmp ((S), "X:X::X:X") == 0))
+#define CMDS_IPV6_PREFIX(S) ((strcmp ((S), "X:X::X:X/M") == 0))
 
 /* Common descriptions. */
 #define SHOW_STR "Show running system information\n"
-- 
2.0.4





More information about the Quagga-dev mailing list