[apparmor] [PATCH 03/11] Split dfa minimize hashing to improve control
John Johansen
john.johansen at canonical.com
Tue Oct 19 01:20:35 BST 2010
Split dfa minimizing hashing into two seperately controllable hashes. The
first hash does hashing on state just state transitions, which always results
in a performance improvement.
The second does hashing based off of accept permissions, which can create
more initial states but can result in not being able to achieve a true
minimum dfa. This can also lead to slowing down total dfa creation because
while minimization, compression can take longer if the dfa isn't completely
minimized.
permission hashing is currently required, as minimization does not accumulate
redundant Node permissions.
---
parser/libapparmor_re/apparmor_re.h | 39 ++++++++++++++++++-----------------
parser/libapparmor_re/regexp.y | 35 +++++++++++++++++++++---------
parser/parser_main.c | 17 +++++++++-----
3 files changed, 55 insertions(+), 36 deletions(-)
diff --git a/parser/libapparmor_re/apparmor_re.h b/parser/libapparmor_re/apparmor_re.h
index acf0e78..5af9a58 100644
--- a/parser/libapparmor_re/apparmor_re.h
+++ b/parser/libapparmor_re/apparmor_re.h
@@ -17,25 +17,26 @@ typedef enum dfaflags {
DFA_CONTROL_NO_TREE_SIMPLE = 1 << 2,
DFA_CONTROL_TREE_LEFT = 1 << 3,
DFA_CONTROL_NO_MINIMIZE = 1 << 4,
- DFA_CONTROL_NO_HASH_PART = 1 << 5,
- DFA_CONTROL_NO_UNREACHABLE = 1 << 6,
- DFA_CONTROL_TRANS_HIGH = 1 << 7,
-
- DFA_DUMP_TREE_STATS = 1 << 8,
- DFA_DUMP_TREE = 1 << 9,
- DFA_DUMP_SIMPLE_TREE = 1 << 10,
- DFA_DUMP_PROGRESS = 1 << 11,
- DFA_DUMP_STATS = 1 << 12,
- DFA_DUMP_STATES = 1 << 13,
- DFA_DUMP_GRAPH = 1 << 14,
- DFA_DUMP_TRANS_PROGRESS = 1 << 15,
- DFA_DUMP_TRANS_STATS = 1 << 16,
- DFA_DUMP_TRANS_TABLE = 1 << 17,
- DFA_DUMP_EQUIV = 1 << 18,
- DFA_DUMP_EQUIV_STATS = 1 << 19,
- DFA_DUMP_MINIMIZE = 1 << 20,
- DFA_DUMP_UNREACHABLE = 1 << 22,
- DFA_DUMP_RULE_EXPR = 1 << 23,
+ DFA_CONTROL_MINIMIZE_HASH_TRANS = 1 << 5,
+ DFA_CONTROL_MINIMIZE_HASH_PERMS = 1 << 6,
+ DFA_CONTROL_NO_UNREACHABLE = 1 << 7,
+ DFA_CONTROL_TRANS_HIGH = 1 << 8,
+
+ DFA_DUMP_TREE_STATS = 1 << 16,
+ DFA_DUMP_TREE = 1 << 17,
+ DFA_DUMP_SIMPLE_TREE = 1 << 18,
+ DFA_DUMP_PROGRESS = 1 << 19,
+ DFA_DUMP_STATS = 1 << 20,
+ DFA_DUMP_STATES = 1 << 21,
+ DFA_DUMP_GRAPH = 1 << 22,
+ DFA_DUMP_TRANS_PROGRESS = 1 << 23,
+ DFA_DUMP_TRANS_STATS = 1 << 24,
+ DFA_DUMP_TRANS_TABLE = 1 << 25,
+ DFA_DUMP_EQUIV = 1 << 26,
+ DFA_DUMP_EQUIV_STATS = 1 << 27,
+ DFA_DUMP_MINIMIZE = 1 << 28,
+ DFA_DUMP_UNREACHABLE = 1 << 29,
+ DFA_DUMP_RULE_EXPR = 1 << 30,
} dfaflags_t;
#ifdef __cplusplus
diff --git a/parser/libapparmor_re/regexp.y b/parser/libapparmor_re/regexp.y
index d5412f6..45946af 100644
--- a/parser/libapparmor_re/regexp.y
+++ b/parser/libapparmor_re/regexp.y
@@ -1701,19 +1701,32 @@ void DFA::minimize(dfaflags_t flags)
list <Partition *> partitions;
map <State *, Partition *> partition_map;
- /* Set up the initial partitions - 1 non accepting, and a
- * partion for each unique combination of permissions
+ /* Set up the initial partitions
+ * minimium of - 1 non accepting, and 1 accepting
+ * if trans hashing is used the accepting and non-accepting partitions
+ * can be further split based on the number and type of transitions
+ * a state makes.
+ * If permission hashing is enabled the accepting partitions can
+ * be further divided by permissions. This can result in not
+ * obtaining a truely minimized dfa but comes close, and can speedup
+ * minimization.
*/
int accept_count = 0;
for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- uint32_t accept1, accept2;
- accept1 = (*i)->accept;
- accept2 = (*i)->accept;
- uint64_t combined = ((uint64_t)accept2)<<32 | (uint64_t)accept1;
- size_t size = 0;
- if (!(flags & DFA_CONTROL_NO_HASH_PART))
- size = hash_trans(*i);
- pair <uint64_t, size_t> group = make_pair(combined, size);
+ uint64_t perm_hash = 0;
+ if (flags & DFA_CONTROL_MINIMIZE_HASH_PERMS) {
+ /* make every unique perm create a new partition */
+ perm_hash = ((uint64_t)(*i)->audit)<<32 |
+ (uint64_t)(*i)->accept;
+ } else if ((*i)->audit || (*i)->accept) {
+ /* combine all perms together into a single parition */
+ perm_hash = 1;
+ } /* else not an accept state so 0 for perm_hash */
+
+ size_t trans_hash = 0;
+ if (flags & DFA_CONTROL_MINIMIZE_HASH_TRANS)
+ trans_hash = hash_trans(*i);
+ pair <uint64_t, size_t> group = make_pair(perm_hash, trans_hash);
map <pair <uint64_t, size_t>, Partition *>::iterator p = perm_map.find(group);
if (p == perm_map.end()) {
Partition *part = new Partition();
@@ -1721,7 +1734,7 @@ void DFA::minimize(dfaflags_t flags)
perm_map.insert(make_pair(group, part));
partitions.push_back(part);
partition_map.insert(make_pair(*i, part));
- if (combined)
+ if (perm_hash)
accept_count++;
} else {
partition_map.insert(make_pair(*i, p->second));
diff --git a/parser/parser_main.c b/parser/parser_main.c
index 30e7e61..2bc897f 100644
--- a/parser/parser_main.c
+++ b/parser/parser_main.c
@@ -69,7 +69,7 @@ int binary_input = 0;
int names_only = 0;
int dump_vars = 0;
int dump_expanded_vars = 0;
-dfaflags_t dfaflags = 0;
+dfaflags_t dfaflags = DFA_CONTROL_MINIMIZE_HASH_TRANS | DFA_CONTROL_MINIMIZE_HASH_PERMS;
int conf_verbose = 0;
int conf_quiet = 0;
int kernel_load = 1;
@@ -222,7 +222,8 @@ static void display_optimize(char *command)
"expr-left-simplify do left simplification first\n"
"expr-right-simplify do right simplification first\n"
"no-minimize don't do state minimization\n"
- "no-hash-part don't hash partitions at start of minimization\n"
+ "no-hash-perms don't use permission hashing to setup partitions at start of minimization\n"
+ "no-hash-trans don't use transition hashing to setup partitions at start of minimization\n"
"no-remove-unreachable don't do unreachable state removal\n"
"trans-comp-high try to do extra transition table compression\n"
"trans-comp-fast do faster transition table compression\n"
@@ -418,10 +419,14 @@ static int process_args(int argc, char *argv[])
dfaflags &= ~DFA_CONTROL_NO_MINIMIZE;
} else if (strcmp(optarg, "no-minimize") == 0) {
dfaflags |= DFA_CONTROL_NO_MINIMIZE;
- } else if (strcmp(optarg, "hash-part") == 0) {
- dfaflags &= ~DFA_CONTROL_NO_HASH_PART;
- } else if (strcmp(optarg, "no-hash-part") == 0) {
- dfaflags |= DFA_CONTROL_NO_HASH_PART;
+ } else if (strcmp(optarg, "hash-trans") == 0) {
+ dfaflags |= DFA_CONTROL_MINIMIZE_HASH_TRANS;
+ } else if (strcmp(optarg, "no-hash-trans") == 0) {
+ dfaflags &= ~DFA_CONTROL_MINIMIZE_HASH_TRANS;
+ } else if (strcmp(optarg, "hash-perm") == 0) {
+ dfaflags |= DFA_CONTROL_MINIMIZE_HASH_PERMS;
+ } else if (strcmp(optarg, "no-hash-perms") == 0) {
+ dfaflags &= ~DFA_CONTROL_MINIMIZE_HASH_PERMS;
} else if (strcmp(optarg, "trans-comp-fast") == 0) {
dfaflags &= ~DFA_CONTROL_TRANS_HIGH;
} else if (strcmp(optarg, "trans-comp-high") == 0) {
--
1.7.1
More information about the AppArmor
mailing list