path: root/fs/ubifs/orphan.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * This file is part of UBIFS.
 *
 * Copyright (C) 2006-2008 Nokia Corporation.
 *
 * Author: Adrian Hunter
 */

#include "ubifs.h"

/*
 * An orphan is an inode number whose inode node has been committed to the index
 * with a link count of zero. That happens when an open file is deleted
 * (unlinked) and then a commit is run. In the normal course of events the inode
 * would be deleted when the file is closed. However in the case of an unclean
 * unmount, orphans need to be accounted for. After an unclean unmount, the
 * orphans' inodes must be deleted which means either scanning the entire index
 * looking for them, or keeping a list on flash somewhere. This unit implements
 * the latter approach.
 *
 * The orphan area is a fixed number of LEBs situated between the LPT area and
 * the main area. The number of orphan area LEBs is specified when the file
 * system is created. The minimum number is 1. The size of the orphan area
 * should be so that it can hold the maximum number of orphans that are expected
 * to ever exist at one time.
 *
 * The number of orphans that can fit in a LEB is:
 *
 *         (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)
 *
 * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough.
 *
 * Orphans are accumulated in a rb-tree. When an inode's link count drops to
 * zero, the inode number is added to the rb-tree. It is removed from the tree
 * when the inode is deleted.  Any new orphans that are in the orphan tree when
 * the commit is run, are written to the orphan area in 1 or more orphan nodes.
 * If the orphan area is full, it is consolidated to make space.  There is
 * always enough space because validation prevents the user from creating more
 * than the maximum number of orphans allowed.
 */

static int dbg_check_orphans(struct ubifs_info *c);

static struct ubifs_orphan *orphan_add(struct ubifs_info *c, ino_t inum,
				       struct ubifs_orphan *parent_orphan)
{
	struct ubifs_orphan *orphan, *o;
	struct rb_node **p, *parent = NULL;

	orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_NOFS);
	if (!orphan)
		return ERR_PTR(-ENOMEM);
	orphan->inum = inum;
	orphan->new = 1;
	INIT_LIST_HEAD(&orphan->child_list);

	spin_lock(&c->orphan_lock);
	if (c->tot_orphans >= c->max_orphans) {
		spin_unlock(&c->orphan_lock);
		kfree(orphan);
		return ERR_PTR(-ENFILE);
	}
	p = &c->orph_tree.rb_node;
	while (*p) {
		parent = *p;
		o = rb_entry(parent, struct ubifs_orphan, rb);
		if (inum < o->inum)
			p = &(*p)->rb_left;
		else if (inum > o->inum)
			p = &(*p)->rb_right;
		else {
			ubifs_err(c, "orphaned twice");
			spin_unlock(&c->orphan_lock);
			kfree(orphan);
			return ERR_PTR(-EINVAL);
		}
	}
	c->tot_orphans += 1;
	c->new_orphans += 1;
	rb_link_node(&orphan->rb, parent, p);
	rb_insert_color(&orphan->rb, &c->orph_tree);
	list_add_tail(&orphan->list, &c->orph_list);
	list_add_tail(&orphan->new_list, &c->orph_new);

	if (parent_orphan) {
		list_add_tail(&orphan->child_list,
			      &parent_orphan->child_list);
	}

	spin_unlock(&c->orphan_lock);
	dbg_gen("ino %lu", (unsigned long)inum);
	return orphan;
}

static struct ubifs_orphan *lookup_orphan(struct ubifs_info *c, ino_t inum)
{
	struct ubifs_orphan *o;
	struct rb_node *p;

	p = c->orph_tree.rb_node;
	while (p) {
		o = rb_entry(p, struct ubifs_orphan, rb);
		if (inum < o->inum)
			p = p->rb_left;
		else if (inum > o->inum)
			p = p->rb_right;
		else {
			return o;
		}
	}
	return NULL;
}

static void __orphan_drop(struct ubifs_info *c, struct ubifs_orphan *o)
{
	rb_erase(&o->rb, &c->orph_tree);
	list_del(&o->list);
	c->tot_orphans -= 1;

	if (o->new) {
		list_del(&o->new_list);
		c->new_orphans -= 1;
	}

	kfree(o);
}

static void orphan_delete(struct ubifs_info *c, struct ubifs_orphan *orph)
{
	if (orph->del) {
		dbg_gen("deleted twice ino %lu", (unsigned long)orph->inum);
		return;
	}

	if (orph->cmt) {
		orph->del = 1;
		orph->dnext = c->orph_dnext;
		c->orph_dnext = orph;
		dbg_gen("delete later ino %lu", (unsigned long)orph->inum);
		return;
	}

	__orphan_drop(c, orph);
}

/**
 * ubifs_add_orphan - add an orphan.
 * @c: UBIFS file-system description object
 * @inum: orphan inode number
 *
 * Add an orphan. This function is called when an inodes link count drops to
 * zero.
 */
int ubifs_add_orphan(struct ubifs_info *c, ino_t inum)
{
	int err = 0;
	ino_t xattr_inum;
	union ubifs_key key;
	struct ubifs_dent_node *xent, *pxent = NULL;
	struct fscrypt_name nm = {0};
	struct ubifs_orphan *xattr_orphan;
	struct ubifs_orphan *orphan;

	orphan = orphan_add(c, inum, NULL);
	if (IS_ERR(orphan))
		return PTR_ERR(orphan);

	lowest_xent_key(c, &key, inum);
	while