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