Re:Sleeping in RCU list traversal

Re:Sleeping in RCU list traversal

[Jun WANG]

Hi
>Something like this?
>
>rcu_read_lock();
>list_for_each_rcu(p, ...) {
>   ptr = list_entry(p, struct ..., list);
>   /* Grab a reference to "ptr". */
>   rcu_read_unlock();
>   my_task_that_may_sleep(ptr);
>   rcu_read_lock();
>   /* Drop a reference to "ptr". */
 >}
 >rcu_read_unlock();

>Regarding my case, memory region pointed by "ptr" never be removed.
>Do I need to grab a reference to "ptr" ?
In Document/RCU/whatisRCU.txt
Note that the value returned by rcu_dereference() is valid
	only within the enclosing RCU read-side critical section.
	For example, the following is -not- legal:

		rcu_read_lock();
		p = rcu_dereference(head.next);
		rcu_read_unlock();
		x = p->address;
		rcu_read_lock();
		y = p->data;
		rcu_read_unlock();

	Holding a reference from one RCU read-side critical section
	to another is just as illegal as holding a reference from
	one lock-based critical section to another!  Similarly,
	using a reference outside of the critical section in which
	it was acquired is just as illegal as doing so with normal
	locking.
                                                            Jun Wang

Re: Sleeping in RCU list traversal

[Tetsuo Handa]

Hello.

Thank you for pointing out.

Jun WANG wrote:
> >rcu_read_lock();
> >list_for_each_rcu(p, ...) {
> >   ptr = list_entry(p, struct ..., list);
> >   /* Grab a reference to "ptr". */
> >   rcu_read_unlock();
> >   my_task_that_may_sleep(ptr);
> >   rcu_read_lock();
> >   /* Drop a reference to "ptr". */
> > }
> > rcu_read_unlock();
> 
> In Document/RCU/whatisRCU.txt
> Note that the value returned by rcu_dereference() is valid
> 	only within the enclosing RCU read-side critical section.
Excuse me, but I think "p" is used only between rcu_read_lock() and rcu_read_unlock().
Is it illegal to use "ptr" after rcu_read_unlock() if "ptr" is obtained before rcu_read_unlock() ?

Regards.

Re: Sleeping in RCU list traversal

[Jun WANG]

> Hello.
> 
> Thank you for pointing out.
> 
> Jun WANG wrote:
> > >rcu_read_lock();
> > >list_for_each_rcu(p, ...) {
> > >   ptr = list_entry(p, struct ..., list);
> > >   /* Grab a reference to "ptr". */
> > >   rcu_read_unlock();
> > >   my_task_that_may_sleep(ptr);
> > >   rcu_read_lock();
> > >   /* Drop a reference to "ptr". */
> > > }
> > > rcu_read_unlock();
>>>Regarding my case, memory region pointed by "ptr" never be removed.
>>>Do I need to grab a reference to "ptr" ?
> > 
> > In Document/RCU/whatisRCU.txt
> > Note that the value returned by rcu_dereference() is valid
> > 	only within the enclosing RCU read-side critical section.
> Excuse me, but I think "p" is used only between rcu_read_lock() and rcu_read_unlock().
> Is it illegal to use "ptr" after rcu_read_unlock() if "ptr" is obtained before rcu_read_unlock() ?
> 
> Regards.
> 
I'm sorry,I think I got your idea, if you do not need ptr in
my_task_that_may_sleep(), why you need to grab a reference to "ptr". If
your my_task_that_may_sleep() needs ptr, and according to the 
>"memory region pointed by "ptr" never be removed." you say,
it is ok to use "ptr" after rcu_read_ulock(). The basic idea behind RCU
is to split updates into "removal" and "reclamation" phases. If you
memory region pointed by "ptr" will not "reclamation" in sleep, it is ok

Regards.

Re: Sleeping in RCU list traversal

[Tetsuo Handa]

Hello.

Jun WANG wrote:
> I'm sorry,I think I got your idea, if you do not need ptr in
> my_task_that_may_sleep(), why you need to grab a reference to "ptr". If
> your my_task_that_may_sleep() needs ptr, and according to the 
> "memory region pointed by "ptr" never be removed." you say,
> it is ok to use "ptr" after rcu_read_ulock(). The basic idea behind RCU
> is to split updates into "removal" and "reclamation" phases. If you
> memory region pointed by "ptr" will not "reclamation" in sleep, it is ok
I need "ptr" in my_task_that_may_sleep(), but regarding my case,
memory region pointed by "ptr" will never be kfree()ed.

So, I don't need to grab a reference to "ptr"
because memory region pointed by "ptr" will never be kfree()ed.
And it is legal to use "ptr" after rcu_read_unlock()
because memory region pointed by "ptr" will never be kfree()ed.

Thank you.

Re: Sleeping in RCU list traversal

[Peter Zijlstra]

On Mon, 2007-10-08 at 01:56 +0900, Tetsuo Handa wrote:

> So, I don't need to grab a reference to "ptr"
> because memory region pointed by "ptr" will never be kfree()ed.
> And it is legal to use "ptr" after rcu_read_unlock()
> because memory region pointed by "ptr" will never be kfree()ed.

Still think that is a very BAD (tm) idea. Esp since with the help of RCU
there is hardly any performance loss of not doing proper deletes.

Re: Sleeping in RCU list traversal

[Tetsuo Handa]

Hello.

Peter Zijlstra wrote:
> > So, I don't need to grab a reference to "ptr"
> > because memory region pointed by "ptr" will never be kfree()ed.
> > And it is legal to use "ptr" after rcu_read_unlock()
> > because memory region pointed by "ptr" will never be kfree()ed.
> 
> Still think that is a very BAD (tm) idea. Esp since with the help of RCU
> there is hardly any performance loss of not doing proper deletes.
> 
Elements I keep in RCU list are policy table for access control
that are referred throughout the lifetime of the kernel.
So, there is hardly any needs to delete these elements.
Honestly speaking, I don't need to use RCU list at all.
Just using a singly linked list that doesn't support deletion is enough.
But James Morris advises me to use the existing API
( http://lkml.org/lkml/2007/10/2/156 http://lkml.org/lkml/2007/10/3/124 ).

Thank you.

Re: [TOMOYO 05/15](repost) Domain transition handler functions.

[James Morris]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 577 bytes --]

On Wed, 3 Oct 2007, YOSHIFUJI Hideaki / µÈÆ£±ÑÌÀ wrote:

> In article <200710032024.DJF78662.FHOLtMSFOOFJVQ@I-love.SAKURA.ne.jp> (at Wed, 3 Oct 2007 20:24:52 +0900), Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> says:
> 
> > It seems that standard kernel list API does not have singly-linked list manipulation.
> > I'm considering the following list manipulation API.
> 
> Tstsuo, please name it "slist", which is well-known.

I'm pretty sure that the singly linked list idea has been rejected a few 
times.  Just use the existing API.

-- 
James Morris
<jmorris@namei.org>

Re: [TOMOYO 05/15](repost) Domain transition handler functions.

[Tetsuo Handa]

James Morris wrote:
> I'm pretty sure that the singly linked list idea has been rejected a few 
> times.  Just use the existing API.
Too bad...

Well, is there a way to avoid read_lock when reading list?

Currently, TOMOYO Linux avoids read_lock, on the assumption that
(1) First, ptr->next is initialized with NULL.
(2) Later, ptr->next is assigned non-NULL address.
(3) Assigning to ptr->next is done atomically.

Regards.

Re: [TOMOYO 05/15](repost) Domain transition handler functions.

[KaiGai Kohei]

Tetsuo Handa wrote:
> James Morris wrote:
>> I'm pretty sure that the singly linked list idea has been rejected a few 
>> times.  Just use the existing API.
> Too bad...
> 
> Well, is there a way to avoid read_lock when reading list?
> 
> Currently, TOMOYO Linux avoids read_lock, on the assumption that
> (1) First, ptr->next is initialized with NULL.
> (2) Later, ptr->next is assigned non-NULL address.
> (3) Assigning to ptr->next is done atomically.
> 
> Regards.

Is it all of the purpose for the list structure?
If so, you can apply RCU instead to avoid read lock
when scanning the list, like:

rcu_read_lock();
list_for_each_entry(...) {
     ....
}
rcu_read_unlock();

-- 
KaiGai Kohei <kaigai@kaigai.gr.jp>

Re: [TOMOYO 05/15](repost) Domain transition handler functions.

[Tetsuo Handa]

Hello.

KaiGai Kohei wrote:
> If so, you can apply RCU instead to avoid read lock
> when scanning the list, like:
> 
> rcu_read_lock();
> list_for_each_entry(...) {
>      ....
> }
> rcu_read_unlock();

Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't sleep.

If I use RCU, I have to give up " [TOMOYO 13/15] Conditional permission support"
because tmy_check_condition() can sleep.

Regards.

Re: [TOMOYO 05/15](repost) Domain transition handler functions.

[Peter Zijlstra]

On Wed, 2007-10-03 at 22:59 +0900, Tetsuo Handa wrote:
> Hello.
> 
> KaiGai Kohei wrote:
> > If so, you can apply RCU instead to avoid read lock
> > when scanning the list, like:
> > 
> > rcu_read_lock();
> > list_for_each_entry(...) {
> >      ....
> > }
> > rcu_read_unlock();
> 
> Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
> As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't sleep.
> 
> If I use RCU, I have to give up " [TOMOYO 13/15] Conditional permission support"
> because tmy_check_condition() can sleep.

You can indeed not sleep in an rcu_read_lock() section. However, you
could grab a reference on an item, stop the iteration, drop
rcu_read_lock. Do you thing, re-acquire rcu_read_lock(), drop the ref,
and continue the iteration.

Also, how do you avoid referencing dead data with your sll? I haven't
actually looked at your patches, but the simple scheme you outlined
didn't handle the iteration + concurrent removal scenario:

thread 1             thread 2

 foo = ptr->next

 < schedule >

                     killme = ptr->next (same item)
                     ptr->next = ptr->next->next;
                     kfree(killme)

                     < schedule >

 foo->bar <-- *BANG*

Sleeping in RCU list traversal

[Tetsuo Handa]

Hello.

Peter Zijlstra wrote:
> > Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
> > As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't sleep.
> You can indeed not sleep in an rcu_read_lock() section. However, you
> could grab a reference on an item, stop the iteration, drop
> rcu_read_lock. Do you thing, re-acquire rcu_read_lock(), drop the ref,
> and continue the iteration.

Something like this?

  rcu_read_lock();
  list_for_each_rcu(p, ...) {
    ptr = list_entry(p, struct ..., list);
    /* Grab a reference to "ptr". */
    rcu_read_unlock();
    my_task_that_may_sleep(ptr);
    rcu_read_lock();
    /* Drop a reference to "ptr". */
  }
  rcu_read_unlock();

Regarding my case, memory region pointed by "ptr" never be removed.
Do I need to grab a reference to "ptr" ?

Regards.