[apparmor] [PATCH 06/10] Lindent + some hand cleanups hfa
John Johansen
john.johansen at canonical.com
Thu Mar 10 20:35:56 UTC 2011
Signed-off-by: John Johansen <john.johansen at canonical.com>
---
parser/libapparmor_re/hfa.cc | 586 ++++++++++++++++++++++--------------------
parser/libapparmor_re/hfa.h | 80 ++++---
2 files changed, 352 insertions(+), 314 deletions(-)
diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
index c392293..1281333 100644
--- a/parser/libapparmor_re/hfa.cc
+++ b/parser/libapparmor_re/hfa.cc
@@ -35,9 +35,7 @@
#include "hfa.h"
#include "../immunix.h"
-
-
-ostream& operator<<(ostream& os, const State& state)
+ostream & operator<<(ostream &os, const State &state)
{
/* dump the state label */
os << '{';
@@ -46,7 +44,9 @@ ostream& operator<<(ostream& os, const State& state)
return os;
}
-State* DFA::add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats)
+State *DFA::add_new_state(NodeMap &nodemap,
+ pair <unsigned long, NodeSet * > index,
+ NodeSet *nodes, dfa_stats_t &stats)
{
State *state = new State(nodemap.size(), nodes);
states.push_back(state);
@@ -62,9 +62,11 @@ State *DFA::find_target_state(NodeMap &nodemap, list <State *> &work_queue,
{
State *target;
- pair <unsigned long, NodeSet *> index = make_pair(hash_NodeSet(nodes), nodes);
+ pair <unsigned long, NodeSet *> index =
+ make_pair(hash_NodeSet(nodes), nodes);
- map<pair <unsigned long, NodeSet *>, State *, deref_less_than>::iterator x = nodemap.find(index);
+ map <pair <unsigned long, NodeSet *>, State *,
+ deref_less_than>::iterator x = nodemap.find(index);
if (x == nodemap.end()) {
/* set of nodes isn't known so create new state, and nodes to
@@ -75,7 +77,7 @@ State *DFA::find_target_state(NodeMap &nodemap, list <State *> &work_queue,
} else {
/* set of nodes already has a mapping so free this one */
stats.duplicates++;
- delete (nodes);
+ delete(nodes);
target = x->second;
}
@@ -94,7 +96,8 @@ void DFA::update_state_transitions(NodeMap &nodemap,
* sets of nodes.
*/
NodeCases cases;
- for (NodeSet::iterator i = state->nodes->begin(); i != state->nodes->end(); i++)
+ for (NodeSet::iterator i = state->nodes->begin();
+ i != state->nodes->end(); i++)
(*i)->follow(cases);
/* Now for each set of nodes in the computed transitions, make
@@ -124,15 +127,13 @@ void DFA::update_state_transitions(NodeMap &nodemap,
}
}
-
/* WARNING: This routine can only be called from within DFA creation as
* the nodes value is only valid during dfa construction.
*/
void DFA::dump_node_to_dfa(void)
{
cerr << "Mapping of States to expr nodes\n"
- " State <= Nodes\n"
- "-------------------\n";
+ " State <= Nodes\n" "-------------------\n";
for (Partition::iterator i = states.begin(); i != states.end(); i++)
cerr << " " << (*i)->label << " <= " << *(*i)->nodes << "\n";
}
@@ -140,7 +141,7 @@ void DFA::dump_node_to_dfa(void)
/**
* Construct a DFA from a syntax tree.
*/
-DFA::DFA(Node *root, dfaflags_t flags) : root(root)
+DFA::DFA(Node *root, dfaflags_t flags): root(root)
{
dfa_stats_t stats = { 0, 0, 0 };
int i = 0;
@@ -162,8 +163,8 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
NodeMap nodemap;
NodeSet *emptynode = new NodeSet;
- nonmatching = add_new_state(nodemap,
- make_pair(hash_NodeSet(emptynode), emptynode),
+ nonmatching = add_new_state(nodemap, make_pair(hash_NodeSet(emptynode),
+ emptynode),
emptynode, stats);
NodeSet *first = new NodeSet(root->firstpos);
@@ -180,12 +181,15 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
* manner, this may help reduce the number of entries on the
* work_queue at any given time, thus reducing peak memory use.
*/
- list<State *> work_queue;
+ list < State * >work_queue;
work_queue.push_back(start);
while (!work_queue.empty()) {
if (i % 1000 == 0 && (flags & DFA_DUMP_PROGRESS))
- fprintf(stderr, "\033[2KCreating dfa: queue %ld\tstates %ld\teliminated duplicates %d\r", work_queue.size(), states.size(), stats.duplicates);
+ fprintf(stderr,
+ "\033[2KCreating dfa: queue %ld\tstates %ld\teliminated duplicates %d\r",
+ work_queue.size(), states.size(),
+ stats.duplicates);
i++;
State *from = work_queue.front();
@@ -196,7 +200,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
*/
update_state_transitions(nodemap, work_queue, from, stats);
- } /* for (NodeSet *nodes ... */
+ } /* for (NodeSet *nodes ... */
/* cleanup Sets of nodes used computing the DFA as they are no longer
* needed.
@@ -215,32 +219,34 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
nodemap.clear();
if (flags & (DFA_DUMP_STATS))
- fprintf(stderr, "\033[2KCreated dfa: states %ld,\teliminated duplicates %d,\tprotostate sets: longest %u, avg %u\n", states.size(), stats.duplicates, stats.proto_max, (unsigned int) (stats.proto_sum/states.size()));
+ fprintf(stderr,
+ "\033[2KCreated dfa: states %ld,\teliminated duplicates %d,\tprotostate sets: longest %u, avg %u\n",
+ states.size(), stats.duplicates, stats.proto_max,
+ (unsigned int)(stats.proto_sum / states.size()));
}
-
DFA::~DFA()
{
- for (Partition::iterator i = states.begin(); i != states.end(); i++)
- delete *i;
+ for (Partition::iterator i = states.begin(); i != states.end(); i++)
+ delete *i;
}
void DFA::dump_uniq_perms(const char *s)
{
- set < pair<uint32_t, uint32_t> > uniq;
+ set <pair <uint32_t, uint32_t> > uniq;
for (Partition::iterator i = states.begin(); i != states.end(); i++)
uniq.insert(make_pair((*i)->accept, (*i)->audit));
cerr << "Unique Permission sets: " << s << " (" << uniq.size() << ")\n";
cerr << "----------------------\n";
- for (set< pair<uint32_t, uint32_t> >::iterator i = uniq.begin();
+ for (set <pair <uint32_t, uint32_t> >::iterator i = uniq.begin();
i != uniq.end(); i++) {
- cerr << " " << hex << i->first << " " << i->second << dec <<"\n";
+ cerr << " " << hex << i->first << " " << i->
+ second << dec << "\n";
}
}
-
/* Remove dead or unreachable states */
void DFA::remove_unreachable(dfaflags_t flags)
{
@@ -276,12 +282,13 @@ void DFA::remove_unreachable(dfaflags_t flags)
next++;
if (reachable.find(*i) == reachable.end()) {
if (flags & DFA_DUMP_UNREACHABLE) {
- cerr << "unreachable: "<< **i;
+ cerr << "unreachable: " << **i;
if (*i == start)
cerr << " <==";
if ((*i)->accept) {
- cerr << " (0x" << hex << (*i)->accept
- << " " << (*i)->audit << dec << ')';
+ cerr << " (0x" << hex << (*i)->
+ accept << " " << (*i)->
+ audit << dec << ')';
}
cerr << endl;
}
@@ -294,12 +301,12 @@ void DFA::remove_unreachable(dfaflags_t flags)
if (count && (flags & DFA_DUMP_STATS))
cerr << "DFA: states " << states.size() << " removed "
- << count << " unreachable states\n";
+ << count << " unreachable states\n";
}
}
/* test if two states have the same transitions under partition_map */
-bool DFA::same_mappings(State *s1, State *s2)
+bool DFA::same_mappings(State * s1, State * s2)
{
if (s1->cases.otherwise && s1->cases.otherwise != nonmatching) {
if (!s2->cases.otherwise || s2->cases.otherwise == nonmatching)
@@ -315,7 +322,7 @@ bool DFA::same_mappings(State *s1, State *s2)
if (s1->cases.cases.size() != s2->cases.cases.size())
return false;
for (Cases::iterator j1 = s1->cases.begin(); j1 != s1->cases.end();
- j1++){
+ j1++) {
Cases::iterator j2 = s2->cases.cases.find(j1->first);
if (j2 == s2->cases.end())
return false;
@@ -335,11 +342,11 @@ bool DFA::same_mappings(State *s1, State *s2)
* Note: this only hashes based off of the alphabet (not destination)
* as different destinations could end up being equiv
*/
-size_t DFA::hash_trans(State *s)
+size_t DFA::hash_trans(State * s)
{
- unsigned long hash = 5381;
+ unsigned long hash = 5381;
- for (Cases::iterator j = s->cases.begin(); j != s->cases.end(); j++){
+ for (Cases::iterator j = s->cases.begin(); j != s->cases.end(); j++) {
hash = ((hash << 5) + hash) + j->first;
State *k = j->second;
hash = ((hash << 5) + hash) + k->cases.cases.size();
@@ -352,7 +359,7 @@ size_t DFA::hash_trans(State *s)
}
hash = (hash << 8) | s->cases.cases.size();
- return hash;
+ return hash;
}
/* minimize the number of dfa states */
@@ -360,7 +367,7 @@ void DFA::minimize(dfaflags_t flags)
{
map <pair <uint64_t, size_t>, Partition *> perm_map;
list <Partition *> partitions;
-
+
/* Set up the initial partitions
* minimium of - 1 non accepting, and 1 accepting
* if trans hashing is used the accepting and non-accepting partitions
@@ -377,18 +384,20 @@ void DFA::minimize(dfaflags_t flags)
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;
+ 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 */
-
+ }
+ /* 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);
+ 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();
part->push_back(*i);
@@ -404,7 +413,9 @@ void DFA::minimize(dfaflags_t flags)
if ((flags & DFA_DUMP_PROGRESS) &&
(partitions.size() % 1000 == 0))
- cerr << "\033[2KMinimize dfa: partitions " << partitions.size() << "\tinit " << partitions.size() << " (accept " << accept_count << ")\r";
+ cerr << "\033[2KMinimize dfa: partitions " <<
+ partitions.size() << "\tinit " << partitions.
+ size() << " (accept " << accept_count << ")\r";
}
/* perm_map is no longer needed so free the memory it is using.
@@ -414,7 +425,9 @@ void DFA::minimize(dfaflags_t flags)
int init_count = partitions.size();
if (flags & DFA_DUMP_PROGRESS)
- cerr << "\033[2KMinimize dfa: partitions " << partitions.size() << "\tinit " << init_count << " (accept " << accept_count << ")\r";
+ cerr << "\033[2KMinimize dfa: partitions " << partitions.
+ size() << "\tinit " << init_count << " (accept " <<
+ accept_count << ")\r";
/* Now do repartitioning until each partition contains the set of
* states that are the same. This will happen when the partition
@@ -431,14 +444,14 @@ void DFA::minimize(dfaflags_t flags)
State *rep = *((*p)->begin());
Partition::iterator next;
for (Partition::iterator s = ++(*p)->begin();
- s != (*p)->end(); ) {
+ s != (*p)->end();) {
if (same_mappings(rep, *s)) {
++s;
continue;
}
if (!new_part) {
new_part = new Partition;
- list <Partition *>::iterator tmp = p;
+ list < Partition * >::iterator tmp = p;
partitions.insert(++tmp, new_part);
new_part_count++;
}
@@ -454,16 +467,22 @@ void DFA::minimize(dfaflags_t flags)
(*m)->partition = new_part;
}
}
- if ((flags & DFA_DUMP_PROGRESS) &&
- (partitions.size() % 100 == 0))
- cerr << "\033[2KMinimize dfa: partitions " << partitions.size() << "\tinit " << init_count << " (accept " << accept_count << ")\r";
+ if ((flags & DFA_DUMP_PROGRESS) &&
+ (partitions.size() % 100 == 0))
+ cerr << "\033[2KMinimize dfa: partitions " <<
+ partitions.
+ size() << "\tinit " << init_count <<
+ " (accept " << accept_count << ")\r";
}
- } while(new_part_count);
+ } while (new_part_count);
if (partitions.size() == states.size()) {
if (flags & DFA_DUMP_STATS)
- cerr << "\033[2KDfa minimization no states removed: partitions " << partitions.size() << "\tinit " << init_count << " (accept " << accept_count << ")\n";
-
+ cerr <<
+ "\033[2KDfa minimization no states removed: partitions "
+ << partitions.
+ size() << "\tinit " << init_count << " (accept " <<
+ accept_count << ")\n";
goto out;
}
@@ -474,7 +493,7 @@ void DFA::minimize(dfaflags_t flags)
* to states within the same partitions, however this can slow
* down compressed dfa compression as there are more states,
*/
- for (list <Partition *>::iterator p = partitions.begin();
+ for (list < Partition * >::iterator p = partitions.begin();
p != partitions.end(); p++) {
/* representative state for this partition */
State *rep = *((*p)->begin());
@@ -494,7 +513,8 @@ void DFA::minimize(dfaflags_t flags)
//cerr << rep->label << ": ";
/* clear the state label for all non representative states,
* and accumulate permissions */
- for (Partition::iterator i = ++(*p)->begin(); i != (*p)->end(); i++) {
+ for (Partition::iterator i = ++(*p)->begin(); i != (*p)->end();
+ i++) {
//cerr << " " << (*i)->label;
(*i)->label = -1;
rep->accept |= (*i)->accept;
@@ -506,9 +526,9 @@ void DFA::minimize(dfaflags_t flags)
//cerr << "\n";
}
if (flags & DFA_DUMP_STATS)
- cerr << "\033[2KMinimized dfa: final partitions " << partitions.size() << " (accept " << final_accept << ")" << "\tinit " << init_count << " (accept " << accept_count << ")\n";
-
-
+ cerr << "\033[2KMinimized dfa: final partitions " << partitions.
+ size() << " (accept " << final_accept << ")" << "\tinit " <<
+ init_count << " (accept " << accept_count << ")\n";
/* make sure nonmatching and start state are up to date with the
* mappings */
@@ -528,7 +548,7 @@ void DFA::minimize(dfaflags_t flags)
* that are not the representive states for their partition, they
* will have a label == -1
*/
- for (Partition::iterator i = states.begin(); i != states.end(); ) {
+ for (Partition::iterator i = states.begin(); i != states.end();) {
if ((*i)->label == -1) {
State *s = *i;
i = states.erase(i);
@@ -537,7 +557,7 @@ void DFA::minimize(dfaflags_t flags)
i++;
}
-out:
+ out:
/* Cleanup */
while (!partitions.empty()) {
Partition *p = partitions.front();
@@ -549,229 +569,238 @@ out:
/**
* text-dump the DFA (for debugging).
*/
-void DFA::dump(ostream& os)
+void DFA::dump(ostream & os)
{
- for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- if (*i == start || (*i)->accept) {
- os << **i;
- if (*i == start)
- os << " <==";
- if ((*i)->accept) {
- os << " (0x" << hex << (*i)->accept << " " << (*i)->audit << dec << ')';
- }
- os << endl;
+ for (Partition::iterator i = states.begin(); i != states.end(); i++) {
+ if (*i == start || (*i)->accept) {
+ os << **i;
+ if (*i == start)
+ os << " <==";
+ if ((*i)->accept) {
+ os << " (0x" << hex << (*i)->
+ accept << " " << (*i)->audit << dec << ')';
+ }
+ os << endl;
+ }
}
- }
- os << endl;
-
- for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- if ((*i)->cases.otherwise)
- os << **i << " -> " << (*i)->cases.otherwise << endl;
- for (Cases::iterator j = (*i)->cases.begin(); j != (*i)->cases.end(); j++) {
- os << **i << " -> " << j->second << ": " << j->first << endl;
+ os << endl;
+
+ for (Partition::iterator i = states.begin(); i != states.end(); i++) {
+ if ((*i)->cases.otherwise)
+ os << **i << " -> " << (*i)->cases.otherwise << endl;
+ for (Cases::iterator j = (*i)->cases.begin();
+ j != (*i)->cases.end(); j++) {
+ os << **i << " -> " << j->second << ": " << j->
+ first << endl;
+ }
}
- }
- os << endl;
+ os << endl;
}
/**
* Create a dot (graphviz) graph from the DFA (for debugging).
*/
-void DFA::dump_dot_graph(ostream& os)
+void DFA::dump_dot_graph(ostream & os)
{
- os << "digraph \"dfa\" {" << endl;
+ os << "digraph \"dfa\" {" << endl;
- for (Partition::iterator i = states.begin(); i != states.end(); i++) {
- if (*i == nonmatching)
- continue;
+ for (Partition::iterator i = states.begin(); i != states.end(); i++) {
+ if (*i == nonmatching)
+ continue;
- os << "\t\"" << **i << "\" [" << endl;
- if (*i == start) {
- os << "\t\tstyle=bold" << endl;
- }
- uint32_t perms = (*i)->accept;
- if (perms) {
- os << "\t\tlabel=\"" << **i << "\\n("
- << perms << ")\"" << endl;
- }
- os << "\t]" << endl;
- }
- 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++) {
- if (j->second == nonmatching)
- excluded.insert(j->first);
- else {
- os << "\t\"" << **i << "\" -> \"";
- os << j->second << "\" [" << endl;
- os << "\t\tlabel=\"" << j->first << "\"" << endl;
- os << "\t]" << endl;
- }
+ os << "\t\"" << **i << "\" [" << endl;
+ if (*i == start) {
+ os << "\t\tstyle=bold" << endl;
+ }
+ uint32_t perms = (*i)->accept;
+ if (perms) {
+ os << "\t\tlabel=\"" << **i << "\\n("
+ << perms << ")\"" << endl;
+ }
+ os << "\t]" << endl;
}
- if (cases.otherwise && cases.otherwise != nonmatching) {
- os << "\t\"" << **i << "\" -> \"" << cases.otherwise
- << "\" [" << endl;
- if (!excluded.empty()) {
- os << "\t\tlabel=\"[^";
- for (Chars::iterator i = excluded.begin();
- i != excluded.end();
- i++) {
- os << *i;
+ 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++) {
+ if (j->second == nonmatching)
+ excluded.insert(j->first);
+ else {
+ os << "\t\"" << **i << "\" -> \"";
+ os << j->second << "\" [" << endl;
+ os << "\t\tlabel=\"" << j->
+ first << "\"" << endl;
+ os << "\t]" << endl;
+ }
+ }
+ if (cases.otherwise && cases.otherwise != nonmatching) {
+ os << "\t\"" << **i << "\" -> \"" << cases.otherwise
+ << "\" [" << endl;
+ if (!excluded.empty()) {
+ os << "\t\tlabel=\"[^";
+ for (Chars::iterator i = excluded.begin();
+ i != excluded.end(); i++) {
+ os << *i;
+ }
+ os << "]\"" << endl;
+ }
+ os << "\t]" << endl;
}
- os << "]\"" << endl;
- }
- os << "\t]" << endl;
}
- }
- os << '}' << endl;
+ os << '}' << endl;
}
/**
* Compute character equivalence classes in the DFA to save space in the
* transition table.
*/
-map<uchar, uchar> DFA::equivalence_classes(dfaflags_t flags)
+map <uchar, uchar> DFA::equivalence_classes(dfaflags_t flags)
{
- map<uchar, uchar> classes;
- 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++)
- node_sets[j->second].insert(j->first);
-
- for (map<const State *, Chars>::iterator j = node_sets.begin();
- j != node_sets.end();
- j++) {
- /* Group edges to the same next state together by class */
- map<uchar, Chars> node_classes;
- bool class_used = false;
- for (Chars::iterator k = j->second.begin();
- k != j->second.end();
- k++) {
- pair<map<uchar, uchar>::iterator, bool> x =
- classes.insert(make_pair(*k, next_class));
- if (x.second)
- class_used = true;
- pair<map<uchar, Chars>::iterator, bool> y =
- node_classes.insert(make_pair(x.first->second, Chars()));
- y.first->second.insert(*k);
- }
- if (class_used) {
- next_class++;
- class_used = false;
- }
- for (map<uchar, Chars>::iterator k = node_classes.begin();
- k != node_classes.end();
- k++) {
+ map <uchar, uchar> classes;
+ 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++)
+ node_sets[j->second].insert(j->first);
+
+ for (map <const State *, Chars>::iterator j =
+ node_sets.begin(); j != node_sets.end(); j++) {
+ /* Group edges to the same next state together by class */
+ map <uchar, Chars> node_classes;
+ bool class_used = false;
+ for (Chars::iterator k = j->second.begin();
+ k != j->second.end(); k++) {
+ pair <map <uchar, uchar>::iterator, bool> x =
+ classes.insert(make_pair(*k, next_class));
+ if (x.second)
+ class_used = true;
+ pair <map <uchar, Chars>::iterator, bool> y =
+ node_classes.
+ insert(make_pair(x.first->second, Chars()));
+ y.first->second.insert(*k);
+ }
+ if (class_used) {
+ next_class++;
+ class_used = false;
+ }
+ for (map <uchar, Chars>::iterator k =
+ node_classes.begin();
+ k != node_classes.end();
+ k++) {
/**
* If any other characters are in the same class, move
* the characters in this class into their own new class
*/
- map<uchar, uchar>::iterator l;
- for (l = classes.begin(); l != classes.end(); l++) {
- if (l->second == k->first &&
- k->second.find(l->first) == k->second.end()) {
- class_used = true;
- break;
- }
- }
- if (class_used) {
- for (Chars::iterator l = k->second.begin();
- l != k->second.end();
- l++) {
- classes[*l] = next_class;
- }
- next_class++;
- class_used = false;
+ map <uchar, uchar>::iterator l;
+ for (l = classes.begin(); l != classes.end();
+ l++) {
+ if (l->second == k->first
+ && k->second.find(l->first) ==
+ k->second.end()) {
+ class_used = true;
+ break;
+ }
+ }
+ if (class_used) {
+ for (Chars::iterator l =
+ k->second.begin();
+ l != k->second.end(); l++) {
+ classes[*l] = next_class;
+ }
+ next_class++;
+ class_used = false;
+ }
+ }
}
- }
}
- }
- if (flags & DFA_DUMP_EQUIV_STATS)
- fprintf(stderr, "Equiv class reduces to %d classes\n", next_class - 1);
- return classes;
+ if (flags & DFA_DUMP_EQUIV_STATS)
+ fprintf(stderr, "Equiv class reduces to %d classes\n",
+ next_class - 1);
+ return classes;
}
/**
* Text-dump the equivalence classes (for debugging).
*/
-void dump_equivalence_classes(ostream& os, map<uchar, uchar>& eq)
+void dump_equivalence_classes(ostream & os, map <uchar, uchar> &eq)
{
- map<uchar, Chars> rev;
-
- for (map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
- Chars& chars = rev.insert(make_pair(i->second,
- Chars())).first->second;
- chars.insert(i->first);
- }
- os << "(eq):" << endl;
- for (map<uchar, Chars>::iterator i = rev.begin(); i != rev.end(); i++) {
- os << (int)i->first << ':';
- Chars& chars = i->second;
- for (Chars::iterator j = chars.begin(); j != chars.end(); j++) {
- os << ' ' << *j;
+ map <uchar, Chars> rev;
+
+ for (map <uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
+ Chars & chars = rev.insert(make_pair(i->second,
+ Chars())).first->second;
+ chars.insert(i->first);
+ }
+ os << "(eq):" << endl;
+ for (map <uchar, Chars>::iterator i = rev.begin(); i != rev.end();
+ i++) {
+ os << (int)i->first << ':';
+ Chars &chars = i->second;
+ for (Chars::iterator j = chars.begin(); j != chars.end(); j++) {
+ os << ' ' << *j;
+ }
+ os << endl;
}
- os << endl;
- }
}
/**
* Replace characters with classes (which are also represented as
* characters) in the DFA transition table.
*/
-void DFA::apply_equivalence_classes(map<uchar, uchar>& eq)
+void DFA::apply_equivalence_classes(map <uchar, uchar> &eq)
{
/**
* Note: We only transform the transition table; the nodes continue to
* contain the original characters.
*/
- 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));
- }
+ 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));
+ }
}
#if 0
-typedef set<ImportantNode *> AcceptNodes;
-map<ImportantNode *, AcceptNodes> dominance(DFA& dfa)
+typedef set < ImportantNode * >AcceptNodes;
+map < ImportantNode *, AcceptNodes > dominance(DFA & dfa)
{
- map<ImportantNode *, AcceptNodes> is_dominated;
-
- for (States::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
- AcceptNodes set1;
- for (State::iterator j = (*i)->begin(); j != (*i)->end(); j++) {
- if (AcceptNode *accept = dynamic_cast<AcceptNode *>(*j))
- set1.insert(accept);
- }
- for (AcceptNodes::iterator j = set1.begin(); j != set1.end(); j++) {
- pair<map<ImportantNode *, AcceptNodes>::iterator, bool> x =
- is_dominated.insert(make_pair(*j, set1));
- if (!x.second) {
- AcceptNodes &set2(x.first->second), set3;
- for (AcceptNodes::iterator l = set2.begin();
- l != set2.end();
- l++) {
- if (set1.find(*l) != set1.end())
- set3.insert(*l);
+ map < ImportantNode *, AcceptNodes > is_dominated;
+
+ for (States::iterator i = dfa.states.begin(); i != dfa.states.end();
+ i++) {
+ AcceptNodes set1;
+ for (State::iterator j = (*i)->begin(); j != (*i)->end(); j++) {
+ if (AcceptNode * accept =
+ dynamic_cast <AcceptNode *>(*j))
+ set1.insert(accept);
+ }
+ for (AcceptNodes::iterator j = set1.begin(); j != set1.end();
+ j++) {
+ pair <map <ImportantNode *, AcceptNodes>::iterator,
+ bool> x = is_dominated.insert(make_pair(*j, set1));
+ if (!x.second) {
+ AcceptNodes & set2(x.first->second), set3;
+ for (AcceptNodes::iterator l = set2.begin();
+ l != set2.end(); l++) {
+ if (set1.find(*l) != set1.end())
+ set3.insert(*l);
+ }
+ set3.swap(set2);
+ }
}
- set3.swap(set2);
- }
}
- }
- return is_dominated;
+ return is_dominated;
}
#endif
-
static inline int diff_qualifiers(uint32_t perm1, uint32_t perm2)
{
return ((perm1 & AA_EXEC_TYPE) && (perm2 & AA_EXEC_TYPE) &&
@@ -785,79 +814,80 @@ static inline int diff_qualifiers(uint32_t perm1, uint32_t perm2)
*/
uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error)
{
- uint32_t perms = 0, exact_match_perms = 0, audit = 0, exact_audit = 0,
+ uint32_t perms = 0, exact_match_perms = 0, audit = 0, exact_audit = 0,
quiet = 0, deny = 0;
- if (error)
- *error = 0;
- for (NodeSet::iterator i = state->begin(); i != state->end(); i++) {
- MatchFlag *match;
- if (!(match= dynamic_cast<MatchFlag *>(*i)))
- continue;
- if (dynamic_cast<ExactMatchFlag *>(match)) {
- /* exact match only ever happens with x */
- if (!is_merged_x_consistent(exact_match_perms,
- match->flag) && error)
- *error = 1;;
- exact_match_perms |= match->flag;
- exact_audit |= match->audit;
- } else if (dynamic_cast<DenyMatchFlag *>(match)) {
- deny |= match->flag;
- quiet |= match->audit;
- } else {
- if (!is_merged_x_consistent(perms, match->flag) && error)
- *error = 1;
- perms |= match->flag;
- audit |= match->audit;
- }
- }
+ if (error)
+ *error = 0;
+ for (NodeSet::iterator i = state->begin(); i != state->end(); i++) {
+ MatchFlag *match;
+ if (!(match = dynamic_cast<MatchFlag *>(*i)))
+ continue;
+ if (dynamic_cast<ExactMatchFlag *>(match)) {
+ /* exact match only ever happens with x */
+ if (!is_merged_x_consistent(exact_match_perms,
+ match->flag) && error)
+ *error = 1;;
+ exact_match_perms |= match->flag;
+ exact_audit |= match->audit;
+ } else if (dynamic_cast<DenyMatchFlag *>(match)) {
+ deny |= match->flag;
+ quiet |= match->audit;
+ } else {
+ if (!is_merged_x_consistent(perms, match->flag)
+ && error)
+ *error = 1;
+ perms |= match->flag;
+ audit |= match->audit;
+ }
+ }
//if (audit || quiet)
//fprintf(stderr, "perms: 0x%x, audit: 0x%x exact: 0x%x eaud: 0x%x deny: 0x%x quiet: 0x%x\n", perms, audit, exact_match_perms, exact_audit, deny, quiet);
- perms |= exact_match_perms &
- ~(AA_USER_EXEC_TYPE | AA_OTHER_EXEC_TYPE);
+ perms |= exact_match_perms & ~(AA_USER_EXEC_TYPE | AA_OTHER_EXEC_TYPE);
- if (exact_match_perms & AA_USER_EXEC_TYPE) {
- perms = (exact_match_perms & AA_USER_EXEC_TYPE) |
+ if (exact_match_perms & AA_USER_EXEC_TYPE) {
+ perms = (exact_match_perms & AA_USER_EXEC_TYPE) |
(perms & ~AA_USER_EXEC_TYPE);
- audit = (exact_audit & AA_USER_EXEC_TYPE) |
- (audit & ~ AA_USER_EXEC_TYPE);
- }
- if (exact_match_perms & AA_OTHER_EXEC_TYPE) {
- perms = (exact_match_perms & AA_OTHER_EXEC_TYPE) |
+ audit = (exact_audit & AA_USER_EXEC_TYPE) |
+ (audit & ~AA_USER_EXEC_TYPE);
+ }
+ if (exact_match_perms & AA_OTHER_EXEC_TYPE) {
+ perms = (exact_match_perms & AA_OTHER_EXEC_TYPE) |
(perms & ~AA_OTHER_EXEC_TYPE);
- audit = (exact_audit & AA_OTHER_EXEC_TYPE) |
+ audit = (exact_audit & AA_OTHER_EXEC_TYPE) |
(audit & ~AA_OTHER_EXEC_TYPE);
- }
- if (perms & AA_USER_EXEC & deny)
- perms &= ~AA_USER_EXEC_TYPE;
+ }
+ if (perms & AA_USER_EXEC & deny)
+ perms &= ~AA_USER_EXEC_TYPE;
- if (perms & AA_OTHER_EXEC & deny)
- perms &= ~AA_OTHER_EXEC_TYPE;
+ if (perms & AA_OTHER_EXEC & deny)
+ perms &= ~AA_OTHER_EXEC_TYPE;
- perms &= ~deny;
+ perms &= ~deny;
- if (audit_ctl)
- *audit_ctl = PACK_AUDIT_CTL(audit, quiet & deny);
+ if (audit_ctl)
+ *audit_ctl = PACK_AUDIT_CTL(audit, quiet & deny);
// if (perms & AA_ERROR_BIT) {
// fprintf(stderr, "error bit 0x%x\n", perms);
// exit(255);
//}
- //if (perms & AA_EXEC_BITS)
- //fprintf(stderr, "accept perm: 0x%x\n", perms);
- /*
- if (perms & ~AA_VALID_PERMS)
- yyerror(_("Internal error accumulated invalid perm 0x%llx\n"), perms);
- */
+ //if (perms & AA_EXEC_BITS)
+ //fprintf(stderr, "accept perm: 0x%x\n", perms);
+ /*
+ if (perms & ~AA_VALID_PERMS)
+ yyerror(_("Internal error accumulated invalid perm 0x%llx\n"), perms);
+ */
//if (perms & AA_CHANGE_HAT)
// fprintf(stderr, "change_hat 0x%x\n", perms);
- if (*error)
- fprintf(stderr, "profile has merged rule with conflicting x modifiers\n");
+ if (*error)
+ fprintf(stderr,
+ "profile has merged rule with conflicting x modifiers\n");
- return perms;
+ return perms;
}
diff --git a/parser/libapparmor_re/hfa.h b/parser/libapparmor_re/hfa.h
index a017a45..0cd0609 100644
--- a/parser/libapparmor_re/hfa.h
+++ b/parser/libapparmor_re/hfa.h
@@ -42,17 +42,22 @@ class State;
* 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(); }
+ typedef map <uchar, State *>::iterator iterator;
+ iterator begin() {
+ return cases.begin();
+ } iterator end() {
+ return cases.end();
+ }
- Cases() : otherwise(0) { }
- map<uchar, State *> cases;
+ Cases():otherwise(0) { }
+
+ map <uchar, State *> cases;
State *otherwise;
-} Cases;
+}
-typedef list<State *> Partition;
+Cases;
+typedef list <State *> Partition;
uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
@@ -71,18 +76,17 @@ uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
* be replaced by using the nodemap, but that is slower
*/
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(int l, NodeSet *n) throw (int):
- label(l), audit(0), accept(0), cases(), nodes(n)
- {
+ public:
+ State():label(0), audit(0), accept(0), cases(), nodes(NULL) { };
+ State(int l):label(l), audit(0), accept(0), cases(), nodes(NULL) { };
+ State(int l, NodeSet * n) throw(int):label(l), audit(0), accept(0),
+ cases(), nodes(n) {
int error;
/* Compute permissions associated with the State. */
accept = accept_perms(nodes, &audit, &error);
if (error) {
- //cerr << "Failing on accept perms " << error << "\n";
+ //cerr << "Failing on accept perms " << error << "\n";
throw error;
}
};
@@ -96,9 +100,9 @@ public:
};
};
-ostream& operator<<(ostream& os, const State& state);
+ostream & operator<<(ostream & os, const State & state);
-typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than > NodeMap;
+typedef map <pair <unsigned long, NodeSet *>, State *, deref_less_than> NodeMap;
/* Transitions in the DFA. */
/* dfa_stats - structure to group various stats about dfa creation
@@ -112,28 +116,32 @@ typedef struct dfa_stats {
} dfa_stats_t;
class DFA {
- void dump_node_to_dfa(void);
- State* add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats);
- void update_state_transitions(NodeMap &nodemap, list <State *> &work_queue, State *state, dfa_stats_t &stats);
- State *find_target_state(NodeMap &nodemap, list <State *> &work_queue,
+ void dump_node_to_dfa(void);
+ State *add_new_state(NodeMap & nodemap,
+ pair <unsigned long, NodeSet *> index,
NodeSet *nodes, dfa_stats_t &stats);
-public:
- DFA(Node *root, dfaflags_t flags);
- virtual ~DFA();
- void remove_unreachable(dfaflags_t flags);
- bool same_mappings(State *s1, State *s2);
- size_t hash_trans(State *s);
- void minimize(dfaflags_t flags);
- void dump(ostream& os);
- void dump_dot_graph(ostream& os);
- void dump_uniq_perms(const char *s);
- map<uchar, uchar> equivalence_classes(dfaflags_t flags);
- void apply_equivalence_classes(map<uchar, uchar>& eq);
- Node *root;
- State *nonmatching, *start;
- Partition states;
+ void update_state_transitions(NodeMap & nodemap,
+ list <State *> &work_queue,
+ State *state, dfa_stats_t &stats);
+ State *find_target_state(NodeMap &nodemap, list <State *> &work_queue,
+ NodeSet *nodes, dfa_stats_t &stats);
+ public:
+ DFA(Node * root, dfaflags_t flags);
+ virtual ~DFA();
+ void remove_unreachable(dfaflags_t flags);
+ bool same_mappings(State *s1, State *s2);
+ size_t hash_trans(State *s);
+ void minimize(dfaflags_t flags);
+ void dump(ostream &os);
+ void dump_dot_graph(ostream &os);
+ void dump_uniq_perms(const char *s);
+ map <uchar, uchar> equivalence_classes(dfaflags_t flags);
+ void apply_equivalence_classes(map <uchar, uchar> &eq);
+ Node *root;
+ State *nonmatching, *start;
+ Partition states;
};
-void dump_equivalence_classes(ostream& os, map<uchar, uchar>& eq);
+void dump_equivalence_classes(ostream &os, map <uchar, uchar> &eq);
#endif /* __LIBAA_RE_HFA_H */
--
1.7.1
More information about the AppArmor
mailing list