Thread safety of AAs

[H. S. Teoh]

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