apparmor: add support for 2^24 states to the dfa state machine.

Currently the dfa state machine is limited by its default, next, and
check tables using u16. Allow loading of u32 tables, and if u16 tables
are loaded map them to u32.

The number of states allowed does not increase to 2^32 because the
base table uses the top 8 bits of its u32 for flags. Moving the flags
into a separate table allowing a full 2^32 bit range wil be done in
a separate patch.

Link: https://gitlab.com/apparmor/apparmor/-/issues/419
Signed-off-by: John Johansen <john.johansen@canonical.com>

3 files changed, 83 insertions, 25 deletions

diff --git a/security/apparmor/apparmorfs.c b/security/apparmor/apparmorfs.c
index 01b923d97a44..2c0185ebc900 100644
--- a/security/apparmor/apparmorfs.c
+++ b/security/apparmor/apparmorfs.c
@@ -2366,6 +2366,7 @@ static struct aa_sfs_entry aa_sfs_entry_policy[] = {
 	AA_SFS_FILE_U64("outofband",		MAX_OOB_SUPPORTED),
 	AA_SFS_FILE_U64("permstable32_version",	1),
 	AA_SFS_FILE_STRING("permstable32", PERMS32STR),
+	AA_SFS_FILE_U64("state32",	1),
 	AA_SFS_DIR("unconfined_restrictions",   aa_sfs_entry_unconfined),
 	{ }
 };
diff --git a/security/apparmor/include/match.h b/security/apparmor/include/match.h
index 4bb0405c9190..536ce3abd598 100644
--- a/security/apparmor/include/match.h
+++ b/security/apparmor/include/match.h
@@ -87,10 +87,12 @@ struct table_header {
 	char td_data[];
 };
 
-#define DEFAULT_TABLE(DFA) ((u16 *)((DFA)->tables[YYTD_ID_DEF]->td_data))
+#define TABLE_DATAU16(TABLE) ((u16 *)((TABLE)->td_data))
+#define TABLE_DATAU32(TABLE) ((u32 *)((TABLE)->td_data))
+#define DEFAULT_TABLE(DFA) ((u32 *)((DFA)->tables[YYTD_ID_DEF]->td_data))
 #define BASE_TABLE(DFA) ((u32 *)((DFA)->tables[YYTD_ID_BASE]->td_data))
-#define NEXT_TABLE(DFA) ((u16 *)((DFA)->tables[YYTD_ID_NXT]->td_data))
-#define CHECK_TABLE(DFA) ((u16 *)((DFA)->tables[YYTD_ID_CHK]->td_data))
+#define NEXT_TABLE(DFA) ((u32 *)((DFA)->tables[YYTD_ID_NXT]->td_data))
+#define CHECK_TABLE(DFA) ((u32 *)((DFA)->tables[YYTD_ID_CHK]->td_data))
 #define EQUIV_TABLE(DFA) ((u8 *)((DFA)->tables[YYTD_ID_EC]->td_data))
 #define ACCEPT_TABLE(DFA) ((u32 *)((DFA)->tables[YYTD_ID_ACCEPT]->td_data))
 #define ACCEPT_TABLE2(DFA) ((u32 *)((DFA)->tables[YYTD_ID_ACCEPT2]->td_data))
diff --git a/security/apparmor/match.c b/security/apparmor/match.c
index 517d77d3c34c..f2d9c57f8794 100644
--- a/security/apparmor/match.c
+++ b/security/apparmor/match.c
@@ -247,6 +247,42 @@ void aa_dfa_free_kref(struct kref *kref)
 	dfa_free(dfa);
 }
 
+
+
+/**
+ * remap_data16_to_data32 - remap u16 @old table to a u32 based table
+ * @old: table to remap
+ *
+ * Returns: new table with u32 entries instead of u16.
+ *
+ * Note: will free @old so caller does not have to
+ */
+static struct table_header *remap_data16_to_data32(struct table_header *old)
+{
+	struct table_header *new;
+	size_t tsize;
+	u32 i;
+
+	tsize = table_size(old->td_lolen, YYTD_DATA32);
+	new = kvzalloc(tsize, GFP_KERNEL);
+	if (!new) {
+		kvfree(old);
+		return NULL;
+	}
+	new->td_id = old->td_id;
+	new->td_flags = YYTD_DATA32;
+	new->td_lolen = old->td_lolen;
+
+	for (i = 0; i < old->td_lolen; i++)
+		TABLE_DATAU32(new)[i] = (u32) TABLE_DATAU16(old)[i];
+
+	kvfree(old);
+	if (is_vmalloc_addr(new))
+		vm_unmap_aliases();
+
+	return new;
+}
+
 /**
  * aa_dfa_unpack - unpack the binary tables of a serialized dfa
  * @blob: aligned serialized stream of data to unpack  (NOT NULL)
@@ -326,8 +362,10 @@ struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
 		case YYTD_ID_DEF:
 		case YYTD_ID_NXT:
 		case YYTD_ID_CHK:
-			if (table->td_flags != YYTD_DATA16)
+			if (!(table->td_flags == YYTD_DATA16 ||
+			      table->td_flags == YYTD_DATA32)) {
 				goto fail;
+			}
 			break;
 		case YYTD_ID_EC:
 			if (table->td_flags != YYTD_DATA8)
@@ -342,6 +380,23 @@ struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
 		dfa->tables[table->td_id] = table;
 		data += table_size(table->td_lolen, table->td_flags);
 		size -= table_size(table->td_lolen, table->td_flags);
+
+		/*
+		 * this remapping has to be done after incrementing data above
+		 * for now straight remap, later have dfa support both
+		 */
+		switch (table->td_id) {
+		case YYTD_ID_DEF:
+		case YYTD_ID_NXT:
+		case YYTD_ID_CHK:
+			if (table->td_flags == YYTD_DATA16) {
+				table = remap_data16_to_data32(table);
+				if (!table)
+					goto fail;
+			}
+			dfa->tables[table->td_id] = table;
+			break;
+		}
 		table = NULL;
 	}
 	error = verify_table_headers(dfa->tables, flags);
@@ -395,10 +450,10 @@ do {							\
 aa_state_t aa_dfa_match_len(struct aa_dfa *dfa, aa_state_t start,
 			    const char *str, int len)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 	aa_state_t state = start;
 
 	if (state == DFA_NOMATCH)
@@ -434,10 +489,10 @@ aa_state_t aa_dfa_match_len(struct aa_dfa *dfa, aa_state_t start,
  */
 aa_state_t aa_dfa_match(struct aa_dfa *dfa, aa_state_t start, const char *str)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 	aa_state_t state = start;
 
 	if (state == DFA_NOMATCH)
@@ -472,10 +527,10 @@ aa_state_t aa_dfa_match(struct aa_dfa *dfa, aa_state_t start, const char *str)
  */
 aa_state_t aa_dfa_next(struct aa_dfa *dfa, aa_state_t state, const char c)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 
 	/* current state is <state>, matching character *str */
 	if (dfa->tables[YYTD_ID_EC]) {
@@ -490,10 +545,10 @@ aa_state_t aa_dfa_next(struct aa_dfa *dfa, aa_state_t state, const char c)
 
 aa_state_t aa_dfa_outofband_transition(struct aa_dfa *dfa, aa_state_t state)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 	u32 b = (base)[(state)];
 
 	if (!(b & MATCH_FLAG_OOB_TRANSITION))
@@ -521,10 +576,10 @@ aa_state_t aa_dfa_outofband_transition(struct aa_dfa *dfa, aa_state_t state)
 aa_state_t aa_dfa_match_until(struct aa_dfa *dfa, aa_state_t start,
 				const char *str, const char **retpos)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 	u32 *accept = ACCEPT_TABLE(dfa);
 	aa_state_t state = start, pos;
 
@@ -582,10 +637,10 @@ aa_state_t aa_dfa_match_until(struct aa_dfa *dfa, aa_state_t start,
 aa_state_t aa_dfa_matchn_until(struct aa_dfa *dfa, aa_state_t start,
 				 const char *str, int n, const char **retpos)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 	u32 *accept = ACCEPT_TABLE(dfa);
 	aa_state_t state = start, pos;
 
@@ -658,10 +713,10 @@ static aa_state_t leftmatch_fb(struct aa_dfa *dfa, aa_state_t start,
 				 const char *str, struct match_workbuf *wb,
 				 unsigned int *count)
 {
-	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *def = DEFAULT_TABLE(dfa);
 	u32 *base = BASE_TABLE(dfa);
-	u16 *next = NEXT_TABLE(dfa);
-	u16 *check = CHECK_TABLE(dfa);
+	u32 *next = NEXT_TABLE(dfa);
+	u32 *check = CHECK_TABLE(dfa);
 	aa_state_t state = start, pos;
 
 	AA_BUG(!dfa);