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