Re: Watch Performance

[Alexander Viro <aviro@redhat.com>]

On Fri, Apr 21, 2006 at 11:10:21AM -0400, Linda Knippers wrote:
> 
> > Al, proposed a different solution. You might want to check with him for 
> > details. It was discussed at the Monday Telecon.
> 
> Maybe Al could post something?  With the buzz on the phone line some
> of the discussion was hard to follow.

Basically, add 3 families of rule lists.  Rule that has one AUDIT_INODE
or AUDIT_WATCH field and would currently sit in audit_filter_list[n]
would be moved to audit_filter_list[AUDIT_NR_FILTERS + n * 31 + ino % 31]
where ino is inode number from the AUDIT_INODE/AUDIT_WATCH field of that
rule.  Everything else would remain where it is now.

If ->ino changes during the lifetime, rule would have to be moved between
these lists.

When we are trying to match context with rules on (current) list #n, we
_know_ that many of them won't match just on the grounds of ->ino mismatch.
With that splitting of lists we can skip most of those - rules from the
current list #n will be on list #n and 31 lists starting with
AUDIR_NR_FILTERS + 31*n.  We only need to scan
	n (that's where non-watch rules remain)
	AUDIT_NR_FILTERS + 31*n + ctx->names[i].ino % 31 for each i less than
ctx->name_count.

Everything else is not going to match and doesn't have to be looked at.