[apparmor] [PATCH 09/10] Split the nodeset used in computing the dfa into two sets, accepting and non-accepting, and have the proto-state use them.

Seth Arnold seth.arnold at gmail.com
Mon Oct 31 22:50:07 UTC 2011

> Forgive the lengthy, and meandering of the reply.  Hopefully it will fully
> explain what is going on, and why certain choices where made :)

Thanks for the effort :) It all makes some amount of sense until I
start re-reading the code again and trying to line up what you wrote
with what I can read. It _sounds_ a little like the effort required to
perform state minimization but that might just be me grasping at
straws. But it sure sounds like _you_ know what's going on, which is
reassuring. :)

> Created dfa: states 12160 proto { cache: size=12160 dups=71797 longest=324 avg=28 }, nnodes { cache: size=11841 dups=72116 longest=322 avg=22 }, anodes { cache: size=55 dups=64655 longest=20 avg=7 }

So this portion here sure sounds compelling -- is this really reducing
a DFA of 12k states down to 55 total accepting nodes -- when the more
"naive" construction would have resulted in 64k total accepting nodes?

Thanks John

More information about the AppArmor mailing list