Tuning avtab to reduce memory usage

Hi.

I would like to propose patch that reduce memory usage of avtab again. It reduces number of hash slots of avtab.
Previous patch was discussed in past threads.
http://marc.info/?t=118517459600001&r=1&w=2
http://marc.info/?t=118526972800008&r=1&w=2
http://marc.info/?t=118647810000001&r=1&w=2

0. Background
* In avtab_init:
h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
Number of hash table size is AVTAB_SIZE.

* In avtab.h
#define AVTAB_HASH_BITS 15
#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
#define AVTAB_SIZE AVTAB_HASH_BUCKETS

AVTAB_SIZE is 2^15 = 32768

So 32768 entries are allocated for avtab,
and 2 avtabs are used in policydb:
struct avtab te_avtab;
struct avtab te_cond_avtab;

If te rules are fewer than 32768,
unused entries are using memory.

In embedded devices, the rules tend to be fewer.
In my test system(SH architecture board), it is less than 10000 rules. We want to save memory for embedded devices.

1. Explanation of patch
It decides number of hash slots dynamically based on number of rules. There was 3 points I had to consider, according to previous discussion.
1) Tuning hash function
I tried to tune hash function(AVTAB_HASH) for avtab.
But I found it is better not to change hash function.

I compared 3 hash functions, default, jhash, hash_long. default is default AVTAB_HASH.
jhash is function defined in linux/jhash.h.
hash_long is defined in linux/hash.h, I used it like following.

	(int)(hash_long(((unsigned long)keyp->target_class)+
    (((unsigned long)keyp->target_type)<<2)+
    (((unsigned long)keyp->source_type)<<9)  , bits))

According to benchmark result in 3.2(1)(2),
chain length of jhash/hash_long are better.
However, performance is worse.
So, I think it is better not to change hash function for avtab.

2) Number of dynamically allocated hash slots I decided to allocate <number of rules>/4 hash slots. Because performance remains almost the same, see benchmark result in 3.2(2).

3) Max number of hash slots
There is max number of hash slots.
It was 32768 in previous patch.
I found we can reduce it to 8192.
Performance had not got worse, see benchmark result in 3.1(1). I also replaced vmalloc with kmalloc to allocate hash slots.

2. Memory usage
I measured memory usage by /proc/memstat before/after tuning.

* Memory usage: SELinux before loading policy.
2720k is used.

* Memory usage: SELinux after loading policy(about 8000 rules) before patch +1116k increase

* Memory usage: SELinux after loading poilcy(about 8000 rules) after patch. configured AVTAB_HASH_BITS as "13"
+780k increase
-> improved 336k

3. Benchmark
3.1 Explanation of benchmark
To measure performance,
I measured time to call security_compute_av varying number of hash slots and hash functions.
I measured time 10000 security_compute_av call from system boot, using below code.

int avc_has_perm_noaudit(u32 ssid, u32 tsid,
u16 tclass, u32 requested, struct av_decision *avd)

{
	struct avc_node *node;
	struct avc_entry entry, *p_ae;
	int rc = 0;
	u32 denied;

(quoted diff) +7 -0

+	unsigned long long t0,t1;
+	unsigned long long t2=0;
+	static unsigned long long t3=0;
+	static int count = 0;
+	static int flag = 1;
+	static int max = 10000;
+	int i = 0;

	rcu_read_lock();

(quoted diff) +13 -0

+	if (flag && ss_initialized) {
+		t0 = sched_clock();
+		security_compute_av(ssid,tsid,tclass, requested, &entry.avd);
+		t1 = sched_clock();
+		t2 = t1 - t0;
+		t3 += t2;
+		count ++;
+	} 
+	if (flag && (count == max)) {
+		flag = 0;
+		printk("SELinux:security_compute_av execution time:%Lu\n", t3);
+
+	}

security_compute_av is located at the entry of avc_has_perm_no_audit. And nano second to call 10000 security_compute_av function is printed out.

3.2 Benchmark Result
1) Benchmark for full strict policy, x86 system
This benchmark is to see performance for PC system with full SELinux feature. ** Environment
* Policy: selinux-policy-strict-2.4.6-80.fc6
166741 unconditional rules
* Kernel: linux-2.6.22
* CPU: Pentium 4 2.26 GHz
* RAM: 1GB
In this environment, max number of hash slot is allocated.

** Result
* number of hash slots: 32768

               longest chain length  time to call security compute_av
 Default hash  34                    0.87(s)
 jhash         21                    1.10(s)
 hash_long     17                    0.99(s)

* hash slot: 8192

              longest chain length   time to call security compute_av
 Default hash  97                    1.00(s)
 jhash         41                    1.92(s)
 hash_long     43                    1.42(s)

* hash slot: 4096

               longest chain length  time to call security compute_av
 Default hash  182                   1.14(s)
 jhash         41                    3.33(s)
 hash_long     43                    2.19(s)

2) Benchmark for small policy, embedded system This benchmark is to see performance for small system. I made small refpolicy, and run on embedded CPU.

** Environment
* Policy: serefpolicy-2.4.6, build with targeted 8188 unconditional rules
* Kernel: linux-2.6.22
* CPU: SH-4(SH 7751R) 240Mhz
* RAM: 64M

** Result
* Number of slot(8192) = num of rules
longest chain length time to call security compute_av

 Default hash  13                   9.67(s)
 hash_long     8                    9.78(s)

* Number of slot(4096) = num of rules/2
longest chain length time to call security compute_av

 Default hash  21                   9.65(s)
 hash_long     10                   9.85(s)

* Number of slot(2048) = num of rules/4

              longest chain length  time to call security compute_av
 Default hash  35                   9.68(s)
 hash_long     13                   9.99(s)

* Number of slot(1024) = num of rules/8

              longest chain length  time to call security compute_av
 Default hash  64                   9.78(s)
 hash_long     19                   10.25(s)

Next is a patch.

Signed-off-by Yuichi Nakamura <[email protected]>

----

 avtab.c       |   61 ++++++++++++++++++++++++++++++++++++++++++++--------------
 avtab.h       |   13 +++++++-----
 conditional.c |    6 +++++
 policydb.c    |    9 ++------
 4 files changed, 64 insertions(+), 25 deletions(-)

diff -ur security/selinux.notuning/ss/avtab.c security/selinux/ss/avtab.c

selinux/ss/avtab.c renamed from selinux.notuning/ss/avtab.c +47 -14

@@ -16,17 +16,16 @@
 
 #include <linux/kernel.h>
 #include <linux/slab.h>
-#include <linux/vmalloc.h>
 #include <linux/errno.h>
 
 #include "avtab.h"
 #include "policydb.h"
 
-#define AVTAB_HASH(keyp) \
+#define AVTAB_HASH(keyp,mask)			\
 ((keyp->target_class + \
  (keyp->target_type << 2) + \
  (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
+ mask)
 
 static struct kmem_cache *avtab_node_cachep;
 

@@ -62,7 +61,7 @@
 	if (!h)
 		return -EINVAL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key,h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {

@@ -102,7 +101,7 @@
 
 	if (!h)
 		return NULL;
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {

@@ -135,7 +134,7 @@
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&

@@ -170,7 +169,7 @@
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&

@@ -228,7 +227,7 @@
 	if (!h || !h->htable)
 		return;
 
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		while (cur != NULL) {
 			temp = cur;

@@ -237,21 +236,48 @@
 		}
 		h->htable[i] = NULL;
 	}
-	vfree(h->htable);
+	kfree(h->htable);
 	h->htable = NULL;
+	h->nslot = 0;
+	h->mask = 0;
 }
 
-
 int avtab_init(struct avtab *h)
 {
+	h->htable = NULL;
+	h->nel = 0;
+	return 0;
+}
+
+int avtab_alloc(struct avtab *h, int nrules) {
 	int i;
+	u16 mask;
+	u32 shift = 0;
+	u32 work = nrules;
+	u32 nslot;
+	
+	while(work) {
+		work  = work>>1;
+		shift++;
+	}	
+	if (shift > 2) {
+		shift = shift - 2;
+	}
+	nslot = 1 << shift;
+	if (nslot > MAX_AVTAB_SIZE) {
+		nslot = MAX_AVTAB_SIZE;
+	}
+	mask = nslot - 1;
 
-	h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
+	h->htable = kmalloc(sizeof(*(h->htable)) * nslot, GFP_KERNEL);
 	if (!h->htable)
 		return -ENOMEM;
-	for (i = 0; i < AVTAB_SIZE; i++)
+	for (i = 0; i < nslot; i++)
 		h->htable[i] = NULL;
 	h->nel = 0;
+	h->nslot = nslot;
+	h->mask = mask;	
+	printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated. Num of rules:%d\n", h->nslot, nrules);
 	return 0;
 }
 

@@ -262,7 +288,7 @@
 
 	slots_used = 0;
 	max_chain_len = 0;
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		if (cur) {
 			slots_used++;

@@ -278,7 +304,7 @@
 	}
 
 	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
-	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
+	       "chain length %d\n", tag, h->nel, slots_used, h->nslot,
 	       max_chain_len);
 }
 

@@ -419,6 +445,13 @@
 		rc = -EINVAL;
 		goto bad;
 	}
+
+	rc = avtab_alloc(a, nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto bad;
+	}
+
 	for (i = 0; i < nel; i++) {
 		rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
 		if (rc) {

diff -ur security/selinux.notuning/ss/avtab.h security/selinux/ss/avtab.h

selinux/ss/avtab.h renamed from selinux.notuning/ss/avtab.h +8 -5

@@ -50,9 +50,13 @@
 struct avtab {
 	struct avtab_node **htable;
 	u32 nel;	/* number of elements */
+	u32 nslot;      /* number of hash slots */
+	u16 mask;       /* mask to compute hash func */
+
 };
 
 int avtab_init(struct avtab *);
+int avtab_alloc(struct avtab *, int);
 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *k);
 void avtab_destroy(struct avtab *h);
 void avtab_hash_eval(struct avtab *h, char *tag);

@@ -74,11 +78,10 @@
 void avtab_cache_init(void);
 void avtab_cache_destroy(void);
 
-#define AVTAB_HASH_BITS 15
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
-
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS
+#define MAX_AVTAB_HASH_BITS 13
+#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
+#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
+#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
 
 #endif	/* _SS_AVTAB_H_ */
 

diff -ur security/selinux.notuning/ss/conditional.c security/selinux/ss/conditional.c

selinux/ss/conditional.c renamed from selinux.notuning/ss/conditional.c +6 -0

@@ -455,6 +455,12 @@
 		return -1;
 
 	len = le32_to_cpu(buf[0]);
+	
+	rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto err;
+	}
 
 	for (i = 0; i < len; i++) {
 		node = kzalloc(sizeof(struct cond_node), GFP_KERNEL);

diff -ur security/selinux.notuning/ss/policydb.c security/selinux/ss/policydb.c

selinux/ss/policydb.c renamed from selinux.notuning/ss/policydb.c +3 -6

@@ -172,22 +172,19 @@
 
 	rc = avtab_init(&p->te_avtab);
 	if (rc)
-		goto out_free_symtab;
+		goto out_free_symtab;	
 
 	rc = roles_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 	rc = cond_policydb_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 out:
 	return rc;
 
-out_free_avtab:
-	avtab_destroy(&p->te_avtab);
-
 out_free_symtab:
 	for (i = 0; i < SYM_NUM; i++)
 		hashtab_destroy(p->symtab[i].table);

Regards,

On Tue, 2007-08-21 at 13:29 +0900, Yuichi Nakamura wrote:

The divergence in times between strict/large policy vs. targeted/small policy seems curious.

Is it because targeted/small policy makes more use of type attributes, making the nested ebitmap_for_each_bit loops much longer?

We likely should look at optimizing the ebitmap code, or replacing it with the native kernel bitmaps (include/linux/bitmap.h, lib/bitmap.c). For example, ebitmap_next could possibly use find_next_bit().

Quoted 4 lines

Next is a patch.

Signed-off-by Yuichi Nakamura <[email protected]>

Looks ok, but a few coding style issues. Run ./scripts/checkpatch.pl on it and fix all issues please. And make it apply with patch -p1 (and use diffstat -p1 to generate the diffstat).

Quoted 240 lines

Quoted 1 line

----

 avtab.c       |   61 ++++++++++++++++++++++++++++++++++++++++++++--------------
 avtab.h       |   13 +++++++-----
 conditional.c |    6 +++++
 policydb.c    |    9 ++------
 4 files changed, 64 insertions(+), 25 deletions(-)

diff -ur security/selinux.notuning/ss/avtab.c security/selinux/ss/avtab.c

selinux/ss/avtab.c renamed from selinux.notuning/ss/avtab.c +47 -14

@@ -16,17 +16,16 @@
 
 #include <linux/kernel.h>
 #include <linux/slab.h>
-#include <linux/vmalloc.h>
 #include <linux/errno.h>
 
 #include "avtab.h"
 #include "policydb.h"
 
-#define AVTAB_HASH(keyp) \
+#define AVTAB_HASH(keyp,mask)			\
 ((keyp->target_class + \
  (keyp->target_type << 2) + \
  (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
+ mask)
 
 static struct kmem_cache *avtab_node_cachep;
 

@@ -62,7 +61,7 @@
 	if (!h)
 		return -EINVAL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key,h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {

@@ -102,7 +101,7 @@
 
 	if (!h)
 		return NULL;
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {

@@ -135,7 +134,7 @@
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&

@@ -170,7 +169,7 @@
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&

@@ -228,7 +227,7 @@
 	if (!h || !h->htable)
 		return;
 
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		while (cur != NULL) {
 			temp = cur;

@@ -237,21 +236,48 @@
 		}
 		h->htable[i] = NULL;
 	}
-	vfree(h->htable);
+	kfree(h->htable);
 	h->htable = NULL;
+	h->nslot = 0;
+	h->mask = 0;
 }
 
-
 int avtab_init(struct avtab *h)
 {
+	h->htable = NULL;
+	h->nel = 0;
+	return 0;
+}
+
+int avtab_alloc(struct avtab *h, int nrules) {
 	int i;
+	u16 mask;
+	u32 shift = 0;
+	u32 work = nrules;
+	u32 nslot;
+	
+	while(work) {
+		work  = work>>1;
+		shift++;
+	}	
+	if (shift > 2) {
+		shift = shift - 2;
+	}
+	nslot = 1 << shift;
+	if (nslot > MAX_AVTAB_SIZE) {
+		nslot = MAX_AVTAB_SIZE;
+	}
+	mask = nslot - 1;
 
-	h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
+	h->htable = kmalloc(sizeof(*(h->htable)) * nslot, GFP_KERNEL);
 	if (!h->htable)
 		return -ENOMEM;
-	for (i = 0; i < AVTAB_SIZE; i++)
+	for (i = 0; i < nslot; i++)
 		h->htable[i] = NULL;
 	h->nel = 0;
+	h->nslot = nslot;
+	h->mask = mask;	
+	printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated. Num of rules:%d\n", h->nslot, nrules);
 	return 0;
 }
 

@@ -262,7 +288,7 @@
 
 	slots_used = 0;
 	max_chain_len = 0;
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		if (cur) {
 			slots_used++;

@@ -278,7 +304,7 @@
 	}
 
 	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
-	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
+	       "chain length %d\n", tag, h->nel, slots_used, h->nslot,
 	       max_chain_len);
 }
 

@@ -419,6 +445,13 @@
 		rc = -EINVAL;
 		goto bad;
 	}
+
+	rc = avtab_alloc(a, nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto bad;
+	}
+
 	for (i = 0; i < nel; i++) {
 		rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
 		if (rc) {

diff -ur security/selinux.notuning/ss/avtab.h security/selinux/ss/avtab.h

selinux/ss/avtab.h renamed from selinux.notuning/ss/avtab.h +8 -5

@@ -50,9 +50,13 @@
 struct avtab {
 	struct avtab_node **htable;
 	u32 nel;	/* number of elements */
+	u32 nslot;      /* number of hash slots */
+	u16 mask;       /* mask to compute hash func */
+
 };
 
 int avtab_init(struct avtab *);
+int avtab_alloc(struct avtab *, int);
 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *k);
 void avtab_destroy(struct avtab *h);
 void avtab_hash_eval(struct avtab *h, char *tag);

@@ -74,11 +78,10 @@
 void avtab_cache_init(void);
 void avtab_cache_destroy(void);
 
-#define AVTAB_HASH_BITS 15
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
-
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS
+#define MAX_AVTAB_HASH_BITS 13
+#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
+#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
+#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
 
 #endif	/* _SS_AVTAB_H_ */
 

diff -ur security/selinux.notuning/ss/conditional.c security/selinux/ss/conditional.c

selinux/ss/conditional.c renamed from selinux.notuning/ss/conditional.c +6 -0

@@ -455,6 +455,12 @@
 		return -1;
 
 	len = le32_to_cpu(buf[0]);
+	
+	rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto err;
+	}
 
 	for (i = 0; i < len; i++) {
 		node = kzalloc(sizeof(struct cond_node), GFP_KERNEL);

diff -ur security/selinux.notuning/ss/policydb.c security/selinux/ss/policydb.c

selinux/ss/policydb.c renamed from selinux.notuning/ss/policydb.c +3 -6

@@ -172,22 +172,19 @@
 
 	rc = avtab_init(&p->te_avtab);
 	if (rc)
-		goto out_free_symtab;
+		goto out_free_symtab;	
 
 	rc = roles_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 	rc = cond_policydb_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 out:
 	return rc;
 
-out_free_avtab:
-	avtab_destroy(&p->te_avtab);
-
 out_free_symtab:
 	for (i = 0; i < SYM_NUM; i++)
 		hashtab_destroy(p->symtab[i].table);

Quoted 1 line

Regards,

Signature · 8 lines

Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to [email protected] with
the words "unsubscribe selinux" without quotes as the message.

We likely should look at optimizing the ebitmap code, or replacing it with the native kernel bitmaps (include/linux/bitmap.h, lib/bitmap.c). For example, ebitmap_next could possibly use find_next_bit().

Quoted 3 lines · Stephen Smalley

We likely should look at optimizing the ebitmap code, or replacing it with the native kernel bitmaps (include/linux/bitmap.h, lib/bitmap.c). For example, ebitmap_next could possibly use find_next_bit().

[Removed the busybox list because I'm sure they don't care]

Would the fact that the MLS category bitmaps grow to 1024 bits be a concern with using a single contiguous bitmap instead of the sparse bitmap the ebitmap currently uses? Granted, in the worst case of c0.c1023 the kernel bitmap would most certainly be better but I wonder what the common case is (and if the MLS compartments even factor into the discussion) and which type is better suited to handle this case.

Quoted 5 lines · Paul Moore

Quoted 3 lines · Stephen Smalley

We likely should look at optimizing the ebitmap code, or replacing it with the native kernel bitmaps (include/linux/bitmap.h, lib/bitmap.c). For example, ebitmap_next could possibly use find_next_bit().

Quoted 8 lines

[Removed the busybox list because I'm sure they don't care]

Would the fact that the MLS category bitmaps grow to 1024 bits be a concern with using a single contiguous bitmap instead of the sparse bitmap the ebitmap currently uses? Granted, in the worst case of c0.c1023 the kernel bitmap would most certainly be better but I wonder what the common case is (and if the MLS compartments even factor into the discussion) and which type is better suited to handle this case.

Even if we retain the ebitmap type as a sparse bitmap, I think we can do some optimization of its internals, possibly leveraging things like find_next_bit(), to speed up the loops that were introduced when we optimized the avtab memory layout by pushing attributes down into the kernel policy (policy.20).

Trying Yuichi's simple instrumentation of security_compute_av, I see a huge difference in security_compute_av times between policy.19 and policy.20. We knew it would slow security_compute_av down (standard tradeoff between runtime performance and memory use), but the thinking at the time was that it wouldn't matter because of the AVC. But we do have to bound our worst case latency.

Quoted 19 lines · Stephen Smalley

Quoted 4 lines · Paul Moore

Quoted 3 lines · Stephen Smalley

We likely should look at optimizing the ebitmap code, or replacing it with the native kernel bitmaps (include/linux/bitmap.h, lib/bitmap.c). For example, ebitmap_next could possibly use find_next_bit().

Quoted 8 lines

[Removed the busybox list because I'm sure they don't care]

Would the fact that the MLS category bitmaps grow to 1024 bits be a concern with using a single contiguous bitmap instead of the sparse bitmap the ebitmap currently uses? Granted, in the worst case of c0.c1023 the kernel bitmap would most certainly be better but I wonder what the common case is (and if the MLS compartments even factor into the discussion) and which type is better suited to handle this case.

Even if we retain the ebitmap type as a sparse bitmap, I think we can do some optimization of its internals, possibly leveraging things like find_next_bit(), to speed up the loops that were introduced when we optimized the avtab memory layout by pushing attributes down into the kernel policy (policy.20).

Quoted 6 lines

Trying Yuichi's simple instrumentation of security_compute_av, I see a huge difference in security_compute_av times between policy.19 and policy.20. We knew it would slow security_compute_av down (standard tradeoff between runtime performance and memory use), but the thinking at the time was that it wouldn't matter because of the AVC. But we do have to bound our worst case latency.

I understand, I was just slightly concerned about losing the sparse bitmap feature which I have a hunch is beneficial in the MLS compartment case. Although I will readily admit I have no data to support this claim, I just wanted to throw it out as something to consider.

do

    echo > file${I}
    chcon -l s0:c${I} file${I}

done

Quoted 20 lines · Paul Moore

Quoted 19 lines · Stephen Smalley

Quoted 4 lines · Paul Moore

Quoted 3 lines · Stephen Smalley

We likely should look at optimizing the ebitmap code, or replacing it with the native kernel bitmaps (include/linux/bitmap.h, lib/bitmap.c). For example, ebitmap_next could possibly use find_next_bit().

Quoted 8 lines

[Removed the busybox list because I'm sure they don't care]

Would the fact that the MLS category bitmaps grow to 1024 bits be a concern with using a single contiguous bitmap instead of the sparse bitmap the ebitmap currently uses? Granted, in the worst case of c0.c1023 the kernel bitmap would most certainly be better but I wonder what the common case is (and if the MLS compartments even factor into the discussion) and which type is better suited to handle this case.

Even if we retain the ebitmap type as a sparse bitmap, I think we can do some optimization of its internals, possibly leveraging things like find_next_bit(), to speed up the loops that were introduced when we optimized the avtab memory layout by pushing attributes down into the kernel policy (policy.20).

Quoted 8 lines

Quoted 6 lines

Trying Yuichi's simple instrumentation of security_compute_av, I see a huge difference in security_compute_av times between policy.19 and policy.20. We knew it would slow security_compute_av down (standard tradeoff between runtime performance and memory use), but the thinking at the time was that it wouldn't matter because of the AVC. But we do have to bound our worst case latency.

I understand, I was just slightly concerned about losing the sparse bitmap feature which I have a hunch is beneficial in the MLS compartment case. Although I will readily admit I have no data to support this claim, I just wanted to throw it out as something to consider.

I think the sparse bitmap feature is also useful to skip unnecessary scan on the ebitmap, so these features should be used together.

The current version of ebitmap contains a 64-bit length bitmap. I have a concern to apply the standard bitops, and memory usage.

The one is a difference in the type of variable. find_next_bit() requires the bitmap defined as unsigned long array, but ebitmap uses a u64 value as a bitmap, so we cannot apply it as is.

The other is memory usage. The ebitmap_node is allocated by kzalloc(). However, sizeof(ebitmap_node) is 16-byte in 32bit arch, although the minimun unit of kmalloc() is 32 byte.

In 32-bit arch, map should be defined as 'unsigned long map[6]' to apply the standard bitops and to maximun memory usage.

Thanks,

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

Quoted 3 lines · KaiGai Kohei

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

In addition to the code changes to ebitmap_netlbl_{import,export}() you should probably either remove, or preferably update, the comment block in the body of the functions.

Quoted 8 lines · Paul Moore

Quoted 3 lines · KaiGai Kohei

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

In addition to the code changes to ebitmap_netlbl_{import,export}() you should probably either remove, or preferably update, the comment block in the body of the functions.

I replaced the comment block as follows:

/* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
* however, it is not always compatible with an array of unsigned long
* in ebitmap_node.
* In addition, you should pay attention the following implementation
* assumes unsigned long has a width equal with or less than 64-bit. */

BTW, is there any wrapper to copy an array of u64 to/from architecture specific unsigned long? If so, it will help implement ebitmap_netlbl_{import|export}() and ebitmap_read() more simply.

Quoted 5 lines · KaiGai Kohei

Quoted 4 lines · Paul Moore

Quoted 3 lines · KaiGai Kohei

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

Quoted 3 lines

BTW, is there any wrapper to copy an array of u64 to/from architecture specific unsigned long? If so, it will help implement ebitmap_netlbl_{import|export}() and ebitmap_read() more simply.

Might want to ask on linux-kernel. More generally, it might be a good idea to cc linux-kernel on your next posting of the patch to get wider review of how you are using the native linux bitmap support.

The patch looks very promising, although a detailed review and testing might take a little bit.

Quoted 8 lines · Paul Moore

Quoted 3 lines · KaiGai Kohei

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

In addition to the code changes to ebitmap_netlbl_{import,export}() you should probably either remove, or preferably update, the comment block in the body of the functions.

I replaced the comment block as follows:

/* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
* however, it is not always compatible with an array of unsigned long
* in ebitmap_node.
* In addition, you should pay attention the following implementation
* assumes unsigned long has a width equal with or less than 64-bit. */

BTW, is there any wrapper to copy an array of u64 to/from architecture specific unsigned long? If so, it will help implement ebitmap_netlbl_{import|export}() and ebitmap_read() more simply.

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

Real-time responsibility is a significant issue for embedded Linux people. This patch also reduce amount of busy loop in the kernel, so it can improve real-time responsibility.

I added ebitmap_for_each_positive_bit() macro not to walk on any native bit within ebitmap, and applies it on
- context_struct_compute_av()
- security_get_user_sids()
- mls_context_isvalid()

ebitmap_node was redefined as follows:

   #define EBITMAP_UNIT_NUMS      \
         ((32 - sizeof(void *) - sizeof(u32)) / sizeof(unsigned long))
   struct ebitmap_node {
       struct ebitmap_node *next;
       unsigned long maps[EBITMAP_UNIT_NUMS];
       u32 startbit;
   };

"u64 map" is replaced by an array of "unsigned long". It enables to apply standard bit operations. In addition, length of the array is determind to fit 32-bytes, the minimum size of kmalloc().

The result of benchmarks seems to me fine.

selinux-2.6 selinux-2.6-ebitmap

AVG:   22.763 [s]          8.750 [s]
STD:    0.265              0.019
------------------------------------------
1st:   22.558 [s]          8.786 [s]
2nd:   22.458 [s]          8.750 [s]
3rd:   22.478 [s]          8.754 [s]
4th:   22.724 [s]          8.745 [s]
5th:   22.918 [s]          8.748 [s]
6th:   22.905 [s]          8.764 [s]
7th:   23.238 [s]          8.726 [s]
8th:   22.822 [s]          8.729 [s]

NOTE: We used the following operatins as a test case.
No need to say, it is a corner case to highlight.
[root@saba ~]# id -Z root:system_r:unconfined_t:SystemLow-SystemHigh [root@saba ~]# cd /dev/shm
[root@saba shm]# for I in seq 1 640

Quoted 4 lines

do

    echo > file${I}
    chcon -l s0:c${I} file${I}

done

[root@saba shm]# ~kaigai/manyfiles 800 file*

I also attached "manyfiles.c" to reproduce them.

In addition, we could not make sure a statistical difference in the AVC-hits case.

Thanks,

The patch looks good overall - a couple minor comments below. Paul, can you test the netlabel import/export functionality?

Quoted 54 lines · KaiGai Kohei

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

Real-time responsibility is a significant issue for embedded Linux people. This patch also reduce amount of busy loop in the kernel, so it can improve real-time responsibility.

I added ebitmap_for_each_positive_bit() macro not to walk on any native bit within ebitmap, and applies it on
- context_struct_compute_av()
- security_get_user_sids()
- mls_context_isvalid()

ebitmap_node was redefined as follows:

   #define EBITMAP_UNIT_NUMS      \
         ((32 - sizeof(void *) - sizeof(u32)) / sizeof(unsigned long))
   struct ebitmap_node {
       struct ebitmap_node *next;
       unsigned long maps[EBITMAP_UNIT_NUMS];
       u32 startbit;
   };

"u64 map" is replaced by an array of "unsigned long". It enables to apply standard bit operations. In addition, length of the array is determind to fit 32-bytes, the minimum size of kmalloc().

The result of benchmarks seems to me fine.

selinux-2.6 selinux-2.6-ebitmap

AVG:   22.763 [s]          8.750 [s]
STD:    0.265              0.019
------------------------------------------
1st:   22.558 [s]          8.786 [s]
2nd:   22.458 [s]          8.750 [s]
3rd:   22.478 [s]          8.754 [s]
4th:   22.724 [s]          8.745 [s]
5th:   22.918 [s]          8.748 [s]
6th:   22.905 [s]          8.764 [s]
7th:   23.238 [s]          8.726 [s]
8th:   22.822 [s]          8.729 [s]

NOTE: We used the following operatins as a test case.
No need to say, it is a corner case to highlight.
[root@saba ~]# id -Z root:system_r:unconfined_t:SystemLow-SystemHigh [root@saba ~]# cd /dev/shm
[root@saba shm]# for I in seq 1 640

Quoted 4 lines

do

    echo > file${I}
    chcon -l s0:c${I} file${I}

done

[root@saba shm]# ~kaigai/manyfiles 800 file*

Quoted 6 lines

I also attached "manyfiles.c" to reproduce them.

In addition, we could not make sure a statistical difference in the AVC-hits case.

Thanks,

The patch looks good overall - a couple minor comments below. Paul, can you test the netlabel import/export functionality?

I was wondering whether it might be useful to also introduce a new policy version with an updated ebitmap representation in the policy format that would be closer to the kernel native representation, although we'd still need to be able to read the old formats for backward compatibility.

If/when we introduce support for reading back the currently loaded policy image from the kernel via a selinuxfs node for use by tools, we'll need conversion code to map the kernel representation back to the policy format. libsepol has an ebitmap_write() function to generate a linear policy format representation from an in-memory policydb, which could be ported to the kernel (it used to be there too, actually, but was expunged because we didn't need it in the kernel code at the time), but naturally it only deals with the current representation.

security/selinux/ss/ebitmap.c +8 -4

index ce492a6..de9ef55 100644
@@ -328,85 +341,84 @@ int ebitmap_read(struct ebitmap *e, void *fp)
 	if (rc < 0)
 		goto out;
 
-	mapsize = le32_to_cpu(buf[0]);
+	mapunit = le32_to_cpu(buf[0]);
 	e->highbit = le32_to_cpu(buf[1]);
 	count = le32_to_cpu(buf[2]);
 
-	if (mapsize != MAPSIZE) {
+	/* round up e->highbit */
+	e->highbit += EBITMAP_SIZE - 1;
+	e->highbit -= (e->highbit % EBITMAP_SIZE);
+
+	if (mapunit != sizeof(u64) * 8) {
 		printk(KERN_ERR "security: ebitmap: map size %u does not "
-		       "match my size %Zd (high bit was %d)\n", mapsize,
-		       MAPSIZE, e->highbit);
+		       "match my size %Zd (high bit was %d)\n",
+		       mapunit, sizeof(u64) * 8, e->highbit);
 

Here you will display the modified highbit value rather than the one that was actually in the policy image. I think you can just move the check before mutating the highbit.

security/selinux/ss/ebitmap.c +0 -5

 		goto bad;
 	}
 	if (!e->highbit) {
 		e->node = NULL;
 		goto ok;
 	}
-	if (e->highbit & (MAPSIZE - 1)) {
-		printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
-		       "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
-		goto bad;
-	}

Not sure why you'd drop this sanity check. As before, it would need to happen before mutating the highbit.

security/selinux/ss/ebitmap.c +4 -0

+		} else if (startbit <= n->startbit) {
+			printk(KERN_ERR "security: ebitmap: start bit %d"
+			       " comes after start bit %d\n",
+			       startbit, n->startbit);

Need to bail out here with an appropriate rc value.

security/selinux/ss/ebitmap.h +2 -0

index 1270e34..fc0ce05 100644
@@ -41,6 +42,19 @@ static inline unsigned int ebitmap_start(struct ebitmap *e,
 	return ebitmap_startbit(e);
 }
 
+static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
+						  struct ebitmap_node **n)
 
 I suspect we could just make these all "static" (not explicitly inline)

and let the compiler do the right thing. That seemed to be the trend upstream and guidance from arjan.

<snip>
static inline int ebitmap_node_get_bit(struct ebitmap_node * n,

security/selinux/ss/ebitmap.h +2 -1

 				       unsigned int bit)
 {
-	if (n->map & (MAPBIT << (bit - n->startbit)))
+	unsigned int ofs =   (bit - n->startbit) % EBITMAP_UNIT_SIZE;
+	unsigned int index = (bit - n->startbit) / EBITMAP_UNIT_SIZE;

Possibly the computation of (ofs,index) should be a common macro since it is done in several of these functions.

security/selinux/ss/ebitmap.h +2 -0

+	
+	if (index < EBITMAP_UNIT_NUMS && (n->maps[index] & (EBITMAP_BIT << ofs)))

Possibly BUG_ON(index >= EBITMAP_UNIT_NUMS) instead of silently returning 0 in that case?

security/selinux/ss/ebitmap.h +4 -0

+#define ebitmap_for_each_bit(e, n, bit)			\
+	for (bit = ebitmap_start(e, &n);		\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next(&n, bit))		\

Ideally we'd kill off all uses of ebitmap_for_each_bit and use the _positive_ form in all cases, although I see that would require some changes to the mls logic.

security/selinux/ss/ebitmap.h +4 -0

+#define ebitmap_for_each_positive_bit(e, n, bit)	\
+	for (bit = ebitmap_start_positive(e, &n);	\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next_positive(e, &n, bit))	\
 
 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);

security/selinux/ss/mls.c +2 -11

index 4a8bab2..846314f 100644
@@ -190,17 +190,17 @@ int mls_context_isvalid(struct policydb *p, struct context *c)
 		if (!levdatum)
 			return 0;
 
-		ebitmap_for_each_bit(&c->range.level[l].cat, node, i) {
-			if (ebitmap_node_get_bit(node, i)) {
-				if (i > p->p_cats.nprim)
-					return 0;
-				if (!ebitmap_get_bit(&levdatum->level->cat, i))
-					/*
-					 * Category may not be associated with
-					 * sensitivity in low level.
-					 */
-					return 0;
-			}
+		ebitmap_for_each_positive_bit(&c->range.level[l].cat, node, i) {
+			// BUG_ON(!ebitmap_node_get_bit(node, i));
 

Drop these BUG_ON's out, or uncomment them if you want to keep them for now for testing purposes.

Quoted 55 lines · Stephen Smalley

Quoted 54 lines · KaiGai Kohei

The attached patch applies the standard bitmap operations for the iteration macro of ebitmap, and enables to improve the performance in AVC-misses case.

Real-time responsibility is a significant issue for embedded Linux people. This patch also reduce amount of busy loop in the kernel, so it can improve real-time responsibility.

I added ebitmap_for_each_positive_bit() macro not to walk on any native bit within ebitmap, and applies it on
- context_struct_compute_av()
- security_get_user_sids()
- mls_context_isvalid()

ebitmap_node was redefined as follows:

   #define EBITMAP_UNIT_NUMS      \
         ((32 - sizeof(void *) - sizeof(u32)) / sizeof(unsigned long))
   struct ebitmap_node {
       struct ebitmap_node *next;
       unsigned long maps[EBITMAP_UNIT_NUMS];
       u32 startbit;
   };

"u64 map" is replaced by an array of "unsigned long". It enables to apply standard bit operations. In addition, length of the array is determind to fit 32-bytes, the minimum size of kmalloc().

The result of benchmarks seems to me fine.

selinux-2.6 selinux-2.6-ebitmap

AVG:   22.763 [s]          8.750 [s]
STD:    0.265              0.019
------------------------------------------
1st:   22.558 [s]          8.786 [s]
2nd:   22.458 [s]          8.750 [s]
3rd:   22.478 [s]          8.754 [s]
4th:   22.724 [s]          8.745 [s]
5th:   22.918 [s]          8.748 [s]
6th:   22.905 [s]          8.764 [s]
7th:   23.238 [s]          8.726 [s]
8th:   22.822 [s]          8.729 [s]

NOTE: We used the following operatins as a test case.
No need to say, it is a corner case to highlight.
[root@saba ~]# id -Z root:system_r:unconfined_t:SystemLow-SystemHigh [root@saba ~]# cd /dev/shm
[root@saba shm]# for I in seq 1 640

Quoted 4 lines

do

    echo > file${I}
    chcon -l s0:c${I} file${I}

done

[root@saba shm]# ~kaigai/manyfiles 800 file*

Quoted 6 lines

Quoted 6 lines

I also attached "manyfiles.c" to reproduce them.

In addition, we could not make sure a statistical difference in the AVC-hits case.

Thanks,

Stephen, Thanks for your comments.

The attached second patch is revised in several points.
- comment blocks in ebitmap_netlbl_(inport|export) are rewritten as I mentioned before.
- rest of codes using ebitmap_for_each_bit() were replaced by _positive_ version. I had to modify logic in ss/mls.c a bit.
- applied your comment as follows:

Quoted 8 lines

The patch looks good overall - a couple minor comments below. Paul, can you test the netlabel import/export functionality?

I was wondering whether it might be useful to also introduce a new policy version with an updated ebitmap representation in the policy format that would be closer to the kernel native representation, although we'd still need to be able to read the old formats for backward compatibility.

I don't think a new policy format is necessary, because the width of unsigned long depends on its architecture, although selinux-policy is a "noarch" package.
The kernel should translate it into another format easier to handle on run-time, if necessary.

Quoted 34 lines

If/when we introduce support for reading back the currently loaded policy image from the kernel via a selinuxfs node for use by tools, we'll need conversion code to map the kernel representation back to the policy format. libsepol has an ebitmap_write() function to generate a linear policy format representation from an in-memory policydb, which could be ported to the kernel (it used to be there too, actually, but was expunged because we didn't need it in the kernel code at the time), but naturally it only deals with the current representation.

security/selinux/ss/ebitmap.c +8 -4

index ce492a6..de9ef55 100644
@@ -328,85 +341,84 @@ int ebitmap_read(struct ebitmap *e, void *fp)
 	if (rc < 0)
 		goto out;
 
-	mapsize = le32_to_cpu(buf[0]);
+	mapunit = le32_to_cpu(buf[0]);
 	e->highbit = le32_to_cpu(buf[1]);
 	count = le32_to_cpu(buf[2]);
 
-	if (mapsize != MAPSIZE) {
+	/* round up e->highbit */
+	e->highbit += EBITMAP_SIZE - 1;
+	e->highbit -= (e->highbit % EBITMAP_SIZE);
+
+	if (mapunit != sizeof(u64) * 8) {
 		printk(KERN_ERR "security: ebitmap: map size %u does not "
-		       "match my size %Zd (high bit was %d)\n", mapsize,
-		       MAPSIZE, e->highbit);
+		       "match my size %Zd (high bit was %d)\n",
+		       mapunit, sizeof(u64) * 8, e->highbit);
 

Quoted 3 lines

Here you will display the modified highbit value rather than the one that was actually in the policy image. I think you can just move the check before mutating the highbit.

I moved it in front of rounding up e->highbit.

Quoted 12 lines

security/selinux/ss/ebitmap.c +0 -5

 		goto bad;
 	}
 	if (!e->highbit) {
 		e->node = NULL;
 		goto ok;
 	}
-	if (e->highbit & (MAPSIZE - 1)) {
-		printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
-		       "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
-		goto bad;
-	}

Quoted 1 line

Not sure why you'd drop this sanity check. As before, it would need to happen before mutating the highbit.

The reason why I dropped this sanity check is to avoid redundant one, because e->highbit is already rounded up to the align of EBITMAP_SIZE. The above condition is not always false.

Quoted 6 lines

security/selinux/ss/ebitmap.c +4 -0

+		} else if (startbit <= n->startbit) {
+			printk(KERN_ERR "security: ebitmap: start bit %d"
+			       " comes after start bit %d\n",
+			       startbit, n->startbit);

Need to bail out here with an appropriate rc value.

I added "goto bad;" at the point. It returns -EINVAL.

Quoted 12 lines

security/selinux/ss/ebitmap.h +2 -0

index 1270e34..fc0ce05 100644
@@ -41,6 +42,19 @@ static inline unsigned int ebitmap_start(struct ebitmap *e,
 	return ebitmap_startbit(e);
 }
 
+static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
+						  struct ebitmap_node **n)
 
 I suspect we could just make these all "static" (not explicitly inline)

Quoted 2 lines

and let the compiler do the right thing. That seemed to be the trend upstream and guidance from arjan.

How should we do the explicitly inlined static functions used as stubs?

For example, ebitmap_netlbl_export() when NetLabel is not enabled is defined as explicitly inlined function which always returns -ENOMEM, however, these are also declarations of function when NetLabel is enabled.

Quoted 10 lines

<snip>
static inline int ebitmap_node_get_bit(struct ebitmap_node * n,

security/selinux/ss/ebitmap.h +2 -1

 				       unsigned int bit)
 {
-	if (n->map & (MAPBIT << (bit - n->startbit)))
+	unsigned int ofs =   (bit - n->startbit) % EBITMAP_UNIT_SIZE;
+	unsigned int index = (bit - n->startbit) / EBITMAP_UNIT_SIZE;

Possibly the computation of (ofs,index) should be a common macro since it is done in several of these functions.

I added EBITMAP_NODE_INDEX(node,bit) and EBITMAP_NODE_OFFSET(node,bit) to compute them.

Quoted 4 lines

security/selinux/ss/ebitmap.h +2 -0

+	
+	if (index < EBITMAP_UNIT_NUMS && (n->maps[index] & (EBITMAP_BIT << ofs)))

Possibly BUG_ON(index >= EBITMAP_UNIT_NUMS) instead of silently returning 0 in that case?

It is good idea indeed.
All caller of ebitmap_node_get_bit() always confirms 'bit' is in the range of ebitmap_node. If the index overs EBITMAP_UNIT_NUMS, it is a bug surely.

Quoted 5 lines

security/selinux/ss/ebitmap.h +4 -0

+#define ebitmap_for_each_bit(e, n, bit)			\
+	for (bit = ebitmap_start(e, &n);		\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next(&n, bit))		\

Quoted 2 lines

Ideally we'd kill off all uses of ebitmap_for_each_bit and use the _positive_ form in all cases, although I see that would require some changes to the mls logic.

ebitmap_start, ebitmap_next and ebitmap_for_each_bit are dropped. The rest of codes using ebitmap_for_each_bit(), in ss/mls.c, are also replaced with _positive_ version.

Quoted 29 lines

security/selinux/ss/ebitmap.h +4 -0

+#define ebitmap_for_each_positive_bit(e, n, bit)	\
+	for (bit = ebitmap_start_positive(e, &n);	\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next_positive(e, &n, bit))	\
 
 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);

security/selinux/ss/mls.c +2 -11

index 4a8bab2..846314f 100644
@@ -190,17 +190,17 @@ int mls_context_isvalid(struct policydb *p, struct context *c)
 		if (!levdatum)
 			return 0;
 
-		ebitmap_for_each_bit(&c->range.level[l].cat, node, i) {
-			if (ebitmap_node_get_bit(node, i)) {
-				if (i > p->p_cats.nprim)
-					return 0;
-				if (!ebitmap_get_bit(&levdatum->level->cat, i))
-					/*
-					 * Category may not be associated with
-					 * sensitivity in low level.
-					 */
-					return 0;
-			}
+		ebitmap_for_each_positive_bit(&c->range.level[l].cat, node, i) {
+			// BUG_ON(!ebitmap_node_get_bit(node, i));
 

Quoted 1 line

Drop these BUG_ON's out, or uncomment them if you want to keep them for now for testing purposes.

I dropped the BUG_ON() to confirm each bit is actually positive.

Quoted 8 lines

Quoted 6 lines

(quoted diff) +2 -0

+static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
+						  struct ebitmap_node **n)

I suspect we could just make these all "static" (not explicitly inline) and let the compiler do the right thing. That seemed to be the trend upstream and guidance from arjan.

How should we do the explicitly inlined static functions used as stubs?

Quoted 3 lines

For example, ebitmap_netlbl_export() when NetLabel is not enabled is defined as explicitly inlined function which always returns -ENOMEM, however, these are also declarations of function when NetLabel is enabled.

Ah, never mind - as these are defined in the header file, they can stay static inline.

Quoted 5 lines

Quoted 5 lines

(quoted diff) +4 -0

+#define ebitmap_for_each_bit(e, n, bit)			\
+	for (bit = ebitmap_start(e, &n);		\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next(&n, bit))		\

Quoted 5 lines

Quoted 2 lines

Ideally we'd kill off all uses of ebitmap_for_each_bit and use the _positive_ form in all cases, although I see that would require some changes to the mls logic.

ebitmap_start, ebitmap_next and ebitmap_for_each_bit are dropped. The rest of codes using ebitmap_for_each_bit(), in ss/mls.c, are also replaced with _positive_ version.

Looks like you've left ebitmap_for_each_bit defined even though no longer used in ebitmap.h.

Ok, looks reasonable. Please run it through ./scripts/checkpatch.pl and fix up the minor issues it reports, then post a clean message with a suitable description and the patch inline.

Quoted 3 lines

Ok, looks reasonable. Please run it through ./scripts/checkpatch.pl and fix up the minor issues it reports, then post a clean message with a suitable description and the patch inline.

What is your stance about warnings for "line over 80 characters" ? To resolve all of them makes harder to read source code, so I'm ignoring them in the attached version.

- snip -

Quoted 12 lines

Quoted 11 lines

Quoted 6 lines

security/selinux/ss/ebitmap.h +2 -0

+static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
+						  struct ebitmap_node **n)

I suspect we could just make these all "static" (not explicitly inline) and let the compiler do the right thing. That seemed to be the trend upstream and guidance from arjan.

How should we do the explicitly inlined static functions used as stubs?

For example, ebitmap_netlbl_export() when NetLabel is not enabled is defined as explicitly inlined function which always returns -ENOMEM, however, these are also declarations of function when NetLabel is enabled.

Quoted 2 lines

Ah, never mind - as these are defined in the header file, they can stay static inline.

OK. I'll submit a patch to clean up non-stub static inline functions next to this patch.

- snip -

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

(quoted diff) +4 -0

+#define ebitmap_for_each_bit(e, n, bit)			\
+	for (bit = ebitmap_start(e, &n);		\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next(&n, bit))		\

Quoted 8 lines

Quoted 5 lines

Quoted 2 lines

Ideally we'd kill off all uses of ebitmap_for_each_bit and use the _positive_ form in all cases, although I see that would require some changes to the mls logic.

ebitmap_start, ebitmap_next and ebitmap_for_each_bit are dropped. The rest of codes using ebitmap_for_each_bit(), in ss/mls.c, are also replaced with _positive_ version.

Looks like you've left ebitmap_for_each_bit defined even though no longer used in ebitmap.h.

I misses to remove it, so its definition is also removed.

- snip -

Quoted 3 lines

Ok, looks reasonable. Please run it through ./scripts/checkpatch.pl and fix up the minor issues it reports, then post a clean message with a suitable description and the patch inline.

What is your stance about warnings for "line over 80 characters" ? To resolve all of them makes harder to read source code, so I'm ignoring them in the attached version.
Rest of warnings except for them are removed.

Thanks,

Signature · 4 lines

OSS Platform Development Division, NEC
KaiGai Kohei <[email protected]>

Signed-off-by: KaiGai Kohei <[email protected]>

security/selinux/ss/ebitmap.c +140 -123

index ce492a6..3a60186 100644
@@ -10,6 +10,10 @@
  *
  * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
  */
+/*
+ * Updated: KaiGai Kohei <[email protected]>
+ *      Applied standard bit operations to improve bitmap scanning.
+ */
 
 #include <linux/kernel.h>
 #include <linux/slab.h>

@@ -29,7 +33,7 @@ int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
 	n2 = e2->node;
 	while (n1 && n2 &&
 	       (n1->startbit == n2->startbit) &&
-	       (n1->map == n2->map)) {
+	       !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
 		n1 = n1->next;
 		n2 = n2->next;
 	}

@@ -54,7 +58,7 @@ int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
 			return -ENOMEM;
 		}
 		new->startbit = n->startbit;
-		new->map = n->map;
+		memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
 		new->next = NULL;
 		if (prev)
 			prev->next = new;

@@ -84,13 +88,15 @@ int ebitmap_netlbl_export(struct ebitmap *ebmap,
 {
 	struct ebitmap_node *e_iter = ebmap->node;
 	struct netlbl_lsm_secattr_catmap *c_iter;
-	u32 cmap_idx;
+	u32 cmap_idx, cmap_sft;
+	int i;
 
-	/* This function is a much simpler because SELinux's MAPTYPE happens
-	 * to be the same as NetLabel's NETLBL_CATMAP_MAPTYPE, if MAPTYPE is
-	 * changed from a u64 this function will most likely need to be changed
-	 * as well.  It's not ideal but I think the tradeoff in terms of
-	 * neatness and speed is worth it. */
+	/* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
+	 * however, it is not always compatible with an array of unsigned long
+	 * in ebitmap_node.
+	 * In addition, you should pay attention the following implementation
+	 * assumes unsigned long has a width equal with or less than 64-bit.
+	 */
 
 	if (e_iter == NULL) {
 		*catmap = NULL;

@@ -104,19 +110,21 @@ int ebitmap_netlbl_export(struct ebitmap *ebmap,
 	c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1);
 
 	while (e_iter != NULL) {
-		if (e_iter->startbit >=
-		    (c_iter->startbit + NETLBL_CATMAP_SIZE)) {
-			c_iter->next = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
-			if (c_iter->next == NULL)
-				goto netlbl_export_failure;
-			c_iter = c_iter->next;
-			c_iter->startbit = e_iter->startbit &
-				           ~(NETLBL_CATMAP_SIZE - 1);
+		for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
+			unsigned int e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE;
+
+			if (e_startbit >= c_iter->startbit + NETLBL_CATMAP_SIZE) {
+				c_iter->next = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
+				if (c_iter->next == NULL)
+					goto netlbl_export_failure;
+				c_iter = c_iter->next;
+				c_iter->startbit = e_startbit & ~(NETLBL_CATMAP_SIZE - 1);
+			}
+			cmap_idx = (e_startbit - c_iter->startbit) / NETLBL_CATMAP_MAPSIZE;
+			cmap_sft = (e_startbit - c_iter->startbit) % NETLBL_CATMAP_MAPSIZE;
+			c_iter->bitmap[cmap_idx] |= e_iter->maps[cmap_idx] << cmap_sft;
+			e_iter = e_iter->next;
 		}
-		cmap_idx = (e_iter->startbit - c_iter->startbit) /
-			   NETLBL_CATMAP_MAPSIZE;
-		c_iter->bitmap[cmap_idx] = e_iter->map;
-		e_iter = e_iter->next;
 	}
 
 	return 0;

@@ -128,7 +136,7 @@ netlbl_export_failure:
 
 /**
  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
- * @ebmap: the ebitmap to export
+ * @ebmap: the ebitmap to import
  * @catmap: the NetLabel category bitmap
  *
  * Description:

@@ -142,36 +150,45 @@ int ebitmap_netlbl_import(struct ebitmap *ebmap,
 	struct ebitmap_node *e_iter = NULL;
 	struct ebitmap_node *emap_prev = NULL;
 	struct netlbl_lsm_secattr_catmap *c_iter = catmap;
-	u32 c_idx;
+	u32 c_idx, c_pos, e_idx, e_sft;
 
-	/* This function is a much simpler because SELinux's MAPTYPE happens
-	 * to be the same as NetLabel's NETLBL_CATMAP_MAPTYPE, if MAPTYPE is
-	 * changed from a u64 this function will most likely need to be changed
-	 * as well.  It's not ideal but I think the tradeoff in terms of
-	 * neatness and speed is worth it. */
+	/* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
+	 * however, it is not always compatible with an array of unsigned long
+	 * in ebitmap_node.
+	 * In addition, you should pay attention the following implementation
+	 * assumes unsigned long has a width equal with or less than 64-bit.
+	 */
 
 	do {
 		for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) {
-			if (c_iter->bitmap[c_idx] == 0)
+			u64 map = c_iter->bitmap[c_idx];
+
+			if (!map)
 				continue;
 
-			e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
-			if (e_iter == NULL)
-				goto netlbl_import_failure;
-			if (emap_prev == NULL)
-				ebmap->node = e_iter;
-			else
-				emap_prev->next = e_iter;
-			emap_prev = e_iter;
-
-			e_iter->startbit = c_iter->startbit +
-				           NETLBL_CATMAP_MAPSIZE * c_idx;
-			e_iter->map = c_iter->bitmap[c_idx];
+			c_pos = c_iter->startbit + c_idx * NETLBL_CATMAP_MAPSIZE;
+			if (!e_iter || c_pos >= e_iter->startbit + EBITMAP_SIZE) {
+				e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
+				if (!e_iter)
+					goto netlbl_import_failure;
+				e_iter->startbit = c_pos - (c_pos % EBITMAP_SIZE);
+				if (emap_prev == NULL)
+					ebmap->node = e_iter;
+				else
+					emap_prev->next = e_iter;
+				emap_prev = e_iter;
+			}
+			e_idx = (c_pos - e_iter->startbit) / EBITMAP_UNIT_SIZE;
+			e_sft = (c_pos - e_iter->startbit) % EBITMAP_UNIT_SIZE;
+			while (map) {
+				e_iter->maps[e_idx++] |= map & (-1UL);
+				map >>= EBITMAP_UNIT_SIZE;
+			}
 		}
 		c_iter = c_iter->next;
 	} while (c_iter != NULL);
 	if (e_iter != NULL)
-		ebmap->highbit = e_iter->startbit + MAPSIZE;
+		ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
 	else
 		ebitmap_destroy(ebmap);
 

@@ -186,6 +203,7 @@ netlbl_import_failure:
 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 {
 	struct ebitmap_node *n1, *n2;
+	int i;
 
 	if (e1->highbit < e2->highbit)
 		return 0;

@@ -197,8 +215,10 @@ int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 			n1 = n1->next;
 			continue;
 		}
-		if ((n1->map & n2->map) != n2->map)
-			return 0;
+		for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
+			if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
+				return 0;
+		}
 
 		n1 = n1->next;
 		n2 = n2->next;

@@ -219,12 +239,8 @@ int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 
 	n = e->node;
 	while (n && (n->startbit <= bit)) {
-		if ((n->startbit + MAPSIZE) > bit) {
-			if (n->map & (MAPBIT << (bit - n->startbit)))
-				return 1;
-			else
-				return 0;
-		}
+		if ((n->startbit + EBITMAP_SIZE) > bit)
+			return ebitmap_node_get_bit(n, bit);
 		n = n->next;
 	}
 

@@ -238,31 +254,31 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 	prev = NULL;
 	n = e->node;
 	while (n && n->startbit <= bit) {
-		if ((n->startbit + MAPSIZE) > bit) {
+		if ((n->startbit + EBITMAP_SIZE) > bit) {
 			if (value) {
-				n->map |= (MAPBIT << (bit - n->startbit));
+				ebitmap_node_set_bit(n, bit);
 			} else {
-				n->map &= ~(MAPBIT << (bit - n->startbit));
-				if (!n->map) {
-					/* drop this node from the bitmap */
-
-					if (!n->next) {
-						/*
-						 * this was the highest map
-						 * within the bitmap
-						 */
-						if (prev)
-							e->highbit = prev->startbit + MAPSIZE;
-						else
-							e->highbit = 0;
-					}
+				ebitmap_node_clr_bit(n, bit);
+
+				if (find_first_bit(n->maps, EBITMAP_SIZE) < EBITMAP_SIZE)
+					return 0;
+
+				/* drop this node from the bitmap */
+				if (!n->next) {
+					/*
+					 * this was the highest map
+					 * within the bitmap
+					 */
 					if (prev)
-						prev->next = n->next;
+						e->highbit = prev->startbit + EBITMAP_SIZE;
 					else
-						e->node = n->next;
-
-					kfree(n);
+						e->highbit = 0;
 				}
+				if (prev)
+					prev->next = n->next;
+				else
+					e->node = n->next;
+				kfree(n);
 			}
 			return 0;
 		}

@@ -277,12 +293,12 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 	if (!new)
 		return -ENOMEM;
 
-	new->startbit = bit & ~(MAPSIZE - 1);
-	new->map = (MAPBIT << (bit - new->startbit));
+	new->startbit = bit - (bit % EBITMAP_SIZE);
+	ebitmap_node_set_bit(new, bit);
 
 	if (!n)
 		/* this node will be the highest map within the bitmap */
-		e->highbit = new->startbit + MAPSIZE;
+		e->highbit = new->startbit + EBITMAP_SIZE;
 
 	if (prev) {
 		new->next = prev->next;

@@ -316,11 +332,11 @@ void ebitmap_destroy(struct ebitmap *e)
 
 int ebitmap_read(struct ebitmap *e, void *fp)
 {
-	int rc;
-	struct ebitmap_node *n, *l;
+	struct ebitmap_node *n = NULL;
+	u32 mapunit, count, startbit, index;
+	u64 map;
 	__le32 buf[3];
-	u32 mapsize, count, i;
-	__le64 map;
+	int rc, i;
 
 	ebitmap_init(e);
 

@@ -328,85 +344,86 @@ int ebitmap_read(struct ebitmap *e, void *fp)
 	if (rc < 0)
 		goto out;
 
-	mapsize = le32_to_cpu(buf[0]);
+	mapunit = le32_to_cpu(buf[0]);
 	e->highbit = le32_to_cpu(buf[1]);
 	count = le32_to_cpu(buf[2]);
 
-	if (mapsize != MAPSIZE) {
+	if (mapunit != sizeof(u64) * 8) {
 		printk(KERN_ERR "security: ebitmap: map size %u does not "
-		       "match my size %Zd (high bit was %d)\n", mapsize,
-		       MAPSIZE, e->highbit);
+		       "match my size %Zd (high bit was %d)\n",
+		       mapunit, sizeof(u64) * 8, e->highbit);
 		goto bad;
 	}
+
+	/* round up e->highbit */
+	e->highbit += EBITMAP_SIZE - 1;
+	e->highbit -= (e->highbit % EBITMAP_SIZE);
+
 	if (!e->highbit) {
 		e->node = NULL;
 		goto ok;
 	}
-	if (e->highbit & (MAPSIZE - 1)) {
-		printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
-		       "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
-		goto bad;
-	}
-	l = NULL;
+
 	for (i = 0; i < count; i++) {
-		rc = next_entry(buf, fp, sizeof(u32));
+		rc = next_entry(&startbit, fp, sizeof(u32));
 		if (rc < 0) {
 			printk(KERN_ERR "security: ebitmap: truncated map\n");
 			goto bad;
 		}
-		n = kzalloc(sizeof(*n), GFP_KERNEL);
-		if (!n) {
-			printk(KERN_ERR "security: ebitmap: out of memory\n");
-			rc = -ENOMEM;
-			goto bad;
-		}
-
-		n->startbit = le32_to_cpu(buf[0]);
+		startbit = le32_to_cpu(startbit);
 
-		if (n->startbit & (MAPSIZE - 1)) {
+		if (startbit & (mapunit - 1)) {
 			printk(KERN_ERR "security: ebitmap start bit (%d) is "
-			       "not a multiple of the map size (%Zd)\n",
-			       n->startbit, MAPSIZE);
-			goto bad_free;
+			       "not a multiple of the map unit size (%Zd)\n",
+			       startbit, mapunit);
+			goto bad;
 		}
-		if (n->startbit > (e->highbit - MAPSIZE)) {
+		if (startbit > e->highbit - mapunit) {
 			printk(KERN_ERR "security: ebitmap start bit (%d) is "
 			       "beyond the end of the bitmap (%Zd)\n",
-			       n->startbit, (e->highbit - MAPSIZE));
-			goto bad_free;
+			       startbit, (e->highbit - mapunit));
+			goto bad;
+		}
+
+		if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
+			struct ebitmap_node *_n = kzalloc(sizeof(*_n), GFP_KERNEL);
+			if (!_n) {
+				printk(KERN_ERR "security: ebitmap: out of memory\n");
+				rc = -ENOMEM;
+				goto bad;
+			}
+			_n->startbit = startbit - (startbit % EBITMAP_SIZE); /* round down */
+			if (n) {
+				n->next = _n;
+			} else {
+				e->node = _n;
+			}
+			n = _n;
+		} else if (startbit <= n->startbit) {
+			printk(KERN_ERR "security: ebitmap: start bit %d"
+			       " comes after start bit %d\n",
+			       startbit, n->startbit);
+			goto bad;
 		}
+
 		rc = next_entry(&map, fp, sizeof(u64));
 		if (rc < 0) {
 			printk(KERN_ERR "security: ebitmap: truncated map\n");
-			goto bad_free;
+			goto bad;
 		}
-		n->map = le64_to_cpu(map);
+		map = le64_to_cpu(map);
 
-		if (!n->map) {
-			printk(KERN_ERR "security: ebitmap: null map in "
-			       "ebitmap (startbit %d)\n", n->startbit);
-			goto bad_free;
+		index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
+		while (map) {
+			n->maps[index] = map & (-1UL);
+			map = map >> EBITMAP_UNIT_SIZE;
+			index++;
 		}
-		if (l) {
-			if (n->startbit <= l->startbit) {
-				printk(KERN_ERR "security: ebitmap: start "
-				       "bit %d comes after start bit %d\n",
-				       n->startbit, l->startbit);
-				goto bad_free;
-			}
-			l->next = n;
-		} else
-			e->node = n;
-
-		l = n;
 	}
-
 ok:
 	rc = 0;
 out:
 	return rc;
-bad_free:
-	kfree(n);
 bad:
 	if (!rc)
 		rc = -EINVAL;

security/selinux/ss/ebitmap.h +65 -21

index 1270e34..417053e 100644
@@ -16,14 +16,15 @@
 
 #include <net/netlabel.h>
 
-#define MAPTYPE u64			/* portion of bitmap in each node */
-#define MAPSIZE (sizeof(MAPTYPE) * 8)	/* number of bits in node bitmap */
-#define MAPBIT  1ULL			/* a bit in the node bitmap */
+#define EBITMAP_UNIT_NUMS	((32 - sizeof(void *) - sizeof(u32)) / sizeof(unsigned long))
+#define EBITMAP_UNIT_SIZE	BITS_PER_LONG
+#define EBITMAP_SIZE		(EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE)
+#define EBITMAP_BIT		1ULL
 
 struct ebitmap_node {
-	u32 startbit;		/* starting position in the total bitmap */
-	MAPTYPE map;		/* this node's portion of the bitmap */
 	struct ebitmap_node *next;
+	unsigned long maps[EBITMAP_UNIT_NUMS];
+	u32 startbit;
 };
 
 struct ebitmap {

@@ -34,11 +35,17 @@ struct ebitmap {
 #define ebitmap_length(e) ((e)->highbit)
 #define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0)
 
-static inline unsigned int ebitmap_start(struct ebitmap *e,
-					 struct ebitmap_node **n)
+static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
+						  struct ebitmap_node **n)
 {
-	*n = e->node;
-	return ebitmap_startbit(e);
+	unsigned int ofs;
+
+	for (*n = e->node; *n; *n = (*n)->next) {
+		ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
+		if (ofs < EBITMAP_SIZE)
+			return (*n)->startbit + ofs;
+	}
+	return ebitmap_length(e);
 }
 
 static inline void ebitmap_init(struct ebitmap *e)

@@ -46,28 +53,65 @@ static inline void ebitmap_init(struct ebitmap *e)
 	memset(e, 0, sizeof(*e));
 }
 
-static inline unsigned int ebitmap_next(struct ebitmap_node **n,
-					unsigned int bit)
+static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
+						 struct ebitmap_node **n,
+						 unsigned int bit)
 {
-	if ((bit == ((*n)->startbit + MAPSIZE - 1)) &&
-	    (*n)->next) {
-		*n = (*n)->next;
-		return (*n)->startbit;
-	}
+	unsigned int ofs;
+
+	ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1);
+	if (ofs < EBITMAP_SIZE)
+		return ofs + (*n)->startbit;
 
-	return (bit+1);
+	for (*n = (*n)->next; *n; *n = (*n)->next) {
+		ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
+		if (ofs < EBITMAP_SIZE)
+			return ofs + (*n)->startbit;
+	}
+	return ebitmap_length(e);
 }
 
-static inline int ebitmap_node_get_bit(struct ebitmap_node * n,
+#define EBITMAP_NODE_INDEX(node, bit)	\
+	(((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE)
+#define EBITMAP_NODE_OFFSET(node, bit)	\
+	(((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE)
+
+static inline int ebitmap_node_get_bit(struct ebitmap_node *n,
 				       unsigned int bit)
 {
-	if (n->map & (MAPBIT << (bit - n->startbit)))
+	unsigned int index = EBITMAP_NODE_INDEX(n, bit);
+	unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
+
+	BUG_ON(index >= EBITMAP_UNIT_NUMS);
+	if ((n->maps[index] & (EBITMAP_BIT << ofs)))
 		return 1;
 	return 0;
 }
 
-#define ebitmap_for_each_bit(e, n, bit) \
-	for (bit = ebitmap_start(e, &n); bit < ebitmap_length(e); bit = ebitmap_next(&n, bit)) \
+static inline void ebitmap_node_set_bit(struct ebitmap_node *n,
+					unsigned int bit)
+{
+	unsigned int index = EBITMAP_NODE_INDEX(n, bit);
+	unsigned int 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)
+{
+	unsigned int index = EBITMAP_NODE_INDEX(n, bit);
+	unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
+
+	BUG_ON(index >= EBITMAP_UNIT_NUMS);
+	n->maps[index] &= ~(EBITMAP_BIT << ofs);
+}
+
+#define ebitmap_for_each_positive_bit(e, n, bit)	\
+	for (bit = ebitmap_start_positive(e, &n);	\
+	     bit < ebitmap_length(e);			\
+	     bit = ebitmap_next_positive(e, &n, bit))	\
 
 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);

security/selinux/ss/mls.c +58 -78

index 4a8bab2..27ef5eb 100644
@@ -34,7 +34,7 @@
  */
 int mls_compute_context_len(struct context * context)
 {
-	int i, l, len, range;
+	int i, l, len, head, prev;
 	struct ebitmap_node *node;
 
 	if (!selinux_mls_enabled)

@@ -42,31 +42,26 @@ int mls_compute_context_len(struct context * context)
 
 	len = 1; /* for the beginning ":" */
 	for (l = 0; l < 2; l++) {
-		range = 0;
 		len += strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
 
-		ebitmap_for_each_bit(&context->range.level[l].cat, node, i) {
-			if (ebitmap_node_get_bit(node, i)) {
-				if (range) {
-					range++;
-					continue;
-				}
-
+		/* categories */
+		head = -2;
+		prev = -2;
+		ebitmap_for_each_positive_bit(&context->range.level[l].cat, node, i) {
+			if (i - prev > 1) {
+				/* one or more negative bits are skipped, at least. */
+				if (head != prev)
+					len += strlen(policydb.p_cat_val_to_name[prev]) + 1;
 				len += strlen(policydb.p_cat_val_to_name[i]) + 1;
-				range++;
-			} else {
-				if (range > 1)
-					len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
-				range = 0;
+				head = i;
 			}
+			prev = i;
 		}
-		/* Handle case where last category is the end of range */
-		if (range > 1)
-			len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
-
+		if (prev != head)
+			len += strlen(policydb.p_cat_val_to_name[prev]) + 1;
 		if (l == 0) {
 			if (mls_level_eq(&context->range.level[0],
-			                 &context->range.level[1]))
+					 &context->range.level[1]))
 				break;
 			else
 				len++;

@@ -85,7 +80,7 @@ void mls_sid_to_context(struct context *context,
                         char **scontext)
 {
 	char *scontextp;
-	int i, l, range, wrote_sep;
+	int i, l, head, prev;
 	struct ebitmap_node *node;
 
 	if (!selinux_mls_enabled)

@@ -97,61 +92,50 @@ void mls_sid_to_context(struct context *context,
 	scontextp++;
 
 	for (l = 0; l < 2; l++) {
-		range = 0;
-		wrote_sep = 0;
 		strcpy(scontextp,
 		       policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
-		scontextp += strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
+		scontextp += strlen(scontextp);
 
 		/* categories */
-		ebitmap_for_each_bit(&context->range.level[l].cat, node, i) {
-			if (ebitmap_node_get_bit(node, i)) {
-				if (range) {
-					range++;
-					continue;
-				}
-
-				if (!wrote_sep) {
-					*scontextp++ = ':';
-					wrote_sep = 1;
-				} else
-					*scontextp++ = ',';
-				strcpy(scontextp, policydb.p_cat_val_to_name[i]);
-				scontextp += strlen(policydb.p_cat_val_to_name[i]);
-				range++;
-			} else {
-				if (range > 1) {
-					if (range > 2)
+		head = -2;
+		prev = -2;
+		ebitmap_for_each_positive_bit(&context->range.level[l].cat, node, i) {
+			if (i - prev > 1) {
+				/* one or more negative bits are skipped, at least. */
+				if (prev != head) {
+					if (prev - head > 1)
 						*scontextp++ = '.';
 					else
 						*scontextp++ = ',';
-
-					strcpy(scontextp, policydb.p_cat_val_to_name[i - 1]);
-					scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
+					strcpy(scontextp, policydb.p_cat_val_to_name[prev]);
+					scontextp += strlen(scontextp);
 				}
-				range = 0;
+				if (prev < 0)
+					*scontextp++ = ':';
+				else
+					*scontextp++ = ',';
+				strcpy(scontextp, policydb.p_cat_val_to_name[i]);
+				scontextp += strlen(scontextp);
+				head = i;
 			}
+			prev = i;
 		}
 
-		/* Handle case where last category is the end of range */
-		if (range > 1) {
-			if (range > 2)
+		if (prev != head) {
+			if (prev - head > 1)
 				*scontextp++ = '.';
 			else
 				*scontextp++ = ',';
-
-			strcpy(scontextp, policydb.p_cat_val_to_name[i - 1]);
-			scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
+			strcpy(scontextp, policydb.p_cat_val_to_name[prev]);
+			scontextp += strlen(scontextp);
 		}
 
 		if (l == 0) {
 			if (mls_level_eq(&context->range.level[0],
 			                 &context->range.level[1]))
 				break;
-			else {
-				*scontextp = '-';
-				scontextp++;
-			}
+			else
+				*scontextp++ = '-';
 		}
 	}
 

@@ -190,17 +174,15 @@ int mls_context_isvalid(struct policydb *p, struct context *c)
 		if (!levdatum)
 			return 0;
 
-		ebitmap_for_each_bit(&c->range.level[l].cat, node, i) {
-			if (ebitmap_node_get_bit(node, i)) {
-				if (i > p->p_cats.nprim)
-					return 0;
-				if (!ebitmap_get_bit(&levdatum->level->cat, i))
-					/*
-					 * Category may not be associated with
-					 * sensitivity in low level.
-					 */
-					return 0;
-			}
+		ebitmap_for_each_positive_bit(&c->range.level[l].cat, node, i) {
+			if (i > p->p_cats.nprim)
+				return 0;
+			if (!ebitmap_get_bit(&levdatum->level->cat, i))
+				/*
+				 * Category may not be associated with
+				 * sensitivity in low level.
+				 */
+				return 0;
 		}
 	}
 

@@ -485,18 +467,16 @@ int mls_convert_context(struct policydb *oldp,
 		c->range.level[l].sens = levdatum->level->sens;
 
 		ebitmap_init(&bitmap);
-		ebitmap_for_each_bit(&c->range.level[l].cat, node, i) {
-			if (ebitmap_node_get_bit(node, i)) {
-				int rc;
-
-				catdatum = hashtab_search(newp->p_cats.table,
-				         	oldp->p_cat_val_to_name[i]);
-				if (!catdatum)
-					return -EINVAL;
-				rc = ebitmap_set_bit(&bitmap, catdatum->value - 1, 1);
-				if (rc)
-					return rc;
-			}
+		ebitmap_for_each_positive_bit(&c->range.level[l].cat, node, i) {
+			int rc;
+
+			catdatum = hashtab_search(newp->p_cats.table,
+						  oldp->p_cat_val_to_name[i]);
+			if (!catdatum)
+				return -EINVAL;
+			rc = ebitmap_set_bit(&bitmap, catdatum->value - 1, 1);
+			if (rc)
+				return rc;
 		}
 		ebitmap_destroy(&c->range.level[l].cat);
 		c->range.level[l].cat = bitmap;

security/selinux/ss/services.c +4 -13

index 6100fc0..19be935 100644
@@ -329,12 +329,8 @@ static int context_struct_compute_av(struct context *scontext,
 	avkey.specified = AVTAB_AV;
 	sattr = &policydb.type_attr_map[scontext->type - 1];
 	tattr = &policydb.type_attr_map[tcontext->type - 1];
-	ebitmap_for_each_bit(sattr, snode, i) {
-		if (!ebitmap_node_get_bit(snode, i))
-			continue;
-		ebitmap_for_each_bit(tattr, tnode, j) {
-			if (!ebitmap_node_get_bit(tnode, j))
-				continue;
+	ebitmap_for_each_positive_bit(sattr, snode, i) {
+		ebitmap_for_each_positive_bit(tattr, tnode, j) {
 			avkey.source_type = i + 1;
 			avkey.target_type = j + 1;
 			for (node = avtab_search_node(&policydb.te_avtab, &avkey);

@@ -1621,14 +1617,10 @@ int security_get_user_sids(u32 fromsid,
 		goto out_unlock;
 	}
 
-	ebitmap_for_each_bit(&user->roles, rnode, i) {
-		if (!ebitmap_node_get_bit(rnode, i))
-			continue;
+	ebitmap_for_each_positive_bit(&user->roles, rnode, i) {
 		role = policydb.role_val_to_struct[i];
 		usercon.role = i+1;
-		ebitmap_for_each_bit(&role->types, tnode, j) {
-			if (!ebitmap_node_get_bit(tnode, j))
-				continue;
+		ebitmap_for_each_positive_bit(&role->types, tnode, j) {
 			usercon.type = j+1;
 
 			if (mls_setup_user_range(fromcon, user, &usercon))
 
--

This message was distributed to subscribers of the selinux mailing list. If you no longer wish to subscribe, send mail to [email protected] with the words "unsubscribe selinux" without quotes as the message.