Skip to contentSkip to conversation

SELinux: remove the unused ae.used

PATCH Applied Eric Paris 5 participants 20 messages Feb 12, 2009 – Feb 13, 2009 SELinux security module

lore
Share & tools
lore

Eric Paris

author
#0 lore raw

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

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.

---

 security/selinux/avc.c |   28 +++++++---------------------
 1 files changed, 7 insertions(+), 21 deletions(-)
security/selinux/avc.c +7 -21
index 703aba1..abfe378 100644
@@ -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 [email protected] with the words "unsubscribe selinux" without quotes as the message.

author
#1 lore raw

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

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.

---

 security/selinux/avc.c |   43 ++++++++++++++++++++++++-------------------
 1 files changed, 24 insertions(+), 19 deletions(-)
security/selinux/avc.c +24 -19
index abfe378..332c3cd 100644
@@ -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 [email protected] with the words "unsubscribe selinux" without quotes as the message.

Reviewed-by on v1 2/5
#2 lore raw

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

Quoted 8 lines · 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.

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

Quoted 22 lines

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) {

security/selinux/avc.c static int avc_latest_notif_update(int seqno, int is_insert) · line 462

Quoted 7 lines
security/selinux/avc.c +1 -1
 	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.

security/selinux/avc.c static int avc_latest_notif_update(int seqno, int is_insert) · line 465

Quoted 2 lines
security/selinux/avc.c +0 -0
 	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" ;) ).

Quoted 6 lines
security/selinux/avc.c +1 -1
 		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) {
Signature · 8 lines
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 [email protected] with
the words "unsubscribe selinux" without quotes as the message.
Acked-by on v1 2/5
#3 lore raw

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

In reply to Eric Paris
Quoted 6 lines · 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.

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).

Quoted 2 lines
Quoted 124 lines

---

 security/selinux/avc.c |   43 ++++++++++++++++++++++++-------------------
 1 files changed, 24 insertions(+), 19 deletions(-)
security/selinux/avc.c +24 -19
index abfe378..332c3cd 100644
@@ -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;
 	}
Signature · 8 lines
Stephen Smalley
National Security Agency


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

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

In reply to Eric Paris
Quoted 8 lines · 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.

Applied.

Quoted 125 lines

---

 security/selinux/avc.c |   43 ++++++++++++++++++++++++-------------------
 1 files changed, 24 insertions(+), 19 deletions(-)
security/selinux/avc.c +24 -19
index abfe378..332c3cd 100644
@@ -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;
 	}
Signature · 7 lines
James Morris
<[email protected]>

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

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

In reply to 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.

---

 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(-)
security/selinux/avc.c +5 -10
index 332c3cd..e9ccacd 100644
@@ -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();
 
security/selinux/include/security.h +0 -1
index e1d9db7..5c3434f 100644
@@ -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;
security/selinux/selinuxfs.c +1 -1
index 214f53c..2d5136e 100644
@@ -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:
security/selinux/ss/services.c +0 -2
index 6e0651a..c6a8f68 100644
@@ -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 [email protected] with the words "unsubscribe selinux" without quotes as the message.

Reviewed-by on v1 3/5
#6 lore raw

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

Quoted 10 lines · 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.

No comments at all this time ;)

Signature · 8 lines
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 [email protected] with
the words "unsubscribe selinux" without quotes as the message.
Acked-by on v1 3/5
#7 lore raw

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

In reply to Eric Paris
Quoted 5 lines · 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.

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

Quoted 5 lines

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

Quoted 101 lines

---

 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(-)
security/selinux/avc.c +5 -10
index 332c3cd..e9ccacd 100644
@@ -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();
 
security/selinux/include/security.h +0 -1
index e1d9db7..5c3434f 100644
@@ -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;
security/selinux/selinuxfs.c +1 -1
index 214f53c..2d5136e 100644
@@ -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:
security/selinux/ss/services.c +0 -2
index 6e0651a..c6a8f68 100644
@@ -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;
Signature · 8 lines
Stephen Smalley
National Security Agency


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

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

In reply to Eric Paris
Quoted 10 lines · 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.

Applied.

Quoted 102 lines

---

 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(-)
security/selinux/avc.c +5 -10
index 332c3cd..e9ccacd 100644
@@ -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();
 
security/selinux/include/security.h +0 -1
index e1d9db7..5c3434f 100644
@@ -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;
security/selinux/selinuxfs.c +1 -1
index 214f53c..2d5136e 100644
@@ -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:
security/selinux/ss/services.c +0 -2
index 6e0651a..c6a8f68 100644
@@ -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;
Signature · 7 lines
James Morris
<[email protected]>

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

PATCH 4/5 SELinux: code readability with avc_cache

In reply to 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.

---

 security/selinux/avc.c |   63 ++++++++++++++++++++++++++++++++++--------------
 1 files changed, 44 insertions(+), 19 deletions(-)
security/selinux/avc.c +44 -19
index e9ccacd..ed051d7 100644
@@ -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 [email protected] with the words "unsubscribe selinux" without quotes as the message.

#10 lore raw

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

Quoted 6 lines · 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.

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

security/selinux/avc.c static inline int avc_reclaim_node(void) · line 320

Quoted 9 lines
security/selinux/avc.c +2 -0
@@ -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.

security/selinux/avc.c static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct av_dec · line 471

Quoted 8 lines
(quoted diff) +0 -0
@@ -458,11 +466,17 @@ static struct avc_node *avc_insert(u32 ssid, u32

tsid, u16 tclass, struct av_dec

security/selinux/avc.c +3 -0
 	node = avc_alloc_node();
 	if (node) {
+		struct list_head *head;
+		spinlock_t *lock;
+

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

Signature · 8 lines
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 [email protected] with
the words "unsubscribe selinux" without quotes as the message.
Applied
#11 lore raw

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

In reply to Eric Paris
Quoted 5 lines · 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.

Applied.

Quoted 187 lines

---

 security/selinux/avc.c |   63 ++++++++++++++++++++++++++++++++++--------------
 1 files changed, 44 insertions(+), 19 deletions(-)
security/selinux/avc.c +44 -19
index e9ccacd..ed051d7 100644
@@ -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) {
Signature · 7 lines
James Morris
<[email protected]>

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

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

In reply to 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....

---

 security/selinux/avc.c |   47 +++++++++++++++++++++++++++--------------------
 1 files changed, 27 insertions(+), 20 deletions(-)
security/selinux/avc.c +27 -20
index ed051d7..cc83acd 100644
@@ -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 [email protected] with the words "unsubscribe selinux" without quotes as the message.

Reviewed-by on v1 5/5
#13 lore raw

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

Quoted 9 lines · 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....

Signature · 8 lines
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 [email protected] with
the words "unsubscribe selinux" without quotes as the message.
Applied
#14 lore raw

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

In reply to Eric Paris
Quoted 9 lines · 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....

Applied.

Quoted 185 lines

---

 security/selinux/avc.c |   47 +++++++++++++++++++++++++++--------------------
 1 files changed, 27 insertions(+), 20 deletions(-)
security/selinux/avc.c +27 -20
index ed051d7..cc83acd 100644
@@ -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);
Signature · 7 lines
James Morris
<[email protected]>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to [email protected] with
the words "unsubscribe selinux" without quotes as the message.
#15 lore raw
In reply to Eric Paris
Quoted 10 lines · 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.

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 <[email protected]>

Quoted 15 lines

struct avc_node {

security/selinux/avc.c +0 -10
@@ -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;
-				}

security/selinux/avc.c static inline int avc_reclaim_node(void) · line 332

Quoted 10 lines
security/selinux/avc.c +7 -0
+			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).

Signature · 8 lines
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 [email protected] with
the words "unsubscribe selinux" without quotes as the message.
author
#16 lore raw
Quoted 40 lines · Paul Moore
Quoted 10 lines · 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.

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 <[email protected]>

Quoted 23 lines

struct avc_node {

security/selinux/avc.c +7 -10
@@ -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;
 			}
Quoted 8 lines

security/selinux/avc.c static inline int avc_reclaim_node(void) · line 332

Quoted 2 lines
security/selinux/avc.c +0 -0
 		}
 		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 [email protected] with the words "unsubscribe selinux" without quotes as the message.

#17 lore raw
Quoted 48 lines · Eric Paris
Quoted 38 lines · Paul Moore
Quoted 10 lines · 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.

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 <[email protected]>

Quoted 22 lines

struct avc_node {

security/selinux/avc.c +7 -10
@@ -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;
Quoted 8 lines

security/selinux/avc.c static inline int avc_reclaim_node(void) · line 332

Quoted 3 lines
security/selinux/avc.c +0 -0
 			}
 		}
 		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).

Quoted 5 lines

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,

Signature · 7 lines
OSS Platform Development Division, NEC
KaiGai Kohei <[email protected]>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to [email protected] with
the words "unsubscribe selinux" without quotes as the message.
Acked-by on v1 1/5
#18 lore raw
In reply to Eric Paris
Quoted 8 lines · 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.

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

Quoted 2 lines
Quoted 65 lines

---

 security/selinux/avc.c |   28 +++++++---------------------
 1 files changed, 7 insertions(+), 21 deletions(-)
security/selinux/avc.c +7 -21
index 703aba1..abfe378 100644
@@ -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;
 }
 
Signature · 8 lines
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to [email protected] with
the words "unsubscribe selinux" without quotes as the message.
Applied
#19 lore raw
In reply to Eric Paris
Quoted 10 lines · 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.

Applied.

Quoted 66 lines

---

 security/selinux/avc.c |   28 +++++++---------------------
 1 files changed, 7 insertions(+), 21 deletions(-)
security/selinux/avc.c +7 -21
index 703aba1..abfe378 100644
@@ -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;
 }
 
Signature · 7 lines
James Morris
<[email protected]>

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