sched_ext: Maintain an online cid mask in the scheduler arenagrafted

Schedulers on the default cid mapping treat [0, nr_online_cids) as the
online set and restart on hotplug. Schedulers that install their own mapping
with scx_bpf_cid_override() have no way to learn which cids are online: the
count no longer identifies members and the CPU-form cpumask is unusable from
cid programs. This is an obvious hole in the cid API.

Add scx_bpf_online_cmask(), a kernel-maintained cmask in the scheduler's
arena, allocated alongside the per-CPU scratch masks and populated after the
cid mapping is finalized and before ops.init(), for child schedulers too.
The pointer stays valid through ops.exit() with no reference to take. It is
the arena offset as a void pointer, the same form struct_ops arena arguments
arrive in. The verifier types the void return as a scalar for the program's
arena cast.

The mask follows the SCX hotplug notifications: seeded from cpu_active_mask
and updated before ops.cid_online/offline() runs, so it lags cpu_online_mask
only inside a hotplug transition. Updates walk the scheduler list under the
lock that also serializes unlinking. Reads are live, not atomic snapshots.
Root initialization excludes hotplug.

v2: Reworded the getter kerneldoc (Andrea Righi).

Signed-off-by: Tejun Heo <tj@kernel.org>
Reviewed-by: Andrea Righi <arighi@nvidia.com>

1 files changed, 361 insertions, 0 deletions

diff --git a/scripts/dtc/dtx_diff b/scripts/dtc/dtx_diff
new file mode 100755
index 000000000..f2bbde4bb
--- /dev/null
+++ b/scripts/dtc/dtx_diff
@@ -0,0 +1,361 @@
+#! /bin/bash
+# SPDX-License-Identifier: GPL-2.0-only
+
+# Copyright (C) 2015 Frank Rowand
+#
+
+
+usage() {
+
+	# use spaces instead of tabs in the usage message
+	cat >&2 <<eod
+
+Usage:
+
+   `basename $0` DTx
+        decompile DTx
+
+   `basename $0` DTx_1 DTx_2
+        diff DTx_1 and DTx_2
+
+
+      --annotate    synonym for -T
+      --color       synonym for -c (requires diff with --color support)
+       -c           enable colored output
+       -f           print full dts in diff (--unified=99999)
+       -h           synonym for --help
+       -help        synonym for --help
+      --help        print this message and exit
+       -s SRCTREE   linux kernel source tree is at path SRCTREE
+                        (default is current directory)
+       -S           linux kernel source tree is at root of current git repo
+       -T           annotate output .dts with input source file and line
+                        (-T -T for more details)
+       -u           unsorted, do not sort DTx
+
+
+Each DTx is processed by the dtc compiler to produce a sorted dts source
+file.  If DTx is a dts source file then it is pre-processed in the same
+manner as done for the compile of the dts source file in the Linux kernel
+build system ('#include' and '/include/' directives are processed).
+
+If two DTx are provided, the resulting dts source files are diffed.
+
+If DTx is a directory, it is treated as a DT subtree, such as
+  /proc/device-tree.
+
+If DTx contains the binary blob magic value in the first four bytes,
+  it is treated as a binary blob (aka .dtb or FDT).
+
+Otherwise DTx is treated as a dts source file (aka .dts).
+
+   If this script is not run from the root of the linux source tree,
+   and DTx utilizes '#include' or '/include/' then the path of the
+   linux source tree can be provided by '-s SRCTREE' or '-S' so that
+   include paths will be set properly.
+
+   The shell variable \${ARCH} must provide the architecture containing
+   the dts source file for include paths to be set properly for '#include'
+   or '/include/' to be processed.
+
+   If DTx_1 and DTx_2 are in different architectures, then this script
+   may not work since \${ARCH} is part of the include path.  The following
+   workaround can be used:
+
+      `basename $0` ARCH=arch_of_dtx_1 DTx_1 >tmp_dtx_1.dts
+      `basename $0` ARCH=arch_of_dtx_2 DTx_2 >tmp_dtx_2.dts
+      `basename $0` tmp_dtx_1.dts tmp_dtx_2.dts
+      rm tmp_dtx_1.dts tmp_dtx_2.dts
+
+   If DTx_1 and DTx_2 are in different directories, then this script will
+   add the path of DTx_1 and DTx_2 to the include paths.  If DTx_2 includes
+   a local file that exists in both the path of DTx_1 and DTx_2 then the
+   file in the path of DTx_1 will incorrectly be included.  Possible
+   workaround:
+
+      `basename $0` DTx_1 >tmp_dtx_1.dts
+      `basename $0` DTx_2 >tmp_dtx_2.dts
+      `basename $0` tmp_dtx_1.dts tmp_dtx_2.dts
+      rm tmp_dtx_1.dts tmp_dtx_2.dts
+
+eod
+}
+
+
+compile_to_dts() {
+
+	dtx="$1"
+	dtc_include="$2"
+
+	if [ -d "${dtx}" ] ; then
+
+		# -----  input is file tree
+
+		if ( ! ${DTC} -I fs ${dtx} ) ; then
+			exit 3
+		fi
+
+	elif [ -f "${dtx}" ] && [ -r "${dtx}" ] ; then
+
+		magic=`hexdump -n 4 -e '/1 "%02x"' ${dtx}`
+		if [ "${magic}" = "d00dfeed" ] ; then
+
+			# -----  input is FDT (binary blob)
+
+			if ( ! ${DTC} -I dtb ${dtx} ) ; then
+				exit 3
+			fi
+
+			return
+
+		fi
+
+		# -----  input is DTS (source)
+
+		if ( cpp ${cpp_flags} -x assembler-with-cpp ${dtx} \
+			| ${DTC} ${dtc_include} -I dts ) ; then
+			return
+		fi
+
+		echo ""                                                      >&2
+		echo "Possible hints to resolve the above error:"            >&2
+		echo "  (hints might not fix the problem)"                   >&2
+
+		hint_given=0
+
+		if [ "${ARCH}" = "" ] ; then
+			hint_given=1
+			echo ""                                              >&2
+			echo "  shell variable \$ARCH not set"               >&2
+		fi
+
+		dtx_arch=`echo "/${dtx}" | sed -e 's|.*/arch/||' -e 's|/.*||'`
+
+		if [ "${dtx_arch}" != ""  -a "${dtx_arch}" != "${ARCH}" ] ; then
+			hint_given=1
+			echo ""                                              >&2
+			echo "  architecture ${dtx_arch} is in file path,"   >&2
+			echo "  but does not match shell variable \$ARCH"    >&2
+			echo "  >>\$ARCH<< is: >>${ARCH}<<"                  >&2
+		fi
+
+		if [ ! -d ${srctree}/arch/${ARCH} ] ; then
+			hint_given=1
+			echo ""                                              >&2
+			echo "  ${srctree}/arch/${ARCH}/ does not exist"     >&2
+			echo "  Is \$ARCH='${ARCH}' correct?"                >&2
+			echo "  Possible fix: use '-s' option"               >&2
+
+			git_root=`git rev-parse --show-toplevel 2>/dev/null`
+			if [ -d ${git_root}/arch/ ] ; then
+				echo "  Possible fix: use '-S' option"       >&2
+			fi
+		fi
+
+		if [ $hint_given = 0 ] ; then
+			echo ""                                              >&2
+			echo "  No hints available."                         >&2
+		fi
+
+		echo ""                                                      >&2
+
+		exit 3
+
+	else
+		echo ""                                                     >&2
+		echo "ERROR: ${dtx} does not exist or is not readable"      >&2
+		echo ""                                                     >&2
+		exit 2
+	fi
+
+}
+
+
+# -----  start of script
+
+annotate=""
+cmd_diff=0
+diff_flags="-u"
+diff_color=""
+dtx_file_1=""
+dtx_file_2=""
+dtc_sort="-s"
+help=0
+srctree=""
+
+
+while [ $# -gt 0 ] ; do
+
+	case $1 in
+
+	-c | --color )
+		if diff --color /dev/null /dev/null 2>/dev/null ; then
+			diff_color="--color=always"
+		fi
+		shift
+		;;
+
+	-f )
+		diff_flags="--unified=999999"
+		shift
+		;;
+
+	-h | -help | --help )
+		help=1
+		shift
+		;;
+
+	-s )
+		srctree="$2"
+		shift 2
+		;;
+
+	-S )
+		git_root=`git rev-parse --show-toplevel 2>/dev/null`
+		srctree="${git_root}"
+		shift
+		;;
+
+	-T | --annotate )
+		if [ "${annotate}"  = "" ] ; then
+			annotate="-T"
+		elif [ "${annotate}"  = "-T" ] ; then
+			annotate="-T -T"
+		fi
+		shift
+		;;
+	-u )
+		dtc_sort=""
+		shift
+		;;
+
+	*)
+		if [ "${dtx_file_1}"  = "" ] ; then
+			dtx_file_1="$1"
+		elif [ "${dtx_file_2}" = "" ] ; then
+			dtx_file_2="$1"
+		else
+			echo ""                                             >&2
+			echo "ERROR: Unexpected parameter: $1"              >&2
+			echo ""                                             >&2
+			exit 2
+		fi
+		shift
+		;;
+
+	esac
+
+done
+
+if [ "${srctree}" = "" ] ; then
+	srctree="."
+fi
+
+if [ "${dtx_file_2}" != "" ]; then
+	cmd_diff=1
+fi
+
+if (( ${help} )) ; then
+	usage
+	exit 1
+fi
+
+# this must follow check for ${help}
+if [ "${dtx_file_1}" = "" ]; then
+	echo ""                                                             >&2
+	echo "ERROR: parameter DTx required"                                >&2
+	echo ""                                                             >&2
+	exit 2
+fi
+
+
+# -----  prefer dtc from linux kernel, allow fallback to dtc in $PATH
+
+if [ "${KBUILD_OUTPUT:0:2}" = ".." ] ; then
+	__KBUILD_OUTPUT="${srctree}/${KBUILD_OUTPUT}"
+elif [ "${KBUILD_OUTPUT}" = "" ] ; then
+	__KBUILD_OUTPUT="."
+else
+	__KBUILD_OUTPUT="${KBUILD_OUTPUT}"
+fi
+
+DTC="${__KBUILD_OUTPUT}/scripts/dtc/dtc"
+
+if [ ! -x ${DTC} ] ; then
+	__DTC="dtc"
+	if grep -q "^CONFIG_DTC=y" ${__KBUILD_OUTPUT}/.config 2>/dev/null; then
+		make_command='
+         make scripts'
+	else
+		make_command='
+         Enable CONFIG_DTC in the kernel configuration
+         make scripts'
+	fi
+	if ( ! which ${__DTC} >/dev/null ) ; then
+
+		# use spaces instead of tabs in the error message
+		cat >&2 <<eod
+
+ERROR: unable to find a 'dtc' program
+
+   Preferred 'dtc' (built from Linux kernel source tree) was not found or
+   is not executable.
+
+      'dtc' is: ${DTC}
+
+      If it does not exist, create it from the root of the Linux source tree:
+${make_command}
+
+      If not at the root of the Linux kernel source tree -s SRCTREE or -S
+      may need to be specified to find 'dtc'.
+
+      If 'O=\${dir}' is specified in your Linux builds, this script requires
+      'export KBUILD_OUTPUT=\${dir}' or add \${dir}/scripts/dtc to \$PATH
+      before running.
+
+      If \${KBUILD_OUTPUT} is a relative path, then '-s SRCDIR', -S, or run
+      this script from the root of the Linux kernel source tree is required.
+
+   Fallback '${__DTC}' was also not in \${PATH} or is not executable.
+
+eod
+		exit 2
+	fi
+	DTC=${__DTC}
+fi
+
+
+# -----  cpp and dtc flags same as for linux source tree build of .dtb files,
+#        plus directories of the dtx file(s)
+
+dtx_path_1_dtc_include="-i `dirname ${dtx_file_1}`"
+
+dtx_path_2_dtc_include=""
+if (( ${cmd_diff} )) ; then
+	dtx_path_2_dtc_include="-i `dirname ${dtx_file_2}`"
+fi
+
+cpp_flags="\
+	-nostdinc                                  \
+	-I${srctree}/scripts/dtc/include-prefixes  \
+	-undef -D__DTS__"
+
+DTC="\
+	${DTC}                                     \
+	-i ${srctree}/scripts/dtc/include-prefixes \
+	-O dts -qq -f ${dtc_sort} ${annotate} -o -"
+
+
+# -----  do the diff or decompile
+
+if (( ${cmd_diff} )) ; then
+
+	diff ${diff_flags} ${diff_color} --label "${dtx_file_1}" --label "${dtx_file_2}" \
+		<(compile_to_dts "${dtx_file_1}" "${dtx_path_1_dtc_include}") \
+		<(compile_to_dts "${dtx_file_2}" "${dtx_path_2_dtc_include}")
+
+else
+
+	compile_to_dts "${dtx_file_1}" "${dtx_path_1_dtc_include}"
+
+fi