drivers/mtd/ftl.c

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