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 <[email protected]>
---
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
@@ -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);
--
2.40.1
Return u32 from avtab_hash() instead of int, since the hashing is done
on u32 and the result is used as an index on the hash array.
Use the type of the limit in for loops.
Avoid signed to unsigned conversion of multiplication result in
avtab_hash_eval() and perform multiplication in destination type.
Use unsigned loop iterator for index operations, to avoid sign
extension.
Signed-off-by: Christian Göttsche <[email protected]>
---
v3:
- use fixed sized counters in avtab_hash_eval()
- perform multiplication in avtab_hash_eval() in destination type
v2: avoid declarations in init-clauses of for loops
---
security/selinux/ss/avtab.c | 24 ++++++++++++------------
1 file changed, 12 insertions(+), 12 deletions(-)
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 243e5dabfa86..86d98a8e291b 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -29,7 +29,7 @@ static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
/* Based on MurmurHash3, written by Austin Appleby and placed in the
* public domain.
*/
-static inline int avtab_hash(const struct avtab_key *keyp, u32 mask)
+static inline u32 avtab_hash(const struct avtab_key *keyp, u32 mask)
{
static const u32 c1 = 0xcc9e2d51;
static const u32 c2 = 0x1b873593;
@@ -66,7 +66,7 @@ static inline int avtab_hash(const struct avtab_key *keyp, u32 mask)
}
static struct avtab_node*
-avtab_insert_node(struct avtab *h, int hvalue,
+avtab_insert_node(struct avtab *h, u32 hvalue,
struct avtab_node *prev,
const struct avtab_key *key, const struct avtab_datum *datum)
{
@@ -106,7 +106,7 @@ avtab_insert_node(struct avtab *h, int hvalue,
static int avtab_insert(struct avtab *h, const struct avtab_key *key,
const struct avtab_datum *datum)
{
- int hvalue;
+ u32 hvalue;
struct avtab_node *prev, *cur, *newnode;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
@@ -152,7 +152,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
const struct avtab_key *key,
const struct avtab_datum *datum)
{
- int hvalue;
+ u32 hvalue;
struct avtab_node *prev, *cur;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
@@ -186,7 +186,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
struct avtab_node *avtab_search_node(struct avtab *h,
const struct avtab_key *key)
{
- int hvalue;
+ u32 hvalue;
struct avtab_node *cur;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
@@ -246,7 +246,7 @@ avtab_search_node_next(struct avtab_node *node, u16 specified)
void avtab_destroy(struct avtab *h)
{
- int i;
+ u32 i;
struct avtab_node *cur, *temp;
if (!h)
@@ -325,7 +325,7 @@ int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
#ifdef CONFIG_SECURITY_SELINUX_DEBUG
void avtab_hash_eval(struct avtab *h, const char *tag)
{
- int i, chain_len, slots_used, max_chain_len;
+ u32 i, chain_len, slots_used, max_chain_len;
unsigned long long chain2_len_sum;
struct avtab_node *cur;
@@ -344,7 +344,7 @@ void avtab_hash_eval(struct avtab *h, const char *tag)
if (chain_len > max_chain_len)
max_chain_len = chain_len;
- chain2_len_sum += chain_len * chain_len;
+ chain2_len_sum += (unsigned long long)chain_len * chain_len;
}
}
@@ -374,13 +374,13 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
{
__le16 buf16[4];
u16 enabled;
- u32 items, items2, val, vers = pol->policyvers;
+ u32 items, items2, val, i;
struct avtab_key key;
struct avtab_datum datum;
struct avtab_extended_perms xperms;
__le32 buf32[ARRAY_SIZE(xperms.perms.p)];
- int i, rc;
- unsigned set;
+ int rc;
+ unsigned int set, vers = pol->policyvers;
memset(&key, 0, sizeof(struct avtab_key));
memset(&datum, 0, sizeof(struct avtab_datum));
@@ -616,7 +616,7 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
int avtab_write(struct policydb *p, struct avtab *a, void *fp)
{
- unsigned int i;
+ u32 i;
int rc = 0;
struct avtab_node *cur;
__le32 buf[1];
--
2.40.1
On Aug 7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <[email protected]> wrote:
>
> Return u32 from avtab_hash() instead of int, since the hashing is done
> on u32 and the result is used as an index on the hash array.
>
> Use the type of the limit in for loops.
>
> Avoid signed to unsigned conversion of multiplication result in
> avtab_hash_eval() and perform multiplication in destination type.
>
> Use unsigned loop iterator for index operations, to avoid sign
> extension.
>
> Signed-off-by: Christian Göttsche <[email protected]>
> ---
> v3:
> - use fixed sized counters in avtab_hash_eval()
> - perform multiplication in avtab_hash_eval() in destination type
> v2: avoid declarations in init-clauses of for loops
> ---
> security/selinux/ss/avtab.c | 24 ++++++++++++------------
> 1 file changed, 12 insertions(+), 12 deletions(-)
Merged into selinux/next, thanks.
--
paul-moore.com
On Aug 7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <[email protected]> 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 <[email protected]>
> ---
> 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 Wed, 16 Aug 2023 at 17:00, Christian Göttsche <[email protected]> wrote:
>
> On Thu, 10 Aug 2023 at 01:07, Paul Moore <[email protected]> wrote:
> >
> > On Aug 7, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <[email protected]> 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 <[email protected]>
> > > ---
> > > 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