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