drivers/mtd/ftl.c

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