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

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!

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

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

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

On Tue, 15 May 2012 22:35:17 -0400, Alex Rønne Petersen <xtzgzorex@gmail.com> 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?

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