On Tue, May 5, 2020 at 1:34 PM Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
> On Mon, May 4, 2020 at 7:59 AM Ondrej Mosnacek <omosnace@xxxxxxxxxx> wrote:
> >
> > Refactor searching and inserting into hashtabs to pave way for
> > converting hashtab_search() and hashtab_insert() to inline functions in
> > the next patch. This will avoid indirect calls and allow the compiler to
> > better optimize individual callers, leading to a drastic performance
> > improvement.
> >
> > In order to avoid the indirect calls, the key hashing and comparison
> > callbacks need to be extracted from the hashtab struct and passed
> > directly to hashtab_search()/_insert() by the callers so that it is
> > always known which callbacks we want to call at compile time. Note that
> > the kernel's rhashtable library (<linux/rhashtable*.h>) also does the
> > same.
> >
> > This of course makes the hashtab functions more easy to misuse by
> > passing a wrong calback set, but unfortunately there is no better way to
> > implement a hash table that is both generic and efficient in C. This
> > patch tries to somewhat mitigate this by only calling the hashtab
> > functions in the same file where the corresponding callbacks are
> > defined (wrapping them into more specialized functions as needed).
> >
> > Note that this patch doesn't bring any benefit without also defining
> > hashtab_search() and -_insert() inline, which is done in a follow-up
> > patch to make it easier to review the hashtab.c changes here.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@xxxxxxxxxx>
> > ---
> > security/selinux/ss/hashtab.c | 44 ++++++++++----------
> > security/selinux/ss/hashtab.h | 22 +++++-----
> > security/selinux/ss/mls.c | 2 +-
> > security/selinux/ss/policydb.c | 76 ++++++++++++++++++++++++----------
> > security/selinux/ss/policydb.h | 9 ++++
> > security/selinux/ss/services.c | 4 +-
> > security/selinux/ss/symtab.c | 16 ++++---
> > 7 files changed, 110 insertions(+), 63 deletions(-)
>
> ...
>
> > diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
> > index 31c11511fe10..4885234257d4 100644
> > --- a/security/selinux/ss/hashtab.h
> > +++ b/security/selinux/ss/hashtab.h
> > @@ -13,6 +13,12 @@
> >
> > #define HASHTAB_MAX_NODES 0xffffffff
> >
> > +struct hashtab_key_params {
> > + u32 (*hash)(const void *key); /* hash function */
> > + int (*cmp)(const void *key1, const void *key2);
> > + /* key comparison function */
> > +};
> > +
> > struct hashtab_node {
> > void *key;
> > void *datum;
> > @@ -23,10 +29,6 @@ struct hashtab {
> > struct hashtab_node **htable; /* hash table */
> > u32 size; /* number of slots in hash table */
> > u32 nel; /* number of elements in hash table */
> > - u32 (*hash_value)(struct hashtab *h, const void *key);
> > - /* hash function */
> > - int (*keycmp)(struct hashtab *h, const void *key1, const void *key2);
> > - /* key comparison function */
> > };
>
> I remain concerned that in the process of chasing performance this
> patchset makes the code worse and more fragile.
>
> What if we took a slightly different approach such that instead of
> breaking apart hashtab_node we moved the variable portions (htable,
> size, nel) into a separate struct which we could reference in
> hashtab_node? For example:
>
> struct hashtab_var {
> struct hashtab_node **htable;
> u32 size;
> u32 nel;
> }
>
> struct hashtab {
> struct hashtab_var *table; // adds an extra ptr deref
> u32 (*hash_value)(...);
> int (*keycmp)(...);
> }
>
> I might be mistaken, but I believe this should still allow you to
> implement the inlining/pass-by-value tricks for search and insert
> while maintaining a binding between the hashtable data and
> hash/compare functions. Yes? Or does the entire struct need to be
> declared as a static const for the compiler optimizations to work? It
> is not clear to me from the commit descriptions or comments in the
> code.
No, that wouldn't work. For example: when compiling a
hashtab_search(&policydb->some_hashtab, ...) call (let's assume it's
defined inline already) inside a function that takes policydb as an
argument, the compiler has no way of knowing what functions you
stashed into hash_value and keycmp in some different function, so it
has to load the pointers from memory and call them. It needs to know
what the functions are right there if it is to generate a direct
constant-address call (or inline them). In C you simply can't
associate functions (data) to types. In C++ this would be easily done
with templates, but the kernel isn't written in C++, so you simply
have to get (somewhat) dirty to get efficient code.
How about if I moved all the 4 hashtab types into a common compilation
unit (policydb_tables.[hc]?) and hid the unsafe generic hashtab
building blocks inside the C file? The header would then only expose
struct hashtab and provide specific functions for each type of
hashtab. And each hashtab "subclass" could be a separate type (which
would just wrap struct hashtab in another struct), which would be even
more type safe than the current state. Let me try to put it into a
patch, where it will be easier to see what I mean...
>
> As far as testing is concerned, whenever possible it is better to show
> performance improvements in the context of some sort of user workload
> and not an artificial stress test or micro benchmark. I understand
> that such focused tests can be attractive both in terms of their
> results and ease of use, but they can also be very misleading.
> Performance improvements for things like policy loads, kernel
> compiles, etc. are much more interesting to me than results from
> running something like stress-ng.
OK, I'll try to make my case on some more realistic benchmark.
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
