Signed-off-by: NJohn Johansen <john.johansen@canonical.com>

Instead of testing whether a given dfa exists in every code path, have
a default null dfa that is used when loaded policy doesn't provide a
dfa.

This will let us get rid of special casing and avoid dereference bugs
when special casing is missed.
Signed-off-by: NJohn Johansen <john.johansen@canonical.com>

The dfa is currently setup to be shared (has the basis of refcounting)
but currently can't be because the count can't be increased.
Signed-off-by: NJohn Johansen <john.johansen@canonical.com>

Signed-off-by: NJohn Johansen <john.johansen@canonical.com>

Signed-off-by: NJohn Johansen <john.johansen@canonical.com>
Acked-by: NSteve Beattie <sbeattie@ubuntu.com>

tidying up comments, includes and defines
Signed-off-by: NJohn Johansen <john.johansen@canonical.com>
Acked-by: NKees Cook <kees@ubuntu.com>

Update aa_dfa_match so that it doesn't result in an input string being
walked twice (once to get its length and another time to match)

Add a single step functions
  aa_dfa_next
Signed-off-by: NJohn Johansen <john.johansen@canonical.com>
Acked-by: NKees Cook <kees@ubuntu.com>

Remove kobject.h from files which don't need it, notably,
sched.h and fs.h.
Signed-off-by: NAlexey Dobriyan <adobriyan@gmail.com>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

"gadget", "through", "command", "maintain", "maintain", "controller", "address",
"between", "initiali[zs]e", "instead", "function", "select", "already",
"equal", "access", "management", "hierarchy", "registration", "interest",
"relative", "memory", "offset", "already",
Signed-off-by: NUwe Kleine-König <u.kleine-koenig@pengutronix.de>
Signed-off-by: NJiri Kosina <jkosina@suse.cz>

A basic dfa matching engine based off the dfa engine in the Dragon
Book.  It uses simple row comb compression with a check field.

This allows AppArmor to do pattern matching in linear time, and also
avoids stack issues that an nfa based engine may have.  The dfa
engine uses a byte based comparison, with all values being valid.
Any potential character encoding are handled user side when the dfa
tables are created.  By convention AppArmor uses \0 to separate two
dependent path matches since \0 is not a valid path character
(this is done in the link permission check).

The dfa tables are generated in user space and are verified at load
time to be internally consistent.

There are several future improvements planned for the dfa engine:
* The dfa engine may be converted to a hybrid nfa-dfa engine, with
  a fixed size limited stack.  This would allow for size time
  tradeoffs, by inserting limited nfa states to help control
  state explosion that can occur with dfas.
* The dfa engine may pickup the ability to do limited dynamic
  variable matching, instead of fixing all variables at policy
  load time.
Signed-off-by: NJohn Johansen <john.johansen@canonical.com>
Signed-off-by: NJames Morris <jmorris@namei.org>