[icinga-checkins] icinga.org: icinga-core/dev/cgis: core: use binary search when looking up macro names, instead of insane strcmp() loops (Andreas Ericsson) #2675

git at icinga.org git at icinga.org
Wed Aug 1 03:00:27 CEST 2012


Module: icinga-core
Branch: dev/cgis
Commit: debab1404363412551aaa940bf6a8831541b29f1
URL:    https://git.icinga.org/?p=icinga-core.git;a=commit;h=debab1404363412551aaa940bf6a8831541b29f1

Author: Michael Friedrich <michael.friedrich at univie.ac.at>
Date:   Fri Jul  6 17:48:00 2012 +0200

core: use binary search when looking up macro names, instead of insane strcmp() loops (Andreas Ericsson) #2675

without the patch, it currently happens like this

on each macro grabbing, a strcmp() happens to see which macro name this
is on each macro grabbing, the cleaning options are determined
strcmp()'s are pretty expensive, especially as macros are called that
frequently (like HOSTADDRESS).

the patch adds 2 things

- shortcuts for the most common used macros (HOSTADDRESS and HOSTADDRESS6)
  which can be strcmp()'ed and returned early, without any special
  cleaning options
- a precomputed array, sorted by macro name, on macro initialization,
  which is then gone through with binary comparison on the actual
  strcmp()'s

sorting the array alphabethical allows to compare it by value, as
strcmp() would then output. you'll check wether it's greater or less
than the mid value of the array. depending on the returned value of
strcmp() you'll either return the key (0), or step down into the logical
half, left or right. such a seek is pretty much more efficient than a
hash table, as the macro names are rather long in direct comparison with
a unique hash id being calculated.

since the previous version ran within a loop through all available
macros (MACRO_X_COUNT = 154) calling strcmp() which results in an O(n)
complexity for each xmacro, it can be reduced to O(log(n)) complexity by
using the precomputed sorted array with the binary search lookups with
strcmp()

requires further tests and profiling though.

refs #2675

---

 Changelog       |    3 +-
 common/macros.c |  134 +++++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 98 insertions(+), 39 deletions(-)

diff --git a/Changelog b/Changelog
index 788ee0c..41b1777 100644
--- a/Changelog
+++ b/Changelog
@@ -10,8 +10,9 @@ ENHANCEMENTS
 * core/classic ui: make hashfunc more efficient by using sdbm #2761
 * core: try the most common macros ($ARGn$, $USERn$) first (Andreas Ericsson) #2674
 * core: handle passive checks via external commands the same way as active checks, bypassing the temp check result file and reaper (Andreas Ericsson) #2687
+* core: use binary search when looking up macro names, instead of insane strcmp() loops (Andreas Ericsson) #2675
 
-* icinga.spec: add devel package 2634
+* icinga.spec: add devel package #2634
 
 FIXES
 * core: unify check scheduling replacement logic for new events (Andreas Ericsson) #2676
diff --git a/common/macros.c b/common/macros.c
index 3296d04..5f69099 100644
--- a/common/macros.c
+++ b/common/macros.c
@@ -56,6 +56,15 @@ extern timeperiod       *timeperiod_list;
 char *macro_x_names[MACRO_X_COUNT]; /* the macro names */
 char *macro_user[MAX_USER_MACROS]; /* $USERx$ macros */
 
+struct macro_key_code {
+	char *name; /* macro key name */
+	int code;  /* numeric macro code, usable in case statements */
+	int clean_options;
+	char *value;
+};
+
+struct macro_key_code macro_keys[MACRO_X_COUNT];
+
 /**
  * These point to their corresponding pointer arrays in global_macros
  * AFTER macros have been initialized.
@@ -83,6 +92,34 @@ icinga_macros *get_global_macros(void) {
 /************************ MACRO FUNCTIONS *************************/
 /******************************************************************/
 
+
+/*
+ * locate a macro key based on its name by using a binary search
+ * over all keys. O(log(n)) complexity and a vast improvement over
+ * the previous linear scan
+ */
+const struct macro_key_code *find_macro_key(const char *name) {
+	unsigned int high, low = 0;
+	int value;
+	struct macro_key_code *key;
+
+	high = MACRO_X_COUNT;
+	while (high - low > 0) {
+		unsigned int mid = low + ((high - low) / 2);
+		key = &macro_keys[mid];
+		value = strcmp(name, key->name);
+		if (value == 0) {
+			return key;
+		}
+		if (value > 0)
+			low = mid + 1;
+		else
+			high = mid;
+	}
+	return NULL;
+}
+
+
 /**
  * replace macros in notification commands with their values,
  * the thread-safe version
@@ -446,8 +483,9 @@ int grab_macro_value_r(icinga_macros *mac, char *macro_buffer, char **output, in
 	contactsmember *temp_contactsmember = NULL;
 	char *temp_buffer = NULL;
 	int delimiter_len = 0;
-	register int x;
-	int result = OK;
+	int x, result = OK;
+	const struct macro_key_code *mkey;
+
 	/* for the early cases, this is the default */
 	*free_macro = FALSE;
 
@@ -495,6 +533,19 @@ int grab_macro_value_r(icinga_macros *mac, char *macro_buffer, char **output, in
 		return OK;
 	}
 
+	/* most frequently used "x" macro gets a shortcut */
+	if (mac->host_ptr && !strcmp(macro_buffer, "HOSTADDRESS")) {
+		if (mac->host_ptr->address)
+			*output = mac->host_ptr->address;
+		return OK;
+	}
+
+	if (mac->host_ptr && !strcmp(macro_buffer, "HOSTADDRESS6")) {
+		if (mac->host_ptr->address6)
+			*output = mac->host_ptr->address6;
+		return OK;
+	}
+
 	/* work with a copy of the original buffer */
 	if ((buf = (char *)strdup(macro_buffer)) == NULL)
 		return ERROR;
@@ -526,41 +577,16 @@ int grab_macro_value_r(icinga_macros *mac, char *macro_buffer, char **output, in
 	}
 
 	/***** X MACROS *****/
-	/* see if this is an x macro */
-	for (x = 0; x < MACRO_X_COUNT; x++) {
-
-		if (macro_x_names[x] == NULL)
-			continue;
-
-		if (!strcmp(macro_name, macro_x_names[x])) {
-
-			log_debug_info(DEBUGL_MACROS, 2, "  macros[%d] (%s) match.\n", x, macro_x_names[x]);
-
-			/* get the macro value */
-			result = grab_macrox_value_r(mac, x, arg[0], arg[1], output, free_macro);
-
-			/* post-processing */
-			/* host/service output/perfdata and author/comment macros should get cleaned */
-			if ((x >= 16 && x <= 19) || (x >= 49 && x <= 52) || (x >= 99 && x <= 100) || (x >= 124 && x <= 127)) {
-				*clean_options |= (STRIP_ILLEGAL_MACRO_CHARS | ESCAPE_MACRO_CHARS);
-				log_debug_info(DEBUGL_MACROS, 2, "  New clean options: %d\n", *clean_options);
-			}
-			/* url macros should get cleaned */
-			if ((x >= 125 && x <= 126) || (x >= 128 && x <= 129) || (x >= 77 && x <= 78) || (x >= 74 && x <= 75)) {
-				*clean_options |= URL_ENCODE_MACRO_CHARS;
-				log_debug_info(DEBUGL_MACROS, 2, "  New clean options: %d\n", *clean_options);
-			}
-
-
-
-
-			break;
+	if ((mkey = find_macro_key(macro_name))) {
+		log_debug_info(DEBUGL_MACROS, 2, "  macros[%d] (%s) match.\n", mkey->code, macro_x_names[mkey->code]);
+		if (mkey->clean_options) {
+			*clean_options |= mkey->clean_options;
+			log_debug_info(DEBUGL_MACROS, 2, "  New clean options: %d\n", *clean_options);
 		}
-	}
 
-	/* we already found the macro... */
-	if (x < MACRO_X_COUNT)
-		x = x;
+		/* get the macro value */
+		result = grab_macrox_value_r(mac, mkey->code, arg[0], arg[1], output, free_macro);
+	}
 
 	/***** CONTACT ADDRESS MACROS *****/
 	/* NOTE: the code below should be broken out into a separate function */
@@ -2607,6 +2633,12 @@ char *get_url_encoded_string(char *input) {
 }
 
 
+static int macro_key_cmp(const void *a_, const void *b_) {
+	struct macro_key_code *a = (struct macro_key_code *)a_;
+	struct macro_key_code *b = (struct macro_key_code *)b_;
+
+	return strcmp(a->name, b->name);
+}
 
 /******************************************************************/
 /***************** MACRO INITIALIZATION FUNCTIONS *****************/
@@ -2617,6 +2649,8 @@ char *get_url_encoded_string(char *input) {
  */
 int init_macros(void) {
 
+	int x;
+
 	init_macrox_names();
 
 	/*
@@ -2631,6 +2665,30 @@ int init_macros(void) {
 	/* backwards compatibility hack */
 	macro_x = global_macros.x;
 
+	/*
+	 * Now build an ordered list of X macro names so we can
+	 * do binary lookups later and avoid a ton of strcmp()'s
+	 * for each and every check that gets run. A hash table
+	 * is actually slower, since the most frequently used
+	 * keys are so long and a binary lookup is completed in
+	 * 7 steps for up to ~200 keys, worst case.
+	 */
+	for (x = 0; x < MACRO_X_COUNT; x++) {
+		macro_keys[x].code = x;
+		macro_keys[x].name = macro_x_names[x];
+
+		/* host/service output/perfdata and author/comment macros should get cleaned */
+		if ((x >= 16 && x <= 19) || (x >= 49 && x <= 52) || (x >= 99 && x <= 100) || (x >= 124 && x <= 127)) {
+			macro_keys[x].clean_options = (STRIP_ILLEGAL_MACRO_CHARS | ESCAPE_MACRO_CHARS);
+		}
+		/* url macros should get cleaned */
+		if ((x >= 125 && x <= 126) || (x >= 128 && x <= 129) || (x >= 77 && x <= 78) || (x >= 74 && x <= 75)) {
+			macro_keys[x].clean_options = URL_ENCODE_MACRO_CHARS;
+		}
+	}
+
+	qsort(macro_keys, x, sizeof(struct macro_key_code), macro_key_cmp);
+
 	return OK;
 }
 
@@ -2973,13 +3031,13 @@ int clear_service_macros_r(icinga_macros *mac) {
 	my_free(mac->x[MACRO_SERVICEOUTPUT]);
 	my_free(mac->x[MACRO_LONGSERVICEOUTPUT]);
 	my_free(mac->x[MACRO_SERVICEPERFDATA]);
-	
+
 	/* recursive, but persistent */
 	my_free(mac->x[MACRO_SERVICECHECKCOMMAND]);
 	my_free(mac->x[MACRO_SERVICEACTIONURL]);
 	my_free(mac->x[MACRO_SERVICENOTESURL]);
 	my_free(mac->x[MACRO_SERVICENOTES]);
-	
+
 	/* numbers or necessarily autogenerated string */
 	my_free(mac->x[MACRO_SERVICECHECKTYPE]);
 	my_free(mac->x[MACRO_SERVICESTATETYPE]);
@@ -3112,7 +3170,7 @@ int clear_hostgroup_macros_r(icinga_macros *mac) {
 	/* these are strings */
 	my_free(mac->x[MACRO_HOSTGROUPNAME]);
 	my_free(mac->x[MACRO_HOSTGROUPALIAS]);
-	
+
 	/* generated */
 	my_free(mac->x[MACRO_HOSTGROUPMEMBERS]);
 





More information about the icinga-checkins mailing list