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