Using Relacy with Boost.Thread

[edward]

Hi,

I have some code that uses Boost.Thread that I would like to test with
Relacy. Unfortunately, it makes use of
boost::recursive_timed_mutex.timed_lock(). It looks like Relacy has no
support for such a function? If not, are there any suggestions for how
I might be able to workaround this problem? The code involved is a
synchronization primitive class that has a "bool lock()" function that
returns false upon detecting a deadlock amongst all instances of the
class.

Thanks in advance!

Regards,
-Edward

[Dmitriy Vyukov]

Hi Edward,

Relacy contains rl::mutex/rl::recursive_mutex which are modeled after
std::mutex/recursive_mutex (C++0x). If you do not need timed_wait
functionality then you may use them.
And if you need timed_wait functionality... well, I decided to not
model boost.thread API in this release, because it's one more API and
a lot of additional work.
But boost::recursive_timed_mutex can be quite easily modeled with, for
example, semaphore.
Here it is:


class recursive_timed_mutex
{
public:
recursive_timed_mutex()
{
sema.init(false, 1, 1, $);
owner = -1;
recursion_count = 0;
}

~recursive_timed_mutex()
{
assert(owner == -1 && recursion_count == 0);
sema.deinit($);
}

void lock(rl::debug_info_param info)
{
rl::context& c = rl::ctx();
if (owner == c.current_thread())
{
RL_HIST(rl::user_msg_event) {"recursive mutex lock"}
RL_HIST_END();
assert(recursion_count > 0);
recursion_count += 1;
}
else
{
sema.wait(false, false, info);
assert(owner == -1 && recursion_count == 0);
owner = c.current_thread();
recursion_count = 1;
}
}

bool try_lock(rl::debug_info_param info)
{
rl::context& c = rl::ctx();
if (owner == c.current_thread())
{
RL_HIST(rl::user_msg_event) {"recursive mutex try lock"}
RL_HIST_END();
assert(recursion_count > 0);
recursion_count += 1;
return true;
}
else
{
rl::sema_wakeup_reason r = sema.wait(true, false, info);
if (r == rl::sema_wakeup_reason_success)
{
assert(owner == -1 && recursion_count == 0);
owner = c.current_thread();
recursion_count = 1;
return true;
}
else
{
return false;
}
}
}

void unlock(rl::debug_info_param info)
{
rl::context& c = rl::ctx();
assert(owner == c.current_thread() && recursion_count > 0);
RL_HIST(rl::user_msg_event) {"recursive mutex unlock"}
RL_HIST_END();
recursion_count -= 1;
if (recursion_count == 0)
{
owner = -1;
unsigned prev;
sema.post(1, prev, info);
}
}

bool timed_lock(rl::debug_info_param info, ... /*abs_time*/)
{
rl::context& c = rl::ctx();
if (owner == c.current_thread())
{
RL_HIST(rl::user_msg_event) {"recursive mutex timed lock"}
RL_HIST_END();
assert(recursion_count > 0);
recursion_count += 1;
return true;
}
else
{
rl::sema_wakeup_reason r = sema.wait(false, true, info);
if (r == rl::sema_wakeup_reason_success)
{
assert(owner == -1 && recursion_count == 0);
owner = c.current_thread();
recursion_count = 1;
return true;
}
else
{
return false;
}
}
}

private:
struct tag_t;
rl::semaphore<tag_t> sema;
rl::thread_id_t owner;
int recursion_count;

recursive_timed_mutex(recursive_timed_mutex const&);
recursive_timed_mutex& operator = (recursive_timed_mutex const&);
};


--
Dmitriy V'jukov

[Dmitriy Vyukov]

On Nov 3, 7:52 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> On Nov 3, 6:41 am, edward <e4...@yahoo.com> wrote:
>
> > Hi,
>
> > I have some code that uses Boost.Thread that I would like to test with
> > Relacy. Unfortunately, it makes use of
> > boost::recursive_timed_mutex.timed_lock(). It looks like Relacy has no
> > support for such a function? If not, are there any suggestions for how
> > I might be able to workaround this problem? The code involved is a
> > synchronization primitive class that has a "bool lock()" function that
> > returns false upon detecting a deadlock amongst all instances of the
> > class.
>
> Hi Edward,
>
> Relacy contains rl::mutex/rl::recursive_mutex which are modeled after
> std::mutex/recursive_mutex (C++0x). If you do not need timed_wait
> functionality then you may use them.
> And if you need timed_wait functionality... well, I decided to not
> model boost.thread API in this release, because it's one more API and
> a lot of additional work.
> But boost::recursive_timed_mutex can be quite easily modeled with, for
> example, semaphore.
> Here it is:
>
> class recursive_timed_mutex

After I've created it I realize that Win32 Mutex is actually what you
need. You may just wrap recursive_timed_mutex around Win32 Mutex:

class recursive_timed_mutex
{
public:
recursive_timed_mutex()
{
mtx = CreateMutex(0, 0, 0);
}

~recursive_timed_mutex()
{
CloseHandle(mtx);
}

void lock(rl::debug_info_param info)
{
rl::rl_WaitForSingleObject(mtx, INFINITE, info);
}

bool try_lock(rl::debug_info_param info)
{
return WAIT_OBJECT_0 == rl::rl_WaitForSingleObject(mtx, 0,
info);
}

void unlock(rl::debug_info_param info)
{
rl::rl_ReleaseMutex(mtx, info);

}

bool timed_lock(rl::debug_info_param info, ... /*abs_time*/)
{

return WAIT_OBJECT_0 == rl::rl_WaitForSingleObject(mtx, 1,
info);
}

private:
HANDLE mtx;

recursive_timed_mutex(recursive_timed_mutex const&);
recursive_timed_mutex& operator = (recursive_timed_mutex const&);
};

Unfortunately I've found that my emulation of Win32 Mutex is not
recursive (it must be), and my tests do not cover that. I've fixed
that in my working release.
You may fix it in RRD v2.0 manually. In file ./relacy/stdlib/
windows.hpp, line 251 change:
mtx->init(false, false, false, false, info);
to:
mtx->init(false, true, false, false, info);


--
Dmitriy V'jukov

[Dmitriy Vyukov]

Don't worry that it's Win32 only API, it's modeled by Relacy anyway,
so may use it on Linux too.

Note that in real life one probably will try to avoid Win32 Mutex
because it's kernel object. But when modeled by Relacy it's actually
the same as user-space lightweight mutex.

--
Dmitriy V'jukov

[edward]

On Nov 3, 11:20 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Don't worry that it's Win32 only API, it's modeled by Relacy anyway,
> so may use it on Linux too.
>
> Note that in real life one probably will try to avoid Win32 Mutex
> because it's kernel object. But when modeled by Relacy it's actually
> the same as user-space lightweight mutex.

Thanks, Dmitriy! I have finally managed to integrate Relacy into my
code but haven't gotten to the stage of writing the testsuite yet. I'm
sure I'll have more questions. :)

Thanks,
-Edward

[edward]

On Nov 3, 11:06 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> After I've created it I realize that Win32 Mutex is actually what you
> need. You may just wrap recursive_timed_mutex around Win32 Mutex:

On a related note, it might also be worthwhile adding a
pthread_mutex_timedlock() wrapper in Relacy since all the code to
support it is already there.

Regards,
-Edward

[edward]

Hi Dmitriy,

On Nov 3, 11:06 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> After I've created it I realize that Win32 Mutex is actually what you
> need. You may just wrap recursive_timed_mutex around Win32 Mutex:

Using this approach, I've found that I can easily run into LIVELOCK
situations under Relacy that I don't think can happen in the real
world. Take a look at the log below where I've added RL_LOG() to show
the timeout that I am giving Relacy:

[25] 1: Locking for 200
[26] 1: <00000001DA0FE088> mutex: blocking
[27] 1: blocking current thread [timed]
[28] 0: <0000000004636EA0> atomic store, value=0000000004628FC0, (prev
value=0000000000000000), order=seq_cst
[29] 0: Locking for 200
[30] 0: <00000001DA0FDFA8> mutex: blocking
[31] 0: blocking current thread [timed]
[32] 0: <0000000004628FC8> atomic load, value=1, order=seq_cst
[33] 0: Locking for 400
[34] 0: <00000001DA0FDFA8> mutex: blocking
[35] 0: blocking current thread [timed]
[36] 0: <0000000004628FC8> atomic load, value=1, order=seq_cst
[37] 0: Locking for 800
[38] 0: <00000001DA0FDFA8> mutex: blocking
[39] 0: blocking current thread [timed]

What is happening here is that thread 1 is supposed to block for 200
ms while thread 0 repeatedly re-locks in an exponential backoff
fashion (starting with 200 ms) until thread 1 takes some action to
cause it to quit. The problem here is that thread 1 never gets
unblocked until AFTER we've reached a LIVELOCK condition. I would have
expected thread 1 to be scheduled at operation [36]. But instead,
Relacy keeps scheduling thread 0 to be run over and over again.

Am I missing something here or is there a bug in Relacy?

Note that in this case, I'm simulating using the
fair_context_bound_scheduler_type. I suspect the crashes before I was
getting with fair_context_bound_scheduler_type was because of the
dining philosopheres test case being too complicated.

Thanks,
-Edward

[Dmitriy Vyukov]

Accepted


--
Dmitriy V'jukov

[Dmitriy Vyukov]

Hi Edward,

Yes, it's a known issue... at least for me :)
I've created a page "Known Issues" to describe such things:
http://groups.google.com/group/relacy/web/known-issues

As a workaround you can manually add yield calls (pthread_yield(),
SwitchToThread()) after timed waits.

> Note that in this case, I'm simulating using the
> fair_context_bound_scheduler_type. I suspect the crashes before I was
> getting with fair_context_bound_scheduler_type was because of the
> dining philosopheres test case being too complicated.

Well, it's intended that Relacy verifies complicated code too :) So I
am interested in fixing it once I localize it.

--
Dmitriy V'jukov

[edward]

Hi Dmitriy,

On Nov 30, 2:02 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> As a workaround you can manually add yield calls (pthread_yield(),
> SwitchToThread()) after timed waits.

Actually, I did try to yield() previously but it didn't work. I just
confirmed that it doesn't work again.

Here's a sample trace:

[41] 1: <00000000045DA5F8> mutex: blocking
[42] 1: blocking current thread [timed]
[43] 0: <00000000045E5CE8> atomic load, value=0, order=relaxed
[44] 0: <00000000045E5C98> atomic load, value=1, order=seq_cst
[45] 0: <00000000045DA518> mutex: blocking
[46] 0: blocking current thread [timed]
[47] 0: yield(1)
[48] 0: <00000000045E5CE8> atomic load, value=0, order=relaxed
[49] 0: <00000000045E5C98> atomic load, value=1, order=seq_cst
[50] 0: <00000000045DA518> mutex: blocking
[51] 0: blocking current thread [timed]
[52] 0: yield(1)
[53] 0: <00000000045E5CE8> atomic load, value=0, order=relaxed
[54] 0: <00000000045E5C98> atomic load, value=1, order=seq_cst
[55] 0: <00000000045DA518> mutex: blocking
[56] 0: blocking current thread [timed]
[57] 0: yield(1)
... repeat lots

I would expect that after the yield(1) call, the scheduler would
automatically run some code from thread 1 but it doesn't seem to do
that. What am I doing wrong?

Thanks,
-Edward

[Dmitriy Vyukov]

Hi Edward,

I think you are doing everything right, the problem is in Relacy.
I guess the problem arises because thread 1 is blocked so yield() in
thread 0 does not actually yielding anything...

I am looking at your execution history...
Thread 1 is blocked on mutex <00000000045DA5F8>.
And thread 0 constantly tries to acquire mutex <00000000045DA518> but
constantly fails.
So who does hold mutex <00000000045DA518>? Is it thread 1? Or some
other thread?

--
Dmitriy V'jukov

[edward]

Hi Dmitriy,

On Dec 2, 1:38 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> I am looking at your execution history...
> Thread 1 is blocked on mutex <00000000045DA5F8>.
> And thread 0 constantly tries to acquire mutex <00000000045DA518> but
> constantly fails.
> So who does hold mutex <00000000045DA518>? Is it thread 1? Or some
> other thread?

Yes, thread 1 holds the mutex. There are only 2 threads in my test and
here is the code for the thread function:

void thread(int thread_index)
{
AbortableLock::ScopedLock left_fork;
AbortableLock::ScopedLock right_fork;
int left = thread_index;
int right = (thread_index+1) % 2;

if (left_fork.lock(myForks[left]))
right_fork.lock(myForks[right]);
}

I apologize not posting this earlier. The AbortableLock class wraps
around a single timed_mutex that it uses for actual mutual exclusion.

-Edward

[Dmitriy Vyukov]

Humm... I need to think about this.

--
Dmitriy V'jukov