[apparmor] [PATCH 15/18] apparmor: add support for default differential encoding.

[John Johansen]

Default differential encoding stores the current state's transitions as
the difference of the default state's transitions.  So for the current
match (state and pos) if the state is diffentially encoded, transition to
the default state without incrementing pos;

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 security/apparmor/apparmorfs.c    |    1 +
 security/apparmor/include/match.h |    2 +
 security/apparmor/match.c         |   80 +++++++++++++++----------------------
 3 files changed, 36 insertions(+), 47 deletions(-)

diff --git a/security/apparmor/apparmorfs.c b/security/apparmor/apparmorfs.c
index ad6c748..e0f8a84 100644
--- a/security/apparmor/apparmorfs.c
+++ b/security/apparmor/apparmorfs.c
@@ -199,6 +199,7 @@ static struct aa_fs_entry aa_fs_entry_domain[] = {
 };
 
 static struct aa_fs_entry aa_fs_entry_policy[] = {
+	AA_FS_FILE_BOOLEAN("diff_encode",	1),
 	{}
 };
 
diff --git a/security/apparmor/include/match.h b/security/apparmor/include/match.h
index 001c43a..2ea0f8c 100644
--- a/security/apparmor/include/match.h
+++ b/security/apparmor/include/match.h
@@ -116,6 +116,8 @@ static inline size_t table_size(size_t len, size_t el_size)
 	return ALIGN(sizeof(struct table_header) + len * el_size, 8);
 }
 
+#define MATCH_FLAG_DIFF_ENCODE 0x80000000
+
 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags);
 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
 			      const char *str, int len);
diff --git a/security/apparmor/match.c b/security/apparmor/match.c
index 727eb42..428b1ad 100644
--- a/security/apparmor/match.c
+++ b/security/apparmor/match.c
@@ -154,6 +154,8 @@ static int verify_dfa(struct aa_dfa *dfa, int flags)
 		}
 	}
 
+	/* TODO: verify diff encode terminates */
+
 	error = 0;
 out:
 	return error;
@@ -281,6 +283,22 @@ fail:
 	return ERR_PTR(error);
 }
 
+#define match_char(state, def, base, next, check, C) \
+do { \
+	for (;;) { \
+		unsigned int pos = base_idx((base)[(state)]) + (C); \
+		if ((check)[pos] == (state)) { \
+			(state) = (next)[pos]; \
+		} else { \
+			bool isdiff = (base)[(state)] & MATCH_FLAG_DIFF_ENCODE;\
+			(state) = (def)[(state)]; \
+			if (isdiff) \
+				continue; \
+		} \
+		break; \
+	} \
+} while (0)
+
 /**
  * aa_dfa_match_len - traverse @dfa to find state @str stops at
  * @dfa: the dfa to match @str against  (NOT NULL)
@@ -304,7 +322,7 @@ unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
 	u32 *base = BASE_TABLE(dfa);
 	u16 *next = NEXT_TABLE(dfa);
 	u16 *check = CHECK_TABLE(dfa);
-	unsigned int state = start, pos;
+	unsigned int state = start;
 
 	if (state == 0)
 		return 0;
@@ -313,23 +331,13 @@ unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
 	if (dfa->tables[YYTD_ID_EC]) {
 		/* Equivalence class table defined */
 		u8 *equiv = EQUIV_TABLE(dfa);
-		/* default is direct to next state */
-		for (; len; len--) {
-			pos = base_idx(base[state]) + equiv[(u8) *str++];
-			if (check[pos] == state)
-				state = next[pos];
-			else
-				state = def[state];
-		}
+		for (; len; len--)
+			match_char(state, def, base, next, check,
+				   equiv[(u8) *str++]);
 	} else {
 		/* default is direct to next state */
-		for (; len; len--) {
-			pos = base_idx(base[state]) + (u8) *str++;
-			if (check[pos] == state)
-				state = next[pos];
-			else
-				state = def[state];
-		}
+		for (; len; len--)
+			match_char(state, def, base, next, check, (u8) *str++);
 	}
 
 	return state;
@@ -354,7 +362,7 @@ unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
 	u32 *base = BASE_TABLE(dfa);
 	u16 *next = NEXT_TABLE(dfa);
 	u16 *check = CHECK_TABLE(dfa);
-	unsigned int state = start, pos;
+	unsigned int state = start;
 
 	if (state == 0)
 		return 0;
@@ -364,22 +372,13 @@ unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
 		/* Equivalence class table defined */
 		u8 *equiv = EQUIV_TABLE(dfa);
 		/* default is direct to next state */
-		while (*str) {
-			pos = base_idx(base[state]) + equiv[(u8) *str++];
-			if (check[pos] == state)
-				state = next[pos];
-			else
-				state = def[state];
-		}
+		while (*str)
+			match_char(state, def, base, next, check,
+				   equiv[(u8) *str++]);
 	} else {
 		/* default is direct to next state */
-		while (*str) {
-			pos = base_idx(base[state]) + (u8) *str++;
-			if (check[pos] == state)
-				state = next[pos];
-			else
-				state = def[state];
-		}
+		while (*str)
+			match_char(state, def, base, next, check, (u8) *str++);
 	}
 
 	return state;
@@ -402,27 +401,14 @@ unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
 	u32 *base = BASE_TABLE(dfa);
 	u16 *next = NEXT_TABLE(dfa);
 	u16 *check = CHECK_TABLE(dfa);
-	unsigned int pos;
 
 	/* current state is <state>, matching character *str */
 	if (dfa->tables[YYTD_ID_EC]) {
 		/* Equivalence class table defined */
 		u8 *equiv = EQUIV_TABLE(dfa);
-		/* default is direct to next state */
-
-		pos = base_idx(base[state]) + equiv[(u8) c];
-		if (check[pos] == state)
-			state = next[pos];
-		else
-			state = def[state];
-	} else {
-		/* default is direct to next state */
-		pos = base_idx(base[state]) + (u8) c;
-		if (check[pos] == state)
-			state = next[pos];
-		else
-			state = def[state];
-	}
+		match_char(state, def, base, next, check, equiv[(u8) c]);
+	} else
+		match_char(state, def, base, next, check, (u8) c);
 
 	return state;
 }
-- 
1.7.10.4