[apparmor] [Patch 0/10] DFA rework - split out permission handling

John Johansen john.johansen at canonical.com
Fri Oct 28 19:19:27 UTC 2011

This is the first set of patches in the permission and dfa backend rework.
This set is some basic cleanups and changes to how the permission nodes are
stored, so that we can have more information in them to fix merging and other
issues that we currently skirt with permission hashing.

As part of this set, work was done to reduce memory consumption because
just storing off the accepting states resulted in increased memory usage
(which was already bad).  These changes are seen in the last two patches.

The affect is a decent decrease in memory used, at a small decrease in
performance.  Specifically heap memory allocations in the dfa construction
phase are reduced.  The amount of the decrease in memory usage is dependant on
the policy being compiled, with the savings being greater the larger the dfa
being generated.  The performance reduction is also related to the size of
the generated dfa with the greatest percentage loss on smaller dfas, with it
actually improving performance slightly on much larger dfas.

Some fiures from valgrind massif output:

Eg.  Mid size DFA:  12160 states geneated, average non-accept chain len=22
                      time    Heap Mem  Pre DFA mem  DFA usage
pre-split:            8.23s   30.76 MB    6.16 MB     24.60 MB
split patch:          8.55s   27.14 MB    6.16 MB     20.98 MB
split + vector patch: 8.27s   15.00 MB    6.16 MB      8.84 MB

with the vector patch on average policy compilation is a little slower at
this size but saves ~16MB (24.60 - 8.84) or ~3x reduction during dfa creation

Eg. Larger DFA: 39776 states generated, average non-accept chain len=61
                      time    Heap Mem  Pre DFA mem  DFA usage
pre-split:            17.00s  177.6 MB   22.96 MB    154.54 MB
split patch:          18.11s  161.5 MB   22.96 MB    138.54 MB
split + vector patch: 15.88s   63.9 MB   22.96 MB     40.94 MB

at this size with the vector patch average policy compilation is a little
faster (15.88s vs 17s) and saves ~115MB (154.54 - 40.94) or ~3.77x reduction
during dfa creation.

Note: These patches are only focused on DFA creation, there are other
patches in the works to address memory issues and performance in other

More information about the AppArmor mailing list