SMS lock on demand WAS: RE: Possible race condition...

[Sander Striker <st...@apache.org>]

Hi,

> Yes, the implementation is straightforward, but not how you paint it. It
> is actually a lot simpler. I'll present this soon in code. [please be
> patient :) ]

I'll present pseudo code here to clarify what I was thinking about.
I'll do the functions first and then explain how it all hangs
together.

apr_sms_thread_register(sms, os_thread)
{
    if (!sms->lock) {
        sms->lock = apr_lock_create();
    }

    apr_lock_acquire(sms->lock);

    sms->thread_count++;

    /* let the sms know about the thread if it is
     * interested (so it can protect its private
     * data with its own lock)
     */
    if (sms->thread_register_fn)
        sms->thread_register_fn(os_thread);

    pms = sms->parent;
    while (pms) {
       apr_sms_thread_register(os_thread);
       pms = pms->parent;
    }

    apr_lock_release(sms->lock);
}

apr_sms_init(sms, parent)
{
    ...

    sms->thread_count = 1;

    ...
}

apr_sms_post_init(sms)
{
    ...    

    if (sms->thread_register_fn)
        sms->thread_register_fn(apr_os_thread_current());
}

apr_thread_create(..., parent_sms, ...)
{
    ...
    
    [don't know how this is going to fit together in detail
     yet. probably need to call the worker thread function
     from a stub, and put the child pool creation in the stub* ]
    
    os_thread = apr_thread_create(stub, stub_data, SUSPENDED);

    apr_sms_thread_register(parent_sms, os_thread);

    apr_thread_resume(thread);

    ...
}

*) The structure of the stub:

stub(stub_data)
{
   sms = apr_sms_trivial_create(stub_data->parent_sms);

   stub_data->thread_fn(stub_data->thread_data);

   apr_sms_thread_unregister(apr_os_thread_current());
}

Like I said, pseudo. I hope you get and the idea on the lock
creation and the threads showing interest in an sms. Also
note that in the framework and most of the smss the os_thread
parameter can be ignored. Counting is enough. As an initial
implementation the apr_sms_unregister function could just
decrease sms->thread_count, lock destruction has some
difficulties that have to be resolved.

Sander

PS. Using a stub for the thread function could be usefull
    to implement suspended thread creation on platforms
    that don't support that natively (if any).

Re: SMS lock on demand WAS: RE: Possible race condition...

[Brian Pane <bp...@pacbell.net>]

Sander Striker wrote:

>[...]
>
>>>The child thread is register in the parent thread. So, in the case of
>>>the first created thread, a lock will be created. This does not happen
>>>in the stub.
>>>
>>That eliminates the first race condition, but not the second.  
>>Consider this
>>usage:
>>  * There are two global SMSs, sms1 and sms2.
>>  * Two threads, p1 and p2, are created with sms1 as the SMS supplied to
>>    apr_thread_create.
>>  * Prior to the creation of p1 and p2, sms2 is unused.
>>  * p1 creates a child thread, c1, and passes sms2 as the SMS for
>>    apr_thread_create to use.
>>  * p2 creates a child thread, c2, and passes sms2 as the SMS for
>>    apr_thread_create to use.
>>
>>During the last two steps, we're vulnerable to the lock creation
>>race condition.
>>
>
>Ok, I can see that. I must say though that anybody who is actually building
>an application like this is asking for trouble. Tell me, why would
>there need to be 2 global smss that are both used to pass in as a parent
>to thread creation. That is very awkward...
>
It's definitely awkward.  I could see it happening, though, if
somebody builds a library based on APR that creates a global
SMS for thread creation, and then a third party uses this library
in an application that creates its own global SMS and uses it to
create additional threads within callbacks invoked by the library's
threads.  (I'm not claiming that this is a good design, but it's a
good test of the robustness of the registration model.  And it
looks like the model can handle this example properly, by
requiring that p1 and p2 register themselves with sms2 as
noted below.)

>>As far as I know, this isn't a case that will ever happen in Apache,
>>but it's possible in APR based apps in general.  I guess there are
>>two ways to solve it: 1) add code to defend against the race condition,
>>or 2) impose a convention that says that p1 and p2 must register
>>themselves with sms2 before they're allowed to create any other
>>threads that use it.
>>
>
>Actually, they need to anyway. When they are _using_ an sms, which
>they are, in this case sms2, by passing it to apr_thread_create(). In that
>function sms2 is used to allocate the thread structure. This all takes
>place in thread p1/p2. p1 and p2 should have registered themselves with
>sms2 prior to using it.
>
Agreed.  And that resolves all the race conditions that
I was worried about.

--Brian

RE: SMS lock on demand WAS: RE: Possible race condition...

[Sander Striker <st...@apache.org>]

[...]
>> The child thread is register in the parent thread. So, in the case of
>> the first created thread, a lock will be created. This does not happen
>> in the stub.
>
> That eliminates the first race condition, but not the second.  
> Consider this
> usage:
>   * There are two global SMSs, sms1 and sms2.
>   * Two threads, p1 and p2, are created with sms1 as the SMS supplied to
>     apr_thread_create.
>   * Prior to the creation of p1 and p2, sms2 is unused.
>   * p1 creates a child thread, c1, and passes sms2 as the SMS for
>     apr_thread_create to use.
>   * p2 creates a child thread, c2, and passes sms2 as the SMS for
>     apr_thread_create to use.
> 
> During the last two steps, we're vulnerable to the lock creation
> race condition.

Ok, I can see that. I must say though that anybody who is actually building
an application like this is asking for trouble. Tell me, why would
there need to be 2 global smss that are both used to pass in as a parent
to thread creation. That is very awkward...
 
> As far as I know, this isn't a case that will ever happen in Apache,
> but it's possible in APR based apps in general.  I guess there are
> two ways to solve it: 1) add code to defend against the race condition,
> or 2) impose a convention that says that p1 and p2 must register
> themselves with sms2 before they're allowed to create any other
> threads that use it.

Actually, they need to anyway. When they are _using_ an sms, which
they are, in this case sms2, by passing it to apr_thread_create(). In that
function sms2 is used to allocate the thread structure. This all takes
place in thread p1/p2. p1 and p2 should have registered themselves with
sms2 prior to using it.

> --Brian

Sander

Re: SMS lock on demand WAS: RE: Possible race condition...

[Brian Pane <bp...@pacbell.net>]

Sander Striker wrote:

>>Sander Striker wrote:
>>
>>[...]
>>
>>>Coupling the registration to thread creation, rather than SMS creation,
>>>resolves some of the concerns that I listed previously.  But I still have
>>>some questions about what happens during alloc/free in this model.
>>>Is your plan that the alloc/free functions should check sms->thread_count
>>>and do locking if it is greater than 1?
>>>
>>>
>>>No, when the thread_count is increased, the lock is automatically
>>>created in the apr_sms_thread_register function.
>>>
>>>In the code we do this:
>>>
>>>   if (SMS_XXX_T(sms)->lock)
>>>       apr_lock_acquire(SMS_XXX_T(sms)->lock);
>>>
>>I still count two, or maybe three, race conditions here:
>>  * The lock can become non-null between the if-statement and
>>    the allocation code that follows (because somebody registers
>>    with the SMS from another thread).
>>  * In apr_sms_thread_register, two threads can collide in this
>>    part:
>>        if (!sms->lock) {
>>            sms_lock = apr_lock_create();
>>        }
>>    It's possible for a newly created lock to be leaked in this code.
>>  * I'm not sure if the pointer assignment "sms_lock = ..."
>>    is going to be atomic on all the supported architectures.
>>
>>[...]
>>
>
>The child thread is register in the parent thread. So, in the case of
>the first created thread, a lock will be created. This does not happen
>in the stub.
>
That eliminates the first race condition, but not the second.  Consider this
usage:
  * There are two global SMSs, sms1 and sms2.
  * Two threads, p1 and p2, are created with sms1 as the SMS supplied to
    apr_thread_create.
  * Prior to the creation of p1 and p2, sms2 is unused.
  * p1 creates a child thread, c1, and passes sms2 as the SMS for
    apr_thread_create to use.
  * p2 creates a child thread, c2, and passes sms2 as the SMS for
    apr_thread_create to use.

During the last two steps, we're vulnerable to the lock creation
race condition.

As far as I know, this isn't a case that will ever happen in Apache,
but it's possible in APR based apps in general.  I guess there are
two ways to solve it: 1) add code to defend against the race condition,
or 2) impose a convention that says that p1 and p2 must register
themselves with sms2 before they're allowed to create any other
threads that use it.

--Brian

RE: SMS lock on demand WAS: RE: Possible race condition...

[Sander Striker <st...@apache.org>]

> Sander Striker wrote:
>
> [...]
>
> >Coupling the registration to thread creation, rather than SMS creation,
> >resolves some of the concerns that I listed previously.  But I still have
> >some questions about what happens during alloc/free in this model.
> >Is your plan that the alloc/free functions should check sms->thread_count
> >and do locking if it is greater than 1?
> >
> >
> >No, when the thread_count is increased, the lock is automatically
> >created in the apr_sms_thread_register function.
> >
> >In the code we do this:
> >
> >    if (SMS_XXX_T(sms)->lock)
> >        apr_lock_acquire(SMS_XXX_T(sms)->lock);
> >
> I still count two, or maybe three, race conditions here:
>   * The lock can become non-null between the if-statement and
>     the allocation code that follows (because somebody registers
>     with the SMS from another thread).
>   * In apr_sms_thread_register, two threads can collide in this
>     part:
>         if (!sms->lock) {
>             sms_lock = apr_lock_create();
>         }
>     It's possible for a newly created lock to be leaked in this code.
>   * I'm not sure if the pointer assignment "sms_lock = ..."
>     is going to be atomic on all the supported architectures.
>
> [...]

The child thread is register in the parent thread. So, in the case of
the first created thread, a lock will be created. This does not happen
in the stub.

I'm working out details, but I'm sure that we can come up with a solid
solution. Expect some commits in about 4 hours.

> >With regard to the addition of parent_sms as an arg to apr_thread_create,
> >am I right in assuming that NULL is valid value (meaning "don't create
> >a stub and don't incur any locking overhead")?
> >
> >
> >No. You need an sms to create your thread structure from. This
> is going to
> >be the parent (ofcourse, this still assumes that pools are going away).
> >In the thread there will be no locking (since there is only one
> registered
> >thread). If the threads sms needs to fall back on its parent, there will
> >be locking involved. To keep this down to a minimum I'm developing the
> >threads sms. It'll be here real soon now(tm).
> >
> >The stub is needed for the thread registration, so it should not be
> >avoided.
> >
> Makes sense to me.

Sorry, you need it for the unregistration and to register the correct
thread with the child sms (only with the child sms).

> Thanks,
> --Brian
>
>
>
>
>

Re: SMS lock on demand WAS: RE: Possible race condition...

[Brian Pane <bp...@pacbell.net>]

Sander Striker wrote:

[...]

>Coupling the registration to thread creation, rather than SMS creation,
>resolves some of the concerns that I listed previously.  But I still have
>some questions about what happens during alloc/free in this model.
>Is your plan that the alloc/free functions should check sms->thread_count
>and do locking if it is greater than 1?
>
>
>No, when the thread_count is increased, the lock is automatically
>created in the apr_sms_thread_register function.
>
>In the code we do this:
>
>    if (SMS_XXX_T(sms)->lock)
>        apr_lock_acquire(SMS_XXX_T(sms)->lock);
>
I still count two, or maybe three, race conditions here:
  * The lock can become non-null between the if-statement and
    the allocation code that follows (because somebody registers
    with the SMS from another thread).
  * In apr_sms_thread_register, two threads can collide in this
    part:
        if (!sms->lock) {
            sms_lock = apr_lock_create();
        }
    It's possible for a newly created lock to be leaked in this code.
  * I'm not sure if the pointer assignment "sms_lock = ..."
    is going to be atomic on all the supported architectures.

[...]

>With regard to the addition of parent_sms as an arg to apr_thread_create,
>am I right in assuming that NULL is valid value (meaning "don't create
>a stub and don't incur any locking overhead")?
>
>
>No. You need an sms to create your thread structure from. This is going to
>be the parent (ofcourse, this still assumes that pools are going away).
>In the thread there will be no locking (since there is only one registered
>thread). If the threads sms needs to fall back on its parent, there will
>be locking involved. To keep this down to a minimum I'm developing the
>threads sms. It'll be here real soon now(tm).
>
>The stub is needed for the thread registration, so it should not be
>avoided.
>
Makes sense to me.

Thanks,
--Brian

RE: SMS lock on demand WAS: RE: Possible race condition...

[Sander Striker <st...@apache.org>]

[...]
> Thanks!  If I understand this correctly, the only place where the thread
> registration logic is invoked automatically is in thread creation, right?

Yes.

> Coupling the registration to thread creation, rather than SMS creation,
> resolves some of the concerns that I listed previously.  But I still have
> some questions about what happens during alloc/free in this model.
> Is your plan that the alloc/free functions should check sms->thread_count
> and do locking if it is greater than 1?

No, when the thread_count is increased, the lock is automatically
created in the apr_sms_thread_register function.

In the code we do this:

    if (SMS_XXX_T(sms)->lock)
        apr_lock_acquire(SMS_XXX_T(sms)->lock);


> If so, there are two problems:
>   1. The "sms->thread_count++" operation in the registration function
>     is not guaranteed to be atomic.  So the check of 
> "sms->thread_count > 1"
>     in the alloc/free functions would need to be protected by a lock.

Thought of that :)

>   2. There are some SMS types where no locking is needed even if
>     the thread_count is greater than 1, for example the sms_std that
>     just calls malloc/free.

Yes, there is a distinction between framework locking (used for cleanup
registration, child sms registration) and private sms locking (used
for allocations). The std sms doesn't have the private sms lock.
 
> With regard to the addition of parent_sms as an arg to apr_thread_create,
> am I right in assuming that NULL is valid value (meaning "don't create
> a stub and don't incur any locking overhead")?

No. You need an sms to create your thread structure from. This is going to
be the parent (ofcourse, this still assumes that pools are going away).
In the thread there will be no locking (since there is only one registered
thread). If the threads sms needs to fall back on its parent, there will
be locking involved. To keep this down to a minimum I'm developing the
threads sms. It'll be here real soon now(tm).

The stub is needed for the thread registration, so it should not be
avoided.

> --Brian

Sander

Re: SMS lock on demand WAS: RE: Possible race condition...

[Brian Pane <bp...@pacbell.net>]

Sander Striker wrote:

>Hi,
>
>>Yes, the implementation is straightforward, but not how you paint it. It
>>is actually a lot simpler. I'll present this soon in code. [please be
>>patient :) ]
>>
>
>I'll present pseudo code here to clarify what I was thinking about.
>I'll do the functions first and then explain how it all hangs
>together.
>
Thanks!  If I understand this correctly, the only place where the thread
registration logic is invoked automatically is in thread creation, right?

Coupling the registration to thread creation, rather than SMS creation,
resolves some of the concerns that I listed previously.  But I still have
some questions about what happens during alloc/free in this model.
Is your plan that the alloc/free functions should check sms->thread_count
and do locking if it is greater than 1?  If so, there are two problems:
  1. The "sms->thread_count++" operation in the registration function
    is not guaranteed to be atomic.  So the check of "sms->thread_count > 1"
    in the alloc/free functions would need to be protected by a lock.
  2. There are some SMS types where no locking is needed even if
    the thread_count is greater than 1, for example the sms_std that
    just calls malloc/free.

With regard to the addition of parent_sms as an arg to apr_thread_create,
am I right in assuming that NULL is valid value (meaning "don't create
a stub and don't incur any locking overhead")?

--Brian

RE: SMS lock on demand WAS: RE: Possible race condition...

[Sander Striker <st...@apache.org>]

> Hi,
>
> > Yes, the implementation is straightforward, but not how you paint it. It
> > is actually a lot simpler. I'll present this soon in code. [please be
> > patient :) ]
>
> I'll present pseudo code here to clarify what I was thinking about.
> I'll do the functions first and then explain how it all hangs
> together.

Whoops. Guess I didn't explain how it all hung together.
The framework(apr) is to call apr_sms_thread_register()
whenever a new thread is created. The framework is also
responsible for calling apr_sms_thread_unregister whenever
a thread dies.

A simple example (using a before and after sms hierarchy).
Before:

        ...
         | thread 1
         |
        sms A (count 1)
         |
         |
        sms B (count 1)

After newly created thread:

        ...
         | thread 1
         |
        sms A (count 2)
         |
         |
        sms B (count 2)
         |
         |
         +--- ...
         | thread 2
         |
        sms C (count 1)

As can be read from the pseudo code in the
previous mail, A and B now perform locking and
C doesn't.

To allow an application to use an sms in another
thread it knows about, the programmer can call
apr_sms_thread_register(known_sms, os_thread_current())
to show interest manually. Ofcourse, when this
is done the programmer is also responsible for calling
apr_sms_thread_unregister().
This should only occur by exception, not by rule.
I can imagine though that there might be one
global shared memory sms (when we get around to
that) which multiple threads are to use.

Hope this clarifies things a bit more.

Sander

RE: SMS lock on demand WAS: RE: Possible race condition...

[Sander Striker <st...@apache.org>]

> On Mon, 2 Jul 2001, Sander Striker wrote:
>
> > apr_sms_thread_register(sms, os_thread)
> > {
>
> [snip]
>
> >     pms = sms->parent;
> >     while (pms) {
> >        apr_sms_thread_register(os_thread);
> >        pms = pms->parent;
> >     }
>
> [snip]
>
> > }
>
> You don't need a while loop here... the recursion ought to take care of it
> for you.

Ah, indeed. Good it was only pseudo code :)
Actually it should be unrolled in the while loop.
Recursion only slows us down :)

So it would become something like this:

apr_sms_thread_register(sms, os_thread)
{
    do {
        if (!sms->lock) {
            sms->lock = apr_lock_create();
        }

        apr_lock_acquire(sms->lock);

        sms->thread_count++;

        /* let the sms know about the thread if it is
         * interested (so it can protect its private
         * data with its own lock)
         */
        if (sms->thread_register_fn)
            sms->thread_register_fn(os_thread);

        apr_lock_release(sms->lock);

        sms = sms->parent;
    } while (sms);
}

Sander

Re: SMS lock on demand WAS: RE: Possible race condition...

[Cliff Woolley <cl...@yahoo.com>]

On Mon, 2 Jul 2001, Sander Striker wrote:

> apr_sms_thread_register(sms, os_thread)
> {

[snip]

>     pms = sms->parent;
>     while (pms) {
>        apr_sms_thread_register(os_thread);
>        pms = pms->parent;
>     }

[snip]

> }

You don't need a while loop here... the recursion ought to take care of it
for you.

--Cliff

--------------------------------------------------------------
   Cliff Woolley
   cliffwoolley@yahoo.com
   Charlottesville, VA