Re: [PATCH v3 2/7] selinux: use u32 as bit type in ebitmap code

[Christian Göttsche]

On Thu, 10 Aug 2023 at 01:07, Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
>
> On Aug  7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@xxxxxxxxxxxxxx> wrote:
> >
> > The extensible bitmap supports bit positions up to U32_MAX due to the
> > type of the member highbit being u32.  Use u32 consistently as the type
> > for bit positions to announce to callers what range of values is
> > supported.
> >
> > Signed-off-by: Christian Göttsche <cgzones@xxxxxxxxxxxxxx>
> > ---
> > v3:
> >   - revert type change of unrelated iter variable
> >   - use U32_MAX instead of (u32)-1
> > v2: avoid declarations in init-clauses of for loops
> > ---
> >  security/selinux/ss/ebitmap.c | 29 +++++++++++++++--------------
> >  security/selinux/ss/ebitmap.h | 32 ++++++++++++++++----------------
> >  2 files changed, 31 insertions(+), 30 deletions(-)
>
> ...
>
> > diff --git a/security/selinux/ss/ebitmap.c b/security/selinux/ss/ebitmap.c
> > index 77875ad355f7..a313e633aa8e 100644
> > --- a/security/selinux/ss/ebitmap.c
> > +++ b/security/selinux/ss/ebitmap.c
> > @@ -471,18 +472,18 @@ int ebitmap_read(struct ebitmap *e, void *fp)
> >  int ebitmap_write(const struct ebitmap *e, void *fp)
> >  {
> >       struct ebitmap_node *n;
> > -     u32 count;
> > +     u32 bit, count, last_bit, last_startbit;
> >       __le32 buf[3];
> >       u64 map;
> > -     int bit, last_bit, last_startbit, rc;
> > +     int rc;
> >
> >       buf[0] = cpu_to_le32(BITS_PER_U64);
> >
> >       count = 0;
> >       last_bit = 0;
> > -     last_startbit = -1;
> > +     last_startbit = U32_MAX;
> >       ebitmap_for_each_positive_bit(e, n, bit) {
> > -             if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
> > +             if (last_startbit == U32_MAX || rounddown(bit, BITS_PER_U64) > last_startbit) {
>
> I'm getting worried about what might happen if the ebitmap starts to
> contain bits near the end of the range, e.g. U32_MAX.  When lastbit
> was signed this was a non-issue as we could set it to a negative
> value (-1) and not worry about it, although the maximum value
> difference between the signed and unsigned types would eventually be
> a problem.

For the maximum bit of U32_MAX `rounddown(bit, BITS_PER_U64)` will
return U32_MAX-63, so it does not collide with the special
last_startbit value of U32_MAX.

> While looking closer at this loop, I'm now wondering if we shouldn't
> just rewrite the logic a bit to simplify things, and possibly speed
> it up a small amount.  How about something like this:
>
>   count = 1;
>   n = e->node;
>   while (n->next) {
>     count++;
>     n = n->next;
>   }
>   last_startbit = n->startbit;
>   last_bit = n->startbit + find_last_bit(n->maps, EBITMAP_SIZE);
>
> You should probably verify that there isn't something stupid like an
> off-by-one bug in the code above, but I think it is a lot cleaner
> than what we currently have and should resolve a lot of the type/math
> issues.

I think this loop does not work, since in the binary format the map
size is 64 bits (and thus we need to calculate the number of 64bit
nodes), but the kernel supports (depending on the architecture) 32bit
maps for the in-memory representation.
So the number of in-memory nodes might not be the same as the number
of nodes in binary format.

p.s.:

Looking at the patch again, `rounddown(bit, BITS_PER_U64)` is computed
twice and last_bit can probably be dropped in favor of e->highbit.

>
> >                       count++;
> >                       last_startbit = rounddown(bit, BITS_PER_U64);
> >               }
> > @@ -496,9 +497,9 @@ int ebitmap_write(const struct ebitmap *e, void *fp)
> >               return rc;
> >
> >       map = 0;
> > -     last_startbit = INT_MIN;
> > +     last_startbit = U32_MAX;
> >       ebitmap_for_each_positive_bit(e, n, bit) {
> > -             if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
> > +             if (last_startbit == U32_MAX || rounddown(bit, BITS_PER_U64) > last_startbit) {
> >                       __le64 buf64[1];
>
> Similar to the above, I think we can probably rewrite this to simply
> walk the ebitmap nodes and write them out.  Using
> ebitmap_for_each_positive_bit() seems overly complicated to me,
> although I may be missing something important and obvious ...
>
> --
> paul-moore.com