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