path: root/fs/ubifs/find.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * This file is part of UBIFS.
 *
 * Copyright (C) 2006-2008 Nokia Corporation.
 *
 * Authors: Artem Bityutskiy (Битюцкий Артём)
 *          Adrian Hunter
 */

/*
 * This file contains functions for finding LEBs for various purposes e.g.
 * garbage collection. In general, lprops category heaps and lists are used
 * for fast access, falling back on scanning the LPT as a last resort.
 */

#include <linux/sort.h>
#include "ubifs.h"

/**
 * struct scan_data - data provided to scan callback functions
 * @min_space: minimum number of bytes for which to scan
 * @pick_free: whether it is OK to scan for empty LEBs
 * @lnum: LEB number found is returned here
 * @exclude_index: whether to exclude index LEBs
 */
struct scan_data {
	int min_space;
	int pick_free;
	int lnum;
	int exclude_index;
};

/**
 * valuable - determine whether LEB properties are valuable.
 * @c: the UBIFS file-system description object
 * @lprops: LEB properties
 *
 * This function return %1 if the LEB properties should be added to the LEB
 * properties tree in memory. Otherwise %0 is returned.
 */
static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops)
{
	int n, cat = lprops->flags & LPROPS_CAT_MASK;
	struct ubifs_lpt_heap *heap;

	switch (cat) {
	case LPROPS_DIRTY:
	case LPROPS_DIRTY_IDX:
	case LPROPS_FREE:
		heap = &c->lpt_heap[cat - 1];
		if (heap->cnt < heap->max_cnt)
			return 1;
		if (lprops->free + lprops->dirty >= c->dark_wm)
			return 1;
		return 0;
	case LPROPS_EMPTY:
		n = c->lst.empty_lebs + c->freeable_cnt -
		    c->lst.taken_empty_lebs;
		if (n < c->lsave_cnt)
			return 1;
		return 0;
	case LPROPS_FREEABLE:
		return 1;
	case LPROPS_FRDI_IDX:
		return 1;
	}
	return 0;
}

/**
 * scan_for_dirty_cb - dirty space scan callback.
 * @c: the UBIFS file-system description object
 * @lprops: LEB properties to scan
 * @in_tree: whether the LEB properties are in main memory
 * @arg: information passed to and from the caller of the scan
 *
 * This function returns a code that indicates whether the scan should continue
 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
 * (%LPT_SCAN_STOP).
 */
static int scan_for_dirty_cb(struct ubifs_info *c,
			     const struct ubifs_lprops *lprops, int in_tree,
			     void *arg)
{
	struct scan_data *data = arg;
	int ret = LPT_SCAN_CONTINUE;

	/* Exclude LEBs that are currently in use */
	if (lprops->flags & LPROPS_TAKEN)
		return LPT_SCAN_CONTINUE;
	/* Determine whether to add these LEB properties to the tree */
	if (!in_tree && valuable(c, lprops))
		ret |= LPT_SCAN_ADD;
	/* Exclude LEBs with too little space */
	if (lprops->free + lprops->dirty < data->min_space)
		return ret;
	/* If specified, exclude index LEBs */
	if (data->exclude_index && lprops->flags & LPROPS_INDEX)
		return ret;
	/* If specified, exclude empty or freeable LEBs */
	if (lprops->free + lprops->dirty == c->leb_size) {
		if (!data->pick_free)
			return ret;
	/* Exclude LEBs with too little dirty space (unless it is empty) */
	} else if (lprops->dirty < c->dead_wm)
		return ret;
	/* Finally we found space */
	data->lnum = lprops->lnum;
	return LPT_SCAN_ADD | LPT_SCAN_STOP;
}

/**
 * scan_for_dirty - find a data LEB with free space.
 * @c: the UBIFS file-system description object
 * @min_space: minimum amount free plus dirty space the returned LEB has to
 *             have
 * @pick_free: if it is OK to return a free or freeable LEB
 * @exclude_index: whether to exclude index LEBs
 *
 * This function returns a pointer to the LEB properties found or a negative
 * error code.
 */
static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c,
						 int min_space, int pick_free,
						 int exclude_index)
{
	const struct ubifs_lprops *lprops;
	struct ubifs_lpt_heap *heap;
	struct scan_data data;
	int err, i;

	/* There may be an LEB with enough dirty space on the free heap */
	heap = &c->lpt_heap[LPROPS_FREE - 1];
	for (i = 0; i < heap->cnt; i++) {
		lprops = heap->arr[i];
		if (lprops->free + lprops->dirty < min_space)
			continue;
		if (lprops->dirty < c->dead_wm)
			continue;
		return lprops;
	}
	/*
	 * A LEB may have fallen off of the bottom of the dirty heap, and ended
	 * up as uncategorized even though it has enough dirty space for us now,
	 * so check the uncategorized list. N.B. neither empty nor freeable LEBs
	 * can end up as uncategorized because they are kept on lists not
	 * finite-sized heaps.
	 */
	list_for_each_entry(lprops, &c->uncat_list, list) {
		if (lprops->flags & LPROPS_TAKEN)
			continue;
		if (lprops->free + lprops->dirty < min_space)
			continue;
		if (exclude_index && (lprops->flags & LPROPS_INDEX))
			continue;
		if (lprops->dirty < c->dead_wm)
			continue;
		return lprops;
	}
<