[std-proposals] Thread preemption inside RCU protected section

[Itaj Sherman]

What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!

When it wakes up, it supposedly continues to run inside the section.

Which means that all rcu protected objects used inside the section have to
be delayed for a long time until after the thread gets scheduled again.

I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.

A tag or some keyword, let’s say PREEMPTION_BREAK that can mark the
enclosed {} section of the protected code:

NON_PREEMPTABLE

{

rcu_reader an_rcu_reader;

my_rcu_type* my_rcu_object = 
;

do_something( *my_rcu_object ); //Some use of protected objects

}

The compiler with OS supports needs to make sure of the following:


1. If the execution gets preempted within the section, it is as-if it calls
an_rcu_reader.unlock() just before the thread got preempted. So that the
thread is not considered inside an rcu protected section anymore, during
the time it won’t be running. And object it protected can be reclaimed.


2.When the thread gets scheduled again, it will restart running from the
beginning of the section NON_PREEMPTABLE (after stack unwinding), as if an
exception was thrown and caught at the section level, and then the section
restarts running (see code below). It doesn’t have to throw immediately at
the preemption position, it can continue running as far as the next time an
instance of an rcu protected type is used, and throw the exception at the
next usage.

Basically the compiler has to add code whenever an instance of an rcu
protected type is used, to check if within a NON_PREEMPTABLE section, and
the thread actually has been preempted after the section started, then
as-if throw an exception.


while(true)

{

try

{

rcu_reader an_rcu_reader;

my_rcu_type* my_rcu_object = 
;

/*Suppose the thread gets preempted here. When rescheduled, it can
continue running only as far as the next usage of *my_rcu_object inside
do_something(), and will “throw std::preemption_exception()” before the
object is accessed.*/

do_something( my_rcu_object ); //Some use of protected objects, function
will dereference it.

}

catch( std::preemption_exception const& )

{

continue; //got preempted, restart section again

}

catch(...)

{

throw;

}

break; //successful, don’t run again.

}

So, the programmer just needs to write the section code as a retryable
transaction.

[Itaj Sherman]

oops, I meant to name the keyword "PREEMPTION_BREAK" instead of
"NON_PREEMPTABLE", but I left both of the words in the post.

Also, the purpose is that the reclamation mechanism knows it only has to
protect object of threads that are currently running on active processors,
and not of threads that got preempted. If a thread actually gets blocked by
the code using a mutex or something, I guess either the developer can take
care of that, or else it would be possible for the compiler to throw
std::preemption_exception() in these cases too.

Post by Itaj Sherman
What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!
When it wakes up, it supposedly continues to run inside the section.
Which means that all rcu protected objects used inside the section have to
be delayed for a long time until after the thread gets scheduled again.
I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.
A tag or some keyword, let’s say PREEMPTION_BREAK that can mark the
NON_PREEMPTABLE
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
do_something( *my_rcu_object ); //Some use of protected objects
}
1. If the execution gets preempted within the section, it is as-if it
calls an_rcu_reader.unlock() just before the thread got preempted. So that
the thread is not considered inside an rcu protected section anymore,
during the time it won’t be running. And object it protected can be
reclaimed.
2.When the thread gets scheduled again, it will restart running from the
beginning of the section NON_PREEMPTABLE (after stack unwinding), as if an
exception was thrown and caught at the section level, and then the section
restarts running (see code below). It doesn’t have to throw immediately at
the preemption position, it can continue running as far as the next time an
instance of an rcu protected type is used, and throw the exception at the
next usage.
Basically the compiler has to add code whenever an instance of an rcu
protected type is used, to check if within a NON_PREEMPTABLE section, and
the thread actually has been preempted after the section started, then
as-if throw an exception.
while(true)
{
try
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
/*Suppose the thread gets preempted here. When rescheduled, it can
continue running only as far as the next usage of *my_rcu_object inside
do_something(), and will “throw std::preemption_exception()” before the
object is accessed.*/
do_something( my_rcu_object ); //Some use of protected objects,
function will dereference it.
}
catch( std::preemption_exception const& )
{
continue; //got preempted, restart section again
}
catch(...)
{
throw;
}
break; //successful, don’t run again.
}
So, the programmer just needs to write the section code as a retryable
transaction.

[Itaj Sherman]

Post by Itaj Sherman
oops, I meant to name the keyword "PREEMPTION_BREAK" instead of
"NON_PREEMPTABLE", but I left both of the words in the post.
Also, the purpose is that the reclamation mechanism knows it only has to
protect object of threads that are currently running on active processors,
and not of threads that got preempted. If a thread actually gets blocked by
the code using a mutex or something, I guess either the developer can take
care of that, or else it would be possible for the compiler to throw
std::preemption_exception() in these cases too.

Post by Itaj Sherman
What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!
When it wakes up, it supposedly continues to run inside the section.
Which means that all rcu protected objects used inside the section have
to be delayed for a long time until after the thread gets scheduled again.
I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.
A tag or some keyword, let’s say PREEMPTION_BREAK that can mark the
NON_PREEMPTABLE
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
do_something( *my_rcu_object ); //Some use of protected objects
}
1. If the execution gets preempted within the section, it is as-if it
calls an_rcu_reader.unlock() just before the thread got preempted. So that
the thread is not considered inside an rcu protected section anymore,
during the time it won’t be running. And object it protected can be
reclaimed.
2.When the thread gets scheduled again, it will restart running from the
beginning of the section NON_PREEMPTABLE (after stack unwinding), as if an
exception was thrown and caught at the section level, and then the section
restarts running (see code below). It doesn’t have to throw immediately at
the preemption position, it can continue running as far as the next time an
instance of an rcu protected type is used, and throw the exception at the
next usage.
Basically the compiler has to add code whenever an instance of an rcu
protected type is used, to check if within a NON_PREEMPTABLE section, and
the thread actually has been preempted after the section started, then
as-if throw an exception.
while(true)
{
try
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
/*Suppose the thread gets preempted here. When rescheduled, it can
continue running only as far as the next usage of *my_rcu_object inside
do_something(), and will “throw std::preemption_exception()” before the
object is accessed.*/
do_something( my_rcu_object ); //Some use of protected objects,
function will dereference it.
}
catch( std::preemption_exception const& )
{
continue; //got preempted, restart section again
}
catch(...)
{
throw;
}
break; //successful, don’t run again.
}
So, the programmer just needs to write the section code as a retryable
transaction.

If there's any access to protected objects inside noexcept functions, it's
going to require a
lot of compiler work.

[Anthony Williams]

Post by Itaj Sherman
What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!

Nothing.

Post by Itaj Sherman
When it wakes up, it supposedly continues to run inside the section.
Which means that all rcu protected objects used inside the section have
to be delayed for a long time until after the thread gets scheduled again.

Yes.

Post by Itaj Sherman
I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.

It is unnecessary. RCU is designed to cope with long grace periods
before reclamation, precisely due to issues like this.

At kernel level, you already have the ability to mark sections of code
non-preemptable.

At user level, this would require the ability to run code when the OS is
preempting you (in order to remove the RCU read tag), which is against
the very concept of preemption, so it is not implementable.

Cheers,

Anthony

[Itaj Sherman]

Post by Anthony Williams

Post by Itaj Sherman
What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!

Nothing.

Post by Itaj Sherman
When it wakes up, it supposedly continues to run inside the section.
Which means that all rcu protected objects used inside the section have
to be delayed for a long time until after the thread gets scheduled

again.
Yes.

Post by Itaj Sherman
I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.

It is unnecessary. RCU is designed to cope with long grace periods
before reclamation, precisely due to issues like this.

Well, I wish it were possible, this could decrease the grace period by

a large factor and simplify the worry about the amount of retired objects.

If a thread with very low priority does get preempted in section, you have

to do something to resolve it.

You force the developer to increase threads’ priorities just to make sure

they run in a manner that doesn’t stall reclamation. In cases where the

developer wouldn’t otherwise wish to do so.

If the reclamation mechanism is going to automatically increase priorities

for threads that got preempted in protected sections, it will need about

the same sort of OS support.

Post by Anthony Williams
At kernel level, you already have the ability to mark sections of code
non-preemptable.
At user level, this would require the ability to run code when the OS is
preempting you (in order to remove the RCU read tag), which is against
the very concept of preemption, so it is not implementable.

Technically you don’t have to run code exactly on the thread when it gets

preempted. But then the reclamation mechanism whenever it runs needs to

be able to query about it and recognize that a thread got preempted while

in protected section.

Or else if it is assumed that all threads in the system use such
PREEMPTION_BREAK,

it can assume that only currently active processors could be in protected
sections.

When the thread gets rescheduled, it will have to be able to run some

code before the execution continues. It has to do something to make

sure that the execution flow eventually changes before the next access

to any protected object. And the OS would have to support some

interrupt handler for that, or some more specialized support.

Otherwise the reclamation mechanism would have to do that,

maybe by somehow directly or indirectly changing the execution position of
the

preempted thread to a separate code that is compiled for this case.

It doesn’t have to be enforced that a preempted section must be restarted,
but it

could at least be known that the implementation is allowed to do it.

Post by Anthony Williams
Cheers,
Anthony

regards,
itaj

[Itaj Sherman]

Post by Itaj Sherman
What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!
When it wakes up, it supposedly continues to run inside the section.
Which means that all rcu protected objects used inside the section have to
be delayed for a long time until after the thread gets scheduled again.
I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.
A tag or some keyword, let’s say PREEMPTION_BREAK that can mark the
NON_PREEMPTABLE
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
do_something( *my_rcu_object ); //Some use of protected objects
}
1. If the execution gets preempted within the section, it is as-if it
calls an_rcu_reader.unlock() just before the thread got preempted. So that
the thread is not considered inside an rcu protected section anymore,
during the time it won’t be running. And object it protected can be
reclaimed.
2.When the thread gets scheduled again, it will restart running from the
beginning of the section NON_PREEMPTABLE (after stack unwinding), as if an
exception was thrown and caught at the section level, and then the section
restarts running (see code below). It doesn’t have to throw immediately at
the preemption position, it can continue running as far as the next time an
instance of an rcu protected type is used, and throw the exception at the
next usage.
Basically the compiler has to add code whenever an instance of an rcu
protected type is used, to check if within a NON_PREEMPTABLE section, and
the thread actually has been preempted after the section started, then
as-if throw an exception.
while(true)
{
try
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
/*Suppose the thread gets preempted here. When rescheduled, it can
continue running only as far as the next usage of *my_rcu_object inside
do_something(), and will “throw std::preemption_exception()” before the
object is accessed.*/
do_something( my_rcu_object ); //Some use of protected objects,
function will dereference it.
}
catch( std::preemption_exception const& )
{
continue; //got preempted, restart section again
}
catch(...)
{
throw;
}
break; //successful, don’t run again.
}
So, the programmer just needs to write the section code as a retryable
transaction.

Well, I guess breaking the protected section isn’t going to be feasible.

How about then enabling the reclamation mechanism to first recognize which
threads have been preempted inside a protected section, and then get a list
of pointers to the specific protected objects that this preempted thread
accessed.

Then it can add just these pointers to a separate protected list and
terminate the grace period.

I guess the thread will have to store all the protected types pointers that
it accesses in a buffer (unique to each thread). Then the reclamation
mechanism will have to read it - I guess it has to know that it
strongly-happens-after the preempted thread has been preempted, or maybe
send a SIGUSR1 to the thread.

Is that possible?

itaj

[Itaj Sherman]

Post by Itaj Sherman

Post by Itaj Sherman
What happens if a user thread enters a section protected by a locked
rcu_reader instance, and gets preempted by the scheduler inside the
section?!
When it wakes up, it supposedly continues to run inside the section.
Which means that all rcu protected objects used inside the section have
to be delayed for a long time until after the thread gets scheduled again.
I want to propose the following suggestion. I really am not sure if it’s
feasible, it needs compiler and OS support that I’m not sure is always
available.
A tag or some keyword, let’s say PREEMPTION_BREAK that can mark the
NON_PREEMPTABLE
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
do_something( *my_rcu_object ); //Some use of protected objects
}
1. If the execution gets preempted within the section, it is as-if it
calls an_rcu_reader.unlock() just before the thread got preempted. So that
the thread is not considered inside an rcu protected section anymore,
during the time it won’t be running. And object it protected can be
reclaimed.
2.When the thread gets scheduled again, it will restart running from the
beginning of the section NON_PREEMPTABLE (after stack unwinding), as if an
exception was thrown and caught at the section level, and then the section
restarts running (see code below). It doesn’t have to throw immediately at
the preemption position, it can continue running as far as the next time an
instance of an rcu protected type is used, and throw the exception at the
next usage.
Basically the compiler has to add code whenever an instance of an rcu
protected type is used, to check if within a NON_PREEMPTABLE section, and
the thread actually has been preempted after the section started, then
as-if throw an exception.
while(true)
{
try
{
rcu_reader an_rcu_reader;
my_rcu_type* my_rcu_object = 
;
/*Suppose the thread gets preempted here. When rescheduled, it can
continue running only as far as the next usage of *my_rcu_object inside
do_something(), and will “throw std::preemption_exception()” before the
object is accessed.*/
do_something( my_rcu_object ); //Some use of protected objects,
function will dereference it.
}
catch( std::preemption_exception const& )
{
continue; //got preempted, restart section again
}
catch(...)
{
throw;
}
break; //successful, don’t run again.
}
So, the programmer just needs to write the section code as a retryable
transaction.

Well, I guess breaking the protected section isn’t going to be feasible.
How about then enabling the reclamation mechanism to first recognize which
threads have been preempted inside a protected section, and then get a list
of pointers to the specific protected objects that this preempted thread
accessed.
Then it can add just these pointers to a separate protected list and
terminate the grace period.
I guess the thread will have to store all the protected types pointers
that it accesses in a buffer (unique to each thread). Then the reclamation
mechanism will have to read it - I guess it has to know that it
strongly-happens-after the preempted thread has been preempted, or maybe
send a SIGUSR1 to the thread.
Is that possible?
itaj

If it could be done inside a SIGUSR1, then the list doesn't need to contain
all addresses that were read. It only needs addresses that the thread
already had gotten, and might access after it is rescheduled - which means
they are all accessible through variables on the thread's stack.

Then it wouldn't need a separate buffer. It's just have to be so that all
these addresses are kept in special pointer objects, instead of raw
pointers. Then it could be some generalized linked list that resides inside
the thread’s stack.
For local variable pointers, instead of T* use protected_ptr<T> (code
below).

It’s somewhat like the hazard pointer usage, but they’re stored only on the
stack with non-atomic operations.
If the thread collects addresses in some containers then more specialized
classes have to be defined. E.g. For some_container<T*> there would have to
be a compatible some_container_of_protected_ptr<T>. And ultimately the list
could be read by calling a thread_local function object.

struct protected_address_node

{

void const* p_; //or some other type erasure

protected_address_node* next_;

};

thread_local protected_address_node* protected_list_head_ = nullptr;

template< typename T >

class protected_ptr

{

private:

T* p_;

protected_address_node node_;

public:

protected_ptr( T* p )

:

p_(p),

node_{ static_cast<...>(p), protected_list_head_ }

{

protected_list_head_ = &node_;

}

~protected_ptr()

{

protected_list_head_ = node_.next_;

}

T* get() const { return p_; }

};

itaj