Race condition

[G-M-twostay]

Hi, I saw that the sorted linked list is based on Harris's linked list, but according to my understanding, it's not correctly written. Harris's linked list is based on 2 assumptions: 1. Atomic operation on node.next can see changes to node.delete. 2. node.next on a deleted node is still valid and can be used to track to the original next. In this implementation, I see that: 1. node.delete and node.next can't be dealt with in a single atomic operation. This is problematic, consider: node.delete can change immediately before(after the if checks) or during a CAS operation on node.next, and during this process, a successful physical deletion can happen before the CAS operation completes/starts, therefore, the new node is linked onto a deleted node. This is my understanding, correct me if I'm wrong.

I encountered the above problem in my initial attempts to implement such a hashmap using Harris's linked list.

With this in mind, I designed a few cases that can reflect the above problem. However, I'm not sure whether the failures in the below cases are solely caused by the above reason or is/are caused by other problems. It appears to me that at least on my end Case1 has some other problem because a given key is guaranteed to fail. Anyway, let's see these cases. Case 1:

func BenchmarkHaxMap_Case1(b *testing.B) {
	b.StopTimer()
	wg := sync.WaitGroup{}
	for i := 0; i < b.N; i++ {
		M := haxmap.New[int, int]()
		b.StartTimer()
		for k := 0; k < iter0; k++ {
			wg.Add(1)
			go func(l, h int) {
				for j := l; j < h; j++ {
					M.Set(j, j)
				}
				for j := l; j < h; j++ {
					_, a := M.Get(j)
					if !a {
						b.Error("key doesn't exist", j)
					}
				}
				for j := l; j < h; j++ {
					x, _ := M.Get(j)
					if x != j {
						b.Error("incorrect value", j, x)
					}
				}
				wg.Done()
			}(k*elementNum0, (k+1)*elementNum0)
		}
		wg.Wait()
		b.StopTimer()
	}
}

Case 2:

func BenchmarkHaxMap_Case3(b *testing.B) {
	b.StopTimer()
	wg := &sync.WaitGroup{}
	for a := 0; a < b.N; a++ {
		M := haxmap.New[int, int]()
		b.StartTimer()
		for j := 0; j < iter0; j++ {
			wg.Add(1)
			go func(l, h int) {
				defer wg.Done()
				for i := l; i < h; i++ {
					M.Set(i, i)
				}

				for i := l; i < h; i++ {
					_, x := M.Get(i)
					if !x {
						b.Errorf("not put: %v\n", i)
					}
				}
				for i := l; i < h; i++ {
					M.Del(i)

				}
				for i := l; i < h; i++ {
					_, x := M.Get(i)
					if x {
						b.Errorf("not removed: %v\n", i)
					}
				}

			}(j*elementNum0, (j+1)*elementNum0)
		}
		wg.Wait()
		b.StopTimer()
	}

}

const (
	iter0       = 1 << 3
	elementNum0 = 1 << 10
)

If you increase the data size, this problem becomes more severe. You can delete all the benchmark and timing things.

Modifying these tests to sync.Map or an ordinary map with Mutex will show that no failures happen. In addition, cornelk's hashmap also fails at these tests.