[PATCH 1/5] SELinux: remove the unused ae.used

[PATCH 1/5] SELinux: remove the unused ae.used

[Eric Paris]

Currently SELinux code has an atomic which was intended to track how many
times an avc entry was used and to evict entries when they haven't been
used recently.  Instead we never let this atomic get above 1 and evict when
it is first checked for eviction since it hits zero.  This is a total waste
of time so I'm completely dropping ae.used.

This change resulted in about a 3% faster avc_has_perm_noaudit when running
oprofile against a tbench benchmark.

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 security/selinux/avc.c |   28 +++++++---------------------
 1 files changed, 7 insertions(+), 21 deletions(-)

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index 703aba1..abfe378 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -88,7 +88,6 @@ struct avc_entry {
 	u32			tsid;
 	u16			tclass;
 	struct av_decision	avd;
-	atomic_t		used;	/* used recently */
 };
 
 struct avc_node {
@@ -321,16 +320,13 @@ static inline int avc_reclaim_node(void)
 
 		rcu_read_lock();
 		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
-			if (atomic_dec_and_test(&node->ae.used)) {
-				/* Recently Unused */
-				avc_node_delete(node);
-				avc_cache_stats_incr(reclaims);
-				ecx++;
-				if (ecx >= AVC_CACHE_RECLAIM) {
-					rcu_read_unlock();
-					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
-					goto out;
-				}
+			avc_node_delete(node);
+			avc_cache_stats_incr(reclaims);
+			ecx++;
+			if (ecx >= AVC_CACHE_RECLAIM) {
+				rcu_read_unlock();
+				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
+				goto out;
 			}
 		}
 		rcu_read_unlock();
@@ -350,7 +346,6 @@ static struct avc_node *avc_alloc_node(void)
 
 	INIT_RCU_HEAD(&node->rhead);
 	INIT_LIST_HEAD(&node->list);
-	atomic_set(&node->ae.used, 1);
 	avc_cache_stats_incr(allocations);
 
 	if (atomic_inc_return(&avc_cache.active_nodes) > avc_cache_threshold)
@@ -383,15 +378,6 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
 		}
 	}
 
-	if (ret == NULL) {
-		/* cache miss */
-		goto out;
-	}
-
-	/* cache hit */
-	if (atomic_read(&ret->ae.used) != 1)
-		atomic_set(&ret->ae.used, 1);
-out:
 	return ret;
 }
 


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[PATCH 2/5] SELinux: more careful use of avd in avc_has_perm_noaudit

[Eric Paris]

we are often needlessly jumping through hoops when it comes to avd
entries in avc_has_perm_noaudit and we have extra initialization and memcpy
which are just wasting performance.  Try to clean the function up a bit.

This patch resulted in a 13% drop in time spent in avc_has_perm_noaudit in my
oprofile sampling of a tbench benchmark.

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 security/selinux/avc.c |   43 ++++++++++++++++++++++++-------------------
 1 files changed, 24 insertions(+), 19 deletions(-)

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index abfe378..332c3cd 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -355,12 +355,12 @@ out:
 	return node;
 }
 
-static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
+static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct av_decision *avd)
 {
 	node->ae.ssid = ssid;
 	node->ae.tsid = tsid;
 	node->ae.tclass = tclass;
-	memcpy(&node->ae.avd, &ae->avd, sizeof(node->ae.avd));
+	memcpy(&node->ae.avd, avd, sizeof(node->ae.avd));
 }
 
 static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
@@ -440,31 +440,31 @@ static int avc_latest_notif_update(int seqno, int is_insert)
  * @ssid: source security identifier
  * @tsid: target security identifier
  * @tclass: target security class
- * @ae: AVC entry
+ * @avd: resulting av decision
  *
  * Insert an AVC entry for the SID pair
  * (@ssid, @tsid) and class @tclass.
  * The access vectors and the sequence number are
  * normally provided by the security server in
  * response to a security_compute_av() call.  If the
- * sequence number @ae->avd.seqno is not less than the latest
+ * sequence number @avd->seqno is not less than the latest
  * revocation notification, then the function copies
  * the access vectors into a cache entry, returns
  * avc_node inserted. Otherwise, this function returns NULL.
  */
-static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
+static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_decision *avd)
 {
 	struct avc_node *pos, *node = NULL;
 	int hvalue;
 	unsigned long flag;
 
-	if (avc_latest_notif_update(ae->avd.seqno, 1))
+	if (avc_latest_notif_update(avd->seqno, 1))
 		goto out;
 
 	node = avc_alloc_node();
 	if (node) {
 		hvalue = avc_hash(ssid, tsid, tclass);
-		avc_node_populate(node, ssid, tsid, tclass, ae);
+		avc_node_populate(node, ssid, tsid, tclass, avd);
 
 		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
 		list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
@@ -777,7 +777,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
 	 * Copy and replace original node.
 	 */
 
-	avc_node_populate(node, ssid, tsid, tclass, &orig->ae);
+	avc_node_populate(node, ssid, tsid, tclass, &orig->ae.avd);
 
 	switch (event) {
 	case AVC_CALLBACK_GRANT:
@@ -869,10 +869,10 @@ int avc_ss_reset(u32 seqno)
 int avc_has_perm_noaudit(u32 ssid, u32 tsid,
 			 u16 tclass, u32 requested,
 			 unsigned flags,
-			 struct av_decision *avd)
+			 struct av_decision *in_avd)
 {
 	struct avc_node *node;
-	struct avc_entry entry, *p_ae;
+	struct av_decision avd_entry, *avd;
 	int rc = 0;
 	u32 denied;
 
@@ -883,26 +883,31 @@ int avc_has_perm_noaudit(u32 ssid, u32 tsid,
 	node = avc_lookup(ssid, tsid, tclass, requested);
 	if (!node) {
 		rcu_read_unlock();
-		rc = security_compute_av(ssid, tsid, tclass, requested, &entry.avd);
+
+		if (in_avd)
+			avd = in_avd;
+		else
+			avd = &avd_entry;
+
+		rc = security_compute_av(ssid, tsid, tclass, requested, avd);
 		if (rc)
 			goto out;
 		rcu_read_lock();
-		node = avc_insert(ssid, tsid, tclass, &entry);
+		node = avc_insert(ssid, tsid, tclass, avd);
+	} else {
+		if (in_avd)
+			memcpy(in_avd, &node->ae.avd, sizeof(*in_avd));
+		avd = &node->ae.avd;
 	}
 
-	p_ae = node ? &node->ae : &entry;
-
-	if (avd)
-		memcpy(avd, &p_ae->avd, sizeof(*avd));
-
-	denied = requested & ~(p_ae->avd.allowed);
+	denied = requested & ~(avd->allowed);
 
 	if (denied) {
 		if (flags & AVC_STRICT)
 			rc = -EACCES;
 		else if (!selinux_enforcing || security_permissive_sid(ssid))
 			avc_update_node(AVC_CALLBACK_GRANT, requested, ssid,
-					tsid, tclass, p_ae->avd.seqno);
+					tsid, tclass, avd->seqno);
 		else
 			rc = -EACCES;
 	}


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 2/5] SELinux: more careful use of avd in avc_has_perm_noaudit

[Paul Moore]

On Thursday 12 February 2009 02:50:49 pm Eric Paris wrote:
> we are often needlessly jumping through hoops when it comes to avd
> entries in avc_has_perm_noaudit and we have extra initialization and memcpy
> which are just wasting performance.  Try to clean the function up a bit.
>
> This patch resulted in a 13% drop in time spent in avc_has_perm_noaudit in
> my oprofile sampling of a tbench benchmark.
>
> Signed-off-by: Eric Paris <eparis@redhat.com>

Looks fine to me, some more not-your-fault comments below.

Reviewed-by: Paul Moore <paul.moore@hp.com>

>  static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16
> tclass) @@ -440,31 +440,31 @@ static int avc_latest_notif_update(int seqno,
> int is_insert) * @ssid: source security identifier
>   * @tsid: target security identifier
>   * @tclass: target security class
> - * @ae: AVC entry
> + * @avd: resulting av decision
>   *
>   * Insert an AVC entry for the SID pair
>   * (@ssid, @tsid) and class @tclass.
>   * The access vectors and the sequence number are
>   * normally provided by the security server in
>   * response to a security_compute_av() call.  If the
> - * sequence number @ae->avd.seqno is not less than the latest
> + * sequence number @avd->seqno is not less than the latest
>   * revocation notification, then the function copies
>   * the access vectors into a cache entry, returns
>   * avc_node inserted. Otherwise, this function returns NULL.
>   */
> -static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct
> avc_entry *ae) +static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16
> tclass, struct av_decision *avd) {
>  	struct avc_node *pos, *node = NULL;
>  	int hvalue;
>  	unsigned long flag;
>
> -	if (avc_latest_notif_update(ae->avd.seqno, 1))
> +	if (avc_latest_notif_update(avd->seqno, 1))
>  		goto out;

Not your fault but why not change the "goto out;" to "return NULL;" and get 
rid of the "out" label.

>  	node = avc_alloc_node();
>  	if (node) {

Hmm, while you're at it how about converting to ...

	node = avc_alloc_node();
	if (node == NULL)
		return NULL;

... this seems to be a better fit with the "best practices" and it makes the 
code a bit more tidy (especially the "found" label, you could probably rename 
that to "out" ;) ).

>  		hvalue = avc_hash(ssid, tsid, tclass);
> -		avc_node_populate(node, ssid, tsid, tclass, ae);
> +		avc_node_populate(node, ssid, tsid, tclass, avd);
>
>  		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
>  		list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {

-- 
paul moore
linux @ hp


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 2/5] SELinux: more careful use of avd in avc_has_perm_noaudit

[Stephen Smalley]

On Thu, 2009-02-12 at 14:50 -0500, Eric Paris wrote:
> we are often needlessly jumping through hoops when it comes to avd
> entries in avc_has_perm_noaudit and we have extra initialization and memcpy
> which are just wasting performance.  Try to clean the function up a bit.
> 
> This patch resulted in a 13% drop in time spent in avc_has_perm_noaudit in my
> oprofile sampling of a tbench benchmark.

Further improvement might be to eliminate the need to return an avd at
all from avc_has_perm_noaudit(); there is only one user left and that
could be handled inside of avc_has_perm if it just passed in a flag
indicating audit vs no-audit (as in the original AVC).

> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Acked-by:  Stephen Smalley <sds@tycho.nsa.gov>

> ---
> 
>  security/selinux/avc.c |   43 ++++++++++++++++++++++++-------------------
>  1 files changed, 24 insertions(+), 19 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index abfe378..332c3cd 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -355,12 +355,12 @@ out:
>  	return node;
>  }
>  
> -static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
> +static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct av_decision *avd)
>  {
>  	node->ae.ssid = ssid;
>  	node->ae.tsid = tsid;
>  	node->ae.tclass = tclass;
> -	memcpy(&node->ae.avd, &ae->avd, sizeof(node->ae.avd));
> +	memcpy(&node->ae.avd, avd, sizeof(node->ae.avd));
>  }
>  
>  static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
> @@ -440,31 +440,31 @@ static int avc_latest_notif_update(int seqno, int is_insert)
>   * @ssid: source security identifier
>   * @tsid: target security identifier
>   * @tclass: target security class
> - * @ae: AVC entry
> + * @avd: resulting av decision
>   *
>   * Insert an AVC entry for the SID pair
>   * (@ssid, @tsid) and class @tclass.
>   * The access vectors and the sequence number are
>   * normally provided by the security server in
>   * response to a security_compute_av() call.  If the
> - * sequence number @ae->avd.seqno is not less than the latest
> + * sequence number @avd->seqno is not less than the latest
>   * revocation notification, then the function copies
>   * the access vectors into a cache entry, returns
>   * avc_node inserted. Otherwise, this function returns NULL.
>   */
> -static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
> +static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_decision *avd)
>  {
>  	struct avc_node *pos, *node = NULL;
>  	int hvalue;
>  	unsigned long flag;
>  
> -	if (avc_latest_notif_update(ae->avd.seqno, 1))
> +	if (avc_latest_notif_update(avd->seqno, 1))
>  		goto out;
>  
>  	node = avc_alloc_node();
>  	if (node) {
>  		hvalue = avc_hash(ssid, tsid, tclass);
> -		avc_node_populate(node, ssid, tsid, tclass, ae);
> +		avc_node_populate(node, ssid, tsid, tclass, avd);
>  
>  		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
>  		list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
> @@ -777,7 +777,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  	 * Copy and replace original node.
>  	 */
>  
> -	avc_node_populate(node, ssid, tsid, tclass, &orig->ae);
> +	avc_node_populate(node, ssid, tsid, tclass, &orig->ae.avd);
>  
>  	switch (event) {
>  	case AVC_CALLBACK_GRANT:
> @@ -869,10 +869,10 @@ int avc_ss_reset(u32 seqno)
>  int avc_has_perm_noaudit(u32 ssid, u32 tsid,
>  			 u16 tclass, u32 requested,
>  			 unsigned flags,
> -			 struct av_decision *avd)
> +			 struct av_decision *in_avd)
>  {
>  	struct avc_node *node;
> -	struct avc_entry entry, *p_ae;
> +	struct av_decision avd_entry, *avd;
>  	int rc = 0;
>  	u32 denied;
>  
> @@ -883,26 +883,31 @@ int avc_has_perm_noaudit(u32 ssid, u32 tsid,
>  	node = avc_lookup(ssid, tsid, tclass, requested);
>  	if (!node) {
>  		rcu_read_unlock();
> -		rc = security_compute_av(ssid, tsid, tclass, requested, &entry.avd);
> +
> +		if (in_avd)
> +			avd = in_avd;
> +		else
> +			avd = &avd_entry;
> +
> +		rc = security_compute_av(ssid, tsid, tclass, requested, avd);
>  		if (rc)
>  			goto out;
>  		rcu_read_lock();
> -		node = avc_insert(ssid, tsid, tclass, &entry);
> +		node = avc_insert(ssid, tsid, tclass, avd);
> +	} else {
> +		if (in_avd)
> +			memcpy(in_avd, &node->ae.avd, sizeof(*in_avd));
> +		avd = &node->ae.avd;
>  	}
>  
> -	p_ae = node ? &node->ae : &entry;
> -
> -	if (avd)
> -		memcpy(avd, &p_ae->avd, sizeof(*avd));
> -
> -	denied = requested & ~(p_ae->avd.allowed);
> +	denied = requested & ~(avd->allowed);
>  
>  	if (denied) {
>  		if (flags & AVC_STRICT)
>  			rc = -EACCES;
>  		else if (!selinux_enforcing || security_permissive_sid(ssid))
>  			avc_update_node(AVC_CALLBACK_GRANT, requested, ssid,
> -					tsid, tclass, p_ae->avd.seqno);
> +					tsid, tclass, avd->seqno);
>  		else
>  			rc = -EACCES;
>  	}
-- 
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 majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 2/5] SELinux: more careful use of avd in avc_has_perm_noaudit

[James Morris]

On Thu, 12 Feb 2009, Eric Paris wrote:

> we are often needlessly jumping through hoops when it comes to avd
> entries in avc_has_perm_noaudit and we have extra initialization and memcpy
> which are just wasting performance.  Try to clean the function up a bit.
> 
> This patch resulted in a 13% drop in time spent in avc_has_perm_noaudit in my
> oprofile sampling of a tbench benchmark.
> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Applied.

> ---
> 
>  security/selinux/avc.c |   43 ++++++++++++++++++++++++-------------------
>  1 files changed, 24 insertions(+), 19 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index abfe378..332c3cd 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -355,12 +355,12 @@ out:
>  	return node;
>  }
>  
> -static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
> +static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct av_decision *avd)
>  {
>  	node->ae.ssid = ssid;
>  	node->ae.tsid = tsid;
>  	node->ae.tclass = tclass;
> -	memcpy(&node->ae.avd, &ae->avd, sizeof(node->ae.avd));
> +	memcpy(&node->ae.avd, avd, sizeof(node->ae.avd));
>  }
>  
>  static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
> @@ -440,31 +440,31 @@ static int avc_latest_notif_update(int seqno, int is_insert)
>   * @ssid: source security identifier
>   * @tsid: target security identifier
>   * @tclass: target security class
> - * @ae: AVC entry
> + * @avd: resulting av decision
>   *
>   * Insert an AVC entry for the SID pair
>   * (@ssid, @tsid) and class @tclass.
>   * The access vectors and the sequence number are
>   * normally provided by the security server in
>   * response to a security_compute_av() call.  If the
> - * sequence number @ae->avd.seqno is not less than the latest
> + * sequence number @avd->seqno is not less than the latest
>   * revocation notification, then the function copies
>   * the access vectors into a cache entry, returns
>   * avc_node inserted. Otherwise, this function returns NULL.
>   */
> -static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
> +static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_decision *avd)
>  {
>  	struct avc_node *pos, *node = NULL;
>  	int hvalue;
>  	unsigned long flag;
>  
> -	if (avc_latest_notif_update(ae->avd.seqno, 1))
> +	if (avc_latest_notif_update(avd->seqno, 1))
>  		goto out;
>  
>  	node = avc_alloc_node();
>  	if (node) {
>  		hvalue = avc_hash(ssid, tsid, tclass);
> -		avc_node_populate(node, ssid, tsid, tclass, ae);
> +		avc_node_populate(node, ssid, tsid, tclass, avd);
>  
>  		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
>  		list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
> @@ -777,7 +777,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  	 * Copy and replace original node.
>  	 */
>  
> -	avc_node_populate(node, ssid, tsid, tclass, &orig->ae);
> +	avc_node_populate(node, ssid, tsid, tclass, &orig->ae.avd);
>  
>  	switch (event) {
>  	case AVC_CALLBACK_GRANT:
> @@ -869,10 +869,10 @@ int avc_ss_reset(u32 seqno)
>  int avc_has_perm_noaudit(u32 ssid, u32 tsid,
>  			 u16 tclass, u32 requested,
>  			 unsigned flags,
> -			 struct av_decision *avd)
> +			 struct av_decision *in_avd)
>  {
>  	struct avc_node *node;
> -	struct avc_entry entry, *p_ae;
> +	struct av_decision avd_entry, *avd;
>  	int rc = 0;
>  	u32 denied;
>  
> @@ -883,26 +883,31 @@ int avc_has_perm_noaudit(u32 ssid, u32 tsid,
>  	node = avc_lookup(ssid, tsid, tclass, requested);
>  	if (!node) {
>  		rcu_read_unlock();
> -		rc = security_compute_av(ssid, tsid, tclass, requested, &entry.avd);
> +
> +		if (in_avd)
> +			avd = in_avd;
> +		else
> +			avd = &avd_entry;
> +
> +		rc = security_compute_av(ssid, tsid, tclass, requested, avd);
>  		if (rc)
>  			goto out;
>  		rcu_read_lock();
> -		node = avc_insert(ssid, tsid, tclass, &entry);
> +		node = avc_insert(ssid, tsid, tclass, avd);
> +	} else {
> +		if (in_avd)
> +			memcpy(in_avd, &node->ae.avd, sizeof(*in_avd));
> +		avd = &node->ae.avd;
>  	}
>  
> -	p_ae = node ? &node->ae : &entry;
> -
> -	if (avd)
> -		memcpy(avd, &p_ae->avd, sizeof(*avd));
> -
> -	denied = requested & ~(p_ae->avd.allowed);
> +	denied = requested & ~(avd->allowed);
>  
>  	if (denied) {
>  		if (flags & AVC_STRICT)
>  			rc = -EACCES;
>  		else if (!selinux_enforcing || security_permissive_sid(ssid))
>  			avc_update_node(AVC_CALLBACK_GRANT, requested, ssid,
> -					tsid, tclass, p_ae->avd.seqno);
> +					tsid, tclass, avd->seqno);
>  		else
>  			rc = -EACCES;
>  	}
> 

-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[PATCH 3/5] SELinux: remove unused av.decided field

[Eric Paris]

It appears there was an intention to have the security server only decide
certain permissions and leave other for later as some sort of a portential
performance win.  We are currently always deciding all 32 bits of
permissions and this is a useless couple of branches and wasted space.
This patch completely drops the av.decided concept.

This in a 17% reduction in the time spent in avc_has_perm_noaudit
based on oprofile sampling of a tbench benchmark.

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 security/selinux/avc.c              |   15 +++++----------
 security/selinux/include/security.h |    1 -
 security/selinux/selinuxfs.c        |    2 +-
 security/selinux/ss/services.c      |    2 --
 4 files changed, 6 insertions(+), 14 deletions(-)

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index 332c3cd..e9ccacd 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -386,30 +386,25 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
  * @ssid: source security identifier
  * @tsid: target security identifier
  * @tclass: target security class
- * @requested: requested permissions, interpreted based on @tclass
  *
  * Look up an AVC entry that is valid for the
- * @requested permissions between the SID pair
  * (@ssid, @tsid), interpreting the permissions
  * based on @tclass.  If a valid AVC entry exists,
  * then this function return the avc_node.
  * Otherwise, this function returns NULL.
  */
-static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass, u32 requested)
+static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass)
 {
 	struct avc_node *node;
 
 	avc_cache_stats_incr(lookups);
 	node = avc_search_node(ssid, tsid, tclass);
 
-	if (node && ((node->ae.avd.decided & requested) == requested)) {
+	if (node)
 		avc_cache_stats_incr(hits);
-		goto out;
-	}
+	else
+		avc_cache_stats_incr(misses);
 
-	node = NULL;
-	avc_cache_stats_incr(misses);
-out:
 	return node;
 }
 
@@ -880,7 +875,7 @@ int avc_has_perm_noaudit(u32 ssid, u32 tsid,
 
 	rcu_read_lock();
 
-	node = avc_lookup(ssid, tsid, tclass, requested);
+	node = avc_lookup(ssid, tsid, tclass);
 	if (!node) {
 		rcu_read_unlock();
 
diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index e1d9db7..5c3434f 100644
--- a/security/selinux/include/security.h
+++ b/security/selinux/include/security.h
@@ -88,7 +88,6 @@ int security_policycap_supported(unsigned int req_cap);
 #define SEL_VEC_MAX 32
 struct av_decision {
 	u32 allowed;
-	u32 decided;
 	u32 auditallow;
 	u32 auditdeny;
 	u32 seqno;
diff --git a/security/selinux/selinuxfs.c b/security/selinux/selinuxfs.c
index 214f53c..2d5136e 100644
--- a/security/selinux/selinuxfs.c
+++ b/security/selinux/selinuxfs.c
@@ -528,7 +528,7 @@ static ssize_t sel_write_access(struct file *file, char *buf, size_t size)
 
 	length = scnprintf(buf, SIMPLE_TRANSACTION_LIMIT,
 			  "%x %x %x %x %u",
-			  avd.allowed, avd.decided,
+			  avd.allowed, 0xffffffff,
 			  avd.auditallow, avd.auditdeny,
 			  avd.seqno);
 out2:
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 6e0651a..c6a8f68 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -416,7 +416,6 @@ static int context_struct_compute_av(struct context *scontext,
 	 * Initialize the access vectors to the default values.
 	 */
 	avd->allowed = 0;
-	avd->decided = 0xffffffff;
 	avd->auditallow = 0;
 	avd->auditdeny = 0xffffffff;
 	avd->seqno = latest_granting;
@@ -761,7 +760,6 @@ int security_compute_av(u32 ssid,
 
 	if (!ss_initialized) {
 		avd->allowed = 0xffffffff;
-		avd->decided = 0xffffffff;
 		avd->auditallow = 0;
 		avd->auditdeny = 0xffffffff;
 		avd->seqno = latest_granting;


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 3/5] SELinux: remove unused av.decided field

[Paul Moore]

On Thursday 12 February 2009 02:50:54 pm Eric Paris wrote:
> It appears there was an intention to have the security server only decide
> certain permissions and leave other for later as some sort of a portential
> performance win.  We are currently always deciding all 32 bits of
> permissions and this is a useless couple of branches and wasted space.
> This patch completely drops the av.decided concept.
>
> This in a 17% reduction in the time spent in avc_has_perm_noaudit
> based on oprofile sampling of a tbench benchmark.
>
> Signed-off-by: Eric Paris <eparis@redhat.com>

No comments at all this time ;)

Reviewed-by: Paul Moore <paul.moore@hp.com>

-- 
paul moore
linux @ hp


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 3/5] SELinux: remove unused av.decided field

[Stephen Smalley]

On Thu, 2009-02-12 at 14:50 -0500, Eric Paris wrote:
> It appears there was an intention to have the security server only decide
> certain permissions and leave other for later as some sort of a portential
> performance win.  We are currently always deciding all 32 bits of
> permissions and this is a useless couple of branches and wasted space.
> This patch completely drops the av.decided concept.

Historical note:  The decided vector was to support history-based
policies, not as a potential performance optimization.

> 
> This in a 17% reduction in the time spent in avc_has_perm_noaudit
> based on oprofile sampling of a tbench benchmark.
> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Acked-by:  Stephen Smalley <sds@tycho.nsa.gov>

> ---
> 
>  security/selinux/avc.c              |   15 +++++----------
>  security/selinux/include/security.h |    1 -
>  security/selinux/selinuxfs.c        |    2 +-
>  security/selinux/ss/services.c      |    2 --
>  4 files changed, 6 insertions(+), 14 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index 332c3cd..e9ccacd 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -386,30 +386,25 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
>   * @ssid: source security identifier
>   * @tsid: target security identifier
>   * @tclass: target security class
> - * @requested: requested permissions, interpreted based on @tclass
>   *
>   * Look up an AVC entry that is valid for the
> - * @requested permissions between the SID pair
>   * (@ssid, @tsid), interpreting the permissions
>   * based on @tclass.  If a valid AVC entry exists,
>   * then this function return the avc_node.
>   * Otherwise, this function returns NULL.
>   */
> -static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass, u32 requested)
> +static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass)
>  {
>  	struct avc_node *node;
>  
>  	avc_cache_stats_incr(lookups);
>  	node = avc_search_node(ssid, tsid, tclass);
>  
> -	if (node && ((node->ae.avd.decided & requested) == requested)) {
> +	if (node)
>  		avc_cache_stats_incr(hits);
> -		goto out;
> -	}
> +	else
> +		avc_cache_stats_incr(misses);
>  
> -	node = NULL;
> -	avc_cache_stats_incr(misses);
> -out:
>  	return node;
>  }
>  
> @@ -880,7 +875,7 @@ int avc_has_perm_noaudit(u32 ssid, u32 tsid,
>  
>  	rcu_read_lock();
>  
> -	node = avc_lookup(ssid, tsid, tclass, requested);
> +	node = avc_lookup(ssid, tsid, tclass);
>  	if (!node) {
>  		rcu_read_unlock();
>  
> diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
> index e1d9db7..5c3434f 100644
> --- a/security/selinux/include/security.h
> +++ b/security/selinux/include/security.h
> @@ -88,7 +88,6 @@ int security_policycap_supported(unsigned int req_cap);
>  #define SEL_VEC_MAX 32
>  struct av_decision {
>  	u32 allowed;
> -	u32 decided;
>  	u32 auditallow;
>  	u32 auditdeny;
>  	u32 seqno;
> diff --git a/security/selinux/selinuxfs.c b/security/selinux/selinuxfs.c
> index 214f53c..2d5136e 100644
> --- a/security/selinux/selinuxfs.c
> +++ b/security/selinux/selinuxfs.c
> @@ -528,7 +528,7 @@ static ssize_t sel_write_access(struct file *file, char *buf, size_t size)
>  
>  	length = scnprintf(buf, SIMPLE_TRANSACTION_LIMIT,
>  			  "%x %x %x %x %u",
> -			  avd.allowed, avd.decided,
> +			  avd.allowed, 0xffffffff,
>  			  avd.auditallow, avd.auditdeny,
>  			  avd.seqno);
>  out2:
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index 6e0651a..c6a8f68 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -416,7 +416,6 @@ static int context_struct_compute_av(struct context *scontext,
>  	 * Initialize the access vectors to the default values.
>  	 */
>  	avd->allowed = 0;
> -	avd->decided = 0xffffffff;
>  	avd->auditallow = 0;
>  	avd->auditdeny = 0xffffffff;
>  	avd->seqno = latest_granting;
> @@ -761,7 +760,6 @@ int security_compute_av(u32 ssid,
>  
>  	if (!ss_initialized) {
>  		avd->allowed = 0xffffffff;
> -		avd->decided = 0xffffffff;
>  		avd->auditallow = 0;
>  		avd->auditdeny = 0xffffffff;
>  		avd->seqno = latest_granting;
-- 
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 majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 3/5] SELinux: remove unused av.decided field

[James Morris]

On Thu, 12 Feb 2009, Eric Paris wrote:

> It appears there was an intention to have the security server only decide
> certain permissions and leave other for later as some sort of a portential
> performance win.  We are currently always deciding all 32 bits of
> permissions and this is a useless couple of branches and wasted space.
> This patch completely drops the av.decided concept.
> 
> This in a 17% reduction in the time spent in avc_has_perm_noaudit
> based on oprofile sampling of a tbench benchmark.
> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Applied.

> ---
> 
>  security/selinux/avc.c              |   15 +++++----------
>  security/selinux/include/security.h |    1 -
>  security/selinux/selinuxfs.c        |    2 +-
>  security/selinux/ss/services.c      |    2 --
>  4 files changed, 6 insertions(+), 14 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index 332c3cd..e9ccacd 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -386,30 +386,25 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
>   * @ssid: source security identifier
>   * @tsid: target security identifier
>   * @tclass: target security class
> - * @requested: requested permissions, interpreted based on @tclass
>   *
>   * Look up an AVC entry that is valid for the
> - * @requested permissions between the SID pair
>   * (@ssid, @tsid), interpreting the permissions
>   * based on @tclass.  If a valid AVC entry exists,
>   * then this function return the avc_node.
>   * Otherwise, this function returns NULL.
>   */
> -static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass, u32 requested)
> +static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass)
>  {
>  	struct avc_node *node;
>  
>  	avc_cache_stats_incr(lookups);
>  	node = avc_search_node(ssid, tsid, tclass);
>  
> -	if (node && ((node->ae.avd.decided & requested) == requested)) {
> +	if (node)
>  		avc_cache_stats_incr(hits);
> -		goto out;
> -	}
> +	else
> +		avc_cache_stats_incr(misses);
>  
> -	node = NULL;
> -	avc_cache_stats_incr(misses);
> -out:
>  	return node;
>  }
>  
> @@ -880,7 +875,7 @@ int avc_has_perm_noaudit(u32 ssid, u32 tsid,
>  
>  	rcu_read_lock();
>  
> -	node = avc_lookup(ssid, tsid, tclass, requested);
> +	node = avc_lookup(ssid, tsid, tclass);
>  	if (!node) {
>  		rcu_read_unlock();
>  
> diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
> index e1d9db7..5c3434f 100644
> --- a/security/selinux/include/security.h
> +++ b/security/selinux/include/security.h
> @@ -88,7 +88,6 @@ int security_policycap_supported(unsigned int req_cap);
>  #define SEL_VEC_MAX 32
>  struct av_decision {
>  	u32 allowed;
> -	u32 decided;
>  	u32 auditallow;
>  	u32 auditdeny;
>  	u32 seqno;
> diff --git a/security/selinux/selinuxfs.c b/security/selinux/selinuxfs.c
> index 214f53c..2d5136e 100644
> --- a/security/selinux/selinuxfs.c
> +++ b/security/selinux/selinuxfs.c
> @@ -528,7 +528,7 @@ static ssize_t sel_write_access(struct file *file, char *buf, size_t size)
>  
>  	length = scnprintf(buf, SIMPLE_TRANSACTION_LIMIT,
>  			  "%x %x %x %x %u",
> -			  avd.allowed, avd.decided,
> +			  avd.allowed, 0xffffffff,
>  			  avd.auditallow, avd.auditdeny,
>  			  avd.seqno);
>  out2:
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index 6e0651a..c6a8f68 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -416,7 +416,6 @@ static int context_struct_compute_av(struct context *scontext,
>  	 * Initialize the access vectors to the default values.
>  	 */
>  	avd->allowed = 0;
> -	avd->decided = 0xffffffff;
>  	avd->auditallow = 0;
>  	avd->auditdeny = 0xffffffff;
>  	avd->seqno = latest_granting;
> @@ -761,7 +760,6 @@ int security_compute_av(u32 ssid,
>  
>  	if (!ss_initialized) {
>  		avd->allowed = 0xffffffff;
> -		avd->decided = 0xffffffff;
>  		avd->auditallow = 0;
>  		avd->auditdeny = 0xffffffff;
>  		avd->seqno = latest_granting;
> 

-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[PATCH 4/5] SELinux: code readability with avc_cache

[Eric Paris]

The code making use of struct avc_cache was not easy to read thanks to liberal
use of &avc_cache.{slots_lock,slots}[hvalue] throughout.  This patch simply
creates local pointers and uses those instead of the long global names.

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 security/selinux/avc.c |   63 ++++++++++++++++++++++++++++++++++--------------
 1 files changed, 44 insertions(+), 19 deletions(-)

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index e9ccacd..ed051d7 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -92,12 +92,12 @@ struct avc_entry {
 
 struct avc_node {
 	struct avc_entry	ae;
-	struct list_head	list;
+	struct list_head	list; /* anchored in avc_cache->slots[i] */
 	struct rcu_head		rhead;
 };
 
 struct avc_cache {
-	struct list_head	slots[AVC_CACHE_SLOTS];
+	struct list_head	slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
 	spinlock_t		slots_lock[AVC_CACHE_SLOTS]; /* lock for writes */
 	atomic_t		lru_hint;	/* LRU hint for reclaim scan */
 	atomic_t		active_nodes;
@@ -254,16 +254,18 @@ int avc_get_hash_stats(char *page)
 {
 	int i, chain_len, max_chain_len, slots_used;
 	struct avc_node *node;
+	struct list_head *head;
 
 	rcu_read_lock();
 
 	slots_used = 0;
 	max_chain_len = 0;
 	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
-		if (!list_empty(&avc_cache.slots[i])) {
+		head = &avc_cache.slots[i];
+		if (!list_empty(head)) {
 			slots_used++;
 			chain_len = 0;
-			list_for_each_entry_rcu(node, &avc_cache.slots[i], list)
+			list_for_each_entry_rcu(node, head, list)
 				chain_len++;
 			if (chain_len > max_chain_len)
 				max_chain_len = chain_len;
@@ -311,26 +313,30 @@ static inline int avc_reclaim_node(void)
 	struct avc_node *node;
 	int hvalue, try, ecx;
 	unsigned long flags;
+	struct list_head *head;
+	spinlock_t *lock;
 
 	for (try = 0, ecx = 0; try < AVC_CACHE_SLOTS; try++) {
 		hvalue = atomic_inc_return(&avc_cache.lru_hint) & (AVC_CACHE_SLOTS - 1);
+		head = &avc_cache.slots[hvalue];
+		lock = &avc_cache.slots_lock[hvalue];
 
-		if (!spin_trylock_irqsave(&avc_cache.slots_lock[hvalue], flags))
+		if (!spin_trylock_irqsave(lock, flags))
 			continue;
 
 		rcu_read_lock();
-		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
+		list_for_each_entry(node, head, list) {
 			avc_node_delete(node);
 			avc_cache_stats_incr(reclaims);
 			ecx++;
 			if (ecx >= AVC_CACHE_RECLAIM) {
 				rcu_read_unlock();
-				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
+				spin_unlock_irqrestore(lock, flags);
 				goto out;
 			}
 		}
 		rcu_read_unlock();
-		spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
+		spin_unlock_irqrestore(lock, flags);
 	}
 out:
 	return ecx;
@@ -367,9 +373,11 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
 {
 	struct avc_node *node, *ret = NULL;
 	int hvalue;
+	struct list_head *head;
 
 	hvalue = avc_hash(ssid, tsid, tclass);
-	list_for_each_entry_rcu(node, &avc_cache.slots[hvalue], list) {
+	head = &avc_cache.slots[hvalue];
+	list_for_each_entry_rcu(node, head, list) {
 		if (ssid == node->ae.ssid &&
 		    tclass == node->ae.tclass &&
 		    tsid == node->ae.tsid) {
@@ -458,11 +466,17 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
 
 	node = avc_alloc_node();
 	if (node) {
+		struct list_head *head;
+		spinlock_t *lock;
+
 		hvalue = avc_hash(ssid, tsid, tclass);
 		avc_node_populate(node, ssid, tsid, tclass, avd);
 
-		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
-		list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
+		head = &avc_cache.slots[hvalue];
+		lock = &avc_cache.slots_lock[hvalue];
+
+		spin_lock_irqsave(lock, flag);
+		list_for_each_entry(pos, head, list) {
 			if (pos->ae.ssid == ssid &&
 			    pos->ae.tsid == tsid &&
 			    pos->ae.tclass == tclass) {
@@ -470,9 +484,9 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
 				goto found;
 			}
 		}
-		list_add_rcu(&node->list, &avc_cache.slots[hvalue]);
+		list_add_rcu(&node->list, head);
 found:
-		spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flag);
+		spin_unlock_irqrestore(lock, flag);
 	}
 out:
 	return node;
@@ -741,6 +755,8 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
 	int hvalue, rc = 0;
 	unsigned long flag;
 	struct avc_node *pos, *node, *orig = NULL;
+	struct list_head *head;
+	spinlock_t *lock;
 
 	node = avc_alloc_node();
 	if (!node) {
@@ -750,9 +766,13 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
 
 	/* Lock the target slot */
 	hvalue = avc_hash(ssid, tsid, tclass);
-	spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
 
-	list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
+	head = &avc_cache.slots[hvalue];
+	lock = &avc_cache.slots_lock[hvalue];
+
+	spin_lock_irqsave(lock, flag);
+
+	list_for_each_entry(pos, head, list) {
 		if (ssid == pos->ae.ssid &&
 		    tsid == pos->ae.tsid &&
 		    tclass == pos->ae.tclass &&
@@ -797,7 +817,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
 	}
 	avc_node_replace(node, orig);
 out_unlock:
-	spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flag);
+	spin_unlock_irqrestore(lock, flag);
 out:
 	return rc;
 }
@@ -812,18 +832,23 @@ int avc_ss_reset(u32 seqno)
 	int i, rc = 0, tmprc;
 	unsigned long flag;
 	struct avc_node *node;
+	struct list_head *head;
+	spinlock_t *lock;
 
 	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
-		spin_lock_irqsave(&avc_cache.slots_lock[i], flag);
+		head = &avc_cache.slots[i];
+		lock = &avc_cache.slots_lock[i];
+
+		spin_lock_irqsave(lock, flag);
 		/*
 		 * With preemptable RCU, the outer spinlock does not
 		 * prevent RCU grace periods from ending.
 		 */
 		rcu_read_lock();
-		list_for_each_entry(node, &avc_cache.slots[i], list)
+		list_for_each_entry(node, head, list)
 			avc_node_delete(node);
 		rcu_read_unlock();
-		spin_unlock_irqrestore(&avc_cache.slots_lock[i], flag);
+		spin_unlock_irqrestore(lock, flag);
 	}
 
 	for (c = avc_callbacks; c; c = c->next) {


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 4/5] SELinux: code readability with avc_cache

[Paul Moore]

On Thursday 12 February 2009 02:50:59 pm Eric Paris wrote:
> The code making use of struct avc_cache was not easy to read thanks to
> liberal use of &avc_cache.{slots_lock,slots}[hvalue] throughout.  This
> patch simply creates local pointers and uses those instead of the long
> global names.
>
> Signed-off-by: Eric Paris <eparis@redhat.com>

If you're going to make these changes you might as well fixup the issues I 
mentioned earlier :)

> @@ -311,26 +313,30 @@ static inline int avc_reclaim_node(void)
>  	struct avc_node *node;
>  	int hvalue, try, ecx;
>  	unsigned long flags;
> +	struct list_head *head;
> +	spinlock_t *lock;
>
>  	for (try = 0, ecx = 0; try < AVC_CACHE_SLOTS; try++) {
>  		hvalue = atomic_inc_return(&avc_cache.lru_hint) & (AVC_CACHE_SLOTS - 1);

See previous comments about getting rid of lru_hint and replacing this hvalue 
with 0.

> @@ -458,11 +466,17 @@ static struct avc_node *avc_insert(u32 ssid, u32
> tsid, u16 tclass, struct av_dec
>
>  	node = avc_alloc_node();
>  	if (node) {
> +		struct list_head *head;
> +		spinlock_t *lock;
> +

Yeah, definitely convert this "if (..." like I mentioned earlier.

-- 
paul moore
linux @ hp


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 4/5] SELinux: code readability with avc_cache

[James Morris]

On Thu, 12 Feb 2009, Eric Paris wrote:

> The code making use of struct avc_cache was not easy to read thanks to liberal
> use of &avc_cache.{slots_lock,slots}[hvalue] throughout.  This patch simply
> creates local pointers and uses those instead of the long global names.
> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Applied.

> ---
> 
>  security/selinux/avc.c |   63 ++++++++++++++++++++++++++++++++++--------------
>  1 files changed, 44 insertions(+), 19 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index e9ccacd..ed051d7 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -92,12 +92,12 @@ struct avc_entry {
>  
>  struct avc_node {
>  	struct avc_entry	ae;
> -	struct list_head	list;
> +	struct list_head	list; /* anchored in avc_cache->slots[i] */
>  	struct rcu_head		rhead;
>  };
>  
>  struct avc_cache {
> -	struct list_head	slots[AVC_CACHE_SLOTS];
> +	struct list_head	slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
>  	spinlock_t		slots_lock[AVC_CACHE_SLOTS]; /* lock for writes */
>  	atomic_t		lru_hint;	/* LRU hint for reclaim scan */
>  	atomic_t		active_nodes;
> @@ -254,16 +254,18 @@ int avc_get_hash_stats(char *page)
>  {
>  	int i, chain_len, max_chain_len, slots_used;
>  	struct avc_node *node;
> +	struct list_head *head;
>  
>  	rcu_read_lock();
>  
>  	slots_used = 0;
>  	max_chain_len = 0;
>  	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
> -		if (!list_empty(&avc_cache.slots[i])) {
> +		head = &avc_cache.slots[i];
> +		if (!list_empty(head)) {
>  			slots_used++;
>  			chain_len = 0;
> -			list_for_each_entry_rcu(node, &avc_cache.slots[i], list)
> +			list_for_each_entry_rcu(node, head, list)
>  				chain_len++;
>  			if (chain_len > max_chain_len)
>  				max_chain_len = chain_len;
> @@ -311,26 +313,30 @@ static inline int avc_reclaim_node(void)
>  	struct avc_node *node;
>  	int hvalue, try, ecx;
>  	unsigned long flags;
> +	struct list_head *head;
> +	spinlock_t *lock;
>  
>  	for (try = 0, ecx = 0; try < AVC_CACHE_SLOTS; try++) {
>  		hvalue = atomic_inc_return(&avc_cache.lru_hint) & (AVC_CACHE_SLOTS - 1);
> +		head = &avc_cache.slots[hvalue];
> +		lock = &avc_cache.slots_lock[hvalue];
>  
> -		if (!spin_trylock_irqsave(&avc_cache.slots_lock[hvalue], flags))
> +		if (!spin_trylock_irqsave(lock, flags))
>  			continue;
>  
>  		rcu_read_lock();
> -		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
> +		list_for_each_entry(node, head, list) {
>  			avc_node_delete(node);
>  			avc_cache_stats_incr(reclaims);
>  			ecx++;
>  			if (ecx >= AVC_CACHE_RECLAIM) {
>  				rcu_read_unlock();
> -				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> +				spin_unlock_irqrestore(lock, flags);
>  				goto out;
>  			}
>  		}
>  		rcu_read_unlock();
> -		spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> +		spin_unlock_irqrestore(lock, flags);
>  	}
>  out:
>  	return ecx;
> @@ -367,9 +373,11 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
>  {
>  	struct avc_node *node, *ret = NULL;
>  	int hvalue;
> +	struct list_head *head;
>  
>  	hvalue = avc_hash(ssid, tsid, tclass);
> -	list_for_each_entry_rcu(node, &avc_cache.slots[hvalue], list) {
> +	head = &avc_cache.slots[hvalue];
> +	list_for_each_entry_rcu(node, head, list) {
>  		if (ssid == node->ae.ssid &&
>  		    tclass == node->ae.tclass &&
>  		    tsid == node->ae.tsid) {
> @@ -458,11 +466,17 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
>  
>  	node = avc_alloc_node();
>  	if (node) {
> +		struct list_head *head;
> +		spinlock_t *lock;
> +
>  		hvalue = avc_hash(ssid, tsid, tclass);
>  		avc_node_populate(node, ssid, tsid, tclass, avd);
>  
> -		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
> -		list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
> +		head = &avc_cache.slots[hvalue];
> +		lock = &avc_cache.slots_lock[hvalue];
> +
> +		spin_lock_irqsave(lock, flag);
> +		list_for_each_entry(pos, head, list) {
>  			if (pos->ae.ssid == ssid &&
>  			    pos->ae.tsid == tsid &&
>  			    pos->ae.tclass == tclass) {
> @@ -470,9 +484,9 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
>  				goto found;
>  			}
>  		}
> -		list_add_rcu(&node->list, &avc_cache.slots[hvalue]);
> +		list_add_rcu(&node->list, head);
>  found:
> -		spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flag);
> +		spin_unlock_irqrestore(lock, flag);
>  	}
>  out:
>  	return node;
> @@ -741,6 +755,8 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  	int hvalue, rc = 0;
>  	unsigned long flag;
>  	struct avc_node *pos, *node, *orig = NULL;
> +	struct list_head *head;
> +	spinlock_t *lock;
>  
>  	node = avc_alloc_node();
>  	if (!node) {
> @@ -750,9 +766,13 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  
>  	/* Lock the target slot */
>  	hvalue = avc_hash(ssid, tsid, tclass);
> -	spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
>  
> -	list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
> +	head = &avc_cache.slots[hvalue];
> +	lock = &avc_cache.slots_lock[hvalue];
> +
> +	spin_lock_irqsave(lock, flag);
> +
> +	list_for_each_entry(pos, head, list) {
>  		if (ssid == pos->ae.ssid &&
>  		    tsid == pos->ae.tsid &&
>  		    tclass == pos->ae.tclass &&
> @@ -797,7 +817,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  	}
>  	avc_node_replace(node, orig);
>  out_unlock:
> -	spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flag);
> +	spin_unlock_irqrestore(lock, flag);
>  out:
>  	return rc;
>  }
> @@ -812,18 +832,23 @@ int avc_ss_reset(u32 seqno)
>  	int i, rc = 0, tmprc;
>  	unsigned long flag;
>  	struct avc_node *node;
> +	struct list_head *head;
> +	spinlock_t *lock;
>  
>  	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
> -		spin_lock_irqsave(&avc_cache.slots_lock[i], flag);
> +		head = &avc_cache.slots[i];
> +		lock = &avc_cache.slots_lock[i];
> +
> +		spin_lock_irqsave(lock, flag);
>  		/*
>  		 * With preemptable RCU, the outer spinlock does not
>  		 * prevent RCU grace periods from ending.
>  		 */
>  		rcu_read_lock();
> -		list_for_each_entry(node, &avc_cache.slots[i], list)
> +		list_for_each_entry(node, head, list)
>  			avc_node_delete(node);
>  		rcu_read_unlock();
> -		spin_unlock_irqrestore(&avc_cache.slots_lock[i], flag);
> +		spin_unlock_irqrestore(lock, flag);
>  	}
>  
>  	for (c = avc_callbacks; c; c = c->next) {
> 

-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[PATCH 5/5] SELinux: convert the avc cache hash list to an hlist

[Eric Paris]

We do not need O(1) access to the tail of the avc cache lists and so we are
wasting lots of space using struct list_head instead of struct hlist_head.
This patch converts the avc cache to use hlists in which there is a single
pointer from the head which saves us about 4k of global memory.

Resulted in about a 1.5% decrease in time spent in avc_has_perm_noaudit based
on oprofile sampling of tbench.  Although likely within the noise....

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 security/selinux/avc.c |   47 +++++++++++++++++++++++++++--------------------
 1 files changed, 27 insertions(+), 20 deletions(-)

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index ed051d7..cc83acd 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -92,12 +92,12 @@ struct avc_entry {
 
 struct avc_node {
 	struct avc_entry	ae;
-	struct list_head	list; /* anchored in avc_cache->slots[i] */
+	struct hlist_node	list; /* anchored in avc_cache->slots[i] */
 	struct rcu_head		rhead;
 };
 
 struct avc_cache {
-	struct list_head	slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
+	struct hlist_head	slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
 	spinlock_t		slots_lock[AVC_CACHE_SLOTS]; /* lock for writes */
 	atomic_t		lru_hint;	/* LRU hint for reclaim scan */
 	atomic_t		active_nodes;
@@ -238,7 +238,7 @@ void __init avc_init(void)
 	int i;
 
 	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
-		INIT_LIST_HEAD(&avc_cache.slots[i]);
+		INIT_HLIST_HEAD(&avc_cache.slots[i]);
 		spin_lock_init(&avc_cache.slots_lock[i]);
 	}
 	atomic_set(&avc_cache.active_nodes, 0);
@@ -254,7 +254,7 @@ int avc_get_hash_stats(char *page)
 {
 	int i, chain_len, max_chain_len, slots_used;
 	struct avc_node *node;
-	struct list_head *head;
+	struct hlist_head *head;
 
 	rcu_read_lock();
 
@@ -262,10 +262,12 @@ int avc_get_hash_stats(char *page)
 	max_chain_len = 0;
 	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
 		head = &avc_cache.slots[i];
-		if (!list_empty(head)) {
+		if (!hlist_empty(head)) {
+			struct hlist_node *next;
+
 			slots_used++;
 			chain_len = 0;
-			list_for_each_entry_rcu(node, head, list)
+			hlist_for_each_entry_rcu(node, next, head, list)
 				chain_len++;
 			if (chain_len > max_chain_len)
 				max_chain_len = chain_len;
@@ -289,7 +291,7 @@ static void avc_node_free(struct rcu_head *rhead)
 
 static void avc_node_delete(struct avc_node *node)
 {
-	list_del_rcu(&node->list);
+	hlist_del_rcu(&node->list);
 	call_rcu(&node->rhead, avc_node_free);
 	atomic_dec(&avc_cache.active_nodes);
 }
@@ -303,7 +305,7 @@ static void avc_node_kill(struct avc_node *node)
 
 static void avc_node_replace(struct avc_node *new, struct avc_node *old)
 {
-	list_replace_rcu(&old->list, &new->list);
+	hlist_replace_rcu(&old->list, &new->list);
 	call_rcu(&old->rhead, avc_node_free);
 	atomic_dec(&avc_cache.active_nodes);
 }
@@ -313,7 +315,8 @@ static inline int avc_reclaim_node(void)
 	struct avc_node *node;
 	int hvalue, try, ecx;
 	unsigned long flags;
-	struct list_head *head;
+	struct hlist_head *head;
+	struct hlist_node *next;
 	spinlock_t *lock;
 
 	for (try = 0, ecx = 0; try < AVC_CACHE_SLOTS; try++) {
@@ -325,7 +328,7 @@ static inline int avc_reclaim_node(void)
 			continue;
 
 		rcu_read_lock();
-		list_for_each_entry(node, head, list) {
+		hlist_for_each_entry(node, next, head, list) {
 			avc_node_delete(node);
 			avc_cache_stats_incr(reclaims);
 			ecx++;
@@ -351,7 +354,7 @@ static struct avc_node *avc_alloc_node(void)
 		goto out;
 
 	INIT_RCU_HEAD(&node->rhead);
-	INIT_LIST_HEAD(&node->list);
+	INIT_HLIST_NODE(&node->list);
 	avc_cache_stats_incr(allocations);
 
 	if (atomic_inc_return(&avc_cache.active_nodes) > avc_cache_threshold)
@@ -373,11 +376,12 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
 {
 	struct avc_node *node, *ret = NULL;
 	int hvalue;
-	struct list_head *head;
+	struct hlist_head *head;
+	struct hlist_node *next;
 
 	hvalue = avc_hash(ssid, tsid, tclass);
 	head = &avc_cache.slots[hvalue];
-	list_for_each_entry_rcu(node, head, list) {
+	hlist_for_each_entry_rcu(node, next, head, list) {
 		if (ssid == node->ae.ssid &&
 		    tclass == node->ae.tclass &&
 		    tsid == node->ae.tsid) {
@@ -466,7 +470,8 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
 
 	node = avc_alloc_node();
 	if (node) {
-		struct list_head *head;
+		struct hlist_head *head;
+		struct hlist_node *next;
 		spinlock_t *lock;
 
 		hvalue = avc_hash(ssid, tsid, tclass);
@@ -476,7 +481,7 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
 		lock = &avc_cache.slots_lock[hvalue];
 
 		spin_lock_irqsave(lock, flag);
-		list_for_each_entry(pos, head, list) {
+		hlist_for_each_entry(pos, next, head, list) {
 			if (pos->ae.ssid == ssid &&
 			    pos->ae.tsid == tsid &&
 			    pos->ae.tclass == tclass) {
@@ -484,7 +489,7 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
 				goto found;
 			}
 		}
-		list_add_rcu(&node->list, head);
+		hlist_add_head_rcu(&node->list, head);
 found:
 		spin_unlock_irqrestore(lock, flag);
 	}
@@ -755,7 +760,8 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
 	int hvalue, rc = 0;
 	unsigned long flag;
 	struct avc_node *pos, *node, *orig = NULL;
-	struct list_head *head;
+	struct hlist_head *head;
+	struct hlist_node *next;
 	spinlock_t *lock;
 
 	node = avc_alloc_node();
@@ -772,7 +778,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
 
 	spin_lock_irqsave(lock, flag);
 
-	list_for_each_entry(pos, head, list) {
+	hlist_for_each_entry(pos, next, head, list) {
 		if (ssid == pos->ae.ssid &&
 		    tsid == pos->ae.tsid &&
 		    tclass == pos->ae.tclass &&
@@ -832,7 +838,8 @@ int avc_ss_reset(u32 seqno)
 	int i, rc = 0, tmprc;
 	unsigned long flag;
 	struct avc_node *node;
-	struct list_head *head;
+	struct hlist_head *head;
+	struct hlist_node *next;
 	spinlock_t *lock;
 
 	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
@@ -845,7 +852,7 @@ int avc_ss_reset(u32 seqno)
 		 * prevent RCU grace periods from ending.
 		 */
 		rcu_read_lock();
-		list_for_each_entry(node, head, list)
+		hlist_for_each_entry(node, next, head, list)
 			avc_node_delete(node);
 		rcu_read_unlock();
 		spin_unlock_irqrestore(lock, flag);


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 5/5] SELinux: convert the avc cache hash list to an hlist

[Paul Moore]

On Thursday 12 February 2009 02:51:04 pm Eric Paris wrote:
> We do not need O(1) access to the tail of the avc cache lists and so we are
> wasting lots of space using struct list_head instead of struct hlist_head.
> This patch converts the avc cache to use hlists in which there is a single
> pointer from the head which saves us about 4k of global memory.
>
> Resulted in about a 1.5% decrease in time spent in avc_has_perm_noaudit
> based on oprofile sampling of tbench.  Although likely within the noise....
>
> Signed-off-by: Eric Paris <eparis@redhat.com>

Reviewed-by: Paul Moore <paul.moore@hp.com>

-- 
paul moore
linux @ hp


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 5/5] SELinux: convert the avc cache hash list to an hlist

[James Morris]

On Thu, 12 Feb 2009, Eric Paris wrote:

> We do not need O(1) access to the tail of the avc cache lists and so we are
> wasting lots of space using struct list_head instead of struct hlist_head.
> This patch converts the avc cache to use hlists in which there is a single
> pointer from the head which saves us about 4k of global memory.
> 
> Resulted in about a 1.5% decrease in time spent in avc_has_perm_noaudit based
> on oprofile sampling of tbench.  Although likely within the noise....
> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Applied.

> ---
> 
>  security/selinux/avc.c |   47 +++++++++++++++++++++++++++--------------------
>  1 files changed, 27 insertions(+), 20 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index ed051d7..cc83acd 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -92,12 +92,12 @@ struct avc_entry {
>  
>  struct avc_node {
>  	struct avc_entry	ae;
> -	struct list_head	list; /* anchored in avc_cache->slots[i] */
> +	struct hlist_node	list; /* anchored in avc_cache->slots[i] */
>  	struct rcu_head		rhead;
>  };
>  
>  struct avc_cache {
> -	struct list_head	slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
> +	struct hlist_head	slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
>  	spinlock_t		slots_lock[AVC_CACHE_SLOTS]; /* lock for writes */
>  	atomic_t		lru_hint;	/* LRU hint for reclaim scan */
>  	atomic_t		active_nodes;
> @@ -238,7 +238,7 @@ void __init avc_init(void)
>  	int i;
>  
>  	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
> -		INIT_LIST_HEAD(&avc_cache.slots[i]);
> +		INIT_HLIST_HEAD(&avc_cache.slots[i]);
>  		spin_lock_init(&avc_cache.slots_lock[i]);
>  	}
>  	atomic_set(&avc_cache.active_nodes, 0);
> @@ -254,7 +254,7 @@ int avc_get_hash_stats(char *page)
>  {
>  	int i, chain_len, max_chain_len, slots_used;
>  	struct avc_node *node;
> -	struct list_head *head;
> +	struct hlist_head *head;
>  
>  	rcu_read_lock();
>  
> @@ -262,10 +262,12 @@ int avc_get_hash_stats(char *page)
>  	max_chain_len = 0;
>  	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
>  		head = &avc_cache.slots[i];
> -		if (!list_empty(head)) {
> +		if (!hlist_empty(head)) {
> +			struct hlist_node *next;
> +
>  			slots_used++;
>  			chain_len = 0;
> -			list_for_each_entry_rcu(node, head, list)
> +			hlist_for_each_entry_rcu(node, next, head, list)
>  				chain_len++;
>  			if (chain_len > max_chain_len)
>  				max_chain_len = chain_len;
> @@ -289,7 +291,7 @@ static void avc_node_free(struct rcu_head *rhead)
>  
>  static void avc_node_delete(struct avc_node *node)
>  {
> -	list_del_rcu(&node->list);
> +	hlist_del_rcu(&node->list);
>  	call_rcu(&node->rhead, avc_node_free);
>  	atomic_dec(&avc_cache.active_nodes);
>  }
> @@ -303,7 +305,7 @@ static void avc_node_kill(struct avc_node *node)
>  
>  static void avc_node_replace(struct avc_node *new, struct avc_node *old)
>  {
> -	list_replace_rcu(&old->list, &new->list);
> +	hlist_replace_rcu(&old->list, &new->list);
>  	call_rcu(&old->rhead, avc_node_free);
>  	atomic_dec(&avc_cache.active_nodes);
>  }
> @@ -313,7 +315,8 @@ static inline int avc_reclaim_node(void)
>  	struct avc_node *node;
>  	int hvalue, try, ecx;
>  	unsigned long flags;
> -	struct list_head *head;
> +	struct hlist_head *head;
> +	struct hlist_node *next;
>  	spinlock_t *lock;
>  
>  	for (try = 0, ecx = 0; try < AVC_CACHE_SLOTS; try++) {
> @@ -325,7 +328,7 @@ static inline int avc_reclaim_node(void)
>  			continue;
>  
>  		rcu_read_lock();
> -		list_for_each_entry(node, head, list) {
> +		hlist_for_each_entry(node, next, head, list) {
>  			avc_node_delete(node);
>  			avc_cache_stats_incr(reclaims);
>  			ecx++;
> @@ -351,7 +354,7 @@ static struct avc_node *avc_alloc_node(void)
>  		goto out;
>  
>  	INIT_RCU_HEAD(&node->rhead);
> -	INIT_LIST_HEAD(&node->list);
> +	INIT_HLIST_NODE(&node->list);
>  	avc_cache_stats_incr(allocations);
>  
>  	if (atomic_inc_return(&avc_cache.active_nodes) > avc_cache_threshold)
> @@ -373,11 +376,12 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
>  {
>  	struct avc_node *node, *ret = NULL;
>  	int hvalue;
> -	struct list_head *head;
> +	struct hlist_head *head;
> +	struct hlist_node *next;
>  
>  	hvalue = avc_hash(ssid, tsid, tclass);
>  	head = &avc_cache.slots[hvalue];
> -	list_for_each_entry_rcu(node, head, list) {
> +	hlist_for_each_entry_rcu(node, next, head, list) {
>  		if (ssid == node->ae.ssid &&
>  		    tclass == node->ae.tclass &&
>  		    tsid == node->ae.tsid) {
> @@ -466,7 +470,8 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
>  
>  	node = avc_alloc_node();
>  	if (node) {
> -		struct list_head *head;
> +		struct hlist_head *head;
> +		struct hlist_node *next;
>  		spinlock_t *lock;
>  
>  		hvalue = avc_hash(ssid, tsid, tclass);
> @@ -476,7 +481,7 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
>  		lock = &avc_cache.slots_lock[hvalue];
>  
>  		spin_lock_irqsave(lock, flag);
> -		list_for_each_entry(pos, head, list) {
> +		hlist_for_each_entry(pos, next, head, list) {
>  			if (pos->ae.ssid == ssid &&
>  			    pos->ae.tsid == tsid &&
>  			    pos->ae.tclass == tclass) {
> @@ -484,7 +489,7 @@ static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec
>  				goto found;
>  			}
>  		}
> -		list_add_rcu(&node->list, head);
> +		hlist_add_head_rcu(&node->list, head);
>  found:
>  		spin_unlock_irqrestore(lock, flag);
>  	}
> @@ -755,7 +760,8 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  	int hvalue, rc = 0;
>  	unsigned long flag;
>  	struct avc_node *pos, *node, *orig = NULL;
> -	struct list_head *head;
> +	struct hlist_head *head;
> +	struct hlist_node *next;
>  	spinlock_t *lock;
>  
>  	node = avc_alloc_node();
> @@ -772,7 +778,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
>  
>  	spin_lock_irqsave(lock, flag);
>  
> -	list_for_each_entry(pos, head, list) {
> +	hlist_for_each_entry(pos, next, head, list) {
>  		if (ssid == pos->ae.ssid &&
>  		    tsid == pos->ae.tsid &&
>  		    tclass == pos->ae.tclass &&
> @@ -832,7 +838,8 @@ int avc_ss_reset(u32 seqno)
>  	int i, rc = 0, tmprc;
>  	unsigned long flag;
>  	struct avc_node *node;
> -	struct list_head *head;
> +	struct hlist_head *head;
> +	struct hlist_node *next;
>  	spinlock_t *lock;
>  
>  	for (i = 0; i < AVC_CACHE_SLOTS; i++) {
> @@ -845,7 +852,7 @@ int avc_ss_reset(u32 seqno)
>  		 * prevent RCU grace periods from ending.
>  		 */
>  		rcu_read_lock();
> -		list_for_each_entry(node, head, list)
> +		hlist_for_each_entry(node, next, head, list)
>  			avc_node_delete(node);
>  		rcu_read_unlock();
>  		spin_unlock_irqrestore(lock, flag);
> 

-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 1/5] SELinux: remove the unused ae.used

[Paul Moore]

On Thursday 12 February 2009 02:50:43 pm Eric Paris wrote:
> Currently SELinux code has an atomic which was intended to track how many
> times an avc entry was used and to evict entries when they haven't been
> used recently.  Instead we never let this atomic get above 1 and evict when
> it is first checked for eviction since it hits zero.  This is a total waste
> of time so I'm completely dropping ae.used.
>
> This change resulted in about a 3% faster avc_has_perm_noaudit when running
> oprofile against a tbench benchmark.
>
> Signed-off-by: Eric Paris <eparis@redhat.com>

Looks okay to me, I did notice another optimization (see below) that might be 
worth including if you respin the patch.

Reviewed by: Paul Moore <paul.moore@hp.com>

>  struct avc_node {
> @@ -321,16 +320,13 @@ static inline int avc_reclaim_node(void)
>
>  		rcu_read_lock();
>  		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
> -			if (atomic_dec_and_test(&node->ae.used)) {
> -				/* Recently Unused */
> -				avc_node_delete(node);
> -				avc_cache_stats_incr(reclaims);
> -				ecx++;
> -				if (ecx >= AVC_CACHE_RECLAIM) {
> -					rcu_read_unlock();
> -					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> -					goto out;
> -				}
> +			avc_node_delete(node);
> +			avc_cache_stats_incr(reclaims);
> +			ecx++;
> +			if (ecx >= AVC_CACHE_RECLAIM) {
> +				rcu_read_unlock();
> +				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> +				goto out;
>  			}
>  		}
>  		rcu_read_unlock();

Not your fault, but in reviewing this code I realized we aren't really using 
the avc_cache.lru_hint atomic either; it looks like it is initialized to zero 
and never changes.  With that in mind we could remove the lru_hint field from 
the avc_cache and simplify the above function a tiny bit (no need for hvalue, 
just use zero).

-- 
paul moore
linux @ hp


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 1/5] SELinux: remove the unused ae.used

[Eric Paris]

On Thu, 2009-02-12 at 15:15 -0500, Paul Moore wrote:
> On Thursday 12 February 2009 02:50:43 pm Eric Paris wrote:
> > Currently SELinux code has an atomic which was intended to track how many
> > times an avc entry was used and to evict entries when they haven't been
> > used recently.  Instead we never let this atomic get above 1 and evict when
> > it is first checked for eviction since it hits zero.  This is a total waste
> > of time so I'm completely dropping ae.used.
> >
> > This change resulted in about a 3% faster avc_has_perm_noaudit when running
> > oprofile against a tbench benchmark.
> >
> > Signed-off-by: Eric Paris <eparis@redhat.com>
> 
> Looks okay to me, I did notice another optimization (see below) that might be 
> worth including if you respin the patch.
> 
> Reviewed by: Paul Moore <paul.moore@hp.com>
> 
> >  struct avc_node {
> > @@ -321,16 +320,13 @@ static inline int avc_reclaim_node(void)
> >
> >  		rcu_read_lock();
> >  		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
> > -			if (atomic_dec_and_test(&node->ae.used)) {
> > -				/* Recently Unused */
> > -				avc_node_delete(node);
> > -				avc_cache_stats_incr(reclaims);
> > -				ecx++;
> > -				if (ecx >= AVC_CACHE_RECLAIM) {
> > -					rcu_read_unlock();
> > -					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> > -					goto out;
> > -				}
> > +			avc_node_delete(node);
> > +			avc_cache_stats_incr(reclaims);
> > +			ecx++;
> > +			if (ecx >= AVC_CACHE_RECLAIM) {
> > +				rcu_read_unlock();
> > +				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> > +				goto out;
> >  			}
> >  		}
> >  		rcu_read_unlock();
> 
> Not your fault, but in reviewing this code I realized we aren't really using 
> the avc_cache.lru_hint atomic either; it looks like it is initialized to zero 
> and never changes.  With that in mind we could remove the lru_hint field from 
> the avc_cache and simplify the above function a tiny bit (no need for hvalue, 
> just use zero).

My look says the the hvalue there is computed as:

hvalue = atomic_inc_return(&avc_cache.lru_hint) & (AVC_CACHE_SLOTS - 1);

Which means it is changed....


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 1/5] SELinux: remove the unused ae.used

[KaiGai Kohei]

Eric Paris wrote:
> On Thu, 2009-02-12 at 15:15 -0500, Paul Moore wrote:
>> On Thursday 12 February 2009 02:50:43 pm Eric Paris wrote:
>>> Currently SELinux code has an atomic which was intended to track how many
>>> times an avc entry was used and to evict entries when they haven't been
>>> used recently.  Instead we never let this atomic get above 1 and evict when
>>> it is first checked for eviction since it hits zero.  This is a total waste
>>> of time so I'm completely dropping ae.used.
>>>
>>> This change resulted in about a 3% faster avc_has_perm_noaudit when running
>>> oprofile against a tbench benchmark.
>>>
>>> Signed-off-by: Eric Paris <eparis@redhat.com>
>> Looks okay to me, I did notice another optimization (see below) that might be 
>> worth including if you respin the patch.
>>
>> Reviewed by: Paul Moore <paul.moore@hp.com>
>>
>>>  struct avc_node {
>>> @@ -321,16 +320,13 @@ static inline int avc_reclaim_node(void)
>>>
>>>  		rcu_read_lock();
>>>  		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
>>> -			if (atomic_dec_and_test(&node->ae.used)) {
>>> -				/* Recently Unused */
>>> -				avc_node_delete(node);
>>> -				avc_cache_stats_incr(reclaims);
>>> -				ecx++;
>>> -				if (ecx >= AVC_CACHE_RECLAIM) {
>>> -					rcu_read_unlock();
>>> -					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
>>> -					goto out;
>>> -				}
>>> +			avc_node_delete(node);
>>> +			avc_cache_stats_incr(reclaims);
>>> +			ecx++;
>>> +			if (ecx >= AVC_CACHE_RECLAIM) {
>>> +				rcu_read_unlock();
>>> +				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
>>> +				goto out;
>>>  			}
>>>  		}
>>>  		rcu_read_unlock();
>> Not your fault, but in reviewing this code I realized we aren't really using 
>> the avc_cache.lru_hint atomic either; it looks like it is initialized to zero 
>> and never changes.  With that in mind we could remove the lru_hint field from 
>> the avc_cache and simplify the above function a tiny bit (no need for hvalue, 
>> just use zero).
> 
> My look says the the hvalue there is computed as:
> 
> hvalue = atomic_inc_return(&avc_cache.lru_hint) & (AVC_CACHE_SLOTS - 1);
> 
> Which means it is changed....

This is an aside:

The purpose of avc_cache.lru_hint and AVC_CACHE_SLOTS (512) of spinlocks is
to reduce lock contention during avc_reclaim_node() and avc_insert().

In the reader side (more than 99.99%), we can refer avc_node without locks.
However, RCU requires to acquire locks when we modify linked objects, so
it is necessary to consider the possibility of scalability issue by lock
contention on writer side.
In this case, the purpose of avc_reclaim_node() is to reduce the number
of active avc_node, not to drop a specific one, so it is not necessary
to serialize all the threads which invokes avc_reclaim_node().

Any avc_cache.slots[] has its own spinlock. This design enables to insert
or reclaim independent avc_node in parallel as far as possible. For example,
CPU-1 can insert a new avc_node into the slot[5], even if CPU-2 holds a lock
on the slot[7] in same time.

The selinux/avc.c was rewritten at the kernel-2.6.11 using RCU, because
there was a scalability issue which protects all the reader/writer by a
single spinlock at that time, so we revised this code so carefully on
the viewpoint of scalability.

Thanks,
-- 
OSS Platform Development Division, NEC
KaiGai Kohei <kaigai@ak.jp.nec.com>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 1/5] SELinux: remove the unused ae.used

[Stephen Smalley]

On Thu, 2009-02-12 at 14:50 -0500, Eric Paris wrote:
> Currently SELinux code has an atomic which was intended to track how many
> times an avc entry was used and to evict entries when they haven't been
> used recently.  Instead we never let this atomic get above 1 and evict when
> it is first checked for eviction since it hits zero.  This is a total waste
> of time so I'm completely dropping ae.used.
> 
> This change resulted in about a 3% faster avc_has_perm_noaudit when running
> oprofile against a tbench benchmark.

Historical note:  The "used" field was correctly used in the original
AVC implementation to try to avoid reclaiming a node that had been used
since the last reclaim sweep, but the conversion to RCU broke it.
Differences in the original AVC:
- used was a simple integer, not an atomic.
- in the reclaim loop, if !used we reclaim the entry; else we clear used
(so that it will look unused the next time we scan if it hasn't been
used in the interim) but continue searching.
- we set used to 1 when we first create the entry and when we have a
cache hit on it

> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Acked-by: Stephen Smalley <sds@tycho.nsa.gov>

> ---
> 
>  security/selinux/avc.c |   28 +++++++---------------------
>  1 files changed, 7 insertions(+), 21 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index 703aba1..abfe378 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -88,7 +88,6 @@ struct avc_entry {
>  	u32			tsid;
>  	u16			tclass;
>  	struct av_decision	avd;
> -	atomic_t		used;	/* used recently */
>  };
>  
>  struct avc_node {
> @@ -321,16 +320,13 @@ static inline int avc_reclaim_node(void)
>  
>  		rcu_read_lock();
>  		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
> -			if (atomic_dec_and_test(&node->ae.used)) {
> -				/* Recently Unused */
> -				avc_node_delete(node);
> -				avc_cache_stats_incr(reclaims);
> -				ecx++;
> -				if (ecx >= AVC_CACHE_RECLAIM) {
> -					rcu_read_unlock();
> -					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> -					goto out;
> -				}
> +			avc_node_delete(node);
> +			avc_cache_stats_incr(reclaims);
> +			ecx++;
> +			if (ecx >= AVC_CACHE_RECLAIM) {
> +				rcu_read_unlock();
> +				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> +				goto out;
>  			}
>  		}
>  		rcu_read_unlock();
> @@ -350,7 +346,6 @@ static struct avc_node *avc_alloc_node(void)
>  
>  	INIT_RCU_HEAD(&node->rhead);
>  	INIT_LIST_HEAD(&node->list);
> -	atomic_set(&node->ae.used, 1);
>  	avc_cache_stats_incr(allocations);
>  
>  	if (atomic_inc_return(&avc_cache.active_nodes) > avc_cache_threshold)
> @@ -383,15 +378,6 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
>  		}
>  	}
>  
> -	if (ret == NULL) {
> -		/* cache miss */
> -		goto out;
> -	}
> -
> -	/* cache hit */
> -	if (atomic_read(&ret->ae.used) != 1)
> -		atomic_set(&ret->ae.used, 1);
> -out:
>  	return ret;
>  }
>  
-- 
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 majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [PATCH 1/5] SELinux: remove the unused ae.used

[James Morris]

On Thu, 12 Feb 2009, Eric Paris wrote:

> Currently SELinux code has an atomic which was intended to track how many
> times an avc entry was used and to evict entries when they haven't been
> used recently.  Instead we never let this atomic get above 1 and evict when
> it is first checked for eviction since it hits zero.  This is a total waste
> of time so I'm completely dropping ae.used.
> 
> This change resulted in about a 3% faster avc_has_perm_noaudit when running
> oprofile against a tbench benchmark.
> 
> Signed-off-by: Eric Paris <eparis@redhat.com>

Applied.

> ---
> 
>  security/selinux/avc.c |   28 +++++++---------------------
>  1 files changed, 7 insertions(+), 21 deletions(-)
> 
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index 703aba1..abfe378 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -88,7 +88,6 @@ struct avc_entry {
>  	u32			tsid;
>  	u16			tclass;
>  	struct av_decision	avd;
> -	atomic_t		used;	/* used recently */
>  };
>  
>  struct avc_node {
> @@ -321,16 +320,13 @@ static inline int avc_reclaim_node(void)
>  
>  		rcu_read_lock();
>  		list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
> -			if (atomic_dec_and_test(&node->ae.used)) {
> -				/* Recently Unused */
> -				avc_node_delete(node);
> -				avc_cache_stats_incr(reclaims);
> -				ecx++;
> -				if (ecx >= AVC_CACHE_RECLAIM) {
> -					rcu_read_unlock();
> -					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> -					goto out;
> -				}
> +			avc_node_delete(node);
> +			avc_cache_stats_incr(reclaims);
> +			ecx++;
> +			if (ecx >= AVC_CACHE_RECLAIM) {
> +				rcu_read_unlock();
> +				spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
> +				goto out;
>  			}
>  		}
>  		rcu_read_unlock();
> @@ -350,7 +346,6 @@ static struct avc_node *avc_alloc_node(void)
>  
>  	INIT_RCU_HEAD(&node->rhead);
>  	INIT_LIST_HEAD(&node->list);
> -	atomic_set(&node->ae.used, 1);
>  	avc_cache_stats_incr(allocations);
>  
>  	if (atomic_inc_return(&avc_cache.active_nodes) > avc_cache_threshold)
> @@ -383,15 +378,6 @@ static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
>  		}
>  	}
>  
> -	if (ret == NULL) {
> -		/* cache miss */
> -		goto out;
> -	}
> -
> -	/* cache hit */
> -	if (atomic_read(&ret->ae.used) != 1)
> -		atomic_set(&ret->ae.used, 1);
> -out:
>  	return ret;
>  }
>  
> 

-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.