Re: [Linux-ima-devel] [RFC 2/4] ima: use namespaced flags for IMA_AUDITED on each namespace

[Magalhaes, G. (B. R&D-CL) <gui...@hp...>]

Mimi,
Let me update you on the ideas below. 
First, on the 2-lookups solution, we have one radix tree inside another. On the first radix tree, the index is namespace id, which seems ok (not sparse). The second radix tree is indexed by iint address, which must be replaced by a rbtree as you indicated.
The second point is about the possible alternative solution I mentioned. Actually, I realized that we would have possible memory leaks on that solution since it would not be possible to delete the namespaced flags when a namespace is released. It would wait when the namespace is reused for the same iint and then it would finally reset the flags under that namespace. Then, the namespaced flags would never be deleted (to avoid the need for locking the inode when the namespace is released).

Therefore, we still have 2 options:
1) namespaced flags tree inside the iint structure, single lookup, but when namespace is released it would have to lock and unlock each related inode accessed under that namespace to safely delete the namespaced flag. There can be hundred/thousands of iints namespaced flags to delete.
2) namespaced flags tree outside the iint structure, we would need 2 lookups when a namespace flag is referenced.

--
Guilherme

-----Original Message-----
From: Magalhaes, Guilherme (Brazil R&D-CL) 
Sent: quarta-feira, 12 de julho de 2017 10:57
To: Mimi Zohar <zo...@li...>
Cc: lin...@li...
Subject: Re: [Linux-ima-devel] [RFC 2/4] ima: use namespaced flags for IMA_AUDITED on each namespace

Hi Mimi,

>Originally IMA used a radix tree for storing the iint information, but 
>later it was replace with a red-black tree. The reasons for using a 
>red-black tree instead are explained in commit 8549164 "IMA: use rbtree 
>instead of radix tree for inode information cache" patch description.

I reviewed the log on this commit and these are the most relevant parts:
     "... uses a radix tree for indexing.
      It uses the *address* of the struct inode as the indexing key.  That
      means the key space is extremely sparse. ... for XFS the struct inode
      addresses are approximately 1000 bytes apart, which means the closest
      the radix tree index keys get is ~1000.  ..., so the radix tree is using
      roughly 550 bytes for every 120byte structure being cached..."
Basically it says that using radix tree would not make an optimized use of memory in case the key values are sparse. On the case of XFS inode address, the values would always be at least 1000 apart. Now, the values used as key on the solution we propose are namespace ids, which are typically incremented by one and easily reused when released. Then our solution doesn't seem to suffer the memory footprint inefficiency described on this commit log. This is one aspect, I don't have a strong/full comparison to decide among radix tree and rbtree, so please advise if rbtree is still the preferable data structure. 

> We really shouldn't need two radix tree lookups to get the namespaced iint flags.
>Finding the namespaced iint information should be very similar to 
>finding the iint itself.  Both should be based on the pointer to the 
>inode.  I could see namespacing the function integrity_find_iint().

I checked the source code of the posted POC (from Mehmet) and it confirmed our understanding of namespacing IMA in general. 
For the discussion about how many lookups are required to retrieve the namespaced iint flags, we actually have two possible solutions. The first solution is the list of namespace flags inside the iint structure (the 'status' in the posted POC), which requires just one more lookup, and the second is the list of namespace flags outside the iint structure, which requires two more lookups (first by namespace id then by iint). 
The chosen solution must handle file change, file deletion and namespace release. 
Name space release may happen concurrently to file change or deletion. When a namespace is released, the namespaced iint flags must be deleted or cleared. Now, when the namespaced iint flags are inside the iint structure and a namespace is released, the namespaced flags deletion may conflict with the deletion of a related inode. That means the inode must be locked (each one in the list of iints in the namespace structure) during the processes of releasing the namespace so the flags can be safely cleared.
So, reviewing the POC code:

+void ima_free_ns_status(struct ima_namespace *ns) {
+	struct ns_status *current_status;
+	struct ns_status *next_status;
+
+	list_for_each_entry_safe(current_status, next_status,
+				 &ns->iint_list, iint_next) {
+		if (!list_empty(&current_status->ns_next))
+			list_del_rcu(&current_status->ns_next);   <--
+		synchronize_rcu();
+		list_del_rcu(&current_status->iint_next);
+		...	
+	}
+}

Deleting 'current_status->ns_next' may impact 'iint->ns_list' field, which can be referenced or even deleted concurrently and then the inode lock should be held (for each respective inode/iint). Take into consideration that the iint may be reused after file deletion which increases the conflict above. For this reason we proceeded to the second solution (flags outside iint structure) which requires two more lookups.
However, we believe another option could avoid the two additional lookups. We store the namespaced flags inside the iint structure, but we don't delete the flags when a namespace is released. We would rely in a sequence/version number stored along with the namespaced flags list which would indicate the version of the current namespace. The version of the namespace would be bumped up whenever the namespace is released and then reused.
If the versions do not match (namespace structure version and iint ns_list version), it means the ns_list in the iint structure is old and the flags are not reliable. The namespaced flags (inside iint) are then all deleted at this time and its version is updated.
Fortunately, the mnt_namespace structure (fs/mount.h) already has this 'seq' number, but we should make this field public to access it in the IMA code. 
If this solution (including the change in fs/namespace.c) is acceptable, this is then another option. Otherwise, the 2-lookups solution seems the only safe option.

--
Guilherme

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________
Linux-ima-devel mailing list
Lin...@li...
https://lists.sourceforge.net/lists/listinfo/linux-ima-devel