linux/drivers/mtd/ftl.c
<<
>>
Prefs
   1/* This version ported to the Linux-MTD system by dwmw2@infradead.org
   2 *
   3 * Fixes: Arnaldo Carvalho de Melo <acme@conectiva.com.br>
   4 * - fixes some leaks on failure in build_maps and ftl_notify_add, cleanups
   5 *
   6 * Based on:
   7 */
   8/*======================================================================
   9
  10    A Flash Translation Layer memory card driver
  11
  12    This driver implements a disk-like block device driver with an
  13    apparent block size of 512 bytes for flash memory cards.
  14
  15    ftl_cs.c 1.62 2000/02/01 00:59:04
  16
  17    The contents of this file are subject to the Mozilla Public
  18    License Version 1.1 (the "License"); you may not use this file
  19    except in compliance with the License. You may obtain a copy of
  20    the License at http://www.mozilla.org/MPL/
  21
  22    Software distributed under the License is distributed on an "AS
  23    IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
  24    implied. See the License for the specific language governing
  25    rights and limitations under the License.
  26
  27    The initial developer of the original code is David A. Hinds
  28    <dahinds@users.sourceforge.net>.  Portions created by David A. Hinds
  29    are Copyright © 1999 David A. Hinds.  All Rights Reserved.
  30
  31    Alternatively, the contents of this file may be used under the
  32    terms of the GNU General Public License version 2 (the "GPL"), in
  33    which case the provisions of the GPL are applicable instead of the
  34    above.  If you wish to allow the use of your version of this file
  35    only under the terms of the GPL and not to allow others to use
  36    your version of this file under the MPL, indicate your decision
  37    by deleting the provisions above and replace them with the notice
  38    and other provisions required by the GPL.  If you do not delete
  39    the provisions above, a recipient may use your version of this
  40    file under either the MPL or the GPL.
  41
  42    LEGAL NOTE: The FTL format is patented by M-Systems.  They have
  43    granted a license for its use with PCMCIA devices:
  44
  45     "M-Systems grants a royalty-free, non-exclusive license under
  46      any presently existing M-Systems intellectual property rights
  47      necessary for the design and development of FTL-compatible
  48      drivers, file systems and utilities using the data formats with
  49      PCMCIA PC Cards as described in the PCMCIA Flash Translation
  50      Layer (FTL) Specification."
  51
  52    Use of the FTL format for non-PCMCIA applications may be an
  53    infringement of these patents.  For additional information,
  54    contact M-Systems directly. M-Systems since acquired by Sandisk. 
  55
  56======================================================================*/
  57#include <linux/mtd/blktrans.h>
  58#include <linux/module.h>
  59#include <linux/mtd/mtd.h>
  60/*#define PSYCHO_DEBUG */
  61
  62#include <linux/kernel.h>
  63#include <linux/ptrace.h>
  64#include <linux/slab.h>
  65#include <linux/string.h>
  66#include <linux/timer.h>
  67#include <linux/major.h>
  68#include <linux/fs.h>
  69#include <linux/init.h>
  70#include <linux/hdreg.h>
  71#include <linux/vmalloc.h>
  72#include <linux/blkpg.h>
  73#include <linux/uaccess.h>
  74
  75#include <linux/mtd/ftl.h>
  76
  77/*====================================================================*/
  78
  79/* Parameters that can be set with 'insmod' */
  80static int shuffle_freq = 50;
  81module_param(shuffle_freq, int, 0);
  82
  83/*====================================================================*/
  84
  85/* Major device # for FTL device */
  86#ifndef FTL_MAJOR
  87#define FTL_MAJOR       44
  88#endif
  89
  90
  91/*====================================================================*/
  92
  93/* Maximum number of separate memory devices we'll allow */
  94#define MAX_DEV         4
  95
  96/* Maximum number of regions per device */
  97#define MAX_REGION      4
  98
  99/* Maximum number of partitions in an FTL region */
 100#define PART_BITS       4
 101
 102/* Maximum number of outstanding erase requests per socket */
 103#define MAX_ERASE       8
 104
 105/* Sector size -- shouldn't need to change */
 106#define SECTOR_SIZE     512
 107
 108
 109/* Each memory region corresponds to a minor device */
 110typedef struct partition_t {
 111    struct mtd_blktrans_dev mbd;
 112    uint32_t            state;
 113    uint32_t            *VirtualBlockMap;
 114    uint32_t            FreeTotal;
 115    struct eun_info_t {
 116        uint32_t                Offset;
 117        uint32_t                EraseCount;
 118        uint32_t                Free;
 119        uint32_t                Deleted;
 120    } *EUNInfo;
 121    struct xfer_info_t {
 122        uint32_t                Offset;
 123        uint32_t                EraseCount;
 124        uint16_t                state;
 125    } *XferInfo;
 126    uint16_t            bam_index;
 127    uint32_t            *bam_cache;
 128    uint16_t            DataUnits;
 129    uint32_t            BlocksPerUnit;
 130    erase_unit_header_t header;
 131} partition_t;
 132
 133/* Partition state flags */
 134#define FTL_FORMATTED   0x01
 135
 136/* Transfer unit states */
 137#define XFER_UNKNOWN    0x00
 138#define XFER_ERASING    0x01
 139#define XFER_ERASED     0x02
 140#define XFER_PREPARED   0x03
 141#define XFER_FAILED     0x04
 142
 143/*====================================================================*/
 144
 145
 146static void ftl_erase_callback(struct erase_info *done);
 147
 148
 149/*======================================================================
 150
 151    Scan_header() checks to see if a memory region contains an FTL
 152    partition.  build_maps() reads all the erase unit headers, builds
 153    the erase unit map, and then builds the virtual page map.
 154
 155======================================================================*/
 156
 157static int scan_header(partition_t *part)
 158{
 159    erase_unit_header_t header;
 160    loff_t offset, max_offset;
 161    size_t ret;
 162    int err;
 163    part->header.FormattedSize = 0;
 164    max_offset = (0x100000<part->mbd.mtd->size)?0x100000:part->mbd.mtd->size;
 165    /* Search first megabyte for a valid FTL header */
 166    for (offset = 0;
 167         (offset + sizeof(header)) < max_offset;
 168         offset += part->mbd.mtd->erasesize ? : 0x2000) {
 169
 170        err = mtd_read(part->mbd.mtd, offset, sizeof(header), &ret,
 171                       (unsigned char *)&header);
 172
 173        if (err)
 174            return err;
 175
 176        if (strcmp(header.DataOrgTuple+3, "FTL100") == 0) break;
 177    }
 178
 179    if (offset == max_offset) {
 180        printk(KERN_NOTICE "ftl_cs: FTL header not found.\n");
 181        return -ENOENT;
 182    }
 183    if (header.BlockSize != 9 ||
 184        (header.EraseUnitSize < 10) || (header.EraseUnitSize > 31) ||
 185        (header.NumTransferUnits >= le16_to_cpu(header.NumEraseUnits))) {
 186        printk(KERN_NOTICE "ftl_cs: FTL header corrupt!\n");
 187        return -1;
 188    }
 189    if ((1 << header.EraseUnitSize) != part->mbd.mtd->erasesize) {
 190        printk(KERN_NOTICE "ftl: FTL EraseUnitSize %x != MTD erasesize %x\n",
 191               1 << header.EraseUnitSize,part->mbd.mtd->erasesize);
 192        return -1;
 193    }
 194    part->header = header;
 195    return 0;
 196}
 197
 198static int build_maps(partition_t *part)
 199{
 200    erase_unit_header_t header;
 201    uint16_t xvalid, xtrans, i;
 202    unsigned blocks, j;
 203    int hdr_ok, ret = -1;
 204    ssize_t retval;
 205    loff_t offset;
 206
 207    /* Set up erase unit maps */
 208    part->DataUnits = le16_to_cpu(part->header.NumEraseUnits) -
 209        part->header.NumTransferUnits;
 210    part->EUNInfo = kmalloc(part->DataUnits * sizeof(struct eun_info_t),
 211                            GFP_KERNEL);
 212    if (!part->EUNInfo)
 213            goto out;
 214    for (i = 0; i < part->DataUnits; i++)
 215        part->EUNInfo[i].Offset = 0xffffffff;
 216    part->XferInfo =
 217        kmalloc(part->header.NumTransferUnits * sizeof(struct xfer_info_t),
 218                GFP_KERNEL);
 219    if (!part->XferInfo)
 220            goto out_EUNInfo;
 221
 222    xvalid = xtrans = 0;
 223    for (i = 0; i < le16_to_cpu(part->header.NumEraseUnits); i++) {
 224        offset = ((i + le16_to_cpu(part->header.FirstPhysicalEUN))
 225                      << part->header.EraseUnitSize);
 226        ret = mtd_read(part->mbd.mtd, offset, sizeof(header), &retval,
 227                       (unsigned char *)&header);
 228
 229        if (ret)
 230            goto out_XferInfo;
 231
 232        ret = -1;
 233        /* Is this a transfer partition? */
 234        hdr_ok = (strcmp(header.DataOrgTuple+3, "FTL100") == 0);
 235        if (hdr_ok && (le16_to_cpu(header.LogicalEUN) < part->DataUnits) &&
 236            (part->EUNInfo[le16_to_cpu(header.LogicalEUN)].Offset == 0xffffffff)) {
 237            part->EUNInfo[le16_to_cpu(header.LogicalEUN)].Offset = offset;
 238            part->EUNInfo[le16_to_cpu(header.LogicalEUN)].EraseCount =
 239                le32_to_cpu(header.EraseCount);
 240            xvalid++;
 241        } else {
 242            if (xtrans == part->header.NumTransferUnits) {
 243                printk(KERN_NOTICE "ftl_cs: format error: too many "
 244                       "transfer units!\n");
 245                goto out_XferInfo;
 246            }
 247            if (hdr_ok && (le16_to_cpu(header.LogicalEUN) == 0xffff)) {
 248                part->XferInfo[xtrans].state = XFER_PREPARED;
 249                part->XferInfo[xtrans].EraseCount = le32_to_cpu(header.EraseCount);
 250            } else {
 251                part->XferInfo[xtrans].state = XFER_UNKNOWN;
 252                /* Pick anything reasonable for the erase count */
 253                part->XferInfo[xtrans].EraseCount =
 254                    le32_to_cpu(part->header.EraseCount);
 255            }
 256            part->XferInfo[xtrans].Offset = offset;
 257            xtrans++;
 258        }
 259    }
 260    /* Check for format trouble */
 261    header = part->header;
 262    if ((xtrans != header.NumTransferUnits) ||
 263        (xvalid+xtrans != le16_to_cpu(header.NumEraseUnits))) {
 264        printk(KERN_NOTICE "ftl_cs: format error: erase units "
 265               "don't add up!\n");
 266        goto out_XferInfo;
 267    }
 268
 269    /* Set up virtual page map */
 270    blocks = le32_to_cpu(header.FormattedSize) >> header.BlockSize;
 271    part->VirtualBlockMap = vmalloc(blocks * sizeof(uint32_t));
 272    if (!part->VirtualBlockMap)
 273            goto out_XferInfo;
 274
 275    memset(part->VirtualBlockMap, 0xff, blocks * sizeof(uint32_t));
 276    part->BlocksPerUnit = (1 << header.EraseUnitSize) >> header.BlockSize;
 277
 278    part->bam_cache = kmalloc(part->BlocksPerUnit * sizeof(uint32_t),
 279                              GFP_KERNEL);
 280    if (!part->bam_cache)
 281            goto out_VirtualBlockMap;
 282
 283    part->bam_index = 0xffff;
 284    part->FreeTotal = 0;
 285
 286    for (i = 0; i < part->DataUnits; i++) {
 287        part->EUNInfo[i].Free = 0;
 288        part->EUNInfo[i].Deleted = 0;
 289        offset = part->EUNInfo[i].Offset + le32_to_cpu(header.BAMOffset);
 290
 291        ret = mtd_read(part->mbd.mtd, offset,
 292                       part->BlocksPerUnit * sizeof(uint32_t), &retval,
 293                       (unsigned char *)part->bam_cache);
 294
 295        if (ret)
 296                goto out_bam_cache;
 297
 298        for (j = 0; j < part->BlocksPerUnit; j++) {
 299            if (BLOCK_FREE(le32_to_cpu(part->bam_cache[j]))) {
 300                part->EUNInfo[i].Free++;
 301                part->FreeTotal++;
 302            } else if ((BLOCK_TYPE(le32_to_cpu(part->bam_cache[j])) == BLOCK_DATA) &&
 303                     (BLOCK_NUMBER(le32_to_cpu(part->bam_cache[j])) < blocks))
 304                part->VirtualBlockMap[BLOCK_NUMBER(le32_to_cpu(part->bam_cache[j]))] =
 305                    (i << header.EraseUnitSize) + (j << header.BlockSize);
 306            else if (BLOCK_DELETED(le32_to_cpu(part->bam_cache[j])))
 307                part->EUNInfo[i].Deleted++;
 308        }
 309    }
 310
 311    ret = 0;
 312    goto out;
 313
 314out_bam_cache:
 315    kfree(part->bam_cache);
 316out_VirtualBlockMap:
 317    vfree(part->VirtualBlockMap);
 318out_XferInfo:
 319    kfree(part->XferInfo);
 320out_EUNInfo:
 321    kfree(part->EUNInfo);
 322out:
 323    return ret;
 324} /* build_maps */
 325
 326/*======================================================================
 327
 328    Erase_xfer() schedules an asynchronous erase operation for a
 329    transfer unit.
 330
 331======================================================================*/
 332
 333static int erase_xfer(partition_t *part,
 334                      uint16_t xfernum)
 335{
 336    int ret;
 337    struct xfer_info_t *xfer;
 338    struct erase_info *erase;
 339
 340    xfer = &part->XferInfo[xfernum];
 341    pr_debug("ftl_cs: erasing xfer unit at 0x%x\n", xfer->Offset);
 342    xfer->state = XFER_ERASING;
 343
 344    /* Is there a free erase slot? Always in MTD. */
 345
 346
 347    erase=kmalloc(sizeof(struct erase_info), GFP_KERNEL);
 348    if (!erase)
 349            return -ENOMEM;
 350
 351    erase->mtd = part->mbd.mtd;
 352    erase->callback = ftl_erase_callback;
 353    erase->addr = xfer->Offset;
 354    erase->len = 1 << part->header.EraseUnitSize;
 355    erase->priv = (u_long)part;
 356
 357    ret = mtd_erase(part->mbd.mtd, erase);
 358
 359    if (!ret)
 360            xfer->EraseCount++;
 361    else
 362            kfree(erase);
 363
 364    return ret;
 365} /* erase_xfer */
 366
 367/*======================================================================
 368
 369    Prepare_xfer() takes a freshly erased transfer unit and gives
 370    it an appropriate header.
 371
 372======================================================================*/
 373
 374static void ftl_erase_callback(struct erase_info *erase)
 375{
 376    partition_t *part;
 377    struct xfer_info_t *xfer;
 378    int i;
 379
 380    /* Look up the transfer unit */
 381    part = (partition_t *)(erase->priv);
 382
 383    for (i = 0; i < part->header.NumTransferUnits; i++)
 384        if (part->XferInfo[i].Offset == erase->addr) break;
 385
 386    if (i == part->header.NumTransferUnits) {
 387        printk(KERN_NOTICE "ftl_cs: internal error: "
 388               "erase lookup failed!\n");
 389        return;
 390    }
 391
 392    xfer = &part->XferInfo[i];
 393    if (erase->state == MTD_ERASE_DONE)
 394        xfer->state = XFER_ERASED;
 395    else {
 396        xfer->state = XFER_FAILED;
 397        printk(KERN_NOTICE "ftl_cs: erase failed: state = %d\n",
 398               erase->state);
 399    }
 400
 401    kfree(erase);
 402
 403} /* ftl_erase_callback */
 404
 405static int prepare_xfer(partition_t *part, int i)
 406{
 407    erase_unit_header_t header;
 408    struct xfer_info_t *xfer;
 409    int nbam, ret;
 410    uint32_t ctl;
 411    ssize_t retlen;
 412    loff_t offset;
 413
 414    xfer = &part->XferInfo[i];
 415    xfer->state = XFER_FAILED;
 416
 417    pr_debug("ftl_cs: preparing xfer unit at 0x%x\n", xfer->Offset);
 418
 419    /* Write the transfer unit header */
 420    header = part->header;
 421    header.LogicalEUN = cpu_to_le16(0xffff);
 422    header.EraseCount = cpu_to_le32(xfer->EraseCount);
 423
 424    ret = mtd_write(part->mbd.mtd, xfer->Offset, sizeof(header), &retlen,
 425                    (u_char *)&header);
 426
 427    if (ret) {
 428        return ret;
 429    }
 430
 431    /* Write the BAM stub */
 432    nbam = (part->BlocksPerUnit * sizeof(uint32_t) +
 433            le32_to_cpu(part->header.BAMOffset) + SECTOR_SIZE - 1) / SECTOR_SIZE;
 434
 435    offset = xfer->Offset + le32_to_cpu(part->header.BAMOffset);
 436    ctl = cpu_to_le32(BLOCK_CONTROL);
 437
 438    for (i = 0; i < nbam; i++, offset += sizeof(uint32_t)) {
 439
 440        ret = mtd_write(part->mbd.mtd, offset, sizeof(uint32_t), &retlen,
 441                        (u_char *)&ctl);
 442
 443        if (ret)
 444            return ret;
 445    }
 446    xfer->state = XFER_PREPARED;
 447    return 0;
 448
 449} /* prepare_xfer */
 450
 451/*======================================================================
 452
 453    Copy_erase_unit() takes a full erase block and a transfer unit,
 454    copies everything to the transfer unit, then swaps the block
 455    pointers.
 456
 457    All data blocks are copied to the corresponding blocks in the
 458    target unit, so the virtual block map does not need to be
 459    updated.
 460
 461======================================================================*/
 462
 463static int copy_erase_unit(partition_t *part, uint16_t srcunit,
 464                           uint16_t xferunit)
 465{
 466    u_char buf[SECTOR_SIZE];
 467    struct eun_info_t *eun;
 468    struct xfer_info_t *xfer;
 469    uint32_t src, dest, free, i;
 470    uint16_t unit;
 471    int ret;
 472    ssize_t retlen;
 473    loff_t offset;
 474    uint16_t srcunitswap = cpu_to_le16(srcunit);
 475
 476    eun = &part->EUNInfo[srcunit];
 477    xfer = &part->XferInfo[xferunit];
 478    pr_debug("ftl_cs: copying block 0x%x to 0x%x\n",
 479          eun->Offset, xfer->Offset);
 480
 481
 482    /* Read current BAM */
 483    if (part->bam_index != srcunit) {
 484
 485        offset = eun->Offset + le32_to_cpu(part->header.BAMOffset);
 486
 487        ret = mtd_read(part->mbd.mtd, offset,
 488                       part->BlocksPerUnit * sizeof(uint32_t), &retlen,
 489                       (u_char *)(part->bam_cache));
 490
 491        /* mark the cache bad, in case we get an error later */
 492        part->bam_index = 0xffff;
 493
 494        if (ret) {
 495            printk( KERN_WARNING "ftl: Failed to read BAM cache in copy_erase_unit()!\n");
 496            return ret;
 497        }
 498    }
 499
 500    /* Write the LogicalEUN for the transfer unit */
 501    xfer->state = XFER_UNKNOWN;
 502    offset = xfer->Offset + 20; /* Bad! */
 503    unit = cpu_to_le16(0x7fff);
 504
 505    ret = mtd_write(part->mbd.mtd, offset, sizeof(uint16_t), &retlen,
 506                    (u_char *)&unit);
 507
 508    if (ret) {
 509        printk( KERN_WARNING "ftl: Failed to write back to BAM cache in copy_erase_unit()!\n");
 510        return ret;
 511    }
 512
 513    /* Copy all data blocks from source unit to transfer unit */
 514    src = eun->Offset; dest = xfer->Offset;
 515
 516    free = 0;
 517    ret = 0;
 518    for (i = 0; i < part->BlocksPerUnit; i++) {
 519        switch (BLOCK_TYPE(le32_to_cpu(part->bam_cache[i]))) {
 520        case BLOCK_CONTROL:
 521            /* This gets updated later */
 522            break;
 523        case BLOCK_DATA:
 524        case BLOCK_REPLACEMENT:
 525            ret = mtd_read(part->mbd.mtd, src, SECTOR_SIZE, &retlen,
 526                           (u_char *)buf);
 527            if (ret) {
 528                printk(KERN_WARNING "ftl: Error reading old xfer unit in copy_erase_unit\n");
 529                return ret;
 530            }
 531
 532
 533            ret = mtd_write(part->mbd.mtd, dest, SECTOR_SIZE, &retlen,
 534                            (u_char *)buf);
 535            if (ret)  {
 536                printk(KERN_WARNING "ftl: Error writing new xfer unit in copy_erase_unit\n");
 537                return ret;
 538            }
 539
 540            break;
 541        default:
 542            /* All other blocks must be free */
 543            part->bam_cache[i] = cpu_to_le32(0xffffffff);
 544            free++;
 545            break;
 546        }
 547        src += SECTOR_SIZE;
 548        dest += SECTOR_SIZE;
 549    }
 550
 551    /* Write the BAM to the transfer unit */
 552    ret = mtd_write(part->mbd.mtd,
 553                    xfer->Offset + le32_to_cpu(part->header.BAMOffset),
 554                    part->BlocksPerUnit * sizeof(int32_t),
 555                    &retlen,
 556                    (u_char *)part->bam_cache);
 557    if (ret) {
 558        printk( KERN_WARNING "ftl: Error writing BAM in copy_erase_unit\n");
 559        return ret;
 560    }
 561
 562
 563    /* All clear? Then update the LogicalEUN again */
 564    ret = mtd_write(part->mbd.mtd, xfer->Offset + 20, sizeof(uint16_t),
 565                    &retlen, (u_char *)&srcunitswap);
 566
 567    if (ret) {
 568        printk(KERN_WARNING "ftl: Error writing new LogicalEUN in copy_erase_unit\n");
 569        return ret;
 570    }
 571
 572
 573    /* Update the maps and usage stats*/
 574    swap(xfer->EraseCount, eun->EraseCount);
 575    swap(xfer->Offset, eun->Offset);
 576    part->FreeTotal -= eun->Free;
 577    part->FreeTotal += free;
 578    eun->Free = free;
 579    eun->Deleted = 0;
 580
 581    /* Now, the cache should be valid for the new block */
 582    part->bam_index = srcunit;
 583
 584    return 0;
 585} /* copy_erase_unit */
 586
 587/*======================================================================
 588
 589    reclaim_block() picks a full erase unit and a transfer unit and
 590    then calls copy_erase_unit() to copy one to the other.  Then, it
 591    schedules an erase on the expired block.
 592
 593    What's a good way to decide which transfer unit and which erase
 594    unit to use?  Beats me.  My way is to always pick the transfer
 595    unit with the fewest erases, and usually pick the data unit with
 596    the most deleted blocks.  But with a small probability, pick the
 597    oldest data unit instead.  This means that we generally postpone
 598    the next reclamation as long as possible, but shuffle static
 599    stuff around a bit for wear leveling.
 600
 601======================================================================*/
 602
 603static int reclaim_block(partition_t *part)
 604{
 605    uint16_t i, eun, xfer;
 606    uint32_t best;
 607    int queued, ret;
 608
 609    pr_debug("ftl_cs: reclaiming space...\n");
 610    pr_debug("NumTransferUnits == %x\n", part->header.NumTransferUnits);
 611    /* Pick the least erased transfer unit */
 612    best = 0xffffffff; xfer = 0xffff;
 613    do {
 614        queued = 0;
 615        for (i = 0; i < part->header.NumTransferUnits; i++) {
 616            int n=0;
 617            if (part->XferInfo[i].state == XFER_UNKNOWN) {
 618                pr_debug("XferInfo[%d].state == XFER_UNKNOWN\n",i);
 619                n=1;
 620                erase_xfer(part, i);
 621            }
 622            if (part->XferInfo[i].state == XFER_ERASING) {
 623                pr_debug("XferInfo[%d].state == XFER_ERASING\n",i);
 624                n=1;
 625                queued = 1;
 626            }
 627            else if (part->XferInfo[i].state == XFER_ERASED) {
 628                pr_debug("XferInfo[%d].state == XFER_ERASED\n",i);
 629                n=1;
 630                prepare_xfer(part, i);
 631            }
 632            if (part->XferInfo[i].state == XFER_PREPARED) {
 633                pr_debug("XferInfo[%d].state == XFER_PREPARED\n",i);
 634                n=1;
 635                if (part->XferInfo[i].EraseCount <= best) {
 636                    best = part->XferInfo[i].EraseCount;
 637                    xfer = i;
 638                }
 639            }
 640                if (!n)
 641                    pr_debug("XferInfo[%d].state == %x\n",i, part->XferInfo[i].state);
 642
 643        }
 644        if (xfer == 0xffff) {
 645            if (queued) {
 646                pr_debug("ftl_cs: waiting for transfer "
 647                      "unit to be prepared...\n");
 648                mtd_sync(part->mbd.mtd);
 649            } else {
 650                static int ne = 0;
 651                if (++ne < 5)
 652                    printk(KERN_NOTICE "ftl_cs: reclaim failed: no "
 653                           "suitable transfer units!\n");
 654                else
 655                    pr_debug("ftl_cs: reclaim failed: no "
 656                          "suitable transfer units!\n");
 657
 658                return -EIO;
 659            }
 660        }
 661    } while (xfer == 0xffff);
 662
 663    eun = 0;
 664    if ((jiffies % shuffle_freq) == 0) {
 665        pr_debug("ftl_cs: recycling freshest block...\n");
 666        best = 0xffffffff;
 667        for (i = 0; i < part->DataUnits; i++)
 668            if (part->EUNInfo[i].EraseCount <= best) {
 669                best = part->EUNInfo[i].EraseCount;
 670                eun = i;
 671            }
 672    } else {
 673        best = 0;
 674        for (i = 0; i < part->DataUnits; i++)
 675            if (part->EUNInfo[i].Deleted >= best) {
 676                best = part->EUNInfo[i].Deleted;
 677                eun = i;
 678            }
 679        if (best == 0) {
 680            static int ne = 0;
 681            if (++ne < 5)
 682                printk(KERN_NOTICE "ftl_cs: reclaim failed: "
 683                       "no free blocks!\n");
 684            else
 685                pr_debug("ftl_cs: reclaim failed: "
 686                       "no free blocks!\n");
 687
 688            return -EIO;
 689        }
 690    }
 691    ret = copy_erase_unit(part, eun, xfer);
 692    if (!ret)
 693        erase_xfer(part, xfer);
 694    else
 695        printk(KERN_NOTICE "ftl_cs: copy_erase_unit failed!\n");
 696    return ret;
 697} /* reclaim_block */
 698
 699/*======================================================================
 700
 701    Find_free() searches for a free block.  If necessary, it updates
 702    the BAM cache for the erase unit containing the free block.  It
 703    returns the block index -- the erase unit is just the currently
 704    cached unit.  If there are no free blocks, it returns 0 -- this
 705    is never a valid data block because it contains the header.
 706
 707======================================================================*/
 708
 709#ifdef PSYCHO_DEBUG
 710static void dump_lists(partition_t *part)
 711{
 712    int i;
 713    printk(KERN_DEBUG "ftl_cs: Free total = %d\n", part->FreeTotal);
 714    for (i = 0; i < part->DataUnits; i++)
 715        printk(KERN_DEBUG "ftl_cs:   unit %d: %d phys, %d free, "
 716               "%d deleted\n", i,
 717               part->EUNInfo[i].Offset >> part->header.EraseUnitSize,
 718               part->EUNInfo[i].Free, part->EUNInfo[i].Deleted);
 719}
 720#endif
 721
 722static uint32_t find_free(partition_t *part)
 723{
 724    uint16_t stop, eun;
 725    uint32_t blk;
 726    size_t retlen;
 727    int ret;
 728
 729    /* Find an erase unit with some free space */
 730    stop = (part->bam_index == 0xffff) ? 0 : part->bam_index;
 731    eun = stop;
 732    do {
 733        if (part->EUNInfo[eun].Free != 0) break;
 734        /* Wrap around at end of table */
 735        if (++eun == part->DataUnits) eun = 0;
 736    } while (eun != stop);
 737
 738    if (part->EUNInfo[eun].Free == 0)
 739        return 0;
 740
 741    /* Is this unit's BAM cached? */
 742    if (eun != part->bam_index) {
 743        /* Invalidate cache */
 744        part->bam_index = 0xffff;
 745
 746        ret = mtd_read(part->mbd.mtd,
 747                       part->EUNInfo[eun].Offset + le32_to_cpu(part->header.BAMOffset),
 748                       part->BlocksPerUnit * sizeof(uint32_t),
 749                       &retlen,
 750                       (u_char *)(part->bam_cache));
 751
 752        if (ret) {
 753            printk(KERN_WARNING"ftl: Error reading BAM in find_free\n");
 754            return 0;
 755        }
 756        part->bam_index = eun;
 757    }
 758
 759    /* Find a free block */
 760    for (blk = 0; blk < part->BlocksPerUnit; blk++)
 761        if (BLOCK_FREE(le32_to_cpu(part->bam_cache[blk]))) break;
 762    if (blk == part->BlocksPerUnit) {
 763#ifdef PSYCHO_DEBUG
 764        static int ne = 0;
 765        if (++ne == 1)
 766            dump_lists(part);
 767#endif
 768        printk(KERN_NOTICE "ftl_cs: bad free list!\n");
 769        return 0;
 770    }
 771    pr_debug("ftl_cs: found free block at %d in %d\n", blk, eun);
 772    return blk;
 773
 774} /* find_free */
 775
 776
 777/*======================================================================
 778
 779    Read a series of sectors from an FTL partition.
 780
 781======================================================================*/
 782
 783static int ftl_read(partition_t *part, caddr_t buffer,
 784                    u_long sector, u_long nblocks)
 785{
 786    uint32_t log_addr, bsize;
 787    u_long i;
 788    int ret;
 789    size_t offset, retlen;
 790
 791    pr_debug("ftl_cs: ftl_read(0x%p, 0x%lx, %ld)\n",
 792          part, sector, nblocks);
 793    if (!(part->state & FTL_FORMATTED)) {
 794        printk(KERN_NOTICE "ftl_cs: bad partition\n");
 795        return -EIO;
 796    }
 797    bsize = 1 << part->header.EraseUnitSize;
 798
 799    for (i = 0; i < nblocks; i++) {
 800        if (((sector+i) * SECTOR_SIZE) >= le32_to_cpu(part->header.FormattedSize)) {
 801            printk(KERN_NOTICE "ftl_cs: bad read offset\n");
 802            return -EIO;
 803        }
 804        log_addr = part->VirtualBlockMap[sector+i];
 805        if (log_addr == 0xffffffff)
 806            memset(buffer, 0, SECTOR_SIZE);
 807        else {
 808            offset = (part->EUNInfo[log_addr / bsize].Offset
 809                          + (log_addr % bsize));
 810            ret = mtd_read(part->mbd.mtd, offset, SECTOR_SIZE, &retlen,
 811                           (u_char *)buffer);
 812
 813            if (ret) {
 814                printk(KERN_WARNING "Error reading MTD device in ftl_read()\n");
 815                return ret;
 816            }
 817        }
 818        buffer += SECTOR_SIZE;
 819    }
 820    return 0;
 821} /* ftl_read */
 822
 823/*======================================================================
 824
 825    Write a series of sectors to an FTL partition
 826
 827======================================================================*/
 828
 829static int set_bam_entry(partition_t *part, uint32_t log_addr,
 830                         uint32_t virt_addr)
 831{
 832    uint32_t bsize, blk, le_virt_addr;
 833#ifdef PSYCHO_DEBUG
 834    uint32_t old_addr;
 835#endif
 836    uint16_t eun;
 837    int ret;
 838    size_t retlen, offset;
 839
 840    pr_debug("ftl_cs: set_bam_entry(0x%p, 0x%x, 0x%x)\n",
 841          part, log_addr, virt_addr);
 842    bsize = 1 << part->header.EraseUnitSize;
 843    eun = log_addr / bsize;
 844    blk = (log_addr % bsize) / SECTOR_SIZE;
 845    offset = (part->EUNInfo[eun].Offset + blk * sizeof(uint32_t) +
 846                  le32_to_cpu(part->header.BAMOffset));
 847
 848#ifdef PSYCHO_DEBUG
 849    ret = mtd_read(part->mbd.mtd, offset, sizeof(uint32_t), &retlen,
 850                   (u_char *)&old_addr);
 851    if (ret) {
 852        printk(KERN_WARNING"ftl: Error reading old_addr in set_bam_entry: %d\n",ret);
 853        return ret;
 854    }
 855    old_addr = le32_to_cpu(old_addr);
 856
 857    if (((virt_addr == 0xfffffffe) && !BLOCK_FREE(old_addr)) ||
 858        ((virt_addr == 0) && (BLOCK_TYPE(old_addr) != BLOCK_DATA)) ||
 859        (!BLOCK_DELETED(virt_addr) && (old_addr != 0xfffffffe))) {
 860        static int ne = 0;
 861        if (++ne < 5) {
 862            printk(KERN_NOTICE "ftl_cs: set_bam_entry() inconsistency!\n");
 863            printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, old = 0x%x"
 864                   ", new = 0x%x\n", log_addr, old_addr, virt_addr);
 865        }
 866        return -EIO;
 867    }
 868#endif
 869    le_virt_addr = cpu_to_le32(virt_addr);
 870    if (part->bam_index == eun) {
 871#ifdef PSYCHO_DEBUG
 872        if (le32_to_cpu(part->bam_cache[blk]) != old_addr) {
 873            static int ne = 0;
 874            if (++ne < 5) {
 875                printk(KERN_NOTICE "ftl_cs: set_bam_entry() "
 876                       "inconsistency!\n");
 877                printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, cache"
 878                       " = 0x%x\n",
 879                       le32_to_cpu(part->bam_cache[blk]), old_addr);
 880            }
 881            return -EIO;
 882        }
 883#endif
 884        part->bam_cache[blk] = le_virt_addr;
 885    }
 886    ret = mtd_write(part->mbd.mtd, offset, sizeof(uint32_t), &retlen,
 887                    (u_char *)&le_virt_addr);
 888
 889    if (ret) {
 890        printk(KERN_NOTICE "ftl_cs: set_bam_entry() failed!\n");
 891        printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, new = 0x%x\n",
 892               log_addr, virt_addr);
 893    }
 894    return ret;
 895} /* set_bam_entry */
 896
 897static int ftl_write(partition_t *part, caddr_t buffer,
 898                     u_long sector, u_long nblocks)
 899{
 900    uint32_t bsize, log_addr, virt_addr, old_addr, blk;
 901    u_long i;
 902    int ret;
 903    size_t retlen, offset;
 904
 905    pr_debug("ftl_cs: ftl_write(0x%p, %ld, %ld)\n",
 906          part, sector, nblocks);
 907    if (!(part->state & FTL_FORMATTED)) {
 908        printk(KERN_NOTICE "ftl_cs: bad partition\n");
 909        return -EIO;
 910    }
 911    /* See if we need to reclaim space, before we start */
 912    while (part->FreeTotal < nblocks) {
 913        ret = reclaim_block(part);
 914        if (ret)
 915            return ret;
 916    }
 917
 918    bsize = 1 << part->header.EraseUnitSize;
 919
 920    virt_addr = sector * SECTOR_SIZE | BLOCK_DATA;
 921    for (i = 0; i < nblocks; i++) {
 922        if (virt_addr >= le32_to_cpu(part->header.FormattedSize)) {
 923            printk(KERN_NOTICE "ftl_cs: bad write offset\n");
 924            return -EIO;
 925        }
 926
 927        /* Grab a free block */
 928        blk = find_free(part);
 929        if (blk == 0) {
 930            static int ne = 0;
 931            if (++ne < 5)
 932                printk(KERN_NOTICE "ftl_cs: internal error: "
 933                       "no free blocks!\n");
 934            return -ENOSPC;
 935        }
 936
 937        /* Tag the BAM entry, and write the new block */
 938        log_addr = part->bam_index * bsize + blk * SECTOR_SIZE;
 939        part->EUNInfo[part->bam_index].Free--;
 940        part->FreeTotal--;
 941        if (set_bam_entry(part, log_addr, 0xfffffffe))
 942            return -EIO;
 943        part->EUNInfo[part->bam_index].Deleted++;
 944        offset = (part->EUNInfo[part->bam_index].Offset +
 945                      blk * SECTOR_SIZE);
 946        ret = mtd_write(part->mbd.mtd, offset, SECTOR_SIZE, &retlen, buffer);
 947
 948        if (ret) {
 949            printk(KERN_NOTICE "ftl_cs: block write failed!\n");
 950            printk(KERN_NOTICE "ftl_cs:   log_addr = 0x%x, virt_addr"
 951                   " = 0x%x, Offset = 0x%zx\n", log_addr, virt_addr,
 952                   offset);
 953            return -EIO;
 954        }
 955
 956        /* Only delete the old entry when the new entry is ready */
 957        old_addr = part->VirtualBlockMap[sector+i];
 958        if (old_addr != 0xffffffff) {
 959            part->VirtualBlockMap[sector+i] = 0xffffffff;
 960            part->EUNInfo[old_addr/bsize].Deleted++;
 961            if (set_bam_entry(part, old_addr, 0))
 962                return -EIO;
 963        }
 964
 965        /* Finally, set up the new pointers */
 966        if (set_bam_entry(part, log_addr, virt_addr))
 967            return -EIO;
 968        part->VirtualBlockMap[sector+i] = log_addr;
 969        part->EUNInfo[part->bam_index].Deleted--;
 970
 971        buffer += SECTOR_SIZE;
 972        virt_addr += SECTOR_SIZE;
 973    }
 974    return 0;
 975} /* ftl_write */
 976
 977static int ftl_getgeo(struct mtd_blktrans_dev *dev, struct hd_geometry *geo)
 978{
 979        partition_t *part = (void *)dev;
 980        u_long sect;
 981
 982        /* Sort of arbitrary: round size down to 4KiB boundary */
 983        sect = le32_to_cpu(part->header.FormattedSize)/SECTOR_SIZE;
 984
 985        geo->heads = 1;
 986        geo->sectors = 8;
 987        geo->cylinders = sect >> 3;
 988
 989        return 0;
 990}
 991
 992static int ftl_readsect(struct mtd_blktrans_dev *dev,
 993                              unsigned long block, char *buf)
 994{
 995        return ftl_read((void *)dev, buf, block, 1);
 996}
 997
 998static int ftl_writesect(struct mtd_blktrans_dev *dev,
 999                              unsigned long block, char *buf)
1000{
1001        return ftl_write((void *)dev, buf, block, 1);
1002}
1003
1004static int ftl_discardsect(struct mtd_blktrans_dev *dev,
1005                           unsigned long sector, unsigned nr_sects)
1006{
1007        partition_t *part = (void *)dev;
1008        uint32_t bsize = 1 << part->header.EraseUnitSize;
1009
1010        pr_debug("FTL erase sector %ld for %d sectors\n",
1011              sector, nr_sects);
1012
1013        while (nr_sects) {
1014                uint32_t old_addr = part->VirtualBlockMap[sector];
1015                if (old_addr != 0xffffffff) {
1016                        part->VirtualBlockMap[sector] = 0xffffffff;
1017                        part->EUNInfo[old_addr/bsize].Deleted++;
1018                        if (set_bam_entry(part, old_addr, 0))
1019                                return -EIO;
1020                }
1021                nr_sects--;
1022                sector++;
1023        }
1024
1025        return 0;
1026}
1027/*====================================================================*/
1028
1029static void ftl_freepart(partition_t *part)
1030{
1031        vfree(part->VirtualBlockMap);
1032        part->VirtualBlockMap = NULL;
1033        kfree(part->EUNInfo);
1034        part->EUNInfo = NULL;
1035        kfree(part->XferInfo);
1036        part->XferInfo = NULL;
1037        kfree(part->bam_cache);
1038        part->bam_cache = NULL;
1039} /* ftl_freepart */
1040
1041static void ftl_add_mtd(struct mtd_blktrans_ops *tr, struct mtd_info *mtd)
1042{
1043        partition_t *partition;
1044
1045        partition = kzalloc(sizeof(partition_t), GFP_KERNEL);
1046
1047        if (!partition) {
1048                printk(KERN_WARNING "No memory to scan for FTL on %s\n",
1049                       mtd->name);
1050                return;
1051        }
1052
1053        partition->mbd.mtd = mtd;
1054
1055        if ((scan_header(partition) == 0) &&
1056            (build_maps(partition) == 0)) {
1057
1058                partition->state = FTL_FORMATTED;
1059#ifdef PCMCIA_DEBUG
1060                printk(KERN_INFO "ftl_cs: opening %d KiB FTL partition\n",
1061                       le32_to_cpu(partition->header.FormattedSize) >> 10);
1062#endif
1063                partition->mbd.size = le32_to_cpu(partition->header.FormattedSize) >> 9;
1064
1065                partition->mbd.tr = tr;
1066                partition->mbd.devnum = -1;
1067                if (!add_mtd_blktrans_dev((void *)partition))
1068                        return;
1069        }
1070
1071        kfree(partition);
1072}
1073
1074static void ftl_remove_dev(struct mtd_blktrans_dev *dev)
1075{
1076        del_mtd_blktrans_dev(dev);
1077        ftl_freepart((partition_t *)dev);
1078}
1079
1080static struct mtd_blktrans_ops ftl_tr = {
1081        .name           = "ftl",
1082        .major          = FTL_MAJOR,
1083        .part_bits      = PART_BITS,
1084        .blksize        = SECTOR_SIZE,
1085        .readsect       = ftl_readsect,
1086        .writesect      = ftl_writesect,
1087        .discard        = ftl_discardsect,
1088        .getgeo         = ftl_getgeo,
1089        .add_mtd        = ftl_add_mtd,
1090        .remove_dev     = ftl_remove_dev,
1091        .owner          = THIS_MODULE,
1092};
1093
1094static int __init init_ftl(void)
1095{
1096        return register_mtd_blktrans(&ftl_tr);
1097}
1098
1099static void __exit cleanup_ftl(void)
1100{
1101        deregister_mtd_blktrans(&ftl_tr);
1102}
1103
1104module_init(init_ftl);
1105module_exit(cleanup_ftl);
1106
1107
1108MODULE_LICENSE("Dual MPL/GPL");
1109MODULE_AUTHOR("David Hinds <dahinds@users.sourceforge.net>");
1110MODULE_DESCRIPTION("Support code for Flash Translation Layer, used on PCMCIA devices");
1111