/*
* 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
/**
* 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.
*/
static unsigned long long 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;
}
/**
* ltree_lookup - look up the lock tree.
* @ubi: UBI device description object
* @vol_id: volume ID
* @lnum: logical eraseblock number
*
* This function returns a pointer to the corresponding &struct ubi_ltree_entry
* object if the logical eraseblock is locked and %NULL if it is not.
* @ubi->ltree_lock has to be locked.
*/
static struct ubi_ltree_entry *ltree_lookup(struct ubi_device *ubi, int vol_id,
int lnum)
{
struct rb_node *p;
p = ubi->ltree.rb_node;
while (p) {
struct ubi_ltree_entry *le;
le = rb_entry(p, struct ubi_ltree_entry, rb);
if (vol_id < le->vol_id)
p = p->rb_left;
else if (vol_id > le->vol_id)
p = p->rb_right;
else {
if (lnum < le->lnum)
p = p->rb_left;
else if (lnum > le->lnum)
p = p->rb_right;
else
return le;
}
}
return NULL;
}
/**
* ltree_add_entry - add new entry to the lock tree.
* @ubi: UBI device description object
* @vol_id: volume ID
* @lnum: logical eraseblock number
*
* This function adds new entry for logical eraseblock (@vol_id, @lnum) to the
* lock tree. If such entry is already there, its usage counter is increased.
* Returns pointer to the lock tree entry or %-ENOMEM if memory allocation
* failed.
*/
static struct ubi_ltree_entry *ltree_add_entry(struct ubi_device *ubi,
int vol_id, int lnum)
{
struct ubi_ltree_entry *le, *le1, *le_free;
le =