[lkml]   [2004]   [Aug]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
Patch in this message
SubjectRe: RCU issue with SELinux (Re: SELINUX performance issues)
On Wed, Aug 25, 2004 at 06:51:53PM +0900, Kaigai Kohei wrote:

Hello again, Kai,

> Hi Paul, thanks for your comments.
> > > I modified the following points:
> > > - We hold the lock for hash backet when avc_insert() and avc_ss_reset() are
> > > called for safety.
> > > - list_for_each_rcu() and list_entry() are replaced by list_for_entry().
> >
> > One subtlety here...
> >
> > The traversals that are protected by rcu_read_lock() (rather than an
> > update-side spinlock) need to be list_for_each_entry_rcu() rather than
> > list_for_each_entry(). The "_rcu()" is required in order to work
> > reliably on Alpha, and has the added benefit of calling out exactly
> > which traversals are RCU-protected.
> >
> > Update-side code remains list_for_each_entry().
> It was a simple misconception.
> I fixed them in the take3-patch.

Let's take them one at a time:

1. The list_for_each_entry_rcu() in avc_hash_eval() is correct.
It is protected by rcu_read_lock(), so it is documenting
a RCU-protected traversal of the list, and inserting needed
memory barriers on Alpha CPUs.

2. The list_for_each_entry_rcu() in avc_reclaim_node() should
instead by list_for_each_entry(), with no _rcu(). This is
because this traversal is guarded by the update-side lock,
not by RCU. The fact that the lock is held means that no
other CPU can be changing this list during the traversal.

3. The list_for_each_entry_rcu() in avc_search_node() is correct.
As in item #1, it is protected by rcu_read_lock().

4. The list_for_each_entry_rcu() in avc_insert() is more interesting,
but needs to be list_for_each_entry(). It is protected by -both-
the spinlock and by an rcu_read_lock() acquired by the caller!

However, the spinlock prevents any other CPU from modifying the
data structure, so this should be list_for_each_entry() rather
than the current list_for_each_entry_rcu().

What is happening is that the code is upgrading from a read-side
rcu_read_lock() to an update-side spin_lock_irqsave(). This
is legal, though perhaps a bit unconventional.

However, looking closer, I don't understand why the rcu_read_lock()
needs to be re-acquired before the call to avc_insert() in

o avc_latest_notif_update() allocates a sequence number
under a lock.

o avc_get_node() allocates and initializes a node. It does
call avc_reclaim_node(), but this function is guarded
by a spinlock.

o avc_insert() calls the above two functions, and other
than that, initializes the new node (which no other CPU
has access to), and inserts it under the spinlock.

So I do not believe that avc_insert() needs rcu_read_lock().
Unless I am missing something, the rcu_read_lock() acquired
in avc_has_perm_noaudit() should be moved after the call to

I was concerned about the possibility that avc_has_perm_noaudit()
might be preempted between the rcu_read_unlock() and the
rcu_read_lock(), but this issue appears to be correctly handled
by the code in avc_insert(), which handles either case, updating
the existing node or inserting a new one.

5. The list_for_each_entry_rcu() in avc_update_node() should be
changed to list_for_each_entry(), since it is protected
by the update-side spinlock, and therefore does not need
RCU protection, as in item #2 above. This is another case
where an rcu_read_lock() is "upgraded" to a write-side lock
by acquiring a spinlock.

6. The list_for_each_entry_rcu() in avc_update_cache() is correct.
It is protected only by rcu_read_lock(), so RCU protection is

7. The list_for_each_entry_rcu() in avc_ss_reset() needs to be
changed to list_for_each_entry(), since it is protected by
the update-side spinlock. Since the array is statically allocated,
there is no need for the enclosing rcu_read_lock() and
rcu_read_unlock(), and they should be removed.

I clearly need to provide more documentation. ;-) This is in progress.

See below for a patch that applies on top of your take3 patch, since
the C code might be more clear than the English in this case.

> > > - avc_node_dual structure which contains two avc_node objects is defined.
> > > It allows to do avc_update_node() without kmalloc() or any locks.
> >
> > What happens when you have two consecutive updates to the same object?
> > Don't you have to defer the second update until a grace period has
> > elapsed since the first update in order to avoid confusing readers that
> > are still accessing the original version?
> I didn't imagine such a situation. Indeed, such thing may happen.
> > One way to do this would be to set a "don't-touch-me" bit that is
> > cleared by an RCU callback. An update to an element with the
> > "don't-touch-me" bit set would block until the bit clears. There
> > are probably better ways...
> I think we can't apply this approach for the implementation
> of avc_update_node(), because execution context isn't permitted to block.

That would certainly invalidate my suggestion! ;-)

> I changed my opinion and implementation of avc_update_node().
> If kmalloc() returns NULL in avc_update_node(), it returns -ENOMEM.
> But this effect of changing the prototype is limited, because only
> avc_has_perm_noaudit() and avc_update_cache() call avc_update_node().
> Even if avc_update_node() return -ENOMEM to avc_has_perm_noaudit(),
> avc_has_perm_noaudit() can ignore it, because the purpose is only
> to control the audit-log floods.
> This adverse effect is only that audit-logs are printed twice.
> Nobody calls avc_update_cache(), which is only defined.

Sounds good!

> Some other trivial fixes are as follows:
> - All list_for_each_entry() were replaced by list_for_each_entry_rcu().

See above. ;-)

> - All spin_lock()/spin_unlock() were replaced by spin_lock_irqsave()
> /spin_unlock_restore().
> - In avc_node_insert(), if an entry with the same ssid/tsid/tclass as new
> one exists, the older entry is replaced by the new one.
> Thank you for the opinion as a specialist of RCU!

Thank -you- for giving RCU a try! Again, the performance results are
quite impressive!

Thanx, Paul

diff -urpN -X dontdiff linux- linux-
--- linux- Wed Aug 25 09:34:26 2004
+++ linux- Wed Aug 25 10:30:10 2004
@@ -253,7 +253,7 @@ static inline int avc_reclaim_node(void)
if (!spin_trylock(&avc_cache.slots_lock[hvalue]))

- list_for_each_entry_rcu(node, &avc_cache.slots[hvalue], list) {
+ list_for_each_entry(node, &avc_cache.slots[hvalue], list) {
if (!atomic_dec_and_test(&node->ae.used)) {
/* Recently Unused */
@@ -419,7 +419,7 @@ struct avc_node *avc_insert(u32 ssid, u3
node->ae.avd.seqno = ae->avd.seqno;

spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
- list_for_each_entry_rcu(pos, &avc_cache.slots[hvalue], list) {
+ list_for_each_entry(pos, &avc_cache.slots[hvalue], list) {
if (pos->ae.ssid == ssid &&
pos->ae.tsid == tsid &&
pos->ae.tclass == tclass) {
@@ -719,7 +719,7 @@ static int avc_update_node(u32 event, u3
hvalue = avc_hash(ssid, tsid, tclass);
spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);

- list_for_each_entry_rcu(pos, &avc_cache.slots[hvalue], list){
+ list_for_each_entry(pos, &avc_cache.slots[hvalue], list){
if ( ssid==pos->ae.ssid &&
tsid==pos->ae.tsid &&
tclass==pos->ae.tclass ){
@@ -912,16 +912,14 @@ int avc_ss_reset(u32 seqno)


- rcu_read_lock();
for (i = 0; i < AVC_CACHE_SLOTS; i++) {
spin_lock_irqsave(&avc_cache.slots_lock[i], flag);
- list_for_each_entry_rcu(node, &avc_cache.slots[i], list){
+ list_for_each_entry(node, &avc_cache.slots[i], list){
call_rcu(&node->rhead, avc_node_free);
spin_unlock_irqrestore(&avc_cache.slots_lock[i], flag);
- rcu_read_unlock();

for (i = 0; i < AVC_NSTATS; i++)
avc_cache_stats[i] = 0;
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at
 \ /
  Last update: 2005-03-22 14:05    [W:0.052 / U:1.672 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site