Multithreaded Heisendebugging advice needed

RmbRT said:
What else could I do to debug this code?

Put a lock around every potential concurrency issue and see when the problem goes away.

In my experience the problem mostly is figuring out if all work is really done or not. But can be anything ofc.
A thread save logging function helped me quite a bit. I've had some non obvious issue which only showed up in practice with very small job counts, undetected for months if not years.

I did some more debugging and somehow I think I am occasionally losing threads without requesting their termination, but also without any log message (maybe a write to stdout or stderr in another thread might not get flushed properly? idk) and without immediate crash. Anyway, for now I'll write a custom heap that uses mmap/mprotect/munmap to manage memory, and has a global allocation index that I can go through to do stricter memory validation than the other systems seem to be doing, and with a custom SIGSEGV handler. I'll then add some code that unwinds the stack and prints a stack trace, then aborts. I'll maybe also add a macro that tracks the allocation site or something.

If that doesn't help, I'll try it with mutexes, but that would leave me quite uneasy, because it might just make the bug not appear, without actually fixing the bug.

RmbRT said:
(maybe a write to stdout or stderr in another thread might not get flushed properly? idk)

I use this:

void SystemTools::Log (const char *text, ...)
{
    static std::mutex mutex;
    std::lock_guard<std::mutex> lock(mutex);
    static int maxLines = 50000;
    if (maxLines < 0) return;
    maxLines--;
    va_list vl;
    va_start (vl, text);
    vprintf (text, vl);
    va_end (vl);
    fflush (stdout);
}

The flush at the end makes sure it updates the file immediately iirc, so i get the messages even if the program crashes.

RmbRT said:
If that doesn't help, I'll try it with mutexes, but that would leave me quite uneasy, because it might just make the bug not appear, without actually fixing the bug.

Yeah, it gives no certainty, but still some probability towards better assumptions. Better than guessing at least.

So I wrote a full debug heap based on mmap() and mprotect() that tracks stack traces of all allocations, and ensures old memory is just made inaccessible, not actually freed for reuse, so that I don't get any chance of use-after-free / dangling pointers that point to coincidentally valid memory after a new, unrelated allocation. It catches SIGSEGV and then detects whether it points into invalid memory, or out of bounds of an existing allocation, or into a freed allocation, and then prints exactly where that allocation came from, its alignment, size, etc., and the offset into the allocation that caused the problem. All allocations are placed at the latest permissible address (satisfying the requested alignment), so that out of bounds reads or writes will end up in an inaccessible page. All bytes of the allocation are initially set to 0xba and the unused bytes around the allocation are all 0xfb, and each call to free() checks that the padding remains at 0xfb.

This rarely triggers, but seems to be a secondary effect of a race somewhere. I then came up with the idea of using a race guard in my data that is supposed to already be protected by the atomics I use in the job queue. It's similar to a mutex but if it fails to acquire the lock, it just dies. It also just uses a relaxed atomic exchange. So it keeps the old mechanism and just adds an error detector on top. The guard stays in effect for the entire duration of the scope, so all accesses to my data are contained within the guard's lifetime, and without acquiring the guard, I cannot access it (type-level guarantee). So in theory, this should detect any actual races that occur. If the issue is in fact caused by the job queue and not something else entirely.

Sadly, every recompilation or any unrelated refactor seems to change the odds of the bug occurring. Anyway, with this extra check in place, I was no longer able to reproduce the problem, even though it did not change how the program fundamentally functions. At least now it should trigger if any races do actually occur.

I'm also letting the program run in a big loop in gdb for hours on end to try to chance upon the issue and debug it.

RmbRT said:
So I wrote a full debug heap based on mmap() and mprotect() that tracks stack traces of all allocations, and ensures old memory is just made inaccessible, not actually freed for reuse, so that I don't get any chance of use-after-free / dangling pointers that point to coincidentally valid memory after a new, unrelated allocation.

You didn't mention the platform you are one, but assuming windows, there is a tool that already does that for you: https://learn.microsoft.com/de-de/windows-hardware/drivers/devtest/application-verifier.
That's part of the Windows Development SDK, you add your app and set the “Heaps” flag, and it will automatically place allocations on its own page with the write-protections on deallocation… you already wrote your own, but thought it'd mention it.

It catches SIGSEGV and then detects whether it points into invalid memory

Are you certain SIGSEGV is the thing triggering the crash in the thread? You didn't mention it explicitely in the post, and in general there are multiple differente mechanisms that can cause a race-condition related crash. Also, catching even just a SIGSEG on the site of allocations/deallocations seems not very solid, as it can be triggered anywhere, realistically. In general, I'd advice you setup any (or all) of the available global crash-handlers. For example, you can register handler for the different crash-related SIGs:

        	void __cdecl abortHandler(int signum)
        	{
        	   // handle crash here
        	}
        
        signal(SIGABRT, abortHandler); // register handler at program startup
        signal(SIGSEGV, abortHandler);
        signal(SIGILL, abortHandler);
        signal(SIGFPE, abortHandler);

Otherwise, you can also try SEH, for trapping most critical runtime-errors:

LONG WINAPI crashHandler(EXCEPTION_POINTERS* ExceptionInfo)
{
    // handle crash here
}

__try
{
	runYourCode(); // SEH has a few restrictions in the calling frame, so best to wrap your actual calls in a function
}
__except(crashHandler(GetExceptionInformation()))
{
	return -1;
}

Additionally, there is Vectored Exception Handling, which may catch types of bugs that result from critical stack-corruption (as most other error-handling code still relies on the stack-unwind prodecure working properly.

It might seem overkill, but I'm using all 3 methods concurrently in production-code, since each manages to catch different types of errors, at different stages of the program. Especially if you only need it for local trapping of a bug.

If you manage to trap it, you can then generate a full Minidump of the application. This can be many GBs large, but it allows you to drag it into VS after the fact and restore the state the program was in at the time of the crash.

RmbRT said:
Sadly, every recompilation or any unrelated refactor seems to change the odds of the bug occurring. Anyway, with this extra check in place, I was no longer able to reproduce the problem, even though it did not change how the program fundamentally functions. At least now it should trigger if any races do actually occur.

I'd assume those extra checks take a lot of time/performance, so the timing-issue probably never occurs. I'd generally assume that the faster all threads can run concurrently, the likelier it is to trigger race-conditions (as otherwise, the point in time where a unsynchronized concurrent access happens is very brief, compared to the rest of the code running). I'd try to test if Application Verifier does anything different; or else restore all changes you did, implement all the global crash handlers mentioned and see if you can then trap the exception more reliably (AppVerifier will not be much faster than your solution; but the other crash-handlers have no runtime-overhead, so you might get the original behaviour).

(Of course, details here may vary if you are actually not on Windows).

Thanks for the effort in replying to me. I'm using Linux, and I had used valgrind before, which basically executes the whole program in an emulation mode or something (at 1/50th the speed…) which tracks even where uninitialised values initially came from and notifies you for example when a condition depends on an uninitialised value. But it couldn't detect any problems. It also detects memory leaks and all that. It also has a race detection mode but that didn't trigger, either, for my code. Maybe that only works in concert with std::mutex, not with custom-rolled synchronisation primitives.

The SIGSEGV is caught globally, and I use my custom debug heap to determine what kind of invalid memory access it is, whether it is within a freed allocation, or out of bounds of an existing allocation, or in some completely unknown region, etc.

The work the threads perform is long compared to a single atomic exchange instruction, it's reading source files from disk (syscall + I/O delay, if the file isn't already in cache), tokenising source files (probably a few cycles per character or something), or parsing token streams. But somehow the addition of the check still made it not occur any longer. But I guess if it never happens in practice, and gets caught if it does happen and forces a crash when it is detected, then any successful execution of my compiler should be seen as probably correct. It's not a great situation to be in, but whatever. I also added a flag that lets me turn off threading and execute everything on the main thread, depending on an environment variable.

Before adding the race detector, 95% of the time the program would run just fine, but sometimes would either do a weird stall where one thread would simply disappear for no identifiable reason and not process more work, and another thread would then panic when no new work got processed in over a second (usually the whole program just takes a couple dozen milliseconds in total). But in other instances, it would die with a segfault, reading some invalid out of bounds address (but with the amount by which it is out of bounds varying per execution). Now, I no longer get any segfaults or stalls, eventhough I only added a race detection, not any actual race prevention.

Before using my custom debug heap, which keeps track of the allocations using the libc system heap (malloc), while allocating the user memory using mmap directly from the kernel, those out-of-bounds accesses probably corrupted the bookkeeping of the standard heap, as that seems to keep bookkeeping information adjacent to the actual user memory allocations. And thread termination seems to perform an integrity check on the standard heap, which was the point at which I got those weird heap error messages. The custom heap instead causes a proper SIGSEGV on out of bounds access in almost all cases, but never allows for accidentally messing up the heap's bookkeeping.

I previously managed to catch a few instances of those thread stalls in the GDB debugger, but I was never able to figure out what went wrong by examining the program state. Except for noticing that some threads seemed to be missing in those cases. So those threads probably also terminated early through some race condition or something, no idea how that happened. Anyway, I let the program run for a few hours in a loop (probably over ten thousand times already) and no longer got any crashes or hangups or SIGSEGVs or anything. So maybe when I start writing more of the rest of the program, I'll be able to reproduce the error again, but for now, it is simply irreproducible. But now I am equipped with all the tools I need to debug such problems again, with a custom debug heap that properly diagnoses SIGSEGV with lots of contextual info on the allocation and stacktraces, and a singlethreading flag, and race detectors, and all that. All of those I can easily turn on or off by just changing environment variables.

Regarding stack corruptions: I have bounds-checked arrays everywhere and also some buffers I just declare as static so that they can't corrupt the stack either. Or I could just heap-allocate them.

Ok I think I know what the problem was. Lockless synchronisation wasn't the issue, I think, but rather that the queues I was working on did not have strong cacheline separation of the contained items. So while the individual bytes were properly guarded by the lockless atomics, the cachelines were still concurrently accessed by the different threads, as multiple items might have been on the same cacheline.

That's something you don't learn in atomics 101… No wonder adding an atomic guard to it helped, because that guard is aligned to cachelines… That's a scary bug that I never encountered before, probably by luck. Because I've been using lockless atomics for ages. Seems like even if individual bytes are properly mutexed, you still get oneshotted by the fact that CPUs don't merge partially updated cachelines across cores, but rather migrate entire cachelines, if I'm not mistaken. Or it was the fact that I use packed structs everywhere, so only explicitly requested alignment requirements get obeyed. So it might have been unaligned reads/writes, too, that caused that. Probably a mix of cacheline contention coupled with unaligned accesses leading to sync problems.

This is why abstract machines defined by language specs suck.

RmbRT said:
the queues I was working on did not have strong cacheline separation of the contained items.

I'm confused.
Does this mean you can have something like an array or allocated memory which allows atomic access per individual item?
How else can your queue items be atomic?

I'm asking because i thought this would not work on CPU, or at least isn't supported by things like std::atomic. Which sucks.

On GPU nothing of this is needed. There are only atomic operations like atomicAdd(), and they work on any memory without the need to specify potential atomic access. Which is great.

EDIT: I guess only a counter / index of your queue is atomic, but then writing the items in normal memory concurrently caused the issues?

The counters that manage which region of the ringbuffer is accessible to a thread are atomic and IMO bugfree. And access to the ringbuffer strictly adheres to what the counters say. But the elements in the ringbuffers are not cacheline aligned, and internally also have no natural alignment (#pragma pack). So it is very well possible that I get two ringbuffer entries that share a cacheline, one that is available for modification for queueing new workloads from the main thread, and the other entry is available for consumption by the worker thread. And both of these might share an 8-byte or 16-byte bank within that cacheline, which might trip up the write conflict resolution when false sharing occurs. So the preparation of the next workload, which modifies bytes that the worker thread doesn't even read, might still modify bytes he reads because false sharing might merge together changes that occur on different banks within a cacheline or something.

I removed the atomic guard around the ringbuffer entries, which was initially a struct containing the normal entry, followed by a cacheline-aligned atomic flag (so it implicitly aligned the entire ringbuffer entry to cacheline boundaries). As I wrote earlier, that guard, eventhough it only used relaxed atomics and only for race detection, not for actual mutual exclusion, prevented the memory corruptions. And now after I removed the guard, but made it so that each element in the ringbuffer is cacheline-aligned, I also no longer get any crashes / corruptions. Also didn't get the weird stall anymore on the worker thread, although that may be a separate issue or something, idk. I still don't fully understand what exactly caused the bug, or how exactly it happened, but I'm sure it has to do with misaligned, non-atomic, but properly guarded access to separate areas in the same cacheline, and then false sharing / cacheline migration messing up.

If you are getting multiple locks like that, there needs to be work around resource priorities and handling potentially recursive and reentrant code, among other varieties. It can also have tendrils into task scheduling and inverting priorities of tasks based on locks, or isolating and bundling sets of work to minimize contention.

Libraries like boost::recursive_mutex are already debugged. There are assorted lock priority systems that can help reduce resource contention and livelock scenarios. What tools to use depends on the design details, and there is no universal solution.

They aren't fun to solve. A few years back we needed to push in a replacement system similar to this, the big block of work took 12 engineers (senior, advanced, and principal in the job title) 4 months of work across the live service game as it was swapped out without bringing the game down. Tricky to get right, disastrous to get wrong, and many instances need efforts to ensure locks are ordered correctly, and a system that detects, reports, and handles the typical errors. Good luck.

And since this felt like something from the past, https://www.gamedev.net/forums/topic/677195-multi-thread-deadlock-issue-with-a-recursive-mutex-need-ideas/ is an example of one such from a decade ago.

The code I was using that for was a simple producer-consumer queue with one producer and one consumer thread, operating on a ring buffer. Really not that complicated. I can write the atomics for that in my sleep. No re-entrancy or recursion, etc.. I already wrote an entire multithreaded coroutine library back before C++ had native coroutines. That was a real challenge, because it was supposed to be fully lockfree and I also had to heavily abuse macros to make the entire thing use a custom scheduling and all that. I also wrote a library for atomic multi-resource locks and all that stuff. I also never used std::memory_order_consume, because I just could not wrap my head around what the documentation was trying to tell me about it. That one is hard. Or using relaxed atomics correctly without getting trolled by the compiler reordering my code or eliminating the accesses altogether, that's another one that sucks. But a simple producer-consumer queue on a ringbuffer is not that hard, atomics-wise.

But yeah, now that I know that I should always separate all mutexed data one cacheline boundary away from other mutexed data not just for performance but also for correctness, I don't think I'll make that mistake again, it's pretty straightforward. Took me over a month (of sporadic effort) to identify the problem. But at least now I also have a really good debug heap with good segfault diagnostics that isn't slow, and it will be available in all my programs by just setting an environment variable.

The thing I was solving this time was that in my self-hosted compiler, I start out with a set of initial file names, which I pass to the file loader thread in a queue. As it starts returning file contents, I tokenise just enough to parse the INCLUDE directives at the start of the file, and pass the file paths for inclusion straight back to the loader thread, and the rest gets multiplexed over to two separate tokeniser job queues for full file tokenisation. The results of those then get fed into a single parser thread which gets a fully tokenised file stream. So far, all the jobs are issued by the main thread and all the results are also collected by it, so it acts as a central hub for passing around work.

The aim of that whole construct is that, assuming we do not have the files in the OS cache, we can only load a file at a time anyway, and we want to bottleneck on disk IO if possible, so we have one thread that handles only raw file loading. For simplicity I only operate on whole files, which only adds a bit of latency but does not affect throughput. Instead of performing a complex operation on each file (chunk-wise load, and tokenise during parse), I keep tasks small to have better instruction cache performance per task. I assume that parsing progresses through a file much faster than tokenising does, so I only need one parser thread, but I use two tokeniser threads because I assume that disk I/O might be quite a bit faster than tokenising, but probably not that much faster to warrant more threads. The parser also just populates data structures from the token stream and because there is only one parser thread, it can have complete single-threaded ownership over the global scope it populates. I haven't gotten further along in this recent full rewrite of the self-hosted compiler yet, so later stages don't exist yet. But the goal is to have all stages run in one pipeline of worker threads (potentially using up to 8 stages or something). The language uses a modern global scope that does not depend on declaration order, so I need a fully populated global scope in order to start actually resolving names (unless they are referring to function-local symbols), which means I need to have the entire project loaded and parsed before I can proceed. Later on, I'll add visibility boundaries to file scopes (private/public), but for now, to keep compatibility with the bootstrap compiler, all file scopes share the same global scope.

The problem this time seemed to simply be that the data that was being protected (the ringbuffer entries for the jobs/results queue) did not start/end on cacheline boundaries and had no natural internal alignment, so I got bank conflicts or whatever, as the CPU cores don't synchronise on a byte granularity, but on some 8/16 byte granularity or something.