fs: dentry cache implementation

This adds the Linux dentry cache implementation to barebox.

Until now every filesystem driver resolves the full path to a file for
itself. This leads to code duplication and is error prone since
resolving paths is a complicated task. Also it can narrow down the
lookup performance since barebox only knows ASCII paths and has no way
of caching lookups.

With this patch we get the Linux dcache implementation. The path
resolving code from fs/namei.c is nearly taken as-is, minus the RCU
and locking code. Dcaching is made simple as of now: We simply cache
everything and never release any dentries. Although we do reference
counting for inodes and dentries it is effectively not used yet.
We never free anything until a fs is unmounted in which case we free
everything no matter if references are taken or not.

This patch also contains a wrapper in fs/legacy.c to support
filesystems with the old API.

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>

7 files changed, 279 insertions, 59 deletions

diff --git a/include/dirent.h b/include/dirent.h
index 5ee4c2063e..1df5d90452 100644
--- a/include/dirent.h
+++ b/include/dirent.h
@@ -1,6 +1,8 @@
 #ifndef __DIRENT_H
 #define __DIRENT_H
 
+#include <linux/list.h>
+
 struct dirent {
 	char d_name[256];
 };
@@ -11,6 +13,7 @@ typedef struct dir {
 	struct node_d *node;
 	struct dirent d;
 	void *priv; /* private data for the fs driver */
+	struct list_head entries;
 } DIR;
 
 DIR *opendir(const char *pathname);
diff --git a/include/fs.h b/include/fs.h
index e6fcd044dd..181318f404 100644
--- a/include/fs.h
+++ b/include/fs.h
@@ -31,14 +31,15 @@ typedef struct filep {
 	/* private fields. Mapping between FILE and filedescriptor number     */
 	int no;
 	char in_use;
+
+	struct inode *f_inode;
+	struct dentry *dentry;
 } FILE;
 
 #define FS_DRIVER_NO_DEV	1
 
 struct fs_driver_d {
 	int (*probe) (struct device_d *dev);
-	int (*mkdir)(struct device_d *dev, const char *pathname);
-	int (*rmdir)(struct device_d *dev, const char *pathname);
 
 	/* create a file. The file is guaranteed to not exist */
 	int (*create)(struct device_d *dev, const char *pathname, mode_t mode);
@@ -47,11 +48,6 @@ struct fs_driver_d {
 	/* Truncate a file to given size */
 	int (*truncate)(struct device_d *dev, FILE *f, ulong size);
 
-	int (*symlink)(struct device_d *dev, const char *pathname,
-		       const char *newpath);
-	int (*readlink)(struct device_d *dev, const char *pathname, char *name,
-			size_t size);
-
 	int (*open)(struct device_d *dev, FILE *f, const char *pathname);
 	int (*close)(struct device_d *dev, FILE *f);
 	int (*read)(struct device_d *dev, FILE *f, void *buf, size_t size);
@@ -59,11 +55,6 @@ struct fs_driver_d {
 	int (*flush)(struct device_d *dev, FILE *f);
 	loff_t (*lseek)(struct device_d *dev, FILE *f, loff_t pos);
 
-	struct dir* (*opendir)(struct device_d *dev, const char *pathname);
-	struct dirent* (*readdir)(struct device_d *dev, struct dir *dir);
-	int (*closedir)(struct device_d *dev, DIR *dir);
-	int (*stat)(struct device_d *dev, const char *file, struct stat *stat);
-
 	int (*ioctl)(struct device_d *dev, FILE *f, int request, void *buf);
 	int (*erase)(struct device_d *dev, FILE *f, loff_t count,
 			loff_t offset);
@@ -72,6 +63,18 @@ struct fs_driver_d {
 
 	int (*memmap)(struct device_d *dev, FILE *f, void **map, int flags);
 
+	/* legacy */
+	int (*mkdir)(struct device_d *dev, const char *pathname);
+	int (*rmdir)(struct device_d *dev, const char *pathname);
+	int (*symlink)(struct device_d *dev, const char *pathname,
+		       const char *newpath);
+	int (*readlink)(struct device_d *dev, const char *pathname, char *name,
+			size_t size);
+	struct dir* (*opendir)(struct device_d *dev, const char *pathname);
+	struct dirent* (*readdir)(struct device_d *dev, struct dir *dir);
+	int (*closedir)(struct device_d *dev, DIR *dir);
+	int (*stat)(struct device_d *dev, const char *file, struct stat *stat);
+
 	struct driver_d drv;
 
 	enum filetype type;
@@ -99,6 +102,10 @@ struct fs_device_d {
 	struct list_head list;
 	char *options;
 	char *linux_rootarg;
+
+	struct super_block sb;
+
+	struct vfsmount vfsmount;
 };
 
 bool __is_tftp_fs(const char *path);
@@ -135,12 +142,6 @@ int ls(const char *path, ulong flags);
 
 char *mkmodestr(unsigned long mode, char *str);
 
-/*
- * This function turns 'path' into an absolute path and removes all occurrences
- * of "..", "." and double slashes. The returned string must be freed wit free().
- */
-char *normalise_path(const char *path);
-
 char *canonicalize_path(const char *pathname);
 
 char *get_mounted_path(const char *path);
@@ -154,6 +155,7 @@ void automount_remove(const char *_path);
 int automount_add(const char *path, const char *cmd);
 void automount_print(void);
 
+int fs_init_legacy(struct fs_device_d *fsdev);
 int fsdev_open_cdev(struct fs_device_d *fsdev);
 const char *cdev_get_mount_path(struct cdev *cdev);
 const char *cdev_mount_default(struct cdev *cdev, const char *fsoptions);
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index dfb466722c..16244129bf 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -53,6 +53,10 @@ struct dentry {
 	spinlock_t d_lock;		/* per dentry lock */
 	struct inode *d_inode;		/* Where the name belongs to - NULL is
 					 * negative */
+
+	unsigned int d_count;
+	const struct dentry_operations *d_op;
+
 	/*
 	 * The next three fields are touched by __d_lookup.  Place them here
 	 * so they all fit in a cache line.
@@ -65,8 +69,8 @@ struct dentry {
 	/*
 	 * d_child and d_rcu can share memory
 	 */
+	struct list_head d_child;       /* child of parent list */
 	struct list_head d_subdirs;	/* our children */
-	struct list_head d_alias;	/* inode alias list */
 	unsigned long d_time;		/* used by d_revalidate */
 	struct super_block *d_sb;	/* The root of the dentry tree */
 	void *d_fsdata;			/* fs-specific data */
@@ -74,7 +78,108 @@ struct dentry {
 	struct dcookie_struct *d_cookie; /* cookie, if any */
 #endif
 	int d_mounted;
-	unsigned char d_iname[DNAME_INLINE_LEN_MIN];	/* small names */
+	unsigned char *name;		/* all names */
+};
+
+struct dentry_operations {
 };
 
+struct dentry * d_make_root(struct inode *);
+void d_add(struct dentry *, struct inode *);
+struct dentry * d_alloc_anon(struct super_block *);
+void d_set_d_op(struct dentry *dentry, const struct dentry_operations *op);
+void d_instantiate(struct dentry *dentry, struct inode *inode);
+void d_delete(struct dentry *);
+struct dentry *dget(struct dentry *);
+void dput(struct dentry *);
+
+#define DCACHE_ENTRY_TYPE		0x00700000
+#define DCACHE_MISS_TYPE		0x00000000 /* Negative dentry (maybe fallthru to nowhere) */
+#define DCACHE_WHITEOUT_TYPE		0x00100000 /* Whiteout dentry (stop pathwalk) */
+#define DCACHE_DIRECTORY_TYPE		0x00200000 /* Normal directory */
+#define DCACHE_AUTODIR_TYPE		0x00300000 /* Lookupless directory (presumed automount) */
+#define DCACHE_REGULAR_TYPE		0x00400000 /* Regular file type (or fallthru to such) */
+#define DCACHE_SPECIAL_TYPE		0x00500000 /* Other file type (or fallthru to such) */
+#define DCACHE_SYMLINK_TYPE		0x00600000 /* Symlink (or fallthru to such) */
+
+#define DCACHE_FALLTHRU			0x01000000 /* Fall through to lower layer */
+#define DCACHE_CANT_MOUNT		0x00000100
+#define DCACHE_MOUNTED                  0x00010000 /* is a mountpoint */
+#define DCACHE_NEED_AUTOMOUNT           0x00020000 /* handle automount on this dir */
+#define DCACHE_MANAGED_DENTRY \
+		(DCACHE_MOUNTED|DCACHE_NEED_AUTOMOUNT)
+
+static inline bool d_mountpoint(const struct dentry *dentry)
+{
+	return dentry->d_flags & DCACHE_MOUNTED;
+}
+
+/*
+ * Directory cache entry type accessor functions.
+ */
+static inline unsigned __d_entry_type(const struct dentry *dentry)
+{
+	return dentry->d_flags & DCACHE_ENTRY_TYPE;
+}
+
+static inline bool d_is_miss(const struct dentry *dentry)
+{
+	return __d_entry_type(dentry) == DCACHE_MISS_TYPE;
+}
+
+static inline bool d_can_lookup(const struct dentry *dentry)
+{
+	return __d_entry_type(dentry) == DCACHE_DIRECTORY_TYPE;
+}
+
+static inline bool d_is_autodir(const struct dentry *dentry)
+{
+	return __d_entry_type(dentry) == DCACHE_AUTODIR_TYPE;
+}
+
+static inline bool d_is_dir(const struct dentry *dentry)
+{
+	return d_can_lookup(dentry) || d_is_autodir(dentry);
+}
+
+static inline bool d_is_symlink(const struct dentry *dentry)
+{
+	return __d_entry_type(dentry) == DCACHE_SYMLINK_TYPE;
+}
+
+static inline bool d_is_reg(const struct dentry *dentry)
+{
+	return __d_entry_type(dentry) == DCACHE_REGULAR_TYPE;
+}
+
+static inline bool d_is_special(const struct dentry *dentry)
+{
+	return __d_entry_type(dentry) == DCACHE_SPECIAL_TYPE;
+}
+
+static inline bool d_is_file(const struct dentry *dentry)
+{
+	return d_is_reg(dentry) || d_is_special(dentry);
+}
+
+static inline bool d_is_negative(const struct dentry *dentry)
+{
+	// TODO: check d_is_whiteout(dentry) also.
+	return d_is_miss(dentry);
+}
+
+static inline bool d_is_positive(const struct dentry *dentry)
+{
+	return !d_is_negative(dentry);
+}
+
+static inline struct inode *d_inode(const struct dentry *dentry)
+{
+	return dentry->d_inode;
+}
+
+#define IS_ROOT(x) ((x) == (x)->d_parent)
+
+char *dpath(struct dentry *dentry, struct dentry *root);
+
 #endif	/* __LINUX_DCACHE_H */
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 153c464470..4550e8feeb 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -34,7 +34,18 @@
 #define DT_SOCK		12
 #define DT_WHT		14
 
+/*
+ * This is the "filldir" function type, used by readdir() to let
+ * the kernel specify what kind of dirent layout it wants to have.
+ * This allows the kernel to read directories into kernel space or
+ * to have different dirent layouts depending on the binary type.
+ */
+struct dir_context;
+typedef int (*filldir_t)(struct dir_context *, const char *, int, loff_t, u64,
+			 unsigned);
+
 struct dir_context {
+	const filldir_t actor;
 	loff_t pos;
 };
 
@@ -94,12 +105,8 @@ struct inode {
 	};
 	uid_t			i_uid;
 	gid_t			i_gid;
-	dev_t			i_rdev;
 	u64			i_version;
 	loff_t			i_size;
-#ifdef __NEED_I_SIZE_ORDERED
-	seqcount_t		i_size_seqcount;
-#endif
 	struct timespec		i_atime;
 	struct timespec		i_mtime;
 	struct timespec		i_ctime;
@@ -107,39 +114,19 @@ struct inode {
 	blkcnt_t		i_blocks;
 	unsigned short          i_bytes;
 	umode_t			i_mode;
-	spinlock_t		i_lock;	/* i_blocks, i_bytes, maybe i_size */
-	struct mutex		i_mutex;
-	struct rw_semaphore	i_alloc_sem;
 	const struct inode_operations	*i_op;
 	const struct file_operations	*i_fop;	/* former ->i_op->default_file_ops */
 	struct super_block	*i_sb;
-	struct file_lock	*i_flock;
-#ifdef CONFIG_QUOTA
-	struct dquot		*i_dquot[MAXQUOTAS];
-#endif
-	struct list_head	i_devices;
-	int			i_cindex;
 
 	__u32			i_generation;
 
-#ifdef CONFIG_DNOTIFY
-	unsigned long		i_dnotify_mask; /* Directory notify events */
-	struct dnotify_struct	*i_dnotify; /* for directory notifications */
-#endif
-
-#ifdef CONFIG_INOTIFY
-	struct list_head	inotify_watches; /* watches on this inode */
-	struct mutex		inotify_mutex;	/* protects the watches list */
-#endif
-
 	unsigned long		i_state;
-	unsigned long		dirtied_when;	/* jiffies of first dirtying */
 
 	unsigned int		i_flags;
+	unsigned int		i_count;
+
+	char			*i_link;
 
-#ifdef CONFIG_SECURITY
-	void			*i_security;
-#endif
 	void			*i_private; /* fs or device private pointer */
 };
 
@@ -199,19 +186,9 @@ struct super_block {
 	   Cannot be worse than a second */
 	u32		   s_time_gran;
 
-	/*
-	 * Filesystem subtype.  If non-empty the filesystem type field
-	 * in /proc/mounts will be "type.subtype"
-	 */
-	char *s_subtype;
-
-	/*
-	 * Saved mount options for lazy filesystems using
-	 * generic_show_options()
-	 */
-	char *s_options;
-
 	/* Number of inodes with nlink == 0 but still referenced */
+
+	const struct dentry_operations *s_d_op; /* default d_op for dentries */
 };
 
 struct file_system_type {
@@ -405,4 +382,80 @@ static inline loff_t i_size_read(const struct inode *inode)
 	return inode->i_size;
 }
 
+struct inode *new_inode(struct super_block *sb);
+unsigned int get_next_ino(void);
+void iput(struct inode *);
+struct inode *iget(struct inode *);
+void inc_nlink(struct inode *inode);
+
+struct inode_operations {
+	struct dentry * (*lookup) (struct inode *,struct dentry *, unsigned int);
+
+	const char *(*get_link) (struct dentry *dentry, struct inode *inode);
+
+	int (*create) (struct inode *,struct dentry *, umode_t);
+	int (*link) (struct dentry *,struct inode *,struct dentry *);
+	int (*unlink) (struct inode *,struct dentry *);
+	int (*symlink) (struct inode *,struct dentry *,const char *);
+	int (*mkdir) (struct inode *,struct dentry *,umode_t);
+	int (*rmdir) (struct inode *,struct dentry *);
+	int (*rename) (struct inode *, struct dentry *,
+		       struct inode *, struct dentry *, unsigned int);
+};
+
+static inline ino_t parent_ino(struct dentry *dentry)
+{
+	return dentry->d_parent->d_inode->i_ino;
+}
+
+static inline bool dir_emit(struct dir_context *ctx,
+			    const char *name, int namelen,
+			    u64 ino, unsigned type)
+{
+	return ctx->actor(ctx, name, namelen, ctx->pos, ino, type) == 0;
+}
+
+static inline bool dir_emit_dot(struct file *file, struct dir_context *ctx)
+{
+	return ctx->actor(ctx, ".", 1, ctx->pos,
+			file->f_path.dentry->d_inode->i_ino, DT_DIR) == 0;
+}
+static inline bool dir_emit_dotdot(struct file *file, struct dir_context *ctx)
+{
+	return ctx->actor(ctx, "..", 2, ctx->pos,
+			parent_ino(file->f_path.dentry), DT_DIR) == 0;
+}
+
+static inline void dir_emit_dots(struct file *file, struct dir_context *ctx)
+{
+	if (ctx->pos == 0) {
+		dir_emit_dot(file, ctx);
+		ctx->pos = 1;
+	}
+	if (ctx->pos == 1) {
+		dir_emit_dotdot(file, ctx);
+		ctx->pos = 2;
+	}
+}
+
+struct file_operations {
+	int (*iterate) (struct file *, struct dir_context *);
+	ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
+	ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
+	int (*ioctl) (struct file *, int request, void *buf);
+	int (*truncate) (struct file *, loff_t);
+};
+
+void drop_nlink(struct inode *inode);
+
+extern const struct file_operations simple_dir_operations;
+extern const struct inode_operations simple_symlink_inode_operations;
+
+int simple_empty(struct dentry *dentry);
+int simple_unlink(struct inode *dir, struct dentry *dentry);
+int simple_rmdir(struct inode *dir, struct dentry *dentry);
+struct dentry *simple_lookup(struct inode *, struct dentry *, unsigned int flags);
+int dcache_readdir(struct file *, struct dir_context *);
+const char *simple_get_link(struct dentry *dentry, struct inode *inode);
+
 #endif /* _LINUX_FS_H */
diff --git a/include/linux/mount.h b/include/linux/mount.h
index 57d5ba9523..9557365fb5 100644
--- a/include/linux/mount.h
+++ b/include/linux/mount.h
@@ -14,8 +14,11 @@
 
 struct vfsmount {
 	struct dentry *mnt_root;	/* root of the mounted tree */
+	struct dentry *mountpoint;	/* where it's mounted (barebox specific, no support */
+	struct vfsmount *parent;	/* for bind mounts and the like) */
 	struct super_block *mnt_sb;	/* pointer to superblock */
 	int mnt_flags;
+	int ref;
 };
 
 #endif /* _LINUX_MOUNT_H */
diff --git a/include/linux/namei.h b/include/linux/namei.h
new file mode 100644
index 0000000000..8ed7f8a1cd
--- /dev/null
+++ b/include/linux/namei.h
@@ -0,0 +1,52 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_NAMEI_H
+#define _LINUX_NAMEI_H
+
+#include <linux/kernel.h>
+#include <linux/path.h>
+
+enum { MAX_NESTED_LINKS = 8 };
+
+#define MAXSYMLINKS 40
+
+/*
+ * Type of the last component on LOOKUP_PARENT
+ */
+enum {LAST_NORM, LAST_ROOT, LAST_DOT, LAST_DOTDOT, LAST_BIND};
+
+/*
+ * The bitmask for a lookup event:
+ *  - follow links at the end
+ *  - require a directory
+ *  - ending slashes ok even for nonexistent files
+ *  - internal "there are more path components" flag
+ *  - dentry cache is untrusted; force a real lookup
+ *  - suppress terminal automount
+ */
+#define LOOKUP_FOLLOW		0x0001
+#define LOOKUP_DIRECTORY	0x0002
+#define LOOKUP_AUTOMOUNT	0x0004
+
+#define LOOKUP_PARENT		0x0010
+#define LOOKUP_REVAL		0x0020
+#define LOOKUP_RCU		0x0040
+#define LOOKUP_NO_REVAL		0x0080
+
+/*
+ * Intent data
+ */
+#define LOOKUP_OPEN		0x0100
+#define LOOKUP_CREATE		0x0200
+#define LOOKUP_EXCL		0x0400
+#define LOOKUP_RENAME_TARGET	0x0800
+
+#define LOOKUP_JUMPED		0x1000
+#define LOOKUP_ROOT		0x2000
+#define LOOKUP_EMPTY		0x4000
+#define LOOKUP_DOWN		0x8000
+
+#define AT_FDCWD                -100    /* Special value used to indicate
+                                           openat should use the current
+                                           working directory. */
+
+#endif /* _LINUX_NAMEI_H */
diff --git a/include/linux/stat.h b/include/linux/stat.h
index af022c5c79..87fe068396 100644
--- a/include/linux/stat.h
+++ b/include/linux/stat.h
@@ -42,6 +42,8 @@ extern "C" {
 #define S_IWOTH 00002		/* read permission for other */
 #define S_IXOTH 00001		/* execute/search permission for other */
 
+#define S_IRWXUGO	(S_IRWXU|S_IRWXG|S_IRWXO)
+
 struct stat {
 	unsigned short st_dev;
 	unsigned short __pad1;