puzzle.c

// For N = 11, a call to perms(p, N, 0) only takes 0.36 seconds.
// Why would a debugger seemingly hang forever when you try to
// step over the outermost recursive call to perms in the loop?
// Hint: How is "step over" ("next" in gdb/lldb) implemented?

u64 perms(u64 p[N], int n, u64 s) {
	if (n == 1) {
		s += signature(p);
	} else {
		for (int i = 0; i < n; i++) {
			swap(p[0], p[i]);
			s = perms(p + 1, n - 1, s);
			swap(p[0], p[i]);
		}
	}
	return s;
}

You can generate a little return shim whose address you push on the stack before starting execution at the step-over call target's address. The shim just does int3 but has unwind info, a proper prologue and whatever else is needed so that generic platform-compliant stack trace logic will be able to walk past it while your debugger's stack tracer can hide it from the user. Another side benefit of this approach (which I haven't seen any debugger do) is that it will handle longjmp/non-local exits more sanely when you longjmp past a step-over stack pointer mark.

Ok, so I got a little further with my understanding of this (implemented the "effectively hangs" version myself), and I have a further question if that's ok.

Regarding Wons comments on "implementing CFA and strategically placing traps": is it worth it at all? My reasoning is as follows: you want to do a single step, which effectively means executing all instructions on a single line of source code. But how many instructions could that be, if we skip over call and rep whatevs? I mean yes, you could put all your code on one line, but in a real situation, how many instructions would a single source line map to? A few dozen?

That's is my argument for "single stepping until the heat death of the universe".

What are your thoughts on this?

I've never bothered doing CFA but the strongest case for something like that is implementing efficient "step over" for inlined calls. I haven't thought it through in detail, though.