sched/deadline, cpuset: total_bw corrupted by a sleeping DL task's cpuset move

[Weiheng Qiu <weihengqiuu@gmail.com>]

Hi,

Moving a sleeping SCHED_DEADLINE task from the root cpuset into an
exclusive partition and back, before it runs again, leaves the root
domain short by the task's bandwidth. The root then over-admits, and
when the task exits its total_bw underflows: small DL requests fail
with -EBUSY while large ones wrap in __dl_overflow() and are admitted.
The partition also keeps a stale reservation.

cpuset_can_attach() and set_cpus_allowed_dl() both decide through
dl_task_needs_bw_move(), which tests task_rq(p)->rd. A sleeping task
is not migrated when its affinity changes, so task_rq(p) still points
at the CPU it last ran on, and on the move back the root domain is
neither re-credited nor the partition debited.

Reproducer below; needs root, cgroup v2 and debugfs, and turns the
last CPU into a partition, so use a test VM. On mainline c339f4010dea
with 4 CPUs:

  cpu3 is a partition; sleeping DL task 76 (0.5 CPU) in the root cgroup
  total_bw in CPUs (change since start):
  start:                     root  0.650 (+0.000)   partition  0.050 (+0.000)
  moved into the partition:  root  0.150 (-0.500)   partition  0.550 (+0.500)
  moved back to the root:    root  0.150 (-0.500)   partition  0.550 (+0.500)
  (expected: +0.000 and +0.000; the task is in state S and has not run)
  root domain admits 28 more 0.1-CPU tasks: 0.650 + 28 x 0.1 = 3.450 CPU
  reserved, limit 3.000 CPU (3 CPUs x 1000000/1000000)
  those tasks exited:        root  0.150 (-0.500)   partition  0.550 (+0.500)
  the DL task exited:        root -0.350 (-1.000)   partition  0.550 (+0.500)
  DL tasks left: 0; new 0.010-CPU request: Device or resource busy
  DL tasks left: 0; new 0.500-CPU request: accepted
  after a root-domain rebuild (recomputed): root 0.150, partition 0.050
  moved in while asleep, then SCHED_DEADLINE: Operation not permitted

Thanks,
Weiheng Qiu
Vanderbilt University

/* A sleeping SCHED_DEADLINE task moved into an exclusive cpuset partition and
 * back, without running in between: the move out debits the root domain and
 * credits the partition, the move back does neither, because
 * dl_task_needs_bw_move() looks at task_rq(p)->rd, which for a task that has
 * not run since the first move is still the root domain.
 * Needs cgroup v2 with the cpuset controller and at least 2 CPUs.
 * It temporarily turns the last CPU into a partition; use a test VM.
 *
 * Build: gcc -O2 -Wall -o cpuset_blocked_move cpuset_blocked_move.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/stat.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	(25 * 1000 * 1000ULL)	/* 25ms / 50ms = 0.5 CPU */
#define PERIOD	(50 * 1000 * 1000ULL)
#define CG	"/sys/fs/cgroup"
#define PART	CG "/dl-repro"
#define MAXF	1000

static int put(const char *path, const char *val)
{
	int fd = open(path, O_WRONLY), rc = 0;

	if (fd < 0 || write(fd, val, strlen(val)) < 0)
		rc = -errno;
	if (fd >= 0)
		close(fd);
	return rc;
}

static void get(const char *path, char *buf, int len)
{
	int fd = open(path, O_RDONLY), n = fd < 0 ? 0 : read(fd, buf, len - 1);

	buf[n > 0 ? n : 0] = 0;
	if (fd >= 0)
		close(fd);
}

static int move(pid_t pid, const char *cg)
{
	char path[128], v[32];

	snprintf(path, sizeof(path), "%s/cgroup.procs", cg);
	snprintf(v, sizeof(v), "%d\n", pid);
	return put(path, v);
}

static int iso;

static void show(const char *what, long long r0, long long p0)
{
	long long r = total_bw(0), p = total_bw(iso);

	printf("%-26s root %6.3f (%+.3f)   partition %6.3f (%+.3f)\n",
	       what, (double)r / BW_UNIT, (double)(r - r0) / BW_UNIT,
	       (double)p / BW_UNIT, (double)(p - p0) / BW_UNIT);
}

int main(void)
{
	pid_t pid, filler[MAXF];
	long long r0, p0;
	char buf[64], cpu[16];
	int rc, n, i, rt_runtime, rt_period;

	need_debugfs();
	/* Read now: reading these rebuilds the root domains (see
	 * recomputed_total_bw()). */
	get("/proc/sys/kernel/sched_rt_runtime_us", buf, sizeof(buf));
	rt_runtime = atoi(buf);
	get("/proc/sys/kernel/sched_rt_period_us", buf, sizeof(buf));
	rt_period = atoi(buf);
	iso = sysconf(_SC_NPROCESSORS_ONLN) - 1;
	if (iso < 1) {
		fprintf(stderr, "needs at least 2 CPUs\n");
		return 2;
	}
	if (access(CG "/cgroup.controllers", F_OK))
		mount("none", CG, "cgroup2", 0, NULL);
	put(CG "/cgroup.subtree_control", "+cpuset");
	mkdir(PART, 0755);
	snprintf(cpu, sizeof(cpu), "%d", iso);
	put(PART "/cpuset.cpus", cpu);
	put(PART "/cpuset.cpus.exclusive", cpu);
	put(PART "/cpuset.cpus.partition", "root");
	get(PART "/cpuset.cpus.partition", buf, sizeof(buf));
	if (strncmp(buf, "root", 4)) {
		fprintf(stderr, "could not make cpu%d a partition: %s", iso, buf);
		return 2;
	}

	pid = spawn_sleeper();
	rc = setattr(pid, SCHED_DEADLINE_, 0, RUNTIME, PERIOD, PERIOD);
	if (rc) {
		fprintf(stderr, "sched_setattr: %s\n", strerror(-rc));
		return 2;
	}
	r0 = total_bw(0);
	p0 = total_bw(iso);
	printf("cpu%d is a partition; sleeping DL task %d (0.5 CPU) in the root "
	       "cgroup\ntotal_bw in CPUs (change since start):\n", iso, pid);
	show("start:", r0, p0);
	rc = move(pid, PART);
	show(rc ? "move out FAILED:" : "moved into the partition:", r0, p0);
	rc = move(pid, CG);
	show(rc ? "move back FAILED:" : "moved back to the root:", r0, p0);
	printf("(expected: +0.000 and +0.000; the task is in state %c and has "
	       "not run)\n", task_state(pid));

	/* The root domain now has 0.5 CPU more "free" than it really has. */
	for (n = 0; n < MAXF; n++) {
		filler[n] = spawn_sleeper();
		if (setattr(filler[n], SCHED_DEADLINE_, 0, 10000000, 100000000,
			    100000000)) {
			reap(filler[n]);
			break;
		}
	}
	printf("root domain admits %d more 0.1-CPU tasks: %.3f + %d x 0.1 = "
	       "%.3f CPU\nreserved, limit %.3f CPU (%d CPUs x %d/%d)\n", n,
	       (double)r0 / BW_UNIT, n, (double)r0 / BW_UNIT + n * 0.1,
	       iso * (double)rt_runtime / rt_period, iso, rt_runtime,
	       rt_period);
	for (i = 0; i < n; i++)
		reap(filler[i]);
	show("those tasks exited:", r0, p0);

	reap(pid);
	show("the DL task exited:", r0, p0);
	try_fresh_admission(1000000, 100000000);
	try_fresh_admission(50000000, 100000000);
	r0 = recomputed_total_bw(0);	/* rebuild first, then read both */
	printf("after a root-domain rebuild (recomputed): root %.3f, "
	       "partition %.3f\n", (double)r0 / BW_UNIT,
	       (double)total_bw(iso) / BW_UNIT);

	/* Same stale rq: a SCHED_OTHER task moved into the partition while
	 * asleep cannot be made SCHED_DEADLINE before it has run. */
	pid = spawn_sleeper();
	rc = move(pid, PART);
	if (!rc)
		rc = setattr(pid, SCHED_DEADLINE_, 0, 1000000, 100000000,
			     100000000);
	printf("moved in while asleep, then SCHED_DEADLINE: %s\n",
	       rc ? strerror(-rc) : "accepted");
	reap(pid);

	put(PART "/cpuset.cpus.partition", "member");
	rmdir(PART);
	return 0;
}