/* DF-3885 model: drm_pick_crtcs() exponential recursion.
 *
 * Kernel code (sys/dev/drm/drm_fb_helper.c:2422-2495): for each connector n,
 * it unconditionally recurses for n+1, and then once more per candidate CRTC:
 *
 *   best_score = drm_pick_crtcs(fb_helper, best_crtcs, modes, n+1, ...);
 *   ...
 *   for (c = 0; c < fb_helper->crtc_count; c++) {
 *           ...
 *           score = my_score + drm_pick_crtcs(fb_helper, crtcs, modes, n+1, ...);
 *   }
 *
 * With every connector carrying a mode (a malicious MST hub can enumerate
 * dozens of fake connectors, each with modes), the call count is
 * (crtcs + 1)^(connectors). On a 4-CRTC i915 (intel_fbdev.c:713 inits the
 * fb helper; MST connectors are appended by intel_dp_mst.c:497), 20
 * connectors => 5^20 ~= 9.5e13 calls in the kms-hotplug worker while it
 * holds fb_helper->lock: a permanent stall that also blocks lastclose /
 * set_par / any other fbdev entry point.
 *
 * This model runs the same recursion (counter only) for increasing connector
 * counts and measures wall time, demonstrating the growth factor per added
 * connector.
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static int crtcs = 4;          /* i915-class GPU */
static unsigned long calls;

static int pick(int n, int N)
{
	int c, o, best, score;

	calls++;
	if (n == N)
		return 0;
	best = pick(n + 1, N);          /* unconditional first recursion */
	for (c = 0; c < crtcs; c++) {
		for (o = 0; o < n; o++)
			;               /* clone check (never trips: multi-crtc) */
		c++;
		c--;
		score = 1 + pick(n + 1, N); /* per-CRTC recursion */
		if (score > best)
			best = score;
	}
	return best;
}

int main(void)
{
	int N;

	for (N = 8; N <= 12; N++) {
		struct timespec t0, t1;
		double ms;

		calls = 0;
		clock_gettime(CLOCK_MONOTONIC, &t0);
		pick(0, N);
		clock_gettime(CLOCK_MONOTONIC, &t1);
		ms = (t1.tv_sec - t0.tv_sec) * 1e3 + (t1.tv_nsec - t0.tv_nsec) / 1e6;
		printf("connectors=%2d crtcs=%d calls=%-12lu time=%8.3f ms\n",
		       N, crtcs, calls, ms);
	}
	printf("\nextrapolation (same growth): 20 connectors = 5^20 = 95367431640625 calls\n");
	printf("at the measured per-call cost above this is hours-days of kernel CPU,\n");
	printf("executed inside the hotplug worker while fb_helper->lock is held.\n");
	return 0;
}