[PATCH] remove many unneeded #includes of sched.h
[linux-2.6] / drivers / mtd / ftl.c
1 /* This version ported to the Linux-MTD system by dwmw2@infradead.org
2  * $Id: ftl.c,v 1.59 2005/11/29 14:48:31 gleixner Exp $
3  *
4  * Fixes: Arnaldo Carvalho de Melo <acme@conectiva.com.br>
5  * - fixes some leaks on failure in build_maps and ftl_notify_add, cleanups
6  *
7  * Based on:
8  */
9 /*======================================================================
10
11     A Flash Translation Layer memory card driver
12
13     This driver implements a disk-like block device driver with an
14     apparent block size of 512 bytes for flash memory cards.
15
16     ftl_cs.c 1.62 2000/02/01 00:59:04
17
18     The contents of this file are subject to the Mozilla Public
19     License Version 1.1 (the "License"); you may not use this file
20     except in compliance with the License. You may obtain a copy of
21     the License at http://www.mozilla.org/MPL/
22
23     Software distributed under the License is distributed on an "AS
24     IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
25     implied. See the License for the specific language governing
26     rights and limitations under the License.
27
28     The initial developer of the original code is David A. Hinds
29     <dahinds@users.sourceforge.net>.  Portions created by David A. Hinds
30     are Copyright (C) 1999 David A. Hinds.  All Rights Reserved.
31
32     Alternatively, the contents of this file may be used under the
33     terms of the GNU General Public License version 2 (the "GPL"), in
34     which case the provisions of the GPL are applicable instead of the
35     above.  If you wish to allow the use of your version of this file
36     only under the terms of the GPL and not to allow others to use
37     your version of this file under the MPL, indicate your decision
38     by deleting the provisions above and replace them with the notice
39     and other provisions required by the GPL.  If you do not delete
40     the provisions above, a recipient may use your version of this
41     file under either the MPL or the GPL.
42
43     LEGAL NOTE: The FTL format is patented by M-Systems.  They have
44     granted a license for its use with PCMCIA devices:
45
46      "M-Systems grants a royalty-free, non-exclusive license under
47       any presently existing M-Systems intellectual property rights
48       necessary for the design and development of FTL-compatible
49       drivers, file systems and utilities using the data formats with
50       PCMCIA PC Cards as described in the PCMCIA Flash Translation
51       Layer (FTL) Specification."
52
53     Use of the FTL format for non-PCMCIA applications may be an
54     infringement of these patents.  For additional information,
55     contact M-Systems (http://www.m-sys.com) directly.
56
57 ======================================================================*/
58 #include <linux/mtd/blktrans.h>
59 #include <linux/module.h>
60 #include <linux/mtd/mtd.h>
61 /*#define PSYCHO_DEBUG */
62
63 #include <linux/kernel.h>
64 #include <linux/ptrace.h>
65 #include <linux/slab.h>
66 #include <linux/string.h>
67 #include <linux/timer.h>
68 #include <linux/major.h>
69 #include <linux/fs.h>
70 #include <linux/init.h>
71 #include <linux/hdreg.h>
72 #include <linux/vmalloc.h>
73 #include <linux/blkpg.h>
74 #include <asm/uaccess.h>
75
76 #include <linux/mtd/ftl.h>
77
78 /*====================================================================*/
79
80 /* Parameters that can be set with 'insmod' */
81 static int shuffle_freq = 50;
82 module_param(shuffle_freq, int, 0);
83
84 /*====================================================================*/
85
86 /* Major device # for FTL device */
87 #ifndef FTL_MAJOR
88 #define FTL_MAJOR       44
89 #endif
90
91
92 /*====================================================================*/
93
94 /* Maximum number of separate memory devices we'll allow */
95 #define MAX_DEV         4
96
97 /* Maximum number of regions per device */
98 #define MAX_REGION      4
99
100 /* Maximum number of partitions in an FTL region */
101 #define PART_BITS       4
102
103 /* Maximum number of outstanding erase requests per socket */
104 #define MAX_ERASE       8
105
106 /* Sector size -- shouldn't need to change */
107 #define SECTOR_SIZE     512
108
109
110 /* Each memory region corresponds to a minor device */
111 typedef struct partition_t {
112     struct mtd_blktrans_dev mbd;
113     u_int32_t           state;
114     u_int32_t           *VirtualBlockMap;
115     u_int32_t           *VirtualPageMap;
116     u_int32_t           FreeTotal;
117     struct eun_info_t {
118         u_int32_t               Offset;
119         u_int32_t               EraseCount;
120         u_int32_t               Free;
121         u_int32_t               Deleted;
122     } *EUNInfo;
123     struct xfer_info_t {
124         u_int32_t               Offset;
125         u_int32_t               EraseCount;
126         u_int16_t               state;
127     } *XferInfo;
128     u_int16_t           bam_index;
129     u_int32_t           *bam_cache;
130     u_int16_t           DataUnits;
131     u_int32_t           BlocksPerUnit;
132     erase_unit_header_t header;
133 #if 0
134     region_info_t       region;
135     memory_handle_t     handle;
136 #endif
137 } partition_t;
138
139 void ftl_freepart(partition_t *part);
140
141 /* Partition state flags */
142 #define FTL_FORMATTED   0x01
143
144 /* Transfer unit states */
145 #define XFER_UNKNOWN    0x00
146 #define XFER_ERASING    0x01
147 #define XFER_ERASED     0x02
148 #define XFER_PREPARED   0x03
149 #define XFER_FAILED     0x04
150
151 /*====================================================================*/
152
153
154 static void ftl_erase_callback(struct erase_info *done);
155
156
157 /*======================================================================
158
159     Scan_header() checks to see if a memory region contains an FTL
160     partition.  build_maps() reads all the erase unit headers, builds
161     the erase unit map, and then builds the virtual page map.
162
163 ======================================================================*/
164
165 static int scan_header(partition_t *part)
166 {
167     erase_unit_header_t header;
168     loff_t offset, max_offset;
169     size_t ret;
170     int err;
171     part->header.FormattedSize = 0;
172     max_offset = (0x100000<part->mbd.mtd->size)?0x100000:part->mbd.mtd->size;
173     /* Search first megabyte for a valid FTL header */
174     for (offset = 0;
175          (offset + sizeof(header)) < max_offset;
176          offset += part->mbd.mtd->erasesize ? : 0x2000) {
177
178         err = part->mbd.mtd->read(part->mbd.mtd, offset, sizeof(header), &ret,
179                               (unsigned char *)&header);
180
181         if (err)
182             return err;
183
184         if (strcmp(header.DataOrgTuple+3, "FTL100") == 0) break;
185     }
186
187     if (offset == max_offset) {
188         printk(KERN_NOTICE "ftl_cs: FTL header not found.\n");
189         return -ENOENT;
190     }
191     if (header.BlockSize != 9 ||
192         (header.EraseUnitSize < 10) || (header.EraseUnitSize > 31) ||
193         (header.NumTransferUnits >= le16_to_cpu(header.NumEraseUnits))) {
194         printk(KERN_NOTICE "ftl_cs: FTL header corrupt!\n");
195         return -1;
196     }
197     if ((1 << header.EraseUnitSize) != part->mbd.mtd->erasesize) {
198         printk(KERN_NOTICE "ftl: FTL EraseUnitSize %x != MTD erasesize %x\n",
199                1 << header.EraseUnitSize,part->mbd.mtd->erasesize);
200         return -1;
201     }
202     part->header = header;
203     return 0;
204 }
205
206 static int build_maps(partition_t *part)
207 {
208     erase_unit_header_t header;
209     u_int16_t xvalid, xtrans, i;
210     u_int blocks, j;
211     int hdr_ok, ret = -1;
212     ssize_t retval;
213     loff_t offset;
214
215     /* Set up erase unit maps */
216     part->DataUnits = le16_to_cpu(part->header.NumEraseUnits) -
217         part->header.NumTransferUnits;
218     part->EUNInfo = kmalloc(part->DataUnits * sizeof(struct eun_info_t),
219                             GFP_KERNEL);
220     if (!part->EUNInfo)
221             goto out;
222     for (i = 0; i < part->DataUnits; i++)
223         part->EUNInfo[i].Offset = 0xffffffff;
224     part->XferInfo =
225         kmalloc(part->header.NumTransferUnits * sizeof(struct xfer_info_t),
226                 GFP_KERNEL);
227     if (!part->XferInfo)
228             goto out_EUNInfo;
229
230     xvalid = xtrans = 0;
231     for (i = 0; i < le16_to_cpu(part->header.NumEraseUnits); i++) {
232         offset = ((i + le16_to_cpu(part->header.FirstPhysicalEUN))
233                       << part->header.EraseUnitSize);
234         ret = part->mbd.mtd->read(part->mbd.mtd, offset, sizeof(header), &retval,
235                               (unsigned char *)&header);
236
237         if (ret)
238             goto out_XferInfo;
239
240         ret = -1;
241         /* Is this a transfer partition? */
242         hdr_ok = (strcmp(header.DataOrgTuple+3, "FTL100") == 0);
243         if (hdr_ok && (le16_to_cpu(header.LogicalEUN) < part->DataUnits) &&
244             (part->EUNInfo[le16_to_cpu(header.LogicalEUN)].Offset == 0xffffffff)) {
245             part->EUNInfo[le16_to_cpu(header.LogicalEUN)].Offset = offset;
246             part->EUNInfo[le16_to_cpu(header.LogicalEUN)].EraseCount =
247                 le32_to_cpu(header.EraseCount);
248             xvalid++;
249         } else {
250             if (xtrans == part->header.NumTransferUnits) {
251                 printk(KERN_NOTICE "ftl_cs: format error: too many "
252                        "transfer units!\n");
253                 goto out_XferInfo;
254             }
255             if (hdr_ok && (le16_to_cpu(header.LogicalEUN) == 0xffff)) {
256                 part->XferInfo[xtrans].state = XFER_PREPARED;
257                 part->XferInfo[xtrans].EraseCount = le32_to_cpu(header.EraseCount);
258             } else {
259                 part->XferInfo[xtrans].state = XFER_UNKNOWN;
260                 /* Pick anything reasonable for the erase count */
261                 part->XferInfo[xtrans].EraseCount =
262                     le32_to_cpu(part->header.EraseCount);
263             }
264             part->XferInfo[xtrans].Offset = offset;
265             xtrans++;
266         }
267     }
268     /* Check for format trouble */
269     header = part->header;
270     if ((xtrans != header.NumTransferUnits) ||
271         (xvalid+xtrans != le16_to_cpu(header.NumEraseUnits))) {
272         printk(KERN_NOTICE "ftl_cs: format error: erase units "
273                "don't add up!\n");
274         goto out_XferInfo;
275     }
276
277     /* Set up virtual page map */
278     blocks = le32_to_cpu(header.FormattedSize) >> header.BlockSize;
279     part->VirtualBlockMap = vmalloc(blocks * sizeof(u_int32_t));
280     if (!part->VirtualBlockMap)
281             goto out_XferInfo;
282
283     memset(part->VirtualBlockMap, 0xff, blocks * sizeof(u_int32_t));
284     part->BlocksPerUnit = (1 << header.EraseUnitSize) >> header.BlockSize;
285
286     part->bam_cache = kmalloc(part->BlocksPerUnit * sizeof(u_int32_t),
287                               GFP_KERNEL);
288     if (!part->bam_cache)
289             goto out_VirtualBlockMap;
290
291     part->bam_index = 0xffff;
292     part->FreeTotal = 0;
293
294     for (i = 0; i < part->DataUnits; i++) {
295         part->EUNInfo[i].Free = 0;
296         part->EUNInfo[i].Deleted = 0;
297         offset = part->EUNInfo[i].Offset + le32_to_cpu(header.BAMOffset);
298
299         ret = part->mbd.mtd->read(part->mbd.mtd, offset,
300                               part->BlocksPerUnit * sizeof(u_int32_t), &retval,
301                               (unsigned char *)part->bam_cache);
302
303         if (ret)
304                 goto out_bam_cache;
305
306         for (j = 0; j < part->BlocksPerUnit; j++) {
307             if (BLOCK_FREE(le32_to_cpu(part->bam_cache[j]))) {
308                 part->EUNInfo[i].Free++;
309                 part->FreeTotal++;
310             } else if ((BLOCK_TYPE(le32_to_cpu(part->bam_cache[j])) == BLOCK_DATA) &&
311                      (BLOCK_NUMBER(le32_to_cpu(part->bam_cache[j])) < blocks))
312                 part->VirtualBlockMap[BLOCK_NUMBER(le32_to_cpu(part->bam_cache[j]))] =
313                     (i << header.EraseUnitSize) + (j << header.BlockSize);
314             else if (BLOCK_DELETED(le32_to_cpu(part->bam_cache[j])))
315                 part->EUNInfo[i].Deleted++;
316         }
317     }
318
319     ret = 0;
320     goto out;
321
322 out_bam_cache:
323     kfree(part->bam_cache);
324 out_VirtualBlockMap:
325     vfree(part->VirtualBlockMap);
326 out_XferInfo:
327     kfree(part->XferInfo);
328 out_EUNInfo:
329     kfree(part->EUNInfo);
330 out:
331     return ret;
332 } /* build_maps */
333
334 /*======================================================================
335
336     Erase_xfer() schedules an asynchronous erase operation for a
337     transfer unit.
338
339 ======================================================================*/
340
341 static int erase_xfer(partition_t *part,
342                       u_int16_t xfernum)
343 {
344     int ret;
345     struct xfer_info_t *xfer;
346     struct erase_info *erase;
347
348     xfer = &part->XferInfo[xfernum];
349     DEBUG(1, "ftl_cs: erasing xfer unit at 0x%x\n", xfer->Offset);
350     xfer->state = XFER_ERASING;
351
352     /* Is there a free erase slot? Always in MTD. */
353
354
355     erase=kmalloc(sizeof(struct erase_info), GFP_KERNEL);
356     if (!erase)
357             return -ENOMEM;
358
359     erase->mtd = part->mbd.mtd;
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         vfree(part->VirtualBlockMap);
1020         part->VirtualBlockMap = NULL;
1021         kfree(part->VirtualPageMap);
1022         part->VirtualPageMap = NULL;
1023         kfree(part->EUNInfo);
1024         part->EUNInfo = NULL;
1025         kfree(part->XferInfo);
1026         part->XferInfo = NULL;
1027         kfree(part->bam_cache);
1028         part->bam_cache = NULL;
1029 } /* ftl_freepart */
1030
1031 static void ftl_add_mtd(struct mtd_blktrans_ops *tr, struct mtd_info *mtd)
1032 {
1033         partition_t *partition;
1034
1035         partition = kzalloc(sizeof(partition_t), GFP_KERNEL);
1036
1037         if (!partition) {
1038                 printk(KERN_WARNING "No memory to scan for FTL on %s\n",
1039                        mtd->name);
1040                 return;
1041         }
1042
1043         partition->mbd.mtd = mtd;
1044
1045         if ((scan_header(partition) == 0) &&
1046             (build_maps(partition) == 0)) {
1047
1048                 partition->state = FTL_FORMATTED;
1049 #ifdef PCMCIA_DEBUG
1050                 printk(KERN_INFO "ftl_cs: opening %d KiB FTL partition\n",
1051                        le32_to_cpu(partition->header.FormattedSize) >> 10);
1052 #endif
1053                 partition->mbd.size = le32_to_cpu(partition->header.FormattedSize) >> 9;
1054
1055                 partition->mbd.tr = tr;
1056                 partition->mbd.devnum = -1;
1057                 if (!add_mtd_blktrans_dev((void *)partition))
1058                         return;
1059         }
1060
1061         ftl_freepart(partition);
1062         kfree(partition);
1063 }
1064
1065 static void ftl_remove_dev(struct mtd_blktrans_dev *dev)
1066 {
1067         del_mtd_blktrans_dev(dev);
1068         ftl_freepart((partition_t *)dev);
1069         kfree(dev);
1070 }
1071
1072 struct mtd_blktrans_ops ftl_tr = {
1073         .name           = "ftl",
1074         .major          = FTL_MAJOR,
1075         .part_bits      = PART_BITS,
1076         .blksize        = SECTOR_SIZE,
1077         .readsect       = ftl_readsect,
1078         .writesect      = ftl_writesect,
1079         .getgeo         = ftl_getgeo,
1080         .add_mtd        = ftl_add_mtd,
1081         .remove_dev     = ftl_remove_dev,
1082         .owner          = THIS_MODULE,
1083 };
1084
1085 static int init_ftl(void)
1086 {
1087         DEBUG(0, "$Id: ftl.c,v 1.59 2005/11/29 14:48:31 gleixner Exp $\n");
1088
1089         return register_mtd_blktrans(&ftl_tr);
1090 }
1091
1092 static void __exit cleanup_ftl(void)
1093 {
1094         deregister_mtd_blktrans(&ftl_tr);
1095 }
1096
1097 module_init(init_ftl);
1098 module_exit(cleanup_ftl);
1099
1100
1101 MODULE_LICENSE("Dual MPL/GPL");
1102 MODULE_AUTHOR("David Hinds <dahinds@users.sourceforge.net>");
1103 MODULE_DESCRIPTION("Support code for Flash Translation Layer, used on PCMCIA devices");