On Mon, Nov 20, 2023 at 8:29 PM Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
>
> On Nov 3, 2023 Jacob Satterfield <jsatterfield.linux@xxxxxxxxx> wrote:
> >
> > Due to how conditional rules are written in the binary policy, the
> > code responsible for loading does not know how many conditional rules
> > there are before creating the avtab structure. Instead, it uses the
> > number of elements in the non-conditional avtab as a hint and allocates
> > the hash table based on it. In the refpolicy and default Fedora policy,
> > the actual sizes of these tables are not similar (~85k vs ~10k) thereby
> > creating more slots than needed and resulting in wasted memory.
> >
> > This patch introduces a two-pass algorithm to calculate the conditional
> > rule count before allocating the avtab nodes array. Albeit with a slight
> > performance penalty in reading a portion of the binary policy twice,
> > this causes the number of hash slots for the conditional array to become
> > 4096 instead of 32768. At 8-bytes per slot on 64-bit architectures, this
> > results in a net savings of 224 KB of heap memory.
> >
> > Signed-off-by: Jacob Satterfield <jsatterfield.linux@xxxxxxxxx>
> > Reviewed-by: Stephen Smalley <stephen.smalley.work@xxxxxxxxx>
> > ---
> > security/selinux/ss/avtab.c | 15 ++++++++++--
> > security/selinux/ss/avtab.h | 2 +-
> > security/selinux/ss/conditional.c | 38 ++++++++++++++++++++-----------
> > security/selinux/ss/conditional.h | 2 +-
> > 4 files changed, 40 insertions(+), 17 deletions(-)
>
> ...
>
> > diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
> > index 81ff676f209a..810319bf0e60 100644
> > --- a/security/selinux/ss/conditional.c
> > +++ b/security/selinux/ss/conditional.c
> > @@ -407,16 +408,17 @@ static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
> > return -EINVAL;
> > }
> >
> > - rc = cond_read_av_list(p, fp, &node->true_list, NULL);
> > + rc = cond_read_av_list(p, fp, &node->true_list, NULL, nrules);
> > if (rc)
> > return rc;
> > - return cond_read_av_list(p, fp, &node->false_list, &node->true_list);
> > + return cond_read_av_list(p, fp, &node->false_list, &node->true_list, nrules);
> > }
> >
> > -int cond_read_list(struct policydb *p, void *fp)
> > +int cond_read_list(struct policydb *p, struct policy_file *fp)
> > {
> > __le32 buf[1];
> > - u32 i, len;
> > + struct policy_file tmp_fp;
> > + u32 i, len, nrules;
> > int rc;
> >
> > rc = next_entry(buf, fp, sizeof(buf));
> > @@ -428,15 +430,25 @@ int cond_read_list(struct policydb *p, void *fp)
> > p->cond_list = kcalloc(len, sizeof(*p->cond_list), GFP_KERNEL);
> > if (!p->cond_list)
> > return -ENOMEM;
> > + p->cond_list_len = len;
> > +
> > + /* first pass to only calculate the avrule count */
> > + tmp_fp = *fp;
> > + nrules = 0;
> > + for (i = 0; i < p->cond_list_len; i++) {
> > + rc = cond_read_node(p, &p->cond_list[i], &tmp_fp, &nrules);
> > + if (rc)
> > + goto err;
> > + cond_node_destroy(&p->cond_list[i]);
> > + }
>
> I'm a concerned about all the work we have to do just to count the
> conditional rules. Other than not working with existing binary
> policies, have you looked at bumping the policy version and introducing
> a binary format change that would include the number of conditional
> rules?
>
> --
> paul-moore.com
Thanks for raising the issue. I had considered adding the total size
of the conditional table to the binary policy, but I wasn't sure if it
would be substantive enough to warrant bumping the policy version. As
you point out, the counting work will be needed for existing binary
policies making this patch necessary for the default case, but if you
are concerned about the performance penalty this patch brings (which
is less than the gain provided by the avtab array patch), then there
are two threads to possibly be worked on.
One is to rework this patch to include more invasive changes to count
rules without actually reading and destroying nodes thus saving cycles
but requiring more lines of code. Because policy parsing is not
handled separately from the construction of the policydb structure
(they are deeply intertwined), I was reluctant to add more complexity
just to have a parse-only code path. Would you prefer speed or simpler
logic for older policies?
The other is to obviously sum and add the total size of the
conditional rules table to the binary policy in cond_write_list() of
libsepol/src/write.c. If you think just adding the total conditional
rules table size is worth bumping the kernel policy version, then I
can prioritize sending a patch to libsepol for inclusion as soon as I
can.
