davidtgoldblatt

It kinda depends; you only do the membarrier when you're about to sleep anyways, and the non-expedited membarrier() call is just a synchronize_rcu(), so it's not that drastically more expensive than a futex wait.

You don't necessarily want a biased lock for all this kind of stuff, because "sparsely contended" doesn't necessarily imply thread-associated. E.g. one place I was looking at this for was locks for pages of virtual memory in a heap; no thread "owns" any given heap page, but it was very uncommon to get unlucky and have two threads touching adjacent pages at the exact same time. These kind of "sloppy mutexes" get half the fast-path speedup of biased locks but without the heavily asymmetric performance costs. (At least, that was the theory; like I said it didn't really pan out to be that useful in practice).

There's two I've tried to do this:

- On the wait side, do the CAS to set the "waiter present" bit. Down unlock, do a (relaxed) read of the lock word, and if "waiter present" isn't set, just do a release store to unlock (and go down some slow CAS-y wake path if a waiter is present). On the wait side, never do an un-timed futex wait; just do a series of timed waits, with increasing wait times (so that you still eventually fix things if you hit the unlucky race between the previous holder's check+store sequence). (You can also do some tricks with counters to let waiters do an unconditional sleep once they get their wait acknowledged).

- Split out the "waiter present" bit into its own byte, do a store-load sequence (with just a compiler reordering fence) to check for waiters, and have waiters either do a membarrier() syscall or wait "long enough" that they're sure they've gotten the same effect. (This gets tricky w.r.t. mutex lifetime though; you either need out of band lifetime knowledge or to use RCU or whatever and indirect through pointers).

Practically, neither was ever "better enough" for anything but microbenchmarks to be worth the complexity.

> There's clearly an opportunity for a much longer talk, this teases that Paul (McKenney, of Linux fame) will have a very different take and we don't hear what it is, maybe that was presented at another session of this conference.

Paul's talk is here: https://www.youtube.com/watch?v=iJP6DWVrLjM

> Maybe there is a way to paper over this in the glibc implementation of free_sized (rather than calling free unconditionally), and still do something useful for the glibc allocator. I don't know.

We emailed about this a little contemporaneously (thread "Sized deallocation for C", from February), and I think we came to the conclusion that glibc can make interposition work seamlessly even for interposed allocators lacking free_sized, by checking (in glibc's free_sized) if the glibc malloc/calloc/realloc has been called, and redirecting to free if it hasn't. (The poorly-named "Application Life-Cycle" section of the paper).

My usages are similar to yours, but new C standards still benefit me because I can opportunistically detect and make use of new features in a configure script.

To use my baby as an example: free_sized(void *ptr, size_t alloc_size) is new in C23. I can detect whether or not it's available and use it if so. If it's not available, I can just fall back to free() and get the same semantics, at some performance or safety cost.

Of particular interest is section 20.18 -- "Mirroring memory operands"; extending (something like) register renaming to memory.

> Maybe there's some reason this doesn't work, or maybe the performance improvements aren't worth the effort?

I work on an allocator, and I've lobbied (Linux) kernel people for this over the years. I think everyone mostly agrees it'd be useful (and, the TLB shootdown cost is indeed often nontrivial), but the current architecture of the various subsystem's you'd need to touch makes it hard to do.

As allocators move more and more to a hugepages-first world, I think we'll see fewer and fewer benefits from faster unmappings (instead, we'll just spend more effort making sure we fill in the holes in existing in-use ranges).

I can't imagine how pissed off I'd be if I survived a nuclear winter and traveled hundreds of miles to read the prophesied guidestones that could save us all, only to find out that they had several weird eugenicist rules but zero information about like, water purification or animal husbandry.

Example usage on some code with interesting pipelining + resource contention properties: https://godbolt.org/z/11oyav

(The code is from the stream vbyte repo; see https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-... ).

Edit: Example interesting fact: the first iteration takes 35 cycles before it finishes; but the reciprocal throughput of the loop (assuming it executes a few times) is 5.3 cycles.

Depending on what exactly you mean by "hand it a block of memory to manage", you can do this with jemalloc's extent hook functionality. Though that's meant for "I have some long-lived data structures, I want all their memory stored on hugepages" more than "I have this small-ish data structure, I want to batch its allocations together".

Oh yes; while certainly mismatched new[]/delete has been a source of problems since forever, what I mean specifically is the new types of exploits possible with the "operator delete(void* ptr, size_t sz)" overload (and its array cousin).

Before C++14, using delete (rather than delete[]) to deallocate an array of ints (or other trivially destructible data types) would be safe in practice, even though it was disallowed. In a world with sized deallocation functions, it's exploitable.

Another fun attack vector that I don't think has been well explored yet involves the use of C++ sized deallocation functions. If a base class is missing a virtual destructor, or if an array allocated with new[] is deallocated with delete (instead of delete[]), then the allocation can be freed with an incorrect size parameter. If this happens, you can trigger some of the same sorts of state corruption issues that a double-free would cause (you set a random bitmap bit to "free" in the metadata, since you're calculating offsets from the start of a slab incorrectly).

Valgrind won't ever catch this, and Address Sanitizer won't always (it depends on both the exact type of bug, and the sanitization settings).

(As background, I'm a jemalloc developer; reposting my twitter comment on the same article): This is quite a bad way of doing a malloc benchmark -- getting realistic activity patterns is critical (see e.g. Wilson et al.'s survey). It doesn't meaningfully test inter-thread interactions, and randomizes in a way that hurts the effectiveness of thread-local caching.

For the large majority of server workloads on Linux, jemalloc or tcmalloc is probably the right choice of allocator. Trying these out (and spending a few additional test runs tuning their configuration) will often yield significant wins compared to the glibc allocator.

It's implementable with a kernel driver on Solaris because of its scheduling hooks. (This was done in the "Mostly Lock-Free Malloc" paper).

My experience working on an OSS project has been that the biggest thing missing from the bug-reporter side isn't phrasing or planning, just dedication. If someone doesn't post a useful initial bug report, we can still probably work our way there if they keep pinging the thread or follow whatever instructions come out of the maintenance side of things. OTOH, if I can't see that an issue is actively causing someone pain, it's way easier for it to fall off my radar. Apathy slows down resolution far more often than antipathy.

All the volume 4A listings are in MMIX, and there's "The MMIX Supplement" by Martin Ruckert, redoing the first three volumes in MMIX, which I believe is regarded as the authoritative edition.

As to the ultimate versions (or even finishing until volume 5): not to be morbid, but the date there has been continually pushed back, and Dr. Knuth is not a young man.

tl;dr for people familiar with the C/C++11 MM: It's very similar. `relaxed` -> `Opaque`, `seq_cst` -> `volatile`. `acquire` and `release` map more or less the same.

Interestingly, there's no equivalent to C++ `acq_rel` on the RMW operations -- you have to either choose the stronger `volatile` ordering, or do a release fence followed by an acquire RMW (or the reverse).

Regular loads/stores may be mixed with atomic ones, but don't give any coherence or forward progress guarantees, and may see word tearing for longs or doubles.

The java `fullFence()` is stronger than a C++ `seq_cst` one; inserting one between every pair of Opaque accesses gives them sequential consistency (though, I understand that C++ is probably going to strengthen the semantics of `seq_cst` fences eventually).

I think you're on the right track (i.e. viewing it as a permutation, and looking at the cycle decomposition of that permutation).

Try indexing from 0 instead of 1 if you're not. Then the cycle containing 1 will start with (1, 2, 4, 8, ...). What happens when it wraps around?

It's part of the core language semantics (arguably the core language semantics) for Java2K (http://p-nand-q.com/programming/languages/java2k/).

Here's a fun related issue: A common Linux mutex-implementation strategy to deal with this issue (waker-waiter races) is by releasing a mutex before futex-waking any threads blocked on it. Since the waker doesn't know for sure if a waiter is present at the time of waking, the locking thread may fail its futex-wait attempt, acquire the mutex, and destroy it, freeing the mutex's memory back to the allocator. In the end the waker issues a wakeup call to an address no longer occupied by a mutex.

As a result, the mutex implementation might spray futex-wake calls into arbitrary addresses not owned by the implementation. This means that other libraries in the same process can't rely on accurate wakeups, even if it would otherwise be algorithmically correct to do so (unless it has some way of guaranteeing that its synchronization locations never share an address with other libraries).

If you've ever wondered why pthreads-style condition variables allow spurious wakeups, this is one reasonable situation in which they can occur.

Hah, I think I'm that person you're referring to. I would characterize my response differently.

Stripping out the specifics, the problem was: "write some code that blocks until one of a set of memory locations changes its value". The Haskell/STM API provides exactly that interface (where the memory locations you block on are those that you looked at in the transaction). Rephrasing then, the question was "how would you implement a simplified version of the Haskell STM blocking mechanism?", and your solution was "I would use the Haskell STM blocking mechanism", answering the question as though it were one of API usage rather than of API implementation.

That's probably fine as a question of workaday engineering (and maybe an argument for Haskell over C++ on the basis that it has more extensive libraries built-in), but somebody's gotta write that STM implementation, and that's what the challenge was trying to get at.

(In fact, the GHC STM implementation does exactly what the solution I outlined does: with each TVar, it keeps a pointer to threads parked waiting for the TVar's value to change, and unparks all those threads when a transaction modifying the TVar commits).

I don't totally follow the conclusion you're trying to draw w.r.t. the definition of a patent troll; clearly there's a lot of people who think that filing and then attempting to enforce a bogus patent applies (though people differ in which patents they think are bogus). Is this some sort of prescriptivist/descriptivist thing?

> The University of Tennessee Knoxville isn't a one man shop.

I mean, sure; but so what? Clearly they were unable or unwilling to fight this battle. Maybe you're right that they should have better protected Plank and society from StreamScale, but I think it makes more sense to put the blame on StreamScale for engaging in this behavior, and our broken patent for encouraging it. Likewise, the paper has multiple authors, but that doesn't really affect the argument at all.

> Ok, if you're going to attack the patent on novelty grounds, you have an easy case to make

I feel like you're deliberately missing the point. Where do you think I'll make this case? I'm certainly not going to spend tens of thousands of dollars fighting the good fight in court. "Technique" in the quote referred to the use of blocking and vector instructions for matrix multiplication. Lots of matrix libraries had such techniques well before the priority date of the patent.

The patent is on using those existing techniques for matrix multiplication, when that matrix multiplication happens to be a part of an error correcting code. I don't think those sorts of patents should exist. (The "matrix multiplication" here is tricky because it's multiplication in a Galois field, but that's not what the patent claims cover).

Saying that "patent troll" is synonymous with "NPE" is more restrictive than its common usage; for example, wikipedia defines it as "a person or company that attempts to enforce patent rights against accused infringers far beyond the patent's actual value or contribution to the prior art".

If you take a minute to read the patent in question (https://www.google.com/patents/US8683296), it's like a caricature of "what's wrong with the patent system". It describes using matrix blocking and vector instructions to do the matrix mulitplication step of (e.g.) Reed-Solomon. It's a very old matrix multiplication speedup. If a particular technique for a problem isn't novel, then using that technique when you encounter that problem in a particular domain shouldn't count as novel. By contrast, the Usenix paper described an actual mechanism of implementing the arithmetic using vector instructions for table lookups, something the StreamScale patent never did. After reading the StreamScale patent, I came away with no new insights on implementing ECC. After reading the Usenix paper, I did.

The arguments you make for why StreamScale's things don't make any sense to me. It seems like they are:

- No one's fought the patent legally

- The author was threatened into issuing a notice with a super weak statement that StreamScale is sometimes faster than his one-man-shop academic code.

- One of the authors of the paper (though not the software in question as far as I can tell) works for a StreamScale competitor? Not really sure why that was relevant.

But of course no one wants to get into an expensive legal battle merely to advance the public good in this instance; no one is incentivized to. The fact that no one has doesn't mean that the patent is a good thing. Of course the author can be threatened into a non-apology apology with vague wording. That he did so doesn't mean all of those statements should be accepted uncritically.

A lot of times with patents, copyrights, trademarks, we get into a weird sort of cognitive dissonance. We (society) create a new type of property right (here, ownership of IP) in order to incentive people to engage in some type of behavior (here, inventing things). It's then easy to forget that the property right isn't necessarily the thing society wants to protect; it's a means to and end. But in cases like these, it's plainly obvious that the patent is stifling rather than encouraging innovation. The world is a worse place with Professor Plank threatened into removing his code.

An anecdote for those who hoped they'd find suggestions in the comments:

I ended up buying some over-the-head earmuff headphones aimed at construction workers (I think with a 25dB noise reduction rating). I put in ear plugs, then the headphones, and play some light music; even relatively loud and nearby conversations drop away pretty quickly. (Ordinary "noise cancelling" headphones aren't intended to block the sound of talking, and don't work as well).

The only issue is comfort; the headphones fit quite tightly. I got used to it after a few hours, and now don't mind it at all. My wife tried it, and couldn't ever adjust.

The KMP paper is "Fast Pattern Matching In Strings", which cites Cook's "Linear time simulation of deterministic two-way pushdown automata". The former has a neat history section that gives a little more detail than the interview.

I got curious about the etymology of this, and it's not clear to me that wikipedia is right on this one. According to [1], the earliest use of "even" and "odd" for functions goes back to Euler [2]. It's been a long time since high school Latin, but it doesn't look like he has the Taylor series in mind here. He certainly calls out the functions f(x) = x^n for some n as even or odd, and notes that the sums work in the ways you'd expect, but he also talks about ratios of those functions, which he wouldn't need to do if he were assuming smoothness and could just expand out the Taylor series of the ratio. It's unclear, but it looks to me like he's using "even" and "odd" to draw an algebraic analogy.

[1] http://jeff560.tripod.com/e.html [2] http://eulerarchive.maa.org/docs/originals/E005.pdf , section XVII.

> Disabling interrupts prevents you from using interrupt-unsafe logic inside the critical section, which is impractical in most cases. It would mean, for example, that you wouldn't be able to touch memory that had been swapped.

Presumably the semantics of the "lock these two cachelines" instruction trap when one of the cachelines you're trying to lock isn't present, rather than when you perform an operation on that cacheline subsequent to the locking.

> It also doesn't actually improve performance. When people do this, it's because they want to edit process-local data structures. Unless you're in kernel, you probably don't want this.

I don't totally follow; off the top of my head, lock-free reference counting and doubly-linked list removal both get significantly simpler. There's lots of algorithms that get much less complicated and dodge more atomic ops if you have access to CAS-2, and this is strictly more powerful.

To be clear, I don't think this instruction is a good idea; I just don't think it's obviously bad.

> As a practical matter, HTM is dead. It's 2x slower than locking in the common cases: uncontended critical section or contended critical section that has a race. It also prevents you from doing effects outside of memory (it's just guaranteed to revert to locks in that case, so you pay all of the overhead of HTM and all of the overhead of locks).

HTM is already showing wins in some domains, and it's only going to get faster relative to other concurrency primitives.

I'm not totally sure what you mean by "contended and racy" and "contended but not racy"; by "racy" do you mean cacheline ping-ponging? Certainly that will never be cheap. I think most of the desire for lock-freedom comes less from fast-path cycle reduction as much as protection from the scheduler or some very slow process. There's also plenty of situations in which data structures are touched mostly by one thread, but periodically need contention management. The overhead of locking in the single-threaded case can be substantial even if the lock acquisition always succeeds; on my machine a non-atomic CAS is about 6x faster than an atomic one even if the CAS always succeeds (and this was with no stores in between the operations; a more realistic example would have a deeper write-buffer).

I assume interrupts would be disabled or deferred during this section, so you get stronger guarantees on worst-case behavior; hence the bound on the number of cycles a thread is allowed to execute for.

On one of the less common unixes (Sun's maybe? I don't totally remember), you could set a bit in some thread-specific part of memory to indicate that you were uninterruptible. If the OS saw that bit was set, it would set a "you need to yield" bit in the same part of memory and then allow the thread to continue (and penalize threads that abused the feature).

As a practical matter, I suspect that the scheme proposed wouldn't have advantages over a careful use of HTM.

I also suspect that the "lock two cachelines" thing is harder to implement than it sounds. The way Intel implements atomic operations that span cachelines now involves waiting for a interconnect quiescence period (taking O(microseconds)). What's proposed here is strictly more general.

> You mean mode switch? Cheaper, but yes, still costly.

Hah, yes.

> Which means we can calculate the cost to be ~1.1 us per probe (on my system). Anyone know what XRay is clocking in at?

I'm not at Google any more to check (and haven't touched the code since 2012), but IIRC XRay overhead while tracing was something like 100 cycles per function (which includes an entry/exit pair). Hard to compare across different machines made years apart of course, but I think that a little over an order of magnitude difference sounds about right.

Most of XRay was written before uprobes was merged into the Linux kernel (and well before such kernels were widely available).

I don't think any of the alternatives you mentioned are Pareto superior to XRay when considering all of "speed while tracing", "speed while not tracing", and "flexibility".

E.g.:

- In "speed while tracing", anything that takes a context switch per traced function will probably be dramatically slower. Even if there's some fast dispatch mechanism you have in mind that I'm not familiar with when you say dynamic tracing, if it doesn't insert the moral equivalent of a nop-sled, it will have to either choose between logging the whole PC (spending data, which means spending RAM and disk time) or figuring out how to map it to a function-specific unique int (spending cycles).

- In "speed while not tracing", anything much more expensive than nop-sleds will be too slow to run in production.

- Anything that doesn't have a compile time component probably won't be able to completely hook functions that get inlined, or whose source you aren't able to change, won't be able to pick out information the runtime wants to summarize from function arguments, etc.

To me, the neat thing about XRay isn't so much the "function patching" aspect, except insofar as it serves as a mechanism to execute arbitrary code at function entry or exit in a way that's runtime-customizable and very low overhead when you want it to be.