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