[apparmor] [PATCH 01/10] Rename State Cases to StateTrans, and fold into the State class as there is no real need for a separate class, and rename cases to trans.
John Johansen
john.johansen at canonical.com
Fri Oct 28 19:19:28 UTC 2011
This helps make the meaning of things a little clearer and provides a clear
distinction betwen NodeCases, and State transitions
Signed-off-by: John Johansen <john.johansen at canonical.com>
---
parser/libapparmor_re/compressed_hfa.cc | 38 +++++++-------
parser/libapparmor_re/compressed_hfa.h | 2 +-
parser/libapparmor_re/hfa.cc | 82 +++++++++++++++----------------
parser/libapparmor_re/hfa.h | 31 +++---------
4 files changed, 67 insertions(+), 86 deletions(-)
diff --git a/parser/libapparmor_re/compressed_hfa.cc b/parser/libapparmor_re/compressed_hfa.cc
index e0ee34d..b29198b 100644
--- a/parser/libapparmor_re/compressed_hfa.cc
+++ b/parser/libapparmor_re/compressed_hfa.cc
@@ -74,14 +74,14 @@ TransitionTable::TransitionTable(DFA &dfa, map<uchar, uchar> &eq,
for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
if (*i == dfa.start || *i == dfa.nonmatching)
continue;
- optimal += (*i)->cases.cases.size();
+ optimal += (*i)->trans.size();
if (flags & DFA_CONTROL_TRANS_HIGH) {
size_t range = 0;
- if ((*i)->cases.cases.size())
+ if ((*i)->trans.size())
range =
- (*i)->cases.cases.rbegin()->first -
- (*i)->cases.begin()->first;
- size_t ord = ((256 - (*i)->cases.cases.size()) << 8) | (256 - range);
+ (*i)->trans.rbegin()->first -
+ (*i)->trans.begin()->first;
+ size_t ord = ((256 - (*i)->trans.size()) << 8) | (256 - range);
/* reverse sort by entry count, most entries first */
order.insert(make_pair(ord, *i));
}
@@ -154,14 +154,14 @@ TransitionTable::TransitionTable(DFA &dfa, map<uchar, uchar> &eq,
}
/**
- * Does <cases> fit into position <base> of the transition table?
+ * Does <trans> fit into position <base> of the transition table?
*/
bool TransitionTable::fits_in(vector<pair<size_t, size_t> > &free_list
__attribute__ ((unused)), size_t pos,
- Cases &cases)
+ StateTrans &trans)
{
- size_t c, base = pos - cases.begin()->first;
- for (Cases::iterator i = cases.begin(); i != cases.end(); i++) {
+ size_t c, base = pos - trans.begin()->first;
+ for (StateTrans::iterator i = trans.begin(); i != trans.end(); i++) {
c = base + i->first;
/* if it overflows the next_check array it fits in as we will
* resize */
@@ -184,14 +184,14 @@ void TransitionTable::insert_state(vector<pair<size_t, size_t> > &free_list,
size_t base = 0;
int resize;
- Cases &cases = from->cases;
- size_t c = cases.begin()->first;
+ StateTrans &trans = from->trans;
+ size_t c = trans.begin()->first;
size_t prev = 0;
size_t x = first_free;
- if (cases.otherwise)
- default_state = cases.otherwise;
- if (cases.cases.empty())
+ if (from->otherwise)
+ default_state = from->otherwise;
+ if (trans.empty())
goto do_insert;
repeat:
@@ -203,16 +203,16 @@ repeat:
}
/* try inserting until we succeed. */
- while (x && !fits_in(free_list, x, cases)) {
+ while (x && !fits_in(free_list, x, trans)) {
prev = x;
x = free_list[x].second;
}
if (!x) {
- resize = 256 - cases.begin()->first;
+ resize = 256 - trans.begin()->first;
x = free_list.size();
/* set prev to last free */
- } else if (x + 255 - cases.begin()->first >= next_check.size()) {
- resize = (255 - cases.begin()->first - (next_check.size() - 1 - x));
+ } else if (x + 255 - trans.begin()->first >= next_check.size()) {
+ resize = (255 - trans.begin()->first - (next_check.size() - 1 - x));
for (size_t y = x; y; y = free_list[y].second)
prev = y;
}
@@ -229,7 +229,7 @@ repeat:
}
base = x - c;
- for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
+ for (StateTrans::iterator j = trans.begin(); j != trans.end(); j++) {
next_check[base + j->first] = make_pair(j->second, from);
size_t prev = free_list[base + j->first].first;
size_t next = free_list[base + j->first].second;
diff --git a/parser/libapparmor_re/compressed_hfa.h b/parser/libapparmor_re/compressed_hfa.h
index 26fcb73..cfc5314 100644
--- a/parser/libapparmor_re/compressed_hfa.h
+++ b/parser/libapparmor_re/compressed_hfa.h
@@ -38,7 +38,7 @@ class TransitionTable {
void init_free_list(vector<pair<size_t, size_t> > &free_list,
size_t prev, size_t start);
bool fits_in(vector<pair<size_t, size_t> > &free_list, size_t base,
- Cases &cases);
+ StateTrans &cases);
void insert_state(vector<pair<size_t, size_t> > &free_list,
State *state, DFA &dfa);
diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
index 1470214..9bee40c 100644
--- a/parser/libapparmor_re/hfa.cc
+++ b/parser/libapparmor_re/hfa.cc
@@ -103,7 +103,7 @@ void DFA::update_state_transitions(NodeMap &nodemap, list<State *> &work_queue,
/* check the default transition first */
if (cases.otherwise)
- state->cases.otherwise = find_target_state(nodemap, work_queue,
+ state->otherwise = find_target_state(nodemap, work_queue,
cases.otherwise,
stats);;
@@ -114,11 +114,11 @@ void DFA::update_state_transitions(NodeMap &nodemap, list<State *> &work_queue,
State *target;
target = find_target_state(nodemap, work_queue, j->second, stats);
- /* Don't insert transition that the default transition
+ /* Don't insert transition that the otherwise transition
* already covers
*/
- if (target != state->cases.otherwise)
- state->cases.cases[j->first] = target;
+ if (target != state->otherwise)
+ state->trans[j->first] = target;
}
}
@@ -254,11 +254,11 @@ void DFA::remove_unreachable(dfaflags_t flags)
work_queue.pop_front();
reachable.insert(from);
- if (from->cases.otherwise &&
- (reachable.find(from->cases.otherwise) == reachable.end()))
- work_queue.push_back(from->cases.otherwise);
+ if (from->otherwise &&
+ (reachable.find(from->otherwise) == reachable.end()))
+ work_queue.push_back(from->otherwise);
- for (Cases::iterator j = from->cases.begin(); j != from->cases.end(); j++) {
+ for (StateTrans::iterator j = from->trans.begin(); j != from->trans.end(); j++) {
if (reachable.find(j->second) == reachable.end())
work_queue.push_back(j->second);
}
@@ -301,22 +301,22 @@ void DFA::remove_unreachable(dfaflags_t flags)
/* test if two states have the same transitions under partition_map */
bool DFA::same_mappings(State *s1, State *s2)
{
- if (s1->cases.otherwise && s1->cases.otherwise != nonmatching) {
- if (!s2->cases.otherwise || s2->cases.otherwise == nonmatching)
+ if (s1->otherwise && s1->otherwise != nonmatching) {
+ if (!s2->otherwise || s2->otherwise == nonmatching)
return false;
- Partition *p1 = s1->cases.otherwise->partition;
- Partition *p2 = s2->cases.otherwise->partition;
+ Partition *p1 = s1->otherwise->partition;
+ Partition *p2 = s2->otherwise->partition;
if (p1 != p2)
return false;
- } else if (s2->cases.otherwise && s2->cases.otherwise != nonmatching) {
+ } else if (s2->otherwise && s2->otherwise != nonmatching) {
return false;
}
- if (s1->cases.cases.size() != s2->cases.cases.size())
+ if (s1->trans.size() != s2->trans.size())
return false;
- for (Cases::iterator j1 = s1->cases.begin(); j1 != s1->cases.end(); j1++) {
- Cases::iterator j2 = s2->cases.cases.find(j1->first);
- if (j2 == s2->cases.end())
+ for (StateTrans::iterator j1 = s1->trans.begin(); j1 != s1->trans.end(); j1++) {
+ StateTrans::iterator j2 = s2->trans.find(j1->first);
+ if (j2 == s2->trans.end())
return false;
Partition *p1 = j1->second->partition;
Partition *p2 = j2->second->partition;
@@ -330,7 +330,7 @@ bool DFA::same_mappings(State *s1, State *s2)
/* Do simple djb2 hashing against a States transition cases
* this provides a rough initial guess at state equivalence as if a state
* has a different number of transitions or has transitions on different
- * cases they will never be equivalent.
+ * trans they will never be equivalent.
* Note: this only hashes based off of the alphabet (not destination)
* as different destinations could end up being equiv
*/
@@ -338,19 +338,19 @@ size_t DFA::hash_trans(State *s)
{
unsigned long hash = 5381;
- for (Cases::iterator j = s->cases.begin(); j != s->cases.end(); j++) {
+ for (StateTrans::iterator j = s->trans.begin(); j != s->trans.end(); j++) {
hash = ((hash << 5) + hash) + j->first;
State *k = j->second;
- hash = ((hash << 5) + hash) + k->cases.cases.size();
+ hash = ((hash << 5) + hash) + k->trans.size();
}
- if (s->cases.otherwise && s->cases.otherwise != nonmatching) {
+ if (s->otherwise && s->otherwise != nonmatching) {
hash = ((hash << 5) + hash) + 5381;
- State *k = s->cases.otherwise;
- hash = ((hash << 5) + hash) + k->cases.cases.size();
+ State *k = s->otherwise;
+ hash = ((hash << 5) + hash) + k->trans.size();
}
- hash = (hash << 8) | s->cases.cases.size();
+ hash = (hash << 8) | s->trans.size();
return hash;
}
@@ -487,11 +487,11 @@ void DFA::minimize(dfaflags_t flags)
cerr << *rep << " : ";
/* update representative state's transitions */
- if (rep->cases.otherwise) {
- Partition *partition = rep->cases.otherwise->partition;
- rep->cases.otherwise = *partition->begin();
+ if (rep->otherwise) {
+ Partition *partition = rep->otherwise->partition;
+ rep->otherwise = *partition->begin();
}
- for (Cases::iterator c = rep->cases.begin(); c != rep->cases.end(); c++) {
+ for (StateTrans::iterator c = rep->trans.begin(); c != rep->trans.end(); c++) {
Partition *partition = c->second->partition;
c->second = *partition->begin();
}
@@ -577,10 +577,10 @@ void DFA::dump(ostream & os)
os << "\n";
for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- if ((*i)->cases.otherwise)
- os << **i << " -> " << (*i)->cases.otherwise << "\n";
- for (Cases::iterator j = (*i)->cases.begin();
- j != (*i)->cases.end(); j++) {
+ if ((*i)->otherwise)
+ os << **i << " -> " << (*i)->otherwise << "\n";
+ for (StateTrans::iterator j = (*i)->trans.begin();
+ j != (*i)->trans.end(); j++) {
os << **i << " -> " << j->second << ": "
<< j->first << "\n";
}
@@ -611,10 +611,9 @@ void DFA::dump_dot_graph(ostream & os)
os << "\t]" << "\n";
}
for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- Cases &cases = (*i)->cases;
Chars excluded;
- for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
+ for (StateTrans::iterator j = (*i)->trans.begin(); j != (*i)->trans.end(); j++) {
if (j->second == nonmatching)
excluded.insert(j->first);
else {
@@ -624,8 +623,8 @@ void DFA::dump_dot_graph(ostream & os)
os << "\t]" << "\n";
}
}
- if (cases.otherwise && cases.otherwise != nonmatching) {
- os << "\t\"" << **i << "\" -> \"" << *cases.otherwise
+ if ((*i)->otherwise && (*i)->otherwise != nonmatching) {
+ os << "\t\"" << **i << "\" -> \"" << *(*i)->otherwise
<< "\" [" << "\n";
if (!excluded.empty()) {
os << "\t\tlabel=\"[^";
@@ -651,11 +650,9 @@ map<uchar, uchar> DFA::equivalence_classes(dfaflags_t flags)
uchar next_class = 1;
for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- Cases & cases = (*i)->cases;
-
/* Group edges to the same next state together */
map<const State *, Chars> node_sets;
- for (Cases::iterator j = cases.begin(); j != cases.end(); j++)
+ for (StateTrans::iterator j = (*i)->trans.begin(); j != (*i)->trans.end(); j++)
node_sets[j->second].insert(j->first);
for (map<const State *, Chars>::iterator j = node_sets.begin();
@@ -742,10 +739,9 @@ void DFA::apply_equivalence_classes(map<uchar, uchar> &eq)
*/
for (Partition::iterator i = states.begin(); i != states.end(); i++) {
map<uchar, State *> tmp;
- tmp.swap((*i)->cases.cases);
- for (Cases::iterator j = tmp.begin(); j != tmp.end(); j++)
- (*i)->cases.cases.
- insert(make_pair(eq[j->first], j->second));
+ tmp.swap((*i)->trans);
+ for (StateTrans::iterator j = tmp.begin(); j != tmp.end(); j++)
+ (*i)->trans.insert(make_pair(eq[j->first], j->second));
}
}
diff --git a/parser/libapparmor_re/hfa.h b/parser/libapparmor_re/hfa.h
index a97f0b2..ee63d21 100644
--- a/parser/libapparmor_re/hfa.h
+++ b/parser/libapparmor_re/hfa.h
@@ -33,25 +33,8 @@
#include "expr-tree.h"
class State;
-/**
- * State cases are identical to NodesCases except they map to State *
- * instead of NodeSet.
- * Out-edges from a state to another: we store the follow State
- * for each input character that is not a default match in cases and
- * default matches in otherwise as well as in all matching explicit cases
- * This avoids enumerating all the explicit tranitions for default matches.
- */
-typedef struct Cases {
- typedef map<uchar, State *>::iterator iterator;
- iterator begin() { return cases.begin(); }
- iterator end() { return cases.end(); }
-
- Cases(): otherwise(0) { }
-
- map<uchar, State *> cases;
- State *otherwise;
-} Cases;
+typedef map<uchar, State *> StateTrans;
typedef list<State *> Partition;
uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
@@ -63,7 +46,8 @@ uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
* the start state is setup to have label == 1
* audit: the audit permission mask for the state
* accept: the accept permissions for the state
- * cases: set of transitions from this state
+ * trans: set of transitions from this state
+ * otherwise: the default state for transitions not in @trans
* parition: Is a temporary work variable used during dfa minimization.
* it can be replaced with a map, but that is slower and uses more
* memory.
@@ -72,10 +56,10 @@ uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
*/
class State {
public:
- State(): label(0), audit(0), accept(0), cases(), nodes(NULL) { };
- State(int l): label(l), audit(0), accept(0), cases(), nodes(NULL) { };
+ State(): label(0), audit(0), accept(0), trans(), otherwise(NULL), nodes(NULL) { };
+ State(int l): label(l), audit(0), accept(0), trans(), otherwise(NULL), nodes(NULL) { };
State(int l, NodeSet * n) throw(int):
- label(l), audit(0), accept(0), cases(), nodes(n)
+ label(l), audit(0), accept(0), trans(), otherwise(NULL), nodes(n)
{
int error;
@@ -89,7 +73,8 @@ public:
int label;
uint32_t audit, accept;
- Cases cases;
+ StateTrans trans;
+ State *otherwise;
union {
Partition *partition;
NodeSet *nodes;
--
1.7.5.4
More information about the AppArmor
mailing list