failed assertion in `relacy/context.hpp line: 569'...

[Chris M. Thomasson]

Here is the program which causes the specific assertion to fail:

http://relacy.pastebin.com/f6d1093e2

I am trying to model the lock-based version of my vZOOM algorithm in
Relacy 2.0. You have a comment in the source code at that specific
line which reads as follows:
_________________________________________________________________
// If you hit assert here, then probably your test is non-
deterministic
// Check whether you are using functions like ::rand() or static
variables in your test
// Replace ::rand() with rl::rand(), eliminate static variables in the
test
RL_VERIFY(second == false);
(void)second;
_________________________________________________________________



Can you see what I am doing wrong? How can I resolve this issue?


Thanks!!!

[Dmitriy Vyukov]

Hi Chris!

I think the source of non-determinism is operation of taking object's
address.
I've described the problem here:
http://groups.google.com/group/relacy/web/known-issues

I will try to fix it so that it will as least work as-is.
And probably add special function rl::hash_ptr(ptr[, table_size]) in
order to provide better coverage for different situation (no
collisions, small amount of collisions, all objects hash to single
cell, etc).


--
Dmitriy V'jukov

[Dmitriy Vyukov]

One possible workaround is to assign hashes to objects manually. I.e.:

struct object_base
{
size_t hash;
};

struct your_object : object_base
{
//...
};

//...

struct test_suite
{
size_t hash_seq;
// note that hash_seq is plain size_t (not rl::atomic, nor rl::var)

static size_t const table_size = 100;
size_t hash_table [table_size];

void before()
{
hash_seq = 0;
}

void thread(unsigned)
{
//...
your_object* obj = new your_object;
obj->hash = hash_seq++;
//...
// use obj->hash instead of hashing of pointer
table[obj->hash % table_size] += 1;
//...
}
};

Another variation that will provide better coverage is to use rl::rand
() to assign hashes:

obj->hash = rl::rand(table_size);

Under random scheduler rl::rand() will just produce some pseudo-random
numbers. But under full/context bound scheduler rl::rand() will
produce ALL possible combinations, so if you have 10 objects and
table_size=100, state space will increase 100^10 times (so use with
caution).

--
Dmitriy V'jukov

[Chris M. Thomasson]

I think I accidentally emailed you my last response. I will see what I
can come up with and post it here.


Thanks Dmitriy.

[Chris M. Thomasson]

Check this out:


http://relacy.pastebin.com/f4de5c3


I commented out all of the test code in which a reader thread keeps
references to objects. I defined RL_GC, and I am getting a access to
freed memory error. I commented out all calls to delete. Nothing gets
deleted, and I am still getting access to freed memory. This seems odd
to me. What am I doing wrong? Do you think it's a bug in my test code?

[Dmitriy Vyukov]

I think the problem is that hash values (foo::m_vzhash) are greater
than table size. As far as I see, you create READERS*ITERS objects,
i.e. 33 objects with hashes 0..32. And table size is VZOOM_REFS=16.
Unable to verify the hypothesis right now, but I do not see where you
do "hash % VZOOM_REFS" part.

--
Dmitriy V'jukov

[Chris M. Thomasson]

STUPID ME!!!!!!!!!!

LOL!



Here, let me fix that:

http://relacy.pastebin.com/f11a73ec8


Sorry!

;^o

[Chris M. Thomasson]

On Dec 1, 3:25 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:

[...]

> Here, let me fix that:
>
> http://relacy.pastebin.com/f11a73ec8

This runs till it gets to around 30 percent then the process starts
using memory uncontrollably and does not stop. The process eventually
crashes. I need to run it in Debug mode to see if any assertions are
being tripped.

[Chris M. Thomasson]

This one passes 10,000,000 iterations in release and debug mode:


http://relacy.pastebin.com/f5492b1cf


I should check about 50,000,000 iterations. I can start the test at
10,000,000 iterations by setting `rl::test_params::initial_state' to
"10000000" right?

[Dmitriy Vyukov]

I will investigate.

--
Dmitriy V'jukov

[Dmitriy Vyukov]

On 2 дек, 09:05, "Chris M. Thomasson" <cris...@charter.net> wrote:
> On Dec 1, 4:07 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
> > On Dec 1, 3:25 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
> > [...]
>
> > > Here, let me fix that:
>
> > >http://relacy.pastebin.com/f11a73ec8
>
> > This runs till it gets to around 30 percent then the process starts
> > using memory uncontrollably and does not stop. The process eventually
> > crashes. I need to run it in Debug mode to see if any assertions are
> > being tripped.
>
> This one passes 10,000,000 iterations in release and debug mode:
>
> http://relacy.pastebin.com/f5492b1cf
>
> I should check about 50,000,000 iterations.

How this one differs from above one that crashes?

> I can start the test at
> 10,000,000 iterations by setting `rl::test_params::initial_state' to
> "10000000" right?

Yes. The verification will "continue" from 10000000 iteration, i.e.
that will be iterations different from first 10000000.

--
Dmitriy V'jukov

[Dmitriy Vyukov]

On Dec 2, 9:27 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> > > [...]
>
> > > > Here, let me fix that:
>
> > > >http://relacy.pastebin.com/f11a73ec8
>
> > > This runs till it gets to around 30 percent then the process starts
> > > using memory uncontrollably and does not stop. The process eventually
> > > crashes. I need to run it in Debug mode to see if any assertions are
> > > being tripped.
>
> > This one passes 10,000,000 iterations in release and debug mode:
>
> >http://relacy.pastebin.com/f5492b1cf
>
> > I should check about 50,000,000 iterations.
>
> How this one differs from above one that crashes?

Ah, ok, I see, pastebin features diff feature. Is it correct diff?
http://relacy.pastebin.com/pastebin.php?diff=f5492b1cf

So you make m_head/m_tail of non_thread_safe_queue plain vars instead
of rl::var<>. And replace yield(1) with a kind of linear-backoff yield
(1..4). Right?

--
Dmitriy V'jukov

[Dmitriy Vyukov]

I think I see that's the problem.
Relacy detects some problem, and then starts building execution
history. And it seems that execution history is just too big. Yes,
that big so it consumes whole 32-bit address space.
You know, it's coded in 'modern' style, so that there are several
std::sringstreams involved and a lot of copying and temporal strings
and so on.

I'm able to model the issue with simple test:
VAR_T(int) x;
std::atomic<int> y;
for (;;)
{
for (int i = 0; i != 100; i += 1)
VAR(x) = 0;
y.store(0, std::memory_order_relaxed);
}

You set p.execution_depth_limit = 10000, but it does not count
operations on VAR_T variables (because they do not call scheduler),
however operations on VAR_T participate in history. So actual history
size can be much bigger than 10000.

I will optimize history output to handle big histories gracefully.

As for now, you may replace some VAR_T with plain vars... or switch to
64-bit mode.

--
Dmitriy V'jukov

[Chris M. Thomasson]

Thank you. Can I hack Relacy in order to prevent it from creating an
execution history? Let's say if Relacy detects a problem alls I want
it do is print "CRASH!" to the screen and terminate the simulation.

> As for now, you may replace some VAR_T with plain vars...

I think I will greatly reduce the complexity of the test. All's I
really need is a single memory location, writers just exchange object
in and out, reader threads would keep a single loaded pointer from it.
_______________________________________________________________
struct foo
{
size_t const m_hash;
};

std::atomic<foo*> g_foo;

// writers
for (i = 0; i < ITERS; ++i)
{
foo* f = g_foo.exchange(foo_factory());

if (f)
{
g_vZOOM[tidx].defer(f);
}

rl::yield(1, $);
}


// readers
foo* f = NULL;
unsigned int i = 0;
while_there_are_writers()
{
if (! (i % 2))
{
if (f)
{
g_vZOOM[tidx].dec(f);
f = NULL;
}
}

if (f)
{
size_t hash = f->hash;
RL_ASSERT(hash < REFS);
}

if (! (i % 2))
{
if (! f)
{
f = g_foo.load();
}
}

// sync

++i;

rl::yield(1, $);
}
_______________________________________________________________

[Chris M. Thomasson]

On Dec 1, 11:24 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> On Dec 2, 9:27 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
>
>
>
>
> > > > [...]
>
> > > > > Here, let me fix that:
>
> > > > >http://relacy.pastebin.com/f11a73ec8
>
> > > > This runs till it gets to around 30 percent then the process starts
> > > > using memory uncontrollably and does not stop. The process eventually
> > > > crashes. I need to run it in Debug mode to see if any assertions are
> > > > being tripped.
>
> > > This one passes 10,000,000 iterations in release and debug mode:
>
> > >http://relacy.pastebin.com/f5492b1cf
>
> > > I should check about 50,000,000 iterations.
>
> > How this one differs from above one that crashes?
>

> Ah, ok, I see, pastebin features diff feature. Is it correct diff?http://relacy.pastebin.com/pastebin.php?diff=f5492b1cf

>
> So you make m_head/m_tail of non_thread_safe_queue plain vars instead
> of rl::var<>. And replace yield(1) with a kind of linear-backoff yield
> (1..4). Right?

Right. Humm... I actually don't need any `rl::var<>' in this test. All
that I need Relacy to do is detect access to freed memory.

[Chris M. Thomasson]

On Dec 2, 3:10 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> On Dec 2, 3:07 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
> > On Dec 1, 3:25 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
> > [...]
>
> > > Here, let me fix that:
>
> > >http://relacy.pastebin.com/f11a73ec8
>
> > This runs till it gets to around 30 percent then the process starts
> > using memory uncontrollably and does not stop. The process eventually
> > crashes. I need to run it in Debug mode to see if any assertions are
> > being tripped.
>
> I think I see that's the problem.

[...]

> As for now, you may replace some VAR_T with plain vars... or switch to
> 64-bit mode.

Here is a simplified test that passes 100,000,000 iterations:

http://relacy.pastebin.com/f200c5375

Everything seems to be working fine.