common/populate

##/bin/bash
# SPDX-License-Identifier: GPL-2.0+
# Copyright (c) 2015 Oracle.  All Rights Reserved.
#
# Routines for populating a scratch fs, and helpers to exercise an FS
# once it's been fuzzed.

. ./common/quota

_require_populate_commands() {
	_require_xfs_io_command "falloc"
	_require_xfs_io_command "fpunch"
	_require_test_program "punch-alternating"
	_require_command "$XFS_DB_PROG" "xfs_db"
}

_require_xfs_db_blocktrash_z_command() {
	test "${FSTYP}" = "xfs" || _notrun "cannot run xfs_db on ${FSTYP}"
	$XFS_DB_PROG -x -f -c 'blocktrash -z' "${TEST_DEV}" | grep -q 'nothing on stack' || _notrun "blocktrash -z not supported"
}

# Attempt to make files of "every" format for data, dirs, attrs etc.
# (with apologies to Eric Sandeen for mutating xfser.sh)

# Create a file of a given size.
__populate_create_file() {
	local sz="$1"
	local fname="$2"

	$XFS_IO_PROG -f -c "pwrite -S 0x62 -W -b 1m 0 $sz" "${fname}"
}

# Punch out every other hole in this file, if it exists.
#
# The goal here is to force the creation of a large number of metadata records
# by creating a lot of tiny extent mappings in a file.  Callers should ensure
# that fragmenting the file actually causes record creation.  Call this
# function /after/ creating all other metadata structures.
__populate_fragment_file() {
	local fname="$1"

	test -f "${fname}" && $here/src/punch-alternating "${fname}"
}

# Create a large directory
__populate_create_dir() {
	name="$1"
	nr="$2"
	missing="$3"

	mkdir -p "${name}"
	seq 0 "${nr}" | while read d; do
		creat=mkdir
		test "$((d % 20))" -eq 0 && creat=touch
		$creat "${name}/$(printf "%.08d" "$d")"
	done

	test -z "${missing}" && return
	seq 1 2 "${nr}" | while read d; do
		rm -rf "${name}/$(printf "%.08d" "$d")"
	done
}

# Add a bunch of attrs to a file
__populate_create_attr() {
	name="$1"
	nr="$2"
	missing="$3"

	touch "${name}"
	seq 0 "${nr}" | while read d; do
		setfattr -n "user.$(printf "%.08d" "$d")" -v "$(printf "%.08d" "$d")" "${name}"
	done

	test -z "${missing}" && return
	seq 1 2 "${nr}" | while read d; do
		setfattr -x "user.$(printf "%.08d" "$d")" "${name}"
	done
}

# Fill up some percentage of the remaining free space
__populate_fill_fs() {
	dir="$1"
	pct="$2"
	test -z "${pct}" && pct=60

	mkdir -p "${dir}/test/1"
	cp -pRdu "${dir}"/S_IFREG* "${dir}/test/1/"

	SRC_SZ="$(du -ks "${dir}/test/1" | cut -f 1)"
	FS_SZ="$(( $(stat -f "${dir}" -c '%a * %S') / 1024 ))"

	NR="$(( (FS_SZ * ${pct} / 100) / SRC_SZ ))"

	echo "FILL FS"
	echo "src_sz $SRC_SZ fs_sz $FS_SZ nr $NR"
	seq 2 "${NR}" | while read nr; do
		cp -pRdu "${dir}/test/1" "${dir}/test/${nr}"
	done
}

# For XFS, force on all the quota options if quota is enabled
# and the user didn't feed us noquota.
_populate_xfs_qmount_option()
{
	# User explicitly told us not to quota
	if echo "${MOUNT_OPTIONS}" | grep -q 'noquota'; then
		return
	fi

	# Don't bother if we can't turn on quotas
	if [ ! -f /proc/fs/xfs/xqmstat ]; then
		# No quota support
		return
	elif [ "${USE_EXTERNAL}" = "yes" ] && [ ! -z "${SCRATCH_RTDEV}" ]; then
		# Quotas not supported on rt filesystems
		return
	elif [ -z "${XFS_QUOTA_PROG}" ]; then
		# xfs quota tools not installed
		return
	fi

	# Turn on all the quotas
	if $XFS_INFO_PROG "${TEST_DIR}" | grep -q 'crc=1'; then
		# v5 filesystems can have group & project quotas
		quota="usrquota,grpquota,prjquota"
	else
		# v4 filesystems cannot mix group & project quotas
		quota="usrquota,grpquota"
	fi

	# Inject our quota mount options
	if echo "${MOUNT_OPTIONS}" | grep -q "${quota}"; then
		return
	elif echo "${MOUNT_OPTIONS}" | egrep -q '(quota|noenforce)'; then
		_qmount_option "${quota}"
	else
		export MOUNT_OPTIONS="$MOUNT_OPTIONS -o ${quota}"
		echo "MOUNT_OPTIONS = $MOUNT_OPTIONS" >>$seqres.full
	fi
}

# Populate an XFS on the scratch device with (we hope) all known
# types of metadata block
_scratch_xfs_populate() {
	fill=1

	for arg in $@; do
		case "${arg}" in
		"nofill")
			fill=0;;
		esac
	done

	_populate_xfs_qmount_option
	_scratch_mount

	# We cannot directly force the filesystem to create the metadata
	# structures we want; we can only achieve this indirectly by carefully
	# crafting files and a directory tree.  Therefore, we must have exact
	# control over the layout and device selection of all files created.
	# Clear the rtinherit flag on the root directory so that files are
	# always created on the data volume regardless of MKFS_OPTIONS.  We can
	# set the realtime flag when needed.
	_xfs_force_bdev data $SCRATCH_MNT

	blksz="$(stat -f -c '%s' "${SCRATCH_MNT}")"
	dblksz="$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep naming.*bsize | sed -e 's/^.*bsize=//g' -e 's/\([0-9]*\).*$/\1/g')"
	crc="$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep crc= | sed -e 's/^.*crc=//g' -e 's/\([0-9]*\).*$/\1/g')"
	if [ $crc -eq 1 ]; then
		leaf_hdr_size=64
	else
		leaf_hdr_size=16
	fi
	leaf_lblk="$((32 * 1073741824 / blksz))"
	node_lblk="$((64 * 1073741824 / blksz))"

	# Data:

	# Fill up the root inode chunk
	echo "+ fill root ino chunk"
	seq 1 64 | while read f; do
		$XFS_IO_PROG -f -c "truncate 0" "${SCRATCH_MNT}/dummy${f}"
	done

	# Regular files
	# - FMT_EXTENTS
	echo "+ extents file"
	__populate_create_file $blksz "${SCRATCH_MNT}/S_IFREG.FMT_EXTENTS"

	# - FMT_BTREE
	echo "+ btree extents file"
	nr="$((blksz * 2 / 16))"
	__populate_create_file $((blksz * nr)) "${SCRATCH_MNT}/S_IFREG.FMT_BTREE"

	# Directories
	# - INLINE
	echo "+ inline dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_INLINE" 1

	# - BLOCK
	echo "+ block dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_BLOCK" "$((dblksz / 40))"

	# - LEAF
	echo "+ leaf dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_LEAF" "$((dblksz / 12))"

	# - LEAFN
	echo "+ leafn dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_LEAFN" "$(( ((dblksz - leaf_hdr_size) / 8) - 3 ))"

	# - NODE
	echo "+ node dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_NODE" "$((16 * dblksz / 40))" true

	# - BTREE
	echo "+ btree dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_BTREE" "$((128 * dblksz / 40))" true

	# Symlinks
	# - FMT_LOCAL
	echo "+ inline symlink"
	ln -s target "${SCRATCH_MNT}/S_IFLNK.FMT_LOCAL"

	# - FMT_EXTENTS
	echo "+ extents symlink"
	ln -s "$(perl -e 'print "x" x 1023;')" "${SCRATCH_MNT}/S_IFLNK.FMT_EXTENTS"

	# Char & block
	echo "+ special"
	mknod "${SCRATCH_MNT}/S_IFCHR" c 1 1
	mknod "${SCRATCH_MNT}/S_IFBLK" b 1 1
	mknod "${SCRATCH_MNT}/S_IFIFO" p

	# special file with an xattr
	setfacl -P -m u:nobody:r ${SCRATCH_MNT}/S_IFCHR

	# Attribute formats
	# LOCAL
	echo "+ local attr"
	__populate_create_attr "${SCRATCH_MNT}/ATTR.FMT_LOCAL" 1

	# LEAF
	echo "+ leaf attr"
	__populate_create_attr "${SCRATCH_MNT}/ATTR.FMT_LEAF" "$((blksz / 40))"

	# NODE
	echo "+ node attr"
	__populate_create_attr "${SCRATCH_MNT}/ATTR.FMT_NODE" "$((8 * blksz / 40))"

	# BTREE
	echo "+ btree attr"
	__populate_create_attr "${SCRATCH_MNT}/ATTR.FMT_BTREE" "$((64 * blksz / 40))" true

	# trusted namespace
	touch ${SCRATCH_MNT}/ATTR.TRUSTED
	setfattr -n trusted.moo -v urk ${SCRATCH_MNT}/ATTR.TRUSTED

	# security namespace
	touch ${SCRATCH_MNT}/ATTR.SECURITY
	setfattr -n security.foo -v bar ${SCRATCH_MNT}/ATTR.SECURITY

	# system namespace
	touch ${SCRATCH_MNT}/ATTR.SYSTEM
	setfacl -m u:root:r ${SCRATCH_MNT}/ATTR.SYSTEM

	# FMT_EXTENTS with a remote less-than-a-block value
	echo "+ attr extents with a remote less-than-a-block value"
	touch "${SCRATCH_MNT}/ATTR.FMT_EXTENTS_REMOTE3K"
	$XFS_IO_PROG -f -c "pwrite -S 0x43 0 $((blksz - 300))" "${SCRATCH_MNT}/attrvalfile" > /dev/null
	attr -q -s user.remotebtreeattrname "${SCRATCH_MNT}/ATTR.FMT_EXTENTS_REMOTE3K" < "${SCRATCH_MNT}/attrvalfile"

	# FMT_EXTENTS with a remote block-size value
	echo "+ attr extents with a remote one-block value"
	touch "${SCRATCH_MNT}/ATTR.FMT_EXTENTS_REMOTE4K"
	$XFS_IO_PROG -f -c "pwrite -S 0x44 0 ${blksz}" "${SCRATCH_MNT}/attrvalfile" > /dev/null
	attr -q -s user.remotebtreeattrname "${SCRATCH_MNT}/ATTR.FMT_EXTENTS_REMOTE4K" < "${SCRATCH_MNT}/attrvalfile"
	rm -rf "${SCRATCH_MNT}/attrvalfile"

	# Make an unused inode
	echo "+ empty file"
	touch "${SCRATCH_MNT}/unused"
	$XFS_IO_PROG -f -c 'fsync' "${SCRATCH_MNT}/unused"
	rm -rf "${SCRATCH_MNT}/unused"

	# Free space btree
	echo "+ freesp btree"
	nr="$((blksz * 2 / 8))"
	__populate_create_file $((blksz * nr)) "${SCRATCH_MNT}/BNOBT"

	# Inode btree
	echo "+ inobt btree"
	local ino_per_rec=64
	local rec_per_btblock=16
	local nr="$(( 2 * (blksz / rec_per_btblock) * ino_per_rec ))"
	local dir="${SCRATCH_MNT}/INOBT"
	mkdir -p "${dir}"
	seq 0 "${nr}" | while read f; do
		touch "${dir}/${f}"
	done

	seq 0 2 "${nr}" | while read f; do
		rm -f "${dir}/${f}"
	done

	# Reverse-mapping btree
	is_rmapbt="$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep -c 'rmapbt=1')"
	if [ $is_rmapbt -gt 0 ]; then
		echo "+ rmapbt btree"
		nr="$((blksz * 2 / 24))"
		__populate_create_file $((blksz * nr)) "${SCRATCH_MNT}/RMAPBT"
	fi

	# Realtime Reverse-mapping btree
	is_rt="$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep -c 'rtextents=[1-9]')"
	if [ $is_rmapbt -gt 0 ] && [ $is_rt -gt 0 ]; then
		echo "+ rtrmapbt btree"
		nr="$((blksz * 2 / 32))"
		$XFS_IO_PROG -R -f -c 'truncate 0' "${SCRATCH_MNT}/RTRMAPBT"
		__populate_create_file $((blksz * nr)) "${SCRATCH_MNT}/RTRMAPBT"
	fi

	# Reference-count btree
	is_reflink="$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep -c 'reflink=1')"
	if [ $is_reflink -gt 0 ]; then
		echo "+ reflink btree"
		nr="$((blksz * 2 / 12))"
		__populate_create_file $((blksz * nr)) "${SCRATCH_MNT}/REFCOUNTBT"
		cp --reflink=always "${SCRATCH_MNT}/REFCOUNTBT" "${SCRATCH_MNT}/REFCOUNTBT2"
	fi

	# Copy some real files (xfs tests, I guess...)
	echo "+ real files"
	test $fill -ne 0 && __populate_fill_fs "${SCRATCH_MNT}" 5

	# Make sure we get all the fragmentation we asked for
	__populate_fragment_file "${SCRATCH_MNT}/S_IFREG.FMT_BTREE"
	__populate_fragment_file "${SCRATCH_MNT}/BNOBT"
	__populate_fragment_file "${SCRATCH_MNT}/RMAPBT"
	__populate_fragment_file "${SCRATCH_MNT}/RTRMAPBT"
	__populate_fragment_file "${SCRATCH_MNT}/REFCOUNTBT"

	umount "${SCRATCH_MNT}"
}

# Populate an ext4 on the scratch device with (we hope) all known
# types of metadata block
_scratch_ext4_populate() {
	fill=1

	for arg in $@; do
		case "${arg}" in
		"nofill")
			fill=0;;
		esac
	done

	_scratch_mount
	blksz="$(stat -f -c '%s' "${SCRATCH_MNT}")"
	dblksz="${blksz}"
	leaf_lblk="$((32 * 1073741824 / blksz))"
	node_lblk="$((64 * 1073741824 / blksz))"

	# Data:

	# Regular files
	# - FMT_INLINE
	echo "+ inline file"
	__populate_create_file 1 "${SCRATCH_MNT}/S_IFREG.FMT_INLINE"

	# - FMT_EXTENTS
	echo "+ extents file"
	__populate_create_file $blksz "${SCRATCH_MNT}/S_IFREG.FMT_EXTENTS"

	# - FMT_ETREE
	echo "+ extent tree file"
	nr="$((blksz * 2 / 12))"
	__populate_create_file $((blksz * nr)) "${SCRATCH_MNT}/S_IFREG.FMT_ETREE"

	# Directories
	# - INLINE
	echo "+ inline dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_INLINE" 1

	# - BLOCK
	echo "+ block dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_BLOCK" "$((dblksz / 32))"

	# - HTREE
	echo "+ htree dir"
	__populate_create_dir "${SCRATCH_MNT}/S_IFDIR.FMT_HTREE" "$((4 * dblksz / 24))"

	# Symlinks
	# - FMT_LOCAL
	echo "+ inline symlink"
	ln -s target "${SCRATCH_MNT}/S_IFLNK.FMT_LOCAL"

	# - FMT_EXTENTS
	echo "+ extents symlink"
	ln -s "$(perl -e 'print "x" x 1023;')" "${SCRATCH_MNT}/S_IFLNK.FMT_EXTENTS"

	# Char & block
	echo "+ special"
	mknod "${SCRATCH_MNT}/S_IFCHR" c 1 1
	mknod "${SCRATCH_MNT}/S_IFBLK" b 1 1
	mknod "${SCRATCH_MNT}/S_IFIFO" p

	# special file with an xattr
	setfacl -P -m u:nobody:r ${SCRATCH_MNT}/S_IFCHR

	# Attribute formats
	# LOCAL
	echo "+ local attr"
	__populate_create_attr "${SCRATCH_MNT}/ATTR.FMT_LOCAL" 0

	# BLOCK
	echo "+ block attr"
	__populate_create_attr "${SCRATCH_MNT}/ATTR.FMT_BLOCK" "$((blksz / 40))"

	# trusted namespace
	touch ${SCRATCH_MNT}/ATTR.TRUSTED
	setfattr -n trusted.moo -v urk ${SCRATCH_MNT}/ATTR.TRUSTED

	# security namespace
	touch ${SCRATCH_MNT}/ATTR.SECURITY
	setfattr -n security.foo -v bar ${SCRATCH_MNT}/ATTR.SECURITY

	# system namespace
	touch ${SCRATCH_MNT}/ATTR.SYSTEM
	setfacl -m u:root:r ${SCRATCH_MNT}/ATTR.SYSTEM

	# Make an unused inode
	echo "+ empty file"
	touch "${SCRATCH_MNT}/unused"
	$XFS_IO_PROG -f -c 'fsync' "${SCRATCH_MNT}/unused"
	rm -rf "${SCRATCH_MNT}/unused"

	# Copy some real files (xfs tests, I guess...)
	echo "+ real files"
	test $fill -ne 0 && __populate_fill_fs "${SCRATCH_MNT}" 5

	# Make sure we get all the fragmentation we asked for
	__populate_fragment_file "${SCRATCH_MNT}/S_IFREG.FMT_ETREE"

	umount "${SCRATCH_MNT}"
}

# Find the inode number of a file
__populate_find_inode() {
	name="$1"
	inode="$(stat -c '%i' "${name}")"
	echo "${inode}"
}

# Check data fork format of XFS file
__populate_check_xfs_dformat() {
	inode="$1"
	format="$2"

	fmt="$(_scratch_xfs_db -c "inode ${inode}" -c 'p core.format' | sed -e 's/^.*(\([a-z]*\)).*$/\1/g')"
	test "${format}" = "${fmt}" || _fail "failed to create ino ${inode} dformat expected ${format} saw ${fmt}"
}

# Check attr fork format of XFS file
__populate_check_xfs_aformat() {
	inode="$1"
	format="$2"

	fmt="$(_scratch_xfs_db -c "inode ${inode}" -c 'p core.aformat' | sed -e 's/^.*(\([a-z]*\)).*$/\1/g')"
	test "${format}" = "${fmt}" || _fail "failed to create ino ${inode} aformat expected ${format} saw ${fmt}"
}

# Check structure of XFS directory
__populate_check_xfs_dir() {
	inode="$1"
	dtype="$2"

	(test -n "${leaf_lblk}" && test -n "${node_lblk}") || _fail "must define leaf_lblk and node_lblk before calling __populate_check_xfs_dir"
	datab=0
	leafb=0
	freeb=0
	#echo "== check dir ${inode} type ${dtype}" ; _scratch_xfs_db -x -c "inode ${inode}" -c "bmap"
	_scratch_xfs_db -x -c "inode ${inode}" -c "dblock 0" -c "stack" | grep -q 'file data block is unmapped' || datab=1
	_scratch_xfs_db -x -c "inode ${inode}" -c "dblock ${leaf_lblk}" -c "stack" | grep -q 'file data block is unmapped' || leafb=1
	_scratch_xfs_db -x -c "inode ${inode}" -c "dblock ${node_lblk}" -c "stack" | grep -q 'file data block is unmapped' || freeb=1

	case "${dtype}" in
	"shortform"|"inline"|"local")
		(test "${datab}" -eq 0 && test "${leafb}" -eq 0 && test "${freeb}" -eq 0) || _fail "failed to create ${dtype} dir ino ${inode} datab ${datab} leafb ${leafb} freeb ${freeb}"
		;;
	"block")
		(test "${datab}" -eq 1 && test "${leafb}" -eq 0 && test "${freeb}" -eq 0) || _fail "failed to create ${dtype} dir ino ${inode} datab ${datab} leafb ${leafb} freeb ${freeb}"
		;;
	"leaf")
		(test "${datab}" -eq 1 && test "${leafb}" -eq 1 && test "${freeb}" -eq 0) || _fail "failed to create ${dtype} dir ino ${inode} datab ${datab} leafb ${leafb} freeb ${freeb}"
		;;
	"leafn")
		_scratch_xfs_db -x -c "inode ${inode}" -c "dblock ${leaf_lblk}" -c "p lhdr.info.hdr.magic" | grep -q '0x3dff' && return
		_scratch_xfs_db -x -c "inode ${inode}" -c "dblock ${leaf_lblk}" -c "p lhdr.info.magic" | grep -q '0xd2ff' && return
		_fail "failed to create ${dtype} dir ino ${inode} datab ${datab} leafb ${leafb} freeb ${freeb}"
		;;
	"node"|"btree")
		(test "${datab}" -eq 1 && test "${leafb}" -eq 1 && test "${freeb}" -eq 1) || _fail "failed to create ${dtype} dir ino ${inode} datab ${datab} leafb ${leafb} freeb ${freeb}"
		;;
	*)
		_fail "Unknown directory type ${dtype}"
	esac
}

# Check structure of XFS attr
__populate_check_xfs_attr() {
	inode="$1"
	atype="$2"

	datab=0
	leafb=0
	#echo "== check attr ${inode} type ${dtype}" ; _scratch_xfs_db -x -c "inode ${inode}" -c "bmap -a"
	_scratch_xfs_db -x -c "inode ${inode}" -c "ablock 0" -c "stack" | grep -q 'file attr block is unmapped' || datab=1
	_scratch_xfs_db -x -c "inode ${inode}" -c "ablock 1" -c "stack" | grep -q 'file attr block is unmapped' || leafb=1

	case "${atype}" in
	"shortform"|"inline"|"local")
		(test "${datab}" -eq 0 && test "${leafb}" -eq 0) || _fail "failed to create ${atype} attr ino ${inode} datab ${datab} leafb ${leafb}"
		;;
	"leaf")
		(test "${datab}" -eq 1 && test "${leafb}" -eq 0) || _fail "failed to create ${atype} attr ino ${inode} datab ${datab} leafb ${leafb}"
		;;
	"node"|"btree")
		(test "${datab}" -eq 1 && test "${leafb}" -eq 1) || _fail "failed to create ${atype} attr ino ${inode} datab ${datab} leafb ${leafb}"
		;;
	*)
		_fail "Unknown attribute type ${atype}"
	esac
}

# Check that there's at least one per-AG btree with multiple levels
__populate_check_xfs_agbtree_height() {
	bt_type="$1"
	nr_ags=$(_scratch_xfs_db -c 'sb 0' -c 'p agcount' | awk '{print $3}')

	case "${bt_type}" in
	"bno"|"cnt"|"rmap"|"refcnt")
		hdr="agf"
		bt_prefix="${bt_type}"
		;;
	"ino")
		hdr="agi"
		bt_prefix=""
		;;
	"fino")
		hdr="agi"
		bt_prefix="free_"
		;;
	*)
		_fail "Don't know about AG btree ${bt_type}"
		;;
	esac

	seq 0 $((nr_ags - 1)) | while read ag; do
		bt_level=$(_scratch_xfs_db -c "${hdr} ${ag}" -c "p ${bt_prefix}level" | awk '{print $3}')
		if [ "${bt_level}" -gt 1 ]; then
			return 100
		fi
	done
	test $? -eq 100 || _fail "Failed to create ${bt_type} of sufficient height!"
	return 1
}

# Check that populate created all the types of files we wanted
_scratch_xfs_populate_check() {
	_scratch_mount
	extents_file="$(__populate_find_inode "${SCRATCH_MNT}/S_IFREG.FMT_EXTENTS")"
	btree_file="$(__populate_find_inode "${SCRATCH_MNT}/S_IFREG.FMT_BTREE")"
	inline_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_INLINE")"
	block_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_BLOCK")"
	leaf_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_LEAF")"
	leafn_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_LEAFN")"
	node_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_NODE")"
	btree_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_BTREE")"
	local_slink="$(__populate_find_inode "${SCRATCH_MNT}/S_IFLNK.FMT_LOCAL")"
	extents_slink="$(__populate_find_inode "${SCRATCH_MNT}/S_IFLNK.FMT_EXTENTS")"
	bdev="$(__populate_find_inode "${SCRATCH_MNT}/S_IFBLK")"
	cdev="$(__populate_find_inode "${SCRATCH_MNT}/S_IFCHR")"
	fifo="$(__populate_find_inode "${SCRATCH_MNT}/S_IFIFO")"
	local_attr="$(__populate_find_inode "${SCRATCH_MNT}/ATTR.FMT_LOCAL")"
	leaf_attr="$(__populate_find_inode "${SCRATCH_MNT}/ATTR.FMT_LEAF")"
	node_attr="$(__populate_find_inode "${SCRATCH_MNT}/ATTR.FMT_NODE")"
	btree_attr="$(__populate_find_inode "${SCRATCH_MNT}/ATTR.FMT_BTREE")"
	is_finobt=$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep -c 'finobt=1')
	is_rmapbt=$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep -c 'rmapbt=1')
	is_reflink=$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep -c 'reflink=1')

	blksz="$(stat -f -c '%s' "${SCRATCH_MNT}")"
	dblksz="$($XFS_INFO_PROG "${SCRATCH_MNT}" | grep naming.*bsize | sed -e 's/^.*bsize=//g' -e 's/\([0-9]*\).*$/\1/g')"
	leaf_lblk="$((32 * 1073741824 / blksz))"
	node_lblk="$((64 * 1073741824 / blksz))"
	umount "${SCRATCH_MNT}"

	__populate_check_xfs_dformat "${extents_file}" "extents"
	__populate_check_xfs_dformat "${btree_file}" "btree"
	__populate_check_xfs_dir "${inline_dir}" "inline"
	__populate_check_xfs_dir "${block_dir}" "block"
	__populate_check_xfs_dir "${leaf_dir}" "leaf"
	__populate_check_xfs_dir "${leafn_dir}" "leafn"
	__populate_check_xfs_dir "${node_dir}" "node"
	__populate_check_xfs_dir "${btree_dir}" "btree"
	__populate_check_xfs_dformat "${btree_dir}" "btree"
	__populate_check_xfs_dformat "${bdev}" "dev"
	__populate_check_xfs_dformat "${cdev}" "dev"
	__populate_check_xfs_dformat "${fifo}" "dev"
	__populate_check_xfs_attr "${local_attr}" "local"
	__populate_check_xfs_attr "${leaf_attr}" "leaf"
	__populate_check_xfs_attr "${node_attr}" "node"
	__populate_check_xfs_attr "${btree_attr}" "btree"
	__populate_check_xfs_aformat "${btree_attr}" "btree"
	__populate_check_xfs_agbtree_height "bno"
	__populate_check_xfs_agbtree_height "cnt"
	__populate_check_xfs_agbtree_height "ino"
	test $is_finobt -ne 0 && __populate_check_xfs_agbtree_height "fino"
	test $is_rmapbt -ne 0 && __populate_check_xfs_agbtree_height "rmap"
	test $is_reflink -ne 0 && __populate_check_xfs_agbtree_height "refcnt"
}

# Check data fork format of ext4 file
__populate_check_ext4_dformat() {
	dev="${SCRATCH_DEV}"
	inode="$1"
	format="$2"

	extents=0
	etree=0
	debugfs -R "stat <${inode}>" "${dev}" 2> /dev/null | grep 'ETB[0-9]' -q && etree=1
	iflags="$(debugfs -R "stat <${inode}>" "${dev}" 2> /dev/null | grep 'Flags:' | sed -e 's/^.*Flags: \([0-9a-fx]*\).*$/\1/g')"
	test "$(echo "${iflags}" | awk '{print and(strtonum($1), 0x80000);}')" -gt 0 && extents=1

	case "${format}" in
	"blockmap")
		test "${extents}" -eq 0 || _fail "failed to create ino ${inode} with blockmap"
		;;
	"extent"|"extents")
		test "${extents}" -eq 1 || _fail "failed to create ino ${inode} with extents"
		;;
	"etree")
		(test "${extents}" -eq 1 && test "${etree}" -eq 1) || _fail "failed to create ino ${inode} with extent tree"
		;;
	*)
		_fail "Unknown dformat ${format}"
	esac
}

# Check attr fork format of ext4 file
__populate_check_ext4_aformat() {
	dev="${SCRATCH_DEV}"
	inode="$1"
	format="$2"

	ablock=1
	debugfs -R "stat <${inode}>" "${dev}" 2> /dev/null | grep 'File ACL: 0' -q && ablock=0

	case "${format}" in
	"local"|"inline")
		test "${ablock}" -eq 0 || _fail "failed to create inode ${inode} with ${format} xattr"
		;;
	"block")
		test "${extents}" -eq 1 || _fail "failed to create inode ${inode} with ${format} xattr"
		;;
	*)
		_fail "Unknown aformat ${format}"
	esac
}

# Check structure of ext4 dir
__populate_check_ext4_dir() {
	dev="${SCRATCH_DEV}"
	inode="$1"
	dtype="$2"

	htree=0
	inline=0
	iflags="$(debugfs -R "stat <${inode}>" "${dev}" 2> /dev/null | grep 'Flags:' | sed -e 's/^.*Flags: \([0-9a-fx]*\).*$/\1/g')"
	test "$(echo "${iflags}" | awk '{print and(strtonum($1), 0x1000);}')" -gt 0 && htree=1
	test "$(echo "${iflags}" | awk '{print and(strtonum($1), 0x10000000);}')" -gt 0 && inline=1

	case "${dtype}" in
	"inline")
		(test "${inline}" -eq 1 && test "${htree}" -eq 0) || _fail "failed to create ${dtype} dir ino ${inode} htree ${htree} inline ${inline}"
		;;
	"block")
		(test "${inline}" -eq 0 && test "${htree}" -eq 0) || _fail "failed to create ${dtype} dir ino ${inode} htree ${htree} inline ${inline}"
		;;
	"htree")
		(test "${inline}" -eq 0 && test "${htree}" -eq 1) || _fail "failed to create ${dtype} dir ino ${inode} htree ${htree} inline ${inline}"
		;;
	*)
		_fail "Unknown directory type ${dtype}"
		;;
	esac
}

# Check that populate created all the types of files we wanted
_scratch_ext4_populate_check() {
	_scratch_mount
	extents_file="$(__populate_find_inode "${SCRATCH_MNT}/S_IFREG.FMT_EXTENTS")"
	etree_file="$(__populate_find_inode "${SCRATCH_MNT}/S_IFREG.FMT_ETREE")"
	block_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_BLOCK")"
	htree_dir="$(__populate_find_inode "${SCRATCH_MNT}/S_IFDIR.FMT_HTREE")"
	extents_slink="$(__populate_find_inode "${SCRATCH_MNT}/S_IFLNK.FMT_EXTENTS")"
	local_attr="$(__populate_find_inode "${SCRATCH_MNT}/ATTR.FMT_LOCAL")"
	block_attr="$(__populate_find_inode "${SCRATCH_MNT}/ATTR.FMT_BLOCK")"
	umount "${SCRATCH_MNT}"

	__populate_check_ext4_dformat "${extents_file}" "extents"
	__populate_check_ext4_dformat "${etree_file}" "etree"
	__populate_check_ext4_dir "${block_dir}" "block"
	__populate_check_ext4_dir "${htree_dir}" "htree"
	__populate_check_ext4_dformat "${extents_slink}" "extents"
	__populate_check_ext4_aformat "${local_attr}" "local"
	__populate_check_ext4_aformat "${block_attr}" "block"
}

# Populate a scratch FS and check the contents to make sure we got that
_scratch_populate() {
	case "${FSTYP}" in
	"xfs")
		_scratch_xfs_populate
		_scratch_xfs_populate_check
		;;
	"ext2"|"ext3"|"ext4")
		_scratch_ext4_populate
		_scratch_ext4_populate_check
		;;
	*)
		_fail "Don't know how to populate a ${FSTYP} filesystem."
		;;
	esac
}

# Fill a file system by repeatedly creating files in the given folder
# starting with the given file size.  Files are reduced in size when
# they can no longer fit until no more files can be created.
_fill_fs()
{
	local file_size=$1
	local dir=$2
	local block_size=$3
	local switch_user=$4
	local file_count=1
	local bytes_written=0
	local use_falloc=1;

	if [ $# -ne 4 ]; then
		echo "Usage: _fill_fs filesize dir blocksize switch_user"
		exit 1
	fi

	if [ $switch_user -eq 0 ]; then
		mkdir -p $dir
	else
		_user_do "mkdir -p $dir"
	fi
	if [ ! -d $dir ]; then
		return 0;
	fi

	testio=`$XFS_IO_PROG -F -fc "falloc 0 $block_size" $dir/$$.xfs_io 2>&1`
	echo $testio | grep -q "not found" && use_falloc=0
	echo $testio | grep -q "Operation not supported" && use_falloc=0

	if [ $file_size -lt $block_size ]; then
		$file_size = $block_size
	fi

	while [ $file_size -ge $block_size ]; do
		bytes_written=0
		if [ $switch_user -eq 0 ]; then
			if [ $use_falloc -eq 0 ]; then
				$XFS_IO_PROG -fc "pwrite -b 8388608 0 $file_size" \
					$dir/$file_count
			else
				$XFS_IO_PROG -fc "falloc 0 $file_size" \
					$dir/$file_count
			fi
		else
			if [ $use_falloc -eq 0 ]; then
				_user_do "$XFS_IO_PROG -f -c \"pwrite -b 8388608 0 \
					$file_size\" $dir/$file_count"
			else
				_user_do "$XFS_IO_PROG -f -c \"falloc 0 \
					$file_size\" $dir/$file_count"
			fi
		fi

		if [ -f $dir/$file_count ]; then
			bytes_written=$(_get_filesize $dir/$file_count)
		fi

		# If there was no room to make the file, then divide it in
		# half, and keep going
		if [ $bytes_written -lt $file_size ]; then
			file_size=$((file_size / 2))
		fi
		file_count=$((file_count + 1))
	done
}

# Compute the fs geometry description of a populated filesystem
_scratch_populate_cache_tag() {
	local extra_descr=""
	local size="$(blockdev --getsz "${SCRATCH_DEV}")"
	local logdev_sz="none"
	local rtdev_sz="none"

	if [ "${USE_EXTERNAL}" = "yes" ] && [ -n "${SCRATCH_LOGDEV}" ]; then
		logdev_sz="$(blockdev --getsz "${SCRATCH_LOGDEV}")"
	fi

	if [ "${USE_EXTERNAL}" = "yes" ] && [ -n "${SCRATCH_RTDEV}" ]; then
		rtdev_sz="$(blockdev --getsz "${SCRATCH_RTDEV}")"
	fi

	case "${FSTYP}" in
	"ext4")
		extra_descr="LOGDEV_SIZE ${logdev_sz}"
		;;
	"xfs")
		extra_descr="LOGDEV_SIZE ${logdev_sz} RTDEV_SIZE ${rtdev_sz}"
		_populate_xfs_qmount_option
		if echo "${MOUNT_OPTIONS}" | grep -q 'usrquota'; then
			extra_descr="${extra_descr} QUOTAS"
		fi
		;;
	esac
	echo "FSTYP ${FSTYP} MKFS_OPTIONS ${MKFS_OPTIONS} SIZE ${size} ${extra_descr} ARGS $@"
}

# Restore a cached populated fs from a metadata dump
_scratch_populate_restore_cached() {
	local metadump="$1"

	# If we're configured for compressed dumps and there isn't already an
	# uncompressed dump, see if we can use DUMP_COMPRESSOR to decompress
	# something.
	if [ -n "$DUMP_COMPRESSOR" ]; then
		for compr in "$metadump".*; do
			[ -e "$compr" ] && $DUMP_COMPRESSOR -d -f -k "$compr" && break
		done
	fi

	test -r "$metadump" || return 1

	case "${FSTYP}" in
	"xfs")
		xfs_mdrestore "${metadump}" "${SCRATCH_DEV}" && return 0
		;;
	"ext2"|"ext3"|"ext4")
		# ext4 cannot e2image external logs, so we cannot restore
		test -n "${SCRATCH_LOGDEV}" && return 1
		e2image -r "${metadump}" "${SCRATCH_DEV}" && return 0
		;;
	esac
	return 1
}

# Populate a scratch FS from scratch or from a cached image.
_scratch_populate_cached() {
	local meta_descr="$(_scratch_populate_cache_tag "$@")"
	local meta_tag="$(echo "${meta_descr}" | md5sum - | cut -d ' ' -f 1)"
	local metadump_stem="${TEST_DIR}/__populate.${FSTYP}.${meta_tag}"

	# These variables are shared outside this function
	POPULATE_METADUMP="${metadump_stem}.metadump"
	POPULATE_METADUMP_DESCR="${metadump_stem}.txt"

	# Don't keep metadata images cached for more 48 hours...
	rm -rf "$(find "${POPULATE_METADUMP}" -mtime +2 2>/dev/null)"

	# Throw away cached image if it doesn't match our spec.
	cmp -s "${POPULATE_METADUMP_DESCR}" <(echo "${meta_descr}") || \
		rm -rf "${POPULATE_METADUMP}"

	# Try to restore from the metadump
	_scratch_populate_restore_cached "${POPULATE_METADUMP}" && \
		return

	# Oh well, just create one from scratch
	_scratch_mkfs
	echo "${meta_descr}" > "${POPULATE_METADUMP_DESCR}"
	case "${FSTYP}" in
	"xfs")
		_scratch_xfs_populate $@
		_scratch_xfs_populate_check
		_scratch_xfs_metadump "${POPULATE_METADUMP}"

		local logdev=
		[ "$USE_EXTERNAL" = yes -a ! -z "$SCRATCH_LOGDEV" ] && \
			logdev=$SCRATCH_LOGDEV

		_xfs_metadump "$POPULATE_METADUMP" "$SCRATCH_DEV" "$logdev" \
			compress
		;;
	"ext2"|"ext3"|"ext4")
		_scratch_ext4_populate $@
		_scratch_ext4_populate_check
		_ext4_metadump "${SCRATCH_DEV}" "${POPULATE_METADUMP}" compress
		;;
	*)
		_fail "Don't know how to populate a ${FSTYP} filesystem."
		;;
	esac
}