[redhat-lspp] Re: Linux Audit Performance Analysis

[Alexander Viro]

	Polite short version: the code in question has been somewhat
misparsed.  Longer one:

What happens is that we are evaluating an expression of form
(major in Set1 && (P11(tsk, ctx, args11) && P12(tsk, ctx, args12) && ....)) ||
(major in Set2 && (P21(tsk, ctx, args21) && P22(tsk, ctx, args22) && ....)) ||
....

Each line in the above corresponds to a rule.  Each P..() comes from a field in
rule.  And implementation is

for all rules
	if major is not in Set<n>
		continue
	if evaluate the rest for rule
		return true
return false

with audit_filter_rules() being that "evaluate the rest for rule".  It,
in turn, is essentially
	for all fields in rule
		result = P<rule><field>(...);
		if (!result)
			return false
	return true

All Pij are from a small set of predicates.  So each field of rule contains
a number indicating which predicate it is and arguments to give it.  And
evaluation of P<rule><field> in the above is done essentually by
	switch rule.fields[field].which_predicate
		<implementations of all possible predicates>

That's what the current code does.

Now for the comments.
	a) 'result' in audit_filter_rules() is a misnomer.  Rename to
'conjunct', perhaps?
	b) audit_filter_rules() itself is a misnomer.  audit_evaluate_rule()?
	c) the only way we can skip the call of that function is if we
apriory know it to return false.  Note that we certainly do _NOT_ call it
for every rule in the list (actual code is
                        if ((e->rule.mask[word] & bit) == bit
                                        && audit_filter_rules(tsk, &e->rule, ctx, &state)) {
and if the first part is false, we don't even look at the second).  We can
do _some_ work in that direction.  Any such work would boil down to paritioning
the set of rules into subsets and turning that loop into
	n = candidate1(); loop over subset #n
	n = candidate2(); loop over subset #n
etc., with the following requirements:
	* we should be able to find which subsets are worth looking into just
by tsk and ctx.
	* reduction of number of rules being evaluated should be worth the
extra efforts taken to find which subsets to look into.

There is one case that appears to be worth the efforts.  Namely, rules
with only one of AUDIT_INODE/AUDIT_WATCH field in them.  These rules
only evaluate to true if one of the ctx->names[<something>].ino is
equal to a fixed number stored in rule.  So we can split them off into
separate subsets (e.g. by ino % 31) and check ones that have any hope
to match + all rules not of that form.   That's essentially what I
propose to do for AUDIT_WATCH-induced performance degradation.

The only reason why it's worth doing is that a lot of rules can be
discriminated against in that way.  Something like extra split based
on e.g. tsk->pid would be worthless - the split is too uneven to
justify it.

	d) we _CAN_ try to reduce the amount of time we spend in those
loops outside of calls to audit_filter_rules().  And that might very
well be worth the efforts.  To do that, we'd need to split the set
of rules into subsets and use the checks on major to discriminate.
Note that this is not as trivial as it sounds, since we do have rules
with Set<n> consisting of more than one element.  We need real-world
data on the rule sets and especially on the distribution of syscall
sets for those rules.  Could somebody collect that?

	e) one thing about that distribution: there will be very frequently
used syscall sets.  Moreover, it might make a lot of sense to _introduce_
such sets on the kernel level.  E.g. have something like
AUDIT_BITMASK_SIZE * 32 - 1 seen in bitmap coming from auditctl turn into
"all directory-modifying syscalls" when kernel fills bitmap in internal data
structure.  That would make life much easier for keeping rule sets _AND_
auditctl binary working across various kernel versions (i.e. solves a
"what if a new version of syscall is added tomorrow" problem).

One thing to watch out for: the _ordering_ of rules is not neutral too;
aside of true/false in the above, there is a "what kind of action does
it want if it applies", so we should be careful with any kind of splitting,
etc. to avoid breaking that.  If more than one rule applies and they
call for different actions, we should make sure that our splitting, etc.
of the rule list doesn't affect which one we will find.