iframe-proxy

slozier · 2025-02-07T00:59:55Z

Cherry-picked my PR for 3.6. It's a nice feature to have so why not include it in 3.4...

BCSharp · 2025-02-07T06:03:41Z

slozier · 2025-02-07T14:10:40Z

Oh, it is not simple code. Looking at the diffs on GitHub I can't see how the thread safety is ensured without locking. I'll have to check it out locally.

I don't think I altered the locking strategy that was currently in place, however now that I look at it I think switching _buckets to a List<Bucket> might have broken it...

Anyway, I need to review this myself since I wrote it two years ago and am a bit foggy on the details. But I would still appreciate a review if you feel like providing one.

Side note, net6.0.CPython.test_keyword has been failing intermittently on macOS during Azure CI. I was going to blame a concurrency issue, but it's already annotated with NotParallelSafe=true. I haven't been able to reproduce it (and it's unclear why it would only occur on the mac).

BCSharp

Well, unfortunately, I think the way it currently is, it is not thread-safe. The main challenge is because of the change from one structure containing data (Bucket[] _buckets) to two (int[] _indices and List<Bucket> _buckets). What was before an atomic operation on _buckets, now is sometimes split into two that are not atomic.

For instance, the call TryGetValue(_buckets, key, out value) would atomically grab field _buckets, and as long as operations that may disrupt readers were done on a new array, which then would be atomically assigned to the field, things were fine.

Now, the call TryGetValue(_indices, _buckets, key, out value) grabs two fields: _indices and _buckets in indeterminate order, that may not be in sync witch each other.

There are various ways of handling it; in my edit suggestions I propose the way based on the following rules:

There is never a situation that _indices point to some bucket that does not exist. The opposite is OK - there may be a bucket that is not indexed yet.
1. If something is added, it is first added to _buckets, and only after to _indices.
2. If something is removed, it is first removed from _indices, only then from _buckets, and not really removed but marked as DUMMY/Bucket.Removed.
3. List _buckets never gets shorter (except for Clear() - special case).
If both _indices and _buckets have to be replaced by new objects (e.g. to shorten them like in Clear()), it is done in a predictable order to ensure Rule 1 is always satisfied.
1. If they are reset, _indices are reset first, then _buckets.
2. If they are read, _buckets are read first, then _indices.

Rule 2 is to ensure that we never get _indices that refer to _buckets that are not (or no longer) around. In other words, if we get a torn read of _indices and _buckets for the lookup, it is always new _indices and old _buckets.

To ensure proper ordering, Thread.MemoryBarrier() was needed in more places than before.

In my code suggestions I tried to demonstrate what I mean by all this. I hope I got all the relevant places, but don't take my word for it.

BCSharp · 2025-02-08T00:54:27Z

+            => TryGetValue(_indices, _buckets, key, out value);

        /// <summary>
        /// Static helper to try and get the value from the dictionary.


Not static anymore.

BCSharp · 2025-02-08T00:54:34Z

        /// Used so the value lookup can run against a buckets while a writer
        /// replaces the buckets.


This description seems obsolete.

BCSharp · 2025-02-08T04:46:40Z

                // we need to clone the buckets so any lock-free readers will only see
                // the old buckets which are homogeneous
-                _buckets = (Bucket[])_buckets.Clone();
+                _indices = (int[])_indices.Clone();


Suggested change

_indices = (int[])_indices.Clone();

_buckets = new List<Bucket>(_buckets);

BCSharp · 2025-02-08T04:47:26Z

+                _indices = new int[(int)(size / Load) + 1];
+                _indices.AsSpan().Fill(FREE);


Suggested change

_indices = new int[(int)(size / Load) + 1];

_indices.AsSpan().Fill(FREE);

var newIndices = new int[(int)(size / Load) + 1];

newIndices.AsSpan().Fill(FREE);

_indices = newIndices;

BCSharp · 2025-02-08T04:49:49Z

+                indices[pair.Key] = buckets.Count;
+                buckets.Add(bucket);
+                _count++;


Suggested change

indices[pair.Key] = buckets.Count;

buckets.Add(bucket);

_count++;

_count++;

buckets.Add(bucket);

Thread.MemoryBarrier();

indices[pair.Key] = buckets.Count;

BCSharp · 2025-02-08T04:50:54Z

+            _indices[pair.Key] = DUMMY;
+            _buckets[pair.Value] = Bucket.Removed;
+            Thread.MemoryBarrier();


Suggested change

_indices[pair.Key] = DUMMY;

_buckets[pair.Value] = Bucket.Removed;

Thread.MemoryBarrier();

_indices[pair.Key] = DUMMY;

Thread.MemoryBarrier();

_buckets[pair.Value] = Bucket.Removed;

BCSharp · 2025-02-08T04:51:47Z

+        public override bool TryGetValue(object key, out object value)
+            => TryGetValue(_indices, _buckets, key, out value);


Suggested change

public override bool TryGetValue(object key, out object value)

=> TryGetValue(_indices, _buckets, key, out value);

public override bool TryGetValue(object key, out object value) {

var buckets = _buckets;

Thread.MemoryBarrier();

var indices = _indices;

return TryGetValue(indices, buckets, key, out value);

}

BCSharp · 2025-02-08T04:53:26Z

+                    _indices = new int[8];
+                    _indices.AsSpan().Fill(FREE);
+                    _buckets.Clear();


_buckets.Clear() is not enough. A new list object is needed not to mess up readers in progress.

Suggested change

_indices = new int[8];

_indices.AsSpan().Fill(FREE);

_buckets.Clear();

var newIndices = new int[InitialBucketSize];

newIndices.AsSpan().Fill(FREE);

_indices = newIndices;

Thread.MemoryBarrier();

_buckets = new List<Bucket>();

BCSharp · 2025-02-08T05:44:31Z

slozier added 4 commits February 6, 2025 19:52

Order-preserving CommonDictionaryStorage

248eaea

Get some tests passing

b5766a3

Add back Serialization

3d8f9c2

Simplify

b71be0e

slozier marked this pull request as ready for review February 7, 2025 01:34

BCSharp self-requested a review February 8, 2025 02:21

BCSharp requested changes Feb 8, 2025

View reviewed changes

slozier marked this pull request as draft June 6, 2026 12:58

BCSharp mentioned this pull request Jun 11, 2026

Implement async functions and generators (.NET) #2046

Merged

BCSharp added this to the 3.6-alpha milestone Jun 18, 2026

		/// Used so the value lookup can run against a buckets while a writer
		/// replaces the buckets.

	_indices = (int[])_indices.Clone();
	_buckets = new List<Bucket>(_buckets);

		_indices = new int[(int)(size / Load) + 1];
		_indices.AsSpan().Fill(FREE);

-                _indices = new int[(int)(size / Load) + 1];
-                _indices.AsSpan().Fill(FREE);
+                var newIndices = new int[(int)(size / Load) + 1];
+                newIndices.AsSpan().Fill(FREE);
+                _indices = newIndices;

		public override bool TryGetValue(object key, out object value)
		=> TryGetValue(_indices, _buckets, key, out value);

-        public override bool TryGetValue(object key, out object value)
-            => TryGetValue(_indices, _buckets, key, out value);
+        public override bool TryGetValue(object key, out object value) {
+            var buckets = _buckets;
+            Thread.MemoryBarrier();
+            var indices = _indices;
+            return TryGetValue(indices, buckets, key, out value);
+        }

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

Conversation

slozier commented Feb 7, 2025

Uh oh!

BCSharp commented Feb 7, 2025

Uh oh!

slozier commented Feb 7, 2025

Uh oh!

BCSharp left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

BCSharp commented Feb 8, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants