[PATCH] Use an IDR to allocate apparmor secids

[PATCH] Use an IDR to allocate apparmor secids

[Matthew Wilcox]

Replace the custom usage of the radix tree to store a list of free IDs
with the IDR.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

 security/apparmor/secid.c |  114 ++++------------------------------------------
 1 file changed, 11 insertions(+), 103 deletions(-)

diff --git a/security/apparmor/secid.c b/security/apparmor/secid.c
index c2f0c1571156..3ad94b2ffbb2 100644
--- a/security/apparmor/secid.c
+++ b/security/apparmor/secid.c
@@ -18,6 +18,7 @@
 #include <linux/errno.h>
 #include <linux/err.h>
 #include <linux/gfp.h>
+#include <linux/idr.h>
 #include <linux/slab.h>
 #include <linux/spinlock.h>
 
@@ -30,18 +31,10 @@
 /*
  * secids - do not pin labels with a refcount. They rely on the label
  * properly updating/freeing them
- *
- * A singly linked free list is used to track secids that have been
- * freed and reuse them before allocating new ones
  */
 
-#define FREE_LIST_HEAD 1
-
-static RADIX_TREE(aa_secids_map, GFP_ATOMIC);
+static DEFINE_IDR(aa_secids);
 static DEFINE_SPINLOCK(secid_lock);
-static u32 alloced_secid = FREE_LIST_HEAD;
-static u32 free_list = FREE_LIST_HEAD;
-static unsigned long free_count;
 
 /*
  * TODO: allow policy to reserve a secid range?
@@ -49,65 +42,6 @@ static unsigned long free_count;
  * TODO: use secid_update in label replace
  */
 
-#define SECID_MAX U32_MAX
-
-/* TODO: mark free list as exceptional */
-static void *to_ptr(u32 secid)
-{
-	return (void *)
-		((((unsigned long) secid) << RADIX_TREE_EXCEPTIONAL_SHIFT));
-}
-
-static u32 to_secid(void *ptr)
-{
-	return (u32) (((unsigned long) ptr) >> RADIX_TREE_EXCEPTIONAL_SHIFT);
-}
-
-
-/* TODO: tag free_list entries to mark them as different */
-static u32 __pop(struct aa_label *label)
-{
-	u32 secid = free_list;
-	void __rcu **slot;
-	void *entry;
-
-	if (free_list == FREE_LIST_HEAD)
-		return AA_SECID_INVALID;
-
-	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
-	AA_BUG(!slot);
-	entry = radix_tree_deref_slot_protected(slot, &secid_lock);
-	free_list = to_secid(entry);
-	radix_tree_replace_slot(&aa_secids_map, slot, label);
-	free_count--;
-
-	return secid;
-}
-
-static void __push(u32 secid)
-{
-	void __rcu **slot;
-
-	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
-	AA_BUG(!slot);
-	radix_tree_replace_slot(&aa_secids_map, slot, to_ptr(free_list));
-	free_list = secid;
-	free_count++;
-}
-
-static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
-{
-	struct aa_label *old;
-	void __rcu **slot;
-
-	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
-	AA_BUG(!slot);
-	old = radix_tree_deref_slot_protected(slot, &secid_lock);
-	radix_tree_replace_slot(&aa_secids_map, slot, label);
-
-	return old;
-}
-
 /**
  * aa_secid_update - update a secid mapping to a new label
  * @secid: secid to update
@@ -115,11 +49,10 @@ static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
  */
 void aa_secid_update(u32 secid, struct aa_label *label)
 {
-	struct aa_label *old;
 	unsigned long flags;
 
 	spin_lock_irqsave(&secid_lock, flags);
-	old = __secid_update(secid, label);
+	idr_replace(&aa_secids, label, secid);
 	spin_unlock_irqrestore(&secid_lock, flags);
 }
 
@@ -132,7 +65,7 @@ struct aa_label *aa_secid_to_label(u32 secid)
 	struct aa_label *label;
 
 	rcu_read_lock();
-	label = radix_tree_lookup(&aa_secids_map, secid);
+	label = idr_find(&aa_secids, secid);
 	rcu_read_unlock();
 
 	return label;
@@ -167,7 +100,6 @@ int apparmor_secid_to_secctx(u32 secid, char **secdata, u32 *seclen)
 	return 0;
 }
 
-
 int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid)
 {
 	struct aa_label *label;
@@ -186,7 +118,6 @@ void apparmor_release_secctx(char *secdata, u32 seclen)
 	kfree(secdata);
 }
 
-
 /**
  * aa_alloc_secid - allocate a new secid for a profile
  */
@@ -195,35 +126,12 @@ u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp)
 	unsigned long flags;
 	u32 secid;
 
-	/* racey, but at worst causes new allocation instead of reuse */
-	if (free_list == FREE_LIST_HEAD) {
-		bool preload = 0;
-		int res;
-
-retry:
-		if (gfpflags_allow_blocking(gfp) && !radix_tree_preload(gfp))
-			preload = 1;
-		spin_lock_irqsave(&secid_lock, flags);
-		if (alloced_secid != SECID_MAX) {
-			secid = ++alloced_secid;
-			res = radix_tree_insert(&aa_secids_map, secid, label);
-			AA_BUG(res == -EEXIST);
-		} else {
-			secid = AA_SECID_INVALID;
-		}
-		spin_unlock_irqrestore(&secid_lock, flags);
-		if (preload)
-			radix_tree_preload_end();
-	} else {
-		spin_lock_irqsave(&secid_lock, flags);
-		/* remove entry from free list */
-		secid = __pop(label);
-		if (secid == AA_SECID_INVALID) {
-			spin_unlock_irqrestore(&secid_lock, flags);
-			goto retry;
-		}
-		spin_unlock_irqrestore(&secid_lock, flags);
-	}
+	idr_preload(gfp);
+	spin_lock_irqsave(&secid_lock, flags);
+	secid = idr_alloc(&aa_secids, label, 0, 0, GFP_ATOMIC);
+	/* XXX: Can return -ENOMEM */
+	spin_unlock_irqrestore(&secid_lock, flags);
+	idr_preload_end();
 
 	return secid;
 }
@@ -237,6 +145,6 @@ void aa_free_secid(u32 secid)
 	unsigned long flags;
 
 	spin_lock_irqsave(&secid_lock, flags);
-	__push(secid);
+	idr_remove(&aa_secids, secid);
 	spin_unlock_irqrestore(&secid_lock, flags);
 }

Re: [PATCH] Use an IDR to allocate apparmor secids

[Matthew Wilcox]

ping?

I have this queued up in my XArray tree.  If I don't hear from you before
-rc1, I'll be submitting it as part of the XArray conversion.

On Tue, May 22, 2018 at 02:32:59AM -0700, Matthew Wilcox wrote:
> Replace the custom usage of the radix tree to store a list of free IDs
> with the IDR.
> 
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> 
>  security/apparmor/secid.c |  114 ++++------------------------------------------
>  1 file changed, 11 insertions(+), 103 deletions(-)
> 
> diff --git a/security/apparmor/secid.c b/security/apparmor/secid.c
> index c2f0c1571156..3ad94b2ffbb2 100644
> --- a/security/apparmor/secid.c
> +++ b/security/apparmor/secid.c
> @@ -18,6 +18,7 @@
>  #include <linux/errno.h>
>  #include <linux/err.h>
>  #include <linux/gfp.h>
> +#include <linux/idr.h>
>  #include <linux/slab.h>
>  #include <linux/spinlock.h>
>  
> @@ -30,18 +31,10 @@
>  /*
>   * secids - do not pin labels with a refcount. They rely on the label
>   * properly updating/freeing them
> - *
> - * A singly linked free list is used to track secids that have been
> - * freed and reuse them before allocating new ones
>   */
>  
> -#define FREE_LIST_HEAD 1
> -
> -static RADIX_TREE(aa_secids_map, GFP_ATOMIC);
> +static DEFINE_IDR(aa_secids);
>  static DEFINE_SPINLOCK(secid_lock);
> -static u32 alloced_secid = FREE_LIST_HEAD;
> -static u32 free_list = FREE_LIST_HEAD;
> -static unsigned long free_count;
>  
>  /*
>   * TODO: allow policy to reserve a secid range?
> @@ -49,65 +42,6 @@ static unsigned long free_count;
>   * TODO: use secid_update in label replace
>   */
>  
> -#define SECID_MAX U32_MAX
> -
> -/* TODO: mark free list as exceptional */
> -static void *to_ptr(u32 secid)
> -{
> -	return (void *)
> -		((((unsigned long) secid) << RADIX_TREE_EXCEPTIONAL_SHIFT));
> -}
> -
> -static u32 to_secid(void *ptr)
> -{
> -	return (u32) (((unsigned long) ptr) >> RADIX_TREE_EXCEPTIONAL_SHIFT);
> -}
> -
> -
> -/* TODO: tag free_list entries to mark them as different */
> -static u32 __pop(struct aa_label *label)
> -{
> -	u32 secid = free_list;
> -	void __rcu **slot;
> -	void *entry;
> -
> -	if (free_list == FREE_LIST_HEAD)
> -		return AA_SECID_INVALID;
> -
> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
> -	AA_BUG(!slot);
> -	entry = radix_tree_deref_slot_protected(slot, &secid_lock);
> -	free_list = to_secid(entry);
> -	radix_tree_replace_slot(&aa_secids_map, slot, label);
> -	free_count--;
> -
> -	return secid;
> -}
> -
> -static void __push(u32 secid)
> -{
> -	void __rcu **slot;
> -
> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
> -	AA_BUG(!slot);
> -	radix_tree_replace_slot(&aa_secids_map, slot, to_ptr(free_list));
> -	free_list = secid;
> -	free_count++;
> -}
> -
> -static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
> -{
> -	struct aa_label *old;
> -	void __rcu **slot;
> -
> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
> -	AA_BUG(!slot);
> -	old = radix_tree_deref_slot_protected(slot, &secid_lock);
> -	radix_tree_replace_slot(&aa_secids_map, slot, label);
> -
> -	return old;
> -}
> -
>  /**
>   * aa_secid_update - update a secid mapping to a new label
>   * @secid: secid to update
> @@ -115,11 +49,10 @@ static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
>   */
>  void aa_secid_update(u32 secid, struct aa_label *label)
>  {
> -	struct aa_label *old;
>  	unsigned long flags;
>  
>  	spin_lock_irqsave(&secid_lock, flags);
> -	old = __secid_update(secid, label);
> +	idr_replace(&aa_secids, label, secid);
>  	spin_unlock_irqrestore(&secid_lock, flags);
>  }
>  
> @@ -132,7 +65,7 @@ struct aa_label *aa_secid_to_label(u32 secid)
>  	struct aa_label *label;
>  
>  	rcu_read_lock();
> -	label = radix_tree_lookup(&aa_secids_map, secid);
> +	label = idr_find(&aa_secids, secid);
>  	rcu_read_unlock();
>  
>  	return label;
> @@ -167,7 +100,6 @@ int apparmor_secid_to_secctx(u32 secid, char **secdata, u32 *seclen)
>  	return 0;
>  }
>  
> -
>  int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid)
>  {
>  	struct aa_label *label;
> @@ -186,7 +118,6 @@ void apparmor_release_secctx(char *secdata, u32 seclen)
>  	kfree(secdata);
>  }
>  
> -
>  /**
>   * aa_alloc_secid - allocate a new secid for a profile
>   */
> @@ -195,35 +126,12 @@ u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp)
>  	unsigned long flags;
>  	u32 secid;
>  
> -	/* racey, but at worst causes new allocation instead of reuse */
> -	if (free_list == FREE_LIST_HEAD) {
> -		bool preload = 0;
> -		int res;
> -
> -retry:
> -		if (gfpflags_allow_blocking(gfp) && !radix_tree_preload(gfp))
> -			preload = 1;
> -		spin_lock_irqsave(&secid_lock, flags);
> -		if (alloced_secid != SECID_MAX) {
> -			secid = ++alloced_secid;
> -			res = radix_tree_insert(&aa_secids_map, secid, label);
> -			AA_BUG(res == -EEXIST);
> -		} else {
> -			secid = AA_SECID_INVALID;
> -		}
> -		spin_unlock_irqrestore(&secid_lock, flags);
> -		if (preload)
> -			radix_tree_preload_end();
> -	} else {
> -		spin_lock_irqsave(&secid_lock, flags);
> -		/* remove entry from free list */
> -		secid = __pop(label);
> -		if (secid == AA_SECID_INVALID) {
> -			spin_unlock_irqrestore(&secid_lock, flags);
> -			goto retry;
> -		}
> -		spin_unlock_irqrestore(&secid_lock, flags);
> -	}
> +	idr_preload(gfp);
> +	spin_lock_irqsave(&secid_lock, flags);
> +	secid = idr_alloc(&aa_secids, label, 0, 0, GFP_ATOMIC);
> +	/* XXX: Can return -ENOMEM */
> +	spin_unlock_irqrestore(&secid_lock, flags);
> +	idr_preload_end();
>  
>  	return secid;
>  }
> @@ -237,6 +145,6 @@ void aa_free_secid(u32 secid)
>  	unsigned long flags;
>  
>  	spin_lock_irqsave(&secid_lock, flags);
> -	__push(secid);
> +	idr_remove(&aa_secids, secid);
>  	spin_unlock_irqrestore(&secid_lock, flags);
>  }
> 

Re: [PATCH] Use an IDR to allocate apparmor secids

[John Johansen]

On 05/28/2018 10:01 AM, Matthew Wilcox wrote:
> 
> ping?
> 
> I have this queued up in my XArray tree.  If I don't hear from you before
> -rc1, I'll be submitting it as part of the XArray conversion.

yeah looking at this is on my to do list (I am might even manage to get to it
today), the last couple weeks have just been really busy.

Re: [PATCH] Use an IDR to allocate apparmor secids

[John Johansen]

On 05/22/2018 02:32 AM, Matthew Wilcox wrote:
> Replace the custom usage of the radix tree to store a list of free IDs
> with the IDR.
> 
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> 
>  security/apparmor/secid.c |  114 ++++------------------------------------------
>  1 file changed, 11 insertions(+), 103 deletions(-)
> 
> diff --git a/security/apparmor/secid.c b/security/apparmor/secid.c
> index c2f0c1571156..3ad94b2ffbb2 100644
> --- a/security/apparmor/secid.c
> +++ b/security/apparmor/secid.c
> @@ -18,6 +18,7 @@
>  #include <linux/errno.h>
>  #include <linux/err.h>
>  #include <linux/gfp.h>
> +#include <linux/idr.h>
>  #include <linux/slab.h>
>  #include <linux/spinlock.h>
>  
> @@ -30,18 +31,10 @@
>  /*
>   * secids - do not pin labels with a refcount. They rely on the label
>   * properly updating/freeing them
> - *
> - * A singly linked free list is used to track secids that have been
> - * freed and reuse them before allocating new ones
>   */
>  
> -#define FREE_LIST_HEAD 1
> -
> -static RADIX_TREE(aa_secids_map, GFP_ATOMIC);
> +static DEFINE_IDR(aa_secids);
>  static DEFINE_SPINLOCK(secid_lock);
> -static u32 alloced_secid = FREE_LIST_HEAD;
> -static u32 free_list = FREE_LIST_HEAD;
> -static unsigned long free_count;
>  
>  /*
>   * TODO: allow policy to reserve a secid range?
> @@ -49,65 +42,6 @@ static unsigned long free_count;
>   * TODO: use secid_update in label replace
>   */
>  
> -#define SECID_MAX U32_MAX
> -
> -/* TODO: mark free list as exceptional */
> -static void *to_ptr(u32 secid)
> -{
> -	return (void *)
> -		((((unsigned long) secid) << RADIX_TREE_EXCEPTIONAL_SHIFT));
> -}
> -
> -static u32 to_secid(void *ptr)
> -{
> -	return (u32) (((unsigned long) ptr) >> RADIX_TREE_EXCEPTIONAL_SHIFT);
> -}
> -
> -
> -/* TODO: tag free_list entries to mark them as different */
> -static u32 __pop(struct aa_label *label)
> -{
> -	u32 secid = free_list;
> -	void __rcu **slot;
> -	void *entry;
> -
> -	if (free_list == FREE_LIST_HEAD)
> -		return AA_SECID_INVALID;
> -
> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
> -	AA_BUG(!slot);
> -	entry = radix_tree_deref_slot_protected(slot, &secid_lock);
> -	free_list = to_secid(entry);
> -	radix_tree_replace_slot(&aa_secids_map, slot, label);
> -	free_count--;
> -
> -	return secid;
> -}
> -
> -static void __push(u32 secid)
> -{
> -	void __rcu **slot;
> -
> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
> -	AA_BUG(!slot);
> -	radix_tree_replace_slot(&aa_secids_map, slot, to_ptr(free_list));
> -	free_list = secid;
> -	free_count++;
> -}
> -
> -static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
> -{
> -	struct aa_label *old;
> -	void __rcu **slot;
> -
> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
> -	AA_BUG(!slot);
> -	old = radix_tree_deref_slot_protected(slot, &secid_lock);
> -	radix_tree_replace_slot(&aa_secids_map, slot, label);
> -
> -	return old;
> -}
> -
>  /**
>   * aa_secid_update - update a secid mapping to a new label
>   * @secid: secid to update
> @@ -115,11 +49,10 @@ static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
>   */
>  void aa_secid_update(u32 secid, struct aa_label *label)
>  {
> -	struct aa_label *old;
>  	unsigned long flags;
>  
>  	spin_lock_irqsave(&secid_lock, flags);
> -	old = __secid_update(secid, label);
> +	idr_replace(&aa_secids, label, secid);
>  	spin_unlock_irqrestore(&secid_lock, flags);
>  }
>  
> @@ -132,7 +65,7 @@ struct aa_label *aa_secid_to_label(u32 secid)
>  	struct aa_label *label;
>  
>  	rcu_read_lock();
> -	label = radix_tree_lookup(&aa_secids_map, secid);
> +	label = idr_find(&aa_secids, secid);
>  	rcu_read_unlock();
>  
>  	return label;
> @@ -167,7 +100,6 @@ int apparmor_secid_to_secctx(u32 secid, char **secdata, u32 *seclen)
>  	return 0;
>  }
>  
> -
>  int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid)
>  {
>  	struct aa_label *label;
> @@ -186,7 +118,6 @@ void apparmor_release_secctx(char *secdata, u32 seclen)
>  	kfree(secdata);
>  }
>  
> -
>  /**
>   * aa_alloc_secid - allocate a new secid for a profile
>   */
> @@ -195,35 +126,12 @@ u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp)
>  	unsigned long flags;
>  	u32 secid;
>  
> -	/* racey, but at worst causes new allocation instead of reuse */
> -	if (free_list == FREE_LIST_HEAD) {
> -		bool preload = 0;
> -		int res;
> -
> -retry:
> -		if (gfpflags_allow_blocking(gfp) && !radix_tree_preload(gfp))
> -			preload = 1;
> -		spin_lock_irqsave(&secid_lock, flags);
> -		if (alloced_secid != SECID_MAX) {
> -			secid = ++alloced_secid;
> -			res = radix_tree_insert(&aa_secids_map, secid, label);
> -			AA_BUG(res == -EEXIST);
> -		} else {
> -			secid = AA_SECID_INVALID;
> -		}
> -		spin_unlock_irqrestore(&secid_lock, flags);
> -		if (preload)
> -			radix_tree_preload_end();
> -	} else {
> -		spin_lock_irqsave(&secid_lock, flags);
> -		/* remove entry from free list */
> -		secid = __pop(label);
> -		if (secid == AA_SECID_INVALID) {
> -			spin_unlock_irqrestore(&secid_lock, flags);
> -			goto retry;
> -		}
> -		spin_unlock_irqrestore(&secid_lock, flags);
> -	}
> +	idr_preload(gfp);
> +	spin_lock_irqsave(&secid_lock, flags);
> +	secid = idr_alloc(&aa_secids, label, 0, 0, GFP_ATOMIC);
> +	/* XXX: Can return -ENOMEM */

need to return AA_SECID_INVALID in the event of an error

if we want to track which error we could change the api of aa_alloc_secid


> +	spin_unlock_irqrestore(&secid_lock, flags);
> +	idr_preload_end();
>  
>  	return secid;
>  }
> @@ -237,6 +145,6 @@ void aa_free_secid(u32 secid)
>  	unsigned long flags;
>  
>  	spin_lock_irqsave(&secid_lock, flags);
> -	__push(secid);
> +	idr_remove(&aa_secids, secid);
>  	spin_unlock_irqrestore(&secid_lock, flags);
>  }
> 

Re: [PATCH] Use an IDR to allocate apparmor secids

[John Johansen]

On 05/28/2018 10:01 AM, Matthew Wilcox wrote:
> 
> ping?
> 
> I have this queued up in my XArray tree.  If I don't hear from you before
> -rc1, I'll be submitting it as part of the XArray conversion.
> 
hey Mathew,

I've pulled this into apparmor-next and done the retuning of
AA_SECID_INVALID a follow on patch. The reworking of the api to
return the specific error type can wait for another cycle.


> On Tue, May 22, 2018 at 02:32:59AM -0700, Matthew Wilcox wrote:
>> Replace the custom usage of the radix tree to store a list of free IDs
>> with the IDR.
>>
>> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
>>
>>  security/apparmor/secid.c |  114 ++++------------------------------------------
>>  1 file changed, 11 insertions(+), 103 deletions(-)
>>
>> diff --git a/security/apparmor/secid.c b/security/apparmor/secid.c
>> index c2f0c1571156..3ad94b2ffbb2 100644
>> --- a/security/apparmor/secid.c
>> +++ b/security/apparmor/secid.c
>> @@ -18,6 +18,7 @@
>>  #include <linux/errno.h>
>>  #include <linux/err.h>
>>  #include <linux/gfp.h>
>> +#include <linux/idr.h>
>>  #include <linux/slab.h>
>>  #include <linux/spinlock.h>
>>  
>> @@ -30,18 +31,10 @@
>>  /*
>>   * secids - do not pin labels with a refcount. They rely on the label
>>   * properly updating/freeing them
>> - *
>> - * A singly linked free list is used to track secids that have been
>> - * freed and reuse them before allocating new ones
>>   */
>>  
>> -#define FREE_LIST_HEAD 1
>> -
>> -static RADIX_TREE(aa_secids_map, GFP_ATOMIC);
>> +static DEFINE_IDR(aa_secids);
>>  static DEFINE_SPINLOCK(secid_lock);
>> -static u32 alloced_secid = FREE_LIST_HEAD;
>> -static u32 free_list = FREE_LIST_HEAD;
>> -static unsigned long free_count;
>>  
>>  /*
>>   * TODO: allow policy to reserve a secid range?
>> @@ -49,65 +42,6 @@ static unsigned long free_count;
>>   * TODO: use secid_update in label replace
>>   */
>>  
>> -#define SECID_MAX U32_MAX
>> -
>> -/* TODO: mark free list as exceptional */
>> -static void *to_ptr(u32 secid)
>> -{
>> -	return (void *)
>> -		((((unsigned long) secid) << RADIX_TREE_EXCEPTIONAL_SHIFT));
>> -}
>> -
>> -static u32 to_secid(void *ptr)
>> -{
>> -	return (u32) (((unsigned long) ptr) >> RADIX_TREE_EXCEPTIONAL_SHIFT);
>> -}
>> -
>> -
>> -/* TODO: tag free_list entries to mark them as different */
>> -static u32 __pop(struct aa_label *label)
>> -{
>> -	u32 secid = free_list;
>> -	void __rcu **slot;
>> -	void *entry;
>> -
>> -	if (free_list == FREE_LIST_HEAD)
>> -		return AA_SECID_INVALID;
>> -
>> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
>> -	AA_BUG(!slot);
>> -	entry = radix_tree_deref_slot_protected(slot, &secid_lock);
>> -	free_list = to_secid(entry);
>> -	radix_tree_replace_slot(&aa_secids_map, slot, label);
>> -	free_count--;
>> -
>> -	return secid;
>> -}
>> -
>> -static void __push(u32 secid)
>> -{
>> -	void __rcu **slot;
>> -
>> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
>> -	AA_BUG(!slot);
>> -	radix_tree_replace_slot(&aa_secids_map, slot, to_ptr(free_list));
>> -	free_list = secid;
>> -	free_count++;
>> -}
>> -
>> -static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
>> -{
>> -	struct aa_label *old;
>> -	void __rcu **slot;
>> -
>> -	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
>> -	AA_BUG(!slot);
>> -	old = radix_tree_deref_slot_protected(slot, &secid_lock);
>> -	radix_tree_replace_slot(&aa_secids_map, slot, label);
>> -
>> -	return old;
>> -}
>> -
>>  /**
>>   * aa_secid_update - update a secid mapping to a new label
>>   * @secid: secid to update
>> @@ -115,11 +49,10 @@ static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
>>   */
>>  void aa_secid_update(u32 secid, struct aa_label *label)
>>  {
>> -	struct aa_label *old;
>>  	unsigned long flags;
>>  
>>  	spin_lock_irqsave(&secid_lock, flags);
>> -	old = __secid_update(secid, label);
>> +	idr_replace(&aa_secids, label, secid);
>>  	spin_unlock_irqrestore(&secid_lock, flags);
>>  }
>>  
>> @@ -132,7 +65,7 @@ struct aa_label *aa_secid_to_label(u32 secid)
>>  	struct aa_label *label;
>>  
>>  	rcu_read_lock();
>> -	label = radix_tree_lookup(&aa_secids_map, secid);
>> +	label = idr_find(&aa_secids, secid);
>>  	rcu_read_unlock();
>>  
>>  	return label;
>> @@ -167,7 +100,6 @@ int apparmor_secid_to_secctx(u32 secid, char **secdata, u32 *seclen)
>>  	return 0;
>>  }
>>  
>> -
>>  int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid)
>>  {
>>  	struct aa_label *label;
>> @@ -186,7 +118,6 @@ void apparmor_release_secctx(char *secdata, u32 seclen)
>>  	kfree(secdata);
>>  }
>>  
>> -
>>  /**
>>   * aa_alloc_secid - allocate a new secid for a profile
>>   */
>> @@ -195,35 +126,12 @@ u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp)
>>  	unsigned long flags;
>>  	u32 secid;
>>  
>> -	/* racey, but at worst causes new allocation instead of reuse */
>> -	if (free_list == FREE_LIST_HEAD) {
>> -		bool preload = 0;
>> -		int res;
>> -
>> -retry:
>> -		if (gfpflags_allow_blocking(gfp) && !radix_tree_preload(gfp))
>> -			preload = 1;
>> -		spin_lock_irqsave(&secid_lock, flags);
>> -		if (alloced_secid != SECID_MAX) {
>> -			secid = ++alloced_secid;
>> -			res = radix_tree_insert(&aa_secids_map, secid, label);
>> -			AA_BUG(res == -EEXIST);
>> -		} else {
>> -			secid = AA_SECID_INVALID;
>> -		}
>> -		spin_unlock_irqrestore(&secid_lock, flags);
>> -		if (preload)
>> -			radix_tree_preload_end();
>> -	} else {
>> -		spin_lock_irqsave(&secid_lock, flags);
>> -		/* remove entry from free list */
>> -		secid = __pop(label);
>> -		if (secid == AA_SECID_INVALID) {
>> -			spin_unlock_irqrestore(&secid_lock, flags);
>> -			goto retry;
>> -		}
>> -		spin_unlock_irqrestore(&secid_lock, flags);
>> -	}
>> +	idr_preload(gfp);
>> +	spin_lock_irqsave(&secid_lock, flags);
>> +	secid = idr_alloc(&aa_secids, label, 0, 0, GFP_ATOMIC);
>> +	/* XXX: Can return -ENOMEM */
>> +	spin_unlock_irqrestore(&secid_lock, flags);
>> +	idr_preload_end();
>>  
>>  	return secid;
>>  }
>> @@ -237,6 +145,6 @@ void aa_free_secid(u32 secid)
>>  	unsigned long flags;
>>  
>>  	spin_lock_irqsave(&secid_lock, flags);
>> -	__push(secid);
>> +	idr_remove(&aa_secids, secid);
>>  	spin_unlock_irqrestore(&secid_lock, flags);
>>  }
>>

Re: [PATCH] Use an IDR to allocate apparmor secids

[Matthew Wilcox]

On Mon, Jun 04, 2018 at 06:27:09PM -0700, John Johansen wrote:
> hey Mathew,
> 
> I've pulled this into apparmor-next and done the retuning of
> AA_SECID_INVALID a follow on patch. The reworking of the api to
> return the specific error type can wait for another cycle.

Oh ... here's what I currently have.  I decided that AA_SECID_INVALID
wasn't needed.

>From 4e43853a7d984d7b16fd68f356aef1b686a05298 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <mawilcox@microsoft.com>
Date: Tue, 22 May 2018 05:37:19 -0400
Subject: [PATCH] Use an IDR to allocate apparmor secids

Replace the custom usage of the radix tree to store a list of free IDs
with the IDR.  Change the aa_alloc_secid() API to store the secid in the
label while holding the spinlock to ensure that a simultaneous lookup
cannot find an uninitialised secid.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 security/apparmor/include/secid.h |   5 +-
 security/apparmor/label.c         |   3 +-
 security/apparmor/secid.c         | 135 ++++++------------------------
 3 files changed, 28 insertions(+), 115 deletions(-)

diff --git a/security/apparmor/include/secid.h b/security/apparmor/include/secid.h
index 686de8e50a79..a8ba767b2d2c 100644
--- a/security/apparmor/include/secid.h
+++ b/security/apparmor/include/secid.h
@@ -19,16 +19,13 @@
 
 struct aa_label;
 
-/* secid value that will not be allocated */
-#define AA_SECID_INVALID 0
-
 struct aa_label *aa_secid_to_label(u32 secid);
 int apparmor_secid_to_secctx(u32 secid, char **secdata, u32 *seclen);
 int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid);
 void apparmor_release_secctx(char *secdata, u32 seclen);
 
 
-u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp);
+int aa_alloc_secid(struct aa_label *label, gfp_t gfp);
 void aa_free_secid(u32 secid);
 void aa_secid_update(u32 secid, struct aa_label *label);
 
diff --git a/security/apparmor/label.c b/security/apparmor/label.c
index a17574df611b..ba11bdf9043a 100644
--- a/security/apparmor/label.c
+++ b/security/apparmor/label.c
@@ -407,8 +407,7 @@ bool aa_label_init(struct aa_label *label, int size, gfp_t gfp)
 	AA_BUG(!label);
 	AA_BUG(size < 1);
 
-	label->secid = aa_alloc_secid(label, gfp);
-	if (label->secid == AA_SECID_INVALID)
+	if (aa_alloc_secid(label, gfp) < 0)
 		return false;
 
 	label->size = size;			/* doesn't include null */
diff --git a/security/apparmor/secid.c b/security/apparmor/secid.c
index c2f0c1571156..bc9f8e101b65 100644
--- a/security/apparmor/secid.c
+++ b/security/apparmor/secid.c
@@ -18,6 +18,7 @@
 #include <linux/errno.h>
 #include <linux/err.h>
 #include <linux/gfp.h>
+#include <linux/idr.h>
 #include <linux/slab.h>
 #include <linux/spinlock.h>
 
@@ -30,18 +31,10 @@
 /*
  * secids - do not pin labels with a refcount. They rely on the label
  * properly updating/freeing them
- *
- * A singly linked free list is used to track secids that have been
- * freed and reuse them before allocating new ones
  */
 
-#define FREE_LIST_HEAD 1
-
-static RADIX_TREE(aa_secids_map, GFP_ATOMIC);
+static DEFINE_IDR(aa_secids);
 static DEFINE_SPINLOCK(secid_lock);
-static u32 alloced_secid = FREE_LIST_HEAD;
-static u32 free_list = FREE_LIST_HEAD;
-static unsigned long free_count;
 
 /*
  * TODO: allow policy to reserve a secid range?
@@ -49,65 +42,6 @@ static unsigned long free_count;
  * TODO: use secid_update in label replace
  */
 
-#define SECID_MAX U32_MAX
-
-/* TODO: mark free list as exceptional */
-static void *to_ptr(u32 secid)
-{
-	return (void *)
-		((((unsigned long) secid) << RADIX_TREE_EXCEPTIONAL_SHIFT));
-}
-
-static u32 to_secid(void *ptr)
-{
-	return (u32) (((unsigned long) ptr) >> RADIX_TREE_EXCEPTIONAL_SHIFT);
-}
-
-
-/* TODO: tag free_list entries to mark them as different */
-static u32 __pop(struct aa_label *label)
-{
-	u32 secid = free_list;
-	void __rcu **slot;
-	void *entry;
-
-	if (free_list == FREE_LIST_HEAD)
-		return AA_SECID_INVALID;
-
-	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
-	AA_BUG(!slot);
-	entry = radix_tree_deref_slot_protected(slot, &secid_lock);
-	free_list = to_secid(entry);
-	radix_tree_replace_slot(&aa_secids_map, slot, label);
-	free_count--;
-
-	return secid;
-}
-
-static void __push(u32 secid)
-{
-	void __rcu **slot;
-
-	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
-	AA_BUG(!slot);
-	radix_tree_replace_slot(&aa_secids_map, slot, to_ptr(free_list));
-	free_list = secid;
-	free_count++;
-}
-
-static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
-{
-	struct aa_label *old;
-	void __rcu **slot;
-
-	slot = radix_tree_lookup_slot(&aa_secids_map, secid);
-	AA_BUG(!slot);
-	old = radix_tree_deref_slot_protected(slot, &secid_lock);
-	radix_tree_replace_slot(&aa_secids_map, slot, label);
-
-	return old;
-}
-
 /**
  * aa_secid_update - update a secid mapping to a new label
  * @secid: secid to update
@@ -115,11 +49,10 @@ static struct aa_label * __secid_update(u32 secid, struct aa_label *label)
  */
 void aa_secid_update(u32 secid, struct aa_label *label)
 {
-	struct aa_label *old;
 	unsigned long flags;
 
 	spin_lock_irqsave(&secid_lock, flags);
-	old = __secid_update(secid, label);
+	idr_replace(&aa_secids, label, secid);
 	spin_unlock_irqrestore(&secid_lock, flags);
 }
 
@@ -132,7 +65,7 @@ struct aa_label *aa_secid_to_label(u32 secid)
 	struct aa_label *label;
 
 	rcu_read_lock();
-	label = radix_tree_lookup(&aa_secids_map, secid);
+	label = idr_find(&aa_secids, secid);
 	rcu_read_unlock();
 
 	return label;
@@ -167,7 +100,6 @@ int apparmor_secid_to_secctx(u32 secid, char **secdata, u32 *seclen)
 	return 0;
 }
 
-
 int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid)
 {
 	struct aa_label *label;
@@ -186,46 +118,31 @@ void apparmor_release_secctx(char *secdata, u32 seclen)
 	kfree(secdata);
 }
 
-
 /**
- * aa_alloc_secid - allocate a new secid for a profile
+ * aa_alloc_secid - Allocate a new secid for a profile.
+ * @label: Freshly allocated label.
+ * @gfp: Memory allocation flags.
+ *
+ * Initialises the label's secid with an unused ID.
+ *
+ * Context: Any context.
+ * Return: 0 if the label's secid has been successfully initialised.  If
+ * memory allocation failed, returns -ENOMEM.  If no more IDs are
+ * available, returns -ENOSPC.
  */
-u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp)
+int aa_alloc_secid(struct aa_label *label, gfp_t gfp)
 {
 	unsigned long flags;
-	u32 secid;
-
-	/* racey, but at worst causes new allocation instead of reuse */
-	if (free_list == FREE_LIST_HEAD) {
-		bool preload = 0;
-		int res;
-
-retry:
-		if (gfpflags_allow_blocking(gfp) && !radix_tree_preload(gfp))
-			preload = 1;
-		spin_lock_irqsave(&secid_lock, flags);
-		if (alloced_secid != SECID_MAX) {
-			secid = ++alloced_secid;
-			res = radix_tree_insert(&aa_secids_map, secid, label);
-			AA_BUG(res == -EEXIST);
-		} else {
-			secid = AA_SECID_INVALID;
-		}
-		spin_unlock_irqrestore(&secid_lock, flags);
-		if (preload)
-			radix_tree_preload_end();
-	} else {
-		spin_lock_irqsave(&secid_lock, flags);
-		/* remove entry from free list */
-		secid = __pop(label);
-		if (secid == AA_SECID_INVALID) {
-			spin_unlock_irqrestore(&secid_lock, flags);
-			goto retry;
-		}
-		spin_unlock_irqrestore(&secid_lock, flags);
-	}
-
-	return secid;
+	int err;
+
+	idr_preload(gfp);
+	spin_lock_irqsave(&secid_lock, flags);
+	err = idr_alloc_u32(&aa_secids, label, &label->secid, UINT_MAX,
+			GFP_ATOMIC);
+	spin_unlock_irqrestore(&secid_lock, flags);
+	idr_preload_end();
+
+	return err;
 }
 
 /**
@@ -237,6 +154,6 @@ void aa_free_secid(u32 secid)
 	unsigned long flags;
 
 	spin_lock_irqsave(&secid_lock, flags);
-	__push(secid);
+	idr_remove(&aa_secids, secid);
 	spin_unlock_irqrestore(&secid_lock, flags);
 }
-- 
2.17.0

Re: [PATCH] Use an IDR to allocate apparmor secids

[John Johansen]

On 06/04/2018 07:27 PM, Matthew Wilcox wrote:
> On Mon, Jun 04, 2018 at 06:27:09PM -0700, John Johansen wrote:
>> hey Mathew,
>>
>> I've pulled this into apparmor-next and done the retuning of
>> AA_SECID_INVALID a follow on patch. The reworking of the api to
>> return the specific error type can wait for another cycle.
> 
> Oh ... here's what I currently have.  I decided that AA_SECID_INVALID
> wasn't needed.
> 
well not needed in the allocation path, but definitely needed and it
needs to be 0.

This is for catching some uninitialized or freed and zeroed values.
The debug checks aren't in the current version, as they were
residing in another debug patch, but I will pull them out into their
own patch.

Re: [PATCH] Use an IDR to allocate apparmor secids

[Matthew Wilcox]

On Mon, Jun 04, 2018 at 07:35:24PM -0700, John Johansen wrote:
> On 06/04/2018 07:27 PM, Matthew Wilcox wrote:
> > On Mon, Jun 04, 2018 at 06:27:09PM -0700, John Johansen wrote:
> >> hey Mathew,
> >>
> >> I've pulled this into apparmor-next and done the retuning of
> >> AA_SECID_INVALID a follow on patch. The reworking of the api to
> >> return the specific error type can wait for another cycle.
> > 
> > Oh ... here's what I currently have.  I decided that AA_SECID_INVALID
> > wasn't needed.
> > 
> well not needed in the allocation path, but definitely needed and it
> needs to be 0.
> 
> This is for catching some uninitialized or freed and zeroed values.
> The debug checks aren't in the current version, as they were
> residing in another debug patch, but I will pull them out into their
> own patch.

With the IDR, I don't know if you need it for debug.

	BUG_ON(label != idr_find(&aa_secids, label->secid))

should do the trick.

Re: [PATCH] Use an IDR to allocate apparmor secids

[John Johansen]

On 06/05/2018 04:47 AM, Matthew Wilcox wrote:
> On Mon, Jun 04, 2018 at 07:35:24PM -0700, John Johansen wrote:
>> On 06/04/2018 07:27 PM, Matthew Wilcox wrote:
>>> On Mon, Jun 04, 2018 at 06:27:09PM -0700, John Johansen wrote:
>>>> hey Mathew,
>>>>
>>>> I've pulled this into apparmor-next and done the retuning of
>>>> AA_SECID_INVALID a follow on patch. The reworking of the api to
>>>> return the specific error type can wait for another cycle.
>>>
>>> Oh ... here's what I currently have.  I decided that AA_SECID_INVALID
>>> wasn't needed.
>>>
>> well not needed in the allocation path, but definitely needed and it
>> needs to be 0.
>>
>> This is for catching some uninitialized or freed and zeroed values.
>> The debug checks aren't in the current version, as they were
>> residing in another debug patch, but I will pull them out into their
>> own patch.
> 
> With the IDR, I don't know if you need it for debug.
> 
> 	BUG_ON(label != idr_find(&aa_secids, label->secid))
> 
> should do the trick.
> 

its not so much the idr as the network and audit structs where the
secid gets used and then security system is asked to convert from
the secid to the secctx.

We need an invalid secid for when conversion result in an error,
partly because the returned error is ignored in some paths (eg. scm)
so we also make sure to have an invalid value.

Having it be zero helps us catch bugs on structs that are zero
but we miss initializing, and also works well with apparmor always
zeroing structs on free.

The debug patch didn't get included yet because the networking
code that make use of the secids hasn't landed yet (they are being
used in the audit path) so the debug patch ends up throwing a
lot of warning for the networking paths.

The patch I am testing on top of your patch is below

---

commit d5de3b1d21687c16df0a75b6309ab8481629a841
Author: John Johansen <john.johansen@canonical.com>
Date:   Mon Jun 4 19:44:59 2018 -0700

    apparmor: cleanup secid map convertion to using idr
    
    The idr convertion didn't handle an error case for when allocating a
    mapping fails.
    
    In addition it did not ensure that mappings did not allocate or use a
    0 value, which is used as an invalid secid because it allows debug
    code to detect when objects have not been correctly initialized or
    freed too early.
    
    Signed-off-by: John Johansen <john.johansen@canonical.com>

diff --git a/security/apparmor/include/secid.h b/security/apparmor/include/secid.h
index 686de8e50a79..dee6fa3b6081 100644
--- a/security/apparmor/include/secid.h
+++ b/security/apparmor/include/secid.h
@@ -28,8 +28,10 @@ int apparmor_secctx_to_secid(const char *secdata, u32 seclen, u32 *secid);
 void apparmor_release_secctx(char *secdata, u32 seclen);
 
 
-u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp);
+int aa_alloc_secid(struct aa_label *label, gfp_t gfp);
 void aa_free_secid(u32 secid);
 void aa_secid_update(u32 secid, struct aa_label *label);
 
+void aa_secids_init(void);
+
 #endif /* __AA_SECID_H */
diff --git a/security/apparmor/label.c b/security/apparmor/label.c
index a17574df611b..ba11bdf9043a 100644
--- a/security/apparmor/label.c
+++ b/security/apparmor/label.c
@@ -407,8 +407,7 @@ bool aa_label_init(struct aa_label *label, int size, gfp_t gfp)
 	AA_BUG(!label);
 	AA_BUG(size < 1);
 
-	label->secid = aa_alloc_secid(label, gfp);
-	if (label->secid == AA_SECID_INVALID)
+	if (aa_alloc_secid(label, gfp) < 0)
 		return false;
 
 	label->size = size;			/* doesn't include null */
diff --git a/security/apparmor/lsm.c b/security/apparmor/lsm.c
index dab5409f2608..9ae7f9339513 100644
--- a/security/apparmor/lsm.c
+++ b/security/apparmor/lsm.c
@@ -1546,6 +1546,8 @@ static int __init apparmor_init(void)
 		return 0;
 	}
 
+	aa_secids_init();
+
 	error = aa_setup_dfa_engine();
 	if (error) {
 		AA_ERROR("Unable to setup dfa engine\n");
diff --git a/security/apparmor/secid.c b/security/apparmor/secid.c
index 3ad94b2ffbb2..ad6221e1f25f 100644
--- a/security/apparmor/secid.c
+++ b/security/apparmor/secid.c
@@ -33,6 +33,8 @@
  * properly updating/freeing them
  */
 
+#define AA_FIRST_SECID 1
+
 static DEFINE_IDR(aa_secids);
 static DEFINE_SPINLOCK(secid_lock);
 
@@ -120,20 +122,30 @@ void apparmor_release_secctx(char *secdata, u32 seclen)
 
 /**
  * aa_alloc_secid - allocate a new secid for a profile
+ * @label: the label to allocate a secid for
+ * @gfp: memory allocation flags
+ *
+ * Returns: 0 with @label->secid initialized
+ *          <0 returns error with @label->secid set to AA_SECID_INVALID
  */
-u32 aa_alloc_secid(struct aa_label *label, gfp_t gfp)
+int aa_alloc_secid(struct aa_label *label, gfp_t gfp)
 {
 	unsigned long flags;
-	u32 secid;
+	int ret;
 
 	idr_preload(gfp);
 	spin_lock_irqsave(&secid_lock, flags);
-	secid = idr_alloc(&aa_secids, label, 0, 0, GFP_ATOMIC);
-	/* XXX: Can return -ENOMEM */
+	ret = idr_alloc(&aa_secids, label, 1, 0, GFP_ATOMIC);
 	spin_unlock_irqrestore(&secid_lock, flags);
 	idr_preload_end();
 
-	return secid;
+	if (ret < 0) {
+		label->secid = AA_SECID_INVALID;
+		return ret;
+	}
+
+	label->secid = ret;
+	return 0;
 }
 
 /**
@@ -148,3 +160,8 @@ void aa_free_secid(u32 secid)
 	idr_remove(&aa_secids, secid);
 	spin_unlock_irqrestore(&secid_lock, flags);
 }
+
+void aa_secids_init(void)
+{
+	idr_init_base(&aa_secids, AA_FIRST_SECID);
+}