[dev] Implement raw partition scanner (MBR+GPT)

Relying in udev has proven unsuitable time and time again.
Sometimes after switchroot, it loses information about partitions that
was already present in the initramfs. When an MBR partition contains a
filesystem that is larger than the partition, the udev info is missing
the MBR partition type from its output (observed with NTFS at least).
As the kernel doesn't expose the mbr type and gpt type GUID directly in
sysfs, we implement our own crude MBR and GPT parsers. In ash.

2 files changed, 137 insertions, 20 deletions

diff --git a/modules/dev.inc b/modules/dev.inc
index c2046d3..6080af6 100644
--- a/modules/dev.inc
+++ b/modules/dev.inc
@@ -8,42 +8,154 @@
 # The output will be a list of matching devices,
 # sorted from largest to smallest.
 dev_find_partitions() {
-	local ID dev exp target
-	exp=
+	local ID dev target
 	# target for the scan, defaults to /dev to check everything
-	if [ -b "$1" ]; then
+	if [ "${1:0:1}" = "/" ] && [ -b "$1" ]; then
 		target="$1"
 		shift
-	elif [ -d "$1" ]; then
+	elif [ "${1:0:1}" = "/" ] && [ -d "$1" ]; then
 		target="$1/"
+		shift
 	else
 		target="/dev/"
 	fi
+	local want_label="never match this#"
+	local want_type="never match this#"
+	local want_uuid="never match this#"
 	while [ "$#" -gt 0 ]; do
 		ID="$1"
 		shift
 		[ -z "$ID" ] && continue
-		# if single digit, e.g. 7, look for 0x7 and 0x07
 		if regex_imatch "$ID" "^[0-9a-f]$"; then
-			ID="0?$ID"
-		fi
-
-		if regex_imatch "$ID" "^[0-9a-f?]{2,3}$"; then # Match two digit and the expanded three digit version from above
-			# if double digit look for MBR types and OpenSLX-ID$ID GPT labels
-			exp="$exp|ID_PART_ENTRY_(NAME=OpenSLX-ID|TYPE=0x)$ID"
+			want_type="$want_type|0$ID"
+			want_label="$want_label|OpenSLX-ID0$ID"
+		elif regex_imatch "$ID" "^[0-9a-f]{2}$"; then
+			want_type="$want_type|$ID"
+			want_label="$want_label|OpenSLX-ID$ID"
 		elif regex_imatch "$ID" "^[0-9a-f]{8}-([0-9a-f]{4}-){3}[0-9a-f]{12}$"; then
-			# if UUID, look for TYPE
-			exp="$exp|ID_PART_ENTRY_TYPE=$ID"
-		else
-			# something else, look for names of partitions / filesystems
-			ID="$( regex_escape "$ID" )"
-			exp="$exp|ID_(PART_ENTRY_NAME|FS_LABEL)=$ID"
+			want_uuid="$want_uuid|$ID"
+		elif [ "${#ID}" -gt 3 ]; then # Safety measure: Want label length >= 4 chars
+			want_label="$want_label|$( regex_escape "$ID" )"
 		fi
 	done
-	exp="${exp:1}"
+	local label number mbrid uuid
 	for dev in $(find $target* -type b); do
-		udevadm info --name="$dev" | grep -iqE "($exp)\$" \
-			&& printf "%s\n" "$(blockdev --getsize64 "$dev") $dev"
+		dev_get_type "$dev"
+		if regex_imatch "$mbrid" "^($want_type)$" || regex_imatch "$uuid" "^($want_uuid)$" \
+				|| regex_match "$label" "^($want_label)$"; then
+			printf "%s\n" "$(blockdev --getsize64 "$dev") $dev"
+		fi
 	done | sort -n -k1 -r | cut -d' ' -f2
 }
 
+dev_get_type() {
+	local part dev partn devn pstart
+	dev=
+	mbrid=
+	uuid=
+	label=
+	number=
+	[ -b "$1" ] || return 1
+	part="$( readlink -f "$1" )"
+	partn="${part##*/}"
+	for devn in "${partn%p?}" "${partn%?}"; do
+		if [ "$dev" != "$part" ] && [ -f "/sys/block/${devn}/${partn}/uevent" ]; then
+			dev="/dev/${devn}"
+			break
+		fi
+	done
+	[ -z "$dev" ] && return 1
+	pstart="$( cat "/sys/block/${devn}/${partn}/start" )" # For validation
+	label="$( grep -Po '(?<=^PARTNAME=).*$' "/sys/block/${devn}/${partn}/uevent" )"
+	number="$( grep -Po '(?<=^PARTN=).*$' "/sys/block/${devn}/${partn}/uevent" )"
+	local gpt=
+	if [ "$( dd if="$dev" bs=1 count=8 skip=512 2> /dev/null )" = "EFI PART" ]; then
+		gpt=512
+	elif [ "$( dd if="$dev" bs=1 count=8 skip=4096 2> /dev/null )" = "EFI PART" ]; then
+		gpt=4096
+	fi
+	if [ -z "$label" ] && [ "$number" -lt 1000 ]  && [ "$number" -gt 0 ] \
+			&& [ "$( __read_mbrsig "$dev" 0 )" = "55aa" ]; then
+		# Get MBR ID
+		if [ "$number" -le 4 ]; then
+			# Primary
+			mbrid="$( __read_mbrid "$dev" 0 "$number" )"
+		else
+			# Scan for Primary type 05, scan linked list of fake MBRs from there
+			local no id ex_start log_id log_start next_id next_start current
+			for no in 1 2 3 4; do
+				id="$( __read_mbrid "$dev" 0 "$no" )"
+				echo "Scanning. Primary $no is type $id" >&2
+				[ "$id" = "05" ] && break
+			done
+			if [ "$id" != "05" ]; then
+				echo "No matching extended primary partition found" >&2
+				return 1
+			fi
+			ex_start="$( __read_mbrstart "$dev" 0 "$no" )"
+			current="$ex_start"
+			no=5 # Count through logical partitions
+			while [ "$no" != 0 ]; do
+				[ "$( __read_mbrsig "$dev" "$current" )" = "55aa" ] || break
+				log_id="$( __read_mbrid "$dev" "$current" 1 )"
+				if [ "$no" = "$number" ]; then
+					log_start="$( __read_mbrstart "$dev" "$current" 1 )"
+					log_start="$(( log_start + current ))"
+					if [ "$pstart" != "$log_start" ]; then
+						echo "Found partition $no, but start mismatch (want: $pstart found: $log_start)" >&2
+						return 1
+					fi
+					mbrid="$log_id"
+					break
+				fi
+				next_id="$( __read_mbrid "$dev" "$current" 2 )"
+				next_start="$( __read_mbrstart "$dev" "$current" 2 )"
+				echo "Extended id $log_id, next $next_id, $next_start" >&2
+				if [ "$next_id" = "05" ] && [ "$next_start" -gt 0 ]; then
+					current="$(( next_start + ex_start ))"
+					no="$(( no + 1 ))"
+				else
+					no=0
+				fi
+			done
+		fi
+		return 0
+	elif [ -n "$gpt" ]; then
+		# GPT
+		local table_start current entries no entry_size log_start
+		table_start="$( __read_le "$dev" "$(( gpt + 72 ))" 8 )"
+		entries="$( __read_le "$dev" "$(( gpt + 80 ))" 4 )"
+		entry_size="$( __read_le "$dev" "$(( gpt + 84 ))" 4 )"
+		current="$(( table_start * gpt ))"
+		if ! [ "$current" -ge "$(( gpt * 2 ))" ] || ! [ "$entries" -gt 0 ] \
+				|| [ "$entries" -lt "$number" ] || ! [ "$entry_size" -le 4096 ]; then
+			echo "Bad GPT table. Start: $current, Partition count: $entries. Want: $number" >&2
+			return 1
+		fi
+		log_start="$( __read_le "$dev" "$(( current + entry_size * (number - 1) + 32 ))" 8 )"
+		if [ "$log_start" != "$pstart" ]; then
+			echo "Found partition $number, but start mismatch (want: $pstart found: $log_start)" >&2
+			return 1
+		fi
+		uuid="$( dd if="$dev" bs=1 count=16 skip="$(( current + entry_size * (number - 1) ))" 2> /dev/null | xxd -p \
+			| sed -r 's/^(..)(..)(..)(..)(..)(..)(..)(..)(....)/\4\3\2\1-\6\5-\8\7-\9-/' )"
+		return 0
+	fi
+}
+
+__read_mbrid() {
+	dd if="$1" bs=1 skip=$(( 512 * $2 + 446 + ($3 - 1) * 16 + 4 )) count=1 2> /dev/null | xxd -p
+}
+
+__read_mbrstart() {
+	__read_le "$1" "$(( 512 * $2 + 446 + ($3 - 1) * 16 + 8 ))" 4
+}
+
+__read_mbrsig() {
+	dd if="$1" bs=1 skip=$(( 512 * $2 + 510 )) count=2 2> /dev/null | xxd -p
+}
+
+__read_le() {
+	local v="$( dd if="$1" bs=1 count="$3" skip="$2" 2> /dev/null | xxd -e -g "$3" | cut -d' ' -f2 )"
+	echo $(( 0x$v ))
+}
diff --git a/modules/regex.inc b/modules/regex.inc
index 21c3d65..3188b2d 100644
--- a/modules/regex.inc
+++ b/modules/regex.inc
@@ -1,5 +1,10 @@
 #!/bin/ash
 
+# Match $1 against perl regex $2, case sensitive
+regex_match() {
+	printf "%s" "$1" | grep -qP "$2"
+}
+
 # Match $1 against perl regex $2, case insensitive
 regex_imatch() {
 	printf "%s" "$1" | grep -qPi "$2"