Flash Gordon said:
spinoza1111 said:
Chris M. Thomasson wrote:
[...]
However, in a multithread environment where strings are passed by
reference (that is, their address is passed by value), whenever you
evaluate snprintf to do your own sprintf, the target strings could
change unless you call them inside a lock. This lock will pin these
strings down for an unpredictable length of time, and this may create
problems in multithread applications that depend on locks using a
constant time.
FWIW, there ways to use shared strings without any locking whatsoever.
One simple example
is a simple COW-based solution to the classic reader/writer problem.
That is a reader thread can take a reference to a shared string
without worry of interference form writers such that they can read the
string without synchronization. I can do this with 100% lock-based or
lock-free scheme, simple pseudo-code for lock-based:
Ummm, pseudo-code for lock-free of course!
Yikes!
Ah, but it doesn't deal with the badly behaved thread that writes to a
string after it has "passed the reference" ;-)
I agree it's a good way of solving the higher level problem, and closer
to what I've done in assembler.
It all boils down to one way or another having to assure that one thread
won't write to the string while the other is reading from it, and it is
the same problem whatever language you are using. I didn't expect the
person I was originally replying to would understand that.
As most of you should have known, but either didn't, or couldn't
express
Chris's post was clear and showed excellent knowledge of the issues and a
lot more knowledge than me in how to deal with it.
[...]
I need to show how the memory barriers could look, and then show some
pseudo-code on how to use it, I also made a typo in the `struct string'
data-structure. I made `string::buffer' constant, it should be mutable by
writer threads when it's quiescent, more on that later:
________________________________________________________________________
struct string {
/*
`buffer' is immutable when it's in a non-quiescent state,
and mutable when it is in a quiescent state.
*/
char* buffer;
atomic_word32 inner;
size_t size;
};
struct string_ref {
struct string* string;
atomic_word32 outer;
};
#define STRING_REF_INIT { NULL }
typedef char static_assert
[
sizeof(struct string_ref) == 64 / CHAR_BIT ? 1 : -1
];
struct string*
string_create(size_t size)
{
struct string* const self = malloc(sizeof(*self) + size + 1);
if (self) {
char* buffer = (char*)(self + 1);
buffer[0] = '\0';
self->inner = 0;
self->size = size;
self->buffer = buffer;
}
return self;
}
void
string_destroy(struct string* const self)
{
free(self);
}
void
string_system_destroy(struct string* const self)
{
MEMBAR_ACQUIRE();
string_destroy(self);
}
struct string*
string_acquire(struct string_ref* const self)
{
struct string_ref cmp, xchg;
cmp = *self;
do
{
xchg.string = cmp.string;
xchg.outer = cmp.outer + 1;
} while (! ATOMIC_DWCAS_ACQUIRE(self, &cmp, &xchg));
return cmp.string;
}
void
string_release(struct string* const self)
{
if (ATOMIC_FAA_RELEASE(&self->inner, -1) == 1)
{
string_system_destroy(self);
}
}
void
string_relpace(struct string_ref* const self,
struct string* new_string)
{
struct string_ref cmp, xchg;
xchg.string = new_string;
xchg.outer = 0;
cmp = *self;
while (! ATOMIC_DWCAS_ACQUIRE(self, &cmp, &xchg));
if (cmp.string)
{
if (ATOMIC_FAA_RELEASE(&cmp.string->inner, cmp.outer) == -cmp.outer)
{
string_system_destroy(cmp.string);
}
}
}
________________________________________________________________________
Here is a simple usage example:
________________________________________________________________________
static struct string_ref g_dynamic_html = STRING_REF_INIT;
/* Writer threads */
void
dynamic_html_update(struct string* new_html)
{
/*
Atomically transfer the local `new_html' string to the
global `g_dynamic_html' string.
*/
string_replace(&g_dynamic_html, new_html);
}
/* Reader threads */
int
dynamic_html_read_and_process(void)
{
/*
Atomically acquire a reference to the global `g_dynamic_html'
string.
*/
struct string* html = string_acquire(&g_dynamic_html);
if (html)
{
/*
`html' is in a non-quiescent state, therefore it's
immutable. Parse it, process the contained data,
whatever.
*/
puts(html->buffer);
string_release(html);
}
}
void foo()
{
struct string* html = string_create(html_get_size(...));
if (html)
{
/*
`html' is in a quiescent state, therefore it's mutable.
*/
html_build(html->buffer);
dynamic_html_update(html);
/*
`html' is in an indeterminate state wrt this thread.
*/
}
}
________________________________________________________________________
That should implement dynamic html which can be concurrently read from and
written to by multiple threads. After a reader thread acquires a reference,
it can read/parse the immutable string buffer directly. A writer simply
atomically swaps a new string in and merges the old strings differential
reference count (e.g., `string::inner' and `string_ref:
uter').
BTW, a quiescent state is defined as when the data-structure cannot, or will
not, be reached by any threads except the for the one that access to it. In
`foo()' the `html' string is only reachable by the currently executing
thread, therefore it's quiescent.
Non-quiescent is when a reader thread has a reference to the data-structure.
As soon as `foo()' passes the `html' string to `dynamic_html_update()' it
gets rendered into a non-quiescent state because it's now visible to, any
may have already been referenced by, reader threads.
