drivers/mtd/ftl.c

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