path: root/drivers/mtd/ubi/eba.c

/*
 * Copyright (c) International Business Machines Corp., 2006
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * Author: Artem Bityutskiy (Битюцкий Артём)
 */

/*
 * The UBI Eraseblock Association (EBA) sub-system.
 *
 * This sub-system is responsible for I/O to/from logical eraseblock.
 *
 * Although in this implementation the EBA table is fully kept and managed in
 * RAM, which assumes poor scalability, it might be (partially) maintained on
 * flash in future implementations.
 *
 * The EBA sub-system implements per-logical eraseblock locking. Before
 * accessing a logical eraseblock it is locked for reading or writing. The
 * per-logical eraseblock locking is implemented by means of the lock tree. The
 * lock tree is an RB-tree which refers all the currently locked logical
 * eraseblocks. The lock tree elements are &struct ubi_ltree_entry objects.
 * They are indexed by (@vol_id, @lnum) pairs.
 *
 * EBA also maintains the global sequence counter which is incremented each
 * time a logical eraseblock is mapped to a physical eraseblock and it is
 * stored in the volume identifier header. This means that each VID header has
 * a unique sequence number. The sequence number is only increased an we assume
 * 64 bits is enough to never overflow.
 */

#include <linux/slab.h>
#include <linux/crc32.h>
#include <linux/err.h>
#include "ubi.h"

/* Number of physical eraseblocks reserved for atomic LEB change operation */
#define EBA_RESERVED_PEBS 1

/**
 * struct ubi_eba_entry - structure encoding a single LEB -> PEB association
 * @pnum: the physical eraseblock number attached to the LEB
 *
 * This structure is encoding a LEB -> PEB association. Note that the LEB
 * number is not stored here, because it is the index used to access the
 * entries table.
 */
struct ubi_eba_entry {
	int pnum;
};

/**
 * struct ubi_eba_table - LEB -> PEB association information
 * @entries: the LEB to PEB mapping (one entry per LEB).
 *
 * This structure is private to the EBA logic and should be kept here.
 * It is encoding the LEB to PEB association table, and is subject to
 * changes.
 */
struct ubi_eba_table {
	struct ubi_eba_entry *entries;
};

/**
 * next_sqnum - get next sequence number.
 * @ubi: UBI device description object
 *
 * This function returns next sequence number to use, which is just the current
 * global sequence counter value. It also increases the global sequence
 * counter.
 */
unsigned long long ubi_next_sqnum(struct ubi_device *ubi)
{
	unsigned long long sqnum;

	spin_lock(&ubi->ltree_lock);
	sqnum = ubi->global_sqnum++;
	spin_unlock(&ubi->ltree_lock);

	return sqnum;
}

/**
 * ubi_get_compat - get compatibility flags of a volume.
 * @ubi: UBI device description object
 * @vol_id: volume ID
 *
 * This function returns compatibility flags for an internal volume. User
 * volumes have no compatibility flags, so %0 is returned.
 */
static int ubi_get_compat(const struct ubi_device *ubi, int vol_id)
{
	if (vol_id == UBI_LAYOUT_VOLUME_ID)
		return UBI_LAYOUT_VOLUME_COMPAT;
	return 0;
}

/**
 * ubi_eba_get_ldesc - get information about a LEB
 * @vol: volume description object
 * @lnum: logical eraseblock number
 * @ldesc: the LEB descriptor to fill
 *
 * Used to query information about a specific LEB.
 * It is currently only returning the physical position of the LEB, but will be
 * extended to provide more information.
 */
void ubi_eba_get_ldesc(struct ubi_volume *vol, int lnum,
		       struct ubi_eba_leb_desc *ldesc)
{
	ldesc->lnum = lnum;
	ldesc->pnum = vol->eba_tbl->entries[lnum].pnum;
}

/**
 * ubi_eba_create_table - allocate a new EBA table and initialize it with all
 *			  LEBs unmapped
 * @vol: volume containing the EBA table to copy
 * @nentries: number of entries in the table
 *
 * Allocate a new EBA table and initialize it with all LEBs unmapped.
 * Returns a valid pointer if it succeed, an ERR_PTR() otherwise.
 */
struct ubi_eba_table *ubi_eba_create_table(struct ubi_volume *vol,
					   int nentries)
{
	struct ubi_eba_table *tbl;
	int err = -ENOMEM;
	int i;

	tbl = kzalloc(sizeof(*tbl), GFP_KERNEL);
	if (!tbl)
		return ERR_PTR(-ENOMEM);

	tbl->entries = kmalloc_array(nentries, sizeof(*tbl->entries),