Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
C++11 crude seqlock...
15 views
Skip to first unread message
Chris M. Thomasson
Mar 1, 2021, 9:53:06 PM3/1/21
to
Fwiw, here is a simple implementation of a seqlock under Relacy Race
Detector. Now, this needs std::memory_order_seq_cst in order to get it
to work, however, I am trying to find a way around that nasty membar.
However, the ct_seqlock::read_enter/read_try_leave functions only does
loads, but uses that damn seq_cst. The idea is to use this for a
distributed poor mans RCU where there would be a seqlock per thread. It
is crucial that a reader does not mutate state on a remote thread. So,
loads are very important here.
Here is the Relacy code:
__________________________________
// Chris M. Thomassons SeqLock Test
//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
#include <relacy/relacy_std.hpp>
#include <cstdio>
#include <cstddef>
#if ! defined (NDEBUG)
# define DBG_PRINTF(e) std::printf e
#else
# define DBG_PRINTF(e) ((void)0)
#endif
struct ct_seqlock
{
std::atomic<unsigned long> m_seq;
std::mutex m_lock;
ct_seqlock() : m_seq(0) {}
unsigned long read_enter()
{
unsigned long seq = 0;
for (;;)
{
seq = m_seq.load(std::memory_order_seq_cst);
if (! (seq & 1)) break;
rl::yield(1, $);
}
return seq;
}
bool read_try_leave(unsigned long cmp_seq)
{
unsigned long seq = m_seq.load(std::memory_order_seq_cst);
return (seq == cmp_seq);
}
void write_lock()
{
m_lock.lock($);
m_seq.fetch_add(1, std::memory_order_seq_cst);
}
void write_unlock()
{
m_seq.fetch_add(1, std::memory_order_release);
m_lock.unlock($);
}
};
#define ITERS 3
#define WRITERS 2
#define READERS 5
#define THREADS (WRITERS + READERS)
struct proxy_test
: rl::test_suite<proxy_test, THREADS>
{
ct_seqlock g_seqlock;
std::atomic<int> g_var_0;
std::atomic<int> g_var_1;
proxy_test() : g_var_0(0), g_var_1(0) {}
~proxy_test()
{
int var_0 = g_var_0.load(std::memory_order_relaxed);
int var_1 = g_var_1.load(std::memory_order_relaxed);
RL_ASSERT(var_0 == var_1);
}
void thread(unsigned int tidx)
{
if (tidx < READERS)
{
// readers
for (unsigned long i = 0; i < ITERS; ++i)
{
unsigned long cmp_seq = 0;
int var_0 = 0;
int var_1 = 0;
do
{
cmp_seq = g_seqlock.read_enter();
var_0 = g_var_0.load(std::memory_order_relaxed);
var_1 = g_var_1.load(std::memory_order_relaxed);
} while (! g_seqlock.read_try_leave(cmp_seq));
RL_ASSERT(var_0 == var_1);
}
}
else
{
// writers
for (unsigned long i = 0; i < ITERS; ++i)
{
g_seqlock.write_lock();
int var_0 = g_var_0.load(std::memory_order_relaxed);
int var_1 = g_var_1.load(std::memory_order_relaxed);
rl::yield(1, $);
g_var_1.store(var_1 + 1, std::memory_order_relaxed);
g_var_0.store(var_0 + 1, std::memory_order_relaxed);
g_seqlock.write_unlock();
}
}
}
};
int main()
{
{
rl::test_params p;
p.iteration_count = 20000000;
p.execution_depth_limit = 10000;
//p.search_type = rl::sched_bound;
//p.search_type = rl::fair_full_search_scheduler_type;
//p.search_type = rl::fair_context_bound_scheduler_type;
rl::simulate<proxy_test>(p);
}
return 0;
}
__________________________________
Humm... Will post a pure C++ port for everybody to compile, and give it
a go.
Detector. Now, this needs std::memory_order_seq_cst in order to get it
to work, however, I am trying to find a way around that nasty membar.
However, the ct_seqlock::read_enter/read_try_leave functions only does
loads, but uses that damn seq_cst. The idea is to use this for a
distributed poor mans RCU where there would be a seqlock per thread. It
is crucial that a reader does not mutate state on a remote thread. So,
loads are very important here.
Here is the Relacy code:
__________________________________
// Chris M. Thomassons SeqLock Test
//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
#include <relacy/relacy_std.hpp>
#include <cstdio>
#include <cstddef>
#if ! defined (NDEBUG)
# define DBG_PRINTF(e) std::printf e
#else
# define DBG_PRINTF(e) ((void)0)
#endif
struct ct_seqlock
{
std::atomic<unsigned long> m_seq;
std::mutex m_lock;
ct_seqlock() : m_seq(0) {}
unsigned long read_enter()
{
unsigned long seq = 0;
for (;;)
{
seq = m_seq.load(std::memory_order_seq_cst);
if (! (seq & 1)) break;
rl::yield(1, $);
}
return seq;
}
bool read_try_leave(unsigned long cmp_seq)
{
unsigned long seq = m_seq.load(std::memory_order_seq_cst);
return (seq == cmp_seq);
}
void write_lock()
{
m_lock.lock($);
m_seq.fetch_add(1, std::memory_order_seq_cst);
}
void write_unlock()
{
m_seq.fetch_add(1, std::memory_order_release);
m_lock.unlock($);
}
};
#define ITERS 3
#define WRITERS 2
#define READERS 5
#define THREADS (WRITERS + READERS)
struct proxy_test
: rl::test_suite<proxy_test, THREADS>
{
ct_seqlock g_seqlock;
std::atomic<int> g_var_0;
std::atomic<int> g_var_1;
proxy_test() : g_var_0(0), g_var_1(0) {}
~proxy_test()
{
int var_0 = g_var_0.load(std::memory_order_relaxed);
int var_1 = g_var_1.load(std::memory_order_relaxed);
RL_ASSERT(var_0 == var_1);
}
void thread(unsigned int tidx)
{
if (tidx < READERS)
{
// readers
for (unsigned long i = 0; i < ITERS; ++i)
{
unsigned long cmp_seq = 0;
int var_0 = 0;
int var_1 = 0;
do
{
cmp_seq = g_seqlock.read_enter();
var_0 = g_var_0.load(std::memory_order_relaxed);
var_1 = g_var_1.load(std::memory_order_relaxed);
} while (! g_seqlock.read_try_leave(cmp_seq));
RL_ASSERT(var_0 == var_1);
}
}
else
{
// writers
for (unsigned long i = 0; i < ITERS; ++i)
{
g_seqlock.write_lock();
int var_0 = g_var_0.load(std::memory_order_relaxed);
int var_1 = g_var_1.load(std::memory_order_relaxed);
rl::yield(1, $);
g_var_1.store(var_1 + 1, std::memory_order_relaxed);
g_var_0.store(var_0 + 1, std::memory_order_relaxed);
g_seqlock.write_unlock();
}
}
}
};
int main()
{
{
rl::test_params p;
p.iteration_count = 20000000;
p.execution_depth_limit = 10000;
//p.search_type = rl::sched_bound;
//p.search_type = rl::fair_full_search_scheduler_type;
//p.search_type = rl::fair_context_bound_scheduler_type;
rl::simulate<proxy_test>(p);
}
return 0;
}
__________________________________
Humm... Will post a pure C++ port for everybody to compile, and give it
a go.
Chris M. Thomasson
Mar 1, 2021, 9:59:06 PM3/1/21
to
On 3/1/2021 6:52 PM, Chris M. Thomasson wrote:
> Fwiw, here is a simple implementation of a seqlock under Relacy Race
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
>
>
> Here is the Relacy code:
> __________________________________
> // Chris M. Thomassons SeqLock Test
>[...]
> Fwiw, here is a simple implementation of a seqlock under Relacy Race
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
>
>
> Here is the Relacy code:
> __________________________________
> // Chris M. Thomassons SeqLock Test
> __________________________________
>
>
>
> Humm... Will post a pure C++ port for everybody to compile, and give it
> a go.
I to talk to Dmitry Vyukov. Still not exactly sure why seq_cst is
>
>
>
> Humm... Will post a pure C++ port for everybody to compile, and give it
> a go.
required. Humm... I got away with a release membar on incrementing the
version count right before releasing the lock:
Chris M. Thomasson
Mar 1, 2021, 10:01:55 PM3/1/21
to
On 3/1/2021 6:52 PM, Chris M. Thomasson wrote:
> Fwiw, here is a simple implementation of a seqlock under Relacy Race
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
>
>
> Here is the Relacy code:
> __________________________________
> // Chris M. Thomassons SeqLock Test
[...]
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
>
>
> Here is the Relacy code:
> __________________________________
> // Chris M. Thomassons SeqLock Test
> void thread(unsigned int tidx)
> {
> if (tidx < READERS)
> {
> // readers
>
[...]
> {
> if (tidx < READERS)
> {
> // readers
>
> }
>
> else
> {
> // writers
> for (unsigned long i = 0; i < ITERS; ++i)
> {
> g_seqlock.write_lock();
>
> int var_0 = g_var_0.load(std::memory_order_relaxed);
> int var_1 = g_var_1.load(std::memory_order_relaxed);
>
> rl::yield(1, $);
>
> g_var_1.store(var_1 + 1, std::memory_order_relaxed);
> g_var_0.store(var_0 + 1, std::memory_order_relaxed);
>
> g_seqlock.write_unlock();
> }
> }
[...]
>
> else
> {
> // writers
> for (unsigned long i = 0; i < ITERS; ++i)
> {
> g_seqlock.write_lock();
>
> int var_0 = g_var_0.load(std::memory_order_relaxed);
> int var_1 = g_var_1.load(std::memory_order_relaxed);
>
> rl::yield(1, $);
>
> g_var_1.store(var_1 + 1, std::memory_order_relaxed);
> g_var_0.store(var_0 + 1, std::memory_order_relaxed);
>
> g_seqlock.write_unlock();
> }
> }
It even works with the following for writers:
// writers
for (unsigned long i = 0; i < ITERS; ++i)
{
g_seqlock.write_lock();
int var_0 = g_var_0.load(std::memory_order_relaxed);
int var_1 = g_var_1.load(std::memory_order_relaxed);
g_seqlock.write_lock();
g_var_1.store(var_1 + 1, std::memory_order_relaxed);
g_var_0.store(var_0 + 1, std::memory_order_relaxed);
g_seqlock.write_unlock();
}
Still not sure about seq_cst. Humm.... Any constructive thoughts?
g_var_0.store(var_0 + 1, std::memory_order_relaxed);
g_seqlock.write_unlock();
}
Chris M. Thomasson
Mar 1, 2021, 10:10:25 PM3/1/21
to
On 3/1/2021 6:52 PM, Chris M. Thomasson wrote:
> Fwiw, here is a simple implementation of a seqlock under Relacy Race
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
>
>
> Here is the Relacy code:
> __________________________________
> // Chris M. Thomassons SeqLock Test
[...]
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
>
>
> Here is the Relacy code:
> __________________________________
> // Chris M. Thomassons SeqLock Test
> #define ITERS 3
> #define WRITERS 2
> #define READERS 5
> #define THREADS (WRITERS + READERS)
>
>
> struct proxy_test
> : rl::test_suite<proxy_test, THREADS>
> {
> ct_seqlock g_seqlock;
> std::atomic<int> g_var_0;
> std::atomic<int> g_var_1;
[...]
> #define WRITERS 2
> #define READERS 5
> #define THREADS (WRITERS + READERS)
>
>
> struct proxy_test
> : rl::test_suite<proxy_test, THREADS>
> {
> ct_seqlock g_seqlock;
> std::atomic<int> g_var_0;
> std::atomic<int> g_var_1;
One other note... I needed to use atomic's with relaxed membars for the
shared state. Afaict, a pure seqlock in C++11 is not standard using raw
variables. There might be a way around this. Need to think!
The reason why its not standard using raw variables is because they can
be read and written to concurrently. That is a no-no in std C++11.
Chris M. Thomasson
Mar 1, 2021, 11:01:42 PM3/1/21
to
On 3/1/2021 6:52 PM, Chris M. Thomasson wrote:
> Fwiw, here is a simple implementation of a seqlock under Relacy Race
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
[...]
> Detector. Now, this needs std::memory_order_seq_cst in order to get it
> to work, however, I am trying to find a way around that nasty membar.
> However, the ct_seqlock::read_enter/read_try_leave functions only does
> loads, but uses that damn seq_cst. The idea is to use this for a
> distributed poor mans RCU where there would be a seqlock per thread. It
> is crucial that a reader does not mutate state on a remote thread. So,
> loads are very important here.
I managed to get rid of a single seq_cst in the reader logic.
ct_seqlock::read_enter.
________________________
struct ct_seqlock
{
std::atomic<unsigned long> m_seq;
std::mutex m_lock;
ct_seqlock() : m_seq(0) {}
unsigned long read_enter()
{
unsigned long seq = 0;
for (;;)
{
if (! (seq & 1)) break;
rl::yield(1, $);
}
return seq;
}
bool read_try_leave(unsigned long cmp_seq)
{
unsigned long seq = m_seq.load(std::memory_order_seq_cst);
}
void write_lock()
{
m_lock.lock($);
m_seq.fetch_add(1, std::memory_order_seq_cst);
}
void write_unlock()
{
m_seq.fetch_add(1, std::memory_order_release);
m_lock.unlock($);
}
};
________________________
void write_lock()
{
m_lock.lock($);
m_seq.fetch_add(1, std::memory_order_seq_cst);
}
void write_unlock()
{
m_seq.fetch_add(1, std::memory_order_release);
m_lock.unlock($);
}
};
I have an idea to possibly get rid of the remaining seq_cst... It
involves embedding the sequence count in the mutex logic. I altered the
read_try_leave to also check to see if the seq is odd.
0 new messages