www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Thread safety of AAs

reply =?ISO-8859-1?Q?Alex_R=F8nne_Petersen?= <xtzgzorex gmail.com> writes:
Hi,

Suppose that I have an AA that I'm doing lookups on from one thread, and 
writing to in another. Is this safe at all? Naturally, I'm willing to 
accept the data races involved, but the question is whether the 
concurrent lookup + mutation is guaranteed to be safe.

-- 
- Alex
May 15 2012
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, May 16, 2012 at 04:35:17AM +0200, Alex Rønne Petersen wrote:

 Hi,
 
 Suppose that I have an AA that I'm doing lookups on from one thread,
 and writing to in another. Is this safe at all? Naturally, I'm
 willing to accept the data races involved, but the question is
 whether the concurrent lookup + mutation is guaranteed to be safe.


[...]

Safe as in, no memory corruption? Or safe as in, the data will be
consistent (barring any data races)?

Memory safety I'm not sure, I _think_ it might be safe, but I have my
doubts; data consistency, likely not, because you could potentially be
reading partially-copied data (say the mutator was assigning new data to
an existing key and the reader is reading that same data
simultaneously; you may be seeing a partial copy of the new data
intermixed with the old data).


T

-- 
Just because you survived after you did it, doesn't mean it wasn't stupid!
May 15 2012
parent reply =?ISO-8859-1?Q?Alex_R=F8nne_Petersen?= <xtzgzorex gmail.com> writes:
On 16-05-2012 05:03, H. S. Teoh wrote:

 On Wed, May 16, 2012 at 04:35:17AM +0200, Alex Rønne Petersen wrote:

 Hi,

 Suppose that I have an AA that I'm doing lookups on from one thread,
 and writing to in another. Is this safe at all? Naturally, I'm
 willing to accept the data races involved, but the question is
 whether the concurrent lookup + mutation is guaranteed to be safe.


 [...]

 Safe as in, no memory corruption? Or safe as in, the data will be
 consistent (barring any data races)?


As in no memory corruption.


 Memory safety I'm not sure, I _think_ it might be safe, but I have my
 doubts; data consistency, likely not, because you could potentially be
 reading partially-copied data (say the mutator was assigning new data to
 an existing key and the reader is reading that same data
 simultaneously; you may be seeing a partial copy of the new data
 intermixed with the old data).


Assuming the AA implementation only does aligned reads/writes, there 
should be no problem with word tearing on any modern architecture. But I 
don't know if it does that...


 T


-- 
- Alex
May 15 2012
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, May 16, 2012 at 05:06:54AM +0200, Alex Rønne Petersen wrote:

 On 16-05-2012 05:03, H. S. Teoh wrote:

On Wed, May 16, 2012 at 04:35:17AM +0200, Alex Rønne Petersen wrote:

Hi,

Suppose that I have an AA that I'm doing lookups on from one thread,
and writing to in another. Is this safe at all? Naturally, I'm
willing to accept the data races involved, but the question is
whether the concurrent lookup + mutation is guaranteed to be safe.


[...]

Safe as in, no memory corruption? Or safe as in, the data will be
consistent (barring any data races)?


 
 As in no memory corruption.


[...]

Hmm. Just noticed that the current aaA.d, in _aaDelX, after a slot is
removed from the linked list gc_free is called on the slot. IIRC, if the
mutator calls gc_free while the reader holds a reference to the slot,
you may be accessing invalid memory. (E.g., reader looks up key being
deleted, gets the pointer to that slot before the mutator does, then the
CPU context-switches to the mutator, which calls gc_free, which cleans
up that slot, now the reader has an invalid pointer.)

I don't know if this will lead to memory corruption, but it sure looks
dangerous to me.



Memory safety I'm not sure, I _think_ it might be safe, but I have my
doubts; data consistency, likely not, because you could potentially be
reading partially-copied data (say the mutator was assigning new data to
an existing key and the reader is reading that same data
simultaneously; you may be seeing a partial copy of the new data
intermixed with the old data).


 
 Assuming the AA implementation only does aligned reads/writes, there
 should be no problem with word tearing on any modern architecture.
 But I don't know if it does that...


[...]

If your data is larger than a word, you'd still have a problem, though.


T

-- 
Nothing in the world is more distasteful to a man than to take the path that
leads to himself. -- Herman Hesse
May 15 2012
parent =?ISO-8859-1?Q?Alex_R=F8nne_Petersen?= <xtzgzorex gmail.com> writes:
On 16-05-2012 05:21, H. S. Teoh wrote:

 On Wed, May 16, 2012 at 05:06:54AM +0200, Alex Rønne Petersen wrote:

 On 16-05-2012 05:03, H. S. Teoh wrote:

 On Wed, May 16, 2012 at 04:35:17AM +0200, Alex Rønne Petersen wrote:

 Hi,

 Suppose that I have an AA that I'm doing lookups on from one thread,
 and writing to in another. Is this safe at all? Naturally, I'm
 willing to accept the data races involved, but the question is
 whether the concurrent lookup + mutation is guaranteed to be safe.


 [...]

 Safe as in, no memory corruption? Or safe as in, the data will be
 consistent (barring any data races)?


 As in no memory corruption.


 [...]

 Hmm. Just noticed that the current aaA.d, in _aaDelX, after a slot is
 removed from the linked list gc_free is called on the slot. IIRC, if the
 mutator calls gc_free while the reader holds a reference to the slot,
 you may be accessing invalid memory. (E.g., reader looks up key being
 deleted, gets the pointer to that slot before the mutator does, then the
 CPU context-switches to the mutator, which calls gc_free, which cleans
 up that slot, now the reader has an invalid pointer.)

 I don't know if this will lead to memory corruption, but it sure looks
 dangerous to me.


See, this is why explicit deallocation of GC memory is bad. ;)

I guess I might just resort to using an R/W mutex.


 Memory safety I'm not sure, I _think_ it might be safe, but I have my
 doubts; data consistency, likely not, because you could potentially be
 reading partially-copied data (say the mutator was assigning new data to
 an existing key and the reader is reading that same data
 simultaneously; you may be seeing a partial copy of the new data
 intermixed with the old data).


 Assuming the AA implementation only does aligned reads/writes, there
 should be no problem with word tearing on any modern architecture.
 But I don't know if it does that...


 [...]

 If your data is larger than a word, you'd still have a problem, though.


 T


It's OK in my case, since I'm just storing a pointer.

-- 
- Alex
May 15 2012
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 15 May 2012 22:35:17 -0400, Alex R=C3=B8nne Petersen  =

<xtzgzorex gmail.com> wrote:


 Hi,

 Suppose that I have an AA that I'm doing lookups on from one thread, a=


nd  =


 writing to in another. Is this safe at all?


No.

AA's are not a default-shared type.

If you need a counter-case, just consider that your adding thread does a=
  =

rehash when you are traversing in your reading thread.

-Steve
May 17 2012