linux/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 { … };

/**
 * 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)
{ … }

/**
 * 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)
{ … }

/**
 * 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)
{ … }

/**
 * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector.
 * @c: the UBIFS file-system description object
 * @ret_lp: LEB properties are returned here on exit
 * @min_space: minimum amount free plus dirty space the returned LEB has to
 *             have
 * @pick_free: controls whether it is OK to pick empty or index LEBs
 *
 * This function tries to find a dirty logical eraseblock which has at least
 * @min_space free and dirty space. It prefers to take an LEB from the dirty or
 * dirty index heap, and it falls-back to LPT scanning if the heaps are empty
 * or do not have an LEB which satisfies the @min_space criteria.
 *
 * Note, LEBs which have less than dead watermark of free + dirty space are
 * never picked by this function.
 *
 * The additional @pick_free argument controls if this function has to return a
 * free or freeable LEB if one is present. For example, GC must to set it to %1,
 * when called from the journal space reservation function, because the
 * appearance of free space may coincide with the loss of enough dirty space
 * for GC to succeed anyway.
 *
 * In contrast, if the Garbage Collector is called from budgeting, it should
 * just make free space, not return LEBs which are already free or freeable.
 *
 * In addition @pick_free is set to %2 by the recovery process in order to
 * recover gc_lnum in which case an index LEB must not be returned.
 *
 * This function returns zero and the LEB properties of found dirty LEB in case
 * of success, %-ENOSPC if no dirty LEB was found and a negative error code in
 * case of other failures. The returned LEB is marked as "taken".
 */
int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp,
			 int min_space, int pick_free)
{ … }

/**
 * scan_for_free_cb - free 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_free_cb(struct ubifs_info *c,
			    const struct ubifs_lprops *lprops, int in_tree,
			    void *arg)
{ … }

/**
 * do_find_free_space - find a data LEB with free space.
 * @c: the UBIFS file-system description object
 * @min_space: minimum amount of free space required
 * @pick_free: whether it is OK to scan for empty LEBs
 * @squeeze: whether to try to find space in a non-empty LEB first
 *
 * This function returns a pointer to the LEB properties found or a negative
 * error code.
 */
static
const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c,
					      int min_space, int pick_free,
					      int squeeze)
{ … }

/**
 * ubifs_find_free_space - find a data LEB with free space.
 * @c: the UBIFS file-system description object
 * @min_space: minimum amount of required free space
 * @offs: contains offset of where free space starts on exit
 * @squeeze: whether to try to find space in a non-empty LEB first
 *
 * This function looks for an LEB with at least @min_space bytes of free space.
 * It tries to find an empty LEB if possible. If no empty LEBs are available,
 * this function searches for a non-empty data LEB. The returned LEB is marked
 * as "taken".
 *
 * This function returns found LEB number in case of success, %-ENOSPC if it
 * failed to find a LEB with @min_space bytes of free space and other a negative
 * error codes in case of failure.
 */
int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs,
			  int squeeze)
{ … }

/**
 * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
 * @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_idx_cb(struct ubifs_info *c,
			   const struct ubifs_lprops *lprops, int in_tree,
			   void *arg)
{ … }

/**
 * scan_for_leb_for_idx - scan for a free LEB for the index.
 * @c: the UBIFS file-system description object
 */
static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
{ … }

/**
 * ubifs_find_free_leb_for_idx - find a free LEB for the index.
 * @c: the UBIFS file-system description object
 *
 * This function looks for a free LEB and returns that LEB number. The returned
 * LEB is marked as "taken", "index".
 *
 * Only empty LEBs are allocated. This is for two reasons. First, the commit
 * calculates the number of LEBs to allocate based on the assumption that they
 * will be empty. Secondly, free space at the end of an index LEB is not
 * guaranteed to be empty because it may have been used by the in-the-gaps
 * method prior to an unclean unmount.
 *
 * If no LEB is found %-ENOSPC is returned. For other failures another negative
 * error code is returned.
 */
int ubifs_find_free_leb_for_idx(struct ubifs_info *c)
{ … }

static int cmp_dirty_idx(const void *a, const void *b)
{ … }

/**
 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
 * @c: the UBIFS file-system description object
 *
 * This function is called each commit to create an array of LEB numbers of
 * dirty index LEBs sorted in order of dirty and free space.  This is used by
 * the in-the-gaps method of TNC commit.
 */
int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
{ … }

/**
 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
 * @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_dirty_idx_cb(struct ubifs_info *c,
			   const struct ubifs_lprops *lprops, int in_tree,
			   void *arg)
{ … }

/**
 * find_dirty_idx_leb - find a dirty index LEB.
 * @c: the UBIFS file-system description object
 *
 * This function returns LEB number upon success and a negative error code upon
 * failure.  In particular, -ENOSPC is returned if a dirty index LEB is not
 * found.
 *
 * Note that this function scans the entire LPT but it is called very rarely.
 */
static int find_dirty_idx_leb(struct ubifs_info *c)
{ … }

/**
 * get_idx_gc_leb - try to get a LEB number from trivial GC.
 * @c: the UBIFS file-system description object
 */
static int get_idx_gc_leb(struct ubifs_info *c)
{ … }

/**
 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
 * @c: the UBIFS file-system description object
 */
static int find_dirtiest_idx_leb(struct ubifs_info *c)
{ … }

/**
 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
 * @c: the UBIFS file-system description object
 *
 * This function attempts to find an untaken index LEB with the most free and
 * dirty space that can be used without overwriting index nodes that were in the
 * last index committed.
 */
int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
{ … }