@@ -97,99 +96,50 @@ static u32 map_old_perms(u32 old)
return new;
}
-static void compute_fperms_allow(struct aa_perms *perms, const struct aa_dfa *dfa,
- aa_state_t state)
+static void compute_fperms_allow(struct aa_perms *perms, u32 accept1)
{
perms->allow |= AA_MAY_GETATTR;
/* change_profile wasn't determined by ownership in old mapping */
- if (ACCEPT_TABLE(dfa)[state] & 0x80000000)
+ if (accept1 & 0x80000000)
perms->allow |= AA_MAY_CHANGE_PROFILE;
- if (ACCEPT_TABLE(dfa)[state] & 0x40000000)
+ if (accept1 & 0x40000000)
perms->allow |= AA_MAY_ONEXEC;
}
-static struct aa_perms compute_fperms_user(const struct aa_dfa *dfa,
- aa_state_t state)
+static struct aa_perms compute_fperms_user(u32 accept1, u32 accept2)
{
struct aa_perms perms = { };
- perms.allow = map_old_perms(dfa_user_allow(dfa, state));
- perms.audit = map_old_perms(dfa_user_audit(dfa, state));
- perms.quiet = map_old_perms(dfa_user_quiet(dfa, state));
- perms.xindex = dfa_user_xindex(dfa, state);
+ perms.allow = map_old_perms(dfa_user_allow(accept1));
+ perms.audit = map_old_perms(dfa_user_audit(accept2));
+ perms.quiet = map_old_perms(dfa_user_quiet(accept2));
+ perms.xindex = dfa_user_xindex(accept1);
- compute_fperms_allow(&perms, dfa, state);
+ compute_fperms_allow(&perms, accept1);
return perms;
}
-static struct aa_perms compute_fperms_other(const struct aa_dfa *dfa,
- aa_state_t state)
+static struct aa_perms compute_fperms_other(u32 accept1, u32 accept2)
{
struct aa_perms perms = { };
- perms.allow = map_old_perms(dfa_other_allow(dfa, state));
- perms.audit = map_old_perms(dfa_other_audit(dfa, state));
- perms.quiet = map_old_perms(dfa_other_quiet(dfa, state));
- perms.xindex = dfa_other_xindex(dfa, state);
+ perms.allow = map_old_perms(dfa_other_allow(accept1));
+ perms.audit = map_old_perms(dfa_other_audit(accept2));
+ perms.quiet = map_old_perms(dfa_other_quiet(accept2));
+ perms.xindex = dfa_other_xindex(accept1);
- compute_fperms_allow(&perms, dfa, state);
+ compute_fperms_allow(&perms, accept1);
return perms;
}
-/**
- * compute_fperms - convert dfa compressed perms to internal perms and store
- * them so they can be retrieved later.
- * @dfa: a dfa using fperms to remap to internal permissions
- * @size: Returns the permission table size
- *
- * Returns: remapped perm table
- */
-static struct aa_perms *compute_fperms(const struct aa_dfa *dfa,
- u32 *size)
-{
- aa_state_t state;
- unsigned int state_count;
- struct aa_perms *table;
-
- AA_BUG(!dfa);
-
- state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
- /* DFAs are restricted from having a state_count of less than 2 */
- table = kvzalloc_objs(struct aa_perms, state_count * 2);
- if (!table)
- return NULL;
- *size = state_count * 2;
-
- for (state = 0; state < state_count; state++) {
- table[state * 2] = compute_fperms_user(dfa, state);
- table[state * 2 + 1] = compute_fperms_other(dfa, state);
- }
-
- return table;
-}
-
-static struct aa_perms *compute_xmatch_perms(const struct aa_dfa *xmatch,
- u32 *size)
+static struct aa_perms compute_xmatch_entry(u32 accept1)
{
- struct aa_perms *perms;
- int state;
- int state_count;
-
- AA_BUG(!xmatch);
-
- state_count = xmatch->tables[YYTD_ID_BASE]->td_lolen;
- /* DFAs are restricted from having a state_count of less than 2 */
- perms = kvzalloc_objs(struct aa_perms, state_count);
- if (!perms)
- return NULL;
- *size = state_count;
+ struct aa_perms perms = { };
- /* zero init so skip the trap state (state == 0) */
- for (state = 1; state < state_count; state++)
- perms[state].allow = dfa_user_allow(xmatch, state);
+ perms.allow = dfa_user_allow(accept1);
return perms;
}@@ -228,106 +177,294 @@ static struct aa_perms compute_perms_entry(const struct aa_dfa *dfa,
* Unfortunately there is no way to force auditing on the
* perms represented by the xbits
*/
- perms.allow |= map_other(dfa_other_allow(dfa, state));
+ perms.allow |= map_other(dfa_other_allow(accept1));
if (VERSION_LE(version, v8))
perms.allow |= AA_MAY_LOCK;
else
- perms.allow |= map_xbits(dfa_user_xbits(dfa, state));
+ perms.allow |= map_xbits(dfa_user_xbits(accept1));
/*
* for v5-v9 perm mapping in the policydb, the other set is used
* to extend the general perm set
*/
- perms.audit |= map_other(dfa_other_audit(dfa, state));
- perms.quiet |= map_other(dfa_other_quiet(dfa, state));
+ perms.audit |= map_other(dfa_other_audit(accept2));
+ perms.quiet |= map_other(dfa_other_quiet(accept2));
if (VERSION_GT(version, v8))
- perms.quiet |= map_xbits(dfa_other_xbits(dfa, state));
+ perms.quiet |= map_xbits(dfa_other_xbits(accept1));
return perms;
}
-static struct aa_perms *compute_perms(const struct aa_dfa *dfa, u32 version,
- u32 *size)
+/*
+ * intern perm entries as they are computed so states sharing a permission
+ * set share a single perms table entry, instead of one entry per state
+ */
+#define INTERN_INVALID U32_MAX
+#define INTERN_HASH_BITS_MIN 6
+#define INTERN_HASH_BITS_MAX 26 /* keeps the table under INT_MAX bytes */
+#define INTERN_PERMS_MIN 8
+
+/* open addressed, slot is stored + 1 so 0 marks a free bucket */
+struct perms_intern_ent {
+ u64 key; /* accept words the entry was computed from */
+ u32 slot;
+ bool pair; /* entry is followed by an 'other' entry */
+};
+
+struct perms_intern {
+ struct aa_perms *perms;
+ u32 nperms;
+ u32 pcap;
+ struct perms_intern_ent *tab;
+ u32 nent;
+ unsigned int hash_bits;
+};
+
+static bool init_intern(struct perms_intern *it)
{
- unsigned int state;
- unsigned int state_count;
- struct aa_perms *table;
+ memset(it, 0, sizeof(*it));
+ it->hash_bits = INTERN_HASH_BITS_MIN;
+ it->pcap = INTERN_PERMS_MIN;
+ it->tab = kvzalloc_objs(struct perms_intern_ent, 1UL << it->hash_bits);
+ it->perms = kvzalloc_objs(struct aa_perms, it->pcap);
- AA_BUG(!dfa);
+ return it->tab && it->perms;
+}
- state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
- /* DFAs are restricted from having a state_count of less than 2 */
- table = kvzalloc_objs(struct aa_perms, state_count);
- if (!table)
- return NULL;
- *size = state_count;
+static void free_intern(struct perms_intern *it)
+{
+ kvfree(it->tab);
+ kvfree(it->perms);
+}
- /* zero init so skip the trap state (state == 0) */
- for (state = 1; state < state_count; state++) {
- table[state] = compute_perms_entry(dfa, state, version);
- AA_DEBUG(DEBUG_UNPACK,
- "[%d]: (0x%x/0x%x/0x%x//0x%x/0x%x//0x%x), converted from accept1: 0x%x, accept2: 0x%x",
- state, table[state].allow, table[state].deny,
- table[state].prompt, table[state].audit,
- table[state].quiet, table[state].xindex,
- ACCEPT_TABLE(dfa)[state], ACCEPT_TABLE2(dfa)[state]);
- }
- return table;
+/* returns the bucket holding @key, or the free bucket for it */
+static u32 probe_intern(const struct perms_intern *it, u64 key)
+{
+ u32 mask = (1UL << it->hash_bits) - 1;
+ u32 i = hash_64(key, it->hash_bits);
+
+ while (it->tab[i].slot && it->tab[i].key != key)
+ i = (i + 1) & mask;
+
+ return i;
}
-/**
- * remap_dfa_accept - remap old dfa accept table to be an index
- * @dfa: dfa to do the remapping on
- * @factor: scaling factor for the index conversion.
- *
- * Used in conjunction with compute_Xperms, it converts old style perms
- * that are encoded in the dfa accept tables to the new style where
- * there is a permission table and the accept table is an index into
- * the permission table.
- */
-static void remap_dfa_accept(struct aa_dfa *dfa, unsigned int factor)
+static bool grow_intern(struct perms_intern *it)
{
- unsigned int state;
- unsigned int state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
+ struct perms_intern_ent *old = it->tab, *tab;
+ u32 n = 1UL << it->hash_bits;
+ u32 i;
+
+ if (it->hash_bits >= INTERN_HASH_BITS_MAX)
+ return false;
+ tab = kvzalloc_objs(struct perms_intern_ent, n * 2);
+ if (!tab)
+ return false;
+ it->tab = tab;
+ it->hash_bits++;
+ for (i = 0; i < n; i++) {
+ if (old[i].slot)
+ it->tab[probe_intern(it, old[i].key)] = old[i];
+ }
+ kvfree(old);
- AA_BUG(!dfa);
+ return true;
+}
- for (state = 0; state < state_count; state++) {
- ACCEPT_TABLE(dfa)[state] = state * factor;
- ACCEPT_TABLE2(dfa)[state] = factor > 1 ? ACCEPT_FLAG_OWNER : 0;
+/* reserve @n adjacent entries, aa_lookup_condperms() expects other at +1 */
+static u32 alloc_perms(struct perms_intern *it, u32 n)
+{
+ u32 slot = it->nperms;
+
+ if (it->nperms + n > it->pcap) {
+ struct aa_perms *perms;
+
+ if (it->pcap > U32_MAX / 2)
+ return INTERN_INVALID;
+ perms = kvrealloc(it->perms,
+ size_mul(it->pcap * 2, sizeof(*perms)),
+ GFP_KERNEL);
+ if (!perms)
+ return INTERN_INVALID;
+ it->perms = perms;
+ it->pcap *= 2;
}
+ it->nperms += n;
+
+ return slot;
+}
+
+/* record that @key maps to @slot */
+static bool bind_intern(struct perms_intern *it, u64 key, u32 slot, bool pair)
+{
+ u32 i;
+
+ /* keep below 3/4 load so probing terminates */
+ if ((it->nent + 1) * 4 > (1UL << it->hash_bits) * 3 &&
+ !grow_intern(it))
+ return false;
+ i = probe_intern(it, key);
+ it->tab[i].key = key;
+ it->tab[i].slot = slot + 1;
+ it->tab[i].pair = pair;
+ it->nent++;
+
+ return true;
+}
+
+static void publish_perms(struct perms_intern *it, struct aa_policydb *policy)
+{
+ policy->perms = it->perms;
+ policy->size = it->nperms;
+ it->perms = NULL;
}
/* TODO: merge different dfa mappings into single map_policy fn */
int aa_compat_map_xmatch(struct aa_policydb *policy)
{
- policy->perms = compute_xmatch_perms(policy->dfa, &policy->size);
- if (!policy->perms)
- return -ENOMEM;
+ struct aa_dfa *dfa = policy->dfa;
+ struct perms_intern it;
+ unsigned int state, state_count;
+ int error = -ENOMEM;
- remap_dfa_accept(policy->dfa, 1);
+ AA_BUG(!dfa);
- return 0;
+ state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
+ if (!init_intern(&it))
+ goto out;
+
+ /* trap state keeps the zero perms it had, slot 0 is zero from alloc */
+ it.nperms = 1;
+ ACCEPT_TABLE(dfa)[0] = 0;
+ ACCEPT_TABLE2(dfa)[0] = 0;
+
+ for (state = 1; state < state_count; state++) {
+ u32 accept1 = ACCEPT_TABLE(dfa)[state];
+ u64 key = (u64)accept1 << 32;
+ u32 i = probe_intern(&it, key);
+ u32 slot;
+
+ if (it.tab[i].slot) {
+ slot = it.tab[i].slot - 1;
+ } else {
+ struct aa_perms perms = compute_xmatch_entry(accept1);
+
+ slot = alloc_perms(&it, 1);
+ if (slot == INTERN_INVALID)
+ goto out;
+ it.perms[slot] = perms;
+ if (!bind_intern(&it, key, slot, false))
+ goto out;
+ }
+ ACCEPT_TABLE(dfa)[state] = slot;
+ ACCEPT_TABLE2(dfa)[state] = 0;
+ }
+ publish_perms(&it, policy);
+ error = 0;
+out:
+ free_intern(&it);
+ return error;
}
int aa_compat_map_policy(struct aa_policydb *policy, u32 version)
{
- policy->perms = compute_perms(policy->dfa, version, &policy->size);
- if (!policy->perms)
- return -ENOMEM;
+ struct aa_dfa *dfa = policy->dfa;
+ struct perms_intern it;
+ unsigned int state, state_count;
+ int error = -ENOMEM;
+
+ AA_BUG(!dfa);
+
+ state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
+ if (!init_intern(&it))
+ goto out;
- remap_dfa_accept(policy->dfa, 1);
+ /* trap state keeps the zero perms it had, slot 0 is zero from alloc */
+ it.nperms = 1;
+ ACCEPT_TABLE(dfa)[0] = 0;
+ ACCEPT_TABLE2(dfa)[0] = 0;
- return 0;
+ for (state = 1; state < state_count; state++) {
+ u32 accept1 = ACCEPT_TABLE(dfa)[state];
+ u32 accept2 = ACCEPT_TABLE2(dfa)[state];
+ u64 key = ((u64)accept1 << 32) | accept2;
+ u32 i = probe_intern(&it, key);
+ u32 slot;
+
+ if (it.tab[i].slot) {
+ slot = it.tab[i].slot - 1;
+ } else {
+ struct aa_perms perms;
+
+ perms = compute_perms_entry(accept1, accept2, version);
+ slot = alloc_perms(&it, 1);
+ if (slot == INTERN_INVALID)
+ goto out;
+ it.perms[slot] = perms;
+ if (!bind_intern(&it, key, slot, false))
+ goto out;
+ AA_DEBUG(DEBUG_UNPACK,
+ "perms[%d]: (0x%x/0x%x/0x%x//0x%x/0x%x//0x%x), converted from accept1: 0x%x, accept2: 0x%x, first seen at state %d",
+ slot, perms.allow, perms.deny, perms.prompt,
+ perms.audit, perms.quiet, perms.xindex,
+ accept1, accept2, state);
+ }
+ ACCEPT_TABLE(dfa)[state] = slot;
+ ACCEPT_TABLE2(dfa)[state] = 0;
+ }
+ publish_perms(&it, policy);
+ error = 0;
+out:
+ free_intern(&it);
+ return error;
}
int aa_compat_map_file(struct aa_policydb *policy)
{
- policy->perms = compute_fperms(policy->dfa, &policy->size);
- if (!policy->perms)
- return -ENOMEM;
+ struct aa_dfa *dfa = policy->dfa;
+ struct perms_intern it;
+ unsigned int state, state_count;
+ int error = -ENOMEM;
- remap_dfa_accept(policy->dfa, 2);
+ AA_BUG(!dfa);
- return 0;
+ state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
+ if (!init_intern(&it))
+ goto out;
+
+ for (state = 0; state < state_count; state++) {
+ u32 accept1 = ACCEPT_TABLE(dfa)[state];
+ u32 accept2 = ACCEPT_TABLE2(dfa)[state];
+ u64 key = ((u64)accept1 << 32) | accept2;
+ u32 i = probe_intern(&it, key);
+ u32 slot;
+ bool pair;
+
+ if (it.tab[i].slot) {
+ slot = it.tab[i].slot - 1;
+ pair = it.tab[i].pair;
+ } else {
+ struct aa_perms user, other;
+
+ user = compute_fperms_user(accept1, accept2);
+ other = compute_fperms_other(accept1, accept2);
+ /* single entry when owner and other agree */
+ pair = memcmp(&user, &other, sizeof(user)) != 0;
+ slot = alloc_perms(&it, pair ? 2 : 1);
+ if (slot == INTERN_INVALID)
+ goto out;
+ it.perms[slot] = user;
+ if (pair)
+ it.perms[slot + 1] = other;
+ if (!bind_intern(&it, key, slot, pair))
+ goto out;
+ }
+ ACCEPT_TABLE(dfa)[state] = slot;
+ ACCEPT_TABLE2(dfa)[state] = pair ? ACCEPT_FLAG_OWNER : 0;
+ }
+ publish_perms(&it, policy);
+ error = 0;
+out:
+ free_intern(&it);
+ return error;
}