sched/deadline: total_bw leak when SCHED_DEADLINE is set on a dead task

sched/deadline: total_bw leak when SCHED_DEADLINE is set on a dead task

[Weiheng Qiu]

Hi,

sched_setattr(SCHED_DEADLINE) on a task that has exited but has not
been reaped returns 0 and charges the root domain's dl_bw->total_bw.
The task never runs again, so nothing releases it, not even reaping.

__sched_setscheduler() does not look at p->exit_state, so
sched_dl_overflow() charges the task. A DL task's bandwidth is
normally released at its last dequeue, which a task that has already
done its final __schedule() never reaches again.

Repeating it fills total_bw to the admission cap: a later
sched_setattr(SCHED_DEADLINE) and CPU offline then fail with -EBUSY
with no DL task left; only a root-domain rebuild recomputes it. A
thread-group leader that exits while its other threads run stays
unreaped and keeps the TGID, so a pid is enough. Needs CAP_SYS_NICE,
as any DL admission does.

Reproducer below; needs root and debugfs, assumes x86-64. On mainline
c339f4010dea (0.25 CPU == 262144):

  task 63 state Z
  total_bw at start: 0.100 CPU (104856)
  SCHED_DEADLINE on the zombie: rc 0, policy 6, total_bw 0.350 CPU (367000)
  zombie reaped: total_bw 0.350 CPU (367000), +0.250 CPU (262144)
  6 more zombies admitted, then: Device or resource busy
  total_bw 1.850 CPU (1939864)
  DL tasks left: 0; new 0.250-CPU request: Device or resource busy
  after a root-domain rebuild (recomputed): total_bw 0.100 CPU (104856)

Thanks,
Weiheng Qiu
Vanderbilt University

/* sched_setattr(SCHED_DEADLINE) on a zombie succeeds and charges total_bw;
 * the task never runs again, so nothing releases the reservation, not even
 * reaping the zombie (only a full root-domain rebuild recomputes total_bw).
 *
 * Build: gcc -O2 -Wall -o zombie_admit_leak zombie_admit_leak.c
 * Run as root. Needs CONFIG_DEBUG_FS; total_bw is read from
 * /sys/kernel/debug/sched/debug.
 */
#define _GNU_SOURCE
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <signal.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mount.h>
#include <sys/syscall.h>
#include <sys/wait.h>

#define SCHED_OTHER_		0
#define SCHED_DEADLINE_		6
#define BW_UNIT			(1LL << 20)	/* BW_SHIFT: 1 CPU == 1 << 20 */

struct sched_attr_ {
	uint32_t size;
	uint32_t sched_policy;
	uint64_t sched_flags;
	int32_t  sched_nice;
	uint32_t sched_priority;
	uint64_t sched_runtime;
	uint64_t sched_deadline;
	uint64_t sched_period;
};

static inline int setattr(pid_t pid, uint32_t policy, uint64_t flags,
		   uint64_t runtime_ns, uint64_t deadline_ns, uint64_t period_ns)
{
	struct sched_attr_ a = {
		.size = sizeof(a), .sched_policy = policy, .sched_flags = flags,
		.sched_runtime = runtime_ns, .sched_deadline = deadline_ns,
		.sched_period = period_ns,
	};
	return syscall(SYS_sched_setattr, pid, &a, 0) ? -errno : 0;
}

static inline int getattr(pid_t pid, struct sched_attr_ *a)
{
	memset(a, 0, sizeof(*a));
	return syscall(SYS_sched_getattr, pid, a, sizeof(*a), 0) ? -errno : 0;
}

static inline void need_debugfs(void)
{
	if (access("/sys/kernel/debug/sched/debug", R_OK))
		mount("debugfs", "/sys/kernel/debug", "debugfs", 0, NULL);
	if (access("/sys/kernel/debug/sched/debug", R_OK)) {
		perror("/sys/kernel/debug/sched/debug");
		exit(2);
	}
}

/* dl_bw->total_bw of the root domain @cpu belongs to. */
static inline long long total_bw(int cpu)
{
	FILE *f = fopen("/sys/kernel/debug/sched/debug", "r");
	char line[256], *p;
	long long v = 0;
	int cur = -1, c;

	if (!f) {
		perror("open sched/debug");
		exit(2);
	}
	while (fgets(line, sizeof(line), f)) {
		if (sscanf(line, "dl_rq[%d]:", &c) == 1)
			cur = c;
		else if (cur == cpu && (p = strstr(line, "dl_bw->total_bw")) &&
			 (p = strchr(p, ':'))) {
			v = atoll(p + 1);
			break;
		}
	}
	fclose(f);
	return v;
}

static inline char task_state(pid_t pid)
{
	char path[64], buf[512], *p;
	FILE *f;

	snprintf(path, sizeof(path), "/proc/%d/stat", pid);
	f = fopen(path, "r");
	if (!f)
		return '?';
	if (!fgets(buf, sizeof(buf), f))
		buf[0] = 0;
	fclose(f);
	p = strrchr(buf, ')');
	return p && p[1] && p[2] ? p[2] : '?';
}

/* Wait until @pid is asleep (S) in the kernel. */
static inline void wait_sleeping(pid_t pid)
{
	for (int i = 0; i < 1000 && task_state(pid) != 'S'; i++)
		usleep(1000);
}

/* A child that blocks in read() and never wakes up by itself. */
static inline pid_t spawn_sleeper(void)
{
	int fd[2];
	pid_t pid;
	char ch;

	if (pipe(fd))
		exit(2);
	pid = fork();
	if (pid == 0) {
		close(fd[1]);
		if (read(fd[0], &ch, 1) < 0)
			_exit(1);
		_exit(0);
	}
	close(fd[0]);
	wait_sleeping(pid);
	return pid;
}

static inline void reap(pid_t pid)
{
	kill(pid, SIGKILL);
	waitpid(pid, NULL, 0);
	usleep(200 * 1000);	/* well past any 0-lag time */
}

static inline const char *bw_str(long long bw)
{
	static char buf[4][48];
	static int i;
	char *b = buf[i++ & 3];

	snprintf(b, 48, "%.3f CPU (%lld)", (double)bw / BW_UNIT, bw);
	return b;
}

/* Number of threads whose policy is SCHED_DEADLINE (field 41 of stat). */
static inline int count_dl_tasks(void)
{
	char path[600], buf[1024], *s;
	struct dirent *p, *t;
	DIR *pd, *td;
	FILE *f;
	int n = 0, i;

	pd = opendir("/proc");
	while (pd && (p = readdir(pd))) {
		if (p->d_name[0] < '0' || p->d_name[0] > '9')
			continue;
		snprintf(path, sizeof(path), "/proc/%s/task", p->d_name);
		td = opendir(path);
		while (td && (t = readdir(td))) {
			if (t->d_name[0] == '.')
				continue;
			snprintf(path, sizeof(path), "/proc/%s/task/%s/stat",
				 p->d_name, t->d_name);
			f = fopen(path, "r");
			if (!f)
				continue;
			s = fgets(buf, sizeof(buf), f) ? strrchr(buf, ')') : NULL;
			fclose(f);
			for (i = 0; s && i < 39; i++)
				s = strchr(s + 1, ' ');
			if (s && atoi(s + 1) == SCHED_DEADLINE_)
				n++;
		}
		if (td)
			closedir(td);
	}
	if (pd)
		closedir(pd);
	return n;
}

/* After a leak, ask for a reservation of the same size for a new task. */
static inline void try_fresh_admission(uint64_t runtime_ns,
				       uint64_t period_ns)
{
	int dl = count_dl_tasks();
	pid_t pid = spawn_sleeper();
	int rc = setattr(pid, SCHED_DEADLINE_, 0, runtime_ns, period_ns,
			 period_ns);

	printf("DL tasks left: %d; new %.3f-CPU request: %s\n", dl,
	       (double)runtime_ns / period_ns,
	       rc ? strerror(-rc) : "accepted");
	reap(pid);
}

/* Reading this sysctl makes sched_rt_handler() call rebuild_sched_domains(),
 * whose dl_rebuild_rd_accounting() recomputes total_bw from the servers and
 * the SCHED_DEADLINE tasks that actually exist. */
static inline long long recomputed_total_bw(int cpu)
{
	char buf[32];
	int fd = open("/proc/sys/kernel/sched_rt_runtime_us", O_RDONLY);

	if (fd >= 0) {
		if (read(fd, buf, sizeof(buf)) < 0)
			perror("sched_rt_runtime_us");
		close(fd);
	}
	return total_bw(cpu);
}

#define RUNTIME	(5 * 1000 * 1000ULL)	/* 5ms / 20ms = 0.25 CPU */
#define PERIOD	(20 * 1000 * 1000ULL)

static pid_t spawn_zombie(void)
{
	siginfo_t si;
	pid_t pid = fork();

	if (pid == 0)
		_exit(0);
	/* Wait for the exit but leave it unreaped. exit_state is set in
	 * exit_notify(), before the child's final schedule; give it time to
	 * get off the runqueue, after which nothing would release a charge. */
	waitid(P_PID, pid, &si, WEXITED | WNOWAIT);
	usleep(20 * 1000);
	return pid;
}

int main(void)
{
	long long base, b1, b2;
	struct sched_attr_ a;
	pid_t pid;
	int i, rc;

	need_debugfs();
	base = total_bw(0);
	pid = spawn_zombie();
	printf("task %d state %c\ntotal_bw at start: %s\n", pid,
	       task_state(pid), bw_str(base));
	rc = setattr(pid, SCHED_DEADLINE_, 0, RUNTIME, PERIOD, PERIOD);
	getattr(pid, &a);
	b1 = total_bw(0);
	printf("SCHED_DEADLINE on the zombie: rc %d, policy %u, total_bw %s\n",
	       rc, a.sched_policy, bw_str(b1));
	waitpid(pid, NULL, 0);
	usleep(200 * 1000);
	b2 = total_bw(0);
	printf("zombie reaped: total_bw %s, +%s\n", bw_str(b2),
	       bw_str(b2 - base));

	for (i = 0; i < 1000; i++) {
		pid = spawn_zombie();
		rc = setattr(pid, SCHED_DEADLINE_, 0, RUNTIME, PERIOD, PERIOD);
		waitpid(pid, NULL, 0);
		if (rc)
			break;
	}
	printf("%d more zombies admitted, then: %s\n", i,
	       rc ? strerror(-rc) : "-");
	printf("total_bw %s\n", bw_str(total_bw(0)));
	try_fresh_admission(RUNTIME, PERIOD);
	printf("after a root-domain rebuild (recomputed): total_bw %s\n",
	       bw_str(recomputed_total_bw(0)));
	return b2 != base;
}