drivers/mtd/ftl.c

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