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