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

/*
 * Copyright (c) 2012 Linutronix GmbH
 * Author: Richard Weinberger <richard@nod.at>
 *
 * 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; version 2.
 *
 * 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.
 *
 */

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

/**
 * ubi_calc_fm_size - calculates the fastmap size in bytes for an UBI device.
 * @ubi: UBI device description object
 */
size_t ubi_calc_fm_size(struct ubi_device *ubi)
{
	size_t size;

	size = sizeof(struct ubi_fm_hdr) + \
		sizeof(struct ubi_fm_scan_pool) + \
		sizeof(struct ubi_fm_scan_pool) + \
		(ubi->peb_count * sizeof(struct ubi_fm_ec)) + \
		(sizeof(struct ubi_fm_eba) + \
		(ubi->peb_count * sizeof(__be32))) + \
		sizeof(struct ubi_fm_volhdr) * UBI_MAX_VOLUMES;
	return roundup(size, ubi->leb_size);
}


/**
 * new_fm_vhdr - allocate a new volume header for fastmap usage.
 * @ubi: UBI device description object
 * @vol_id: the VID of the new header
 *
 * Returns a new struct ubi_vid_hdr on success.
 * NULL indicates out of memory.
 */
static struct ubi_vid_hdr *new_fm_vhdr(struct ubi_device *ubi, int vol_id)
{
	struct ubi_vid_hdr *new;

	new = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
	if (!new)
		goto out;

	new->vol_type = UBI_VID_DYNAMIC;
	new->vol_id = cpu_to_be32(vol_id);

	/* UBI implementations without fastmap support have to delete the
	 * fastmap.
	 */
	new->compat = UBI_COMPAT_DELETE;

out:
	return new;
}

/**
 * add_aeb - create and add a attach erase block to a given list.
 * @ai: UBI attach info object
 * @list: the target list
 * @pnum: PEB number of the new attach erase block
 * @ec: erease counter of the new LEB
 * @scrub: scrub this PEB after attaching
 *
 * Returns 0 on success, < 0 indicates an internal error.
 */
static int add_aeb(struct ubi_attach_info *ai, struct list_head *list,
		   int pnum, int ec, int scrub)
{
	struct ubi_ainf_peb *aeb;

	aeb = kmem_cache_alloc(ai->aeb_slab_cache, GFP_KERNEL);
	if (!aeb)
		return -ENOMEM;

	aeb->pnum = pnum;
	aeb->ec = ec;
	aeb->lnum = -1;
	aeb->scrub = scrub;
	aeb->copy_flag = aeb->sqnum = 0;

	ai->ec_sum += aeb->ec;
	ai->ec_count++;

	if (ai->max_ec < aeb->ec)
		ai->max_ec = aeb->ec;

	if (ai->min_ec > aeb->ec)
		ai->min_ec = aeb->ec;

	list_add_tail(&aeb->u.list, list);

	return 0;
}

/**
 * add_vol - create and add a new volume to ubi_attach_info.
 * @ai: ubi_attach_info object
 * @vol_id: VID of the new volume
 * @used_ebs: number of used EBS
 * @data_pad: data padding value of the new volume
 * @vol_type: volume type
 * @last_eb_bytes: number of bytes in the last LEB
 *
 * Returns the new struct ubi_ainf_volume on success.
 * NULL indicates an error.
 */
static struct ubi_ainf_volume *add_vol(struct ubi_attach_info *ai, int vol_id,
				       int used_ebs, int data_pad, u8 vol_type,
				       int last_eb_bytes)
{
	struct ubi_ainf_volume *av;
	struct rb_node **p = &ai->volumes.rb_node, *parent = NULL;

	while (*p) {
		parent = *p;
		av = rb_entry(parent, struct ubi_ainf_volume, rb);

		if (vol_id < av->vol_id)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

	av = kmalloc(sizeof(struct ubi_ainf_volume), GFP_KERNEL);
	if (!av)
		goto out;

	av->highest_lnum = av->leb_count = 0;
	av->vol_id = vol_id;
	av->used_ebs = used_ebs;
	av->data_pad = data_pad;
	av->last_data_size = last_eb_bytes;
	av->compat = 0;
	av->vol_type = vol_type;
	av->root = RB_ROOT;

	dbg_bld("found volume (ID %i)", vol_id);

	rb_link_node(&av->rb, parent, p);
	rb_insert_color(&av->rb, &ai->volumes);

out:
	return av;
}

/**
 * assign_aeb_to_av - assigns a SEB to a given ainf_volume and removes it
 * from it's original list.
 * @ai: ubi_attach_info object
 * @aeb: the to be assigned SEB
 * @av: target scan volume
 */
static void assign_aeb_to_av(struct ubi_attach_info *ai,
			     struct ubi_ainf_peb *aeb,
			     struct ubi_ainf_volume *av)
{
	struct ubi_ainf_peb *tmp_aeb;
	struct rb_node **p = &ai->volumes.rb_node, *parent = NULL;

	p = &av->root.rb_node;
	while (*p) {
		parent = *p;

		tmp_aeb = rb_entry(parent, struct ubi_ainf_peb, u.rb);
		if (aeb->lnum != tmp_aeb->lnum) {
			if (aeb->lnum < tmp_aeb->lnum)
				p = &(*p)->rb_left;
			else
				p = &(*p)->rb_right;

			continue;
		} else
			break;
	}

	list_del(&aeb->u.list);
	av->leb_count++;

	rb_link_node(&aeb->u.rb, parent, p);
	rb_insert_color(&aeb->u.rb, &av->root);
}

/**
 * update_vol - inserts or updates a LEB which was found a pool.
 * @ubi: the UBI device object
 * @ai: attach info object
 * @av: the volume this LEB belongs to
 * @new_vh: the volume header derived from new_aeb
 * @new_aeb: the AEB to be examined
 *
 * Returns 0 on success, < 0 indicates an internal error.
 */
static int update_vol(struct ubi_device *ubi, struct ubi_attach_info *ai,
		      struct ubi_ainf_volume *av, struct ubi_vid_hdr *new_vh,
		      struct ubi_ainf_peb *new_aeb)
{
	struct rb_node **p = &av->root.rb_node, *parent = NULL;
	struct ubi_ainf_peb *aeb, *victim;
	int cmp_res;

	while (*p) {
		parent = *p;
		aeb = rb_entry(parent, struct ubi_ainf_peb, u.rb);

		if (be32_to_cpu(new_vh->lnum) != aeb->lnum) {
			if (be32_to_cpu(new_vh->lnum) < aeb->lnum)
				p = &(*p)->rb_left;
			else
				p = &(*p)->rb_right;

			continue;
		}

		/* This case can happen if the fastmap gets written
		 * because of a volume change (creation, deletion, ..).
		 * Then a PEB can be within the persistent EBA and the pool.
		 */
		if (aeb->pnum == new_aeb->pnum) {
			ubi_assert(aeb->