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