| Message ID | 20230807171143.208481-1-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Delegated to: | Paul Moore |
| Headers | show |
| Series | [v3,1/7] selinux: avoid implicit conversions in avtab code | expand |
On Aug 7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@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 type > for bit positions to announce to callers what range of values is > supported. > > Signed-off-by: Christian Göttsche <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/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. 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. > 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
On Thu, 10 Aug 2023 at 01:07, Paul Moore <paul@paul-moore.com> wrote: > > On Aug 7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@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 type > > for bit positions to announce to callers what range of values is > > supported. > > > > Signed-off-by: Christian Göttsche <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/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
On Wed, 16 Aug 2023 at 17:00, Christian Göttsche <cgzones@googlemail.com> wrote: > > On Thu, 10 Aug 2023 at 01:07, Paul Moore <paul@paul-moore.com> wrote: > > > > On Aug 7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@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 type > > > for bit positions to announce to callers what range of values is > > > supported. > > > > > > Signed-off-by: Christian Göttsche <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/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. 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 = 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. 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 = 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
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 @@ -24,7 +24,7 @@ #include "ebitmap.h" #include "policydb.h" -#define BITS_PER_U64 (sizeof(u64) * 8) +#define BITS_PER_U64 ((u32)(sizeof(u64) * 8)) static struct kmem_cache *ebitmap_node_cachep __ro_after_init; @@ -82,7 +82,8 @@ int ebitmap_cpy(struct ebitmap *dst, const struct ebitmap *src) int ebitmap_and(struct ebitmap *dst, const struct ebitmap *e1, const struct ebitmap *e2) { struct ebitmap_node *n; - int bit, rc; + u32 bit; + int rc; ebitmap_init(dst); @@ -259,7 +260,7 @@ int ebitmap_contains(const struct ebitmap *e1, const struct ebitmap *e2, u32 las return 1; } -int ebitmap_get_bit(const struct ebitmap *e, unsigned long bit) +int ebitmap_get_bit(const struct ebitmap *e, u32 bit) { const struct ebitmap_node *n; @@ -276,7 +277,7 @@ int ebitmap_get_bit(const struct ebitmap *e, unsigned long bit) return 0; } -int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) +int ebitmap_set_bit(struct ebitmap *e, u32 bit, int value) { struct ebitmap_node *n, *prev, *new; @@ -287,7 +288,7 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) if (value) { ebitmap_node_set_bit(n, bit); } else { - unsigned int s; + u32 s; ebitmap_node_clr_bit(n, bit); @@ -365,12 +366,12 @@ void ebitmap_destroy(struct ebitmap *e) int ebitmap_read(struct ebitmap *e, void *fp) { struct ebitmap_node *n = NULL; - u32 mapunit, count, startbit, index; + u32 mapunit, count, startbit, index, i; __le32 ebitmap_start; u64 map; __le64 mapbits; __le32 buf[3]; - int rc, i; + int rc; ebitmap_init(e); @@ -384,7 +385,7 @@ int ebitmap_read(struct ebitmap *e, void *fp) if (mapunit != BITS_PER_U64) { pr_err("SELinux: ebitmap: map size %u does not " - "match my size %zd (high bit was %d)\n", + "match my size %d (high bit was %d)\n", mapunit, BITS_PER_U64, e->highbit); goto bad; } @@ -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) { 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]; /* this is the very first bit */ diff --git a/security/selinux/ss/ebitmap.h b/security/selinux/ss/ebitmap.h index e3c807cfad90..43c32077d483 100644 --- a/security/selinux/ss/ebitmap.h +++ b/security/selinux/ss/ebitmap.h @@ -44,10 +44,10 @@ struct ebitmap { #define ebitmap_length(e) ((e)->highbit) -static inline unsigned int ebitmap_start_positive(const struct ebitmap *e, +static inline u32 ebitmap_start_positive(const struct ebitmap *e, struct ebitmap_node **n) { - unsigned int ofs; + u32 ofs; for (*n = e->node; *n; *n = (*n)->next) { ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); @@ -62,11 +62,11 @@ static inline void ebitmap_init(struct ebitmap *e) memset(e, 0, sizeof(*e)); } -static inline unsigned int ebitmap_next_positive(const struct ebitmap *e, +static inline u32 ebitmap_next_positive(const struct ebitmap *e, struct ebitmap_node **n, - unsigned int bit) + u32 bit) { - unsigned int ofs; + u32 ofs; ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1); if (ofs < EBITMAP_SIZE) @@ -86,10 +86,10 @@ static inline unsigned int ebitmap_next_positive(const struct ebitmap *e, (((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE) static inline int ebitmap_node_get_bit(const struct ebitmap_node *n, - unsigned int bit) + u32 bit) { - unsigned int index = EBITMAP_NODE_INDEX(n, bit); - unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); + u32 index = EBITMAP_NODE_INDEX(n, bit); + u32 ofs = EBITMAP_NODE_OFFSET(n, bit); BUG_ON(index >= EBITMAP_UNIT_NUMS); if ((n->maps[index] & (EBITMAP_BIT << ofs))) @@ -98,20 +98,20 @@ static inline int ebitmap_node_get_bit(const struct ebitmap_node *n, } static inline void ebitmap_node_set_bit(struct ebitmap_node *n, - unsigned int bit) + u32 bit) { - unsigned int index = EBITMAP_NODE_INDEX(n, bit); - unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); + u32 index = EBITMAP_NODE_INDEX(n, bit); + u32 ofs = EBITMAP_NODE_OFFSET(n, bit); BUG_ON(index >= EBITMAP_UNIT_NUMS); n->maps[index] |= (EBITMAP_BIT << ofs); } static inline void ebitmap_node_clr_bit(struct ebitmap_node *n, - unsigned int bit) + u32 bit) { - unsigned int index = EBITMAP_NODE_INDEX(n, bit); - unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); + u32 index = EBITMAP_NODE_INDEX(n, bit); + u32 ofs = EBITMAP_NODE_OFFSET(n, bit); BUG_ON(index >= EBITMAP_UNIT_NUMS); n->maps[index] &= ~(EBITMAP_BIT << ofs); @@ -126,8 +126,8 @@ int ebitmap_cmp(const struct ebitmap *e1, const struct ebitmap *e2); int ebitmap_cpy(struct ebitmap *dst, const struct ebitmap *src); int ebitmap_and(struct ebitmap *dst, const struct ebitmap *e1, const struct ebitmap *e2); int ebitmap_contains(const struct ebitmap *e1, const struct ebitmap *e2, u32 last_e2bit); -int ebitmap_get_bit(const struct ebitmap *e, unsigned long bit); -int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value); +int ebitmap_get_bit(const struct ebitmap *e, u32 bit); +int ebitmap_set_bit(struct ebitmap *e, u32 bit, int value); void ebitmap_destroy(struct ebitmap *e); int ebitmap_read(struct ebitmap *e, void *fp); int ebitmap_write(const struct ebitmap *e, void *fp);
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@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(-)