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