Swap meta allocators with much more reserve.

We increase the reserve from 2x to 3x the minimum number of blocks
needed for our reserve, and change the algorithm that determines when
to swap them.

The old algorithm swaps them if _avail is just larger than _freed. While
the simplest algorithm, it suffers from the problem that in practice,
when we hit ENOSPC conditions, it will almost always swap on every
iteration when we hit our low water mark.

In our testing, we regularly see failures because what is effectively
happening is that we starve both allocators by slowly draining them
block by block, trying to do work. The work of course requires us to
drain more blocks to commit changes. This cycle doesn't end until both
allocators are almost completely drained and not enough blocks remain to
do any real work anymore.

The new algorithm will not swap allocators unless _freed is 50%
larger than _avail.

The outcome is that, during meta space pressure, we're allowing _avail to
slowly drain down to the same levels as before, effectively. However, we
then swap to _freed which is now 1.5x larger.

This results in us being able to do a whole chunk of work without
needing to swap. While draining _avail for longer, we allow work to
commit and recycle blocks back into _freed muich more effectively.

Signed-off-by: Auke Kok <auke.kok@versity.com>

ReleaseNotes.md

@@ -1,6 +1,28 @@
 Versity ScoutFS Release Notes
 =============================
 
+---
+v1.23
+\
+*Dec 11, 2024*
+
+Add support for kernels in the RHEL 9.5 minor release.
+
+---
+v1.22
+\
+*Nov 1, 2024*
+
+Add support for building against the RHEL9 family of kernels.
+
+Fix failure of the setattr\_more ioctl() to set the attributes of a
+zero-length file when restoring.
+
+Fix support for POSIX ACLs in the RHEL8 and later family of kernels.
+
+Fix a race condition in the lock server that could drop lock requests
+under heavy load and cause cluster lock attempts to hang.
+
 ---
 v1.21
 \

kmod/scoutfs-kmod.spec.in

@@ -4,18 +4,13 @@
 %define kmod_git_describe @@GITDESCRIBE@@
 %define pkg_date %(date +%%Y%%m%%d)
 
-# Disable the building of the debug package(s).
-%define debug_package %{nil}
-
 # take kernel version or default to uname -r
 %{!?kversion: %global kversion %(uname -r)}
 %global kernel_version %{kversion}
-%global sanitized_kversion %(echo %{kernel_version} | sed -e 's/-/_/g' -e 's/\.el.*//')
 
 %if 0%{?el7}
 %global kernel_source() /usr/src/kernels/%{kernel_version}.$(arch)
-%endif
-%if 0%{?el8}
+%else
 %global kernel_source() /usr/src/kernels/%{kernel_version}
 %endif
 
@@ -23,21 +18,19 @@
 
 %if 0%{?el7}
 Name:           %{kmod_name}
-%endif
-%if 0%{?el8}
+%else
 Name:           kmod-%{kmod_name}
 %endif
 Summary:        %{kmod_name} kernel module
 Version:        %{kmod_version}
-Release:        %{_release}+%{sanitized_kversion}%{?dist}
+Release:        %{_release}%{?dist}
 License:        GPLv2
 Group:          System/Kernel
 URL:            http://scoutfs.org/
 
 %if 0%{?el7}
 BuildRequires:  %{kernel_module_package_buildreqs}
-%endif
-%if 0%{?el8}
+%else
 BuildRequires:  elfutils-libelf-devel
 %endif
 BuildRequires:  kernel-devel-uname-r = %{kernel_version}
@@ -55,10 +48,23 @@ Source:		%{kmod_name}-kmod-%{kmod_version}.tar
 %endif
 
 %global install_mod_dir extra/%{kmod_name}
-%if 0%{?el8}
+
+%if ! 0%{?el7}
 %global flavors_to_build x86_64
 %endif
 
+# el9 sanity: make sure we lock to the minor release we built for and block upgrades
+%{lua:
+  if string.match(rpm.expand("%{dist}"), "%.el9") then
+    rpm.define("el9 1")
+  end
+}
+
+%if 0%{?el9}
+%define release_major_minor 9.%{lua: print(rpm.expand("%{dist}"):match("%.el9_(%d)"))}
+Requires: system-release = %{release_major_minor}
+%endif
+
 %description
 %{kmod_name} - kernel module
 
@@ -94,7 +100,7 @@ done
 # mark modules executable so that strip-to-file can strip them
 find %{buildroot} -type f -name \*.ko -exec %{__chmod} u+x \{\} \;
 
-%if 0%{?el8}
+%if ! 0%{?el7}
 %files
 /lib/modules
 
@@ -112,8 +118,5 @@ SCOUTFS_RPM_NAME=$(rpm -q %{name} | grep "%{version}-%{release}")
 rpm -ql $SCOUTFS_RPM_NAME | grep '\.ko$' > /var/run/%{name}-modules-%{version}-%{release} || true
 
 %postun
-if [ -x /sbin/weak-modules ]; then
-    cat /var/run/%{name}-modules-%{version}-%{release} | /sbin/weak-modules --remove-modules --no-initramfs
-fi
-
+cat /var/run/%{name}-modules-%{version}-%{release} | weak-modules --remove-modules --no-initramfs
 rm /var/run/%{name}-modules-%{version}-%{release} || true

kmod/src/Makefile.kernelcompat

@@ -78,8 +78,9 @@ endif
 # v4.8-rc1-29-g31051c85b5e2
 #
 # inode_change_ok() removed - replace with setattr_prepare()
+# v5.11-rc4-7-g2f221d6f7b88 removes extern attribute
 #
-ifneq (,$(shell grep 'extern int setattr_prepare' include/linux/fs.h))
+ifneq (,$(shell grep 'int setattr_prepare' include/linux/fs.h))
 ccflags-y += -DKC_SETATTR_PREPARE
 endif
 
@@ -191,7 +192,7 @@ endif
 #
 # Kernel has current_time(inode) to uniformly retreive timespec in the right unit
 #
-ifneq (,$(shell grep 'extern struct timespec64 current_time' include/linux/fs.h))
+ifneq (,$(shell grep 'struct timespec64 current_time' include/linux/fs.h))
 ccflags-y += -DKC_CURRENT_TIME_INODE=1
 endif
 
@@ -258,3 +259,175 @@ endif
 ifneq (,$(shell grep 'static inline const char .xattr_prefix' include/linux/xattr.h))
 ccflags-y += -DKC_XATTR_HANDLER_NAME=1
 endif
+
+#
+# v5.19-rc4-96-g342a72a33407
+#
+# Adds `typedef __u32 __bitwise blk_opf_t` to aid flag checking
+ifneq (,$(shell grep 'typedef __u32 __bitwise blk_opf_t' include/linux/blk_types.h))
+ccflags-y += -DKC_HAVE_BLK_OPF_T=1
+endif
+
+#
+# v5.12-rc6-9-g4f0f586bf0c8
+#
+# list_sort cmp function takes const list_head args
+ifneq (,$(shell grep 'const struct list_head ., const struct list_head .' include/linux/list_sort.h))
+ccflags-y += -DKC_LIST_CMP_CONST_ARG_LIST_HEAD
+endif
+
+# v5.7-523-g88dca4ca5a93
+#
+# The pgprot argument to vmalloc is always PAGE_KERNEL, so it is removed.
+ifneq (,$(shell grep 'extern void .__vmalloc.unsigned long size, gfp_t gfp_mask, pgprot_t prot' include/linux/vmalloc.h))
+ccflags-y += -DKC_VMALLOC_PGPROT_T
+endif
+
+# v6.2-rc1-18-g01beba7957a2
+#
+# fs: port inode_owner_or_capable() to mnt_idmap
+ifneq (,$(shell grep 'bool inode_owner_or_capable.struct user_namespace .mnt_userns' include/linux/fs.h))
+ccflags-y += -DKC_INODE_OWNER_OR_CAPABLE_USERNS
+endif
+
+#
+# v5.11-rc4-5-g47291baa8ddf
+#
+# namei: make permission helpers idmapped mount aware
+ifneq (,$(shell grep 'int inode_permission.struct user_namespace' include/linux/fs.h))
+ccflags-y += -DKC_INODE_PERMISSION_USERNS
+endif
+
+#
+# v5.11-rc4-24-g549c7297717c
+#
+# fs: make helpers idmap mount aware
+# Enlarges the VFS API methods to include user namespace argument.
+ifneq (,$(shell grep 'int ..mknod. .struct user_namespace' include/linux/fs.h))
+ccflags-y += -DKC_VFS_METHOD_USER_NAMESPACE_ARG
+endif
+
+#
+# v5.17-rc2-21-g07888c665b40
+#
+# Detect new style bio_alloc - pass bdev and opf.
+ifneq (,$(shell grep 'struct bio .bio_alloc.struct block_device .bdev' include/linux/bio.h))
+ccflags-y += -DKC_BIO_ALLOC_DEV_OPF_ARGS
+endif
+
+#
+# v5.7-rc4-53-gcddf8a2c4a82
+#
+# fiemap_prep() replaces fiemap_check_flags()
+ifneq (,$(shell grep -s 'int fiemap_prep.struct inode' include/linux/fiemap.h))
+ccflags-y += -DKC_FIEMAP_PREP
+endif
+
+#
+# v5.17-13043-g800ba29547e1
+#
+# generic_perform_write args use kiocb for passing filp and pos
+ifneq (,$(shell grep 'ssize_t generic_perform_write.struct kiocb ., struct iov_iter' include/linux/fs.h))
+ccflags-y += -DKC_GENERIC_PERFORM_WRITE_KIOCB_IOV_ITER
+endif
+
+#
+# v5.7-rc6-2496-g76ee0785f42a
+#
+# net: add sock_set_sndtimeo
+ifneq (,$(shell grep 'void sock_set_sndtimeo.struct sock' include/net/sock.h))
+ccflags-y += -DKC_SOCK_SET_SNDTIMEO
+endif
+
+#
+# v5.8-rc4-1931-gba423fdaa589
+#
+# setsockopt functions are now passed a sockptr_t value instead of char*
+ifneq (,$(shell grep -s 'include .linux/sockptr.h.' include/linux/net.h))
+ccflags-y += -DKC_SETSOCKOPT_SOCKPTR_T
+endif
+
+#
+# v5.7-rc6-2507-g71c48eb81c9e
+#
+# Adds a bunch of low level TCP sock parameter functions that we want to use.
+ifneq (,$(shell grep 'int tcp_sock_set_keepintvl' include/linux/tcp.h))
+ccflags-y += -DKC_HAVE_TCP_SET_SOCKFN
+endif
+
+#
+# v4.16-rc3-13-ga84d1169164b
+#
+# Fixes y2038 issues with struct timeval.
+ifneq (,$(shell grep -s '^struct __kernel_old_timeval .' include/uapi/linux/time_types.h))
+ccflags-y += -DKC_KERNEL_OLD_TIMEVAL_STRUCT
+endif
+
+#
+# v5.19-rc4-52-ge33c267ab70d
+#
+# register_shrinker now requires a name, used for debug stats etc.
+ifneq (,$(shell grep 'int __printf.*register_shrinker.struct shrinker .shrinker,' include/linux/shrinker.h))
+ccflags-y += -DKC_SHRINKER_NAME
+endif
+
+#
+# v5.18-rc5-246-gf132ab7d3ab0
+#
+# mpage_readpage() is now replaced with mpage_read_folio.
+ifneq (,$(shell grep 'int mpage_read_folio.struct folio .folio' include/linux/mpage.h))
+ccflags-y += -DKC_MPAGE_READ_FOLIO
+endif
+
+#
+# v5.18-rc5-219-gb3992d1e2ebc
+#
+# block_write_begin() no longer is being passed aop_flags
+ifneq (,$(shell grep -C1 'int block_write_begin' include/linux/buffer_head.h | tail -n 2 | grep 'unsigned flags'))
+ccflags-y += -DKC_BLOCK_WRITE_BEGIN_AOP_FLAGS
+endif
+
+#
+# v6.0-rc6-9-g863f144f12ad
+#
+# the .tmpfile() vfs method calling convention changed and now a struct
+# file* is passed to this metiond instead of a dentry. The function also
+# should open the created file and call finish_open_simple() before returning.
+ifneq (,$(shell grep 'extern void d_tmpfile.struct dentry' include/linux/dcache.h))
+ccflags-y += -DKC_D_TMPFILE_DENTRY
+endif
+
+#
+# v6.4-rc2-201-g0733ad800291
+#
+# New blk_mode_t replaces abuse of fmode_t
+ifneq (,$(shell grep 'typedef unsigned int __bitwise blk_mode_t' include/linux/blkdev.h))
+ccflags-y += -DKC_HAVE_BLK_MODE_T
+endif
+
+#
+# v6.4-rc2-186-g2736e8eeb0cc
+#
+# Reworks FMODE_EXCL kludge and instead modifies the blkdev_put() call to pass in
+# the (exclusive) holder to implement FMODE_EXCL handling.
+ifneq (,$(shell grep 'blkdev_put.struct block_device .bdev, void .holder' include/linux/blkdev.h))
+ccflags-y += -DKC_BLKDEV_PUT_HOLDER_ARG
+endif
+
+#
+# v6.4-rc4-163-g0d625446d0a4
+#
+# Entirely removes current->backing_dev_info to ultimately remove buffer_head
+# completely at some point.
+ifneq (,$(shell grep 'struct backing_dev_info.*backing_dev_info;' include/linux/sched.h))
+ccflags-y += -DKC_CURRENT_BACKING_DEV_INFO
+endif
+
+#
+# v6.8-rc1-4-gf3a608827d1f
+#
+# adds bdev_file_open_by_path() and later in v6.8-rc1-30-ge97d06a46526 removes bdev_open_by_path()
+# which requires us to use the file method from now on.
+ifneq (,$(shell grep 'struct file.*bdev_file_open_by_path.const char.*path' include/linux/blkdev.h))
+ccflags-y += -DKC_BDEV_FILE_OPEN_BY_PATH
+endif

kmod/src/acl.c

@@ -153,7 +153,8 @@ int scoutfs_set_acl_locked(struct inode *inode, struct posix_acl *acl, int type,
 	switch (type) {
 	case ACL_TYPE_ACCESS:
 		if (acl) {
-			ret = posix_acl_update_mode(inode, &new_mode, &acl);
+			ret = posix_acl_update_mode(KC_VFS_INIT_NS
+						    inode, &new_mode, &acl);
 			if (ret < 0)
 				goto out;
 			set_mode = true;
@@ -252,7 +253,9 @@ int scoutfs_acl_get_xattr(struct dentry *dentry, const char *name, void *value,
 }
 
 #ifdef KC_XATTR_STRUCT_XATTR_HANDLER
-int scoutfs_acl_set_xattr(const struct xattr_handler *handler, struct dentry *dentry,
+int scoutfs_acl_set_xattr(const struct xattr_handler *handler,
+			  KC_VFS_NS_DEF
+			  struct dentry *dentry,
 			  struct inode *inode, const char *name, const void *value,
 			  size_t size, int flags)
 {
@@ -265,7 +268,7 @@ int scoutfs_acl_set_xattr(struct dentry *dentry, const char *name, const void *v
 	struct posix_acl *acl = NULL;
 	int ret;
 
-	if (!inode_owner_or_capable(dentry->d_inode))
+	if (!inode_owner_or_capable(KC_VFS_INIT_NS dentry->d_inode))
 		return -EPERM;
 
 	if (!IS_POSIXACL(dentry->d_inode))

kmod/src/acl.h

@@ -10,7 +10,9 @@ int scoutfs_set_acl_locked(struct inode *inode, struct posix_acl *acl, int type,
 int scoutfs_acl_get_xattr(const struct xattr_handler *, struct dentry *dentry,
 			  struct inode *inode, const char *name, void *value,
 			  size_t size);
-int scoutfs_acl_set_xattr(const struct xattr_handler *, struct dentry *dentry,
+int scoutfs_acl_set_xattr(const struct xattr_handler *,
+			  KC_VFS_NS_DEF
+			  struct dentry *dentry,
 			  struct inode *inode, const char *name, const void *value,
 			  size_t size, int flags);
 #else

kmod/src/alloc.c

@@ -14,6 +14,7 @@
 #include <linux/module.h>
 #include <linux/fs.h>
 #include <linux/slab.h>
+#include <linux/blkdev.h>
 #include <linux/sort.h>
 #include <linux/random.h>
 

kmod/src/block.c

@@ -120,8 +120,7 @@ do {												\
 
 static __le32 block_calc_crc(struct scoutfs_block_header *hdr, u32 size)
 {
-	int off = offsetof(struct scoutfs_block_header, crc) +
-		  FIELD_SIZEOF(struct scoutfs_block_header, crc);
+	int off = offsetofend(struct scoutfs_block_header, crc);
 	u32 calc = crc32c(~0, (char *)hdr + off, size - off);
 
 	return cpu_to_le32(calc);
@@ -159,7 +158,7 @@ static struct block_private *block_alloc(struct super_block *sb, u64 blkno)
 		 */
 		lockdep_off();
 		nofs_flags = memalloc_nofs_save();
-		bp->virt = __vmalloc(SCOUTFS_BLOCK_LG_SIZE, GFP_NOFS | __GFP_HIGHMEM, PAGE_KERNEL);
+		bp->virt = kc__vmalloc(SCOUTFS_BLOCK_LG_SIZE, GFP_NOFS | __GFP_HIGHMEM);
 		memalloc_nofs_restore(nofs_flags);
 		lockdep_on();
 
@@ -438,7 +437,7 @@ static void block_remove_all(struct super_block *sb)
  * possible.  Final freeing, verifying checksums, and unlinking errored
  * blocks are all done by future users of the blocks.
  */
-static void block_end_io(struct super_block *sb, unsigned int opf,
+static void block_end_io(struct super_block *sb, blk_opf_t opf,
 			 struct block_private *bp, int err)
 {
 	DECLARE_BLOCK_INFO(sb, binf);
@@ -478,7 +477,7 @@ static void KC_DECLARE_BIO_END_IO(block_bio_end_io, struct bio *bio)
  * Kick off IO for a single block.
  */
 static int block_submit_bio(struct super_block *sb, struct block_private *bp,
-			    unsigned int opf)
+			    blk_opf_t opf)
 {
 	struct scoutfs_sb_info *sbi = SCOUTFS_SB(sb);
 	struct bio *bio = NULL;
@@ -505,15 +504,13 @@ static int block_submit_bio(struct super_block *sb, struct block_private *bp,
 
 	for (off = 0; off < SCOUTFS_BLOCK_LG_SIZE; off += PAGE_SIZE) {
 		if (!bio) {
-			bio = bio_alloc(GFP_NOFS, SCOUTFS_BLOCK_LG_PAGES_PER);
+			bio = kc_bio_alloc(sbi->meta_bdev, SCOUTFS_BLOCK_LG_PAGES_PER, opf, GFP_NOFS);
 			if (!bio) {
 				ret = -ENOMEM;
 				break;
 			}
 
-			kc_bio_set_opf(bio, opf);
 			kc_bio_set_sector(bio, sector + (off >> 9));
-			bio_set_dev(bio, sbi->meta_bdev);
 			bio->bi_end_io = block_bio_end_io;
 			bio->bi_private = bp;
 
@@ -1201,7 +1198,7 @@ static void KC_DECLARE_BIO_END_IO(sm_block_bio_end_io, struct bio *bio)
  * only layer that sees the full block buffer so we pass the calculated
  * crc to the caller for them to check in their context.
  */
-static int sm_block_io(struct super_block *sb, struct block_device *bdev, unsigned int opf,
+static int sm_block_io(struct super_block *sb, struct block_device *bdev, blk_opf_t opf,
 		       u64 blkno, struct scoutfs_block_header *hdr, size_t len, __le32 *blk_crc)
 {
 	struct scoutfs_block_header *pg_hdr;
@@ -1233,15 +1230,13 @@ static int sm_block_io(struct super_block *sb, struct block_device *bdev, unsign
 		pg_hdr->crc = block_calc_crc(pg_hdr, SCOUTFS_BLOCK_SM_SIZE);
 	}
 
-	bio = bio_alloc(GFP_NOFS, 1);
+	bio = kc_bio_alloc(bdev, 1, opf, GFP_NOFS);
 	if (!bio) {
 		ret = -ENOMEM;
 		goto out;
 	}
 
-	kc_bio_set_opf(bio, opf | REQ_SYNC);
 	kc_bio_set_sector(bio, blkno << (SCOUTFS_BLOCK_SM_SHIFT - 9));
-	bio_set_dev(bio, bdev);
 	bio->bi_end_io = sm_block_bio_end_io;
 	bio->bi_private = &sbc;
 	bio_add_page(bio, page, SCOUTFS_BLOCK_SM_SIZE, 0);
@@ -1302,7 +1297,7 @@ int scoutfs_block_setup(struct super_block *sb)
 	init_waitqueue_head(&binf->waitq);
 	KC_INIT_SHRINKER_FUNCS(&binf->shrinker, block_count_objects,
 			       block_scan_objects);
-	KC_REGISTER_SHRINKER(&binf->shrinker);
+	KC_REGISTER_SHRINKER(&binf->shrinker, "scoutfs-block:" SCSBF, SCSB_ARGS(sb));
 	INIT_WORK(&binf->free_work, block_free_work);
 	init_llist_head(&binf->free_llist);
 

kmod/src/client.c

@@ -20,6 +20,7 @@
 #include <net/sock.h>
 #include <net/tcp.h>
 #include <asm/barrier.h>
+#include <linux/overflow.h>
 
 #include "format.h"
 #include "counters.h"
@@ -68,6 +69,7 @@ int scoutfs_client_alloc_inodes(struct super_block *sb, u64 count,
 	struct client_info *client = SCOUTFS_SB(sb)->client_info;
 	struct scoutfs_net_inode_alloc ial;
 	__le64 lecount = cpu_to_le64(count);
+	u64 tmp;
 	int ret;
 
 	ret = scoutfs_net_sync_request(sb, client->conn,
@@ -80,7 +82,7 @@ int scoutfs_client_alloc_inodes(struct super_block *sb, u64 count,
 
 		if (*nr == 0)
 			ret = -ENOSPC;
-		else if (*ino + *nr < *ino)
+		else if (check_add_overflow(*ino, *nr - 1, &tmp))
 			ret = -EINVAL;
 	}
 

kmod/src/data.c

@@ -20,7 +20,9 @@
 #include <linux/hash.h>
 #include <linux/log2.h>
 #include <linux/falloc.h>
+#include <linux/fiemap.h>
 #include <linux/writeback.h>
+#include <linux/overflow.h>
 
 #include "format.h"
 #include "super.h"
@@ -679,8 +681,14 @@ int scoutfs_get_block_write(struct inode *inode, sector_t iblock, struct buffer_
  * We can return errors from locking and checking offline extents.  The
  * page is unlocked if we return an error.
  */
+#ifdef KC_MPAGE_READ_FOLIO
+static int scoutfs_read_folio(struct file *file, struct folio *folio)
+{
+	struct page *page = &folio->page;
+#else
 static int scoutfs_readpage(struct file *file, struct page *page)
 {
+#endif
 	struct inode *inode = file->f_inode;
 	struct scoutfs_inode_info *si = SCOUTFS_I(inode);
 	struct super_block *sb = inode->i_sb;
@@ -727,7 +735,11 @@ static int scoutfs_readpage(struct file *file, struct page *page)
 			return ret;
 	}
 
+#ifdef KC_MPAGE_READ_FOLIO
+	ret = mpage_read_folio(folio, scoutfs_get_block_read);
+#else
 	ret = mpage_readpage(page, scoutfs_get_block_read);
+#endif
 
 	scoutfs_unlock(sb, inode_lock, SCOUTFS_LOCK_READ);
 	scoutfs_per_task_del(&si->pt_data_lock, &pt_ent);
@@ -825,7 +837,10 @@ struct write_begin_data {
 
 static int scoutfs_write_begin(struct file *file,
 			       struct address_space *mapping, loff_t pos,
-			       unsigned len, unsigned flags,
+			       unsigned len,
+#ifdef KC_BLOCK_WRITE_BEGIN_AOP_FLAGS
+			       unsigned flags,
+#endif
 			       struct page **pagep, void **fsdata)
 {
 	struct inode *inode = mapping->host;
@@ -860,13 +875,18 @@ retry:
 	if (ret < 0)
 		goto out;
 
+#ifdef KC_BLOCK_WRITE_BEGIN_AOP_FLAGS
 	/* can't re-enter fs, have trans */
 	flags |= AOP_FLAG_NOFS;
+#endif
 
 	/* generic write_end updates i_size and calls dirty_inode */
 	ret = scoutfs_dirty_inode_item(inode, wbd->lock) ?:
-	      block_write_begin(mapping, pos, len, flags, pagep,
-				scoutfs_get_block_write);
+	      block_write_begin(mapping, pos, len,
+#ifdef KC_BLOCK_WRITE_BEGIN_AOP_FLAGS
+				flags,
+#endif
+				pagep, scoutfs_get_block_write);
 	if (ret < 0) {
 		scoutfs_release_trans(sb);
 		scoutfs_inode_index_unlock(sb, &wbd->ind_locks);
@@ -1068,6 +1088,7 @@ long scoutfs_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
 	loff_t end;
 	u64 iblock;
 	u64 last;
+	loff_t tmp;
 	s64 ret;
 
 	/* XXX support more flags */
@@ -1076,14 +1097,14 @@ long scoutfs_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
 		goto out;
 	}
 
-	/* catch wrapping */
-	if (offset + len < offset) {
-		ret = -EINVAL;
+	if (len == 0) {
+		ret = 0;
 		goto out;
 	}
 
-	if (len == 0) {
-		ret = 0;
+	/* catch wrapping */
+	if (check_add_overflow(offset, len - 1, &tmp)) {
+		ret = -EINVAL;
 		goto out;
 	}
 
@@ -1304,8 +1325,8 @@ int scoutfs_data_move_blocks(struct inode *from, u64 from_off,
 		goto out;
 	}
 
-	ret = inode_permission(from, MAY_WRITE) ?:
-	      inode_permission(to, MAY_WRITE);
+	ret = inode_permission(KC_VFS_INIT_NS from, MAY_WRITE) ?:
+	      inode_permission(KC_VFS_INIT_NS to, MAY_WRITE);
 	if (ret < 0)
 		goto out;
 
@@ -1543,7 +1564,7 @@ int scoutfs_data_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
 		goto out;
 	}
 
-	ret = fiemap_check_flags(fieinfo, FIEMAP_FLAG_SYNC);
+	ret = fiemap_prep(inode, fieinfo, start, &len, FIEMAP_FLAG_SYNC);
 	if (ret)
 		goto out;
 
@@ -1709,12 +1730,16 @@ int scoutfs_data_wait_check(struct inode *inode, loff_t pos, loff_t len,
 	u64 last_block;
 	u64 on;
 	u64 off;
+	loff_t tmp;
 	int ret = 0;
 
+	if (len == 0)
+		goto out;
+
 	if (WARN_ON_ONCE(sef & SEF_UNKNOWN) ||
 	    WARN_ON_ONCE(op & SCOUTFS_IOC_DWO_UNKNOWN) ||
 	    WARN_ON_ONCE(dw && !RB_EMPTY_NODE(&dw->node)) ||
-	    WARN_ON_ONCE(pos + len < pos)) {
+	    WARN_ON_ONCE(check_add_overflow(pos, len - 1, &tmp))) {
 		ret = -EINVAL;
 		goto out;
 	}
@@ -1890,7 +1915,13 @@ int scoutfs_data_waiting(struct super_block *sb, u64 ino, u64 iblock,
 }
 
 const struct address_space_operations scoutfs_file_aops = {
+#ifdef KC_MPAGE_READ_FOLIO
+	.dirty_folio		= block_dirty_folio,
+	.invalidate_folio	= block_invalidate_folio,
+	.read_folio		= scoutfs_read_folio,
+#else
 	.readpage		= scoutfs_readpage,
+#endif
 #ifndef KC_FILE_AOPS_READAHEAD
 	.readpages		= scoutfs_readpages,
 #else
@@ -1911,6 +1942,8 @@ const struct file_operations scoutfs_file_fops = {
 #else
 	.read_iter	= scoutfs_file_read_iter,
 	.write_iter	= scoutfs_file_write_iter,
+	.splice_read	= generic_file_splice_read,
+	.splice_write	= iter_file_splice_write,
 #endif
 	.unlocked_ioctl	= scoutfs_ioctl,
 	.fsync		= scoutfs_file_fsync,

kmod/src/dir.c

@@ -703,8 +703,9 @@ out_unlock:
 	return inode;
 }
 
-static int scoutfs_mknod(struct inode *dir, struct dentry *dentry, umode_t mode,
-		       dev_t rdev)
+static int scoutfs_mknod(KC_VFS_NS_DEF
+			 struct inode *dir,
+			 struct dentry *dentry, umode_t mode, dev_t rdev)
 {
 	struct super_block *sb = dir->i_sb;
 	struct inode *inode = NULL;
@@ -773,15 +774,20 @@ out:
 }
 
 /* XXX hmm, do something with excl? */
-static int scoutfs_create(struct inode *dir, struct dentry *dentry,
-			  umode_t mode, bool excl)
+static int scoutfs_create(KC_VFS_NS_DEF
+			  struct inode *dir,
+			  struct dentry *dentry, umode_t mode, bool excl)
 {
-	return scoutfs_mknod(dir, dentry, mode | S_IFREG, 0);
+	return scoutfs_mknod(KC_VFS_NS
+			     dir, dentry, mode | S_IFREG, 0);
 }
 
-static int scoutfs_mkdir(struct inode *dir, struct dentry *dentry, umode_t mode)
+static int scoutfs_mkdir(KC_VFS_NS_DEF
+			 struct inode *dir,
+			 struct dentry *dentry, umode_t mode)
 {
-	return scoutfs_mknod(dir, dentry, mode | S_IFDIR, 0);
+	return scoutfs_mknod(KC_VFS_NS
+			     dir, dentry, mode | S_IFDIR, 0);
 }
 
 static int scoutfs_link(struct dentry *old_dentry,
@@ -1176,7 +1182,8 @@ static const char *scoutfs_get_link(struct dentry *dentry, struct inode *inode,
  * Symlink target paths can be annoyingly large.  We store relatively
  * rare large paths in multiple items.
  */
-static int scoutfs_symlink(struct inode *dir, struct dentry *dentry,
+static int scoutfs_symlink(KC_VFS_NS_DEF
+			   struct inode *dir, struct dentry *dentry,
 			   const char *symname)
 {
 	struct super_block *sb = dir->i_sb;
@@ -1563,7 +1570,8 @@ static int verify_ancestors(struct super_block *sb, u64 p1, u64 p2,
  * from using parent/child locking orders as two groups can have both
  * parent and child relationships to each other.
  */
-static int scoutfs_rename_common(struct inode *old_dir,
+static int scoutfs_rename_common(KC_VFS_NS_DEF
+				 struct inode *old_dir,
 				 struct dentry *old_dentry, struct inode *new_dir,
 				 struct dentry *new_dentry, unsigned int flags)
 {
@@ -1840,18 +1848,21 @@ static int scoutfs_rename(struct inode *old_dir,
 			  struct dentry *old_dentry, struct inode *new_dir,
 			  struct dentry *new_dentry)
 {
-	return scoutfs_rename_common(old_dir, old_dentry, new_dir, new_dentry, 0);
+	return scoutfs_rename_common(KC_VFS_INIT_NS
+				     old_dir, old_dentry, new_dir, new_dentry, 0);
 }
 #endif
 
-static int scoutfs_rename2(struct inode *old_dir,
+static int scoutfs_rename2(KC_VFS_NS_DEF
+			  struct inode *old_dir,
 			  struct dentry *old_dentry, struct inode *new_dir,
 			  struct dentry *new_dentry, unsigned int flags)
 {
 	if (flags & ~RENAME_NOREPLACE)
 		return -EINVAL;
 
-	return scoutfs_rename_common(old_dir, old_dentry, new_dir, new_dentry, flags);
+	return scoutfs_rename_common(KC_VFS_NS
+				     old_dir, old_dentry, new_dir, new_dentry, flags);
 }
 
 #ifdef KC_FMODE_KABI_ITERATE
@@ -1863,8 +1874,18 @@ static int scoutfs_dir_open(struct inode *inode, struct file *file)
 }
 #endif
 
-static int scoutfs_tmpfile(struct inode *dir, struct dentry *dentry, umode_t mode)
+static int scoutfs_tmpfile(KC_VFS_NS_DEF
+			   struct inode *dir,
+#ifdef KC_D_TMPFILE_DENTRY
+			   struct dentry *dentry,
+#else
+			   struct file *file,
+#endif
+			   umode_t mode)
 {
+#ifndef KC_D_TMPFILE_DENTRY
+	struct dentry *dentry = file->f_path.dentry;
+#endif
 	struct super_block *sb = dir->i_sb;
 	struct inode *inode = NULL;
 	struct scoutfs_lock *dir_lock = NULL;
@@ -1891,7 +1912,11 @@ static int scoutfs_tmpfile(struct inode *dir, struct dentry *dentry, umode_t mod
 	si->crtime = inode->i_mtime;
 	insert_inode_hash(inode);
 	ihold(inode); /* need to update inode modifications in d_tmpfile */
+#ifdef KC_D_TMPFILE_DENTRY
 	d_tmpfile(dentry, inode);
+#else
+	d_tmpfile(file, inode);
+#endif
 	inode_inc_iversion(inode);
 	scoutfs_forest_inc_inode_count(sb);
 
@@ -1899,6 +1924,10 @@ static int scoutfs_tmpfile(struct inode *dir, struct dentry *dentry, umode_t mod
 	scoutfs_update_inode_item(dir, dir_lock, &ind_locks);
 	scoutfs_inode_index_unlock(sb, &ind_locks);
 
+#ifndef KC_D_TMPFILE_DENTRY
+	ret = finish_open_simple(file, 0);
+#endif
+
 out:
 	scoutfs_release_trans(sb);
 	scoutfs_inode_index_unlock(sb, &ind_locks);

kmod/src/fence.c

@@ -105,12 +105,12 @@ static ssize_t elapsed_secs_show(struct kobject *kobj,
 {
 	DECLARE_FENCE_FROM_KOBJ(fence, kobj);
 	ktime_t now = ktime_get();
-	struct timeval tv = { 0, };
+	ktime_t t = ns_to_ktime(0);
 
 	if (ktime_after(now, fence->start_kt))
-		tv = ktime_to_timeval(ktime_sub(now, fence->start_kt));
+		t = ktime_sub(now, fence->start_kt);
 
-	return snprintf(buf, PAGE_SIZE, "%llu", (long long)tv.tv_sec);
+	return snprintf(buf, PAGE_SIZE, "%llu", (long long)ktime_divns(t, NSEC_PER_SEC));
 }
 SCOUTFS_ATTR_RO(elapsed_secs);
 

kmod/src/file.c

@@ -267,7 +267,8 @@ out:
 }
 #endif
 
-int scoutfs_permission(struct inode *inode, int mask)
+int scoutfs_permission(KC_VFS_NS_DEF
+		       struct inode *inode, int mask)
 {
 	struct super_block *sb = inode->i_sb;
 	struct scoutfs_lock *inode_lock = NULL;
@@ -281,7 +282,8 @@ int scoutfs_permission(struct inode *inode, int mask)
 	if (ret)
 		return ret;
 
-	ret = generic_permission(inode, mask);
+	ret = generic_permission(KC_VFS_INIT_NS
+				 inode, mask);
 
 	scoutfs_unlock(sb, inode_lock, SCOUTFS_LOCK_READ);
 

kmod/src/file.h

@@ -10,7 +10,8 @@ ssize_t scoutfs_file_aio_write(struct kiocb *iocb, const struct iovec *iov,
 ssize_t scoutfs_file_read_iter(struct kiocb *, struct iov_iter *);
 ssize_t scoutfs_file_write_iter(struct kiocb *, struct iov_iter *);
 #endif
-int scoutfs_permission(struct inode *inode, int mask);
+int scoutfs_permission(KC_VFS_NS_DEF
+		       struct inode *inode, int mask);
 loff_t scoutfs_file_llseek(struct file *file, loff_t offset, int whence);
 
 #endif	/* _SCOUTFS_FILE_H_ */

kmod/src/inode.c

@@ -373,7 +373,8 @@ int scoutfs_getattr(struct vfsmount *mnt, struct dentry *dentry,
 {
 	struct inode *inode = dentry->d_inode;
 #else
-int scoutfs_getattr(const struct path *path, struct kstat *stat,
+int scoutfs_getattr(KC_VFS_NS_DEF
+		    const struct path *path, struct kstat *stat,
 		    u32 request_mask, unsigned int query_flags)
 {
 	struct inode *inode = d_inode(path->dentry);
@@ -385,7 +386,8 @@ int scoutfs_getattr(const struct path *path, struct kstat *stat,
 	ret = scoutfs_lock_inode(sb, SCOUTFS_LOCK_READ,
 				 SCOUTFS_LKF_REFRESH_INODE, inode, &lock);
 	if (ret == 0) {
-		generic_fillattr(inode, stat);
+		generic_fillattr(KC_VFS_INIT_NS
+				 inode, stat);
 		scoutfs_unlock(sb, lock, SCOUTFS_LOCK_READ);
 	}
 	return ret;
@@ -483,7 +485,8 @@ int scoutfs_complete_truncate(struct inode *inode, struct scoutfs_lock *lock)
  * re-acquire it.  Ideally we'd fix this so that we can acquire the lock
  * instead of the caller.
  */
-int scoutfs_setattr(struct dentry *dentry, struct iattr *attr)
+int scoutfs_setattr(KC_VFS_NS_DEF
+		    struct dentry *dentry, struct iattr *attr)
 {
 	struct inode *inode = dentry->d_inode;
 	struct super_block *sb = inode->i_sb;
@@ -501,7 +504,8 @@ retry:
 				 SCOUTFS_LKF_REFRESH_INODE, inode, &lock);
 	if (ret)
 		return ret;
-	ret = setattr_prepare(dentry, attr);
+	ret = setattr_prepare(KC_VFS_INIT_NS
+			      dentry, attr);
 	if (ret)
 		goto out;
 
@@ -565,7 +569,8 @@ retry:
 	if (ret < 0)
 		goto release;
 
-	setattr_copy(inode, attr);
+	setattr_copy(KC_VFS_INIT_NS
+		     inode, attr);
 	inode_inc_iversion(inode);
 	scoutfs_update_inode_item(inode, lock, &ind_locks);
 
@@ -979,10 +984,10 @@ static bool inode_has_index(umode_t mode, u8 type)
 	}
 }
 
-static int cmp_index_lock(void *priv, struct list_head *A, struct list_head *B)
+static int cmp_index_lock(void *priv, KC_LIST_CMP_CONST struct list_head *A, KC_LIST_CMP_CONST struct list_head *B)
 {
-	struct index_lock *a = list_entry(A, struct index_lock, head);
-	struct index_lock *b = list_entry(B, struct index_lock, head);
+	KC_LIST_CMP_CONST struct index_lock *a = list_entry(A, KC_LIST_CMP_CONST struct index_lock, head);
+	KC_LIST_CMP_CONST struct index_lock *b = list_entry(B, KC_LIST_CMP_CONST struct index_lock, head);
 
 	return ((int)a->type - (int)b->type) ?:
 	       scoutfs_cmp_u64s(a->major, b->major) ?:
@@ -1562,7 +1567,8 @@ int scoutfs_new_inode(struct super_block *sb, struct inode *dir, umode_t mode, d
 	scoutfs_inode_set_data_seq(inode);
 
 	inode->i_ino = ino; /* XXX overflow */
-	inode_init_owner(inode, dir, mode);
+	inode_init_owner(KC_VFS_INIT_NS
+			 inode, dir, mode);
 	inode_set_bytes(inode, 0);
 	inode->i_mtime = inode->i_atime = inode->i_ctime = current_time(inode);
 	inode->i_rdev = rdev;

kmod/src/inode.h

@@ -135,10 +135,12 @@ int scoutfs_inode_refresh(struct inode *inode, struct scoutfs_lock *lock);
 int scoutfs_getattr(struct vfsmount *mnt, struct dentry *dentry,
 		    struct kstat *stat);
 #else
-int scoutfs_getattr(const struct path *path, struct kstat *stat,
+int scoutfs_getattr(KC_VFS_NS_DEF
+		    const struct path *path, struct kstat *stat,
 		    u32 request_mask, unsigned int query_flags);
 #endif
-int scoutfs_setattr(struct dentry *dentry, struct iattr *attr);
+int scoutfs_setattr(KC_VFS_NS_DEF
+		    struct dentry *dentry, struct iattr *attr);
 
 int scoutfs_inode_orphan_create(struct super_block *sb, u64 ino, struct scoutfs_lock *lock,
 				struct scoutfs_lock *primary);

kmod/src/ioctl.c

@@ -23,6 +23,7 @@
 #include <linux/aio.h>
 #include <linux/list_sort.h>
 #include <linux/backing-dev.h>
+#include <linux/overflow.h>
 
 #include "format.h"
 #include "key.h"
@@ -47,6 +48,7 @@
 #include "wkic.h"
 #include "quota.h"
 #include "scoutfs_trace.h"
+#include "util.h"
 
 /*
  * We make inode index items coherent by locking fixed size regions of
@@ -288,6 +290,7 @@ static long scoutfs_ioc_release(struct file *file, unsigned long arg)
 	u64 online;
 	u64 offline;
 	u64 isize;
+	__u64 tmp;
 	int ret;
 
 	if (copy_from_user(&args, (void __user *)arg, sizeof(args)))
@@ -297,12 +300,11 @@ static long scoutfs_ioc_release(struct file *file, unsigned long arg)
 
 	if (args.length == 0)
 		return 0;
-	if (((args.offset + args.length) < args.offset) ||
+	if ((check_add_overflow(args.offset, args.length - 1, &tmp)) ||
 	    (args.offset & SCOUTFS_BLOCK_SM_MASK) ||
 	    (args.length & SCOUTFS_BLOCK_SM_MASK))
 		return -EINVAL;
 
-
 	ret = mnt_want_write_file(file);
 	if (ret)
 		return ret;
@@ -522,7 +524,9 @@ static long scoutfs_ioc_stage(struct file *file, unsigned long arg)
 	}
 
 	si->staging = true;
+#ifdef KC_CURRENT_BACKING_DEV_INFO
 	current->backing_dev_info = inode_to_bdi(inode);
+#endif
 
 	pos = args.offset;
 	written = 0;
@@ -535,7 +539,9 @@ static long scoutfs_ioc_stage(struct file *file, unsigned long arg)
 	} while (ret > 0 && written < args.length);
 
 	si->staging = false;
+#ifdef KC_CURRENT_BACKING_DEV_INFO
 	current->backing_dev_info = NULL;
+#endif
 out:
 	scoutfs_per_task_del(&si->pt_data_lock, &pt_ent);
 	scoutfs_unlock(sb, lock, SCOUTFS_LOCK_WRITE);
@@ -674,8 +680,8 @@ static long scoutfs_ioc_setattr_more(struct file *file, unsigned long arg)
 		goto out;
 	}
 
-	iax->x_mask = SCOUTFS_IOC_IAX_DATA_VERSION | SCOUTFS_IOC_IAX_CTIME |
-		      SCOUTFS_IOC_IAX_CRTIME | SCOUTFS_IOC_IAX_SIZE;
+	iax->x_mask = SCOUTFS_IOC_IAX_CTIME | SCOUTFS_IOC_IAX_CRTIME |
+		      SCOUTFS_IOC_IAX_SIZE;
 	iax->data_version = sm.data_version;
 	iax->ctime_sec = sm.ctime_sec;
 	iax->ctime_nsec = sm.ctime_nsec;
@@ -686,6 +692,9 @@ static long scoutfs_ioc_setattr_more(struct file *file, unsigned long arg)
 	if (sm.flags & SCOUTFS_IOC_SETATTR_MORE_OFFLINE)
 		iax->x_flags |= SCOUTFS_IOC_IAX_F_SIZE_OFFLINE;
 
+	if (sm.data_version != 0)
+		iax->x_mask |= SCOUTFS_IOC_IAX_DATA_VERSION;
+
 	ret = mnt_want_write_file(file);
 	if (ret < 0)
 		goto out;
@@ -713,7 +722,8 @@ static long scoutfs_ioc_listxattr_hidden(struct file *file, unsigned long arg)
 	int total = 0;
 	int ret;
 
-	ret = inode_permission(inode, MAY_READ);
+	ret = inode_permission(KC_VFS_INIT_NS
+			       inode, MAY_READ);
 	if (ret < 0)
 		goto out;
 
@@ -951,6 +961,7 @@ static long scoutfs_ioc_move_blocks(struct file *file, unsigned long arg)
 	struct scoutfs_ioctl_move_blocks mb;
 	struct file *from_file;
 	struct inode *from;
+	u64 tmp;
 	int ret;
 
 	if (copy_from_user(&mb, umb, sizeof(mb)))
@@ -959,8 +970,8 @@ static long scoutfs_ioc_move_blocks(struct file *file, unsigned long arg)
 	if (mb.len == 0)
 		return 0;
 
-	if (mb.from_off + mb.len < mb.from_off ||
-	    mb.to_off + mb.len < mb.to_off)
+	if ((check_add_overflow(mb.from_off, mb.len - 1, &tmp)) ||
+	    (check_add_overflow(mb.to_off, mb.len - 1, &tmp)))
 		return -EOVERFLOW;
 
 	from_file = fget(mb.from_fd);

kmod/src/item.c

@@ -2241,18 +2241,18 @@ u64 scoutfs_item_dirty_pages(struct super_block *sb)
 	return (u64)atomic_read(&cinf->dirty_pages);
 }
 
-static int cmp_pg_start(void *priv, struct list_head *A, struct list_head *B)
+static int cmp_pg_start(void *priv, KC_LIST_CMP_CONST struct list_head *A, KC_LIST_CMP_CONST struct list_head *B)
 {
-	struct cached_page *a = list_entry(A, struct cached_page, dirty_head);
-	struct cached_page *b = list_entry(B, struct cached_page, dirty_head);
+	KC_LIST_CMP_CONST struct cached_page *a = list_entry(A, KC_LIST_CMP_CONST struct cached_page, dirty_head);
+	KC_LIST_CMP_CONST struct cached_page *b = list_entry(B, KC_LIST_CMP_CONST struct cached_page, dirty_head);
 
 	return scoutfs_key_compare(&a->start, &b->start);
 }
 
-static int cmp_item_key(void *priv, struct list_head *A, struct list_head *B)
+static int cmp_item_key(void *priv, KC_LIST_CMP_CONST struct list_head *A, KC_LIST_CMP_CONST struct list_head *B)
 {
-	struct cached_item *a = list_entry(A, struct cached_item, dirty_head);
-	struct cached_item *b = list_entry(B, struct cached_item, dirty_head);
+	KC_LIST_CMP_CONST struct cached_item *a = list_entry(A, KC_LIST_CMP_CONST struct cached_item, dirty_head);
+	KC_LIST_CMP_CONST struct cached_item *b = list_entry(B, KC_LIST_CMP_CONST struct cached_item, dirty_head);
 
 	return scoutfs_key_compare(&a->key, &b->key);
 }
@@ -2693,7 +2693,7 @@ int scoutfs_item_setup(struct super_block *sb)
 
 	KC_INIT_SHRINKER_FUNCS(&cinf->shrinker, item_cache_count_objects,
 			       item_cache_scan_objects);
-	KC_REGISTER_SHRINKER(&cinf->shrinker);
+	KC_REGISTER_SHRINKER(&cinf->shrinker, "scoutfs-item:" SCSBF, SCSB_ARGS(sb));
 #ifdef KC_CPU_NOTIFIER
         cinf->notifier.notifier_call = item_cpu_callback;
         register_hotcpu_notifier(&cinf->notifier);

kmod/src/kernelcompat.c

@@ -67,12 +67,11 @@ kc_generic_file_buffered_write(struct kiocb *iocb, const struct iovec *iov,
 			       unsigned long nr_segs, loff_t pos, loff_t *ppos,
 			       size_t count, ssize_t written)
 {
-	struct file *file = iocb->ki_filp;
 	ssize_t status;
 	struct iov_iter i;
 
 	iov_iter_init(&i, WRITE, iov, nr_segs, count);
-	status = generic_perform_write(file, &i, pos);
+	status = kc_generic_perform_write(iocb, &i, pos);
 
 	if (likely(status >= 0)) {
 		written += status;

kmod/src/kernelcompat.h

@@ -197,7 +197,11 @@ struct timespec64 kc_current_time(struct inode *inode);
 } while (0)
 
 #define KC_SHRINKER_CONTAINER_OF(ptr, type) container_of(ptr, type, shrinker)
-#define KC_REGISTER_SHRINKER(ptr) (register_shrinker(ptr))
+#ifdef KC_SHRINKER_NAME
+#define KC_REGISTER_SHRINKER register_shrinker
+#else
+#define KC_REGISTER_SHRINKER(ptr, fmt, ...) (register_shrinker(ptr))
+#endif /* KC_SHRINKER_NAME */
 #define KC_UNREGISTER_SHRINKER(ptr) (unregister_shrinker(ptr))
 #define KC_SHRINKER_FN(ptr) (ptr)
 #else
@@ -224,7 +228,7 @@ struct kc_shrinker_wrapper {
 	_wrap->shrink.seeks = DEFAULT_SEEKS;			\
 } while (0)
 #define KC_SHRINKER_CONTAINER_OF(ptr, type) container_of(container_of(ptr, struct kc_shrinker_wrapper, shrink), type, shrinker)
-#define KC_REGISTER_SHRINKER(ptr) (register_shrinker(ptr.shrink))
+#define KC_REGISTER_SHRINKER(ptr, fmt, ...) (register_shrinker(ptr.shrink))
 #define KC_UNREGISTER_SHRINKER(ptr) (unregister_shrinker(ptr.shrink))
 #define KC_SHRINKER_FN(ptr) (ptr.shrink)
 
@@ -271,6 +275,167 @@ ssize_t kc_generic_file_buffered_write(struct kiocb *iocb, const struct iovec *i
                unsigned long nr_segs, loff_t pos, loff_t *ppos,
                size_t count, ssize_t written);
 #define generic_file_buffered_write kc_generic_file_buffered_write
+#ifdef KC_GENERIC_PERFORM_WRITE_KIOCB_IOV_ITER
+static inline int kc_generic_perform_write(struct kiocb *iocb, struct iov_iter *iter, loff_t pos)
+{
+	iocb->ki_pos = pos;
+	return generic_perform_write(iocb, iter);
+}
+#else
+static inline int kc_generic_perform_write(struct kiocb *iocb, struct iov_iter *iter, loff_t pos)
+{
+	struct file *file = iocb->ki_filp;
+	return generic_perform_write(file, iter, pos);
+}
+#endif
+#endif // KC_GENERIC_FILE_BUFFERED_WRITE
+
+#ifndef KC_HAVE_BLK_OPF_T
+/* typedef __u32 __bitwise blk_opf_t; */
+typedef unsigned int blk_opf_t;
+#endif
+
+#ifdef KC_LIST_CMP_CONST_ARG_LIST_HEAD
+#define KC_LIST_CMP_CONST const
+#else
+#define KC_LIST_CMP_CONST
+#endif
+
+#ifdef KC_VMALLOC_PGPROT_T
+#define kc__vmalloc(size, gfp_mask) __vmalloc(size, gfp_mask, PAGE_KERNEL)
+#else
+#define kc__vmalloc __vmalloc
+#endif
+
+#ifdef KC_VFS_METHOD_USER_NAMESPACE_ARG
+#define KC_VFS_NS_DEF struct user_namespace *mnt_user_ns,
+#define KC_VFS_NS mnt_user_ns,
+#define KC_VFS_INIT_NS &init_user_ns,
+#else
+#define KC_VFS_NS_DEF
+#define KC_VFS_NS
+#define KC_VFS_INIT_NS
+#endif
+
+#ifdef KC_BIO_ALLOC_DEV_OPF_ARGS
+#define kc_bio_alloc bio_alloc
+#else
+#include <linux/bio.h>
+static inline struct bio *kc_bio_alloc(struct block_device *bdev, unsigned short nr_vecs,
+				       blk_opf_t opf, gfp_t gfp_mask)
+{
+	struct bio *b = bio_alloc(gfp_mask, nr_vecs);
+	if (b) {
+		kc_bio_set_opf(b, opf);
+		bio_set_dev(b, bdev);
+	}
+	return b;
+}
+#endif
+
+#ifndef KC_FIEMAP_PREP
+#define fiemap_prep(inode, fieinfo, start, len, flags) fiemap_check_flags(fieinfo, flags)
+#endif
+
+#ifndef KC_KERNEL_OLD_TIMEVAL_STRUCT
+#define __kernel_old_timeval timeval
+#define ns_to_kernel_old_timeval(ktime) ns_to_timeval(ktime.tv64)
+#endif
+
+#ifdef KC_SOCK_SET_SNDTIMEO
+#include <net/sock.h>
+static inline int kc_sock_set_sndtimeo(struct socket *sock, s64 secs)
+{
+	sock_set_sndtimeo(sock->sk, secs);
+	return 0;
+}
+static inline int kc_tcp_sock_set_rcvtimeo(struct socket *sock, ktime_t to)
+{
+	struct __kernel_old_timeval tv;
+	sockptr_t kopt;
+
+	tv = ns_to_kernel_old_timeval(to);
+
+	kopt = KERNEL_SOCKPTR(&tv);
+
+	return sock_setsockopt(sock, SOL_SOCKET, SO_RCVTIMEO_NEW,
+			       kopt, sizeof(tv));
+}
+#else
+#include <net/sock.h>
+static inline int kc_sock_set_sndtimeo(struct socket *sock, s64 secs)
+{
+	struct timeval tv = { .tv_sec = secs, .tv_usec = 0 };
+	return kernel_setsockopt(sock, SOL_SOCKET, SO_SNDTIMEO,
+				 (char *)&tv, sizeof(tv));
+}
+static inline int kc_tcp_sock_set_rcvtimeo(struct socket *sock, ktime_t to)
+{
+	struct __kernel_old_timeval tv;
+
+	tv = ns_to_kernel_old_timeval(to);
+	return kernel_setsockopt(sock, SOL_SOCKET, SO_RCVTIMEO,
+				 (char *)&tv, sizeof(tv));
+}
+#endif
+
+#ifdef KC_SETSOCKOPT_SOCKPTR_T
+static inline int kc_sock_setsockopt(struct socket *sock, int level, int op, int *optval, unsigned int optlen)
+{
+	sockptr_t kopt = KERNEL_SOCKPTR(optval);
+	return sock_setsockopt(sock, level, op, kopt, sizeof(optval));
+}
+#else
+static inline int kc_sock_setsockopt(struct socket *sock, int level, int op, int *optval, unsigned int optlen)
+{
+	return kernel_setsockopt(sock, level, op, (char *)optval, sizeof(optval));
+}
+#endif
+
+#ifdef KC_HAVE_TCP_SET_SOCKFN
+#include <linux/net.h>
+#include <net/tcp.h>
+static inline int kc_tcp_sock_set_keepintvl(struct socket *sock, int val)
+{
+	return tcp_sock_set_keepintvl(sock->sk, val);
+}
+static inline int kc_tcp_sock_set_keepidle(struct socket *sock, int val)
+{
+	return tcp_sock_set_keepidle(sock->sk, val);
+}
+static inline int kc_tcp_sock_set_user_timeout(struct socket *sock, int val)
+{
+	tcp_sock_set_user_timeout(sock->sk, val);
+	return 0;
+}
+static inline int kc_tcp_sock_set_nodelay(struct socket *sock)
+{
+	tcp_sock_set_nodelay(sock->sk);
+	return 0;
+}
+#else
+#include <linux/net.h>
+#include <net/tcp.h>
+static inline int kc_tcp_sock_set_keepintvl(struct socket *sock, int val)
+{
+	int optval = val;
+	return kernel_setsockopt(sock, SOL_TCP, TCP_KEEPINTVL, (char *)&optval, sizeof(optval));
+}
+static inline int kc_tcp_sock_set_keepidle(struct socket *sock, int val)
+{
+	int optval = val;
+	return kernel_setsockopt(sock, SOL_TCP, TCP_KEEPIDLE, (char *)&optval, sizeof(optval));
+}
+static inline int kc_tcp_sock_set_user_timeout(struct socket *sock, int val)
+{
+	int optval = val;
+	return kernel_setsockopt(sock, SOL_TCP, TCP_USER_TIMEOUT, (char *)&optval, sizeof(optval));
+}
+static inline int kc_tcp_sock_set_nodelay(struct socket *sock)
+{
+	int optval = 1;
+	return kernel_setsockopt(sock, SOL_TCP, TCP_NODELAY, (char *)&optval, sizeof(optval));
+}
 #endif
 
 #endif

kmod/src/key.h

@@ -125,8 +125,8 @@ static inline bool scoutfs_key_is_ones(struct scoutfs_key *key)
  * other alternatives across keys that first differ in any of the
  * values.  Say maybe 20% faster than memcmp.
  */
-static inline int scoutfs_key_compare(struct scoutfs_key *a,
-				      struct scoutfs_key *b)
+static inline int scoutfs_key_compare(const struct scoutfs_key *a,
+				      const struct scoutfs_key *b)
 {
 	return scoutfs_cmp(a->sk_zone, b->sk_zone) ?:
 	  scoutfs_cmp(le64_to_cpu(a->_sk_first), le64_to_cpu(b->_sk_first)) ?:
@@ -142,10 +142,10 @@ static inline int scoutfs_key_compare(struct scoutfs_key *a,
  *       1: a_start > b_end
  *  else 0: ranges overlap
  */
-static inline int scoutfs_key_compare_ranges(struct scoutfs_key *a_start,
-				             struct scoutfs_key *a_end,
-				             struct scoutfs_key *b_start,
-				             struct scoutfs_key *b_end)
+static inline int scoutfs_key_compare_ranges(const struct scoutfs_key *a_start,
+				             const struct scoutfs_key *a_end,
+				             const struct scoutfs_key *b_start,
+				             const struct scoutfs_key *b_end)
 {
 	return scoutfs_key_compare(a_end, b_start) < 0 ? -1 :
 	       scoutfs_key_compare(a_start, b_end) > 0 ? 1 :

kmod/src/lock.c

@@ -1732,7 +1732,7 @@ int scoutfs_lock_setup(struct super_block *sb)
 	linfo->lock_range_tree = RB_ROOT;
 	KC_INIT_SHRINKER_FUNCS(&linfo->shrinker, lock_count_objects,
 			       lock_scan_objects);
-	KC_REGISTER_SHRINKER(&linfo->shrinker);
+	KC_REGISTER_SHRINKER(&linfo->shrinker, "scoutfs-lock:" SCSBF, SCSB_ARGS(sb));
 	INIT_LIST_HEAD(&linfo->lru_list);
 	INIT_WORK(&linfo->inv_work, lock_invalidate_worker);
 	INIT_LIST_HEAD(&linfo->inv_list);

kmod/src/lock_server.c

@@ -202,21 +202,48 @@ static u8 invalidation_mode(u8 granted, u8 requested)
 
 /*
  * Return true of the client lock instances described by the entries can
- * be granted at the same time.  Typically this only means they're both
- * modes that are compatible between nodes. In addition there's the
- * special case where a read lock on a client is compatible with a write
- * lock on the same client because the client's cache covered by the
- * read lock is still valid if they get a write lock.
+ * be granted at the same time.  There's only three cases where this is
+ * true.
+ *
+ * First, the two locks are both of the same mode that allows full
+ * sharing -- read and write only.  The only point of these modes is
+ * that everyone can share them.
+ *
+ * Second, a write lock gives the client permission to read as well.
+ * This means that a client can upgrade its read lock to a write lock
+ * without having to invalidate the existing read and drop caches.
+ *
+ * Third, null locks are always compatible between clients.  It's as
+ * though the client with the null lock has no lock at all.  But it's
+ * never compatible with all locks on the client requesting null.
+ * Sending invalidations for existing locks on a client when we get a
+ * null request is how we resolve races in shrinking locks -- we turn it
+ * into the unsolicited remote invalidation case.
+ *
+ * All other mode and client combinations can not be shared, most
+ * typically a write lock invalidating all other non-write holders to
+ * drop caches and force a read after the write has completed.
  */
 static bool client_entries_compatible(struct client_lock_entry *granted,
 				      struct client_lock_entry *requested)
 {
-	return (granted->mode == requested->mode &&
-		(granted->mode == SCOUTFS_LOCK_READ ||
-		 granted->mode == SCOUTFS_LOCK_WRITE_ONLY)) ||
-	       (granted->rid == requested->rid &&
-		granted->mode == SCOUTFS_LOCK_READ &&
-		requested->mode == SCOUTFS_LOCK_WRITE);
+	/* only read and write_only can be full shared */
+	if ((granted->mode == requested->mode) &&
+	    (granted->mode == SCOUTFS_LOCK_READ || granted->mode == SCOUTFS_LOCK_WRITE_ONLY))
+		return true;
+
+	/* _write includes reading, so a client can upgrade its read to write */
+	if (granted->rid == requested->rid &&
+	    granted->mode == SCOUTFS_LOCK_READ &&
+	    requested->mode == SCOUTFS_LOCK_WRITE)
+		return true;
+
+	/* null is always compatible across clients, never within a client */
+	if ((granted->rid != requested->rid) &&
+	    (granted->mode == SCOUTFS_LOCK_NULL || requested->mode == SCOUTFS_LOCK_NULL))
+		return true;
+
+	return false;
 }
 
 /*
@@ -317,16 +344,18 @@ static void put_server_lock(struct lock_server_info *inf,
 
 	BUG_ON(!mutex_is_locked(&snode->mutex));
 
+	spin_lock(&inf->lock);
+
 	if (atomic_dec_and_test(&snode->refcount) &&
 	    list_empty(&snode->granted) &&
 	    list_empty(&snode->requested) &&
 	    list_empty(&snode->invalidated)) {
-		spin_lock(&inf->lock);
 		rb_erase(&snode->node, &inf->locks_root);
-		spin_unlock(&inf->lock);
 		should_free = true;
 	}
 
+	spin_unlock(&inf->lock);
+
 	mutex_unlock(&snode->mutex);
 
 	if (should_free) {

kmod/src/net.c

@@ -502,12 +502,12 @@ static void scoutfs_net_proc_worker(struct work_struct *work)
  * Free live responses up to and including the seq by marking them dead
  * and moving them to the send queue to be freed.
  */
-static int move_acked_responses(struct scoutfs_net_connection *conn,
-				struct list_head *list, u64 seq)
+static bool move_acked_responses(struct scoutfs_net_connection *conn,
+				 struct list_head *list, u64 seq)
 {
 	struct message_send *msend;
 	struct message_send *tmp;
-	int ret = 0;
+	bool moved = false;
 
 	assert_spin_locked(&conn->lock);
 
@@ -519,20 +519,20 @@ static int move_acked_responses(struct scoutfs_net_connection *conn,
 
 		msend->dead = 1;
 		list_move(&msend->head, &conn->send_queue);
-		ret = 1;
+		moved = true;
 	}
 
-	return ret;
+	return moved;
 }
 
 /* acks are processed inline in the recv worker */
 static void free_acked_responses(struct scoutfs_net_connection *conn, u64 seq)
 {
-	int moved;
+	bool moved;
 
 	spin_lock(&conn->lock);
 
-	moved = move_acked_responses(conn, &conn->send_queue, seq) +
+	moved = move_acked_responses(conn, &conn->send_queue, seq) |
 		move_acked_responses(conn, &conn->resend_queue, seq);
 
 	spin_unlock(&conn->lock);
@@ -904,53 +904,44 @@ static void destroy_conn(struct scoutfs_net_connection *conn)
 static int sock_opts_and_names(struct scoutfs_net_connection *conn,
 			       struct socket *sock)
 {
-	struct timeval tv;
 	int optval;
 	int ret;
 
 	/* we use a keepalive timeout instead of send timeout */
-	tv.tv_sec = 0;
-	tv.tv_usec = 0;
-	ret = kernel_setsockopt(sock, SOL_SOCKET, SO_SNDTIMEO,
-				(char *)&tv, sizeof(tv));
+	ret = kc_sock_set_sndtimeo(sock, 0);
 	if (ret)
 		goto out;
 
 	/* not checked when user_timeout != 0, but for clarity */
 	optval = UNRESPONSIVE_PROBES;
-	ret = kernel_setsockopt(sock, SOL_TCP, TCP_KEEPCNT,
-				(char *)&optval, sizeof(optval));
+	ret = kc_sock_setsockopt(sock, SOL_TCP, TCP_KEEPCNT,
+				&optval, sizeof(optval));
 	if (ret)
 		goto out;
 
 	BUILD_BUG_ON(UNRESPONSIVE_PROBES >= UNRESPONSIVE_TIMEOUT_SECS);
 	optval = UNRESPONSIVE_TIMEOUT_SECS - (UNRESPONSIVE_PROBES);
-	ret = kernel_setsockopt(sock, SOL_TCP, TCP_KEEPIDLE,
-				(char *)&optval, sizeof(optval));
+	ret = kc_tcp_sock_set_keepidle(sock, optval);
 	if (ret)
 		goto out;
 
 	optval = 1;
-	ret = kernel_setsockopt(sock, SOL_TCP, TCP_KEEPINTVL,
-				(char *)&optval, sizeof(optval));
+	ret = kc_tcp_sock_set_keepintvl(sock, optval);
 	if (ret)
 		goto out;
 
 	optval = UNRESPONSIVE_TIMEOUT_SECS * MSEC_PER_SEC;
-	ret = kernel_setsockopt(sock, SOL_TCP, TCP_USER_TIMEOUT,
-				(char *)&optval, sizeof(optval));
+	ret = kc_tcp_sock_set_user_timeout(sock, optval);
 	if (ret)
 		goto out;
 
 	optval = 1;
-	ret = kernel_setsockopt(sock, SOL_SOCKET, SO_KEEPALIVE,
-				(char *)&optval, sizeof(optval));
+	ret = kc_sock_setsockopt(sock, SOL_SOCKET, SO_KEEPALIVE,
+				&optval, sizeof(optval));
 	if (ret)
 		goto out;
 
-	optval = 1;
-	ret = kernel_setsockopt(sock, SOL_TCP, TCP_NODELAY,
-				(char *)&optval, sizeof(optval));
+	ret = kc_tcp_sock_set_nodelay(sock);
 	if (ret)
 		goto out;
 
@@ -1049,7 +1040,6 @@ static void scoutfs_net_connect_worker(struct work_struct *work)
 	DEFINE_CONN_FROM_WORK(conn, work, connect_work);
 	struct super_block *sb = conn->sb;
 	struct socket *sock;
-	struct timeval tv;
 	int ret;
 
 	trace_scoutfs_net_connect_work_enter(sb, 0, 0);
@@ -1060,11 +1050,8 @@ static void scoutfs_net_connect_worker(struct work_struct *work)
 
 	sock->sk->sk_allocation = GFP_NOFS;
 
-	/* caller specified connect timeout */
-	tv.tv_sec = conn->connect_timeout_ms / MSEC_PER_SEC;
-	tv.tv_usec = (conn->connect_timeout_ms % MSEC_PER_SEC) * USEC_PER_MSEC;
-	ret = kernel_setsockopt(sock, SOL_SOCKET, SO_SNDTIMEO,
-				(char *)&tv, sizeof(tv));
+	/* caller specified connect timeout, defaults to 1 sec */
+	ret = kc_sock_set_sndtimeo(sock, conn->connect_timeout_ms / MSEC_PER_SEC);
 	if (ret) {
 		sock_release(sock);
 		goto out;
@@ -1462,8 +1449,8 @@ int scoutfs_net_bind(struct super_block *sb,
 	sock->sk->sk_allocation = GFP_NOFS;
 
 	optval = 1;
-	ret = kernel_setsockopt(sock, SOL_SOCKET, SO_REUSEADDR,
-				(char *)&optval, sizeof(optval));
+	ret = kc_sock_setsockopt(sock, SOL_SOCKET, SO_REUSEADDR,
+				&optval, sizeof(optval));
 	if (ret)
 		goto out;
 

kmod/src/quorum.c

@@ -303,7 +303,6 @@ static int recv_msg(struct super_block *sb, struct quorum_host_msg *msg,
 	DECLARE_QUORUM_INFO(sb, qinf);
 	struct scoutfs_sb_info *sbi = SCOUTFS_SB(sb);
 	struct scoutfs_quorum_message qmes;
-	struct timeval tv;
 	ktime_t rel_to;
 	ktime_t now;
 	int ret;
@@ -328,14 +327,10 @@ static int recv_msg(struct super_block *sb, struct quorum_host_msg *msg,
 	else
 		rel_to = ns_to_ktime(0);
 
-	tv = ktime_to_timeval(rel_to);
-	if (tv.tv_sec == 0 && tv.tv_usec == 0) {
+	if (ktime_compare(rel_to, ns_to_ktime(NSEC_PER_USEC)) <= 0) {
 		mh.msg_flags |= MSG_DONTWAIT;
 	} else {
-		ret = kernel_setsockopt(qinf->sock, SOL_SOCKET, SO_RCVTIMEO,
-					(char *)&tv, sizeof(tv));
-		if (ret < 0)
-			return ret;
+		ret = kc_tcp_sock_set_rcvtimeo(qinf->sock, rel_to);
 	}
 
 #ifdef KC_MSGHDR_STRUCT_IOV_ITER
@@ -486,7 +481,7 @@ static void set_quorum_block_event(struct super_block *sb, struct scoutfs_quorum
 	if (WARN_ON_ONCE(event < 0 || event >= SCOUTFS_QUORUM_EVENT_NR))
 		return;
 
-	getnstimeofday64(&ts);
+	ktime_get_ts64(&ts);
 	le64_add_cpu(&blk->write_nr, 1);
 
 	ev = &blk->events[event];
@@ -1325,8 +1320,8 @@ int scoutfs_quorum_setup(struct super_block *sb)
 	qinf = kzalloc(sizeof(struct quorum_info), GFP_KERNEL);
 	super = kmalloc(sizeof(struct scoutfs_super_block), GFP_KERNEL);
 	if (qinf)
-		qinf->hb_delay = __vmalloc(HB_DELAY_NR * sizeof(struct count_recent),
-					   GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
+		qinf->hb_delay = kc__vmalloc(HB_DELAY_NR * sizeof(struct count_recent),
+					   GFP_KERNEL | __GFP_ZERO);
 	if (!qinf || !super || !qinf->hb_delay) {
 		if (qinf)
 			vfree(qinf->hb_delay);

kmod/src/quota.c

@@ -1226,7 +1226,7 @@ int scoutfs_quota_setup(struct super_block *sb)
 	init_waitqueue_head(&qtinf->waitq);
 
 	KC_INIT_SHRINKER_FUNCS(&qtinf->shrinker, count_cached_checks, scan_cached_checks);
-	KC_REGISTER_SHRINKER(&qtinf->shrinker);
+	KC_REGISTER_SHRINKER(&qtinf->shrinker, "scoutfs-quota:" SCSBF, SCSB_ARGS(sb));
 
 	sbi->squota_info = qtinf;
 

kmod/src/recov.c

@@ -76,10 +76,10 @@ static struct recov_pending *lookup_pending(struct recov_info *recinf, u64 rid,
  * We keep the pending list sorted by rid so that we can iterate over
  * them.  The list should be small and shouldn't be used often.
  */
-static int cmp_pending_rid(void *priv, struct list_head *A, struct list_head *B)
+static int cmp_pending_rid(void *priv, KC_LIST_CMP_CONST struct list_head *A, KC_LIST_CMP_CONST struct list_head *B)
 {
-	struct recov_pending *a = list_entry(A, struct recov_pending, head);
-	struct recov_pending *b = list_entry(B, struct recov_pending, head);
+	KC_LIST_CMP_CONST struct recov_pending *a = list_entry(A, KC_LIST_CMP_CONST struct recov_pending, head);
+	KC_LIST_CMP_CONST struct recov_pending *b = list_entry(B, KC_LIST_CMP_CONST struct recov_pending, head);
 
 	return scoutfs_cmp_u64s(a->rid, b->rid);
 }

kmod/src/scoutfs_trace.h

@@ -24,7 +24,6 @@
 
 #include <linux/tracepoint.h>
 #include <linux/in.h>
-#include <linux/unaligned/access_ok.h>
 
 #include "key.h"
 #include "format.h"
@@ -1047,9 +1046,12 @@ DECLARE_EVENT_CLASS(scoutfs_lock_class,
 		sk_trace_define(start)
 		sk_trace_define(end)
 		__field(u64, refresh_gen)
+		__field(u64, write_seq)
+		__field(u64, dirty_trans_seq)
 		__field(unsigned char, request_pending)
 		__field(unsigned char, invalidate_pending)
 		__field(int, mode)
+		__field(int, invalidating_mode)
 		__field(unsigned int, waiters_cw)
 		__field(unsigned int, waiters_pr)
 		__field(unsigned int, waiters_ex)
@@ -1062,9 +1064,12 @@ DECLARE_EVENT_CLASS(scoutfs_lock_class,
 		sk_trace_assign(start, &lck->start);
 		sk_trace_assign(end, &lck->end);
 		__entry->refresh_gen = lck->refresh_gen;
+		__entry->write_seq = lck->write_seq;
+		__entry->dirty_trans_seq = lck->dirty_trans_seq;
 		__entry->request_pending = lck->request_pending;
 		__entry->invalidate_pending = lck->invalidate_pending;
 		__entry->mode = lck->mode;
+		__entry->invalidating_mode = lck->invalidating_mode;
 		__entry->waiters_pr = lck->waiters[SCOUTFS_LOCK_READ];
 		__entry->waiters_ex = lck->waiters[SCOUTFS_LOCK_WRITE];
 		__entry->waiters_cw = lck->waiters[SCOUTFS_LOCK_WRITE_ONLY];
@@ -1072,10 +1077,11 @@ DECLARE_EVENT_CLASS(scoutfs_lock_class,
 		__entry->users_ex = lck->users[SCOUTFS_LOCK_WRITE];
 		__entry->users_cw = lck->users[SCOUTFS_LOCK_WRITE_ONLY];
         ),
-        TP_printk(SCSBF" start "SK_FMT" end "SK_FMT" mode %u reqpnd %u invpnd %u rfrgen %llu waiters: pr %u ex %u cw %u users: pr %u ex %u cw %u",
+        TP_printk(SCSBF" start "SK_FMT" end "SK_FMT" mode %u invmd %u reqp %u invp %u refg %llu wris %llu dts %llu waiters: pr %u ex %u cw %u users: pr %u ex %u cw %u",
 		  SCSB_TRACE_ARGS, sk_trace_args(start), sk_trace_args(end),
-		  __entry->mode, __entry->request_pending,
-		  __entry->invalidate_pending, __entry->refresh_gen,
+		  __entry->mode, __entry->invalidating_mode, __entry->request_pending,
+		  __entry->invalidate_pending, __entry->refresh_gen, __entry->write_seq,
+		  __entry->dirty_trans_seq,
 		  __entry->waiters_pr, __entry->waiters_ex, __entry->waiters_cw,
 		  __entry->users_pr, __entry->users_ex, __entry->users_cw)
 );

kmod/src/server.c

@@ -298,7 +298,7 @@ static void check_holder_budget(struct super_block *sb, struct server_info *serv
 {
 	static bool exceeded_once = false;
 	struct commit_hold *hold;
-	struct timespec ts;
+	struct timespec64 ts;
 	u32 avail_used;
 	u32 freed_used;
 	u32 avail_now;
@@ -330,7 +330,7 @@ static void check_holder_budget(struct super_block *sb, struct server_info *serv
 		    cusers->freed_before, freed_now);
 
 	list_for_each_entry(hold, &cusers->holding, entry) {
-		ts = ktime_to_timespec(hold->start);
+		ts = ktime_to_timespec64(hold->start);
 		scoutfs_err(sb, "exceeding hold start %llu.%09llu av %u fr %u",
 			    (u64)ts.tv_sec, (u64)ts.tv_nsec, hold->avail, hold->freed);
 		hold->exceeded = true;
@@ -445,7 +445,7 @@ static int server_apply_commit(struct super_block *sb, struct commit_hold *hold,
 {
 	DECLARE_SERVER_INFO(sb, server);
 	struct commit_users *cusers = &server->cusers;
-	struct timespec ts;
+	struct timespec64 ts;
 
 	spin_lock(&cusers->lock);
 
@@ -454,7 +454,7 @@ static int server_apply_commit(struct super_block *sb, struct commit_hold *hold,
 	check_holder_budget(sb, server, cusers);
 
 	if (hold->exceeded) {
-		ts = ktime_to_timespec(hold->start);
+		ts = ktime_to_timespec64(hold->start);
 		scoutfs_err(sb, "exceeding hold start %llu.%09llu stack:",
 			    (u64)ts.tv_sec, (u64)ts.tv_nsec);
 		dump_stack();
@@ -668,14 +668,16 @@ static void scoutfs_server_commit_func(struct work_struct *work)
 	 * the reserved blocks after having filled the log trees's avail
 	 * allocator during its transaction.  To avoid prematurely
 	 * setting the low flag and causing enospc we make sure that the
-	 * next transaction's meta_avail has 2x the reserved blocks so
+	 * next transaction's meta_avail has 3x the reserved blocks so
 	 * that it can consume a full reserved amount and still have
 	 * enough to avoid enospc.  We swap to freed if avail is under
-	 * the buffer and freed is larger.
+	 * the buffer and freed is larger by 50%. This results in much less
+	 * swapping overall and allows the pools to refill naturally.
 	 */
 	if ((le64_to_cpu(server->meta_avail->total_len) <
-	     (scoutfs_server_reserved_meta_blocks(sb) * 2)) &&
-	    (le64_to_cpu(server->meta_freed->total_len) >
+	     (scoutfs_server_reserved_meta_blocks(sb) * 3)) &&
+	    ((le64_to_cpu(server->meta_freed->total_len) +
+	     (le64_to_cpu(server->meta_freed->total_len) >> 1)) >
 	     le64_to_cpu(server->meta_avail->total_len)))
 		swap(server->meta_avail, server->meta_freed);
 

kmod/src/srch.c

@@ -18,6 +18,7 @@
 #include <linux/pagemap.h>
 #include <linux/vmalloc.h>
 #include <linux/sort.h>
+#include <asm/unaligned.h>
 
 #include "super.h"
 #include "format.h"
@@ -1588,8 +1589,7 @@ static int kway_merge(struct super_block *sb,
 	nr_parents = max_t(unsigned long, 1, roundup_pow_of_two(nr) - 1);
 	/* root at [1] for easy sib/parent index calc, final pad for odd sib */
 	nr_nodes = 1 + nr_parents + nr + 1;
-	tnodes = __vmalloc(nr_nodes * sizeof(struct tourn_node),
-			   GFP_NOFS, PAGE_KERNEL);
+	tnodes = kc__vmalloc(nr_nodes * sizeof(struct tourn_node), GFP_NOFS);
 	if (!tnodes)
 		return -ENOMEM;
 

kmod/src/super.c

@@ -160,7 +160,17 @@ static void scoutfs_metadev_close(struct super_block *sb)
 		 * from kill_sb->put_super.
 		 */
 		lockdep_off();
+
+#ifdef KC_BDEV_FILE_OPEN_BY_PATH
+		bdev_fput(sbi->meta_bdev_file);
+#else
+#ifdef KC_BLKDEV_PUT_HOLDER_ARG
+		blkdev_put(sbi->meta_bdev, sb);
+#else
 		blkdev_put(sbi->meta_bdev, SCOUTFS_META_BDEV_MODE);
+#endif
+#endif
+
 		lockdep_on();
 		sbi->meta_bdev = NULL;
 	}
@@ -477,7 +487,11 @@ out:
 static int scoutfs_fill_super(struct super_block *sb, void *data, int silent)
 {
 	struct scoutfs_mount_options opts;
+#ifdef KC_BDEV_FILE_OPEN_BY_PATH
+	struct file *meta_bdev_file;
+#else
 	struct block_device *meta_bdev;
+#endif
 	struct scoutfs_sb_info *sbi;
 	struct inode *inode;
 	int ret;
@@ -523,7 +537,27 @@ static int scoutfs_fill_super(struct super_block *sb, void *data, int silent)
 		goto out;
 	}
 
+#ifdef KC_BDEV_FILE_OPEN_BY_PATH
+	/*
+	 * pass sbi as holder, since dev_mount already passes sb, which triggers a
+	 * WARN_ON because dev_mount also passes non-NULL hops. By passing sbi
+	 * here we just get a simple error in our test cases.
+	 */
+	meta_bdev_file = bdev_file_open_by_path(opts.metadev_path, SCOUTFS_META_BDEV_MODE, sbi, NULL);
+	if (IS_ERR(meta_bdev_file)) {
+		scoutfs_err(sb, "could not open metadev: error %ld",
+			    PTR_ERR(meta_bdev_file));
+		ret = PTR_ERR(meta_bdev_file);
+		goto out;
+	}
+	sbi->meta_bdev_file = meta_bdev_file;
+	sbi->meta_bdev = file_bdev(meta_bdev_file);
+#else
+#ifdef KC_BLKDEV_PUT_HOLDER_ARG
+	meta_bdev = blkdev_get_by_path(opts.metadev_path, SCOUTFS_META_BDEV_MODE, sb, NULL);
+#else
 	meta_bdev = blkdev_get_by_path(opts.metadev_path, SCOUTFS_META_BDEV_MODE, sb);
+#endif
 	if (IS_ERR(meta_bdev)) {
 		scoutfs_err(sb, "could not open metadev: error %ld",
 			    PTR_ERR(meta_bdev));
@@ -531,6 +565,8 @@ static int scoutfs_fill_super(struct super_block *sb, void *data, int silent)
 		goto out;
 	}
 	sbi->meta_bdev = meta_bdev;
+#endif
+
 	ret = set_blocksize(sbi->meta_bdev, SCOUTFS_BLOCK_SM_SIZE);
 	if (ret != 0) {
 		scoutfs_err(sb, "failed to set metadev blocksize, returned %d",

kmod/src/super.h

@@ -42,6 +42,9 @@ struct scoutfs_sb_info {
 	u64 fmt_vers;
 
 	struct block_device *meta_bdev;
+#ifdef KC_BDEV_FILE_OPEN_BY_PATH
+	struct file *meta_bdev_file;
+#endif
 
 	spinlock_t next_ino_lock;
 
@@ -101,7 +104,11 @@ static inline bool SCOUTFS_IS_META_BDEV(struct scoutfs_super_block *super_block)
 	return !!(le64_to_cpu(super_block->flags) & SCOUTFS_FLAG_IS_META_BDEV);
 }
 
+#ifdef KC_HAVE_BLK_MODE_T
+#define SCOUTFS_META_BDEV_MODE (BLK_OPEN_READ | BLK_OPEN_WRITE | BLK_OPEN_EXCL)
+#else
 #define SCOUTFS_META_BDEV_MODE (FMODE_READ | FMODE_WRITE | FMODE_EXCL)
+#endif
 
 static inline bool scoutfs_forcing_unmount(struct super_block *sb)
 {

kmod/src/sysfs.c

@@ -13,6 +13,7 @@
 #include <linux/kernel.h>
 #include <linux/slab.h>
 #include <linux/fs.h>
+#include <linux/blkdev.h>
 
 #include "super.h"
 #include "sysfs.h"

kmod/src/triggers.c

@@ -93,13 +93,9 @@ int scoutfs_setup_triggers(struct super_block *sb)
 		goto out;
 	}
 
-	for (i = 0; i < ARRAY_SIZE(triggers->atomics); i++) {
-		if (!debugfs_create_atomic_t(names[i], 0644, triggers->dir,
-					     &triggers->atomics[i])) {
-			ret = -ENOMEM;
-			goto out;
-		}
-	}
+	for (i = 0; i < ARRAY_SIZE(triggers->atomics); i++)
+		debugfs_create_atomic_t(names[i], 0644, triggers->dir,
+					&triggers->atomics[i]);
 
 	ret = 0;
 out:

kmod/src/tseq.c

@@ -183,6 +183,13 @@ static void *scoutfs_tseq_seq_next(struct seq_file *m, void *v, loff_t *pos)
 	ent = tseq_rb_next(ent);
 	if (ent)
 		*pos = ent->pos;
+	else
+		/*
+		 * once we hit the end, *pos is never used, but it has to
+		 * be updated to avoid an error in bpf_seq_read()
+		 */
+		(*pos)++;
+
 	return ent;
 }
 

kmod/src/wkic.c

@@ -1113,7 +1113,7 @@ int scoutfs_wkic_setup(struct super_block *sb)
 
 	winf->sb = sb;
 	KC_INIT_SHRINKER_FUNCS(&winf->shrinker, wkic_shrink_count, wkic_shrink_scan);
-	KC_REGISTER_SHRINKER(&winf->shrinker);
+	KC_REGISTER_SHRINKER(&winf->shrinker, "scoutfs-weak_item:" SCSBF, SCSB_ARGS(sb));
 
 	sbi->wkic_info = winf;
 	return 0;

kmod/src/xattr.c

@@ -1026,7 +1026,9 @@ static int scoutfs_xattr_get_handler
 
 static int scoutfs_xattr_set_handler
 #ifdef KC_XATTR_STRUCT_XATTR_HANDLER
-		(const struct xattr_handler *handler, struct dentry *dentry,
+		(const struct xattr_handler *handler,
+		 KC_VFS_NS_DEF
+		 struct dentry *dentry,
 		 struct inode *inode, const char *name, const void *value,
 		 size_t size, int flags)
 {

tests/.xfstests-branch

@@ -0,0 +1 @@
+v2022.05.01-2-g787cd20

tests/funcs/exec.sh

@@ -7,8 +7,9 @@ t_status_msg()
 export T_PASS_STATUS=100
 export T_SKIP_STATUS=101
 export T_FAIL_STATUS=102
+export T_SKIP_PERMITTED_STATUS=103
 export T_FIRST_STATUS="$T_PASS_STATUS"
-export T_LAST_STATUS="$T_FAIL_STATUS"
+export T_LAST_STATUS="$T_SKIP_PERMITTED_STATUS"
 
 t_pass()
 {
@@ -21,6 +22,17 @@ t_skip()
 	exit $T_SKIP_STATUS
 }
 
+#
+# This exit code is *reserved* for tests that are up-front never going to work
+# in certain cases. This should be expressly documented per-case and made
+# abundantly clear before merging. The test itself should document its case.
+#
+t_skip_permitted()
+{
+	t_status_msg "$@"
+	exit $T_SKIP_PERMITTED_STATUS
+}
+
 t_fail()
 {
 	t_status_msg "$@"

tests/funcs/filter.sh

@@ -143,14 +143,23 @@ t_filter_dmesg()
 	# change-devices causes loop device resizing
 	re="$re|loop: module loaded"
 	re="$re|loop[0-9].* detected capacity change from.*"
+	re="$re|dm-[0-9].* detected capacity change from.*"
 
 	# ignore systemd-journal rotating
 	re="$re|systemd-journald.*"
 
+	# process accounting can be noisy
+	re="$re|Process accounting resumed.*"
+
 	# format vers back/compat tries bad mounts
 	re="$re|scoutfs .* error.*outside of supported version.*"
 	re="$re|scoutfs .* error.*could not get .*super.*"
 
+	# ignore "unsafe core pattern" when xfstests tries to disable cores"
+	re="$re|Unsafe core_pattern used with fs.suid_dumpable=2.*"
+	re="$re|Pipe handler or fully qualified core dump path required.*"
+	re="$re|Set kernel.core_pattern before fs.suid_dumpable.*"
+
 	egrep -v "($re)" | \
 		ignore_harmless_unwind_kasan_stack_oob
 }

tests/golden/basic-posix-acl

@@ -41,9 +41,7 @@ group::r-x
 mask::rwx
 other::r-x
 
-bash: line 0: cd: dir-root: Permission denied
 Failed
-bash: line 0: cd: symlinkdir-root: Permission denied
 Failed
 # file: dir-root
 # owner: root

tests/golden/data-prealloc

@@ -1,29 +1,29 @@
 == initial writes smaller than prealloc grow to prealloc size
-/mnt/test/test/data-prealloc/file-1: 7 extents found
-/mnt/test/test/data-prealloc/file-2: 7 extents found
+/mnt/test/test/data-prealloc/file-1: extents: 7
+/mnt/test/test/data-prealloc/file-2: extents: 7
 == larger files get full prealloc extents
-/mnt/test/test/data-prealloc/file-1: 9 extents found
-/mnt/test/test/data-prealloc/file-2: 9 extents found
+/mnt/test/test/data-prealloc/file-1: extents: 9
+/mnt/test/test/data-prealloc/file-2: extents: 9
 == non-streaming writes with contig have per-block extents
-/mnt/test/test/data-prealloc/file-1: 32 extents found
-/mnt/test/test/data-prealloc/file-2: 32 extents found
+/mnt/test/test/data-prealloc/file-1: extents: 32
+/mnt/test/test/data-prealloc/file-2: extents: 32
 == any writes to region prealloc get full extents
-/mnt/test/test/data-prealloc/file-1: 4 extents found
-/mnt/test/test/data-prealloc/file-2: 4 extents found
-/mnt/test/test/data-prealloc/file-1: 4 extents found
-/mnt/test/test/data-prealloc/file-2: 4 extents found
+/mnt/test/test/data-prealloc/file-1: extents: 4
+/mnt/test/test/data-prealloc/file-2: extents: 4
+/mnt/test/test/data-prealloc/file-1: extents: 4
+/mnt/test/test/data-prealloc/file-2: extents: 4
 == streaming offline writes get full extents either way
-/mnt/test/test/data-prealloc/file-1: 4 extents found
-/mnt/test/test/data-prealloc/file-2: 4 extents found
-/mnt/test/test/data-prealloc/file-1: 4 extents found
-/mnt/test/test/data-prealloc/file-2: 4 extents found
+/mnt/test/test/data-prealloc/file-1: extents: 4
+/mnt/test/test/data-prealloc/file-2: extents: 4
+/mnt/test/test/data-prealloc/file-1: extents: 4
+/mnt/test/test/data-prealloc/file-2: extents: 4
 == goofy preallocation amounts work
-/mnt/test/test/data-prealloc/file-1: 5 extents found
-/mnt/test/test/data-prealloc/file-2: 5 extents found
-/mnt/test/test/data-prealloc/file-1: 5 extents found
-/mnt/test/test/data-prealloc/file-2: 5 extents found
-/mnt/test/test/data-prealloc/file-1: 3 extents found
-/mnt/test/test/data-prealloc/file-2: 3 extents found
+/mnt/test/test/data-prealloc/file-1: extents: 6
+/mnt/test/test/data-prealloc/file-2: extents: 6
+/mnt/test/test/data-prealloc/file-1: extents: 6
+/mnt/test/test/data-prealloc/file-2: extents: 6
+/mnt/test/test/data-prealloc/file-1: extents: 3
+/mnt/test/test/data-prealloc/file-2: extents: 3
 == block writes into region allocs hole
 wrote blk 24
 wrote blk 32

tests/golden/lock-shrink-read-race

@@ -0,0 +1,2 @@
+=== setup
+=== spin reading and shrinking

tests/golden/setattr_more

@@ -22,10 +22,8 @@ scoutfs: setattr failed: Invalid argument (22)
 == large ctime is set
 1972-02-19 00:06:25.999999999 +0000
 == large offline extents are created
-Filesystem type is: 554f4353
-File size of /mnt/test/test/setattr_more/file is 40988672 (10007 blocks of 4096 bytes)
- ext:     logical_offset:        physical_offset: length:   expected: flags:
-   0:        0..   10006:          0..     10006:  10007:             unknown,eof
-/mnt/test/test/setattr_more/file: 1 extent found
+0: offset: 0 0 length: 10007 flags: O.L
+extents: 1
 == correct offline extent length
 976563
+== omitting data_version should not fail

tests/golden/simple-staging

@@ -1,5 +1,9 @@
 == create/release/stage single block file
+0: offset: 0 0 length: 1 flags: O.L
+extents: 1
 == create/release/stage larger file
+0: offset: 0 0 length: 4096 flags: O.L
+extents: 1
 == multiple release,drop_cache,stage cycles
 == release+stage shouldn't change stat, data seq or vers
 == stage does change meta_seq
@@ -7,16 +11,22 @@
 stage: must provide file version with --data-version
 Try `stage --help' or `stage --usage' for more information.
 == wrapped region fails
-stage returned -1, not 4096: error Invalid argument (22)
+stage returned -1, not 8192: error Invalid argument (22)
 scoutfs: stage failed: Input/output error (5)
 == non-block aligned offset fails
 stage returned -1, not 4095: error Invalid argument (22)
 scoutfs: stage failed: Input/output error (5)
+0: offset: 0 0 length: 1 flags: O.L
+extents: 1
 == non-block aligned len within block fails
 stage returned -1, not 1024: error Invalid argument (22)
 scoutfs: stage failed: Input/output error (5)
+0: offset: 0 0 length: 1 flags: O.L
+extents: 1
 == partial final block that writes to i_size does work
 == zero length stage doesn't bring blocks online
+0: offset: 0 0 length: 100 flags: O.L
+extents: 1
 == stage of non-regular file fails
 ioctl failed: Inappropriate ioctl for device (25)
 stage: must provide file version with --data-version

tests/golden/xfstests

@@ -5,24 +5,44 @@ generic/004
 generic/005
 generic/006
 generic/007
+generic/008
+generic/009
 generic/011
+generic/012
 generic/013
 generic/014
+generic/015
+generic/016
+generic/018
 generic/020
+generic/021
+generic/022
 generic/023
 generic/024
+generic/025
+generic/026
 generic/028
+generic/031
 generic/032
+generic/033
 generic/034
 generic/035
 generic/037
 generic/039
 generic/040
 generic/041
+generic/050
+generic/052
 generic/053
 generic/056
 generic/057
+generic/058
+generic/059
+generic/060
+generic/061
 generic/062
+generic/063
+generic/064
 generic/065
 generic/066
 generic/067
@@ -31,42 +51,193 @@ generic/070
 generic/071
 generic/073
 generic/076
+generic/078
+generic/079
+generic/081
+generic/082
 generic/084
 generic/086
 generic/087
 generic/088
 generic/090
+generic/091
 generic/092
+generic/094
+generic/096
+generic/097
 generic/098
+generic/099
 generic/101
 generic/104
 generic/105
 generic/106
 generic/107
+generic/110
+generic/111
+generic/113
+generic/114
+generic/115
+generic/116
 generic/117
+generic/118
+generic/119
+generic/121
+generic/122
+generic/123
 generic/124
+generic/128
 generic/129
+generic/130
 generic/131
+generic/134
+generic/135
+generic/136
+generic/138
+generic/139
+generic/140
+generic/142
+generic/143
+generic/144
+generic/145
+generic/146
+generic/147
+generic/148
+generic/149
+generic/150
+generic/151
+generic/152
+generic/153
+generic/154
+generic/155
+generic/156
+generic/157
+generic/158
+generic/159
+generic/160
+generic/161
+generic/162
+generic/163
 generic/169
+generic/171
+generic/172
+generic/173
+generic/174
+generic/177
+generic/178
+generic/179
+generic/180
+generic/181
+generic/182
+generic/183
 generic/184
+generic/185
+generic/188
+generic/189
+generic/190
+generic/191
+generic/193
+generic/194
+generic/195
+generic/196
+generic/197
+generic/198
+generic/199
+generic/200
+generic/201
+generic/202
+generic/203
+generic/205
+generic/206
+generic/207
+generic/210
+generic/211
+generic/212
+generic/214
+generic/216
+generic/217
+generic/218
+generic/219
+generic/220
 generic/221
+generic/222
+generic/223
+generic/225
+generic/227
 generic/228
+generic/229
+generic/230
+generic/235
 generic/236
 generic/237
+generic/238
+generic/240
+generic/244
 generic/245
 generic/249
+generic/250
+generic/252
+generic/253
+generic/254
+generic/255
+generic/256
 generic/257
 generic/258
+generic/259
+generic/260
+generic/261
+generic/262
+generic/263
+generic/264
+generic/265
+generic/266
+generic/267
+generic/268
+generic/271
+generic/272
+generic/276
+generic/277
+generic/278
+generic/279
+generic/281
+generic/282
+generic/283
+generic/284
 generic/286
+generic/287
+generic/288
+generic/289
+generic/290
+generic/291
+generic/292
+generic/293
 generic/294
+generic/295
+generic/296
+generic/301
+generic/302
+generic/303
+generic/304
+generic/305
 generic/306
 generic/307
 generic/308
 generic/309
+generic/312
 generic/313
+generic/314
 generic/315
+generic/316
+generic/317
 generic/319
 generic/322
+generic/324
+generic/326
+generic/327
+generic/328
+generic/329
+generic/330
+generic/331
+generic/332
 generic/335
 generic/336
 generic/337
@@ -74,10 +245,255 @@ generic/341
 generic/342
 generic/343
 generic/348
+generic/353
+generic/355
+generic/358
+generic/359
 generic/360
+generic/361
+generic/362
+generic/363
+generic/364
+generic/365
+generic/366
+generic/367
+generic/368
+generic/369
+generic/370
+generic/371
+generic/372
+generic/373
+generic/374
 generic/375
 generic/376
 generic/377
+generic/378
+generic/379
+generic/380
+generic/381
+generic/382
+generic/383
+generic/384
+generic/385
+generic/386
+generic/389
+generic/391
+generic/392
+generic/393
+generic/394
+generic/395
+generic/396
+generic/397
+generic/398
+generic/400
+generic/401
+generic/402
+generic/403
+generic/404
+generic/406
+generic/407
+generic/408
+generic/412
+generic/413
+generic/414
+generic/417
+generic/419
+generic/420
+generic/421
+generic/422
+generic/424
+generic/425
+generic/426
+generic/427
+generic/436
+generic/439
+generic/440
+generic/443
+generic/445
+generic/446
+generic/448
+generic/449
+generic/450
+generic/451
+generic/453
+generic/454
+generic/456
+generic/458
+generic/460
+generic/462
+generic/463
+generic/465
+generic/466
+generic/468
+generic/469
+generic/470
+generic/471
+generic/474
+generic/477
+generic/478
+generic/479
+generic/480
+generic/481
+generic/483
+generic/485
+generic/486
+generic/487
+generic/488
+generic/489
+generic/490
+generic/491
+generic/492
+generic/498
+generic/499
+generic/501
+generic/502
+generic/503
+generic/504
+generic/505
+generic/506
+generic/507
+generic/508
+generic/509
+generic/510
+generic/511
+generic/512
+generic/513
+generic/514
+generic/515
+generic/516
+generic/517
+generic/518
+generic/519
+generic/520
+generic/523
+generic/524
+generic/525
+generic/526
+generic/527
+generic/528
+generic/529
+generic/530
+generic/531
+generic/533
+generic/534
+generic/535
+generic/536
+generic/537
+generic/538
+generic/539
+generic/540
+generic/541
+generic/542
+generic/543
+generic/544
+generic/545
+generic/546
+generic/547
+generic/548
+generic/549
+generic/550
+generic/552
+generic/553
+generic/555
+generic/556
+generic/557
+generic/566
+generic/567
+generic/571
+generic/572
+generic/573
+generic/574
+generic/575
+generic/576
+generic/577
+generic/578
+generic/580
+generic/581
+generic/582
+generic/583
+generic/584
+generic/586
+generic/587
+generic/588
+generic/591
+generic/592
+generic/593
+generic/594
+generic/595
+generic/596
+generic/597
+generic/598
+generic/599
+generic/600
+generic/601
+generic/602
+generic/603
+generic/604
+generic/605
+generic/606
+generic/607
+generic/608
+generic/609
+generic/610
+generic/611
+generic/612
+generic/613
+generic/618
+generic/621
+generic/623
+generic/624
+generic/625
+generic/626
+generic/628
+generic/629
+generic/630
+generic/632
+generic/634
+generic/635
+generic/637
+generic/639
+generic/640
+generic/644
+generic/645
+generic/646
+generic/647
+generic/651
+generic/652
+generic/653
+generic/654
+generic/655
+generic/657
+generic/658
+generic/659
+generic/660
+generic/661
+generic/662
+generic/663
+generic/664
+generic/665
+generic/666
+generic/667
+generic/668
+generic/669
+generic/673
+generic/674
+generic/675
+generic/676
+generic/677
+generic/678
+generic/679
+generic/680
+generic/681
+generic/682
+generic/683
+generic/684
+generic/685
+generic/686
+generic/687
+generic/688
+generic/689
+shared/002
+shared/032
 Not
 run:
 generic/008
@@ -251,8 +667,6 @@ generic/331
 generic/332
 generic/353
 generic/355
-generic/356
-generic/357
 generic/358
 generic/359
 generic/361
@@ -278,11 +692,174 @@ generic/383
 generic/384
 generic/385
 generic/386
-shared/001
+generic/391
+generic/392
+generic/395
+generic/396
+generic/397
+generic/398
+generic/400
+generic/402
+generic/404
+generic/406
+generic/407
+generic/408
+generic/412
+generic/413
+generic/414
+generic/417
+generic/419
+generic/420
+generic/421
+generic/422
+generic/424
+generic/425
+generic/427
+generic/439
+generic/440
+generic/446
+generic/449
+generic/450
+generic/451
+generic/453
+generic/454
+generic/456
+generic/458
+generic/462
+generic/463
+generic/465
+generic/466
+generic/468
+generic/469
+generic/470
+generic/471
+generic/474
+generic/485
+generic/487
+generic/488
+generic/491
+generic/492
+generic/499
+generic/501
+generic/503
+generic/505
+generic/506
+generic/507
+generic/508
+generic/511
+generic/513
+generic/514
+generic/515
+generic/516
+generic/517
+generic/518
+generic/519
+generic/520
+generic/528
+generic/530
+generic/536
+generic/537
+generic/538
+generic/539
+generic/540
+generic/541
+generic/542
+generic/543
+generic/544
+generic/545
+generic/546
+generic/548
+generic/549
+generic/550
+generic/552
+generic/553
+generic/555
+generic/556
+generic/566
+generic/567
+generic/572
+generic/573
+generic/574
+generic/575
+generic/576
+generic/577
+generic/578
+generic/580
+generic/581
+generic/582
+generic/583
+generic/584
+generic/586
+generic/587
+generic/588
+generic/591
+generic/592
+generic/593
+generic/594
+generic/595
+generic/596
+generic/597
+generic/598
+generic/599
+generic/600
+generic/601
+generic/602
+generic/603
+generic/605
+generic/606
+generic/607
+generic/608
+generic/609
+generic/610
+generic/612
+generic/613
+generic/621
+generic/623
+generic/624
+generic/625
+generic/626
+generic/628
+generic/629
+generic/630
+generic/635
+generic/644
+generic/645
+generic/646
+generic/647
+generic/651
+generic/652
+generic/653
+generic/654
+generic/655
+generic/657
+generic/658
+generic/659
+generic/660
+generic/661
+generic/662
+generic/663
+generic/664
+generic/665
+generic/666
+generic/667
+generic/668
+generic/669
+generic/673
+generic/674
+generic/675
+generic/677
+generic/678
+generic/679
+generic/680
+generic/681
+generic/682
+generic/683
+generic/684
+generic/685
+generic/686
+generic/687
+generic/688
+generic/689
 shared/002
-shared/003
-shared/004
 shared/032
-shared/051
-shared/289
-Passed all 79 tests
+Passed all 495 tests

tests/run-tests.sh

@@ -515,6 +515,7 @@ msg "running tests"
 passed=0
 skipped=0
 failed=0
+skipped_permitted=0
 for t in $tests; do
 	# tests has basenames from sequence, get path and name
 	t="tests/$t"
@@ -557,6 +558,9 @@ for t in $tests; do
 
 	printf "  %-30s $stats" "$test_name"
 
+	# mark in dmesg as to what test we are running
+	echo "run scoutfs test $test_name" > /dev/kmsg
+
 	# record dmesg before
 	dmesg | t_filter_dmesg > "$T_TMPDIR/dmesg.before"
 
@@ -618,6 +622,10 @@ for t in $tests; do
 		grep -s -v "^$test_name " "$last" > "$last.tmp"
 		echo "$test_name $stats" >> "$last.tmp"
 		mv -f "$last.tmp" "$last"
+	elif [ "$sts" == "$T_SKIP_PERMITTED_STATUS" ]; then
+		echo "  [ skipped (permitted): $message ]"
+		echo "$test_name skipped (permitted) $message " >> "$T_RESULTS/skip.log"
+		((skipped_permitted++))
 	elif [ "$sts" == "$T_SKIP_STATUS" ]; then
 		echo "  [ skipped: $message ]"
 		echo "$test_name $message" >> "$T_RESULTS/skip.log"
@@ -631,7 +639,7 @@ for t in $tests; do
 	fi
 done
 
-msg "all tests run: $passed passed, $skipped skipped, $failed failed"
+msg "all tests run: $passed passed, $skipped skipped, $skipped_permitted skipped (permitted), $failed failed"
 
 
 if [ -n "$T_TRACE_GLOB" -o -n "$T_TRACE_PRINTK" ]; then

tests/sequence

@@ -25,6 +25,7 @@ totl-xattr-tag.sh
 quota.sh
 lock-refleak.sh
 lock-shrink-consistency.sh
+lock-shrink-read-race.sh
 lock-pr-cw-conflict.sh
 lock-revoke-getcwd.sh
 lock-recover-invalidate.sh

tests/tests/basic-posix-acl.sh

@@ -55,16 +55,16 @@ L dir-root/file-group-write
 L symlinkdir-root/file-group-write
 
 echo "== directory exec"
-setpriv $SET_UID bash -c "cd dir-root && echo Success"
-setpriv $SET_UID bash -c "cd symlinkdir-root && echo Success"
+setpriv $SET_UID bash -c "cd dir-root 2>&- && echo Success"
+setpriv $SET_UID bash -c "cd symlinkdir-root 2>&- && echo Success"
 setfacl -m u:22222:rw dir-root
 getfacl dir-root
-setpriv $SET_UID bash -c "cd dir-root || echo Failed"
-setpriv $SET_UID bash -c "cd symlinkdir-root || echo Failed"
+setpriv $SET_UID bash -c "cd dir-root 2>&- || echo Failed"
+setpriv $SET_UID bash -c "cd symlinkdir-root 2>&- || echo Failed"
 setfacl -m g:44444:rwx dir-root
 getfacl dir-root
-setpriv $SET_GID bash -c "cd dir-root && echo Success"
-setpriv $SET_GID bash -c "cd symlinkdir-root && echo Success"
+setpriv $SET_GID bash -c "cd dir-root 2>&- && echo Success"
+setpriv $SET_GID bash -c "cd symlinkdir-root 2>&- && echo Success"
 
 echo "== get/set attr"
 rm -rf file-root

tests/tests/basic-posix-consistency.sh

@@ -3,13 +3,13 @@
 # operations in one mount and verify the results in another.
 #
 
-t_require_commands getfattr setfattr dd filefrag diff touch stat scoutfs
+t_require_commands getfattr setfattr dd diff touch stat scoutfs
 t_require_mounts 2
 
 GETFATTR="getfattr --absolute-names"
 SETFATTR="setfattr"
 DD="dd status=none"
-FILEFRAG="filefrag -v -b4096"
+FIEMAP="scoutfs get-fiemap"
 
 echo "== root inode updates flow back and forth"
 sleep 1
@@ -55,8 +55,8 @@ for i in $(seq 1 10); do
 		conv=notrunc oflag=append &
 	wait
 done
-$FILEFRAG "$T_D0/file" | t_filter_fs > "$T_TMP.0"
-$FILEFRAG "$T_D1/file" | t_filter_fs > "$T_TMP.1"
+$FIEMAP "$T_D0/file" > "$T_TMP.0"
+$FIEMAP "$T_D1/file" > "$T_TMP.1"
 diff -u "$T_TMP.0" "$T_TMP.1"
 
 echo "== unlinked file isn't found"

tests/tests/data-prealloc.sh

@@ -4,7 +4,16 @@
 # merge adjacent consecutive allocations.  (we don't have multiple
 # allocation cursors)
 #
-t_require_commands scoutfs stat filefrag dd touch truncate
+t_require_commands scoutfs stat dd touch truncate
+
+get_fiemap()
+{
+	scoutfs get-fiemap "$1" | awk '($1 != "extents:") {
+			unwritten = (substr($8, 2, 1) == "U") ? "unwritten" : "";
+			eof = (substr($8, 3, 1) == "L") ? "eof" : "";
+			print $3 ".. " $6 ": " unwritten eof;
+			};'
+}
 
 write_block()
 {
@@ -76,26 +85,9 @@ print_extents_found()
 {
 	local prefix="$1"
 
-	filefrag "$prefix"* 2>&1 | grep "extent.*found" | t_filter_fs
-}
-
-#
-# print the logical start, len, and flags if they're there.
-#
-print_logical_extents()
-{
-	local file="$1"
-
-	filefrag -v -b4096 "$file" 2>&1 | t_filter_fs | awk '
-		($1 ~ /[0-9]+:/) {
-			if ($NF !~  /[0-9]+:/) {
-				flags=$NF
-			} else {
-				flags=""
-			}
-			print $2, $6, flags
-		}
-	' | sed 's/last,eof/eof/'
+	for f in "$prefix"-*; do
+		echo "$f: $(scoutfs get-fiemap "$f" | tail -n 1)" | t_filter_fs
+	done
 }
 
 t_save_all_sysfs_mount_options data_prealloc_blocks
@@ -197,7 +189,7 @@ for sides in 0 1 2 3; do
 done
 
 echo before:
-print_logical_extents "$prefix"
+get_fiemap "$prefix"
 
 # now write into the first, middle, and last empty block of each
 t_set_sysfs_mount_option 0 data_prealloc_contig_only 0
@@ -223,7 +215,7 @@ for sides in 0 1 2 3; do
 			# mid (both has 6 blocks internally)
 			2) write_block $prefix $((left + 3)) ;;
 		esac
-		print_logical_extents "$prefix"
+		get_fiemap "$prefix"
 		((base+=8))
 	done
 done

tests/tests/format-version-forward-back.sh

@@ -11,6 +11,11 @@
 # format version.
 #
 
+# not supported on el9!
+if [ $(source /etc/os-release ; echo ${VERSION_ID:0:1}) -gt 8 ]; then
+	t_skip_permitted "Unsupported OS version"
+fi
+
 mount_has_format_version()
 {
 	local mnt="$1"

tests/tests/lock-shrink-read-race.sh

@@ -0,0 +1,40 @@
+#
+# We had a lock server refcounting bug that could let one thread get a
+# reference on a lock struct that was being freed by another thread.  We
+# were able to reproduce this by having all clients try and produce a
+# lot of read and null requests.
+#
+# This will manfiest as a hung lock and timed out test runs, probably
+# with hung task messages on the console.  Depending on how the race
+# turns out, it can trigger KASAN warnings in
+# process_waiting_requests().
+#
+
+READERS_PER=3
+SECS=30
+
+echo "=== setup"
+touch "$T_D0/file"
+
+echo "=== spin reading and shrinking"
+END=$((SECONDS + SECS))
+for m in $(t_fs_nrs); do
+	eval file="\$T_D${m}/file"
+
+	# lots of tasks reading as fast as they can
+	for t in $(seq 1 $READERS_PER); do
+		(while [ $SECONDS -lt $END ]; do
+			stat $file > /dev/null
+		 done) &
+	done
+	# one task shrinking (triggering null requests) and reading
+	(while [ $SECONDS -lt $END ]; do
+		stat $file > /dev/null
+		t_trigger_arm_silent statfs_lock_purge $m
+		stat -f "$file" > /dev/null
+	 done) &
+done
+
+wait
+
+t_pass

tests/tests/move-blocks.sh

@@ -83,9 +83,9 @@ touch "$OTHER"
 ln "$FROM" "$HARD"
 
 echo "== wrapped offsets should fail"
-HUGE=0x8000000000000000
-scoutfs move-blocks "$FROM" -f "$HUGE" -l "$HUGE" "$TO" -t 0 2>&1 | t_filter_fs
-scoutfs move-blocks "$FROM" -f 0 -l "$HUGE" "$TO" -t "$HUGE" 2>&1 | t_filter_fs
+HUGE=0xfffffffffffff000
+scoutfs move-blocks "$FROM" -f "$HUGE" -l "8192" "$TO" -t 0 2>&1 | t_filter_fs
+scoutfs move-blocks "$FROM" -f 0 -l "$HUGE" "$TO" -t "8192" 2>&1 | t_filter_fs
 
 echo "== specifying same file fails"
 scoutfs move-blocks "$FROM" -f 0 -l "$BS" "$HARD" -t 0 2>&1 | t_filter_fs

tests/tests/quota.sh

@@ -22,7 +22,7 @@ reset_all()
 	getfattr --absolute-names -d -m - "$T_D0" | \
 		grep "^scoutfs.totl." | \
 		cut -d '=' -f 1 | \
-		xargs -n 1 -I'{}'  setfattr -x '{}' "$T_D0"
+		xargs -I'{}'  setfattr -x '{}' "$T_D0"
 }
 
 echo "== prepare dir with write perm for test ids"

tests/tests/setattr_more.sh

@@ -2,7 +2,7 @@
 # Test correctness of the setattr_more ioctl.
 #
 
-t_require_commands filefrag scoutfs touch mkdir rm stat mknod
+t_require_commands scoutfs touch mkdir rm stat mknod
 
 FILE="$T_D0/file"
 
@@ -55,17 +55,10 @@ scoutfs setattr -t 67305985.999999999 -V 1 -s 1 "$FILE" 2>&1 | t_filter_fs
 TZ=GMT stat -c "%z" "$FILE"
 rm "$FILE"
 
-#
-# With e2fsprogs-v1.42.10-10-g29758d2f, the output of filefrag 'flags' changes
-# significantly. First, the _LAST flag is now output. Second, the 'unknown'
-# flag is now printed out as 'unknown_loc'. To compensate for this, we check
-# and replace the "correct" output for new versions here with the expected
-# value.
-#
 echo "== large offline extents are created"
 touch "$FILE"
 scoutfs setattr -V 1 -o -s $((10007 * 4096)) "$FILE" 2>&1 | t_filter_fs
-filefrag -v -b4096 "$FILE" 2>&1 | sed 's/last,unknown_loc,eof$/unknown,eof/' | t_filter_fs
+scoutfs get-fiemap "$FILE"
 rm "$FILE"
 
 # had a bug where we were creating extents that were too long
@@ -75,4 +68,11 @@ scoutfs setattr -V 1 -o -s 4000000000 "$FILE" 2>&1 | t_filter_fs
 scoutfs stat -s offline_blocks "$FILE"
 rm "$FILE"
 
+# Do not fail if data_version is unset - the unset `0` value should not
+# be passed down to attr_x handling code which will -EINVAL on that.
+echo "== omitting data_version should not fail"
+touch "$FILE"
+scoutfs setattr -s 0 -t 1725670311.0 -r 1725670311.0 "$FILE"
+rm "$FILE"
+
 t_pass

tests/tests/simple-release-extents.sh

@@ -7,6 +7,7 @@ t_require_commands xfs_io filefrag scoutfs mknod
 # this test wants to ignore unwritten extents
 fiemap_file() {
 	filefrag -v -b4096 "$1" | grep -v "unwritten"
+	scoutfs get-fiemap "$1" | grep -v 'flags:.*U'
 }
 
 create_file() {
@@ -61,7 +62,10 @@ echo "== release past i_size is fine"
 release_vers "$FILE" stat 400K 4K
 
 echo "== wrapped blocks fails"
-release_vers "$FILE" stat $vers 0x8000000000000000 0x8000000000000000
+# just under!
+release_vers "$FILE" stat $vers 0xfffffffffffff000 4096
+# this goes over
+release_vers "$FILE" stat $vers 0xfffffffffffff000 8192
 
 echo "== releasing non-file fails"
 mknod "$CHAR" c 1 3
@@ -105,25 +109,20 @@ for c in $(seq 0 4); do
 		fi
 	done
 
-	start=$(fiemap_file "$FILE" | \
-		awk '($1 == "0:"){print substr($4, 0, length($4)- 2)}')
-
 	release_vers "$FILE" stat $(($a * 4))K 4K
 	release_vers "$FILE" stat $(($b * 4))K 4K
 	release_vers "$FILE" stat $(($c * 4))K 4K
 
 	echo -n "$a $b $c:"
 
-	fiemap_file "$FILE" | \
-		awk 'BEGIN{ORS=""}($1 == (NR - 4)":") {
-			off=substr($2, 0, length($2)- 2);
-			phys=substr($4, 0, length($4)- 2);
-			if (phys > 100) {
-				phys = phys - phys + 100 + off;
-			}
-			len=substr($6, 0, length($6)- 1);
-			print "  (" off, phys, len ")";
-		}'
+	scoutfs get-fiemap "$FILE" | \
+		awk 'BEGIN{ORS=""}($1 != "extents:") {
+			off=$3;
+			len=$6;
+			phys=substr($8, 0, 1);
+			phys = (phys == ".") ? off + 100 : 0;
+			print "  (" off, phys, len ")"
+		};'
 	echo
 
 	rm "$FILE"

tests/tests/simple-staging.sh

@@ -2,11 +2,7 @@
 # Test correctness of the staging operation
 #
 
-t_require_commands filefrag dd scoutfs cp cmp rm
-
-fiemap_file() {
-	filefrag -v -b4096 "$1"
-}
+t_require_commands dd scoutfs cp cmp rm
 
 create_file() {
 	local file="$1"
@@ -62,7 +58,7 @@ create_file "$FILE" 4096
 cp "$FILE"  "$T_TMP"
 release_vers "$FILE" stat 0 4K
 # make sure there only offline extents
-fiemap_file "$FILE" | grep "^[ 0-9]*:" | grep -v "unknown"
+scoutfs get-fiemap "$FILE"
 stage_vers "$FILE" stat 0 4096 "$T_TMP"
 cmp "$FILE" "$T_TMP"
 rm -f "$FILE"
@@ -72,7 +68,7 @@ create_file "$FILE" $((4096 * 4096))
 cp "$FILE"  "$T_TMP"
 release_vers "$FILE" stat 0 16M
 # make sure there only offline extents
-fiemap_file "$FILE" | grep "^[ 0-9]*:" | grep -v "unknown"
+scoutfs get-fiemap "$FILE"
 stage_vers "$FILE" stat 0 $((4096 * 4096)) "$T_TMP"
 cmp "$FILE" "$T_TMP"
 rm -f "$FILE"
@@ -143,8 +139,8 @@ hexdump -C "$FILE"
 rm -f "$FILE"
 
 echo "== wrapped region fails"
-create_file "$FILE" 4096
-stage_vers "$FILE" stat 0xFFFFFFFFFFFFF000 4096 /dev/zero
+create_file "$FILE" 8192
+stage_vers "$FILE" stat 0xFFFFFFFFFFFFF000 8192 /dev/zero
 rm -f "$FILE"
 
 echo "== non-block aligned offset fails"
@@ -152,7 +148,7 @@ create_file "$FILE" 4096
 cp "$FILE"  "$T_TMP"
 release_vers "$FILE" stat 0 4K
 stage_vers "$FILE" stat 1 4095 "$T_TMP"
-fiemap_file "$FILE" | grep "^[ 0-9]*:" | grep -v "unknown"
+scoutfs get-fiemap "$FILE"
 rm -f "$FILE"
 
 echo "== non-block aligned len within block fails"
@@ -160,7 +156,7 @@ create_file "$FILE" 4096
 cp "$FILE"  "$T_TMP"
 release_vers "$FILE" stat 0 4K
 stage_vers "$FILE" stat 0 1024 "$T_TMP"
-fiemap_file "$FILE" | grep "^[ 0-9]*:" | grep -v "unknown"
+scoutfs get-fiemap "$FILE"
 rm -f "$FILE"
 
 echo "== partial final block that writes to i_size does work"
@@ -175,7 +171,7 @@ echo "== zero length stage doesn't bring blocks online"
 create_file "$FILE" $((4096 * 100))
 release_vers "$FILE" stat 0 400K
 stage_vers "$FILE" stat 4096 0 /dev/zero
-fiemap_file "$FILE" | grep "^[ 0-9]*:" | grep -v "unknown"
+scoutfs get-fiemap "$FILE"
 rm -f "$FILE"
 
 # XXX yup, needs to be updated for demand staging

tests/tests/xfstests.sh

@@ -30,8 +30,13 @@ t_quiet mkdir -p "$T_TMPDIR/mnt.scratch"
 t_quiet cd "$T_XFSTESTS_REPO"
 if [ -z "$T_SKIP_CHECKOUT" ]; then
 	t_quiet git fetch
+	# if we're passed a tag instead of a branch, we can't --track
+	TRACK="--track"
+	if git tag -l | grep -q "$T_XFSTESTS_BRANCH" ; then
+		TRACK=""
+	fi
 	# this remote use is bad, do better
-	t_quiet git checkout -B "$T_XFSTESTS_BRANCH" --track "origin/$T_XFSTESTS_BRANCH"
+	t_quiet git checkout -B "$T_XFSTESTS_BRANCH" ${TRACK} "origin/$T_XFSTESTS_BRANCH"
 fi
 t_quiet make
 t_quiet sync
@@ -81,6 +86,45 @@ generic/325	# mmap missing
 generic/338	# BUG_ON update inode error handling
 generic/346	# mmap missing
 generic/347	# _dmthin_mount doesn't work?
+generic/356	# swap
+generic/357	# swap
+generic/409	# bind mounts not scripted yet
+generic/410	# bind mounts not scripted yet
+generic/411	# bind mounts not scripted yet
+generic/423	# symlink inode size is strlen() + 1 on scoutfs
+generic/428	# mmap missing
+generic/430	# xfs_io copy_range missing in el7
+generic/431	# xfs_io copy_range missing in el7
+generic/432	# xfs_io copy_range missing in el7
+generic/433	# xfs_io copy_range missing in el7
+generic/434	# xfs_io copy_range missing in el7
+generic/437	# mmap missing
+generic/441	# dm-mapper
+generic/444	# el9's posix_acl_update_mode is buggy ?
+generic/452	# exec test - no mmap
+generic/467	# open_by_handle ESTALE
+generic/472	# swap
+generic/484	# dm-mapper
+generic/493	# swap
+generic/494	# swap
+generic/495	# swap
+generic/496	# swap
+generic/497	# swap
+generic/532	# xfs_io statx attrib_mask missing in el7
+generic/554	# swap
+generic/563	# cgroup+loopdev
+generic/564	# xfs_io copy_range missing in el7
+generic/565	# xfs_io copy_range missing in el7
+generic/568	# falloc not resulting in block count increase
+generic/569	# swap
+generic/570	# swap
+generic/614	# mmap missing
+generic/620	# dm-hugedisk
+generic/633	# mmap, id-mapped mounts missing in el7
+generic/636	# swap
+generic/638	# mmap missing
+generic/641	# swap
+generic/643	# swap
 EOF
 
 t_restore_output

utils/sparse.sh

@@ -37,10 +37,23 @@ search=$(gcc -print-search-dirs | awk '($1 == "install:"){print "-I" $2}')
 #
 # We're trying to use sparse against glibc headers which go wild trying to
 # use internal compiler macros to test features.  We copy gcc's and give
-# them to sparse.  But not __SIZE_TYPE__ 'cause sparse defines that one.
+# them to sparse, but not the ones that sparse already has.
 #
-defines=".sparse.gcc-defines.h"
-gcc -dM -E -x c - < /dev/null | grep -v __SIZE_TYPE__ > $defines
+defines=".sparse.gcc-defines.$$.h"
+awk '
+	# save defines from gcc
+	( FNR == NR ) { lines[$2]=$0 }
+
+	# delete defines that sparse also has
+	( FNR < NR ) { delete lines[$2] }
+
+	# dump remaining lines unique to gcc
+	END {
+		for (a in lines) {
+			print lines[a]
+		}
+	}
+' <(gcc -dM -E -x c - < /dev/null) <(sparse -dM -E -x c - < /dev/null) > $defines
 include="-include $defines"
 
 #
@@ -54,6 +67,9 @@ else
 fi
 
 sparse $m64 $include $search/include "$@" 2>&1 | egrep -v "($RE)" | tee .sparse.output
+
+rm -f $defines
+
 if  [ -s .sparse.output ]; then
 	exit 1
 else

utils/src/bitmap.c

@@ -10,6 +10,11 @@
  * Just a quick simple native bitmap.
  */
 
+int test_bit(unsigned long *bits, u64 nr)
+{
+	return !!(bits[nr / BITS_PER_LONG] & (1UL << (nr & (BITS_PER_LONG - 1))));
+}
+
 void set_bit(unsigned long *bits, u64 nr)
 {
 	bits[nr / BITS_PER_LONG] |= 1UL << (nr & (BITS_PER_LONG - 1));

utils/src/bitmap.h

@@ -1,6 +1,7 @@
 #ifndef _BITMAP_H_
 #define _BITMAP_H_
 
+int test_bit(unsigned long *bits, u64 nr);
 void set_bit(unsigned long *bits, u64 nr);
 void clear_bit(unsigned long *bits, u64 nr);
 u64 find_next_set_bit(unsigned long *start, u64 from, u64 total);

utils/src/bloom.c

@@ -0,0 +1,20 @@
+#include <errno.h>
+
+#include "sparse.h"
+#include "util.h"
+#include "format.h"
+#include "hash.h"
+#include "bloom.h"
+
+void calc_bloom_nrs(struct scoutfs_key *key, unsigned int *nrs)
+{
+	u64 hash;
+	int i;
+
+	hash = scoutfs_hash64(key, sizeof(struct scoutfs_key));
+
+	for (i = 0; i < SCOUTFS_FOREST_BLOOM_NRS; i++) {
+		nrs[i] = (u32)hash % SCOUTFS_FOREST_BLOOM_BITS;
+		hash >>= SCOUTFS_FOREST_BLOOM_FUNC_BITS;
+	}
+}

utils/src/bloom.h

@@ -0,0 +1,6 @@
+#ifndef _BLOOM_H_
+#define _BLOOM_H_
+
+void calc_bloom_nrs(struct scoutfs_key *key, unsigned int *nrs);
+
+#endif

utils/src/btree.c

@@ -8,7 +8,7 @@
 #include "leaf_item_hash.h"
 #include "btree.h"
 
-static void init_block(struct scoutfs_btree_block *bt, int level)
+void btree_init_block(struct scoutfs_btree_block *bt, int level)
 {
 	int free;
 
@@ -33,7 +33,7 @@ void btree_init_root_single(struct scoutfs_btree_root *root,
 
 	memset(bt, 0, SCOUTFS_BLOCK_LG_SIZE);
 
-	init_block(bt, 0);
+	btree_init_block(bt, 0);
 }
 
 static void *alloc_val(struct scoutfs_btree_block *bt, int len)

utils/src/btree.h

@@ -1,6 +1,7 @@
 #ifndef _BTREE_H_
 #define _BTREE_H_
 
+void btree_init_block(struct scoutfs_btree_block *bt, int level);
 void btree_init_root_single(struct scoutfs_btree_root *root,
 			    struct scoutfs_btree_block *bt,
 			    u64 seq, u64 blkno);

utils/src/fiemap.c

@@ -0,0 +1,191 @@
+#include <unistd.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/ioctl.h>
+#include <linux/fs.h>
+#include <linux/fiemap.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <string.h>
+#include <argp.h>
+
+#include "sparse.h"
+#include "parse.h"
+#include "util.h"
+#include "format.h"
+#include "ioctl.h"
+#include "cmd.h"
+
+/*
+ * This is wholly modeled after e2fsprogs/filefrag.c from tso
+ */
+
+struct get_fiemap_args {
+	char *filename;
+	bool phys;
+	bool logical;
+	bool byte;
+};
+
+static int do_get_fiemap(struct get_fiemap_args *args)
+{
+	__u64 buf[2048];        /* __u64 for proper field alignment */
+	struct stat st;
+	struct fiemap *fiemap = (struct fiemap *)buf;
+	struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
+	int count = (sizeof(buf) - sizeof(*fiemap)) /
+			sizeof(struct fiemap_extent);
+	int fd;
+	int ret;
+	int i;
+	u64 nr = 0; /* XXX we could put this in fm_start to make start/count an option */
+	int last = 0;
+	u64 off_p, off_l;
+	u64 len;
+
+	memset(fiemap, 0, sizeof(struct fiemap));
+
+	fd = open(args->filename, O_RDONLY);
+	if (fd < 0) {
+		ret = -errno;
+		fprintf(stderr, "failed to open '%s': %s (%d)\n",
+			args->filename, strerror(errno), errno);
+		goto out;
+	}
+
+	/* get block size from stat */
+	if (fstat(fd, &st) != 0) {
+		ret = -errno;
+		fprintf(stderr, "stat failed on '%s': %s (%d)\n",
+			args->filename, strerror(errno), errno);
+		goto out;
+	};
+
+	do {
+		fiemap->fm_length = ~0ULL;
+		fiemap->fm_extent_count = count;
+
+		ret = ioctl(fd, FS_IOC_FIEMAP, (unsigned long) fiemap);
+		if (ret < 0) {
+			ret = -errno;
+			fprintf(stderr, "get_fiemap ioctl failed: "
+				"%s (%d)\n", strerror(errno), errno);
+			goto out;
+		}
+
+		/* nothing returned, so exit */
+		if (fiemap->fm_mapped_extents == 0)
+			break;
+
+		for (i = 0; i < fiemap->fm_mapped_extents; i++) {
+			off_p = fm_ext[i].fe_physical;
+			off_l = fm_ext[i].fe_logical;
+			len = fm_ext[i].fe_length;
+
+			if (!args->byte) {
+				off_p /= st.st_blksize;
+				off_l /= st.st_blksize;
+				len /= st.st_blksize;
+			}
+
+			printf("%llu: offset: ", nr++);
+
+			if (!args->phys)
+				printf("%llu ", off_l);
+			else if (!args->logical)
+				printf("%llu ", off_p);
+			else
+				printf("%llu %llu ", off_l, off_p);
+
+			printf("length: %llu flags: %c%c%c\n",
+				len,
+				(fm_ext[i].fe_flags & FIEMAP_EXTENT_UNKNOWN) ? 'O' : '.',
+				(fm_ext[i].fe_flags & FIEMAP_EXTENT_UNWRITTEN) ? 'U' : '.',
+				(fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST) ? 'L' : '.');
+
+			if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+				last = 1;
+		}
+
+		/* fm_start from the next logical extent */
+		fiemap->fm_start = fm_ext[i-1].fe_logical + fm_ext[i-1].fe_length;
+	} while (last == 0);
+
+	printf("extents: %llu\n", nr);
+
+out:
+	if (fd >= 0)
+		close(fd);
+
+	return ret;
+};
+
+static int parse_opt(int key, char *arg, struct argp_state *state)
+{
+	struct get_fiemap_args *args = state->input;
+
+	switch (key) {
+	case 'P':
+		args->logical = false;
+		break;
+	case 'L':
+		args->phys = false;
+		break;
+	case 'b':
+		args->byte = true;
+		break;
+	case ARGP_KEY_ARG:
+		if (!args->filename)
+			args->filename = strdup_or_error(state, arg);
+		else
+			argp_error(state, "more than one argument given");
+		break;
+	case ARGP_KEY_FINI:
+		if ((!args->logical) && (!args->phys))
+			argp_error(state, "can't pass both -P and -L options");
+		if (!args->filename)
+			argp_error(state, "no filename given");
+		break;
+	default:
+		break;
+	}
+
+	return 0;
+}
+
+static struct argp_option options[] = {
+	{ "physical", 'P', NULL, 0, "Output physical offsets only"},
+	{ "logical", 'L', NULL, 0, "Output logical offsets only"},
+	{ "byte", 'b', NULL, 0, "Output byte values instead of blocks"},
+	{ NULL }
+};
+
+static struct argp argp = {
+	options,
+	parse_opt,
+	"FILE",
+	"Print fiemap extent mapping"
+};
+
+static int get_fiemap_cmd(int argc, char **argv)
+{
+	struct get_fiemap_args get_fiemap_args = {NULL};
+	int ret;
+
+	get_fiemap_args.phys = true;
+	get_fiemap_args.logical = true;
+
+	ret = argp_parse(&argp, argc, argv, 0, NULL, &get_fiemap_args);
+	if (ret)
+		return ret;
+
+	return do_get_fiemap(&get_fiemap_args);
+}
+
+static void __attribute__((constructor)) get_fiemap_ctor(void)
+{
+	cmd_register_argp("get-fiemap", &argp, GROUP_DEBUG, get_fiemap_cmd);
+}

utils/src/list.h

@@ -156,6 +156,16 @@ static inline void list_move_tail(struct list_head *list,
         list_add_tail(list, head);
 }
 
+/**
+ * list_is_head - tests whether @list is the list @head
+ * @list: the entry to test
+ * @head: the head of the list
+ */
+static inline int list_is_head(const struct list_head *list, const struct list_head *head)
+{
+	return list == head;
+}
+
 /**
  * list_empty - tests whether a list is empty
  * @head: the list to test.
@@ -242,6 +252,15 @@ static inline void list_splice_init(struct list_head *list,
         for (pos = (head)->next, n = pos->next; pos != (head); \
                 pos = n, n = pos->next)
 
+/**
+ * list_entry_is_head - test if the entry points to the head of the list
+ * @pos:	the type * to cursor
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_entry_is_head(pos, head, member)				\
+	(&pos->member == (head))
+
 /**
  * list_for_each_entry        -        iterate over list of given type
  * @pos:        the type * to use as a loop counter.
@@ -307,4 +326,28 @@ static inline void list_splice_init(struct list_head *list,
 #define list_next_entry(pos, member) \
         list_entry((pos)->member.next, typeof(*(pos)), member)
 
+/**
+ * list_prev_entry - get the prev element in list
+ * @pos:	the type * to cursor
+ * @member:	the name of the list_head within the struct.
+ */
+#define list_prev_entry(pos, member) \
+	list_entry((pos)->member.prev, typeof(*(pos)), member)
+
+/**
+ * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
+ * @pos:	the type * to use as a loop cursor.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Iterate backwards over list of given type, safe against removal
+ * of list entry.
+ */
+#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
+	for (pos = list_last_entry(head, typeof(*pos), member),		\
+		n = list_prev_entry(pos, member);			\
+	     !list_entry_is_head(pos, head, member); 			\
+	     pos = n, n = list_prev_entry(n, member))
+
 #endif

utils/src/lk_rbtree_wrapper.h

@@ -0,0 +1,24 @@
+#ifndef _LK_RBTREE_WRAPPER_H_
+#define _LK_RBTREE_WRAPPER_H_
+
+/*
+ * We're using this lame hack to build and use the kernel's rbtree in
+ * userspace.  We drop the kernel's rbtree*[ch] implementation in and
+ * use them with this wrapper.  We only have to remove the kernel
+ * includes from the imported files.
+ */
+
+#include <stdbool.h>
+#include "util.h"
+
+#define rcu_assign_pointer(a, b)	do { a = b; } while (0)
+#define READ_ONCE(a)			({ a; })
+#define WRITE_ONCE(a, b)		do { a = b; } while (0)
+#define unlikely(a)			({ a; })
+#define EXPORT_SYMBOL(a)		/* nop */
+
+#include "rbtree_types.h"
+#include "rbtree.h"
+#include "rbtree_augmented.h"
+
+#endif

utils/src/mode_types.c

@@ -0,0 +1,24 @@
+#include <unistd.h>
+#include <sys/stat.h>
+
+#include "sparse.h"
+#include "util.h"
+#include "format.h"
+#include "mode_types.h"
+
+unsigned int mode_to_type(mode_t mode)
+{
+#define S_SHIFT 12
+	static unsigned char mode_types[S_IFMT >> S_SHIFT] = {
+		[S_IFIFO >> S_SHIFT]	= SCOUTFS_DT_FIFO,
+		[S_IFCHR >> S_SHIFT]	= SCOUTFS_DT_CHR,
+		[S_IFDIR >> S_SHIFT]	= SCOUTFS_DT_DIR,
+		[S_IFBLK >> S_SHIFT]	= SCOUTFS_DT_BLK,
+		[S_IFREG >> S_SHIFT]	= SCOUTFS_DT_REG,
+		[S_IFLNK >> S_SHIFT]	= SCOUTFS_DT_LNK,
+		[S_IFSOCK >> S_SHIFT]	= SCOUTFS_DT_SOCK,
+	};
+
+	return mode_types[(mode & S_IFMT) >> S_SHIFT];
+#undef S_SHIFT
+}

utils/src/mode_types.h

@@ -0,0 +1,6 @@
+#ifndef _MODE_TYPES_H_
+#define _MODE_TYPES_H_
+
+unsigned int mode_to_type(mode_t mode);
+
+#endif

utils/src/name_hash.h

@@ -0,0 +1,46 @@
+#ifndef _SCOUTFS_NAME_HASH_H_
+#define _SCOUTFS_NAME_HASH_H_
+
+#include "hash.h"
+
+/*
+ * Test a bit number as though an array of bytes is a large len-bit
+ * big-endian value.  nr 0 is the LSB of the final byte, nr (len - 1) is
+ * the MSB of the first byte.
+ */
+static int test_be_bytes_bit(int nr, const char *bytes, int len)
+{
+	return bytes[(len - 1 - nr) >> 3] & (1 << (nr & 7));
+}
+
+/*
+ * Generate a 32bit "fingerprint" of the name by extracting 32 evenly
+ * distributed bits from the name.  The intent is to have the sort order
+ * of the fingerprints reflect the memcmp() sort order of the names
+ * while mapping large names down to small fs keys.
+ *
+ * Names that are smaller than 32bits are biased towards the high bits
+ * of the fingerprint so that most significant bits of the fingerprints
+ * consistently reflect the initial characters of the names.
+ */
+static inline u32 dirent_name_fingerprint(const char *name, unsigned int name_len)
+{
+	int name_bits = name_len * 8;
+	int skip = max(name_bits / 32, 1);
+	u32 fp = 0;
+	int f;
+	int n;
+
+	for (f = 31, n = name_bits - 1; f >= 0 && n >= 0; f--, n -= skip)
+		fp |= !!test_be_bytes_bit(n, name, name_bits) << f;
+
+	return fp;
+}
+
+static inline u64 dirent_name_hash(const char *name, unsigned int name_len)
+{
+       return scoutfs_hash32(name, name_len) |
+              ((u64)dirent_name_fingerprint(name, name_len) << 32);
+}
+
+#endif

utils/src/print.c

@@ -645,6 +645,8 @@ static int print_alloc_list_block(int fd, char *str, struct scoutfs_block_ref *r
 	u64 blkno;
 	u64 start;
 	u64 len;
+	u64 st;
+	u64 nr;
 	int wid;
 	int ret;
 	int i;
@@ -663,27 +665,37 @@ static int print_alloc_list_block(int fd, char *str, struct scoutfs_block_ref *r
 	       AL_REF_A(&lblk->next), le32_to_cpu(lblk->start),
 	       le32_to_cpu(lblk->nr));
 
-	if (lblk->nr) {
-		wid = printf("  exts: ");
-		start = 0;
-		len = 0;
-		for (i = 0; i < le32_to_cpu(lblk->nr); i++) {
-			if (len == 0)
-				start = le64_to_cpu(lblk->blknos[i]);
-			len++;
-
-			if (i == (le32_to_cpu(lblk->nr) - 1) ||
-			    start + len != le64_to_cpu(lblk->blknos[i + 1])) {
-				if (wid >= 72)
-					wid = printf("\n        ");
-
-				wid += printf("%llu,%llu ", start, len);
-				len = 0;
-			}
-		}
-		printf("\n");
+	st = le32_to_cpu(lblk->start);
+	nr = le32_to_cpu(lblk->nr);
+	if (st >= SCOUTFS_ALLOC_LIST_MAX_BLOCKS ||
+	    nr > SCOUTFS_ALLOC_LIST_MAX_BLOCKS ||
+	    (st + nr) > SCOUTFS_ALLOC_LIST_MAX_BLOCKS) {
+		printf("  (invalid start and nr fields)\n");
+		goto out;
 	}
 
+	if (lblk->nr == 0)
+		goto out;
+
+	wid = printf("  exts: ");
+	start = 0;
+	len = 0;
+	for (i = 0; i < nr; i++) {
+		if (len == 0)
+			start = le64_to_cpu(lblk->blknos[st + i]);
+		len++;
+
+		if (i == (nr - 1) || (start + len) != le64_to_cpu(lblk->blknos[st + i + 1])) {
+			if (wid >= 72)
+				wid = printf("\n        ");
+
+			wid += printf("%llu,%llu ", start, len);
+			len = 0;
+		}
+	}
+	printf("\n");
+
+out:
 	next = lblk->next;
 	free(lblk);
 	return print_alloc_list_block(fd, str, &next);

utils/src/quota.c

@@ -385,7 +385,8 @@ static int parse_stdin_in_fn(int fd, struct scoutfs_ioctl_quota_rule *irules, si
 
 	ret = getline(&line, &size, stdin);
 	if (ret < 0) {
-		if (errno == ENOENT)
+		free(line);
+		if ((errno == ENOENT) || (errno == 0))
 			return 0;
 
 		ret = -errno;

utils/src/rbtree.c

@@ -0,0 +1,629 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  (C) 2002  David Woodhouse <dwmw2@infradead.org>
+  (C) 2012  Michel Lespinasse <walken@google.com>
+
+
+  linux/lib/rbtree.c
+*/
+
+#include "lk_rbtree_wrapper.h"
+
+/*
+ * red-black trees properties:  https://en.wikipedia.org/wiki/Rbtree
+ *
+ *  1) A node is either red or black
+ *  2) The root is black
+ *  3) All leaves (NULL) are black
+ *  4) Both children of every red node are black
+ *  5) Every simple path from root to leaves contains the same number
+ *     of black nodes.
+ *
+ *  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ *  consecutive red nodes in a path and every red node is therefore followed by
+ *  a black. So if B is the number of black nodes on every simple path (as per
+ *  5), then the longest possible path due to 4 is 2B.
+ *
+ *  We shall indicate color with case, where black nodes are uppercase and red
+ *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
+ *  parentheses and have some accompanying text comment.
+ */
+
+/*
+ * Notes on lockless lookups:
+ *
+ * All stores to the tree structure (rb_left and rb_right) must be done using
+ * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
+ * tree structure as seen in program order.
+ *
+ * These two requirements will allow lockless iteration of the tree -- not
+ * correct iteration mind you, tree rotations are not atomic so a lookup might
+ * miss entire subtrees.
+ *
+ * But they do guarantee that any such traversal will only see valid elements
+ * and that it will indeed complete -- does not get stuck in a loop.
+ *
+ * It also guarantees that if the lookup returns an element it is the 'correct'
+ * one. But not returning an element does _NOT_ mean it's not present.
+ *
+ * NOTE:
+ *
+ * Stores to __rb_parent_color are not important for simple lookups so those
+ * are left undone as of now. Nor did I check for loops involving parent
+ * pointers.
+ */
+
+static inline void rb_set_black(struct rb_node *rb)
+{
+	rb->__rb_parent_color |= RB_BLACK;
+}
+
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
+{
+	return (struct rb_node *)red->__rb_parent_color;
+}
+
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+			struct rb_root *root, int color)
+{
+	struct rb_node *parent = rb_parent(old);
+	new->__rb_parent_color = old->__rb_parent_color;
+	rb_set_parent_color(old, new, color);
+	__rb_change_child(old, new, parent, root);
+}
+
+static __always_inline void
+__rb_insert(struct rb_node *node, struct rb_root *root,
+	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
+
+	while (true) {
+		/*
+		 * Loop invariant: node is red.
+		 */
+		if (unlikely(!parent)) {
+			/*
+			 * The inserted node is root. Either this is the
+			 * first node, or we recursed at Case 1 below and
+			 * are no longer violating 4).
+			 */
+			rb_set_parent_color(node, NULL, RB_BLACK);
+			break;
+		}
+
+		/*
+		 * If there is a black parent, we are done.
+		 * Otherwise, take some corrective action as,
+		 * per 4), we don't want a red root or two
+		 * consecutive red nodes.
+		 */
+		if(rb_is_black(parent))
+			break;
+
+		gparent = rb_red_parent(parent);
+
+		tmp = gparent->rb_right;
+		if (parent != tmp) {	/* parent == gparent->rb_left */
+			if (tmp && rb_is_red(tmp)) {
+				/*
+				 * Case 1 - node's uncle is red (color flips).
+				 *
+				 *       G            g
+				 *      / \          / \
+				 *     p   u  -->   P   U
+				 *    /            /
+				 *   n            n
+				 *
+				 * However, since g's parent might be red, and
+				 * 4) does not allow this, we need to recurse
+				 * at g.
+				 */
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
+				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
+				continue;
+			}
+
+			tmp = parent->rb_right;
+			if (node == tmp) {
+				/*
+				 * Case 2 - node's uncle is black and node is
+				 * the parent's right child (left rotate at parent).
+				 *
+				 *      G             G
+				 *     / \           / \
+				 *    p   U  -->    n   U
+				 *     \           /
+				 *      n         p
+				 *
+				 * This still leaves us in violation of 4), the
+				 * continuation into Case 3 will fix that.
+				 */
+				tmp = node->rb_left;
+				WRITE_ONCE(parent->rb_right, tmp);
+				WRITE_ONCE(node->rb_left, parent);
+				if (tmp)
+					rb_set_parent_color(tmp, parent,
+							    RB_BLACK);
+				rb_set_parent_color(parent, node, RB_RED);
+				augment_rotate(parent, node);
+				parent = node;
+				tmp = node->rb_right;
+			}
+
+			/*
+			 * Case 3 - node's uncle is black and node is
+			 * the parent's left child (right rotate at gparent).
+			 *
+			 *        G           P
+			 *       / \         / \
+			 *      p   U  -->  n   g
+			 *     /                 \
+			 *    n                   U
+			 */
+			WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
+			WRITE_ONCE(parent->rb_right, gparent);
+			if (tmp)
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
+			augment_rotate(gparent, parent);
+			break;
+		} else {
+			tmp = gparent->rb_left;
+			if (tmp && rb_is_red(tmp)) {
+				/* Case 1 - color flips */
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
+				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
+				continue;
+			}
+
+			tmp = parent->rb_left;
+			if (node == tmp) {
+				/* Case 2 - right rotate at parent */
+				tmp = node->rb_right;
+				WRITE_ONCE(parent->rb_left, tmp);
+				WRITE_ONCE(node->rb_right, parent);
+				if (tmp)
+					rb_set_parent_color(tmp, parent,
+							    RB_BLACK);
+				rb_set_parent_color(parent, node, RB_RED);
+				augment_rotate(parent, node);
+				parent = node;
+				tmp = node->rb_left;
+			}
+
+			/* Case 3 - left rotate at gparent */
+			WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
+			WRITE_ONCE(parent->rb_left, gparent);
+			if (tmp)
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
+			augment_rotate(gparent, parent);
+			break;
+		}
+	}
+}
+
+/*
+ * Inline version for rb_erase() use - we want to be able to inline
+ * and eliminate the dummy_rotate callback there
+ */
+static __always_inline void
+____rb_erase_color(struct rb_node *parent, struct rb_root *root,
+	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
+
+	while (true) {
+		/*
+		 * Loop invariants:
+		 * - node is black (or NULL on first iteration)
+		 * - node is not the root (parent is not NULL)
+		 * - All leaf paths going through parent and node have a
+		 *   black node count that is 1 lower than other leaf paths.
+		 */
+		sibling = parent->rb_right;
+		if (node != sibling) {	/* node == parent->rb_left */
+			if (rb_is_red(sibling)) {
+				/*
+				 * Case 1 - left rotate at parent
+				 *
+				 *     P               S
+				 *    / \             / \
+				 *   N   s    -->    p   Sr
+				 *      / \         / \
+				 *     Sl  Sr      N   Sl
+				 */
+				tmp1 = sibling->rb_left;
+				WRITE_ONCE(parent->rb_right, tmp1);
+				WRITE_ONCE(sibling->rb_left, parent);
+				rb_set_parent_color(tmp1, parent, RB_BLACK);
+				__rb_rotate_set_parents(parent, sibling, root,
+							RB_RED);
+				augment_rotate(parent, sibling);
+				sibling = tmp1;
+			}
+			tmp1 = sibling->rb_right;
+			if (!tmp1 || rb_is_black(tmp1)) {
+				tmp2 = sibling->rb_left;
+				if (!tmp2 || rb_is_black(tmp2)) {
+					/*
+					 * Case 2 - sibling color flip
+					 * (p could be either color here)
+					 *
+					 *    (p)           (p)
+					 *    / \           / \
+					 *   N   S    -->  N   s
+					 *      / \           / \
+					 *     Sl  Sr        Sl  Sr
+					 *
+					 * This leaves us violating 5) which
+					 * can be fixed by flipping p to black
+					 * if it was red, or by recursing at p.
+					 * p is red when coming from Case 1.
+					 */
+					rb_set_parent_color(sibling, parent,
+							    RB_RED);
+					if (rb_is_red(parent))
+						rb_set_black(parent);
+					else {
+						node = parent;
+						parent = rb_parent(node);
+						if (parent)
+							continue;
+					}
+					break;
+				}
+				/*
+				 * Case 3 - right rotate at sibling
+				 * (p could be either color here)
+				 *
+				 *   (p)           (p)
+				 *   / \           / \
+				 *  N   S    -->  N   sl
+				 *     / \             \
+				 *    sl  Sr            S
+				 *                       \
+				 *                        Sr
+				 *
+				 * Note: p might be red, and then both
+				 * p and sl are red after rotation(which
+				 * breaks property 4). This is fixed in
+				 * Case 4 (in __rb_rotate_set_parents()
+				 *         which set sl the color of p
+				 *         and set p RB_BLACK)
+				 *
+				 *   (p)            (sl)
+				 *   / \            /  \
+				 *  N   sl   -->   P    S
+				 *       \        /      \
+				 *        S      N        Sr
+				 *         \
+				 *          Sr
+				 */
+				tmp1 = tmp2->rb_right;
+				WRITE_ONCE(sibling->rb_left, tmp1);
+				WRITE_ONCE(tmp2->rb_right, sibling);
+				WRITE_ONCE(parent->rb_right, tmp2);
+				if (tmp1)
+					rb_set_parent_color(tmp1, sibling,
+							    RB_BLACK);
+				augment_rotate(sibling, tmp2);
+				tmp1 = sibling;
+				sibling = tmp2;
+			}
+			/*
+			 * Case 4 - left rotate at parent + color flips
+			 * (p and sl could be either color here.
+			 *  After rotation, p becomes black, s acquires
+			 *  p's color, and sl keeps its color)
+			 *
+			 *      (p)             (s)
+			 *      / \             / \
+			 *     N   S     -->   P   Sr
+			 *        / \         / \
+			 *      (sl) sr      N  (sl)
+			 */
+			tmp2 = sibling->rb_left;
+			WRITE_ONCE(parent->rb_right, tmp2);
+			WRITE_ONCE(sibling->rb_left, parent);
+			rb_set_parent_color(tmp1, sibling, RB_BLACK);
+			if (tmp2)
+				rb_set_parent(tmp2, parent);
+			__rb_rotate_set_parents(parent, sibling, root,
+						RB_BLACK);
+			augment_rotate(parent, sibling);
+			break;
+		} else {
+			sibling = parent->rb_left;
+			if (rb_is_red(sibling)) {
+				/* Case 1 - right rotate at parent */
+				tmp1 = sibling->rb_right;
+				WRITE_ONCE(parent->rb_left, tmp1);
+				WRITE_ONCE(sibling->rb_right, parent);
+				rb_set_parent_color(tmp1, parent, RB_BLACK);
+				__rb_rotate_set_parents(parent, sibling, root,
+							RB_RED);
+				augment_rotate(parent, sibling);
+				sibling = tmp1;
+			}
+			tmp1 = sibling->rb_left;
+			if (!tmp1 || rb_is_black(tmp1)) {
+				tmp2 = sibling->rb_right;
+				if (!tmp2 || rb_is_black(tmp2)) {
+					/* Case 2 - sibling color flip */
+					rb_set_parent_color(sibling, parent,
+							    RB_RED);
+					if (rb_is_red(parent))
+						rb_set_black(parent);
+					else {
+						node = parent;
+						parent = rb_parent(node);
+						if (parent)
+							continue;
+					}
+					break;
+				}
+				/* Case 3 - left rotate at sibling */
+				tmp1 = tmp2->rb_left;
+				WRITE_ONCE(sibling->rb_right, tmp1);
+				WRITE_ONCE(tmp2->rb_left, sibling);
+				WRITE_ONCE(parent->rb_left, tmp2);
+				if (tmp1)
+					rb_set_parent_color(tmp1, sibling,
+							    RB_BLACK);
+				augment_rotate(sibling, tmp2);
+				tmp1 = sibling;
+				sibling = tmp2;
+			}
+			/* Case 4 - right rotate at parent + color flips */
+			tmp2 = sibling->rb_right;
+			WRITE_ONCE(parent->rb_left, tmp2);
+			WRITE_ONCE(sibling->rb_right, parent);
+			rb_set_parent_color(tmp1, sibling, RB_BLACK);
+			if (tmp2)
+				rb_set_parent(tmp2, parent);
+			__rb_rotate_set_parents(parent, sibling, root,
+						RB_BLACK);
+			augment_rotate(parent, sibling);
+			break;
+		}
+	}
+}
+
+/* Non-inline version for rb_erase_augmented() use */
+void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+	____rb_erase_color(parent, root, augment_rotate);
+}
+EXPORT_SYMBOL(__rb_erase_color);
+
+/*
+ * Non-augmented rbtree manipulation functions.
+ *
+ * We use dummy augmented callbacks here, and have the compiler optimize them
+ * out of the rb_insert_color() and rb_erase() function definitions.
+ */
+
+static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
+static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
+static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
+
+static const struct rb_augment_callbacks dummy_callbacks = {
+	.propagate = dummy_propagate,
+	.copy = dummy_copy,
+	.rotate = dummy_rotate
+};
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+	__rb_insert(node, root, dummy_rotate);
+}
+EXPORT_SYMBOL(rb_insert_color);
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *rebalance;
+	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
+	if (rebalance)
+		____rb_erase_color(rebalance, root, dummy_rotate);
+}
+EXPORT_SYMBOL(rb_erase);
+
+/*
+ * Augmented rbtree manipulation functions.
+ *
+ * This instantiates the same __always_inline functions as in the non-augmented
+ * case, but this time with user-defined callbacks.
+ */
+
+void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+	__rb_insert(node, root, augment_rotate);
+}
+EXPORT_SYMBOL(__rb_insert_augmented);
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(const struct rb_root *root)
+{
+	struct rb_node	*n;
+
+	n = root->rb_node;
+	if (!n)
+		return NULL;
+	while (n->rb_left)
+		n = n->rb_left;
+	return n;
+}
+EXPORT_SYMBOL(rb_first);
+
+struct rb_node *rb_last(const struct rb_root *root)
+{
+	struct rb_node	*n;
+
+	n = root->rb_node;
+	if (!n)
+		return NULL;
+	while (n->rb_right)
+		n = n->rb_right;
+	return n;
+}
+EXPORT_SYMBOL(rb_last);
+
+struct rb_node *rb_next(const struct rb_node *node)
+{
+	struct rb_node *parent;
+
+	if (RB_EMPTY_NODE(node))
+		return NULL;
+
+	/*
+	 * If we have a right-hand child, go down and then left as far
+	 * as we can.
+	 */
+	if (node->rb_right) {
+		node = node->rb_right;
+		while (node->rb_left)
+			node = node->rb_left;
+		return (struct rb_node *)node;
+	}
+
+	/*
+	 * No right-hand children. Everything down and left is smaller than us,
+	 * so any 'next' node must be in the general direction of our parent.
+	 * Go up the tree; any time the ancestor is a right-hand child of its
+	 * parent, keep going up. First time it's a left-hand child of its
+	 * parent, said parent is our 'next' node.
+	 */
+	while ((parent = rb_parent(node)) && node == parent->rb_right)
+		node = parent;
+
+	return parent;
+}
+EXPORT_SYMBOL(rb_next);
+
+struct rb_node *rb_prev(const struct rb_node *node)
+{
+	struct rb_node *parent;
+
+	if (RB_EMPTY_NODE(node))
+		return NULL;
+
+	/*
+	 * If we have a left-hand child, go down and then right as far
+	 * as we can.
+	 */
+	if (node->rb_left) {
+		node = node->rb_left;
+		while (node->rb_right)
+			node = node->rb_right;
+		return (struct rb_node *)node;
+	}
+
+	/*
+	 * No left-hand children. Go up till we find an ancestor which
+	 * is a right-hand child of its parent.
+	 */
+	while ((parent = rb_parent(node)) && node == parent->rb_left)
+		node = parent;
+
+	return parent;
+}
+EXPORT_SYMBOL(rb_prev);
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+		     struct rb_root *root)
+{
+	struct rb_node *parent = rb_parent(victim);
+
+	/* Copy the pointers/colour from the victim to the replacement */
+	*new = *victim;
+
+	/* Set the surrounding nodes to point to the replacement */
+	if (victim->rb_left)
+		rb_set_parent(victim->rb_left, new);
+	if (victim->rb_right)
+		rb_set_parent(victim->rb_right, new);
+	__rb_change_child(victim, new, parent, root);
+}
+EXPORT_SYMBOL(rb_replace_node);
+
+void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
+			 struct rb_root *root)
+{
+	struct rb_node *parent = rb_parent(victim);
+
+	/* Copy the pointers/colour from the victim to the replacement */
+	*new = *victim;
+
+	/* Set the surrounding nodes to point to the replacement */
+	if (victim->rb_left)
+		rb_set_parent(victim->rb_left, new);
+	if (victim->rb_right)
+		rb_set_parent(victim->rb_right, new);
+
+	/* Set the parent's pointer to the new node last after an RCU barrier
+	 * so that the pointers onwards are seen to be set correctly when doing
+	 * an RCU walk over the tree.
+	 */
+	__rb_change_child_rcu(victim, new, parent, root);
+}
+EXPORT_SYMBOL(rb_replace_node_rcu);
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+	for (;;) {
+		if (node->rb_left)
+			node = node->rb_left;
+		else if (node->rb_right)
+			node = node->rb_right;
+		else
+			return (struct rb_node *)node;
+	}
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+	const struct rb_node *parent;
+	if (!node)
+		return NULL;
+	parent = rb_parent(node);
+
+	/* If we're sitting on node, we've already seen our children */
+	if (parent && node == parent->rb_left && parent->rb_right) {
+		/* If we are the parent's left node, go to the parent's right
+		 * node then all the way down to the left */
+		return rb_left_deepest_node(parent->rb_right);
+	} else
+		/* Otherwise we are the parent's right node, and the parent
+		 * should be next */
+		return (struct rb_node *)parent;
+}
+EXPORT_SYMBOL(rb_next_postorder);
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+	if (!root->rb_node)
+		return NULL;
+
+	return rb_left_deepest_node(root->rb_node);
+}
+EXPORT_SYMBOL(rb_first_postorder);

utils/src/rbtree.h

@@ -0,0 +1,328 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  
+
+  linux/include/linux/rbtree.h
+
+  To use rbtrees you'll have to implement your own insert and search cores.
+  This will avoid us to use callbacks and to drop drammatically performances.
+  I know it's not the cleaner way,  but in C (not in C++) to get
+  performances and genericity...
+
+  See Documentation/core-api/rbtree.rst for documentation and samples.
+*/
+
+#ifndef	_LINUX_RBTREE_H
+#define	_LINUX_RBTREE_H
+
+#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
+
+#define	rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
+#define RB_EMPTY_NODE(node)  \
+	((node)->__rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  \
+	((node)->__rb_parent_color = (unsigned long)(node))
+
+
+extern void rb_insert_color(struct rb_node *, struct rb_root *);
+extern void rb_erase(struct rb_node *, struct rb_root *);
+
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
+
+/* Postorder iteration - always visit the parent after its children */
+extern struct rb_node *rb_first_postorder(const struct rb_root *);
+extern struct rb_node *rb_next_postorder(const struct rb_node *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+			    struct rb_root *root);
+extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
+				struct rb_root *root);
+
+static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
+				struct rb_node **rb_link)
+{
+	node->__rb_parent_color = (unsigned long)parent;
+	node->rb_left = node->rb_right = NULL;
+
+	*rb_link = node;
+}
+
+static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
+				    struct rb_node **rb_link)
+{
+	node->__rb_parent_color = (unsigned long)parent;
+	node->rb_left = node->rb_right = NULL;
+
+	rcu_assign_pointer(*rb_link, node);
+}
+
+#define rb_entry_safe(ptr, type, member) \
+	({ typeof(ptr) ____ptr = (ptr); \
+	   ____ptr ? rb_entry(____ptr, type, member) : NULL; \
+	})
+
+/**
+ * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
+ * given type allowing the backing memory of @pos to be invalidated
+ *
+ * @pos:	the 'type *' to use as a loop cursor.
+ * @n:		another 'type *' to use as temporary storage
+ * @root:	'rb_root *' of the rbtree.
+ * @field:	the name of the rb_node field within 'type'.
+ *
+ * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
+ * list_for_each_entry_safe() and allows the iteration to continue independent
+ * of changes to @pos by the body of the loop.
+ *
+ * Note, however, that it cannot handle other modifications that re-order the
+ * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
+ * rb_erase() may rebalance the tree, causing us to miss some nodes.
+ */
+#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
+	for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
+	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
+			typeof(*pos), field); 1; }); \
+	     pos = n)
+
+/* Same as rb_first(), but O(1) */
+#define rb_first_cached(root) (root)->rb_leftmost
+
+static inline void rb_insert_color_cached(struct rb_node *node,
+					  struct rb_root_cached *root,
+					  bool leftmost)
+{
+	if (leftmost)
+		root->rb_leftmost = node;
+	rb_insert_color(node, &root->rb_root);
+}
+
+
+static inline struct rb_node *
+rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
+{
+	struct rb_node *leftmost = NULL;
+
+	if (root->rb_leftmost == node)
+		leftmost = root->rb_leftmost = rb_next(node);
+
+	rb_erase(node, &root->rb_root);
+
+	return leftmost;
+}
+
+static inline void rb_replace_node_cached(struct rb_node *victim,
+					  struct rb_node *new,
+					  struct rb_root_cached *root)
+{
+	if (root->rb_leftmost == victim)
+		root->rb_leftmost = new;
+	rb_replace_node(victim, new, &root->rb_root);
+}
+
+/*
+ * The below helper functions use 2 operators with 3 different
+ * calling conventions. The operators are related like:
+ *
+ *	comp(a->key,b) < 0  := less(a,b)
+ *	comp(a->key,b) > 0  := less(b,a)
+ *	comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
+ *
+ * If these operators define a partial order on the elements we make no
+ * guarantee on which of the elements matching the key is found. See
+ * rb_find().
+ *
+ * The reason for this is to allow the find() interface without requiring an
+ * on-stack dummy object, which might not be feasible due to object size.
+ */
+
+/**
+ * rb_add_cached() - insert @node into the leftmost cached tree @tree
+ * @node: node to insert
+ * @tree: leftmost cached tree to insert @node into
+ * @less: operator defining the (partial) node order
+ *
+ * Returns @node when it is the new leftmost, or NULL.
+ */
+static __always_inline struct rb_node *
+rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
+	      bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	bool leftmost = true;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent)) {
+			link = &parent->rb_left;
+		} else {
+			link = &parent->rb_right;
+			leftmost = false;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+
+	return leftmost ? node : NULL;
+}
+
+/**
+ * rb_add() - insert @node into @tree
+ * @node: node to insert
+ * @tree: tree to insert @node into
+ * @less: operator defining the (partial) node order
+ */
+static __always_inline void
+rb_add(struct rb_node *node, struct rb_root *tree,
+       bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_node;
+	struct rb_node *parent = NULL;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent))
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+}
+
+/**
+ * rb_find_add() - find equivalent @node in @tree, or add @node
+ * @node: node to look-for / insert
+ * @tree: tree to search / modify
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @node, or NULL when no match is found and @node
+ * is inserted.
+ */
+static __always_inline struct rb_node *
+rb_find_add(struct rb_node *node, struct rb_root *tree,
+	    int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_node;
+	struct rb_node *parent = NULL;
+	int c;
+
+	while (*link) {
+		parent = *link;
+		c = cmp(node, parent);
+
+		if (c < 0)
+			link = &parent->rb_left;
+		else if (c > 0)
+			link = &parent->rb_right;
+		else
+			return parent;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+	return NULL;
+}
+
+/**
+ * rb_find() - find @key in tree @tree
+ * @key: key to match
+ * @tree: tree to search
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @key or NULL.
+ */
+static __always_inline struct rb_node *
+rb_find(const void *key, const struct rb_root *tree,
+	int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+
+	while (node) {
+		int c = cmp(key, node);
+
+		if (c < 0)
+			node = node->rb_left;
+		else if (c > 0)
+			node = node->rb_right;
+		else
+			return node;
+	}
+
+	return NULL;
+}
+
+/**
+ * rb_find_first() - find the first @key in @tree
+ * @key: key to match
+ * @tree: tree to search
+ * @cmp: operator defining node order
+ *
+ * Returns the leftmost node matching @key, or NULL.
+ */
+static __always_inline struct rb_node *
+rb_find_first(const void *key, const struct rb_root *tree,
+	      int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+	struct rb_node *match = NULL;
+
+	while (node) {
+		int c = cmp(key, node);
+
+		if (c <= 0) {
+			if (!c)
+				match = node;
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		}
+	}
+
+	return match;
+}
+
+/**
+ * rb_next_match() - find the next @key in @tree
+ * @key: key to match
+ * @tree: tree to search
+ * @cmp: operator defining node order
+ *
+ * Returns the next node matching @key, or NULL.
+ */
+static __always_inline struct rb_node *
+rb_next_match(const void *key, struct rb_node *node,
+	      int (*cmp)(const void *key, const struct rb_node *))
+{
+	node = rb_next(node);
+	if (node && cmp(key, node))
+		node = NULL;
+	return node;
+}
+
+/**
+ * rb_for_each() - iterates a subtree matching @key
+ * @node: iterator
+ * @key: key to match
+ * @tree: tree to search
+ * @cmp: operator defining node order
+ */
+#define rb_for_each(node, key, tree, cmp) \
+	for ((node) = rb_find_first((key), (tree), (cmp)); \
+	     (node); (node) = rb_next_match((key), (node), (cmp)))
+
+#endif	/* _LINUX_RBTREE_H */

utils/src/rbtree_augmented.h

@@ -0,0 +1,313 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  (C) 2002  David Woodhouse <dwmw2@infradead.org>
+  (C) 2012  Michel Lespinasse <walken@google.com>
+
+
+  linux/include/linux/rbtree_augmented.h
+*/
+
+#ifndef _LINUX_RBTREE_AUGMENTED_H
+#define _LINUX_RBTREE_AUGMENTED_H
+
+/*
+ * Please note - only struct rb_augment_callbacks and the prototypes for
+ * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
+ * The rest are implementation details you are not expected to depend on.
+ *
+ * See Documentation/core-api/rbtree.rst for documentation and samples.
+ */
+
+struct rb_augment_callbacks {
+	void (*propagate)(struct rb_node *node, struct rb_node *stop);
+	void (*copy)(struct rb_node *old, struct rb_node *new);
+	void (*rotate)(struct rb_node *old, struct rb_node *new);
+};
+
+extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+
+/*
+ * Fixup the rbtree and update the augmented information when rebalancing.
+ *
+ * On insertion, the user must update the augmented information on the path
+ * leading to the inserted node, then call rb_link_node() as usual and
+ * rb_insert_augmented() instead of the usual rb_insert_color() call.
+ * If rb_insert_augmented() rebalances the rbtree, it will callback into
+ * a user provided function to update the augmented information on the
+ * affected subtrees.
+ */
+static inline void
+rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+		    const struct rb_augment_callbacks *augment)
+{
+	__rb_insert_augmented(node, root, augment->rotate);
+}
+
+static inline void
+rb_insert_augmented_cached(struct rb_node *node,
+			   struct rb_root_cached *root, bool newleft,
+			   const struct rb_augment_callbacks *augment)
+{
+	if (newleft)
+		root->rb_leftmost = node;
+	rb_insert_augmented(node, &root->rb_root, augment);
+}
+
+/*
+ * Template for declaring augmented rbtree callbacks (generic case)
+ *
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ */
+
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
+			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
+static inline void							\
+RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
+{									\
+	while (rb != stop) {						\
+		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
+		if (RBCOMPUTE(node, true))				\
+			break;						\
+		rb = rb_parent(&node->RBFIELD);				\
+	}								\
+}									\
+static inline void							\
+RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
+{									\
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
+}									\
+static void								\
+RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
+{									\
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
+	RBCOMPUTE(old, false);						\
+}									\
+RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
+	.propagate = RBNAME ## _propagate,				\
+	.copy = RBNAME ## _copy,					\
+	.rotate = RBNAME ## _rotate					\
+};
+
+/*
+ * Template for declaring augmented rbtree callbacks,
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
+ *
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBTYPE:      type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
+ */
+
+#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	      \
+				 RBTYPE, RBAUGMENTED, RBCOMPUTE)	      \
+static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
+{									      \
+	RBSTRUCT *child;						      \
+	RBTYPE max = RBCOMPUTE(node);					      \
+	if (node->RBFIELD.rb_left) {					      \
+		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
+		if (child->RBAUGMENTED > max)				      \
+			max = child->RBAUGMENTED;			      \
+	}								      \
+	if (node->RBFIELD.rb_right) {					      \
+		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
+		if (child->RBAUGMENTED > max)				      \
+			max = child->RBAUGMENTED;			      \
+	}								      \
+	if (exit && node->RBAUGMENTED == max)				      \
+		return true;						      \
+	node->RBAUGMENTED = max;					      \
+	return false;							      \
+}									      \
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,					      \
+		     RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
+
+
+#define	RB_RED		0
+#define	RB_BLACK	1
+
+#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc)     ((pc) & 1)
+#define __rb_is_black(pc)  __rb_color(pc)
+#define __rb_is_red(pc)    (!__rb_color(pc))
+#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
+}
+
+static inline void rb_set_parent_color(struct rb_node *rb,
+				       struct rb_node *p, int color)
+{
+	rb->__rb_parent_color = (unsigned long)p | color;
+}
+
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+		  struct rb_node *parent, struct rb_root *root)
+{
+	if (parent) {
+		if (parent->rb_left == old)
+			WRITE_ONCE(parent->rb_left, new);
+		else
+			WRITE_ONCE(parent->rb_right, new);
+	} else
+		WRITE_ONCE(root->rb_node, new);
+}
+
+static inline void
+__rb_change_child_rcu(struct rb_node *old, struct rb_node *new,
+		      struct rb_node *parent, struct rb_root *root)
+{
+	if (parent) {
+		if (parent->rb_left == old)
+			rcu_assign_pointer(parent->rb_left, new);
+		else
+			rcu_assign_pointer(parent->rb_right, new);
+	} else
+		rcu_assign_pointer(root->rb_node, new);
+}
+
+extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+
+static __always_inline struct rb_node *
+__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+		     const struct rb_augment_callbacks *augment)
+{
+	struct rb_node *child = node->rb_right;
+	struct rb_node *tmp = node->rb_left;
+	struct rb_node *parent, *rebalance;
+	unsigned long pc;
+
+	if (!tmp) {
+		/*
+		 * Case 1: node to erase has no more than 1 child (easy!)
+		 *
+		 * Note that if there is one child it must be red due to 5)
+		 * and node must be black due to 4). We adjust colors locally
+		 * so as to bypass __rb_erase_color() later on.
+		 */
+		pc = node->__rb_parent_color;
+		parent = __rb_parent(pc);
+		__rb_change_child(node, child, parent, root);
+		if (child) {
+			child->__rb_parent_color = pc;
+			rebalance = NULL;
+		} else
+			rebalance = __rb_is_black(pc) ? parent : NULL;
+		tmp = parent;
+	} else if (!child) {
+		/* Still case 1, but this time the child is node->rb_left */
+		tmp->__rb_parent_color = pc = node->__rb_parent_color;
+		parent = __rb_parent(pc);
+		__rb_change_child(node, tmp, parent, root);
+		rebalance = NULL;
+		tmp = parent;
+	} else {
+		struct rb_node *successor = child, *child2;
+
+		tmp = child->rb_left;
+		if (!tmp) {
+			/*
+			 * Case 2: node's successor is its right child
+			 *
+			 *    (n)          (s)
+			 *    / \          / \
+			 *  (x) (s)  ->  (x) (c)
+			 *        \
+			 *        (c)
+			 */
+			parent = successor;
+			child2 = successor->rb_right;
+
+			augment->copy(node, successor);
+		} else {
+			/*
+			 * Case 3: node's successor is leftmost under
+			 * node's right child subtree
+			 *
+			 *    (n)          (s)
+			 *    / \          / \
+			 *  (x) (y)  ->  (x) (y)
+			 *      /            /
+			 *    (p)          (p)
+			 *    /            /
+			 *  (s)          (c)
+			 *    \
+			 *    (c)
+			 */
+			do {
+				parent = successor;
+				successor = tmp;
+				tmp = tmp->rb_left;
+			} while (tmp);
+			child2 = successor->rb_right;
+			WRITE_ONCE(parent->rb_left, child2);
+			WRITE_ONCE(successor->rb_right, child);
+			rb_set_parent(child, successor);
+
+			augment->copy(node, successor);
+			augment->propagate(parent, successor);
+		}
+
+		tmp = node->rb_left;
+		WRITE_ONCE(successor->rb_left, tmp);
+		rb_set_parent(tmp, successor);
+
+		pc = node->__rb_parent_color;
+		tmp = __rb_parent(pc);
+		__rb_change_child(node, successor, tmp, root);
+
+		if (child2) {
+			rb_set_parent_color(child2, parent, RB_BLACK);
+			rebalance = NULL;
+		} else {
+			rebalance = rb_is_black(successor) ? parent : NULL;
+		}
+		successor->__rb_parent_color = pc;
+		tmp = successor;
+	}
+
+	augment->propagate(tmp, NULL);
+	return rebalance;
+}
+
+static __always_inline void
+rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+		   const struct rb_augment_callbacks *augment)
+{
+	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
+	if (rebalance)
+		__rb_erase_color(rebalance, root, augment->rotate);
+}
+
+static __always_inline void
+rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
+			  const struct rb_augment_callbacks *augment)
+{
+	if (root->rb_leftmost == node)
+		root->rb_leftmost = rb_next(node);
+	rb_erase_augmented(node, &root->rb_root, augment);
+}
+
+#endif	/* _LINUX_RBTREE_AUGMENTED_H */

utils/src/rbtree_types.h

@@ -0,0 +1,34 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#ifndef _LINUX_RBTREE_TYPES_H
+#define _LINUX_RBTREE_TYPES_H
+
+struct rb_node {
+	unsigned long  __rb_parent_color;
+	struct rb_node *rb_right;
+	struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+/* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root {
+	struct rb_node *rb_node;
+};
+
+/*
+ * Leftmost-cached rbtrees.
+ *
+ * We do not cache the rightmost node based on footprint
+ * size vs number of potential users that could benefit
+ * from O(1) rb_last(). Just not worth it, users that want
+ * this feature can always implement the logic explicitly.
+ * Furthermore, users that want to cache both pointers may
+ * find it a bit asymmetric, but that's ok.
+ */
+struct rb_root_cached {
+	struct rb_root rb_root;
+	struct rb_node *rb_leftmost;
+};
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
+
+#endif

utils/src/srch.c

@@ -44,3 +44,37 @@ int srch_decode_entry(void *buf, struct scoutfs_srch_entry *sre,
 
 	return tot;
 }
+
+static int encode_u64(__le64 *buf, u64 val)
+{
+	int bytes;
+
+	val = (val << 1) ^ ((s64)val >> 63); /* shift sign extend */
+	bytes = (fls64(val) + 7) >> 3;
+
+	put_unaligned_le64(val, buf);
+	return bytes;
+}
+
+int srch_encode_entry(void *buf, struct scoutfs_srch_entry *sre, struct scoutfs_srch_entry *prev)
+{
+	u64 diffs[] = {
+		le64_to_cpu(sre->hash) - le64_to_cpu(prev->hash),
+		le64_to_cpu(sre->ino) - le64_to_cpu(prev->ino),
+		le64_to_cpu(sre->id) - le64_to_cpu(prev->id),
+	};
+	u16 lengths = 0;
+	int bytes;
+	int tot = 2;
+	int i;
+
+	for (i = 0; i < array_size(diffs); i++) {
+		bytes = encode_u64(buf + tot, diffs[i]);
+		lengths |= bytes << (i << 2);
+		tot += bytes;
+	}
+
+	put_unaligned_le16(lengths, buf);
+
+	return tot;
+}

utils/src/srch.h

@@ -3,5 +3,6 @@
 
 int srch_decode_entry(void *buf, struct scoutfs_srch_entry *sre,
 		      struct scoutfs_srch_entry *prev);
+int srch_encode_entry(void *buf, struct scoutfs_srch_entry *sre, struct scoutfs_srch_entry *prev);
 
 #endif

utils/src/util.c

@@ -145,7 +145,7 @@ int read_block_verify(int fd, u32 magic, u64 fsid, u64 blkno, int shift, void **
 		else if (fsid != 0 && le64_to_cpu(hdr->fsid) != fsid)
 			fprintf(stderr, "read blkno %llu has bad fsid %016llx != expected %016llx\n",
 				blkno, le64_to_cpu(hdr->fsid), fsid);
-		else if (le32_to_cpu(hdr->blkno) != blkno)
+		else if (le64_to_cpu(hdr->blkno) != blkno)
 			fprintf(stderr, "read blkno %llu has bad blkno %llu != expected %llu\n",
 				blkno, le64_to_cpu(hdr->blkno), blkno);
 		else

utils/src/util.h

@@ -2,6 +2,7 @@
 #define _UTIL_H_
 
 #include <unistd.h>
+#include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>
@@ -69,6 +70,8 @@ do {				\
 #define container_of(ptr, type, memb) \
 	((type *)((void *)(ptr) - offsetof(type, memb)))
 
+#define NSEC_PER_SEC 1000000000
+
 #define BITS_PER_LONG (sizeof(long) * 8)
 #define U8_MAX ((u8)~0ULL)
 #define U16_MAX ((u16)~0ULL)
@@ -81,6 +84,7 @@ do {				\
 							\
 	(_x == 0 ? 0 : 64 - __builtin_clzll(_x));	\
 })
+#define fls64(x) flsll(x)
 
 #define ilog2(x)					\
 ({							\
@@ -98,6 +102,16 @@ emit_get_unaligned_le(16)
 emit_get_unaligned_le(32)
 emit_get_unaligned_le(64)
 
+#define emit_put_unaligned_le(nr)				\
+static inline void put_unaligned_le##nr(u##nr val, void *buf)	\
+{								\
+	__le##nr x = cpu_to_le##nr(val);			\
+	memcpy(buf, &x, sizeof(x));				\
+}
+emit_put_unaligned_le(16)
+emit_put_unaligned_le(32)
+emit_put_unaligned_le(64)
+
 /*
  * return -1,0,+1 based on the memcmp comparison of the minimum of their
  * two lengths.  If their min shared bytes are equal but the lengths