path: root/fs/ubifs/lprops.c

/*
 * This file is part of UBIFS.
 *
 * Copyright (C) 2006-2008 Nokia Corporation.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 as published by
 * the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc., 51
 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 *
 * Authors: Adrian Hunter
 *          Artem Bityutskiy (Битюцкий Артём)
 */

/*
 * This file implements the functions that access LEB properties and their
 * categories. LEBs are categorized based on the needs of UBIFS, and the
 * categories are stored as either heaps or lists to provide a fast way of
 * finding a LEB in a particular category. For example, UBIFS may need to find
 * an empty LEB for the journal, or a very dirty LEB for garbage collection.
 */

#include "ubifs.h"

/**
 * get_heap_comp_val - get the LEB properties value for heap comparisons.
 * @lprops: LEB properties
 * @cat: LEB category
 */
static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)
{
	switch (cat) {
	case LPROPS_FREE:
		return lprops->free;
	case LPROPS_DIRTY_IDX:
		return lprops->free + lprops->dirty;
	default:
		return lprops->dirty;
	}
}

/**
 * move_up_lpt_heap - move a new heap entry up as far as possible.
 * @c: UBIFS file-system description object
 * @heap: LEB category heap
 * @lprops: LEB properties to move
 * @cat: LEB category
 *
 * New entries to a heap are added at the bottom and then moved up until the
 * parent's value is greater.  In the case of LPT's category heaps, the value
 * is either the amount of free space or the amount of dirty space, depending
 * on the category.
 */
static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
			     struct ubifs_lprops *lprops, int cat)
{
	int val1, val2, hpos;

	hpos = lprops->hpos;
	if (!hpos)
		return; /* Already top of the heap */
	val1 = get_heap_comp_val(lprops, cat);
	/* Compare to parent and, if greater, move up the heap */
	do {
		int ppos = (hpos - 1) / 2;

		val2 = get_heap_comp_val(heap->arr[ppos], cat);
		if (val2 >= val1)
			return;
		/* Greater than parent so move up */
		heap->arr[ppos]->hpos = hpos;
		heap->arr[hpos] = heap->arr[ppos];
		heap->arr[ppos] = lprops;
		lprops->hpos = ppos;
		hpos = ppos;
	} while (hpos);
}

/**
 * adjust_lpt_heap - move a changed heap entry up or down the heap.
 * @c: UBIFS file-system description object
 * @heap: LEB category heap
 * @lprops: LEB properties to move
 * @hpos: heap position of @lprops
 * @cat: LEB category
 *
 * Changed entries in a heap are moved up or down until the parent's value is
 * greater.  In the case of LPT's category heaps, the value is either the amount
 * of free space or the amount of dirty space, depending on the category.
 */
static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
			    struct