[RFC] install_session_keyring

[RFC] install_session_keyring

[Suzanne Wood]

Hello,
In a study of the control flow graph dumps to check that 
an rcu_assign_pointer() with a given argument type has 
preceded a call to rcu_dereference(), I've come across 
install_session_keyring() of security/keys/process_keys.c.  
We note that although no rcu_read_lock() is in place 
locally or in the function's kernel callers, siglock 
likely addresses that.  While the rcu_dereference() would 
indicate a desire for 'old' to persist, synchronize_rcu() 
is called prior to key_put(old) which "disposes of 
reference to a key."  The order of events with a use of 
the copy of the pointer following synchronize_rcu() is 
what I question.

Thanks.
Suzanne

/******************************************************/
/*
 * install a session keyring, discarding the old one
 * - if a keyring is not supplied, an empty one is invented
 */
static int install_session_keyring(struct task_struct *tsk,
                                   struct key *keyring)
{
        unsigned long flags;
        struct key *old;
        char buf[20];
        int ret;

        /* create an empty session keyring */
        if (!keyring) {
                sprintf(buf, "_ses.%u", tsk->tgid);

                keyring = keyring_alloc(buf, tsk->uid, tsk->gid, 1, NULL);
                if (IS_ERR(keyring)) {
                        ret = PTR_ERR(keyring);
                        goto error;
                }
        }
        else {
                atomic_inc(&keyring->usage);
        }

        /* install the keyring */
        spin_lock_irqsave(&tsk->sighand->siglock, flags);
        old = rcu_dereference(tsk->signal->session_keyring);
        rcu_assign_pointer(tsk->signal->session_keyring, keyring);
        spin_unlock_irqrestore(&tsk->sighand->siglock, flags);

        ret = 0;

        /* we're using RCU on the pointer */
        synchronize_rcu();
        key_put(old);
error:
        return ret;

} /* end install_session_keyring() */

Re: [RFC] install_session_keyring

[David Howells]

Suzanne Wood <suzannew@cs.pdx.edu> wrote:

> In a study of the control flow graph dumps to check that 
> an rcu_assign_pointer() with a given argument type has 
> preceded a call to rcu_dereference(), I've come across 
> install_session_keyring() of security/keys/process_keys.c.  
> We note that although no rcu_read_lock() is in place 
> locally or in the function's kernel callers, siglock 
> likely addresses that.  While the rcu_dereference() would 
> indicate a desire for 'old' to persist, synchronize_rcu() 
> is called prior to key_put(old) which "disposes of 
> reference to a key."  The order of events with a use of 
> the copy of the pointer following synchronize_rcu() is 
> what I question.

Are you simply suggesting that the rcu_dereference() in:

	/* install the keyring */
       	spin_lock_irqsave(&tsk->sighand->siglock, flags);
       	old = rcu_dereference(tsk->signal->session_keyring);
       	rcu_assign_pointer(tsk->signal->session_keyring, keyring);
       	spin_unlock_irqrestore(&tsk->sighand->siglock, flags);

is unnecessary?

If so, I think you are right since the pointer is only changed with the
siglock held[*], and so modify/modify conflict isn't a problem and doesn't
need memory barriers.

[*] Apart from during the exit() cleanup, when I don't think this should be a
problem anyway.

David

Re: [RFC] install_session_keyring

[Suzanne Wood]

  > From David Howells Mon Apr  3 01:46:08 2006

  > Suzanne Wood <suzannew@cs.pdx.edu> wrote:

  > > In a study of the control flow graph dumps to check that 
  > > an rcu_assign_pointer() with a given argument type has 
  > > preceded a call to rcu_dereference(), I've come across 
  > > install_session_keyring() of security/keys/process_keys.c.  
  > > We note that although no rcu_read_lock() is in place 
  > > locally or in the function's kernel callers, siglock 
  > > likely addresses that.  While the rcu_dereference() would 
  > > indicate a desire for 'old' to persist, synchronize_rcu() 
  > > is called prior to key_put(old) which "disposes of 
  > > reference to a key."  The order of events with a use of 
  > > the copy of the pointer following synchronize_rcu() is 
  > > what I question.

  > Are you simply suggesting that the rcu_dereference() in:

  > 	/* install the keyring */
  >        	spin_lock_irqsave(&tsk->sighand->siglock, flags);
  >        	old = rcu_dereference(tsk->signal->session_keyring);
  >        	rcu_assign_pointer(tsk->signal->session_keyring, keyring);
  >        	spin_unlock_irqrestore(&tsk->sighand->siglock, flags);

  > is unnecessary?

Since RCU is applicable in read intensive environments and I
look for rcu_dereference() on the read side to be paired with
rcu_assign_pointer() on the update side, I wonder if key_put()
might be redundant or risky after synchronize_rcu(), because 
key_put() opens with if(key) and employs atomic_dec_and_test(&key->usage)) 
before schedule_work(&key_cleanup_task).  If the memory referenced 
by old has already been reclaimed which appears is made possible by 
synchronize_rcu(), it seems that there is a contention here.

Yes, so I guess you mean to get rid of 'old' altogether and the three
lines that refer to it.  But I think the original intent was to have
the former session keyring persist to some extent.
Thanks.
Suzanne 

  > If so, I think you are right since the pointer is only changed with the
  > siglock held[*], and so modify/modify conflict isn't a problem and doesn't
  > need memory barriers.

  > [*] Apart from during the exit() cleanup, when I don't think this should be a
  > problem anyway.

  > David

Re: [RFC] install_session_keyring

[David Howells]

Suzanne Wood <suzannew@cs.pdx.edu> wrote:

> Since RCU is applicable in read intensive environments and I
> look for rcu_dereference() on the read side to be paired with
> rcu_assign_pointer() on the update side, I wonder if key_put()
> might be redundant or risky after synchronize_rcu(),

No, it's not redundant, and neither is it risky, at least, not as far as I can
tell from the RCU docs.

> because key_put() opens with if(key)

That's just to permit key_put(NULL) to avoid going splat.

> and employs atomic_dec_and_test(&key->usage)) before
> schedule_work(&key_cleanup_task).

How else does the cleaner-upper know to dispose of the key? And which key?

The cleaner scans the entire key tree and weeds out any key that is dead.

> If the memory referenced by old has already been reclaimed which appears is
> made possible by synchronize_rcu(), it seems that there is a contention
> here.

It will not be reclaimed until after its refcount is zero, and once that
happens, there can't be any other valid links to it.

> Yes, so I guess you mean to get rid of 'old' altogether and the three
> lines that refer to it.  But I think the original intent was to have
> the former session keyring persist to some extent.

Sorry, I'm not sure what you mean.

I can't get rid of "old". I have to exchange the new pointer for the old
pointer and then release the old object, otherwise there's a resource leak.

However, I think the code should probably be:

	spin_lock_irqsave(&tsk->sighand->siglock, flags);
	old = tsk->signal->session_keyring;
	rcu_assign_pointer(tsk->signal->session_keyring, keyring);
	spin_unlock_irqrestore(&tsk->sighand->siglock, flags);

The code then calls synchronize_rcu() to make sure no one can then follow that
pointer and then releases the reference on it.  Anyone who wants the object to
persist beyond the rcu_read_lock()'d region must have incremented the refcount
whilst inside that region.  But once the synchronize_rcu() completes, it must
be safe for me to release the reference.

It's possible, if not probable, that a memory barrier is required before the
atomic_dec_and_test() in key_put().

I don't think one is required after an atomic_inc() between rcu_read_lock()
and rcu_read_unlock() because I think those need to imply LOCK/UNLOCK barrier
semantics.  Maybe Paul McKenney thinks otherwise, though I think I convinced
him to agree with me.

By the way, the use of schedule_work() to dispose of keys is so that the key
destroyer can be relatively slow; it also keeps the latency of key_get() as
minimal as possible in the slow case, but that's a lesser consideration.  It
also makes the locking simpler.  Note that there is no intention for the key
to persist any great length of time after its usage count reaches zero.

Note also that the replacement of the session keyring does not suggest that
the session keyring will most likely be destroyed; in fact the likelyhood is
that it won't.  It's a _session_ keyring, and is most probably going to be
shared by quite a few processes.


So, to sum up, I think there's three potential problems with my code:

 (1) key_put() probably needs smp_mb__before_atomic_dec().

 (2) key_get() may need smp_mb__after_atomic_inc() inside of rcu_read_lock()'d
     sections, but I don't think that's necessary as the mere fact it's inside
     a locked section should obviate that need.

 (3) rcu_dereference() is a waste of processing time inside the spinlocks in
     install_session_keyring().  It should be a direct dereference.  The
     semantics of spin_unlock() should obviate the need for the
     smp_read_barrier_depends().


But thanks for pointing out the potential problems in my code.  That's much
appreciated.  The kernel needs a good memory barrier audit.

David

Re: [RFC] install_session_keyring

[Suzanne Wood]

  > From David Howells Mon Apr  3 12:08:16 2006

  > Suzanne Wood <suzannew@cs.pdx.edu> wrote:

  > > Since RCU is applicable in read intensive environments and I
  > > look for rcu_dereference() on the read side to be paired with
  > > rcu_assign_pointer() on the update side, I wonder if key_put()
  > > might be redundant or risky after synchronize_rcu(),

  > No, it's not redundant, and neither is it risky, at least, not as far as I can
  > tell from the RCU docs.

  > > because key_put() opens with if(key)

  > That's just to permit key_put(NULL) to avoid going splat.

  > > and employs atomic_dec_and_test(&key->usage)) before
  > > schedule_work(&key_cleanup_task).

  > How else does the cleaner-upper know to dispose of the key? And which key?

  > The cleaner scans the entire key tree and weeds out any key that is dead.

  > > If the memory referenced by old has already been reclaimed which appears is
  > > made possible by synchronize_rcu(), it seems that there is a contention
  > > here.

>From P. McKenney's 'What is RCU?': "synchronize_rcu() marks the end of updater 
code and the beginning of reclaimer code. It does this by blocking until all 
pre-existing RCU read-side critical sections on all CPUs have completed. Note 
that synchronize_rcu() will not necessarily wait for any subsequent RCU read-side 
critical sections to complete."

It seems that once synchronize_rcu() is called, the rcu-protected memory
can be reclaimed which means available for reuse, so a NULL check wouldn't be
reliable.

  > It will not be reclaimed until after its refcount is zero, and once that
  > happens, there can't be any other valid links to it.

  > > Yes, so I guess you mean to get rid of 'old' altogether and the three
  > > lines that refer to it.  But I think the original intent was to have
  > > the former session keyring persist to some extent.

  > Sorry, I'm not sure what you mean.

We do find rcu_dereference(tsk->signal->session_keyring) within 
rcu_read_lock()/unlock() pairs (and similarly current->signal->session_keyring 
and context->signal->session_keyring) in security/keys/process_keys.c and 
request_key.c.

  > I can't get rid of "old". I have to exchange the new pointer for the old
  > pointer and then release the old object, otherwise there's a resource leak.

  > However, I think the code should probably be:

  > 	spin_lock_irqsave(&tsk->sighand->siglock, flags);
  > 	old = tsk->signal->session_keyring;
  > 	rcu_assign_pointer(tsk->signal->session_keyring, keyring);
  > 	spin_unlock_irqrestore(&tsk->sighand->siglock, flags);

  > The code then calls synchronize_rcu() to make sure no one can then follow that
  > pointer and then releases the reference on it.  Anyone who wants the object to
  > persist beyond the rcu_read_lock()'d region must have incremented the refcount
  > whilst inside that region.  But once the synchronize_rcu() completes, it must
  > be safe for me to release the reference.

When synchronize_rcu() reclaims memory, it's because the old references to stale
data were retained just for the duration of the rcu readside critical sections.

  > It's possible, if not probable, that a memory barrier is required before the
  > atomic_dec_and_test() in key_put().

  > I don't think one is required after an atomic_inc() between rcu_read_lock()
  > and rcu_read_unlock() because I think those need to imply LOCK/UNLOCK barrier
  > semantics.  Maybe Paul McKenney thinks otherwise, though I think I convinced
  > him to agree with me.

  > By the way, the use of schedule_work() to dispose of keys is so that the key
  > destroyer can be relatively slow; it also keeps the latency of key_get() as
  > minimal as possible in the slow case, but that's a lesser consideration.  It
  > also makes the locking simpler.  Note that there is no intention for the key
  > to persist any great length of time after its usage count reaches zero.

  > Note also that the replacement of the session keyring does not suggest that
  > the session keyring will most likely be destroyed; in fact the likelyhood is
  > that it won't.  It's a _session_ keyring, and is most probably going to be
  > shared by quite a few processes.


  > So, to sum up, I think there's three potential problems with my code:

  >  (1) key_put() probably needs smp_mb__before_atomic_dec().

  >  (2) key_get() may need smp_mb__after_atomic_inc() inside of rcu_read_lock()'d
  >      sections, but I don't think that's necessary as the mere fact it's inside
  >      a locked section should obviate that need.

  >  (3) rcu_dereference() is a waste of processing time inside the spinlocks in
  >      install_session_keyring().  It should be a direct dereference.  The
  >      semantics of spin_unlock() should obviate the need for the
  >      smp_read_barrier_depends().

  > But thanks for pointing out the potential problems in my code.  That's much
  > appreciated.  The kernel needs a good memory barrier audit.

  > David

I'm hoping to develop rules to automate a correct application
of the RCU-API and appreciate your help.  And memory barrier issues 
specific to different architectures provide complexity.

Thanks.
Suzanne

Re: [RFC] install_session_keyring

[David Howells]

Suzanne Wood <suzannew@cs.pdx.edu> wrote:

> From P. McKenney's 'What is RCU?': "synchronize_rcu() marks the end of
> updater code and the beginning of reclaimer code. It does this by blocking
> until all pre-existing RCU read-side critical sections on all CPUs have
> completed. Note that synchronize_rcu() will not necessarily wait for any
> subsequent RCU read-side critical sections to complete."
> 
> It seems that once synchronize_rcu() is called, the rcu-protected memory can
> be reclaimed which means available for reuse, so a NULL check wouldn't be
> reliable.

I'm not sure why you think it wouldn't be reliable.

Look at it this way:

 (1) In install_session_keyring(), before going into the critical section, we
     elevate the reference count on the new keyring by one.  This ensures that
     the signal_struct will hold a reference on the new keyring.

 (2) Then, whilst under lock, we replace the pointer to the old session
     keyring with a pointer to the new session keyring, and we leave the
     critical section with a pointer in a local variable to the old keyring.

     On leaving the critical section, the local variable "old" will be NULL if
     there wasn't an old session keyring, and will point to the old session
     keyring if there was one.

     If there _was_ an old session keyring, then there will still be an extra
     reference on it that was used to pin it on behalf of the signal_struct.

 (3) We then wait for all other current RCU-readers to finish doing stuff with
     the old session keyring by calling synchronize_rcu()[*].

     [*] This could probably be skipped if old == NULL.

     Future RCU readers are irrelevant as they'll see the new keyring and not
     the old.

 (4) Then:

     (a) If there _was_ an old session keyring, there'll still be that extra
     	 reference to deal with - so we will need to decrement the reference
     	 count and destroy the keyring if the refcount reaches zero.

     (b) If there _wasn't_ an old session keyring, the old pointer will be
     	 NULL, and we don't do anything more.

> "synchronize_rcu() marks the end of updater code

That's steps (2) and (3) above.

>  and the beginning of reclaimer code

That's step (4).

Why should the NULL-pointer check not be reliable?  Either old is NULL or it
isn't.  This isn't going to change when we call synchronize_rcu() - if it
does, then we've got real problems all over the place, not just here.

synchronize_rcu() acts as a full memory barrier, thus preventing the
atomic_dec_and_test() in key_put() from seeping into the critical section,
though I think this should probably have an smp_mb__before_atomic_dec()
anyway.

> We do find rcu_dereference(tsk->signal->session_keyring) within
> rcu_read_lock()/unlock() pairs (and similarly
> current->signal->session_keyring and context->signal->session_keyring) in
> security/keys/process_keys.c and request_key.c.

Yes, so?

> When synchronize_rcu() reclaims memory, it's because the old references to
> stale data were retained just for the duration of the rcu readside critical
> sections.

synchronize_rcu() doesn't reclaim memory.

And in this specific case, there's no guarantee that the old keyring will be
deleted after synchronize_rcu() is called.  It's quite likely the old keyring
will persist because it's attached to some other task.

The reason that we jump through these hoops here is that it _might_ be the
last reference, but some other thread in the same process may be attempting to
look up a key whilst we're doing this.

> I'm hoping to develop rules to automate a correct application
> of the RCU-API and appreciate your help.  And memory barrier issues 
> specific to different architectures provide complexity.

Don't forget: you should assume the minimum specification anywhere that's
outside of arch specific code.

David