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