andikleen2

gcc unfortunately cannot do this (and also not the related optimization of using word/byte offsets for the jump table, which LLVM can do) because it only has approximate estimation of code size. If it got the code size wrong it would be a mis-compilation. This is related to it not using an integrated assembler.

I might be wrong, but I always assumed that Gimple Lint / PC Lint has its own C++23 frontend too. It looks very different from what other compilers have.

It's usually custom scripts, I'm not aware of a standard tool. You fill up the file system and then do lots of operations that cause fragmentation.

Actually here is a recent paper discussing this (although the basic concept is much older):

https://arxiv.org/abs/2401.08858

Such tools really exist and they're used for testing file systems, so that you have a more realistic "aged" layout on a freshly created test file systems.

We also have memory fragmenters to do the same for memory for the same reasons.

Dave Jones used to have a series of "Why user space sucks" Linux kernel conference talks with many such examples, usually with dumb and redundant system calls.

However as someone who looks a lot at instruction traces I could probably write on e on why Linux kernel code sucks too. One of my current pet peeves is the way Linux walks bitmasks of CPU bits, which is a reasonably common operation. Due to a chain of unfortunate changes and decisions it currently needs 16+ instructions to find the next bit for something which the x86 instruction set has a single instruction. Of course that is so big that it is even outlined, adding even more overhead.

Early x86-64 Linux had a similar problem. The x86-64 ABI uses registers for the first 6 arguments. To support variable number of arguments (like printf) requires passing the number of arguments in an extra register (RAX), so that the callee can save the registers to memory for va_arg() and friends. Doing this for every call is too expensive, so it's only done when the prototype is marked as stdarg.

Now the initial gcc implemented this saving to memory with a kind of duffs device, with a computed jump into a block of register saving instructions to only save the needed registers. There was no boundary check, so if the no argument register (RAX) was not initialized correctly it would jump randomly based on the junk, and cause very confusing bug reports.

This bit quite some software which didn't use correct prototypes, calling stdarg functions without indicating that in the prototype. On 32bit code which didn't use register arguments this wasn't a problem.

Later compiler versions switched to saving all registers unconditionally.

If you read Anderson "A history of Aerodynamics" it disagrees on this point. It states that the Wright's didn't have a good way to calculate drag, and they didn't understand many of the side effects from real wings (like flow separation) which caused wrong measurements initially. Later on they apparently came back to something that was closer to Lilienthal's numbers, even though the problem simply wasn't fully understood at the time.

This paper has a similar conclusion: https://corescholar.libraries.wright.edu/cgi/viewcontent.cgi...

"When the Wright brothers compared their results with those of Lilienthal, they found some disagreement, but not as much as they expected. As Wilbur states in his diary for October 16, 1901: "It would appear that Lilienthal is very much nearer the truth then we have heretofore been disposed to think." [Wolko, 21]. 17 The formulas were still not producing the lift and drag that were actually being produced. The only other possible source of error in these equations was the Smeaton coefficient of air pressure."

> 4. First design that used a wind tunnel to get an efficient wing shape

The Wrights based their wing on Lilienthal's who used a variant of a wind tunnel (as well as actual gliders) for optimizations.

You could also argue he ran a coherent research program too, just it was sadly stopped by his fatal flying accident.

https://www.lilienthal-museum.de/olma/ewright.htm

This technique works with any instruction that clobbers a register, not just with CPUID. In the worst case you could just single step the other CPUs until you hit an instruction that overwrites a register too. These are common.

In my case (for a custom hypervisor for a sadly cancelled project) it wasn't a problem because the hypervisor quit itself in early guest boot, which is single CPU only.

Having spent a lot of time porting 32bit system code to 64bit, I developed a dislike for these explicit types. It's a slippery slope to hard code your bitness with people making assumptions where size_t or pointers fit.

Now maybe if you're already 64bit that's fine (it's unlikely that we'll ever need 128bit, and code is unlikely to grow down), but for anything starting smaller it's a pain.

Back when Usenet was still functional, de.sci.history (German history group) had some dedicated proponents of a German conspiracy theory that the early middle ages (Carolingian dynasty in middle Europe) didn't exist. Basically their argument was that there are gaps in the respective documents and also a lot of forgeries, and the best explanation was that a few hundred years were missing. This of course ignored all the carbon dating, and as well as the parallel chronology of other cultures (including early Islam, which fell exactly into the "missing" period)

https://en.wikipedia.org/wiki/Phantom_time_hypothesis

At the beginning I found it amusing, but after some time it got just tiring.

Even if they don't livelock retries can be significantly slower than a direct atomic operation under contention. Compare https://www.cs.tau.ac.il/~mad/publications/ppopp2013-x86queu...

Programming under high cache line contention is like message passing on a really busy network with many nodes, and anything that cuts down round trips can make a big difference in scalability. Most people who do network programming know these lessons by heart, but it's still poorly understood by people doing shared memory.

So maybe it's simpler, but likely it's slower too.

>Put simply, TSX is not mainstream, and isn't on track to be mainstream anytime soon.

Being in the vast majority of servers deployed in the last decade (Intel+POWER) is not mainstream?

Yes it totally is.

How much confidence do you have in your lockless code?

>essentially no cost unless the lock is contested.

Atomics are not free. And fetching a cache line can be very expensive, even without contention.

However lock less algorithms are often worse because they have even more atomics and even more cache line transfers. And they're really hard to get right. (iirc there was a statistic somewhere about the average number of corrections in lock less papers -- it wasn't pretty)

Back to the non contended locks. Usually the way to get non contended locks is to push down the locks to smaller and smaller pieces of data. But imagine what happens when you have some contention (e.g. due to a freak hash collisions). Instead of paying the cache transfer cost once you'll pay it many times, and that can really ruin your day (speed of light is very limiting at nano second scales)

I wrote more about this here [1]

I am somewhat biased but I would recommend that every time you consider something lockless, consider using lock elision/HTM instead (see [2] and [3]). It often has most of the advantages with few of the down sides (but admittedly also some of its own quirks)

[1] http://halobates.de/applicative-mental-models.pdf [2] http://queue.acm.org/detail.cfm?id=2579227 [3] http://www.intel.com/software/tsx

In the early tens we ran an engineering project to improve critical sections in applications using transactional memory. We had a PhD level intern applying our techniques to various open source projects. One target was MongoDB. After a few days of investigation of the Mongo source code, he had to give up because he couldn't even find the critical sections in the source. They had locking, but it was extremely convoluted.

So yes I would agree with that. Never use MongoDB.

Seems trivial to exploit the kernel module:

  struct network_activity * activity = NLMSG_DATA(nlh);

<untrusted data from the netlink socket> append_rule(activity->process_path, (activity->allowed == 1)); ...

append_rule: // Don't do anything if the process_path length is > PATH_LENGTH if (strlen(process_path) > PATH_LENGTH) return;

But nobody enforces the process_path has a terminating 0 byte, so likely it can be abused for all kinds of attacks on the kernel. Better don't run it anywhere you care about security.

I found this from about 2 minutes code reading, so likely there wasn't any code audit done ever.

Small mistake in the article. System V code was never released publicly by SCO, just some earlier variants not too far removed from V7.

They make great code reading if anyone is interested. The early Unix variants were quite simple and concise, nothing like the complexity of a modern variant.

https://github.com/dspinellis/unix-history-repo/tree/Researc...

For example early process swapping was really simple:

https://github.com/dspinellis/unix-history-repo/blob/Researc...

or scheduling was quite simple too:

https://github.com/dspinellis/unix-history-repo/blob/Researc...

or that's most of a file system:

https://github.com/dspinellis/unix-history-repo/blob/Researc...

scanner and lexer of the earlier (pre pcc) c compiler:

https://github.com/dspinellis/unix-history-repo/blob/Researc...

and that is ls:

https://github.com/dspinellis/unix-history-repo/blob/Researc...

ed, the standard editor:

https://github.com/dspinellis/unix-history-repo/blob/Researc...

You have to be a bit careful with the CLFLUSH method. I tried to use it in a widely used program years ago because Intel recommended it, but we found that it just hangs the CPU on some older VIA/Centaur CPUs. Presumably that's fixed these days, but the old CPUs are likely still around.

Yes with a read primitive it could be done in theory. It will be just quite awkward to use however as every caller has to do all that: define a lock, pass it always in, make sure the check for "lock is free" is correct etc.

Your unit tests don't seem to do it right.

It would probably be easier to hide the lock in your library, and enforce all other access to follow the right protocol using some ADTs. But then you just have a simple hardware TM accelerated STM.

FWIW the sweet spots for nice to use TM APIs are currently either lock elision, or compiler assisted TM (like __transaction* in gcc), or higher level libraries.

This would be only useful for "good" page faults that fault something in, but not for "bad" ones (like NULL pointer). If a bad page fault was executed it would allow transactions to crash the program, which wouldn't be very atomic.

The transaction mechanism doesn't know in advance if it's a good or a bad page fault.

You would need to tell the operating system kernel that the page fault happened in a transaction, and let it ignore it if it was a bad page fault. That would be much more complicated than current TSX.

Also there are other cases were retries will not succeed, page fault was just an example. Another common case is the dynamic linker when a library function is first executed.

Practically all valid fallback schemes require putting the lock (or something else like a sequence counter for a STM) into the read set of the transaction to properly synchronize between transactions and non transactions. Since you hide the transaction in your library it's not possible to do that with your current API. It would be very hard to construct a fallback path that is not racy.

(See Anti pattern #4 in the link above)

A global lock is usually the simplest fall back path, and the performance can be good enough because it's just a slow path. Of course it's always possible to do something more complex.

He's assuming that retrying forever is a valid retry strategy, which it is not. For example if a page fault was needed to satisfy one of the memory access it would never finish.

See https://software.intel.com/en-us/articles/tsx-anti-patterns-... and https://software.intel.com/en-us/blogs/2013/06/23/tsx-fallba... for more details/

To make his code work he likely would need a global fallback lock (or a real STM) and guarantee that every change of the touched memory uses those too (which would be hard)

So I'm afraid the library is fairly broken.