path: root/fs/overlayfs/readdir.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *
 * Copyright (C) 2011 Novell Inc.
 */

#include <linux/fs.h>
#include <linux/slab.h>
#include <linux/namei.h>
#include <linux/file.h>
#include <linux/xattr.h>
#include <linux/rbtree.h>
#include <linux/security.h>
#include <linux/cred.h>
#include <linux/ratelimit.h>
#include "overlayfs.h"

struct ovl_cache_entry {
	unsigned int len;
	unsigned int type;
	u64 real_ino;
	u64 ino;
	struct list_head l_node;
	struct rb_node node;
	struct ovl_cache_entry *next_maybe_whiteout;
	bool is_upper;
	bool is_whiteout;
	char name[];
};

struct ovl_dir_cache {
	long refcount;
	u64 version;
	struct list_head entries;
	struct rb_root root;
};

struct ovl_readdir_data {
	struct dir_context ctx;
	struct dentry *dentry;
	bool is_lowest;
	struct rb_root *root;
	struct list_head *list;
	struct list_head middle;
	struct ovl_cache_entry *first_maybe_whiteout;
	int count;
	int err;
	bool is_upper;
	bool d_type_supported;
};

struct ovl_dir_file {
	bool is_real;
	bool is_upper;
	struct ovl_dir_cache *cache;
	struct list_head *cursor;
	struct file *realfile;
	struct file *upperfile;
};

static struct ovl_cache_entry *ovl_cache_entry_from_node(struct rb_node *n)
{
	return rb_entry(n, struct ovl_cache_entry, node);
}

static bool ovl_cache_entry_find_link(const char *name, int len,
				      struct rb_node ***link,
				      struct rb_node **parent)
{
	bool found = false;
	struct rb_node **newp = *link;

	while (!found && *newp) {
		int cmp;
		struct ovl_cache_entry *tmp;

		*parent = *newp;
		tmp = ovl_cache_entry_from_node(*newp);
		cmp = strncmp(name, tmp->name, len);
		if (cmp > 0)
			newp = &tmp->node.rb_right;
		else if (cmp < 0 || len < tmp->len)
			newp = &tmp->node.rb_left;
		else
			found = true;
	}
	*link = newp;

	return found;
}

static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
						    const char *name, int len)
{
	struct rb_node *node = root->rb_node;
	int cmp;

	while (node) {
		struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);

		cmp = strncmp(name, p->name, len);
		if (cmp > 0)
			node = p->node.rb_right;
		else if (cmp < 0 || len < p->len)
			node = p->node.rb_left;
		else
			return p;
	}

	return NULL;
}

static bool ovl_calc_d_ino(struct ovl_readdir_data *rdd,
			   struct ovl_cache_entry *p)
{
	/* Don't care if not doing ovl_iter() */
	if (!rdd->dentry)
		return false;

	/* Always recalc d_ino when remapping lower inode numbers */
	if (ovl_xino_bits(rdd->dentry->d_sb))
		return true;

	/* Always recalc d_ino for parent */
	if (strcmp(p->name, "..") == 0)
		return true;

	/* If this is lower, then native d_ino will do */
	if (