Skip to contentSkip to conversation

SELinux patches for 2.6.24

PATCH In review James Morris 4 participants 14 messages Oct 9, 2007 – Oct 10, 2007

Subsystems (3)
lore
Share & tools
lore

James Morris

author maintainer
#0 lore raw

cover SELinux patches for 2.6.24

Please pull.

The following changes since commit bbf25010f1a6b761914430f5fca081ec8c7accd1:
Linus Torvalds (1):

        Linux 2.6.23

are available in the git repository at:

git://git.kernel.org/pub/scm/linux/kernel/git/jmorris/selinux-2.6.git for-linus

Eric Paris (2):
SELinux: change Kconfig to use select instead of depends
SELinux: policy selectable handling of unknown classes and perms

KaiGai Kohei (2):
SELinux: improve performance when AVC misses.
SELinux: kills warnings in Improve SELinux performance when AVC misses

Yuichi Nakamura (2):
SELinux: tune avtab to reduce memory usage
SELinux: Improve read/write performance

 fs/open.c                           |    4 +
 include/linux/security.h            |   18 +++
 security/dummy.c                    |    6 +
 security/selinux/Kconfig            |    7 +-
 security/selinux/avc.c              |    5 +
 security/selinux/hooks.c            |   53 +++++++-
 security/selinux/include/avc.h      |    2 +
 security/selinux/include/objsec.h   |    2 +
 security/selinux/include/security.h |    2 +
 security/selinux/selinuxfs.c        |   26 ++++
 security/selinux/ss/avtab.c         |   91 ++++++++----
 security/selinux/ss/avtab.h         |   16 ++-
 security/selinux/ss/conditional.c   |    4 +
 security/selinux/ss/ebitmap.c       |  282 +++++++++++++++++++---------------
 security/selinux/ss/ebitmap.h       |   89 +++++++++---
 security/selinux/ss/mls.c           |  156 +++++++++----------
 security/selinux/ss/policydb.c      |   11 +-
 security/selinux/ss/policydb.h      |    8 +
 security/selinux/ss/services.c      |   91 +++++++++---
 19 files changed, 588 insertions(+), 285 deletions(-)
author maintainer
#1 lore raw

PATCH 1/6 SELinux: change Kconfig to use select instead of depends

From: Eric Paris <[email protected]>

Changes the security/selinux/Kconfig to use select instead of depends for most of the SELinux requirements. This allows the SELinux option to show up when people do a make config without already knowing they had to enable audit and other non-obvious choices. Added a depends on SECURITY (which previously existed through SECURITY_NETWORK) so that SELinux would not always show up, but would be easy and intuitive to find.

---
 security/selinux/Kconfig |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)
security/selinux/Kconfig +6 -1
index b32a459..40b97e6 100644
@@ -1,6 +1,10 @@
 config SECURITY_SELINUX
 	bool "NSA SELinux Support"
-	depends on SECURITY_NETWORK && AUDIT && NET && INET
+	depends on SECURITY
+	select SECURITY_NETWORK
+	select AUDIT
+	select NET
+	select INET
 	select NETWORK_SECMARK
 	default n
 	help
@@ -9,6 +13,7 @@ config SECURITY_SELINUX
 	  You can obtain the policy compiler (checkpolicy), the utility for
 	  labeling filesystems (setfiles), and an example policy configuration
 	  from <http://www.nsa.gov/selinux/>.
+
 	  If you are unsure how to answer this question, answer N.
 
 config SECURITY_SELINUX_BOOTPARAM
Signature · 1 line
1.5.2.4
#2 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

Quoted 22 lines · On Wed, 10 Oct 2007 09:19:55 +1000 (EST) James Morris wrote:

From: Eric Paris <[email protected]>

Changes the security/selinux/Kconfig to use select instead of depends for most of the SELinux requirements. This allows the SELinux option to show up when people do a make config without already knowing they had to enable audit and other non-obvious choices. Added a depends on SECURITY (which previously existed through SECURITY_NETWORK) so that SELinux would not always show up, but would be easy and intuitive to find.

---
 security/selinux/Kconfig |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)
security/selinux/Kconfig +0 -0
index b32a459..40b97e6 100644
@@ -1,6 +1,10 @@
 config SECURITY_SELINUX

security/selinux/Kconfig line 10

Quoted 10 lines
security/selinux/Kconfig +5 -1
 	bool "NSA SELinux Support"
-	depends on SECURITY_NETWORK && AUDIT && NET && INET
+	depends on SECURITY
+	select SECURITY_NETWORK
+	select AUDIT
+	select NET
+	select INET
 	select NETWORK_SECMARK
 	default n
 	help

I doth protest. Enabling the entire NET subsystem thru a hidden select is awful. Select should be used (sparingly) to enable library code only. If someone wants NET enabled, they should enable it overtly, not covertly.

security/selinux/Kconfig config SECURITY_SELINUX · line 19

Quoted 8 lines
security/selinux/Kconfig +1 -0
@@ -9,6 +13,7 @@ config SECURITY_SELINUX
 	  You can obtain the policy compiler (checkpolicy), the utility for
 	  labeling filesystems (setfiles), and an example policy configuration
 	  from <http://www.nsa.gov/selinux/>.
+
 	  If you are unsure how to answer this question, answer N.
 
 config SECURITY_SELINUX_BOOTPARAM

---
~Randy

author maintainer
#3 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

Quoted 4 lines · Randy Dunlap

I doth protest. Enabling the entire NET subsystem thru a hidden select is awful. Select should be used (sparingly) to enable library code only. If someone wants NET enabled, they should enable it overtly, not covertly.

Ok, fair enough.

I've dropped the patch and rebased the branch. Please pull per:

The following changes since commit bbf25010f1a6b761914430f5fca081ec8c7accd1:
Linus Torvalds (1):

        Linux 2.6.23

are available in the git repository at:

ssh://master.kernel.org/pub/scm/linux/kernel/git/jmorris/selinux-2.6.git for-linus

Eric Paris (1):
SELinux: policy selectable handling of unknown classes and perms

KaiGai Kohei (2):
SELinux: improve performance when AVC misses.
SELinux: kills warnings in Improve SELinux performance when AVC misses

Yuichi Nakamura (2):
SELinux: tune avtab to reduce memory usage
SELinux: Improve read/write performance

 fs/open.c                           |    4 +
 include/linux/security.h            |   18 +++
 security/dummy.c                    |    6 +
 security/selinux/avc.c              |    5 +
 security/selinux/hooks.c            |   53 +++++++-
 security/selinux/include/avc.h      |    2 +
 security/selinux/include/objsec.h   |    2 +
 security/selinux/include/security.h |    2 +
 security/selinux/selinuxfs.c        |   26 ++++
 security/selinux/ss/avtab.c         |   91 ++++++++----
 security/selinux/ss/avtab.h         |   16 ++-
 security/selinux/ss/conditional.c   |    4 +
 security/selinux/ss/ebitmap.c       |  282 +++++++++++++++++++---------------
 security/selinux/ss/ebitmap.h       |   89 +++++++++---
 security/selinux/ss/mls.c           |  156 +++++++++----------
 security/selinux/ss/policydb.c      |   11 +-
 security/selinux/ss/policydb.h      |    8 +
 security/selinux/ss/services.c      |   91 +++++++++---
 18 files changed, 582 insertions(+), 284 deletions(-)
Signature · 2 lines
James Morris
<[email protected]>
#4 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

Quoted 10 lines · On Wed, 10 Oct 2007 09:50:49 +1000 (EST) James Morris wrote:
Quoted 4 lines · Randy Dunlap

I doth protest. Enabling the entire NET subsystem thru a hidden select is awful. Select should be used (sparingly) to enable library code only. If someone wants NET enabled, they should enable it overtly, not covertly.

Ok, fair enough.

I've dropped the patch and rebased the branch. Please pull per:

Great, thanks.

---
~Randy

#5 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

In reply to Randy Dunlap
Quoted 31 lines · Randy Dunlap
Quoted 29 lines · On Wed, 10 Oct 2007 09:19:55 +1000 (EST) James Morris wrote:

From: Eric Paris <[email protected]>

Changes the security/selinux/Kconfig to use select instead of depends for most of the SELinux requirements. This allows the SELinux option to show up when people do a make config without already knowing they had to enable audit and other non-obvious choices. Added a depends on SECURITY (which previously existed through SECURITY_NETWORK) so that SELinux would not always show up, but would be easy and intuitive to find.

---
 security/selinux/Kconfig |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)
security/selinux/Kconfig +5 -1
index b32a459..40b97e6 100644
@@ -1,6 +1,10 @@
 config SECURITY_SELINUX
 	bool "NSA SELinux Support"
-	depends on SECURITY_NETWORK && AUDIT && NET && INET
+	depends on SECURITY
+	select SECURITY_NETWORK
+	select AUDIT
+	select NET
+	select INET
Quoted 8 lines

security/selinux/Kconfig line 10

Quoted 3 lines
security/selinux/Kconfig +0 -0
 	select NETWORK_SECMARK
 	default n
 	help

I doth protest. Enabling the entire NET subsystem thru a hidden select is awful. Select should be used (sparingly) to enable library code only. If someone wants NET enabled, they should enable it overtly, not covertly.

Does that apply to all the options, or only to NET (e.g. is it ok to select AUDIT)? I thought that this patch came out of earlier discussions about proper use of select vs. depends. It may have gone too far, but I'm not sure it should be discarded entirely.

Quoted 15 lines

security/selinux/Kconfig config SECURITY_SELINUX · line 19

Quoted 10 lines
security/selinux/Kconfig +1 -0
@@ -9,6 +13,7 @@ config SECURITY_SELINUX
 	  You can obtain the policy compiler (checkpolicy), the utility for
 	  labeling filesystems (setfiles), and an example policy configuration
 	  from <http://www.nsa.gov/selinux/>.
+
 	  If you are unsure how to answer this question, answer N.
 
 config SECURITY_SELINUX_BOOTPARAM

---
~Randy

Signature · 2 lines
Stephen Smalley
National Security Agency
#6 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

Quoted 40 lines · Stephen Smalley
Quoted 30 lines · Randy Dunlap
Quoted 28 lines · On Wed, 10 Oct 2007 09:19:55 +1000 (EST) James Morris wrote:

From: Eric Paris <[email protected]>

Changes the security/selinux/Kconfig to use select instead of depends for most of the SELinux requirements. This allows the SELinux option to show up when people do a make config without already knowing they had to enable audit and other non-obvious choices. Added a depends on SECURITY (which previously existed through SECURITY_NETWORK) so that SELinux would not always show up, but would be easy and intuitive to find.

---
 security/selinux/Kconfig |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)
security/selinux/Kconfig +4 -1
index b32a459..40b97e6 100644
@@ -1,6 +1,10 @@
 config SECURITY_SELINUX
 	bool "NSA SELinux Support"
-	depends on SECURITY_NETWORK && AUDIT && NET && INET
+	depends on SECURITY
+	select SECURITY_NETWORK
+	select AUDIT
+	select NET
Quoted 8 lines

security/selinux/Kconfig line 10

Quoted 4 lines
security/selinux/Kconfig +1 -0
+	select INET
 	select NETWORK_SECMARK
 	default n
 	help

I doth protest. Enabling the entire NET subsystem thru a hidden select is awful. Select should be used (sparingly) to enable library code only. If someone wants NET enabled, they should enable it overtly, not covertly.

Quoted 4 lines

Does that apply to all the options, or only to NET (e.g. is it ok to select AUDIT)? I thought that this patch came out of earlier discussions about proper use of select vs. depends. It may have gone too far, but I'm not sure it should be discarded entirely.

AUDIT isn't quite library code, still I don't have a (big) problem with selecting it or NETWORK_SECMARK. (other than select is evil :)

OTOH, NET and INET are large config options, not library-like code, and should not be selected.

Signature · 1 line
~Randy
#7 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

Quoted 13 lines · Randy Dunlap
Quoted 9 lines
Quoted 9 lines

security/selinux/Kconfig line 8

Quoted 9 lines

config SECURITY_SELINUX

security/selinux/Kconfig +5 -1
 	bool "NSA SELinux Support"
-	depends on SECURITY_NETWORK && AUDIT && NET && INET
+	depends on SECURITY
+	select SECURITY_NETWORK
+	select AUDIT
+	select NET
+	select INET
 	select NETWORK_SECMARK

AUDIT isn't quite library code, still I don't have a (big) problem with selecting it or NETWORK_SECMARK. (other than select is evil :)

Quoted 2 lines

OTOH, NET and INET are large config options, not library-like code, and should not be selected.

If it does a 'select SECURITY_NETWORK' but NET=n, does the resulting kernel actually build? The problem seems to be that select isn't transitive - if you select something, it won't automagically select that something's pre-reqs (modulo the recent patches I've seen posted, have those been mainlined?).

#8 lore raw

Re: [PATCH 1/6] SELinux: change Kconfig to use select instead of depends

Quoted 15 lines · [email protected] wrote:
Quoted 13 lines · Randy Dunlap
Quoted 9 lines
Quoted 9 lines

security/selinux/Kconfig line 8

Quoted 9 lines

config SECURITY_SELINUX

security/selinux/Kconfig +5 -1
 	bool "NSA SELinux Support"
-	depends on SECURITY_NETWORK && AUDIT && NET && INET
+	depends on SECURITY
+	select SECURITY_NETWORK
+	select AUDIT
+	select NET
+	select INET
 	select NETWORK_SECMARK

AUDIT isn't quite library code, still I don't have a (big) problem with selecting it or NETWORK_SECMARK. (other than select is evil :)

Quoted 7 lines
Quoted 2 lines

OTOH, NET and INET are large config options, not library-like code, and should not be selected.

If it does a 'select SECURITY_NETWORK' but NET=n, does the resulting kernel actually build? The problem seems to be that select isn't transitive - if you select something, it won't automagically select that something's pre-reqs (modulo the recent patches I've seen posted, have those been mainlined?).

Good point.

I haven't tested that, but it's most likely still a problem. "select" does not follow its dependency chain...

Signature · 1 line
~Randy
author maintainer
#9 lore raw

PATCH 2/6 SELinux: tune avtab to reduce memory usage

In reply to James Morris

From: Yuichi Nakamura <[email protected]>

This patch reduces memory usage of SELinux by tuning avtab. Number of hash slots in avtab was 32768. Unused slots used memory when number of rules is fewer. This patch decides number of hash slots dynamically based on number of rules. (chain length)^2 is also printed out in avtab_hash_eval to see standard deviation of avtab hash table.

---
 security/selinux/ss/avtab.c       |   91 ++++++++++++++++++++++++++-----------
 security/selinux/ss/avtab.h       |   16 +++++--
 security/selinux/ss/conditional.c |    4 ++
 security/selinux/ss/policydb.c    |    7 +--
 4 files changed, 82 insertions(+), 36 deletions(-)
security/selinux/ss/avtab.c +65 -26
index 85705eb..7551af1 100644
@@ -12,24 +12,25 @@
  *	This program is free software; you can redistribute it and/or modify
  *  	it under the terms of the GNU General Public License as published by
  *	the Free Software Foundation, version 2.
+ *
+ * Updated: Yuichi Nakamura <[email protected]>
+ * 	Tuned number of hash slots for avtab to reduce memory usage
  */
 
 #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) \
-((keyp->target_class + \
- (keyp->target_type << 2) + \
- (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
-
 static struct kmem_cache *avtab_node_cachep;
 
+static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
+{
+	return ((keyp->target_class + (keyp->target_type << 2) +
+		 (keyp->source_type << 9)) & mask);
+}
+
 static struct avtab_node*
 avtab_insert_node(struct avtab *h, int hvalue,
 		  struct avtab_node * prev, struct avtab_node * cur,
@@ -59,10 +60,10 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat
 	struct avtab_node *prev, *cur, *newnode;
 	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-	if (!h)
+	if (!h || !h->htable)
 		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) {
@@ -100,9 +101,9 @@ avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_da
 	struct avtab_node *prev, *cur, *newnode;
 	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-	if (!h)
+	if (!h || !h->htable)
 		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) {
@@ -132,10 +133,10 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
 	struct avtab_node *cur;
 	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-	if (!h)
+	if (!h || !h->htable)
 		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 &&
@@ -167,10 +168,10 @@ avtab_search_node(struct avtab *h, struct avtab_key *key)
 	struct avtab_node *cur;
 	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-	if (!h)
+	if (!h || !h->htable)
 		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 +229,7 @@ void avtab_destroy(struct avtab *h)
 	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,32 +238,63 @@ void avtab_destroy(struct avtab *h)
 		}
 		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)
 {
-	int i;
+	h->htable = NULL;
+	h->nel = 0;
+	return 0;
+}
+
+int avtab_alloc(struct avtab *h, u32 nrules)
+{
+	u16 mask = 0;
+	u32 shift = 0;
+	u32 work = nrules;
+	u32 nslot = 0;
+
+	if (nrules == 0)
+		goto avtab_alloc_out;
 
-	h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
+	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 = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL);
 	if (!h->htable)
 		return -ENOMEM;
-	for (i = 0; i < AVTAB_SIZE; i++)
-		h->htable[i] = NULL;
+
+ avtab_alloc_out:
 	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;
 }
 
 void avtab_hash_eval(struct avtab *h, char *tag)
 {
 	int i, chain_len, slots_used, max_chain_len;
+	unsigned long long chain2_len_sum;
 	struct avtab_node *cur;
 
 	slots_used = 0;
 	max_chain_len = 0;
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	chain2_len_sum = 0;
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		if (cur) {
 			slots_used++;
@@ -274,12 +306,14 @@ void avtab_hash_eval(struct avtab *h, char *tag)
 
 			if (chain_len > max_chain_len)
 				max_chain_len = chain_len;
+			chain2_len_sum += chain_len * chain_len;
 		}
 	}
 
 	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
-	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
-	       max_chain_len);
+	       "chain length %d sum of chain length^2 %Lu\n",
+	       tag, h->nel, slots_used, h->nslot, max_chain_len,
+	       chain2_len_sum);
 }
 
 static uint16_t spec_order[] = {
@@ -419,6 +453,11 @@ int avtab_read(struct avtab *a, void *fp, u32 vers)
 		rc = -EINVAL;
 		goto bad;
 	}
+
+	rc = avtab_alloc(a, nel);
+	if (rc)
+		goto bad;
+
 	for (i = 0; i < nel; i++) {
 		rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
 		if (rc) {
security/selinux/ss/avtab.h +11 -5
index 0a90d93..d8edf8c 100644
@@ -16,6 +16,9 @@
  *	This program is free software; you can redistribute it and/or modify
  *  	it under the terms of the GNU General Public License as published by
  *	the Free Software Foundation, version 2.
+ *
+ * Updated: Yuichi Nakamura <[email protected]>
+ * 	Tuned number of hash slots for avtab to reduce memory usage
  */
 #ifndef _SS_AVTAB_H_
 #define _SS_AVTAB_H_
@@ -50,9 +53,13 @@ struct avtab_node {
 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 *, u32);
 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 +81,10 @@ struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified
 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_ */
 
security/selinux/ss/conditional.c +4 -0
index d2737ed..45b93a8 100644
@@ -456,6 +456,10 @@ int cond_read_list(struct policydb *p, void *fp)
 
 	len = le32_to_cpu(buf[0]);
 
+	rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
+	if (rc)
+		goto err;
+
 	for (i = 0; i < len; i++) {
 		node = kzalloc(sizeof(struct cond_node), GFP_KERNEL);
 		if (!node)
security/selinux/ss/policydb.c +2 -5
index f05f97a..5ecbad7 100644
@@ -177,18 +177,15 @@ static int policydb_init(struct policydb *p)
 
 	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);
Signature · 1 line
1.5.2.4
author maintainer
#10 lore raw

PATCH 3/6 SELinux: Improve read/write performance

In reply to James Morris

From: Yuichi Nakamura <[email protected]>

It reduces the selinux overhead on read/write by only revalidating permissions in selinux_file_permission if the task or inode labels have changed or the policy has changed since the open-time check. A new LSM hook, security_dentry_open, is added to capture the necessary state at open time to allow this optimization.

(see http://marc.info/?l=selinux&m=118972995207740&w=2)

---
 fs/open.c                         |    4 +++
 include/linux/security.h          |   18 ++++++++++++
 security/dummy.c                  |    6 ++++
 security/selinux/avc.c            |    5 +++
 security/selinux/hooks.c          |   53 ++++++++++++++++++++++++++++++++++++-
 security/selinux/include/avc.h    |    2 +
 security/selinux/include/objsec.h |    2 +
 7 files changed, 89 insertions(+), 1 deletions(-)
fs/open.c +4 -0
index 1d9e5e9..044bfa8 100644
@@ -757,6 +757,10 @@ static struct file *__dentry_open(struct dentry *dentry, struct vfsmount *mnt,
 	f->f_op = fops_get(inode->i_fop);
 	file_move(f, &inode->i_sb->s_files);
 
+	error = security_dentry_open(f);
+	if (error)
+		goto cleanup_all;
+
 	if (!open && f->f_op)
 		open = f->f_op->open;
 	if (open) {
include/linux/security.h +18 -0
index 1a15526..928d479 100644
@@ -504,6 +504,13 @@ struct request_sock;
  *	@file contains the file structure being received.
  *	Return 0 if permission is granted.
  *
+ * Security hook for dentry
+ *
+ * @dentry_open
+ *	Save open-time permission checking state for later use upon
+ *	file_permission, and recheck access if anything has changed
+ *	since inode_permission.
+ *
  * Security hooks for task operations.
  *
  * @task_create:
@@ -1256,6 +1263,7 @@ struct security_operations {
 	int (*file_send_sigiotask) (struct task_struct * tsk,
 				    struct fown_struct * fown, int sig);
 	int (*file_receive) (struct file * file);
+	int (*dentry_open)  (struct file *file);
 
 	int (*task_create) (unsigned long clone_flags);
 	int (*task_alloc_security) (struct task_struct * p);
@@ -1864,6 +1872,11 @@ static inline int security_file_receive (struct file *file)
 	return security_ops->file_receive (file);
 }
 
+static inline int security_dentry_open (struct file *file)
+{
+	return security_ops->dentry_open (file);
+}
+
 static inline int security_task_create (unsigned long clone_flags)
 {
 	return security_ops->task_create (clone_flags);
@@ -2546,6 +2559,11 @@ static inline int security_file_receive (struct file *file)
 	return 0;
 }
 
+static inline int security_dentry_open (struct file *file)
+{
+	return 0;
+}
+
 static inline int security_task_create (unsigned long clone_flags)
 {
 	return 0;
security/dummy.c +6 -0
index 853ec22..64b647a 100644
@@ -463,6 +463,11 @@ static int dummy_file_receive (struct file *file)
 	return 0;
 }
 
+static int dummy_dentry_open (struct file *file)
+{
+	return 0;
+}
+
 static int dummy_task_create (unsigned long clone_flags)
 {
 	return 0;
@@ -1033,6 +1038,7 @@ void security_fixup_ops (struct security_operations *ops)
 	set_to_dummy_if_null(ops, file_set_fowner);
 	set_to_dummy_if_null(ops, file_send_sigiotask);
 	set_to_dummy_if_null(ops, file_receive);
+	set_to_dummy_if_null(ops, dentry_open);
 	set_to_dummy_if_null(ops, task_create);
 	set_to_dummy_if_null(ops, task_alloc_security);
 	set_to_dummy_if_null(ops, task_free_security);
security/selinux/avc.c +5 -0
index 0e69adf..81b3dff 100644
@@ -916,3 +916,8 @@ int avc_has_perm(u32 ssid, u32 tsid, u16 tclass,
 	avc_audit(ssid, tsid, tclass, requested, &avd, rc, auditdata);
 	return rc;
 }
+
+u32 avc_policy_seqno(void)
+{
+	return avc_cache.latest_notif;
+}
security/selinux/hooks.c +52 -1

83 lines not on this page · raw message

security/selinux/include/avc.h +2 -0
index e145f6e..553607a 100644
@@ -112,6 +112,8 @@ int avc_has_perm(u32 ssid, u32 tsid,
                  u16 tclass, u32 requested,
                  struct avc_audit_data *auditdata);
 
+u32 avc_policy_seqno(void);
+
 #define AVC_CALLBACK_GRANT		1
 #define AVC_CALLBACK_TRY_REVOKE		2
 #define AVC_CALLBACK_REVOKE		4
security/selinux/include/objsec.h +2 -0
index 91b88f0..642a9fd 100644
@@ -53,6 +53,8 @@ struct file_security_struct {
 	struct file *file;              /* back pointer to file object */
 	u32 sid;              /* SID of open file description */
 	u32 fown_sid;         /* SID of file owner (for SIGIO) */
+	u32 isid;             /* SID of inode at the time of file open */
+	u32 pseqno;           /* Policy seqno at the time of file open */
 };
 
 struct superblock_security_struct {
Signature · 1 line
1.5.2.4
author maintainer
#11 lore raw

PATCH 4/6 SELinux: policy selectable handling of unknown classes and perms

In reply to James Morris

From: Eric Paris <[email protected]>

Allow policy to select, in much the same way as it selects MLS support, how the kernel should handle access decisions which contain either unknown classes or unknown permissions in known classes. The three choices for the policy flags are

0 - Deny unknown security access. (default)
2 - reject loading policy if it does not contain all definitions 4 - allow unknown security access

The policy's choice is exported through 2 booleans in selinuxfs. /selinux/deny_unknown and /selinux/reject_unknown.

---
 security/selinux/include/security.h |    2 +
 security/selinux/selinuxfs.c        |   26 ++++++++++++
 security/selinux/ss/policydb.c      |    4 ++
 security/selinux/ss/policydb.h      |    8 ++++
 security/selinux/ss/services.c      |   75 ++++++++++++++++++++++++++++++----
 5 files changed, 106 insertions(+), 9 deletions(-)
security/selinux/include/security.h +2 -0
index 83bdd4d..39337af 100644
@@ -90,6 +90,8 @@ int security_sid_mls_copy(u32 sid, u32 mls_sid, u32 *new_sid);
 
 int security_get_classes(char ***classes, int *nclasses);
 int security_get_permissions(char *class, char ***perms, int *nperms);
+int security_get_reject_unknown(void);
+int security_get_allow_unknown(void);
 
 #define SECURITY_FS_USE_XATTR		1 /* use xattr */
 #define SECURITY_FS_USE_TRANS		2 /* use transition SIDs, e.g. devpts/tmpfs */
security/selinux/selinuxfs.c +26 -0
index c9e92da..f5f3e6d 100644
@@ -103,6 +103,8 @@ enum sel_inos {
 	SEL_MEMBER,	/* compute polyinstantiation membership decision */
 	SEL_CHECKREQPROT, /* check requested protection, not kernel-applied one */
 	SEL_COMPAT_NET,	/* whether to use old compat network packet controls */
+	SEL_REJECT_UNKNOWN, /* export unknown reject handling to userspace */
+	SEL_DENY_UNKNOWN, /* export unknown deny handling to userspace */
 	SEL_INO_NEXT,	/* The next inode number to use */
 };
 
@@ -177,6 +179,23 @@ static const struct file_operations sel_enforce_ops = {
 	.write		= sel_write_enforce,
 };
 
+static ssize_t sel_read_handle_unknown(struct file *filp, char __user *buf,
+					size_t count, loff_t *ppos)
+{
+	char tmpbuf[TMPBUFLEN];
+	ssize_t length;
+	ino_t ino = filp->f_path.dentry->d_inode->i_ino;
+	int handle_unknown = (ino == SEL_REJECT_UNKNOWN) ?
+		security_get_reject_unknown() : !security_get_allow_unknown();
+
+	length = scnprintf(tmpbuf, TMPBUFLEN, "%d", handle_unknown);
+	return simple_read_from_buffer(buf, count, ppos, tmpbuf, length);
+}
+
+static const struct file_operations sel_handle_unknown_ops = {
+	.read		= sel_read_handle_unknown,
+};
+
 #ifdef CONFIG_SECURITY_SELINUX_DISABLE
 static ssize_t sel_write_disable(struct file * file, const char __user * buf,
 				 size_t count, loff_t *ppos)
@@ -309,6 +328,11 @@ static ssize_t sel_write_load(struct file * file, const char __user * buf,
 		length = count;
 
 out1:
+
+	printk(KERN_INFO "SELinux: policy loaded with handle_unknown=%s\n",
+	       (security_get_reject_unknown() ? "reject" :
+		(security_get_allow_unknown() ? "allow" : "deny")));
+
 	audit_log(current->audit_context, GFP_KERNEL, AUDIT_MAC_POLICY_LOAD,
 		"policy loaded auid=%u",
 		audit_get_loginuid(current->audit_context));
@@ -1575,6 +1599,8 @@ static int sel_fill_super(struct super_block * sb, void * data, int silent)
 		[SEL_MEMBER] = {"member", &transaction_ops, S_IRUGO|S_IWUGO},
 		[SEL_CHECKREQPROT] = {"checkreqprot", &sel_checkreqprot_ops, S_IRUGO|S_IWUSR},
 		[SEL_COMPAT_NET] = {"compat_net", &sel_compat_net_ops, S_IRUGO|S_IWUSR},
+		[SEL_REJECT_UNKNOWN] = {"reject_unknown", &sel_handle_unknown_ops, S_IRUGO},
+		[SEL_DENY_UNKNOWN] = {"deny_unknown", &sel_handle_unknown_ops, S_IRUGO},
 		/* last one */ {""}
 	};
 	ret = simple_fill_super(sb, SELINUX_MAGIC, selinux_files);
security/selinux/ss/policydb.c +4 -0
index 5ecbad7..539828b 100644
@@ -674,6 +674,8 @@ void policydb_destroy(struct policydb *p)
 	}
 	kfree(p->type_attr_map);
 
+	kfree(p->undefined_perms);
+
 	return;
 }
 
@@ -1527,6 +1529,8 @@ int policydb_read(struct policydb *p, void *fp)
 			goto bad;
 		}
 	}
+	p->reject_unknown = !!(le32_to_cpu(buf[1]) & REJECT_UNKNOWN);
+	p->allow_unknown = !!(le32_to_cpu(buf[1]) & ALLOW_UNKNOWN);
 
 	info = policydb_lookup_compat(p->policyvers);
 	if (!info) {
security/selinux/ss/policydb.h +8 -0
index 8319d5f..844d310 100644
@@ -242,6 +242,10 @@ struct policydb {
 	struct ebitmap *type_attr_map;
 
 	unsigned int policyvers;
+
+	unsigned int reject_unknown : 1;
+	unsigned int allow_unknown : 1;
+	u32 *undefined_perms;
 };
 
 extern void policydb_destroy(struct policydb *p);
@@ -253,6 +257,10 @@ extern int policydb_read(struct policydb *p, void *fp);
 
 #define POLICYDB_CONFIG_MLS    1
 
+/* the config flags related to unknown classes/perms are bits 2 and 3 */
+#define REJECT_UNKNOWN	0x00000002
+#define ALLOW_UNKNOWN	0x00000004
+
 #define OBJECT_R "object_r"
 #define OBJECT_R_VAL 1
 
security/selinux/ss/services.c +66 -9

139 lines not on this page · raw message

Signature · 1 line
1.5.2.4
author maintainer
#12 lore raw

PATCH 5/6 SELinux: improve performance when AVC misses

In reply to James Morris

From: KaiGai Kohei <[email protected]>

* We add ebitmap_for_each_positive_bit() which enables to walk on any positive bit on the given ebitmap, to improve its performance using common bit-operations defined in linux/bitops.h.
In the previous version, this logic was implemented using a combination of ebitmap_for_each_bit() and ebitmap_node_get_bit(), but is was worse in performance aspect.
This logic is most frequestly used to compute a new AVC entry, so this patch can improve SELinux performance when AVC misses are happen.
* struct ebitmap_node is redefined as an array of "unsigned long", to get suitable for using find_next_bit() which is fasted than iteration of shift and logical operation, and to maximize memory usage allocated from general purpose slab.
* Any ebitmap_for_each_bit() are repleced by the new implementation in ss/service.c and ss/mls.c. Some of related implementation are changed, however, there is no incompatibility with the previous version.
* The width of any new line are less or equal than 80-chars.

The following benchmark shows the effect of this patch, when we access many files which have different security context one after another. The number is more than /selinux/avc/cache_threshold, so any access always causes AVC misses.

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]
---
 security/selinux/ss/ebitmap.c  |  281 ++++++++++++++++++++++-----------------
 security/selinux/ss/ebitmap.h  |   87 ++++++++++---
 security/selinux/ss/mls.c      |  156 +++++++++++------------
 security/selinux/ss/services.c |   16 +--
 4 files changed, 303 insertions(+), 237 deletions(-)
security/selinux/ss/ebitmap.c +158 -123
index ce492a6..ae44c0c 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,27 @@ 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 delta, e_startbit, c_endbit;
+
+			e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE;
+			c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE;
+			if (e_startbit >= c_endbit) {
+				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);
+			}
+			delta = e_startbit - c_iter->startbit;
+			cmap_idx = delta / NETLBL_CATMAP_MAPSIZE;
+			cmap_sft = delta % 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 +142,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 +156,50 @@ 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)
+			unsigned int delta;
+			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;
+			}
+			delta = c_pos - e_iter->startbit;
+			e_idx = delta / EBITMAP_UNIT_SIZE;
+			e_sft = delta % 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 +214,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 +226,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 +250,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 +265,35 @@ 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;
-					}
+				unsigned int s;
+
+				ebitmap_node_clr_bit(n, bit);
+
+				s = find_first_bit(n->maps, EBITMAP_SIZE);
+				if (s < 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 +308,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 +347,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 +359,89 @@ 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 *tmp;
+			tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
+			if (!tmp) {
+				printk(KERN_ERR
+				       "security: ebitmap: out of memory\n");
+				rc = -ENOMEM;
+				goto bad;
+			}
+			/* round down */
+			tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
+			if (n) {
+				n->next = tmp;
+			} else {
+				e->node = tmp;
+			}
+			n = tmp;
+		} 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 +66 -21

119 lines not on this page · raw message

security/selinux/ss/mls.c +75 -81

217 lines not on this page · raw message

security/selinux/ss/services.c +4 -12
index 03140ed..d572dc9 100644
@@ -353,12 +353,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);
@@ -1668,14 +1664,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))
Signature · 1 line
1.5.2.4
author maintainer
#13 lore raw

PATCH 6/6 SELinux: kills warnings in Improve SELinux performance when AVC misses

In reply to James Morris

From: KaiGai Kohei <[email protected]>

This patch kills ugly warnings when the "Improve SELinux performance when AVC misses" patch.

---
 security/selinux/ss/ebitmap.c |   11 +++++------
 security/selinux/ss/ebitmap.h |    2 ++
 2 files changed, 7 insertions(+), 6 deletions(-)
security/selinux/ss/ebitmap.c +5 -6
index ae44c0c..c1a6b22 100644
@@ -193,7 +193,7 @@ int ebitmap_netlbl_import(struct ebitmap *ebmap,
 			e_sft = delta % EBITMAP_UNIT_SIZE;
 			while (map) {
 				e_iter->maps[e_idx++] |= map & (-1UL);
-				map >>= EBITMAP_UNIT_SIZE;
+				map = EBITMAP_SHIFT_UNIT_SIZE(map);
 			}
 		}
 		c_iter = c_iter->next;
@@ -389,13 +389,13 @@ int ebitmap_read(struct ebitmap *e, void *fp)
 
 		if (startbit & (mapunit - 1)) {
 			printk(KERN_ERR "security: ebitmap start bit (%d) is "
-			       "not a multiple of the map unit size (%Zd)\n",
+			       "not a multiple of the map unit size (%u)\n",
 			       startbit, mapunit);
 			goto bad;
 		}
 		if (startbit > e->highbit - mapunit) {
 			printk(KERN_ERR "security: ebitmap start bit (%d) is "
-			       "beyond the end of the bitmap (%Zd)\n",
+			       "beyond the end of the bitmap (%u)\n",
 			       startbit, (e->highbit - mapunit));
 			goto bad;
 		}
@@ -433,9 +433,8 @@ int ebitmap_read(struct ebitmap *e, void *fp)
 
 		index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
 		while (map) {
-			n->maps[index] = map & (-1UL);
-			map = map >> EBITMAP_UNIT_SIZE;
-			index++;
+			n->maps[index++] = map & (-1UL);
+			map = EBITMAP_SHIFT_UNIT_SIZE(map);
 		}
 	}
 ok:
security/selinux/ss/ebitmap.h +2 -0
index e38a327..f283b43 100644
@@ -21,6 +21,8 @@
 #define EBITMAP_UNIT_SIZE	BITS_PER_LONG
 #define EBITMAP_SIZE		(EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE)
 #define EBITMAP_BIT		1ULL
+#define EBITMAP_SHIFT_UNIT_SIZE(x)					\
+	(((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2)
 
 struct ebitmap_node {
 	struct ebitmap_node *next;
Signature · 1 line
1.5.2.4