drivers/mtd/ftl.c

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