[PATCH 1/2] make: parallelize tags generation

[Yury Norov <ynorov@nvidia.com>]

Generate per-directory tags in parallel with Exuberant or Universal Ctags.
A recursive make shares the caller's jobserver, allowing make -jN tags to
schedule directory jobs concurrently, then join them to get the traditional
tags file.

Allow compiled-source discovery to find no source references in a batch
of .cmd files, while still propagating grep errors.

The performance of the current vs parallel tags generation with

		time make -j8 ALLSOURCE_ARCHS=all tags

is:

         real         user          sys
Before:  4m40.797s    4m14.229s     0m39.341s
After:   1m39.203s    9m1.450s      2m7.552s

Assisted-by: OpenAI Codex
Signed-off-by: Yury Norov <ynorov@nvidia.com>
---
 Documentation/kbuild/kbuild.rst |   9 +++
 Makefile                        |   5 +-
 scripts/Makefile.tags           |   9 +++
 scripts/tags.sh                 | 137 +++++++++++++++++++++++++++++---
 4 files changed, 148 insertions(+), 12 deletions(-)
 create mode 100644 scripts/Makefile.tags

diff --git a/Documentation/kbuild/kbuild.rst b/Documentation/kbuild/kbuild.rst
index 5a9013bacfb7..61587adeedba 100644
--- a/Documentation/kbuild/kbuild.rst
+++ b/Documentation/kbuild/kbuild.rst
@@ -317,6 +317,15 @@ To get all available archs you can also specify all. E.g.::
 
     $ make ALLSOURCE_ARCHS=all tags
 
+With Exuberant or Universal Ctags, ``make -jN tags`` generates tags for
+directories in parallel and merges them into a single sorted ``tags`` file.
+The jobs share make's jobserver with other build targets. For example::
+
+    $ make -j8 ALLSOURCE_ARCHS=all tags
+
+Per-directory tag files are temporary and are removed after merging.
+Every invocation regenerates the complete tags file.
+
 IGNORE_DIRS
 -----------
 For tags/TAGS/cscope targets, you can choose which directories won't
diff --git a/Makefile b/Makefile
index 66654fa71655..6f3945fa3fc6 100644
--- a/Makefile
+++ b/Makefile
@@ -2260,7 +2260,10 @@ clean: $(clean-dirs)
 quiet_cmd_tags = GEN     $@
       cmd_tags = $(BASH) $(srctree)/scripts/tags.sh $@
 
-tags TAGS cscope gtags: FORCE
+tags: FORCE
+	+$(call cmd,tags)
+
+TAGS cscope gtags: FORCE
 	$(call cmd,tags)
 
 # Generate rust-project.json (a file that describes the structure of non-Cargo
diff --git a/scripts/Makefile.tags b/scripts/Makefile.tags
new file mode 100644
index 000000000000..d5967a3ac496
--- /dev/null
+++ b/scripts/Makefile.tags
@@ -0,0 +1,9 @@
+# SPDX-License-Identifier: GPL-2.0-only
+# Directory tag shards share the parent make's jobserver.
+
+.PHONY: tags
+tags: $(shell cat $(tags_tmp)/shards)
+	$(Q)$(BASH) $(srctree)/scripts/tags.sh tags-merge $(tags_tmp)
+
+%.tags: %.files
+	$(Q)$(BASH) $(srctree)/scripts/tags.sh tags-worker $@
diff --git a/scripts/tags.sh b/scripts/tags.sh
index 41e38df96984..b001e0f78d2f 100755
--- a/scripts/tags.sh
+++ b/scripts/tags.sh
@@ -121,8 +121,12 @@ all_compiled_sources()
 {
 	{
 		echo include/generated/autoconf.h
-		find $ignore -name "*.cmd" -exec \
-			grep -Poh '(?<=^  )\S+\.([chS]|rs)(?=\s)|(?<== )\S+\.(?1)(?=$)' {} \+ |
+		# A .cmd batch with no source references is not an error.
+		find $ignore -name "*.cmd" -exec sh -c '
+			pattern=$1
+			shift
+			grep -Poh "$pattern" "$@" || [ "$?" -eq 1 ]
+		' sh '(?<=^  )\S+\.([chS]|rs)(?=\s)|(?<== )\S+\.(?1)(?=$)' {} \+ |
 		awk '!a[$0]++'
 	} | xargs realpath -esq $([ -z "$KBUILD_ABS_SRCTREE" ] && echo --relative-to=.) |
 	sort -u
@@ -130,7 +134,9 @@ all_compiled_sources()
 
 all_target_sources()
 {
-	if [ -n "$COMPILED_SOURCE" ]; then
+	if [ -n "$tags_input" ]; then
+		sed -n 's/^s //p' "$tags_input.files"
+	elif [ -n "$COMPILED_SOURCE" ]; then
 		all_compiled_sources
 	else
 		all_sources
@@ -139,6 +145,10 @@ all_target_sources()
 
 all_kconfigs()
 {
+	if [ -n "$tags_input" ]; then
+		sed -n 's/^k //p' "$tags_input.files"
+		return
+	fi
 	find ${tree}arch/ -maxdepth 1 $ignore \
 	       -name "Kconfig*" -not -type l -print;
 	for arch in $ALLSOURCE_ARCHS; do
@@ -282,12 +292,24 @@ setup_regex()
 	done
 }
 
-exuberant()
+setup_ctags()
 {
 	CTAGS_EXTRA="extra"
 	if $1 --version 2>&1 | grep -iq universal; then
 	    CTAGS_EXTRA="extras"
 	fi
+	CTAGS_KCONFIG=n
+	if $1 --list-languages | grep -iq kconfig; then
+		CTAGS_KCONFIG=y
+	fi
+	export CTAGS_EXTRA CTAGS_KCONFIG
+}
+
+exuberant()
+{
+	if [ -z "$CTAGS_EXTRA" ]; then
+		setup_ctags "$1"
+	fi
 	setup_regex exuberant asm c
 	# identifiers to ignore by ctags
 	local ign=(
@@ -312,16 +334,75 @@ exuberant()
 		static
 	)
 	all_target_sources | \
-	xargs $1 -a -I "$(IFS=','; echo "${ign[*]}")" \
+	xargs -r $1 -a "${tags_flags[@]}" -I "$(IFS=','; echo "${ign[*]}")" \
 	--$CTAGS_EXTRA=+fq --c-kinds=+px --fields=+iaS --langmap=c:+.h \
-	"${regex[@]}"
+	"${regex[@]}" || return
 
 	KCONFIG_ARGS=()
-	if ! $1 --list-languages | grep -iq kconfig; then
+	if [ "$CTAGS_KCONFIG" != y ]; then
 		setup_regex exuberant kconfig
 		KCONFIG_ARGS=(--langdef=kconfig --language-force=kconfig "${regex[@]}")
 	fi
-	all_kconfigs | xargs $1 -a "${KCONFIG_ARGS[@]}"
+	all_kconfigs | xargs -r $1 -a "${tags_flags[@]}" "${KCONFIG_ARGS[@]}"
+}
+
+# Call in a subshell so error handling and cleanup stay local to the operation.
+setup_tags_tmp()
+{
+	set -eo pipefail
+	tmp=$(mktemp -d .tmp_tags.XXXXXX)
+	trap 'rm -rf "$tmp"' EXIT
+	trap 'exit 1' HUP INT TERM
+}
+
+# Let recursive make schedule directory shards using the caller's jobserver.
+parallel_tags()
+(
+	local tmp
+	setup_tags_tmp
+	# Workers inherit these capabilities instead of probing for each directory.
+	setup_ctags ${CTAGS:-ctags}
+
+	{
+		all_target_sources | sed 's/^/s /'
+		all_kconfigs | sed 's/^/k /'
+	} | LC_ALL=C sort -u | awk -v tmp="$tmp" '
+		{
+			dir = substr($0, 3)
+			if (!sub(/\/[^\/]*$/, "", dir))
+				dir = "."
+			if (!(dir in ids)) {
+				ids[dir] = ++n
+				print tmp "/" n ".tags"
+			}
+			out = tmp "/" ids[dir] ".files"
+			if (out != previous) {
+				if (previous != "")
+					close(previous)
+				previous = out
+			}
+			print >> out
+		}' > "$tmp/shards"
+	${MAKE:-make} -f "${tree}scripts/Makefile.tags" tags_tmp="$tmp"
+)
+
+merge_tags()
+(
+	local tmp
+	setup_tags_tmp
+
+	# Read filenames from stdin to avoid command-line length limits.
+	{
+		tr '\n' '\0' < "$1/shards"
+		# sort requires at least one input, even when there are no shards.
+		printf '/dev/null\0'
+	} | LC_ALL=C sort -m -u --files0-from=- | cut -f2- > "$tmp/merged"
+	mv "$tmp/merged" tags
+)
+
+remove_struct_forward_declarations()
+{
+	LC_ALL=C sed -e '/^\([a-zA-Z_][a-zA-Z0-9_]*\)\t.*\t\/\^struct \1;.*\$\/;"\tx$/d' "$@"
 }
 
 emacs()
@@ -366,11 +447,45 @@ case "$1" in
 		;;
 
 	"tags")
-		rm -f tags
-		xtags ${CTAGS:-ctags}
+		# Recursive recipes also run in dry-run, touch and question modes.
+		# Only normal invocations may generate intermediate files.
+		case ${MAKEFLAGS%% *} in
+		*n*) exit 0 ;;
+		*t*) touch tags; exit $? ;;
+		*q*) exit 1 ;;
+		esac
+		if ${CTAGS:-ctags} --version 2>&1 | grep -Eiq 'exuberant|universal'; then
+			parallel_tags
+			exit $?
+		else
+			rm -f tags
+			xtags ${CTAGS:-ctags}
+		fi
 		remove_structs=y
 		;;
 
+	"tags-worker")
+		tags_input=${2%.tags}
+		# Never expose an incomplete shard after an error or interruption.
+		setup_tags_tmp
+		tags_flags=(-f "$tmp/tags" --sort=no --tag-relative=no)
+		exuberant ${CTAGS:-ctags}
+		# Sort once per changed directory. Prefix records so the final merge
+		# keeps pseudo-tags ahead of all regular tag names.
+		remove_struct_forward_declarations "$tmp/tags" | awk '
+			{
+				sub(/^!_TAG_FILE_SORTED\t0\t/, "!_TAG_FILE_SORTED\t1\t")
+				print (/^!_TAG_/ ? "0\t" : "1\t") $0
+			}' | LC_ALL=C sort --parallel=1 -u > "$tmp/sorted"
+		mv "$tmp/sorted" "$2"
+		exit 0
+		;;
+
+	"tags-merge")
+		merge_tags "$2"
+		exit $?
+		;;
+
 	"TAGS")
 		rm -f TAGS
 		xtags etags
@@ -380,5 +495,5 @@ esac
 
 # Remove structure forward declarations.
 if [ -n "$remove_structs" ]; then
-    LC_ALL=C sed -i -e '/^\([a-zA-Z_][a-zA-Z0-9_]*\)\t.*\t\/\^struct \1;.*\$\/;"\tx$/d' $1
+	remove_struct_forward_declarations -i "$1"
 fi
-- 
2.53.0