[apparmor] Patch 0/11] various dfa improvements

[John Johansen]

This set of patches applies on top of the previous (yet uncommitted) patch
and provide further enhancements to dfa creation.  They don't significantly
affect peak memory consumption but they do result in faster compilation
and smaller dfas.

Just how much faster and smaller is dependent on the size of the dfa and
the amount of extra states that can now be removed during minimization.  In
general the large the dfa the better the minimization and speed improvements
are.

For example using the evince profile

2.5.1 gets
jj at ortho:~/apparmor/master-new/parser$ time ./apparmor_parser -QT -D dfa-stats /etc/apparmor.d/usr.bin.evince
Created dfa: states 22	matching 2	nonmatching 20
Minimize dfa: partitions 22	init 17	(accept 1)
Created dfa: states 26267	matching 166234	nonmatching 26265
Minimize dfa: partitions 13790	init 4545	(accept 3847)
Created dfa: states 32	matching 2	nonmatching 30
Minimize dfa: partitions 32	init 20	(accept 1)
Created dfa: states 16098	matching 99605	nonmatching 16096
Minimize dfa: partitions 10975	init 3964	(accept 3240)
Created dfa: states 34	matching 2	nonmatching 32
Minimize dfa: partitions 34	init 23	(accept 1)
Created dfa: states 18113	matching 112208	nonmatching 18111
Minimize dfa: partitions 10754	init 3837	(accept 3113)

real	0m30.202s
user	0m29.840s
sys	0m0.190s

with the full set of patches applied

jj at ortho:~/apparmor/master-new/parser$ time ./apparmor_parser -QT -D dfa-stats /etc/apparmor.d/usr.bin.evince
Created dfa: states 22	matching 2	nonmatching 21
Dfa minimization no states removed: partitions 22	init 17 (accept 1)
Created dfa: states 26267	matching 166234	nonmatching 26266
Minimized dfa: final partitions 9070 (accept 6369)	init 1838 (accept 1140)
Created dfa: states 32	matching 2	nonmatching 31
Dfa minimization no states removed: partitions 32	init 20 (accept 1)
Created dfa: states 16098	matching 99605	nonmatching 16097
Minimized dfa: final partitions 7836 (accept 5336)	init 1912 (accept 1188)
Created dfa: states 34	matching 2	nonmatching 33
Dfa minimization no states removed: partitions 34	init 23 (accept 1)
Created dfa: states 18113	matching 112208	nonmatching 18112
Minimized dfa: final partitions 7947 (accept 5441)	init 1913 (accept 1189)

real	0m17.469s
user	0m17.180s
sys	0m0.130s


about 1/2 of the performance improvements are comming from the tweaks to
dfa generation, the other half from the dfa's being smaller 9070 vs 13790
states, which speeds up dfa compression.