Crash in METIS_PartGraphRecursive in UE 5.7

[jamiehayes]

Hello,

We are seeing a crash in the wild with UE 5.7 with our usage of libmetis 5.2.1. The only thing that has changed since 5.6 with the affected area is that we upgraded libmetis to 5.2.1 from 5.1. Attached is a dump + symbols to debug it. Any help here would be appreciated.

-Jamie

libmetiscrash_UEMinidump.zip

[gfaster]

I could probably help (I know a potential unreported bug that I've fixed in my fork), could you share the configuration settings you use? I dont have a handy way of viewing minidumps.

[jamiehayes]

You can open that in just Visual Studio. But here's the callstack of the crash:

	libmetis__FM_2WayCutRefine()
 	libmetis__GrowBisection()
	libmetis__Init2WayPartition()
	libmetis__MlevelRecursiveBisection()
	METIS_PartGraphRecursive()

By configuration settings, do you mean the options passed to the function?

 	idx_t NumConstraints = 1;
	idx_t NumParts = 2;
	idx_t EdgesCut = 0;

	real_t PartitionWeights[] = {
		float( TargetNumPartitions / 2 ) / TargetNumPartitions,
		1.0f - float( TargetNumPartitions / 2 ) / TargetNumPartitions
	};

	idx_t Options[ METIS_NOPTIONS ];
	METIS_SetDefaultOptions( Options );

	// Allow looser tolerance when at the higher levels. Strict balance isn't that important until it gets closer to partition sized.
	bool bLoose = TargetNumPartitions >= 128 || MaxPartitionSize / MinPartitionSize > 1;	
	
	Options[ METIS_OPTION_UFACTOR ] = bLoose ? 200 : 1;

[gfaster]

I removed Windows from my last machine a couple years ago now, so opening in Visual Studio is non-trivial. I had a friend help with that, but it looks like there is something more significant happening here, mainly that this crash info seems like nonsense.

%rip isn't on an (or rather a reasonable) instruction boundary, so I can only conclude there was a corrupted indirect jump, which is strange because METIS doesn't utilize any function pointers. The instruction the dump is reporting doesn't access memory and the faulting address isn't in any of the registers in the METIS thread. There also isn't detailed debugging information for METIS other than symbol names, so there isn't much to go on beyond that.

Regardless, with those options it seems unlikely the bug I was thinking of was the culprit, as I've only seen it with the minconn or contig options. Is this happening with any regularity? I'm still generally somewhat familiar with the codebase from RIIR-ing it so I may be able to gain some insights from a less inconsistent core dump.

[jamiehayes]

Unfortunately I've not been able to reproduce this myself, we've only got the dumps from our crash dump reporter. From my limited look at it, it doesn't necessarily seem that the IP is in a strange place, but rather that the minidump probably had not captured the pages these ?? instructions are on (perhaps they weren't paged in?). Indeed the dump seems to think the IP is on the add instruction below. But if any nearby access seems invalid based on register values and memory accesses, it seems the cmp instruction would be the culprit:

00007FF91F2768DC  ?? ?????? 
00007FF91F2768DD  ?? ?????? 
00007FF91F2768DE  ?? ?????? 
00007FF91F2768DF  ?? ?????? 
00007FF91F2768E0  add         al,46h  
00007FF91F2768E2  cmp         edi,dword ptr [rax+4]  
00007FF91F2768E6  jl          libmetis__FM_2WayCutRefine+4C0h (07FF91F276780h)  

Registers:
RAX = 00000000000014BE RBX = 000000000000000F RCX = FFFFFFFFC5430000 RDX = 0000000000000006 RSI = 00000000000000A8 RDI = 000001A7D45A5750 R8  = 0000000000000000 R9  = 000001A8FE90B4B0 R10 = 0000000000000001 R11 = 000001A8FE90B770 R12 = 0000000000000008 R13 = 000001A7D45A53F0 R14 = 000001A7D45A57B0 R15 = 000000000000002A RIP = 00007FF91F2768E0 RSP = 00000064991FDBF0 RBP = 000000000000000F EFL = 00010217 

dword ptr [rax+4] seems like a likely null dereference. I wonder if out-of-order execution and pipelining could be making it so the exact instruction that caused the exception doesn't necessarily align with the IP. Also, the debugger is reporting Access violation reading location 0x00000062C337DC88, but the closest register to that value is the stack pointer, and it's not really close at all, tbh.

[gfaster]

From my limited look at it, it doesn't necessarily seem that the IP is in a strange place, but rather that the minidump probably had not captured the pages these ?? instructions are on (perhaps they weren't paged in?)

The minidump ip is not on a page boundary, so that seems unlikely. If I recall correctly, if you adjust the ip two bytes earlier the rest of the disassembly works (it was rather confusing trying to manually find the ip in objdump)

I wonder if out-of-order execution and pipelining could be making it so the exact instruction that caused the exception doesn't necessarily align with the IP

I would not expect to see that behavior ever. Page faults are serializing operations, so OOO should appear in-order here. Even if there were OOO effects, the IP should be set to the exact instruction that caused it to allow for normal page fault handler behavior (e.g. for memory mapped files). My best guess at what happened here (which is weak conjecture at best) is that there's a version mismatch between the library that crashed and the reported library. That being said, I would expect the crash reporter to save hashes of the binary or something like that and that doesn't explain the deal with the faulting address. Gavin Rohrer

[jamiehayes]

This dump seems to be a little less weird, and looks like it's trying to dereference a pointer that's set to 0xFFFFFFFFFFFFFFFF.

libmetiscrash_UEMinidump2.zip

[gfaster]

(this is mostly for myself) I've taken a look and it seems like what happened is that we somehow got where[k] = 4 at:

METIS/libmetis/fm.c

Line 150 in a6e6a2c

rpqInsert(queues[where[k]], k, ed[k]-id[k]);

I've ruled out the most likely cause being the update to 5.2 running into ABI problems (order of moptions_et was changed)

There's no memory mapped in where we could've gotten that from (I think), but I need to look with a better decompiler. I feel like there should be full debug info generated but alas there is none (I also don't know what it takes to fix that on Windows).

[gfaster]

@jamiehayes I'm at a bit of an impasse here - please do share any other crash dumps that appear to be related if they come up.

[jamiehayes]

Here's the latest dump from UE 5.7.1. Definitely looks like where[10] gave a bad index (0xffffffffc38e8000) (sign extended) in this line:

rpqUpdate(queues[where[k]], k, ed[k]-id[k]);

contents of where[0-10]:

[0x00000000] | 0x44e4a000
[0x00000001] | 0x0000000a
[0x00000002] | 0xc489c000
[0x00000003] | 0x00000009
[0x00000004] | 0xc5146000
[0x00000005] | 0x00000006
[0x00000006] | 0xc489c000
[0x00000007] | 0x00000009
[0x00000008] | 0xc5151000
[0x00000009] | 0x0000000a
[0x0000000a] | 0xc38e8000

libmetiscrash_UEMinidump3.zip

[karypis]

Is this issue reproducible using Metis' command line programs? If it is, upload the graph and the command line that creates the problem.

[jamiehayes]

Unfortunately we’re only seeing this in the wild via a crash reporter, and it’s fairly rare. As soon as I do have a repro on hand I’ll post it though.