Bug#284294: mkinitrd module detection using hotplug algorithm

[Erik van Konijnenburg <ekonijn@xs4all.nl>]

Package:	initrd-tools
Version:	0.1.74
Severity:	wishlist

Hi,

This is a proposal to improve mkinitrd by reusing code from the hotplug
project to determine which modules are needed on the initrd image to
support block devices.

It is an alternative to an earlier proposal to make devices in sysfs
point to the module that implements their driver.  It improves on the
original proposal in the following ways:
- no kernel changes required, so will work with older 2.6 kernels
- can cope with differences between modules in running kernel and
  new kernel; as an example, it understands that a USB stick in 2.6.8
  needs usb-storage, but in 2.6.9 will need the ub module.

The original proposal and the problems motivating it are discussed in:
- http://marc.theaimsgroup.com/?l=linux-scsi&m=109570145108639&w=2
- http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=263169

The method is simple: mkinitrd runs under an old kernel on some hardware,
and it needs to find the minimal set of modules needed to boot a new
kernel on that hardware.  Sysfs describes the hardware, complete with
device identifiers, and a module map provided with the new kernel
describes which modules are needed to operate a particular piece of
hardware.  Finally, modules.dep shows which support modules must be loaded
before a module can be loaded.

Hotplug uses this same information to load modules for a new device into
a running kernel.  In fact hotplug and mkinitrd are two sides of the same
coin: hotplug finds modules for available hardware given a running kernel,
and mkinitrd finds modules for some kernel given available hardware.

So I copied the module table processing from hotplug and adapted it to
use tables from a different kernel.  After that, it's only a matter of
identifying which hardware devices are used to implement block devices;
essentially that's just /sys/block/*/device/.  One little twist: if you're
using for example a USB stick, you need not only the USB driver, but also
the PCI driver for the bus that the USB host is attached to.  The pathname
of the device in /sys/devices identifies all such parent devices.

The attached script implements this method, and seems to give more or less
correct answers on a machine with SATA drive (although I wonder about
the location of ide0 in sysfs):

	konijn@framboos:/dat/tmp$ uname -r
	2.6.8-1-686
	konijn@framboos:/dat/tmp$ sh joke4
	=============== /sys/block/hda
	devno 3:0 at: /sys/devices/ide0/0.0
	needs:
	=============== /sys/block/sda
	devno 8:0 at: /sys/devices/pci0000:00/0000:00:1f.2/host0/0:0:0:0
	needs: ata_piix
	=============== /sys/block/sdb
	devno 8:16 at: /sys/devices/pci0000:00/0000:00:1d.7/usb5/5-4/5-4.3/5-4.3:1.0/host7/7:0:0:0
	needs: ehci-hcd usbcore usbcore usb-storage
	recommended module load order:
		/lib/modules/2.6.8-1-686/kernel/drivers/scsi/libata.ko
		/lib/modules/2.6.8-1-686/kernel/drivers/scsi/scsi_mod.ko
		/lib/modules/2.6.8-1-686/kernel/drivers/scsi/ata_piix.ko
		/lib/modules/2.6.8-1-686/kernel/drivers/usb/core/usbcore.ko
		/lib/modules/2.6.8-1-686/kernel/drivers/usb/host/ehci-hcd.ko
		/lib/modules/2.6.8-1-686/kernel/drivers/ide/ide-core.ko
		/lib/modules/2.6.8-1-686/kernel/drivers/usb/storage/usb-storage.ko
	konijn@framboos:/dat/tmp$ sh joke4 2.6.10-rc2-e
	=============== /sys/block/hda
	devno 3:0 at: /sys/devices/ide0/0.0
	needs:
	=============== /sys/block/sda
	devno 8:0 at: /sys/devices/pci0000:00/0000:00:1f.2/host0/0:0:0:0
	needs: ata_piix
	=============== /sys/block/sdb
	devno 8:16 at: /sys/devices/pci0000:00/0000:00:1d.7/usb5/5-4/5-4.3/5-4.3:1.0/host7/7:0:0:0
	needs: ehci-hcd usbcore usbcore ub
	recommended module load order:
		/lib/modules/2.6.10-rc2-e/kernel/drivers/scsi/libata.ko
		/lib/modules/2.6.10-rc2-e/kernel/drivers/scsi/scsi_mod.ko
		/lib/modules/2.6.10-rc2-e/kernel/drivers/scsi/ata_piix.ko
		/lib/modules/2.6.10-rc2-e/kernel/drivers/usb/core/usbcore.ko
		/lib/modules/2.6.10-rc2-e/kernel/drivers/usb/host/ehci-hcd.ko
		/lib/modules/2.6.10-rc2-e/kernel/drivers/block/ub.ko
	konijn@framboos:/dat/tmp$


I'm looking for comments: could this approach be made to work, and if so
what would be the best way to go about moving from this proof of concept
to something that could be used as part of a complete mkinitrd?

Regards,
Erik


#
# Given a kernel version (default the running kernel)
# print an ordered minimal list of all files that must
# be loaded into that kernel in order for all block
# devices to be operational.
#
# A large part of this script is copied from the hotplug package,
# http://linux-hotplug.sourceforge.net/
#
# This software may be used and distributed according to the terms
# of the GNU General Public License, incorporated herein by reference.
#
#


#
# Each modules.usbmap format line corresponds to one entry in a
# MODULE_DEVICE_TABLE(usb,...) declaration in a kernel file.
#
# Think of it as a database column with up to three "match specs"
# to associate kernel modules with particular devices or classes
# of device.  The match specs provide a reasonably good filtering
# mechanism, but some driver probe() routines need to provide
# extra filtering.
#
usb_convert_vars ()
{
    # work around 2.2.early brokenness
    # munges the usb_bcdDevice such that it is a integer rather
    # than a float: e.g. 1.0 become 0100
    DEFAULT_IFS="$IFS"
    PRODUCT=`echo $PRODUCT | sed -e "s+\.\([0-9]\)$+.\10+" -e "s/\.$/00/" \
                                  -e "s+/\([0-9]\)\.\([0-9][0-9]\)+/0\1\2+" \
			  -e "s+/\([0-9][0-9]\)\.\([0-9][0-9]\)+/\1\2+"`
    set $(echo $PRODUCT | sed -e 's+\([^/]*\)/\([^/]*\)/\(.*\)+\1 \2 \3+')
    usb_idVendor=$((0x$1))
    usb_idProduct=$((0x$2))
    usb_bcdDevice=$((0x$3))

    if [ "$TYPE" != "" ]; then
    	IFS=/
    	set $TYPE ''
	usb_bDeviceClass=$1
        usb_bDeviceSubClass=$2
        usb_bDeviceProtocol=$3
	IFS="$DEFAULT_IFS"
    elif [ -r $SYSFS/$DEVPATH/bDeviceClass ]; then
	usb_bDeviceClass=$((0x$(cat $SYSFS/$DEVPATH/bDeviceClass)))
	usb_bDeviceSubClass=$((0x$(cat $SYSFS/$DEVPATH/bDeviceSubClass)))
	usb_bDeviceProtocol=$((0x$(cat $SYSFS/$DEVPATH/bDeviceProtocol)))
    else
	# out-of-range values
	usb_bDeviceClass=1000
	usb_bDeviceSubClass=1000
	usb_bDeviceProtocol=1000
    fi

    if [ "$INTERFACE" != "" ]; then
	IFS=/
	set $INTERFACE ''
	usb_bInterfaceClass=$1
	usb_bInterfaceSubClass=$2
    	usb_bInterfaceProtocol=$3
	IFS="$DEFAULT_IFS"
    elif [ -r $SYSFS/$DEVPATH/bInterfaceClass ]; then
	usb_bInterfaceClass=$((0x$(cat $SYSFS/$DEVPATH/bInterfaceClass)))
	usb_bInterfaceSubClass=$((0x$(cat $SYSFS/$DEVPATH/bInterfaceSubClass)))
	usb_bInterfaceProtocol=$((0x$(cat $SYSFS/$DEVPATH/bInterfaceProtocol)))
    else
	# out-of-range values
	usb_bInterfaceClass=1000
	usb_bInterfaceSubClass=1000
	usb_bInterfaceProtocol=1000
    fi
}

USB_MATCH_VENDOR=$((0x0001))
USB_MATCH_PRODUCT=$((0x0002))
USB_MATCH_DEV_LO=$((0x0004))
USB_MATCH_DEV_HI=$((0x0008))
USB_MATCH_DEV_CLASS=$((0x0010))
USB_MATCH_DEV_SUBCLASS=$((0x0020))
USB_MATCH_DEV_PROTOCOL=$((0x0040))
USB_MATCH_INT_CLASS=$((0x0080))
USB_MATCH_INT_SUBCLASS=$((0x0100))
USB_MATCH_INT_PROTOCOL=$((0x0200))

#
# stdin is "modules.usbmap" syntax
# on return, all matching modules have been added to $DRIVERS
#
usb_map_modules ()
{
    local line module

    # look at each usb_device_id entry
    # collect all matches in $DRIVERS

    while read line
    do
        # comments are lines that start with "#" ...
	# be careful, they still get parsed by bash!
	case "$line" in
	\#*) continue ;;
	"")  continue ;;
	esac

	set $line

	module=$1
	match_flags=$(($2))

	idVendor=$(($3))
	idProduct=$(($4))
	bcdDevice_lo=$(($5))
	bcdDevice_hi=$(($6))

	bDeviceClass=$(($7))
	bDeviceSubClass=$(($8))
	bDeviceProtocol=$(($9))

	shift 9
	bInterfaceClass=$(($1))
	bInterfaceSubClass=$(($2))
	bInterfaceProtocol=$(($3))

	: checkmatch $module

	: idVendor $idVendor $usb_idVendor
        if [ $USB_MATCH_VENDOR -eq $(( $match_flags & $USB_MATCH_VENDOR )) ] && 
	   [ $idVendor -ne $usb_idVendor ]; then
	    continue
	fi

	: idProduct $idProduct $usb_idProduct
	if [ $USB_MATCH_PRODUCT -eq $(( $match_flags & $USB_MATCH_PRODUCT )) ] &&
	   [ $idProduct -ne $usb_idProduct ]; then
	    continue
	fi

	: bcdDevice range $bcdDevice_hi $bcdDevice_lo actual $usb_bcdDevice
	if [ $USB_MATCH_DEV_LO -eq $(( $match_flags & $USB_MATCH_DEV_LO )) ] &&
	   [ $usb_bcdDevice -lt $bcdDevice_lo ]; then
	    continue
	fi

	# bcdDevice_lo <= bcdDevice <= bcdDevice_hi
	if [ $USB_MATCH_DEV_HI -eq $(( $match_flags & $USB_MATCH_DEV_HI )) ] &&
	   [ $usb_bcdDevice -gt $bcdDevice_hi ]; then
	    continue
	fi

	: bDeviceClass $bDeviceClass $usb_bDeviceClass
	if [ $USB_MATCH_DEV_CLASS -eq $(( $match_flags & $USB_MATCH_DEV_CLASS )) ] &&
	   [ $bDeviceClass -ne $usb_bDeviceClass ]; then
	    continue
	fi
	: bDeviceSubClass $bDeviceSubClass $usb_bDeviceSubClass
	if [ $USB_MATCH_DEV_SUBCLASS -eq $(( $match_flags & $USB_MATCH_DEV_SUBCLASS )) ] &&
	   [ $bDeviceSubClass -ne $usb_bDeviceSubClass ]; then
	    continue
	fi
	: bDeviceProtocol $bDeviceProtocol $usb_bDeviceProtocol
	if [ $USB_MATCH_DEV_PROTOCOL -eq $(( $match_flags & $USB_MATCH_DEV_PROTOCOL )) ] &&
	   [ $bDeviceProtocol -ne $usb_bDeviceProtocol ]; then
	    continue
	fi

	# NOTE:  for now, this only checks the first of perhaps
	# several interfaces for this device.

	: bInterfaceClass $bInterfaceClass $usb_bInterfaceClass
	if [ $USB_MATCH_INT_CLASS -eq $(( $match_flags & $USB_MATCH_INT_CLASS )) ] &&
	   [ $bInterfaceClass -ne $usb_bInterfaceClass ]; then
	    continue
	fi
	: bInterfaceSubClass $bInterfaceSubClass $usb_bInterfaceSubClass
	if [ $USB_MATCH_INT_SUBCLASS -eq $(( $match_flags & $USB_MATCH_INT_SUBCLASS )) ] &&
	   [ $bInterfaceSubClass -ne $usb_bInterfaceSubClass ]; then
	    continue
	fi
	: bInterfaceProtocol $bInterfaceProtocol $usb_bInterfaceProtocol
	if [ $USB_MATCH_INT_PROTOCOL -eq $(( $match_flags & $USB_MATCH_INT_PROTOCOL )) ] &&
	   [ $bInterfaceProtocol -ne $usb_bInterfaceProtocol ]; then
	    continue
	fi

	# It was a match!
	DRIVERS="$module $DRIVERS"
	: drivers $DRIVERS
    done
}



#
# Given path to USB device, add any required modules
# to $DRIVERS, based on modules.usbmap
#
usb_device() {
    PRODUCT=0/0/0
    TYPE=
    INTERFACE=
    DEVPATH=
    DEVICE=
    export ACTION PRODUCT TYPE INTERFACE DEVPATH DEVICE
    DEVPATH=$1
    DEVPATH=${1#$SYSFS}

    usb_convert_vars
    usb_map_modules < $MAP_USB
}

#
# Given path to USB interface, add any required modules
# to $DRIVERS, based on modules.usbmap
#
usb_interface() {
    PRODUCT=0/0/0
    TYPE=
    INTERFACE=
    DEVPATH=
    DEVICE=
    export ACTION PRODUCT TYPE INTERFACE DEVPATH DEVICE

    DEVPATH=$1
    dir=$DEVPATH/.. # XXX I don't know why this is needed, but it works
    PRODUCT="$(cat $dir/idVendor)/$(cat $dir/idProduct)/$(cat $dir/bcdDevice)"
    # echo "++++++++ $PRODUCT"
    DEVPATH=${DEVPATH#$SYSFS}

    usb_convert_vars
    usb_map_modules < $MAP_USB
}

#
# Each modules.usbmap format line corresponds to one entry in a
# MODULE_DEVICE_TABLE(pci,...) declaration in a kernel file.
#
# Think of it as a database column with up to three "match specs"
# to associate kernel modules with particular devices or classes
# of device.  The match specs provide a reasonably good filtering
# mechanism, but some driver probe() routines need to provide
# extra filtering.
#

pci_convert_vars ()
{
    pci_class=$((0x$PCI_CLASS))

    set $(echo $PCI_ID | sed -e 's/\([^:]*\):\(.*\)/\1 \2/')
    pci_id_vendor=$((0x$1))
    pci_id_device=$((0x$2))

    set $(echo $PCI_SUBSYS_ID | sed -e 's/\([^:]*\):\(.*\)/\1 \2/')
    pci_subid_vendor=$((0x$1))
    pci_subid_device=$((0x$2))
}

PCI_ANY=$((0xffffffff))


#
# stdin is "modules.pcimap" syntax
# on return, ONE matching module was added to $DRIVERS
#
pci_map_modules ()
{
    local module ignored

    # comment line lists (current) pci_device_id field names
    read ignored

    # look at each pci_device_id entry
    # collect one match in $DRIVERS
    while read module vendor device subvendor subdevice class class_mask ignored
    do
	# comments are lines that start with "#" ...
	# be careful, they still get parsed by bash!
	case "$module" in
	\#*) continue ;;
	esac

	# convert the fields from hex to dec
	vendor=$(($vendor)); device=$(($device))
	subvendor=$(($subvendor)); subdevice=$(($subdevice))
	class=$(($class)); class_mask=$(($class_mask))

	: checkmatch $module

	: vendor $vendor $pci_id_vendor
	if [ $vendor -ne $PCI_ANY -a $vendor -ne $pci_id_vendor ]; then
	    continue
	fi
	: device $device $pci_id_device
	if [ $device -ne $PCI_ANY -a $device -ne $pci_id_device ]; then
	    continue
	fi
	: sub-vendor $subvendor $pci_subid_vendor
	if [ $subvendor -ne $PCI_ANY -a $subvendor -ne $pci_subid_vendor ]; then
	    continue
	fi
	: sub-device $subdevice $pci_subid_device
	if [ $subdevice -ne $PCI_ANY -a $subdevice -ne $pci_subid_device ]; then
	    continue
	fi

	class_temp=$(($pci_class & $class_mask))
	if [ $class_temp -eq $class ]; then
	    DRIVERS="$module $DRIVERS"
	    : drivers $DRIVERS
	fi
    done
}


#
# Given path to PCI device, add any required modules
# to $DRIVERS, based on modules.pcimap
#
pci_device() {
    ACTION=add
    PCI_CLASS=0
    PCI_ID=0:0
    PCI_SLOT_NAME=0:0.0
    PCI_SUBSYS_ID=0:0
    export ACTION PCI_CLASS PCI_ID PCI_SLOT_NAME PCI_SUBSYS_ID

    PCI_DEVICE=$1
    set `echo $PCI_DEVICE \
	| sed -e 's/\([^:]*\):\(.*\):\(.*\)\.\(.*\)/\1 \2 \3 \4/'`
    PCI_SLOT_NAME=$2:$3.$4
    PCI_CLASS="`cat $PCI_DEVICE/class`"
    PCI_CLASS=${PCI_CLASS#0x}
    vendor_id=`cat $PCI_DEVICE/vendor`
    device_id=`cat $PCI_DEVICE/device`
    PCI_ID="${vendor_id#0x}:${device_id#0x}"
    sub_vendor_id=`cat $PCI_DEVICE/subsystem_vendor`
    sub_device_id=`cat $PCI_DEVICE/subsystem_device`
    PCI_SUBSYS_ID="${sub_vendor_id#0x}:${sub_device_id#0x}"

    pci_convert_vars
    pci_map_modules < $MAP_PCI
}

#
# Given path to a device, determine all devices that
# connect it to the core.  For each device, determine
# the type (PCI, USB); add directly required modules
# to $ALL_DRIVERS.  Ignores possible support modules.
#
phys_device() {
    path=$1
    DRIVERS=""
    while [ "$path" != '/' ]
    do
	# echo "in $path"
	if [ -f "$path/subsystem_vendor" ]
	then
	    # echo "PCI device: $path"
	    pci_device $path
	fi
	if [ -f "$path/bDeviceClass" ]
	then
	    # echo "USB device: $path"
	    usb_device $path
	fi
	if [ -f "$path/bInterfaceClass" ]
	then
	    # echo "USB interface: $path"
	    usb_interface $path
	fi
	path=`dirname $path`
    done
    echo "needs: $DRIVERS"
    ALL_DRIVERS="$ALL_DRIVERS $DRIVERS"
}

#
# Iterate over all block devices,
# return a list of required drivers in $ALL_DRIVERS.
# A block device may require multiple drivers,
# eg when an USB stick is only reachable via an USB controller on a PCI bus.
# Duplicates possible
#
block_devs() {
    ALL_DRIVERS=""
    for blockdev in $SYSFS/block/*
    do
	if [ -e $blockdev/device ]
	then
	    device=`readlink -f $blockdev/device`
	    # ignore partitions for now;
	    # this is a nice place to filter for root and swap.
	    devno=$(cat $blockdev/dev)
	    echo =============== $blockdev
	    echo "devno $devno at: $device"
	    phys_device $device
	fi
    done
}

#
# Given a list of modules, make $ALL_FILES a list of files
# containing those modules.
#
find_files() {
    ALL_FILES=""
    for DRIVER in $*
    do
    	FILE=$(find $MODULE_DIR/kernel/drivers -name "$DRIVER.ko" -print)
	ALL_FILES="$ALL_FILES $FILE"
    done
}


#
# Given a filename, make $PRE_REQ a list of all files that must
# be loaded into the kernel before the file can be loaded
# succesfully.
#
find_dep() {
	FILE=$1
	while read KEY REST
	do
		if [ "$KEY" = "$FILE:" ]
		then
			# echo ++++++++++ BINGO: $REST
			PRE_REQ="$REST"
			break
		fi
	done < $MODULE_DIR/modules.dep
}

#
# Given a list of filenames, add before each file X a list
# of all files that need to be loaded before X; return
# list in $THE_WORKS.
#
find_dependencies() {
	THE_WORKS=""
	for FILE in $*
	do
		find_dep $FILE
		THE_WORKS="$THE_WORKS $PRE_REQ $FILE"
	done
}

#
# Given a list of filenames, make a list where only
# the first occurence of each element is present;
# return in $THE_ESSENTIALS.
#
prune() {
	THE_ESSENTIALS=""
	for FILE in $*
	do
		BASE=`basename $FILE`
		BASE=${BASE%.ko}
		BASE=$(echo $BASE | sed -e 's/-/_/')
		eval "SEEN=\$SEEN_$BASE"
		if [ "$SEEN" = "" ]
		then
			THE_ESSENTIALS="$THE_ESSENTIALS $FILE"
		fi
		eval "SEEN_$BASE=1"
	done
}


main() {

    if [ "$1" != "" ]
    then
    	VERSION="$1"
    else
	VERSION=`uname -r`
    fi

    SYSFS=/sys
    MODULE_DIR=/lib/modules/$VERSION
    MAP_USB=$MODULE_DIR/modules.usbmap
    MAP_PCI=$MODULE_DIR/modules.pcimap

    block_devs
    find_files $ALL_DRIVERS
    find_dependencies $ALL_FILES
    prune $THE_WORKS
    echo "recommended module load order:"
    for f in $THE_ESSENTIALS
    do
    	echo "	$f"
    done

}


main $*