path: root/kernel/cgroup/rstat.c

// SPDX-License-Identifier: GPL-2.0-only
#include "cgroup-internal.h"

#include <linux/sched/cputime.h>

#include <linux/bpf.h>
#include <linux/btf.h>
#include <linux/btf_ids.h>

#include <trace/events/cgroup.h>

static DEFINE_SPINLOCK(rstat_base_lock);
static DEFINE_PER_CPU(struct llist_head, rstat_backlog_list);

static void cgroup_base_stat_flush(struct cgroup *cgrp, int cpu);

/*
 * Determines whether a given css can participate in rstat.
 * css's that are cgroup::self use rstat for base stats.
 * Other css's associated with a subsystem use rstat only when
 * they define the ss->css_rstat_flush callback.
 */
static inline bool css_uses_rstat(struct cgroup_subsys_state *css)
{
	return css_is_self(css) || css->ss->css_rstat_flush != NULL;
}

static struct css_rstat_cpu *css_rstat_cpu(
		struct cgroup_subsys_state *css, int cpu)
{
	return per_cpu_ptr(css->rstat_cpu, cpu);
}

static struct cgroup_rstat_base_cpu *cgroup_rstat_base_cpu(
		struct cgroup *cgrp, int cpu)
{
	return per_cpu_ptr(cgrp->rstat_base_cpu, cpu);
}

static spinlock_t *ss_rstat_lock(struct cgroup_subsys *ss)
{
	if (ss)
		return &ss->rstat_ss_lock;

	return &rstat_base_lock;
}

static inline struct llist_head *ss_lhead_cpu(struct cgroup_subsys *ss, int cpu)
{
	if (ss)
		return per_cpu_ptr(ss->lhead, cpu);
	return per_cpu_ptr(&rstat_backlog_list, cpu);
}

/**
 * css_rstat_updated - keep track of updated rstat_cpu
 * @css: target cgroup subsystem state
 * @cpu: cpu on which rstat_cpu was updated
 *
 * Atomically inserts the css in the ss's llist for the given cpu. This is
 * reentrant safe i.e. safe against softirq, hardirq and nmi. The ss's llist
 * will be processed at the flush time to create the update tree.
 *
 * NOTE: if the user needs the guarantee that the updater either add itself in
 * the lockless list or the concurrent flusher flushes its updated stats, a
 * memory barrier is needed before the call to css_rstat_updated() i.e. a
 * barrier after updating the per-cpu stats and before calling
 * css_rstat_updated().
 */
__bpf_kfunc void css_rstat_updated(struct cgroup_subsys_state *css, int cpu)
{
	struct llist_head *lhead;
	struct css_rstat_cpu *rstatc;
	struct llist_node *self;

	/*
	 * Since bpf programs can call this function, prevent access to
	 * uninitialized rstat pointers.
	 */
	if (!css_uses_rstat(css))
		return;

	lockdep_assert_preemption_disabled();

	/*
	 * For archs withnot nmi safe cmpxchg or percpu ops support, ignore
	 * the requests from nmi context.
	 */
	if ((!IS_ENABLED(CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG) ||
	     !IS_ENABLED(CONFIG_ARCH_HAS_NMI_SAFE_THIS_CPU_OPS)) && in_nmi())
		return;

	rstatc = css_rstat_cpu(css, cpu);
	/*
	 * If already on list return. This check is racy and smp_mb() is needed
	 * to pair it with the smp_mb() in css_process_update_tree() if the
	 * guarantee that the updated stats are visible to concurrent flusher is
	 * needed.
	 */
	if (llist_on_list(&rstatc->lnode))
		return;

	/*
	 * This function can be renentered by irqs and nmis for the same cgroup
	 * and may try to insert the same per-cpu lnode into the llist. Note
	 * that llist_add() does not protect against such scenarios. In addition
	 * this same per-cpu lnode can be modified through init_llist_node()
	 * from css_rstat_flush() running on a different CPU.
	 *
	 * To protect against such stacked contexts of irqs/nmis, we use the
	 * fact that lnode points to itself when not on a list and then use
	 * try_cmpxchg() to atomically set to NULL to select the winner
	 * which will call llist_add(). The losers can assume the insertion is
	 * successful and the winner will eventually add the per-cpu lnode to
	 * the llist.
	 *
	 * Please note that we can not use this_cpu_cmpxchg() here as on some
	 * archs it is not safe against modifications from multiple CPUs.
	 */
	self = &rstatc->lnode;
	if (!try_cmpxchg(&rstatc->lnode.next, &self, NULL))
		return;

	lhead = ss_lhead_cpu(css->ss, cpu);
	llist_add(&rstatc->lnode, lhead);
}

static void __css_process_update_tree(struct cgroup_subsys_state *css, int cpu)
{
	/* put @css and all ancestors on the corresponding updated lists */
	while (true) {
		struct css_rstat_cpu *rstatc = css_rstat_cpu(css, cpu);
		struct cgroup_subsys_state *parent = css->parent;
		struct css_rstat_cpu *prstatc;

		/*
		 * Both additions and removals are bottom-up.  If a cgroup
		 * is already in the tree, all ancestors are.
		 */
		if (rstatc->updated_next)
			break;

		/* Root has no parent to link it to, but mark it busy */
		if (!parent) {
			rstatc->updated_next = css;
			break;
		}

		prstatc = css_rstat_cpu(parent, cpu);
		rstatc->updated_next = prstatc->updated_children;
		prstatc->updated_children = css;

		css = parent;
	}
}

static void css_process_update_tree(struct cgroup_subsys *ss, int cpu)
{
	struct llist_head *lhead = ss_lhead_cpu(ss, cpu);
	struct llist_node *lnode;

	while ((lnode = llist_del_first_init(lhead))) {
		struct css_rstat_cpu *rstatc;

		/*
		 * smp_mb() is needed here (more specifically in between
		 * init_llist_node() and per-cpu stats flushing) if the
		 * guarantee is required by a rstat user where etiher the
		 * updater should add itself on the lockless list or the
		 * flusher flush the stats updated by the updater who have
		 * observed that they are already on the list. The
		 * corresponding barrier pair for this one should be before
		 * css_rstat_updated() by the user.
		 *
		 * For now, there aren't any such user, so not adding the
		 * barrier here but if such a use-case arise, please add
		 * smp_mb() here.
		 */

		rstatc = container_of(lnode, struct css_rstat_cpu, lnode);
		__css_process_update_tree(rstatc->owner, cpu);
	}
}

/**
 * css_rstat_push_children - push children css's into the given list
 * @head: current head of the list (= subtree root)
 * @child: first child of the root
 * @cpu: target cpu
 * Return: A new singly linked list of css's to be flushed
 *
 * Iteratively traverse down the css_rstat_cpu updated tree level by
 * level and push all the parents first before their next level children
 * into a singly linked list via the rstat_flush_next pointer built from the
 * tail backward like "pushing" css's into a stack. The root is pushed by
 * the caller.
 */
static struct cgroup_subsys_state *css_rstat_push_children(
		struct cgroup_subsys_state *head,
		struct cgroup_subsys_state *child, int cpu)
{
	struct cgroup_subsys_state *cnext = child;	/* Next head of child css level */
	struct cgroup_subsys_state *ghead = NULL;	/* Head of grandchild css level */
	struct cgroup_subsys_state *parent, *grandchild;
	struct css_rstat_cpu *crstatc;

	child->rstat_flush_next = NULL;

	/*
	 * The subsystem rstat lock must be held for the whole duration from
	 * here as the rstat_flush_next list is being constructed to when
	 * it is consumed later in css_rstat_flush().
	 */
	lockdep_assert_held(ss_rstat_lock(head->ss));

	/*
	 * Notation: -> updated_next pointer
	 *	     => rstat_flush_next pointer
	 *
	 * Assuming the following sample updated_children lists:
	 *  P: C1 -> C2 -> P
	 *  C1: G11 -> G12 -> C1
	 *  C2: G21 -> G22 -> C2
	 *
	 * After 1st iteration:
	 *  head => C2 => C1 => NULL
	 *  ghead => G21 => G11 => NULL
	 *
	 * After 2nd iteration:
	 *  head => G12 => G11 => G22 => G21 => C2 => C1 => NULL
	 */
next_level:
	while (cnext) {
		child = cnext;
		cnext = child->rstat_flush_next;
		parent = child->parent;

		/* updated_next is parent cgroup terminated if !NULL */
		while (child != parent) {
			child->rstat_flush_next = head;
			head = child;
			crstatc = css_rstat_cpu(child, cpu);
			grandchild = crstatc->updated_children;
			if (grandchild != child) {
				/* Push the grand child to the next level */
				crstatc