Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18;
MIME-Version: 1.0
References: <20230807171143.208481-1-cgzones@googlemail.com>
 <67cee6245e2895e81a0177c4c1ed01ba.paul@paul-moore.com> <CAJ2a_DdLR40CB6Ua5cNjYhtexNmGkzQRsVrJn+dhVaZO-aVKsA@mail.gmail.com>
In-Reply-To: <CAJ2a_DdLR40CB6Ua5cNjYhtexNmGkzQRsVrJn+dhVaZO-aVKsA@mail.gmail.com>
From:   =?UTF-8?Q?Christian_G=C3=B6ttsche?= <cgzones@googlemail.com>
Date:   Fri, 18 Aug 2023 15:55:28 +0200
Message-ID: <CAJ2a_Dfz6anX5FaTL0OsmwC6Yji=3Po=uNBWhTuvE2NUReXL6w@mail.gmail.com>
Subject: Re: [PATCH v3 2/7] selinux: use u32 as bit type in ebitmap code
To:     Paul Moore <paul@paul-moore.com>
Cc:     selinux@vger.kernel.org,
        Stephen Smalley <stephen.smalley.work@gmail.com>,
        Eric Paris <eparis@parisplace.org>,
        linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, 16 Aug 2023 at 17:00, Christian G=C3=B6ttsche <cgzones@googlemail.c=
om> wrote:
>
> On Thu, 10 Aug 2023 at 01:07, Paul Moore <paul@paul-moore.com> wrote:
> >
> > On Aug  7, 2023 =3D?UTF-8?q?Christian=3D20G=3DC3=3DB6ttsche?=3D <cgzone=
s@googlemail.com> 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 ty=
pe
> > > for bit positions to announce to callers what range of values is
> > > supported.
> > >
> > > Signed-off-by: Christian G=C3=B6ttsche <cgzones@googlemail.com>
> > > ---
> > > 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/ebit=
map.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] =3D cpu_to_le32(BITS_PER_U64);
> > >
> > >       count =3D 0;
> > >       last_bit =3D 0;
> > > -     last_startbit =3D -1;
> > > +     last_startbit =3D U32_MAX;
> > >       ebitmap_for_each_positive_bit(e, n, bit) {
> > > -             if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) =
{
> > > +             if (last_startbit =3D=3D 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.

Also the current implementation is not safe for bits in the range
[rounddown(U32_MAX, EBITMAP_SIZE), U32_MAX], since the highbit and
`startbit + EBITMAP_SIZE` calculations are not checked for overflows
(since EBITMAP_UNIT_SIZE is not a power of 2 (it's 6 on x64).

>
> > 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 =3D 1;
> >   n =3D e->node;
> >   while (n->next) {
> >     count++;
> >     n =3D n->next;
> >   }
> >   last_startbit =3D n->startbit;
> >   last_bit =3D 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.

The last_bit comment can be ignored, since last_bit is the highbit for
the mapsize of the binary format, so it's no equal to e->highbit
(which is relative to the in-memory mapsize).

>
> >
> > >                       count++;
> > >                       last_startbit =3D rounddown(bit, BITS_PER_U64);
> > >               }
> > > @@ -496,9 +497,9 @@ int ebitmap_write(const struct ebitmap *e, void *=
fp)
> > >               return rc;
> > >
> > >       map =3D 0;
> > > -     last_startbit =3D INT_MIN;
> > > +     last_startbit =3D U32_MAX;
> > >       ebitmap_for_each_positive_bit(e, n, bit) {
> > > -             if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) =
{
> > > +             if (last_startbit =3D=3D 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