Skip to contentSkip to conversation

nodups_specs: speedup

RFC PATCH New [email protected] 1 participant 1 message Aug 31, 2016 SELinux security module

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 nodups_specs: speedup

From: William Roberts <[email protected]>

I noticed, via gprof, that the time spent in nodups_specs() accounts for 100% of the label_open() call.

It seems as though the N^2 comparison using strcmp is very slow.

Do two major things:
1. move the rec->validating check to the left, check the simple thing first before runnning the expensive strcmp(). strcmp() is used to check string equality, check lengths first.
2. strlen() is used all over to calculate lengths, just store it in a struct with the string so its usable elsewhere, rather than recalculating it.

text 21.4% speedup:
before text: 248
after text: 195

binary 24.6% speedup:
before bin: 236
after bin: 178

Some things to ponder:
1. We can use C ABI safe pointer instead of len_str structure
https://bitbucket.org/billcroberts/twist
There are pros and cons to this approach, namely if someone calls free(x) instead of twist_free(x)
It also currently has 0 support for stack based strings (simple enough to add). I think this approach is overkill here.

2. The location of the str_len struct and routines should likely move elsewhere.

3. The impact on Android is currently unmeasured, that's next. Also, bionic uses something from label_file.h for processing property_contexts for the Android property subsystem... so need to ensure that all works as advertised still.

Things to do:
1. Cleanup the code locations, likely a util.h or a len_str.h, a better name would be nice.
2. Spell check this commit message

---
 libselinux/src/label.c                  |  8 ++--
 libselinux/src/label_android_property.c | 44 +++++++++----------
 libselinux/src/label_db.c               |  7 +--
 libselinux/src/label_file.c             | 63 ++++++++++++++------------
 libselinux/src/label_file.h             | 78 +++++++++++++++++++--------------
 libselinux/src/label_internal.h         | 22 +++++++++-
 libselinux/src/label_media.c            |  5 ++-
 libselinux/src/label_support.c          | 32 ++++++++------
 libselinux/src/label_x.c                |  5 ++-
 libselinux/src/matchpathcon.c           |  2 +-
 10 files changed, 159 insertions(+), 107 deletions(-)
libselinux/src/label.c +4 -4
index 963bfcb..11324ea 100644
@@ -209,7 +209,7 @@ int selabel_validate(struct selabel_handle *rec,
 	if (!rec->validating || contexts->validated)
 		goto out;
 
-	rc = selinux_validate(&contexts->ctx_raw);
+	rc = selinux_validate(&contexts->ctx_raw.str);
 	if (rc < 0)
 		goto out;
 
@@ -248,7 +248,7 @@ static int selabel_fini(struct selabel_handle *rec,
 		return -1;
 
 	if (translating && !lr->ctx_trans &&
-	    selinux_raw_to_trans_context(lr->ctx_raw, &lr->ctx_trans))
+	    selinux_raw_to_trans_context(lr->ctx_raw.str, &lr->ctx_trans))
 		return -1;
 
 	return 0;
@@ -369,7 +369,7 @@ int selabel_lookup_raw(struct selabel_handle *rec, char **con,
 	if (!lr)
 		return -1;
 
-	*con = strdup(lr->ctx_raw);
+	*con = strdup(lr->ctx_raw.str);
 	return *con ? 0 : -1;
 }
 
@@ -429,7 +429,7 @@ int selabel_lookup_best_match_raw(struct selabel_handle *rec, char **con,
 	if (!lr)
 		return -1;
 
-	*con = strdup(lr->ctx_raw);
+	*con = strdup(lr->ctx_raw.str);
 	return *con ? 0 : -1;
 }
 
libselinux/src/label_android_property.c +22 -22

105 lines not on this page · raw message

libselinux/src/label_db.c +4 -3
index 1155bcc..c700aca 100644
@@ -153,7 +153,8 @@ process_line(const char *path, char *line_buf, unsigned int line_num,
 
 	free(type);
 	spec->key = key;
-	spec->lr.ctx_raw = context;
+	spec->lr.ctx_raw.str = context;
+	spec->lr.ctx_raw.len = strlen(context);
 
 	catalog->nspec++;
 
@@ -181,7 +182,7 @@ db_close(struct selabel_handle *rec)
 	for (i = 0; i < catalog->nspec; i++) {
 		spec = &catalog->specs[i];
 		free(spec->key);
-		free(spec->lr.ctx_raw);
+		free(spec->lr.ctx_raw.str);
 		free(spec->lr.ctx_trans);
 	}
 	free(catalog);
@@ -333,7 +334,7 @@ out_error:
 		spec_t	       *spec = &catalog->specs[i];
 
 		free(spec->key);
-		free(spec->lr.ctx_raw);
+		free(spec->lr.ctx_raw.str);
 		free(spec->lr.ctx_trans);
 	}
 	free(catalog);
libselinux/src/label_file.c +36 -27

150 lines not on this page · raw message

libselinux/src/label_file.h +46 -32

167 lines not on this page · raw message

libselinux/src/label_internal.h +21 -1
index aa48fff..51aa33d 100644
@@ -71,8 +71,28 @@ extern struct selabel_sub *selabel_subs_init(const char *path,
 				    struct selabel_sub *list,
 				    struct selabel_digest *digest);
 
+/*
+ * A simple struct for tracking string lengths
+ * with strings.
+ */
+struct len_str {
+	size_t len;
+	char *str;
+};
+
+static inline bool len_str_eq(struct len_str *a, struct len_str *b)
+{
+	if (a->len != b->len)
+		return false;
+
+	if (a->str == b->str)
+		return true;
+
+	return !strcmp(a->str, b->str);
+}
+
 struct selabel_lookup_rec {
-	char * ctx_raw;
+	struct len_str ctx_raw;
 	char * ctx_trans;
 	int validated;
 };
libselinux/src/label_media.c +3 -2
index 622741b..e85e973 100644
@@ -56,7 +56,8 @@ static int process_line(const char *path, char *line_buf, int pass,
 
 	if (pass == 1) {
 		data->spec_arr[data->nspec].key = key;
-		data->spec_arr[data->nspec].lr.ctx_raw = context;
+		data->spec_arr[data->nspec].lr.ctx_raw.str = context;
+		data->spec_arr[data->nspec].lr.ctx_raw.len = strlen(context);
 	}
 
 	data->nspec++;
@@ -159,7 +160,7 @@ static void close(struct selabel_handle *rec)
 	for (i = 0; i < data->nspec; i++) {
 		spec = &spec_arr[i];
 		free(spec->key);
-		free(spec->lr.ctx_raw);
+		free(spec->lr.ctx_raw.str);
 		free(spec->lr.ctx_trans);
 	}
 
libselinux/src/label_support.c +19 -13
index 26f9ef1..e9b842f 100644
@@ -22,16 +22,17 @@
  *            errno will be set.
  *
  */
-static inline int read_spec_entry(char **entry, char **ptr, int *len, const char **errbuf)
+static inline int read_spec_entry(struct len_str *entry, char **ptr, const char **errbuf)
 {
-	*entry = NULL;
+	size_t len = 0;
 	char *tmp_buf = NULL;
 
+	memset(entry, 0, sizeof(*entry));
+
 	while (isspace(**ptr) && **ptr != '\0')
 		(*ptr)++;
 
 	tmp_buf = *ptr;
-	*len = 0;
 
 	while (!isspace(**ptr) && **ptr != '\0') {
 		if (!isascii(**ptr)) {
@@ -40,13 +41,15 @@ static inline int read_spec_entry(char **entry, char **ptr, int *len, const char
 			return -1;
 		}
 		(*ptr)++;
-		(*len)++;
+		len++;
 	}
 
-	if (*len) {
-		*entry = strndup(tmp_buf, *len);
-		if (!*entry)
+	if (len) {
+		entry->str = strndup(tmp_buf, len);
+		if (!entry->str)
 			return -1;
+
+		entry->len = len;
 	}
 
 	return 0;
@@ -56,7 +59,7 @@ static inline int read_spec_entry(char **entry, char **ptr, int *len, const char
  * line_buf - Buffer containing the spec entries .
  * errbuf   - Double pointer used for passing back specific error messages.
  * num_args - The number of spec parameter entries to process.
- * ...      - A 'char **spec_entry' for each parameter.
+ * ...      - A 'struct len_str **spec_entry' for each parameter.
  * returns  - The number of items processed. On error, it returns -1 with errno
  *            set and may set errbuf to a specific error message.
  *
@@ -65,8 +68,9 @@ static inline int read_spec_entry(char **entry, char **ptr, int *len, const char
  */
 int hidden read_spec_entries(char *line_buf, const char **errbuf, int num_args, ...)
 {
-	char **spec_entry, *buf_p;
-	int len, rc, items, entry_len = 0;
+	struct len_str *spec_entry;
+	char *buf_p;
+	int len, rc, items;
 	va_list ap;
 
 	*errbuf = NULL;
@@ -93,20 +97,22 @@ int hidden read_spec_entries(char *line_buf, const char **errbuf, int num_args,
 
 	items = 0;
 	while (items < num_args) {
-		spec_entry = va_arg(ap, char **);
+		spec_entry = va_arg(ap, struct len_str *);
 
 		if (len - 1 == buf_p - line_buf) {
 			va_end(ap);
 			return items;
 		}
 
-		rc = read_spec_entry(spec_entry, &buf_p, &entry_len, errbuf);
+		rc = read_spec_entry(spec_entry, &buf_p, errbuf);
 		if (rc < 0) {
 			va_end(ap);
 			return rc;
 		}
-		if (entry_len)
+
+		if (spec_entry->len) {
 			items++;
+		}
 	}
 	va_end(ap);
 	return items;
libselinux/src/label_x.c +3 -2
index 700def1..cdbac8c 100644
@@ -81,7 +81,8 @@ static int process_line(const char *path, char *line_buf, int pass,
 			return 0;
 		}
 		data->spec_arr[data->nspec].key = key;
-		data->spec_arr[data->nspec].lr.ctx_raw = context;
+		data->spec_arr[data->nspec].lr.ctx_raw.str = context;
+		data->spec_arr[data->nspec].lr.ctx_raw.len = strlen(context);
 		free(type);
 	}
 
@@ -186,7 +187,7 @@ static void close(struct selabel_handle *rec)
 	for (i = 0; i < data->nspec; i++) {
 		spec = &spec_arr[i];
 		free(spec->key);
-		free(spec->lr.ctx_raw);
+		free(spec->lr.ctx_raw.str);
 		free(spec->lr.ctx_trans);
 	}
 
libselinux/src/matchpathcon.c +1 -1
index 4764ab7..96c39b4 100644
@@ -541,7 +541,7 @@ int compat_validate(struct selabel_handle *rec,
 		    const char *path, unsigned lineno)
 {
 	int rc;
-	char **ctx = &contexts->ctx_raw;
+	char **ctx = &contexts->ctx_raw.str;
 
 	if (myinvalidcon)
 		rc = myinvalidcon(path, lineno, *ctx);
Signature · 1 line
1.9.1