j_seigh

Sort of. Basically you have a situation where one thread needs to see another thread's memory accesses in sequential consistent order. If you can determine the other thread has synchronized its memory accesses at some point, then all its memory accesses before that are in observably sequentially consistent.

The thing is you don't know exactly when that synchronization took place so your code logic has to take that into account. In the case of hazard pointers, false positives are ok and false negatives, i.e. thread is using reference that was not detected, cannot occur.

There's 2 or 3 other tricks you can make hazard pointers wait-free. Getting rid of the conditional branching in the instruction pipeline gives you a considerable speed up.

For hazard pointers it was proposed here https://groups.google.com/g/comp.programming.threads/c/XU6Bt...

I did a POC afterwards. For linux it was a bit PITA since /proc text had to be parsed to track context switches w/ associated full MB. For Mac OS on the ppc also bit PITA since Apple tried to hide their unix api and some stuff involved calling the mach micro kernel.

An informal proof of why memory barrierless hazard pointers can't have false negatives. https://drive.google.com/file/d/1zDrXDdJHQEYILlwUSILPfSSiVzM...

Lighting rods also work by dissipating the local electric potential and reducing the likelihood of a lightning strike. That's why they are pointed, or fractal in the newer ones.

From https://en.wikipedia.org/wiki/Lightning_rod "and that a considerable electric current can be measured through the conductors as ionization occurs at the point when an electric field is present, such as happens when thunderclouds are overhead."

You can get a ground charge even when thunderclouds aren't present. It just has to be windy. I've always wondered if it was worth collecting this, say with a field with a grid of interconnected lightning rods in a windy location.

Couldn't traceroute run the entire TTL range in parallel, assuming the destination host was reachable and replies are disambiguable? I always hated waiting for traceroutes with lots of non responding routers.

My impression was LL/SC had forward progress issues due to the difficulties of preventing false sharing of the locked memory reservation region. Updates into that region would keep invalidating the lock.

I had a version of atomic* reference counting that used LL/SC on a ppc mac mini along side x86 versions using cmpxchg16b. Code used to be sourceforge before it went to the dark side.

An early posting of the idea before I got around to implementing it. https://groups.google.com/g/comp.programming.threads/c/HZqn5...

* Std::shared_ptr and Rust ARC aren't actually atomic. You have to own a reference to do a copy. The are what POSIX calls thread-safe. With atomic reference counting, if you copy a reference, you either get a valid reference or null. Like Java references.

It seems almost nobody can spell lose correctly anymore. I assume it's deliberate.

The comments about HFT needing tightly synchronized clocks got me thinking.

Back in the day, way back in the 80's, IBM replaced the VM with VMXA. VM could trap and emulate all the important instructions since they were privileged instructions except one, the STCK (store clock) instruction. So virtual machines couldn't set their virtual clocks so they were always in sync. VMXA used new hw features that let you set the virtual clock. You could specify an offset to the system clock. But some of IBM's biggest customers depended on all the virtual machines clocks always being in sync. So VMXA had to add an option to disallow setting the clock for specified virtual machines.

Except all of development knew how trivial it was to trap or modify the STCK's to produce a timestamp of you choosing. This was before it was common knowledge the client code should never be trusted. But nobody enlightened IBM corporate management. It was a serious career limiting move at IBM. It didn't matter if you were right. So I'm pretty sure some serious fortunes were made as a result.

So the question for HFT is; are they using and trusting client timestamps, or are the timestamps being generated on the market maker's servers? If the latter, how would the customer know?

Ok,so people use NTP to "synchronize" their clocks and then write applications that assume the clocks are in exact sync and can use timestamps for synchronization, even though NTP can see the clocks aren't always in sync. Do I have that right?

I did a lock-free MPMC ring buffer with 1 128 bit CAS and 1 64 bit CAS for enqueue and 1 64 bit CAS for dequeue. The payload is an unrestricted uintptr_t (64 bit) value so no way to avoid the 128 bit CAS in the enqueue.

Paywalled, but if you are familiar with the ABA problem in lock-free programming you can pretty much figure things out.

Coherent cache is transparent to the memory model. So if someone trying to explain memory model and ordering mentioned cache as affecting the memory model, it was pretty much a sign they didn't fully understand what they were talking about.

How is this different than something like https://www.espertech.com/

I'm assuming they're using an unbounded MPMC queue. With GC you can use a lock-free queue, otherwise you have to use mutexes, or reference counting which is nearly as bad.

I did do an actual lock-free MPMC ring buffer implementation as an exercise. I used that to make blocking bounded queues using various synchronization mechanisms, mutex/condvars and eventcounts among others. The eventcount version runs about 8x faster than the mutex version.

Only using way more bits. The original IBM lock-free stack algorithm assumed 32 bits was safe because it would take 100 years for a 32 bit counter to wrap at the time. Now it's less than 1 second.

There's some Bugblatter Beast logic here. They assume that if they can't imagine a counter/pointer value reuse ever reoccurring then malicious actors won't be able to imagine it either.

Here's an idea. How about fixing the buffer overflows and lack of data sanitation that allow code injection to occur in the first place.

I did find some links to some of my old posts on restartable sequences for user space rcu. Looked into using unix signal handling but it was pretty problematic to put it mildly. Definitely something you had to implement in the kernel.

https://groups.google.com/g/comp.os.linux.development.system... https://groups.google.com/g/comp.programming.threads/c/bq61m... https://groups.google.com/g/comp.programming.threads/c/muhN3...

It's worse than you think. I've closed PayPal accounts and opened new ones with a different email address and PayPal updates the merchants who've been spamming me with the new email address. There's no legitimate technical reason PayPal can't use a mail relay with transaction specific email addresses to control spam.

I don't think it has to be. Conceptually it's just a couple of queues.

There's a software equivalent of the Peter Principle where software or an API becomes increasingly complex to the point where no one understands it. They then attempt to fix that by adding more functionality (complexity).

https://groups.google.com/g/comp.programming.threads/c/XU6Bt... https://groups.google.com/g/linux.kernel/c/gk6AUkXR9As/m/-1W... Yes, I am aware of the asymmetric memory barriers trick and the atomic memory move trick also.

There's a couple of other ways to achieve wait freedom on hazard pointer loads (protect) but they haven't been published so they're kind of moot.

Bakery locks are good for spin locks. They're more cache friendly. Plus you can do reader/writer spin locks. They're going to be strictly FIFO though.

I guess you could tack on a futex wait for the spin wait in user space but it's going to be really inefficient. You are going to get a lot of spurious wake ups. Not one of the things futex's are designed for.

Lock-free with hazard pointers or RCU* is still kind of tricky. It's going to be data structure specific and you really have to know what you are doing.

Fun fact. You can make hazard pointers wait-free, actual wait free, not the dubious bounded retry loop hack.

* Doing copy on write with RCU is fairly straight forward but probably expensive if updates are frequent.

Here's an interesting scheme. Some credit/debit card merchant accounts can arrange to get updated card info if your card expires and/or gets replaced. So if the merchant is a bad actor and doesn't charge your card directly but just tracks your updated card info so it can be used fraudulently elsewhere, you, your bank, and the card company will never know they were the source. And the card is linked to your bank account, you can replace it ad infinitum and the bad actors will get the updated info for the new card every time. The only way to break out of this is to close your bank account and open a new one.

One of the few places I get a citation. It's where the idea of asymmetric memory barriers came from. RCU is used as the quiescent states are context switches which gives you a memory barrier on the thread doing the context switch. The Linux asymmetric memory barriers, membarrier(), uses IPI to effect that.

Anyway, getting rid of the memory barrier in fast paths, speeds things up considerably.

ChromeOS flex. It will run on hardware that even Linux complains about. I've even installed it on a Chromebook that stopped getting updates. Though, you have to replace the firmware, which entails some risk of bricking, so you can do a UEFI boot.

Also you can upgrade windows 10 to windows 11 even on hardware that Microsoft says is unsupported. Google for the workarounds. You only need to download the win11 iso from Microsoft and make a bootable USB stick using Rufus. Don't download anything from anywhere else. I wouldn't trust it.

Thread local vars would be used with lazy initialization. Clean up might be a little tricky depending on what implementation of thread local you use. Thread local support is not as great as it should be.

You just need to keep track of each thread's quiescent states however they are implemented.

A few ways to do wait-free hazard pointers, some portable, semi-portable, or not so much in this an subsequent blog posts. It's pretty high level, I'm assuming one knows how asymetric memory barriers and hazard pointers without the store/load memory barrier work.

Wait-free is interesting more from an academic point of view in that you can use hazard pointers to implement wait-free algorithms and still claim they are wait-free.

While one of them is 50% faster than lock-free hazard pointers, probably due to not having a conditional branch, the latter is pretty fast already.

You used quotes so I can't tell if you think it's a real problem or just a self inflicted one because the warning that finalizers aren't guaranteed to run was ignored.

If the finalizer was for an object that is just memory, it's not a problem. The GC has decided it doesn't need to recover the memory used by that object just yet. I've seen this with heaps defined to be large enough to handle a memory spike. When the spikes stop happening, a lot of stuff in the old gen pool just stays there. At one point I was looking at 50GB heap dumps looking for memory leaks.

It is a problem when the object has non memory resources like a socket descriptor. You can run out of descriptors. So not relying on GC and using try with resource is a good idea.

I've done implementations of most of these (qsbr, ebr, atomic reference counting, hazard pointers w/o the store/load memory barrier (you're welcome btw), etc...) and have a pretty good idea of how they work and how to use them. I think there should be more articles on how to use them properly. It's not obvious and can be a bit tricky if you don't have experience in this area.

A simple example would be how to implement a simple linked list that can be traversed safely under concurrent modifications.

Could have been worse https://www.nytimes.com/1994/08/05/nyregion/the-terror-of-th... It was really hot and traffic was backed up and at a standstill, so sitting in a car with windows rolled up for hours could not have been pleasant. I had spotted the backup beforehand and avoided it fortunately.

Performance from using atomics in reference counting is going to degrade quite a bit under heavy usage due to cache contention. If you are in that situation, you should be looking at something else like RCU or hazard Pointers.