drivers/mtd/ftl.c

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