Optimize restorecon_recursive tree walk.idea133-weekly-release

restorecon_recursive can prune the tree walk whenever it
encounters a directory for which there is no possible match
for any of its descendants in the file_contexts configuration.
This will only presently benefit the restorecon_recursive("/sys") call
by init since other restorecon_recursive calls always have
top-level entries that will match anything underneath and this
is required to fully label those partitions on upgrade. However,
those other cases are already optimized to only run once per
file_contexts change (upgrade) and thus do not need this optimization.

Change-Id: I854bf1ccff6ded56e9da2c4184435f67d7069bc1
Signed-off-by: Stephen Smalley <sds@tycho.nsa.gov>

5 files changed, 65 insertions, 3 deletions

diff --git a/include/selinux/label.h b/include/selinux/label.h
index 628c5d5..facfa57 100644
--- a/include/selinux/label.h
+++ b/include/selinux/label.h
@@ -6,6 +6,7 @@
 #ifndef _SELABEL_H_
 #define _SELABEL_H_
 
+#include <stdbool.h>
 #include <sys/types.h>
 #include <selinux/selinux.h>
 
@@ -98,6 +99,8 @@ int selabel_lookup(struct selabel_handle *handle, char **con,
 int selabel_lookup_raw(struct selabel_handle *handle, char **con,
 		       const char *key, int type);
 
+bool selabel_partial_match(struct selabel_handle *handle, const char *key);
+
 /**
  * selabel_stats - log labeling operation statistics.
  * @handle: specifies backend instance to query
diff --git a/src/android.c b/src/android.c
index 947554d..a15c9ab 100644
--- a/src/android.c
+++ b/src/android.c
@@ -25,6 +25,7 @@
 #include "policy.h"
 #include "callbacks.h"
 #include "selinux_internal.h"
+#include "label_internal.h"
 
 /*
  * XXX Where should this configuration file be located?
@@ -1098,6 +1099,7 @@ static int selinux_android_restorecon_common(const char* pathname,
     bool recurse = (flags & SELINUX_ANDROID_RESTORECON_RECURSE) ? true : false;
     bool force = (flags & SELINUX_ANDROID_RESTORECON_FORCE) ? true : false;
     bool datadata = (flags & SELINUX_ANDROID_RESTORECON_DATADATA) ? true : false;
+    bool issys = strcmp(pathname, "/sys") == 0 ? true : false;
     struct stat sb;
     FTS *fts;
     FTSENT *ftsent;
@@ -1176,6 +1178,10 @@ static int selinux_android_restorecon_common(const char* pathname,
                 fts_set(fts, ftsent, FTS_SKIP);
                 continue;
             }
+            if (issys && !selabel_partial_match(sehandle, ftsent->fts_path)) {
+                fts_set(fts, ftsent, FTS_SKIP);
+                continue;
+            }
             /* fall through */
         default:
             (void) restorecon_sb(ftsent->fts_path, ftsent->fts_statp, true, nochange, verbose, seinfo, uid);
diff --git a/src/label.c b/src/label.c
index d29b459..800a8a2 100644
--- a/src/label.c
+++ b/src/label.c
@@ -119,6 +119,18 @@ int selabel_lookup(struct selabel_handle *rec, char **con,
 	return *con ? 0 : -1;
 }
 
+bool selabel_partial_match(struct selabel_handle *rec, const char *key)
+{
+	if (!rec->func_partial_match) {
+		/*
+		 * If the label backend does not support partial matching,
+		 * then assume a match is possible.
+		 */
+		return true;
+	}
+	return rec->func_partial_match(rec, key);
+}
+
 void selabel_close(struct selabel_handle *rec)
 {
 	rec->func_close(rec);
diff --git a/src/label_file.c b/src/label_file.c
index 79239c4..9923e38 100644
--- a/src/label_file.c
+++ b/src/label_file.c
@@ -33,6 +33,7 @@ typedef struct spec {
 	int matches;		/* number of matching pathnames */
 	int hasMetaChars;	/* regular expression has meta-chars */
 	int stem_id;		/* indicates which stem-compression item */
+	size_t prefix_len;      /* length of fixed path prefix */
 } spec_t;
 
 /* A regular expression stem */
@@ -184,7 +185,7 @@ static int nodups_specs(struct saved_data *data, const char *path)
 static void spec_hasMetaChars(struct spec *spec)
 {
 	char *c;
-	int len;
+	size_t len;
 	char *end;
 
 	c = spec->regex_str;
@@ -192,6 +193,7 @@ static void spec_hasMetaChars(struct spec *spec)
 	end = c + len;
 
 	spec->hasMetaChars = 0;
+	spec->prefix_len = len;
 
 	/* Look at each character in the RE specification string for a 
 	 * meta character. Return when any meta character reached. */
@@ -208,6 +210,7 @@ static void spec_hasMetaChars(struct spec *spec)
 		case '(':
 		case '{':
 			spec->hasMetaChars = 1;
+			spec->prefix_len = c - spec->regex_str;
 			return;
 		case '\\':	/* skip the next character */
 			c++;
@@ -566,8 +569,9 @@ static void closef(struct selabel_handle *rec)
 	free(data);
 }
 
-static struct selabel_lookup_rec *lookup(struct selabel_handle *rec,
-					 const char *key, int type)
+static struct selabel_lookup_rec *lookup_common(struct selabel_handle *rec,
+						const char *key, int type,
+						bool partial)
 {
 	struct saved_data *data = (struct saved_data *)rec->data;
 	spec_t *spec_arr = data->spec_arr;
@@ -578,6 +582,7 @@ static struct selabel_lookup_rec *lookup(struct selabel_handle *rec,
 	char *clean_key = NULL;
 	const char *prev_slash, *next_slash;
 	unsigned int sofar = 0;
+	size_t keylen = strlen(key);
 
 	if (!data->nspec) {
 		errno = ENOENT;
@@ -628,6 +633,29 @@ static struct selabel_lookup_rec *lookup(struct selabel_handle *rec,
 				spec_arr[i].matches++;
 				break;
 			}
+
+			if (partial) {
+				/*
+				 * We already checked above to see if the
+				 * key has any direct match.  Now we just need
+				 * to check for partial matches.
+				 * Since POSIX regex functions do not support
+				 * partial match, we crudely approximate it
+				 * via a prefix match.
+				 * This is imprecise and could yield
+				 * false positives or negatives but
+				 * appears to work with our current set of
+				 * regex strings.
+				 * Convert to using pcre partial match
+				 * if/when pcre becomes available in Android.
+				 */
+				if (spec_arr[i].prefix_len > 1 &&
+				    !strncmp(key, spec_arr[i].regex_str,
+					     keylen < spec_arr[i].prefix_len ?
+					     keylen : spec_arr[i].prefix_len))
+					break;
+			}
+
 			if (rc == REG_NOMATCH)
 				continue;
 			/* else it's an error */
@@ -648,6 +676,17 @@ finish:
 	return ret;
 }
 
+static struct selabel_lookup_rec *lookup(struct selabel_handle *rec,
+					 const char *key, int type)
+{
+	return lookup_common(rec, key, type, false);
+}
+
+static bool partial_match(struct selabel_handle *rec, const char *key)
+{
+	return lookup_common(rec, key, 0, true) ? true : false;
+}
+
 static void stats(struct selabel_handle *rec)
 {
 	struct saved_data *data = (struct saved_data *)rec->data;
@@ -686,6 +725,7 @@ int selabel_file_init(struct selabel_handle *rec, const struct selinux_opt *opts
 	rec->func_close = &closef;
 	rec->func_stats = &stats;
 	rec->func_lookup = &lookup;
+	rec->func_partial_match = &partial_match;
 
 	return init(rec, opts, nopts);
 }
diff --git a/src/label_internal.h b/src/label_internal.h
index c8303a4..e44e3cc 100644
--- a/src/label_internal.h
+++ b/src/label_internal.h
@@ -54,6 +54,7 @@ struct selabel_handle {
 						   const char *key, int type);
 	void (*func_close) (struct selabel_handle *h);
 	void (*func_stats) (struct selabel_handle *h);
+	bool (*func_partial_match) (struct selabel_handle *h, const char *key);
 
 	/* supports backend-specific state information */
 	void *data;