1#! /bin/bash
2# SPDX-License-Identifier: GPL-2.0
3#
4# (c) 2019, Google
5progname="${0##*/}"
6
7USAGE="USAGE: ${progname} [dir]
8
9Call this when depmod breaks down, or when one needs a list of the symbols
10implicated in the circular dependency.
11
12Search current or dir directory for all kernel modules.  Itemize what they
13export, and what they import.  Discover links and report who fulfills them.
14Report any first order circular relationships and the symbols that got us
15into the situation.
16
17Standard output is of the form:
18
19module1.ko(symbols) -> module2.ko(symbols) -> module1.ko
20
21Leaves an annotated modules.dep file in the specified directory.
22
23TBA: higher order circular dependencies"
24
25if [ X"--help" = X"${1}" -o X"{-h}" = X"${1}" ]; then
26  echo "${USAGE}" >&2
27  exit
28fi
29DIR=.
30if [ 1 = ${#} ]; then
31  DIR=${1}
32  shift
33fi
34if [ 0 != ${#} ]; then
35  echo "Unexpected Argument: ${*}" >&2
36  echo >&2
37  echo "${USAGE}" >&2
38  exit 1
39fi
40
41# A _real_ embedded tab character
42TAB="`echo | tr '\n' '\t'`"
43
44#
45# Start Work
46#
47
48# Construct our version (symbols annoted as comments) of the modules.dep file.
49
50TMP=`mktemp -d`
51
52# Acquire a list of files that are modules
53find ${DIR%/} -name '*.ko' >${TMP}/modules
54
55# Fill symbols with file type symbol
56#  type is > for requires symbol
57#  type is < for supplies symbol
58#  type is pre for requires module (in symbol field)
59#  type is post for supplies module (in file field)
60
61# Mine for symbols
62xargs nm -o <${TMP}/modules |
63  sed "s@^${DIR%/}/@@" |
64  sed -n \
65      -e 's/^\([^:]*\):.* U \(.*\)/\1 > \2/p' \
66      -e 's/^\([^:]*\):.* [TD] \(.*\)/\1 < \2/p' >${TMP}/symbols
67if [ ! -s ${TMP}/symbols ]; then
68  rm -rf ${TMP}
69  echo ERROR: failed to find any .ko module files in the specified directory ${DIR%/}
70  exit 1
71fi
72
73# Mine for softdep pre
74  while read file; do
75    strings ${file} |
76      sed -n 's/^softdep=pre: \(.*\)/\1/p' |
77      tr ' ' '\n' |
78      sed "s@.*@${file#${DIR%/}/} pre &@"
79  done < ${TMP}/modules |
80  sort -u >>${TMP}/symbols
81
82# Mine for softdep post
83  while read file; do
84    strings ${file} |
85      sed -n 's/^softdep=post: \(.*\)/\1/p' |
86      tr ' ' '\n' |
87      sed "s@.*@$& post {file#${DIR%/}/}@"
88  done < ${TMP}/modules |
89  sort -u >>${TMP}/symbols
90
91# Translate symbols to annotated modules.dep
92(
93  sed -n 's/ > / /p' ${TMP}/symbols |
94    while read file symbol ; do
95      sed -n "s@^\(.*\) < ${symbol}\$@${file}: \1 # ${symbol}@p" ${TMP}/symbols
96    done
97  sed -n 's/ pre / /p' ${TMP}/symbols |
98    while read file softdep ; do
99      grep "/${softdep}[.]ko\$" ${TMP}/modules |
100        sed "s@^${DIR%/}/@@" |
101        while read source; do
102          echo "${file}: ${source} # pre:${softdep}"
103        done
104    done
105  sed -n 's/ post / /p' ${TMP}/symbols |
106    while read softdep source ; do
107      grep "/${softdep}[.]ko\$" ${TMP}/modules |
108        sed "s@^${DIR%/}/@@" |
109        while read file; do
110          echo "${file}: ${source} # post:${softdep}"
111        done
112    done
113) |
114  sort -u >${DIR%/}/modules.dep
115
116# Cleanup (already!)
117rm -rf ${TMP}
118
119# Evaluate first order dependencies from our annotated ${DIR}/modules.dep file.
120
121# squash adjacent lines with match for first symbols, merge second
122merge_second_symbols() {
123  sed ': loop
124       N
125       s/^\(.*(.*) -> .*(\)\(.*\)\().*\)\n\1\(.*\)\3/\1\2,\4\3/
126       t loop
127       h
128       s/\n.*//p
129       g
130       s/^[^\n]*\n//
131       t loop'
132}
133
134# squash adjacent lines with match for second symbols, merge first
135merge_first_symbols() {
136  sed ': loop
137       N
138       s/^\(.*(\)\(.*\)\() -> .*(.*).*\)\n\1\(.*\)\3/\1\2,\4\3/
139       t loop
140       h
141       s/\n.*//p
142       g
143       s/^[^\n]*\n//
144       t loop'
145}
146
147# squash adjacent lines with identical, but shifted one, circular dependencies
148merge_duplicates() {
149  sed ': loop
150       N
151       s/^\(.*\)\((.*)\) -> \(.*\)\((.*)\) -> \1\n\3\4 -> \1\2 -> \3$/\1\2 -> \3\4 -> \1/
152       t end
153       s/\n.*//p
154       g
155       s/^[^\n]*\n//
156       t loop
157       : end'
158}
159
160# Report the first order circular dependencies
161sed 's/://' ${DIR%/}/modules.dep |
162  while read file source comment symbol; do
163    sed -n "s@^${source}: ${file} # \(.*\)@${file}(${symbol}) -> ${source}(\1) -> ${file}@p" ${DIR%/}/modules.dep
164  done |
165  merge_second_symbols |
166  merge_first_symbols |
167  merge_duplicates |
168  sort -u
169
170# TBA: second order dependencies
171