ftl.c 30.6 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
/* This version ported to the Linux-MTD system by dwmw2@infradead.org
 *
 * Fixes: Arnaldo Carvalho de Melo <acme@conectiva.com.br>
 * - fixes some leaks on failure in build_maps and ftl_notify_add, cleanups
 *
 * Based on:
 */
/*======================================================================

    A Flash Translation Layer memory card driver

    This driver implements a disk-like block device driver with an
    apparent block size of 512 bytes for flash memory cards.

    ftl_cs.c 1.62 2000/02/01 00:59:04

    The contents of this file are subject to the Mozilla Public
    License Version 1.1 (the "License"); you may not use this file
    except in compliance with the License. You may obtain a copy of
    the License at http://www.mozilla.org/MPL/

    Software distributed under the License is distributed on an "AS
    IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
    implied. See the License for the specific language governing
    rights and limitations under the License.

    The initial developer of the original code is David A. Hinds
    <dahinds@users.sourceforge.net>.  Portions created by David A. Hinds
29
    are Copyright © 1999 David A. Hinds.  All Rights Reserved.
Linus Torvalds's avatar
Linus Torvalds committed
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

    Alternatively, the contents of this file may be used under the
    terms of the GNU General Public License version 2 (the "GPL"), in
    which case the provisions of the GPL are applicable instead of the
    above.  If you wish to allow the use of your version of this file
    only under the terms of the GPL and not to allow others to use
    your version of this file under the MPL, indicate your decision
    by deleting the provisions above and replace them with the notice
    and other provisions required by the GPL.  If you do not delete
    the provisions above, a recipient may use your version of this
    file under either the MPL or the GPL.

    LEGAL NOTE: The FTL format is patented by M-Systems.  They have
    granted a license for its use with PCMCIA devices:

     "M-Systems grants a royalty-free, non-exclusive license under
      any presently existing M-Systems intellectual property rights
      necessary for the design and development of FTL-compatible
      drivers, file systems and utilities using the data formats with
      PCMCIA PC Cards as described in the PCMCIA Flash Translation
      Layer (FTL) Specification."

    Use of the FTL format for non-PCMCIA applications may be an
    infringement of these patents.  For additional information,
54
    contact M-Systems directly. M-Systems since acquired by Sandisk. 
55

Linus Torvalds's avatar
Linus Torvalds committed
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
======================================================================*/
#include <linux/mtd/blktrans.h>
#include <linux/module.h>
#include <linux/mtd/mtd.h>
/*#define PSYCHO_DEBUG */

#include <linux/kernel.h>
#include <linux/ptrace.h>
#include <linux/slab.h>
#include <linux/string.h>
#include <linux/timer.h>
#include <linux/major.h>
#include <linux/fs.h>
#include <linux/init.h>
#include <linux/hdreg.h>
#include <linux/vmalloc.h>
#include <linux/blkpg.h>
73
#include <linux/uaccess.h>
Linus Torvalds's avatar
Linus Torvalds committed
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

#include <linux/mtd/ftl.h>

/*====================================================================*/

/* Parameters that can be set with 'insmod' */
static int shuffle_freq = 50;
module_param(shuffle_freq, int, 0);

/*====================================================================*/

/* Major device # for FTL device */
#ifndef FTL_MAJOR
#define FTL_MAJOR	44
#endif


/*====================================================================*/

/* Maximum number of separate memory devices we'll allow */
#define MAX_DEV		4

/* Maximum number of regions per device */
#define MAX_REGION	4

/* Maximum number of partitions in an FTL region */
#define PART_BITS	4

/* Maximum number of outstanding erase requests per socket */
#define MAX_ERASE	8

/* Sector size -- shouldn't need to change */
#define SECTOR_SIZE	512


/* Each memory region corresponds to a minor device */
typedef struct partition_t {
    struct mtd_blktrans_dev mbd;
112 113 114
    uint32_t		state;
    uint32_t		*VirtualBlockMap;
    uint32_t		FreeTotal;
Linus Torvalds's avatar
Linus Torvalds committed
115
    struct eun_info_t {
116 117 118 119
	uint32_t		Offset;
	uint32_t		EraseCount;
	uint32_t		Free;
	uint32_t		Deleted;
Linus Torvalds's avatar
Linus Torvalds committed
120 121
    } *EUNInfo;
    struct xfer_info_t {
122 123 124
	uint32_t		Offset;
	uint32_t		EraseCount;
	uint16_t		state;
Linus Torvalds's avatar
Linus Torvalds committed
125
    } *XferInfo;
126 127 128 129
    uint16_t		bam_index;
    uint32_t		*bam_cache;
    uint16_t		DataUnits;
    uint32_t		BlocksPerUnit;
Linus Torvalds's avatar
Linus Torvalds committed
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
    erase_unit_header_t	header;
} partition_t;

/* Partition state flags */
#define FTL_FORMATTED	0x01

/* Transfer unit states */
#define XFER_UNKNOWN	0x00
#define XFER_ERASING	0x01
#define XFER_ERASED	0x02
#define XFER_PREPARED	0x03
#define XFER_FAILED	0x04

/*======================================================================

    Scan_header() checks to see if a memory region contains an FTL
    partition.  build_maps() reads all the erase unit headers, builds
    the erase unit map, and then builds the virtual page map.
148

Linus Torvalds's avatar
Linus Torvalds committed
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
======================================================================*/

static int scan_header(partition_t *part)
{
    erase_unit_header_t header;
    loff_t offset, max_offset;
    size_t ret;
    int err;
    part->header.FormattedSize = 0;
    max_offset = (0x100000<part->mbd.mtd->size)?0x100000:part->mbd.mtd->size;
    /* Search first megabyte for a valid FTL header */
    for (offset = 0;
	 (offset + sizeof(header)) < max_offset;
	 offset += part->mbd.mtd->erasesize ? : 0x2000) {

164 165
	err = mtd_read(part->mbd.mtd, offset, sizeof(header), &ret,
                       (unsigned char *)&header);
166 167

	if (err)
Linus Torvalds's avatar
Linus Torvalds committed
168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
	    return err;

	if (strcmp(header.DataOrgTuple+3, "FTL100") == 0) break;
    }

    if (offset == max_offset) {
	printk(KERN_NOTICE "ftl_cs: FTL header not found.\n");
	return -ENOENT;
    }
    if (header.BlockSize != 9 ||
	(header.EraseUnitSize < 10) || (header.EraseUnitSize > 31) ||
	(header.NumTransferUnits >= le16_to_cpu(header.NumEraseUnits))) {
	printk(KERN_NOTICE "ftl_cs: FTL header corrupt!\n");
	return -1;
    }
    if ((1 << header.EraseUnitSize) != part->mbd.mtd->erasesize) {
	printk(KERN_NOTICE "ftl: FTL EraseUnitSize %x != MTD erasesize %x\n",
	       1 << header.EraseUnitSize,part->mbd.mtd->erasesize);
	return -1;
    }
    part->header = header;
    return 0;
}

static int build_maps(partition_t *part)
{
    erase_unit_header_t header;
195 196
    uint16_t xvalid, xtrans, i;
    unsigned blocks, j;
Linus Torvalds's avatar
Linus Torvalds committed
197 198 199 200 201 202 203
    int hdr_ok, ret = -1;
    ssize_t retval;
    loff_t offset;

    /* Set up erase unit maps */
    part->DataUnits = le16_to_cpu(part->header.NumEraseUnits) -
	part->header.NumTransferUnits;
204 205
    part->EUNInfo = kmalloc_array(part->DataUnits, sizeof(struct eun_info_t),
                                  GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
206 207 208 209 210
    if (!part->EUNInfo)
	    goto out;
    for (i = 0; i < part->DataUnits; i++)
	part->EUNInfo[i].Offset = 0xffffffff;
    part->XferInfo =
211 212 213
	kmalloc_array(part->header.NumTransferUnits,
                      sizeof(struct xfer_info_t),
                      GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
214 215 216 217 218 219 220
    if (!part->XferInfo)
	    goto out_EUNInfo;

    xvalid = xtrans = 0;
    for (i = 0; i < le16_to_cpu(part->header.NumEraseUnits); i++) {
	offset = ((i + le16_to_cpu(part->header.FirstPhysicalEUN))
		      << part->header.EraseUnitSize);
221 222
	ret = mtd_read(part->mbd.mtd, offset, sizeof(header), &retval,
                       (unsigned char *)&header);
223 224

	if (ret)
Linus Torvalds's avatar
Linus Torvalds committed
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262
	    goto out_XferInfo;

	ret = -1;
	/* Is this a transfer partition? */
	hdr_ok = (strcmp(header.DataOrgTuple+3, "FTL100") == 0);
	if (hdr_ok && (le16_to_cpu(header.LogicalEUN) < part->DataUnits) &&
	    (part->EUNInfo[le16_to_cpu(header.LogicalEUN)].Offset == 0xffffffff)) {
	    part->EUNInfo[le16_to_cpu(header.LogicalEUN)].Offset = offset;
	    part->EUNInfo[le16_to_cpu(header.LogicalEUN)].EraseCount =
		le32_to_cpu(header.EraseCount);
	    xvalid++;
	} else {
	    if (xtrans == part->header.NumTransferUnits) {
		printk(KERN_NOTICE "ftl_cs: format error: too many "
		       "transfer units!\n");
		goto out_XferInfo;
	    }
	    if (hdr_ok && (le16_to_cpu(header.LogicalEUN) == 0xffff)) {
		part->XferInfo[xtrans].state = XFER_PREPARED;
		part->XferInfo[xtrans].EraseCount = le32_to_cpu(header.EraseCount);
	    } else {
		part->XferInfo[xtrans].state = XFER_UNKNOWN;
		/* Pick anything reasonable for the erase count */
		part->XferInfo[xtrans].EraseCount =
		    le32_to_cpu(part->header.EraseCount);
	    }
	    part->XferInfo[xtrans].Offset = offset;
	    xtrans++;
	}
    }
    /* Check for format trouble */
    header = part->header;
    if ((xtrans != header.NumTransferUnits) ||
	(xvalid+xtrans != le16_to_cpu(header.NumEraseUnits))) {
	printk(KERN_NOTICE "ftl_cs: format error: erase units "
	       "don't add up!\n");
	goto out_XferInfo;
    }
263

Linus Torvalds's avatar
Linus Torvalds committed
264 265
    /* Set up virtual page map */
    blocks = le32_to_cpu(header.FormattedSize) >> header.BlockSize;
266
    part->VirtualBlockMap = vmalloc(array_size(blocks, sizeof(uint32_t)));
Linus Torvalds's avatar
Linus Torvalds committed
267 268 269
    if (!part->VirtualBlockMap)
	    goto out_XferInfo;

270
    memset(part->VirtualBlockMap, 0xff, blocks * sizeof(uint32_t));
Linus Torvalds's avatar
Linus Torvalds committed
271 272
    part->BlocksPerUnit = (1 << header.EraseUnitSize) >> header.BlockSize;

273 274
    part->bam_cache = kmalloc_array(part->BlocksPerUnit, sizeof(uint32_t),
                                    GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
275 276 277 278 279 280 281 282 283 284
    if (!part->bam_cache)
	    goto out_VirtualBlockMap;

    part->bam_index = 0xffff;
    part->FreeTotal = 0;

    for (i = 0; i < part->DataUnits; i++) {
	part->EUNInfo[i].Free = 0;
	part->EUNInfo[i].Deleted = 0;
	offset = part->EUNInfo[i].Offset + le32_to_cpu(header.BAMOffset);
285

286 287 288
	ret = mtd_read(part->mbd.mtd, offset,
                       part->BlocksPerUnit * sizeof(uint32_t), &retval,
                       (unsigned char *)part->bam_cache);
289 290

	if (ret)
Linus Torvalds's avatar
Linus Torvalds committed
291 292 293 294 295 296 297 298 299 300 301 302 303 304
		goto out_bam_cache;

	for (j = 0; j < part->BlocksPerUnit; j++) {
	    if (BLOCK_FREE(le32_to_cpu(part->bam_cache[j]))) {
		part->EUNInfo[i].Free++;
		part->FreeTotal++;
	    } else if ((BLOCK_TYPE(le32_to_cpu(part->bam_cache[j])) == BLOCK_DATA) &&
		     (BLOCK_NUMBER(le32_to_cpu(part->bam_cache[j])) < blocks))
		part->VirtualBlockMap[BLOCK_NUMBER(le32_to_cpu(part->bam_cache[j]))] =
		    (i << header.EraseUnitSize) + (j << header.BlockSize);
	    else if (BLOCK_DELETED(le32_to_cpu(part->bam_cache[j])))
		part->EUNInfo[i].Deleted++;
	}
    }
305

Linus Torvalds's avatar
Linus Torvalds committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
    ret = 0;
    goto out;

out_bam_cache:
    kfree(part->bam_cache);
out_VirtualBlockMap:
    vfree(part->VirtualBlockMap);
out_XferInfo:
    kfree(part->XferInfo);
out_EUNInfo:
    kfree(part->EUNInfo);
out:
    return ret;
} /* build_maps */

/*======================================================================

    Erase_xfer() schedules an asynchronous erase operation for a
    transfer unit.
325

Linus Torvalds's avatar
Linus Torvalds committed
326 327 328
======================================================================*/

static int erase_xfer(partition_t *part,
329
		      uint16_t xfernum)
Linus Torvalds's avatar
Linus Torvalds committed
330 331 332 333 334 335
{
    int ret;
    struct xfer_info_t *xfer;
    struct erase_info *erase;

    xfer = &part->XferInfo[xfernum];
336
    pr_debug("ftl_cs: erasing xfer unit at 0x%x\n", xfer->Offset);
Linus Torvalds's avatar
Linus Torvalds committed
337 338 339
    xfer->state = XFER_ERASING;

    /* Is there a free erase slot? Always in MTD. */
340 341


Linus Torvalds's avatar
Linus Torvalds committed
342
    erase=kmalloc(sizeof(struct erase_info), GFP_KERNEL);
343
    if (!erase)
Linus Torvalds's avatar
Linus Torvalds committed
344 345 346 347
            return -ENOMEM;

    erase->addr = xfer->Offset;
    erase->len = 1 << part->header.EraseUnitSize;
348

349
    ret = mtd_erase(part->mbd.mtd, erase);
350 351 352 353 354 355 356
    if (!ret) {
	xfer->state = XFER_ERASED;
	xfer->EraseCount++;
    } else {
	xfer->state = XFER_FAILED;
	pr_notice("ftl_cs: erase failed: err = %d\n", ret);
    }
Linus Torvalds's avatar
Linus Torvalds committed
357

358
    kfree(erase);
Linus Torvalds's avatar
Linus Torvalds committed
359 360 361 362 363 364 365 366

    return ret;
} /* erase_xfer */

/*======================================================================

    Prepare_xfer() takes a freshly erased transfer unit and gives
    it an appropriate header.
367

Linus Torvalds's avatar
Linus Torvalds committed
368 369 370 371 372 373 374
======================================================================*/

static int prepare_xfer(partition_t *part, int i)
{
    erase_unit_header_t header;
    struct xfer_info_t *xfer;
    int nbam, ret;
375
    uint32_t ctl;
Linus Torvalds's avatar
Linus Torvalds committed
376 377 378 379 380
    ssize_t retlen;
    loff_t offset;

    xfer = &part->XferInfo[i];
    xfer->state = XFER_FAILED;
381

382
    pr_debug("ftl_cs: preparing xfer unit at 0x%x\n", xfer->Offset);
Linus Torvalds's avatar
Linus Torvalds committed
383 384 385 386 387 388

    /* Write the transfer unit header */
    header = part->header;
    header.LogicalEUN = cpu_to_le16(0xffff);
    header.EraseCount = cpu_to_le32(xfer->EraseCount);

389 390
    ret = mtd_write(part->mbd.mtd, xfer->Offset, sizeof(header), &retlen,
                    (u_char *)&header);
Linus Torvalds's avatar
Linus Torvalds committed
391 392 393 394 395 396

    if (ret) {
	return ret;
    }

    /* Write the BAM stub */
Arushi's avatar
Arushi committed
397 398
    nbam = DIV_ROUND_UP(part->BlocksPerUnit * sizeof(uint32_t) +
			le32_to_cpu(part->header.BAMOffset), SECTOR_SIZE);
Linus Torvalds's avatar
Linus Torvalds committed
399 400 401 402

    offset = xfer->Offset + le32_to_cpu(part->header.BAMOffset);
    ctl = cpu_to_le32(BLOCK_CONTROL);

403
    for (i = 0; i < nbam; i++, offset += sizeof(uint32_t)) {
Linus Torvalds's avatar
Linus Torvalds committed
404

405 406
	ret = mtd_write(part->mbd.mtd, offset, sizeof(uint32_t), &retlen,
                        (u_char *)&ctl);
Linus Torvalds's avatar
Linus Torvalds committed
407 408 409 410 411 412

	if (ret)
	    return ret;
    }
    xfer->state = XFER_PREPARED;
    return 0;
413

Linus Torvalds's avatar
Linus Torvalds committed
414 415 416 417 418 419 420 421 422 423 424
} /* prepare_xfer */

/*======================================================================

    Copy_erase_unit() takes a full erase block and a transfer unit,
    copies everything to the transfer unit, then swaps the block
    pointers.

    All data blocks are copied to the corresponding blocks in the
    target unit, so the virtual block map does not need to be
    updated.
425

Linus Torvalds's avatar
Linus Torvalds committed
426 427
======================================================================*/

428 429
static int copy_erase_unit(partition_t *part, uint16_t srcunit,
			   uint16_t xferunit)
Linus Torvalds's avatar
Linus Torvalds committed
430 431 432 433
{
    u_char buf[SECTOR_SIZE];
    struct eun_info_t *eun;
    struct xfer_info_t *xfer;
434 435
    uint32_t src, dest, free, i;
    uint16_t unit;
Linus Torvalds's avatar
Linus Torvalds committed
436 437 438
    int ret;
    ssize_t retlen;
    loff_t offset;
439
    uint16_t srcunitswap = cpu_to_le16(srcunit);
Linus Torvalds's avatar
Linus Torvalds committed
440 441 442

    eun = &part->EUNInfo[srcunit];
    xfer = &part->XferInfo[xferunit];
443
    pr_debug("ftl_cs: copying block 0x%x to 0x%x\n",
Linus Torvalds's avatar
Linus Torvalds committed
444
	  eun->Offset, xfer->Offset);
445 446


Linus Torvalds's avatar
Linus Torvalds committed
447 448 449 450 451
    /* Read current BAM */
    if (part->bam_index != srcunit) {

	offset = eun->Offset + le32_to_cpu(part->header.BAMOffset);

452 453 454
	ret = mtd_read(part->mbd.mtd, offset,
                       part->BlocksPerUnit * sizeof(uint32_t), &retlen,
                       (u_char *)(part->bam_cache));
Linus Torvalds's avatar
Linus Torvalds committed
455 456 457 458 459

	/* mark the cache bad, in case we get an error later */
	part->bam_index = 0xffff;

	if (ret) {
460
	    printk( KERN_WARNING "ftl: Failed to read BAM cache in copy_erase_unit()!\n");
Linus Torvalds's avatar
Linus Torvalds committed
461 462 463
	    return ret;
	}
    }
464

Linus Torvalds's avatar
Linus Torvalds committed
465 466 467 468 469
    /* Write the LogicalEUN for the transfer unit */
    xfer->state = XFER_UNKNOWN;
    offset = xfer->Offset + 20; /* Bad! */
    unit = cpu_to_le16(0x7fff);

470 471
    ret = mtd_write(part->mbd.mtd, offset, sizeof(uint16_t), &retlen,
                    (u_char *)&unit);
472

Linus Torvalds's avatar
Linus Torvalds committed
473 474 475 476
    if (ret) {
	printk( KERN_WARNING "ftl: Failed to write back to BAM cache in copy_erase_unit()!\n");
	return ret;
    }
477

Linus Torvalds's avatar
Linus Torvalds committed
478 479 480 481 482 483 484 485 486 487 488 489
    /* Copy all data blocks from source unit to transfer unit */
    src = eun->Offset; dest = xfer->Offset;

    free = 0;
    ret = 0;
    for (i = 0; i < part->BlocksPerUnit; i++) {
	switch (BLOCK_TYPE(le32_to_cpu(part->bam_cache[i]))) {
	case BLOCK_CONTROL:
	    /* This gets updated later */
	    break;
	case BLOCK_DATA:
	case BLOCK_REPLACEMENT:
490 491
	    ret = mtd_read(part->mbd.mtd, src, SECTOR_SIZE, &retlen,
                           (u_char *)buf);
Linus Torvalds's avatar
Linus Torvalds committed
492 493 494 495 496 497
	    if (ret) {
		printk(KERN_WARNING "ftl: Error reading old xfer unit in copy_erase_unit\n");
		return ret;
            }


498 499
	    ret = mtd_write(part->mbd.mtd, dest, SECTOR_SIZE, &retlen,
                            (u_char *)buf);
Linus Torvalds's avatar
Linus Torvalds committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516
	    if (ret)  {
		printk(KERN_WARNING "ftl: Error writing new xfer unit in copy_erase_unit\n");
		return ret;
            }

	    break;
	default:
	    /* All other blocks must be free */
	    part->bam_cache[i] = cpu_to_le32(0xffffffff);
	    free++;
	    break;
	}
	src += SECTOR_SIZE;
	dest += SECTOR_SIZE;
    }

    /* Write the BAM to the transfer unit */
517 518 519 520 521
    ret = mtd_write(part->mbd.mtd,
                    xfer->Offset + le32_to_cpu(part->header.BAMOffset),
                    part->BlocksPerUnit * sizeof(int32_t),
                    &retlen,
                    (u_char *)part->bam_cache);
Linus Torvalds's avatar
Linus Torvalds committed
522 523 524 525 526
    if (ret) {
	printk( KERN_WARNING "ftl: Error writing BAM in copy_erase_unit\n");
	return ret;
    }

527

Linus Torvalds's avatar
Linus Torvalds committed
528
    /* All clear? Then update the LogicalEUN again */
529 530
    ret = mtd_write(part->mbd.mtd, xfer->Offset + 20, sizeof(uint16_t),
                    &retlen, (u_char *)&srcunitswap);
Linus Torvalds's avatar
Linus Torvalds committed
531 532 533 534

    if (ret) {
	printk(KERN_WARNING "ftl: Error writing new LogicalEUN in copy_erase_unit\n");
	return ret;
535 536 537
    }


Linus Torvalds's avatar
Linus Torvalds committed
538
    /* Update the maps and usage stats*/
539 540
    swap(xfer->EraseCount, eun->EraseCount);
    swap(xfer->Offset, eun->Offset);
Linus Torvalds's avatar
Linus Torvalds committed
541 542 543 544
    part->FreeTotal -= eun->Free;
    part->FreeTotal += free;
    eun->Free = free;
    eun->Deleted = 0;
545

Linus Torvalds's avatar
Linus Torvalds committed
546 547
    /* Now, the cache should be valid for the new block */
    part->bam_index = srcunit;
548

Linus Torvalds's avatar
Linus Torvalds committed
549 550 551 552 553 554 555 556 557 558 559 560 561 562
    return 0;
} /* copy_erase_unit */

/*======================================================================

    reclaim_block() picks a full erase unit and a transfer unit and
    then calls copy_erase_unit() to copy one to the other.  Then, it
    schedules an erase on the expired block.

    What's a good way to decide which transfer unit and which erase
    unit to use?  Beats me.  My way is to always pick the transfer
    unit with the fewest erases, and usually pick the data unit with
    the most deleted blocks.  But with a small probability, pick the
    oldest data unit instead.  This means that we generally postpone
Brian Norris's avatar
Brian Norris committed
563
    the next reclamation as long as possible, but shuffle static
Linus Torvalds's avatar
Linus Torvalds committed
564
    stuff around a bit for wear leveling.
565

Linus Torvalds's avatar
Linus Torvalds committed
566 567 568 569
======================================================================*/

static int reclaim_block(partition_t *part)
{
570 571
    uint16_t i, eun, xfer;
    uint32_t best;
Linus Torvalds's avatar
Linus Torvalds committed
572 573
    int queued, ret;

574 575
    pr_debug("ftl_cs: reclaiming space...\n");
    pr_debug("NumTransferUnits == %x\n", part->header.NumTransferUnits);
Linus Torvalds's avatar
Linus Torvalds committed
576 577 578 579 580 581 582
    /* Pick the least erased transfer unit */
    best = 0xffffffff; xfer = 0xffff;
    do {
	queued = 0;
	for (i = 0; i < part->header.NumTransferUnits; i++) {
	    int n=0;
	    if (part->XferInfo[i].state == XFER_UNKNOWN) {
583
		pr_debug("XferInfo[%d].state == XFER_UNKNOWN\n",i);
Linus Torvalds's avatar
Linus Torvalds committed
584 585 586 587
		n=1;
		erase_xfer(part, i);
	    }
	    if (part->XferInfo[i].state == XFER_ERASING) {
588
		pr_debug("XferInfo[%d].state == XFER_ERASING\n",i);
Linus Torvalds's avatar
Linus Torvalds committed
589 590 591 592
		n=1;
		queued = 1;
	    }
	    else if (part->XferInfo[i].state == XFER_ERASED) {
593
		pr_debug("XferInfo[%d].state == XFER_ERASED\n",i);
Linus Torvalds's avatar
Linus Torvalds committed
594 595 596 597
		n=1;
		prepare_xfer(part, i);
	    }
	    if (part->XferInfo[i].state == XFER_PREPARED) {
598
		pr_debug("XferInfo[%d].state == XFER_PREPARED\n",i);
Linus Torvalds's avatar
Linus Torvalds committed
599 600 601 602 603 604 605
		n=1;
		if (part->XferInfo[i].EraseCount <= best) {
		    best = part->XferInfo[i].EraseCount;
		    xfer = i;
		}
	    }
		if (!n)
606
		    pr_debug("XferInfo[%d].state == %x\n",i, part->XferInfo[i].state);
Linus Torvalds's avatar
Linus Torvalds committed
607 608 609 610

	}
	if (xfer == 0xffff) {
	    if (queued) {
611
		pr_debug("ftl_cs: waiting for transfer "
Linus Torvalds's avatar
Linus Torvalds committed
612
		      "unit to be prepared...\n");
613
		mtd_sync(part->mbd.mtd);
Linus Torvalds's avatar
Linus Torvalds committed
614 615 616 617 618 619
	    } else {
		static int ne = 0;
		if (++ne < 5)
		    printk(KERN_NOTICE "ftl_cs: reclaim failed: no "
			   "suitable transfer units!\n");
		else
620
		    pr_debug("ftl_cs: reclaim failed: no "
Linus Torvalds's avatar
Linus Torvalds committed
621
			  "suitable transfer units!\n");
622

Linus Torvalds's avatar
Linus Torvalds committed
623 624 625 626 627 628 629
		return -EIO;
	    }
	}
    } while (xfer == 0xffff);

    eun = 0;
    if ((jiffies % shuffle_freq) == 0) {
630
	pr_debug("ftl_cs: recycling freshest block...\n");
Linus Torvalds's avatar
Linus Torvalds committed
631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649
	best = 0xffffffff;
	for (i = 0; i < part->DataUnits; i++)
	    if (part->EUNInfo[i].EraseCount <= best) {
		best = part->EUNInfo[i].EraseCount;
		eun = i;
	    }
    } else {
	best = 0;
	for (i = 0; i < part->DataUnits; i++)
	    if (part->EUNInfo[i].Deleted >= best) {
		best = part->EUNInfo[i].Deleted;
		eun = i;
	    }
	if (best == 0) {
	    static int ne = 0;
	    if (++ne < 5)
		printk(KERN_NOTICE "ftl_cs: reclaim failed: "
		       "no free blocks!\n");
	    else
650
		pr_debug("ftl_cs: reclaim failed: "
Linus Torvalds's avatar
Linus Torvalds committed
651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670
		       "no free blocks!\n");

	    return -EIO;
	}
    }
    ret = copy_erase_unit(part, eun, xfer);
    if (!ret)
	erase_xfer(part, xfer);
    else
	printk(KERN_NOTICE "ftl_cs: copy_erase_unit failed!\n");
    return ret;
} /* reclaim_block */

/*======================================================================

    Find_free() searches for a free block.  If necessary, it updates
    the BAM cache for the erase unit containing the free block.  It
    returns the block index -- the erase unit is just the currently
    cached unit.  If there are no free blocks, it returns 0 -- this
    is never a valid data block because it contains the header.
671

Linus Torvalds's avatar
Linus Torvalds committed
672 673 674 675 676 677 678 679 680 681 682 683 684 685 686
======================================================================*/

#ifdef PSYCHO_DEBUG
static void dump_lists(partition_t *part)
{
    int i;
    printk(KERN_DEBUG "ftl_cs: Free total = %d\n", part->FreeTotal);
    for (i = 0; i < part->DataUnits; i++)
	printk(KERN_DEBUG "ftl_cs:   unit %d: %d phys, %d free, "
	       "%d deleted\n", i,
	       part->EUNInfo[i].Offset >> part->header.EraseUnitSize,
	       part->EUNInfo[i].Free, part->EUNInfo[i].Deleted);
}
#endif

687
static uint32_t find_free(partition_t *part)
Linus Torvalds's avatar
Linus Torvalds committed
688
{
689 690
    uint16_t stop, eun;
    uint32_t blk;
Linus Torvalds's avatar
Linus Torvalds committed
691 692
    size_t retlen;
    int ret;
693

Linus Torvalds's avatar
Linus Torvalds committed
694 695 696 697 698 699 700 701 702 703 704
    /* Find an erase unit with some free space */
    stop = (part->bam_index == 0xffff) ? 0 : part->bam_index;
    eun = stop;
    do {
	if (part->EUNInfo[eun].Free != 0) break;
	/* Wrap around at end of table */
	if (++eun == part->DataUnits) eun = 0;
    } while (eun != stop);

    if (part->EUNInfo[eun].Free == 0)
	return 0;
705

Linus Torvalds's avatar
Linus Torvalds committed
706 707 708 709 710
    /* Is this unit's BAM cached? */
    if (eun != part->bam_index) {
	/* Invalidate cache */
	part->bam_index = 0xffff;

711 712 713 714 715
	ret = mtd_read(part->mbd.mtd,
                       part->EUNInfo[eun].Offset + le32_to_cpu(part->header.BAMOffset),
                       part->BlocksPerUnit * sizeof(uint32_t),
                       &retlen,
                       (u_char *)(part->bam_cache));
716

Linus Torvalds's avatar
Linus Torvalds committed
717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735
	if (ret) {
	    printk(KERN_WARNING"ftl: Error reading BAM in find_free\n");
	    return 0;
	}
	part->bam_index = eun;
    }

    /* Find a free block */
    for (blk = 0; blk < part->BlocksPerUnit; blk++)
	if (BLOCK_FREE(le32_to_cpu(part->bam_cache[blk]))) break;
    if (blk == part->BlocksPerUnit) {
#ifdef PSYCHO_DEBUG
	static int ne = 0;
	if (++ne == 1)
	    dump_lists(part);
#endif
	printk(KERN_NOTICE "ftl_cs: bad free list!\n");
	return 0;
    }
736
    pr_debug("ftl_cs: found free block at %d in %d\n", blk, eun);
Linus Torvalds's avatar
Linus Torvalds committed
737
    return blk;
738

Linus Torvalds's avatar
Linus Torvalds committed
739 740 741 742 743 744
} /* find_free */


/*======================================================================

    Read a series of sectors from an FTL partition.
745

Linus Torvalds's avatar
Linus Torvalds committed
746 747 748 749 750
======================================================================*/

static int ftl_read(partition_t *part, caddr_t buffer,
		    u_long sector, u_long nblocks)
{
751
    uint32_t log_addr, bsize;
Linus Torvalds's avatar
Linus Torvalds committed
752 753 754
    u_long i;
    int ret;
    size_t offset, retlen;
755

756
    pr_debug("ftl_cs: ftl_read(0x%p, 0x%lx, %ld)\n",
Linus Torvalds's avatar
Linus Torvalds committed
757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774
	  part, sector, nblocks);
    if (!(part->state & FTL_FORMATTED)) {
	printk(KERN_NOTICE "ftl_cs: bad partition\n");
	return -EIO;
    }
    bsize = 1 << part->header.EraseUnitSize;

    for (i = 0; i < nblocks; i++) {
	if (((sector+i) * SECTOR_SIZE) >= le32_to_cpu(part->header.FormattedSize)) {
	    printk(KERN_NOTICE "ftl_cs: bad read offset\n");
	    return -EIO;
	}
	log_addr = part->VirtualBlockMap[sector+i];
	if (log_addr == 0xffffffff)
	    memset(buffer, 0, SECTOR_SIZE);
	else {
	    offset = (part->EUNInfo[log_addr / bsize].Offset
			  + (log_addr % bsize));
775 776
	    ret = mtd_read(part->mbd.mtd, offset, SECTOR_SIZE, &retlen,
                           (u_char *)buffer);
Linus Torvalds's avatar
Linus Torvalds committed
777 778 779 780 781 782 783 784 785 786 787 788 789 790

	    if (ret) {
		printk(KERN_WARNING "Error reading MTD device in ftl_read()\n");
		return ret;
	    }
	}
	buffer += SECTOR_SIZE;
    }
    return 0;
} /* ftl_read */

/*======================================================================

    Write a series of sectors to an FTL partition
791

Linus Torvalds's avatar
Linus Torvalds committed
792 793
======================================================================*/

794 795
static int set_bam_entry(partition_t *part, uint32_t log_addr,
			 uint32_t virt_addr)
Linus Torvalds's avatar
Linus Torvalds committed
796
{
797
    uint32_t bsize, blk, le_virt_addr;
Linus Torvalds's avatar
Linus Torvalds committed
798
#ifdef PSYCHO_DEBUG
799
    uint32_t old_addr;
Linus Torvalds's avatar
Linus Torvalds committed
800
#endif
801
    uint16_t eun;
Linus Torvalds's avatar
Linus Torvalds committed
802 803 804
    int ret;
    size_t retlen, offset;

805
    pr_debug("ftl_cs: set_bam_entry(0x%p, 0x%x, 0x%x)\n",
Linus Torvalds's avatar
Linus Torvalds committed
806 807 808 809
	  part, log_addr, virt_addr);
    bsize = 1 << part->header.EraseUnitSize;
    eun = log_addr / bsize;
    blk = (log_addr % bsize) / SECTOR_SIZE;
810
    offset = (part->EUNInfo[eun].Offset + blk * sizeof(uint32_t) +
Linus Torvalds's avatar
Linus Torvalds committed
811
		  le32_to_cpu(part->header.BAMOffset));
812

Linus Torvalds's avatar
Linus Torvalds committed
813
#ifdef PSYCHO_DEBUG
814 815
    ret = mtd_read(part->mbd.mtd, offset, sizeof(uint32_t), &retlen,
                   (u_char *)&old_addr);
Linus Torvalds's avatar
Linus Torvalds committed
816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
    if (ret) {
	printk(KERN_WARNING"ftl: Error reading old_addr in set_bam_entry: %d\n",ret);
	return ret;
    }
    old_addr = le32_to_cpu(old_addr);

    if (((virt_addr == 0xfffffffe) && !BLOCK_FREE(old_addr)) ||
	((virt_addr == 0) && (BLOCK_TYPE(old_addr) != BLOCK_DATA)) ||
	(!BLOCK_DELETED(virt_addr) && (old_addr != 0xfffffffe))) {
	static int ne = 0;
	if (++ne < 5) {
	    printk(KERN_NOTICE "ftl_cs: set_bam_entry() inconsistency!\n");
	    printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, old = 0x%x"
		   ", new = 0x%x\n", log_addr, old_addr, virt_addr);
	}
	return -EIO;
    }
#endif
    le_virt_addr = cpu_to_le32(virt_addr);
    if (part->bam_index == eun) {
#ifdef PSYCHO_DEBUG
	if (le32_to_cpu(part->bam_cache[blk]) != old_addr) {
	    static int ne = 0;
	    if (++ne < 5) {
		printk(KERN_NOTICE "ftl_cs: set_bam_entry() "
		       "inconsistency!\n");
		printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, cache"
		       " = 0x%x\n",
		       le32_to_cpu(part->bam_cache[blk]), old_addr);
	    }
	    return -EIO;
	}
#endif
	part->bam_cache[blk] = le_virt_addr;
    }
851 852
    ret = mtd_write(part->mbd.mtd, offset, sizeof(uint32_t), &retlen,
                    (u_char *)&le_virt_addr);
Linus Torvalds's avatar
Linus Torvalds committed
853 854 855 856 857 858 859 860 861 862 863 864

    if (ret) {
	printk(KERN_NOTICE "ftl_cs: set_bam_entry() failed!\n");
	printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, new = 0x%x\n",
	       log_addr, virt_addr);
    }
    return ret;
} /* set_bam_entry */

static int ftl_write(partition_t *part, caddr_t buffer,
		     u_long sector, u_long nblocks)
{
865
    uint32_t bsize, log_addr, virt_addr, old_addr, blk;
Linus Torvalds's avatar
Linus Torvalds committed
866 867 868 869
    u_long i;
    int ret;
    size_t retlen, offset;

870
    pr_debug("ftl_cs: ftl_write(0x%p, %ld, %ld)\n",
Linus Torvalds's avatar
Linus Torvalds committed
871 872 873 874 875 876 877 878 879 880 881
	  part, sector, nblocks);
    if (!(part->state & FTL_FORMATTED)) {
	printk(KERN_NOTICE "ftl_cs: bad partition\n");
	return -EIO;
    }
    /* See if we need to reclaim space, before we start */
    while (part->FreeTotal < nblocks) {
	ret = reclaim_block(part);
	if (ret)
	    return ret;
    }
882

Linus Torvalds's avatar
Linus Torvalds committed
883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
    bsize = 1 << part->header.EraseUnitSize;

    virt_addr = sector * SECTOR_SIZE | BLOCK_DATA;
    for (i = 0; i < nblocks; i++) {
	if (virt_addr >= le32_to_cpu(part->header.FormattedSize)) {
	    printk(KERN_NOTICE "ftl_cs: bad write offset\n");
	    return -EIO;
	}

	/* Grab a free block */
	blk = find_free(part);
	if (blk == 0) {
	    static int ne = 0;
	    if (++ne < 5)
		printk(KERN_NOTICE "ftl_cs: internal error: "
		       "no free blocks!\n");
	    return -ENOSPC;
	}

	/* Tag the BAM entry, and write the new block */
	log_addr = part->bam_index * bsize + blk * SECTOR_SIZE;
	part->EUNInfo[part->bam_index].Free--;
	part->FreeTotal--;
906
	if (set_bam_entry(part, log_addr, 0xfffffffe))
Linus Torvalds's avatar
Linus Torvalds committed
907 908 909 910
	    return -EIO;
	part->EUNInfo[part->bam_index].Deleted++;
	offset = (part->EUNInfo[part->bam_index].Offset +
		      blk * SECTOR_SIZE);
911
	ret = mtd_write(part->mbd.mtd, offset, SECTOR_SIZE, &retlen, buffer);
Linus Torvalds's avatar
Linus Torvalds committed
912 913 914 915 916 917 918 919

	if (ret) {
	    printk(KERN_NOTICE "ftl_cs: block write failed!\n");
	    printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, virt_addr"
		   " = 0x%x, Offset = 0x%zx\n", log_addr, virt_addr,
		   offset);
	    return -EIO;
	}
920

Linus Torvalds's avatar
Linus Torvalds committed
921 922 923 924 925 926 927 928 929 930 931 932 933 934
	/* Only delete the old entry when the new entry is ready */
	old_addr = part->VirtualBlockMap[sector+i];
	if (old_addr != 0xffffffff) {
	    part->VirtualBlockMap[sector+i] = 0xffffffff;
	    part->EUNInfo[old_addr/bsize].Deleted++;
	    if (set_bam_entry(part, old_addr, 0))
		return -EIO;
	}

	/* Finally, set up the new pointers */
	if (set_bam_entry(part, log_addr, virt_addr))
	    return -EIO;
	part->VirtualBlockMap[sector+i] = log_addr;
	part->EUNInfo[part->bam_index].Deleted--;
935

Linus Torvalds's avatar
Linus Torvalds committed
936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968
	buffer += SECTOR_SIZE;
	virt_addr += SECTOR_SIZE;
    }
    return 0;
} /* ftl_write */

static int ftl_getgeo(struct mtd_blktrans_dev *dev, struct hd_geometry *geo)
{
	partition_t *part = (void *)dev;
	u_long sect;

	/* Sort of arbitrary: round size down to 4KiB boundary */
	sect = le32_to_cpu(part->header.FormattedSize)/SECTOR_SIZE;

	geo->heads = 1;
	geo->sectors = 8;
	geo->cylinders = sect >> 3;

	return 0;
}

static int ftl_readsect(struct mtd_blktrans_dev *dev,
			      unsigned long block, char *buf)
{
	return ftl_read((void *)dev, buf, block, 1);
}

static int ftl_writesect(struct mtd_blktrans_dev *dev,
			      unsigned long block, char *buf)
{
	return ftl_write((void *)dev, buf, block, 1);
}

969 970 971 972 973 974
static int ftl_discardsect(struct mtd_blktrans_dev *dev,
			   unsigned long sector, unsigned nr_sects)
{
	partition_t *part = (void *)dev;
	uint32_t bsize = 1 << part->header.EraseUnitSize;

975
	pr_debug("FTL erase sector %ld for %d sectors\n",
976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991
	      sector, nr_sects);

	while (nr_sects) {
		uint32_t old_addr = part->VirtualBlockMap[sector];
		if (old_addr != 0xffffffff) {
			part->VirtualBlockMap[sector] = 0xffffffff;
			part->EUNInfo[old_addr/bsize].Deleted++;
			if (set_bam_entry(part, old_addr, 0))
				return -EIO;
		}
		nr_sects--;
		sector++;
	}

	return 0;
}
Linus Torvalds's avatar
Linus Torvalds committed
992 993
/*====================================================================*/

994
static void ftl_freepart(partition_t *part)
Linus Torvalds's avatar
Linus Torvalds committed
995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009
{
	vfree(part->VirtualBlockMap);
	part->VirtualBlockMap = NULL;
	kfree(part->EUNInfo);
	part->EUNInfo = NULL;
	kfree(part->XferInfo);
	part->XferInfo = NULL;
	kfree(part->bam_cache);
	part->bam_cache = NULL;
} /* ftl_freepart */

static void ftl_add_mtd(struct mtd_blktrans_ops *tr, struct mtd_info *mtd)
{
	partition_t *partition;

1010
	partition = kzalloc(sizeof(partition_t), GFP_KERNEL);
1011

Linus Torvalds's avatar
Linus Torvalds committed
1012 1013 1014 1015
	if (!partition) {
		printk(KERN_WARNING "No memory to scan for FTL on %s\n",
		       mtd->name);
		return;
1016
	}
Linus Torvalds's avatar
Linus Torvalds committed
1017 1018 1019

	partition->mbd.mtd = mtd;

1020
	if ((scan_header(partition) == 0) &&
Linus Torvalds's avatar
Linus Torvalds committed
1021
	    (build_maps(partition) == 0)) {
1022

Linus Torvalds's avatar
Linus Torvalds committed
1023 1024 1025 1026 1027 1028
		partition->state = FTL_FORMATTED;
#ifdef PCMCIA_DEBUG
		printk(KERN_INFO "ftl_cs: opening %d KiB FTL partition\n",
		       le32_to_cpu(partition->header.FormattedSize) >> 10);
#endif
		partition->mbd.size = le32_to_cpu(partition->header.FormattedSize) >> 9;
1029

Linus Torvalds's avatar
Linus Torvalds committed
1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044
		partition->mbd.tr = tr;
		partition->mbd.devnum = -1;
		if (!add_mtd_blktrans_dev((void *)partition))
			return;
	}

	kfree(partition);
}

static void ftl_remove_dev(struct mtd_blktrans_dev *dev)
{
	del_mtd_blktrans_dev(dev);
	ftl_freepart((partition_t *)dev);
}

1045
static struct mtd_blktrans_ops ftl_tr = {
Linus Torvalds's avatar
Linus Torvalds committed
1046 1047 1048
	.name		= "ftl",
	.major		= FTL_MAJOR,
	.part_bits	= PART_BITS,
1049
	.blksize 	= SECTOR_SIZE,
Linus Torvalds's avatar
Linus Torvalds committed
1050 1051
	.readsect	= ftl_readsect,
	.writesect	= ftl_writesect,
1052
	.discard	= ftl_discardsect,
Linus Torvalds's avatar
Linus Torvalds committed
1053 1054 1055 1056 1057 1058
	.getgeo		= ftl_getgeo,
	.add_mtd	= ftl_add_mtd,
	.remove_dev	= ftl_remove_dev,
	.owner		= THIS_MODULE,
};

1059
static int __init init_ftl(void)
Linus Torvalds's avatar
Linus Torvalds committed
1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075
{
	return register_mtd_blktrans(&ftl_tr);
}

static void __exit cleanup_ftl(void)
{
	deregister_mtd_blktrans(&ftl_tr);
}

module_init(init_ftl);
module_exit(cleanup_ftl);


MODULE_LICENSE("Dual MPL/GPL");
MODULE_AUTHOR("David Hinds <dahinds@users.sourceforge.net>");
MODULE_DESCRIPTION("Support code for Flash Translation Layer, used on PCMCIA devices");