1 /* Linux driver for NAND Flash Translation Layer */
2 /* (c) 1999 Machine Vision Holdings, Inc. */
3 /* Author: David Woodhouse <dwmw2@infradead.org> */
6 The contents of this file are distributed under the GNU General
7 Public License version 2. The author places no additional
8 restrictions of any kind on it.
13 #include <linux/kernel.h>
14 #include <linux/module.h>
15 #include <asm/errno.h>
17 #include <asm/uaccess.h>
18 #include <linux/delay.h>
19 #include <linux/slab.h>
20 #include <linux/init.h>
21 #include <linux/hdreg.h>
23 #include <linux/kmod.h>
24 #include <linux/mtd/mtd.h>
25 #include <linux/mtd/nand.h>
26 #include <linux/mtd/nftl.h>
27 #include <linux/mtd/blktrans.h>
29 /* maximum number of loops while examining next block, to have a
30 chance to detect consistency problems (they should never happen
31 because of the checks done in the mounting */
33 #define MAX_LOOPS 10000
36 static void nftl_add_mtd(struct mtd_blktrans_ops *tr, struct mtd_info *mtd)
38 struct NFTLrecord *nftl;
41 if (mtd->type != MTD_NANDFLASH || mtd->size > UINT_MAX)
43 /* OK, this is moderately ugly. But probably safe. Alternatives? */
44 if (memcmp(mtd->name, "DiskOnChip", 10))
47 if (!mtd->block_isbad) {
49 "NFTL no longer supports the old DiskOnChip drivers loaded via docprobe.\n"
50 "Please use the new diskonchip driver under the NAND subsystem.\n");
54 DEBUG(MTD_DEBUG_LEVEL1, "NFTL: add_mtd for %s\n", mtd->name);
56 nftl = kzalloc(sizeof(struct NFTLrecord), GFP_KERNEL);
59 printk(KERN_WARNING "NFTL: out of memory for data structures\n");
64 nftl->mbd.devnum = -1;
68 if (NFTL_mount(nftl) < 0) {
69 printk(KERN_WARNING "NFTL: could not mount device\n");
74 /* OK, it's a new one. Set up all the data structures. */
76 /* Calculate geometry */
77 nftl->cylinders = 1024;
80 temp = nftl->cylinders * nftl->heads;
81 nftl->sectors = nftl->mbd.size / temp;
82 if (nftl->mbd.size % temp) {
84 temp = nftl->cylinders * nftl->sectors;
85 nftl->heads = nftl->mbd.size / temp;
87 if (nftl->mbd.size % temp) {
89 temp = nftl->heads * nftl->sectors;
90 nftl->cylinders = nftl->mbd.size / temp;
94 if (nftl->mbd.size != nftl->heads * nftl->cylinders * nftl->sectors) {
97 mbd.size == heads * cylinders * sectors
99 printk(KERN_WARNING "NFTL: cannot calculate a geometry to "
100 "match size of 0x%lx.\n", nftl->mbd.size);
101 printk(KERN_WARNING "NFTL: using C:%d H:%d S:%d "
102 "(== 0x%lx sects)\n",
103 nftl->cylinders, nftl->heads , nftl->sectors,
104 (long)nftl->cylinders * (long)nftl->heads *
105 (long)nftl->sectors );
108 if (add_mtd_blktrans_dev(&nftl->mbd)) {
109 kfree(nftl->ReplUnitTable);
110 kfree(nftl->EUNtable);
115 printk(KERN_INFO "NFTL: Found new nftl%c\n", nftl->mbd.devnum + 'a');
119 static void nftl_remove_dev(struct mtd_blktrans_dev *dev)
121 struct NFTLrecord *nftl = (void *)dev;
123 DEBUG(MTD_DEBUG_LEVEL1, "NFTL: remove_dev (i=%d)\n", dev->devnum);
125 del_mtd_blktrans_dev(dev);
126 kfree(nftl->ReplUnitTable);
127 kfree(nftl->EUNtable);
132 * Read oob data from flash
134 int nftl_read_oob(struct mtd_info *mtd, loff_t offs, size_t len,
135 size_t *retlen, uint8_t *buf)
137 struct mtd_oob_ops ops;
140 ops.mode = MTD_OOB_PLACE;
141 ops.ooboffs = offs & (mtd->writesize - 1);
146 res = mtd->read_oob(mtd, offs & ~(mtd->writesize - 1), &ops);
147 *retlen = ops.oobretlen;
152 * Write oob data to flash
154 int nftl_write_oob(struct mtd_info *mtd, loff_t offs, size_t len,
155 size_t *retlen, uint8_t *buf)
157 struct mtd_oob_ops ops;
160 ops.mode = MTD_OOB_PLACE;
161 ops.ooboffs = offs & (mtd->writesize - 1);
166 res = mtd->write_oob(mtd, offs & ~(mtd->writesize - 1), &ops);
167 *retlen = ops.oobretlen;
171 #ifdef CONFIG_NFTL_RW
174 * Write data and oob to flash
176 static int nftl_write(struct mtd_info *mtd, loff_t offs, size_t len,
177 size_t *retlen, uint8_t *buf, uint8_t *oob)
179 struct mtd_oob_ops ops;
182 ops.mode = MTD_OOB_PLACE;
184 ops.ooblen = mtd->oobsize;
189 res = mtd->write_oob(mtd, offs & ~(mtd->writesize - 1), &ops);
190 *retlen = ops.retlen;
194 /* Actual NFTL access routines */
195 /* NFTL_findfreeblock: Find a free Erase Unit on the NFTL partition. This function is used
196 * when the give Virtual Unit Chain
198 static u16 NFTL_findfreeblock(struct NFTLrecord *nftl, int desperate )
200 /* For a given Virtual Unit Chain: find or create a free block and
201 add it to the chain */
202 /* We're passed the number of the last EUN in the chain, to save us from
203 having to look it up again */
204 u16 pot = nftl->LastFreeEUN;
205 int silly = nftl->nb_blocks;
207 /* Normally, we force a fold to happen before we run out of free blocks completely */
208 if (!desperate && nftl->numfreeEUNs < 2) {
209 DEBUG(MTD_DEBUG_LEVEL1, "NFTL_findfreeblock: there are too few free EUNs\n");
213 /* Scan for a free block */
215 if (nftl->ReplUnitTable[pot] == BLOCK_FREE) {
216 nftl->LastFreeEUN = pot;
221 /* This will probably point to the MediaHdr unit itself,
222 right at the beginning of the partition. But that unit
223 (and the backup unit too) should have the UCI set
224 up so that it's not selected for overwriting */
225 if (++pot > nftl->lastEUN)
226 pot = le16_to_cpu(nftl->MediaHdr.FirstPhysicalEUN);
229 printk("Argh! No free blocks found! LastFreeEUN = %d, "
230 "FirstEUN = %d\n", nftl->LastFreeEUN,
231 le16_to_cpu(nftl->MediaHdr.FirstPhysicalEUN));
234 } while (pot != nftl->LastFreeEUN);
239 static u16 NFTL_foldchain (struct NFTLrecord *nftl, unsigned thisVUC, unsigned pendingblock )
241 struct mtd_info *mtd = nftl->mbd.mtd;
242 u16 BlockMap[MAX_SECTORS_PER_UNIT];
243 unsigned char BlockLastState[MAX_SECTORS_PER_UNIT];
244 unsigned char BlockFreeFound[MAX_SECTORS_PER_UNIT];
245 unsigned int thisEUN;
248 unsigned int targetEUN;
253 memset(BlockMap, 0xff, sizeof(BlockMap));
254 memset(BlockFreeFound, 0, sizeof(BlockFreeFound));
256 thisEUN = nftl->EUNtable[thisVUC];
258 if (thisEUN == BLOCK_NIL) {
259 printk(KERN_WARNING "Trying to fold non-existent "
260 "Virtual Unit Chain %d!\n", thisVUC);
264 /* Scan to find the Erase Unit which holds the actual data for each
265 512-byte block within the Chain.
268 targetEUN = BLOCK_NIL;
269 while (thisEUN <= nftl->lastEUN ) {
270 unsigned int status, foldmark;
273 for (block = 0; block < nftl->EraseSize / 512; block ++) {
274 nftl_read_oob(mtd, (thisEUN * nftl->EraseSize) +
275 (block * 512), 16 , &retlen,
278 foldmark = oob.u.c.FoldMark | oob.u.c.FoldMark1;
279 if (foldmark == FOLD_MARK_IN_PROGRESS) {
280 DEBUG(MTD_DEBUG_LEVEL1,
281 "Write Inhibited on EUN %d\n", thisEUN);
284 /* There's no other reason not to do inplace,
285 except ones that come later. So we don't need
286 to preserve inplace */
290 status = oob.b.Status | oob.b.Status1;
291 BlockLastState[block] = status;
295 BlockFreeFound[block] = 1;
299 if (!BlockFreeFound[block])
300 BlockMap[block] = thisEUN;
303 "SECTOR_USED found after SECTOR_FREE "
304 "in Virtual Unit Chain %d for block %d\n",
308 if (!BlockFreeFound[block])
309 BlockMap[block] = BLOCK_NIL;
312 "SECTOR_DELETED found after SECTOR_FREE "
313 "in Virtual Unit Chain %d for block %d\n",
320 printk("Unknown status for block %d in EUN %d: %x\n",
321 block, thisEUN, status);
326 printk(KERN_WARNING "Infinite loop in Virtual Unit Chain 0x%x\n",
331 thisEUN = nftl->ReplUnitTable[thisEUN];
335 /* We're being asked to be a fold-in-place. Check
336 that all blocks which actually have data associated
337 with them (i.e. BlockMap[block] != BLOCK_NIL) are
338 either already present or SECTOR_FREE in the target
339 block. If not, we're going to have to fold out-of-place
342 for (block = 0; block < nftl->EraseSize / 512 ; block++) {
343 if (BlockLastState[block] != SECTOR_FREE &&
344 BlockMap[block] != BLOCK_NIL &&
345 BlockMap[block] != targetEUN) {
346 DEBUG(MTD_DEBUG_LEVEL1, "Setting inplace to 0. VUC %d, "
347 "block %d was %x lastEUN, "
348 "and is in EUN %d (%s) %d\n",
349 thisVUC, block, BlockLastState[block],
351 BlockMap[block]== targetEUN ? "==" : "!=",
358 if (pendingblock >= (thisVUC * (nftl->EraseSize / 512)) &&
359 pendingblock < ((thisVUC + 1)* (nftl->EraseSize / 512)) &&
360 BlockLastState[pendingblock - (thisVUC * (nftl->EraseSize / 512))] !=
362 DEBUG(MTD_DEBUG_LEVEL1, "Pending write not free in EUN %d. "
363 "Folding out of place.\n", targetEUN);
369 DEBUG(MTD_DEBUG_LEVEL1, "Cannot fold Virtual Unit Chain %d in place. "
370 "Trying out-of-place\n", thisVUC);
371 /* We need to find a targetEUN to fold into. */
372 targetEUN = NFTL_findfreeblock(nftl, 1);
373 if (targetEUN == BLOCK_NIL) {
374 /* Ouch. Now we're screwed. We need to do a
375 fold-in-place of another chain to make room
376 for this one. We need a better way of selecting
377 which chain to fold, because makefreeblock will
378 only ask us to fold the same one again.
381 "NFTL_findfreeblock(desperate) returns 0xffff.\n");
385 /* We put a fold mark in the chain we are folding only if we
386 fold in place to help the mount check code. If we do not fold in
387 place, it is possible to find the valid chain by selecting the
389 oob.u.c.FoldMark = oob.u.c.FoldMark1 = cpu_to_le16(FOLD_MARK_IN_PROGRESS);
390 oob.u.c.unused = 0xffffffff;
391 nftl_write_oob(mtd, (nftl->EraseSize * targetEUN) + 2 * 512 + 8,
392 8, &retlen, (char *)&oob.u);
395 /* OK. We now know the location of every block in the Virtual Unit Chain,
396 and the Erase Unit into which we are supposed to be copying.
399 DEBUG(MTD_DEBUG_LEVEL1,"Folding chain %d into unit %d\n", thisVUC, targetEUN);
400 for (block = 0; block < nftl->EraseSize / 512 ; block++) {
401 unsigned char movebuf[512];
404 /* If it's in the target EUN already, or if it's pending write, do nothing */
405 if (BlockMap[block] == targetEUN ||
406 (pendingblock == (thisVUC * (nftl->EraseSize / 512) + block))) {
410 /* copy only in non free block (free blocks can only
411 happen in case of media errors or deleted blocks) */
412 if (BlockMap[block] == BLOCK_NIL)
415 ret = mtd->read(mtd, (nftl->EraseSize * BlockMap[block]) + (block * 512),
416 512, &retlen, movebuf);
417 if (ret < 0 && ret != -EUCLEAN) {
418 ret = mtd->read(mtd, (nftl->EraseSize * BlockMap[block])
419 + (block * 512), 512, &retlen,
422 printk("Error went away on retry.\n");
424 memset(&oob, 0xff, sizeof(struct nftl_oob));
425 oob.b.Status = oob.b.Status1 = SECTOR_USED;
427 nftl_write(nftl->mbd.mtd, (nftl->EraseSize * targetEUN) +
428 (block * 512), 512, &retlen, movebuf, (char *)&oob);
431 /* add the header so that it is now a valid chain */
432 oob.u.a.VirtUnitNum = oob.u.a.SpareVirtUnitNum = cpu_to_le16(thisVUC);
433 oob.u.a.ReplUnitNum = oob.u.a.SpareReplUnitNum = 0xffff;
435 nftl_write_oob(mtd, (nftl->EraseSize * targetEUN) + 8,
436 8, &retlen, (char *)&oob.u);
438 /* OK. We've moved the whole lot into the new block. Now we have to free the original blocks. */
440 /* At this point, we have two different chains for this Virtual Unit, and no way to tell
441 them apart. If we crash now, we get confused. However, both contain the same data, so we
442 shouldn't actually lose data in this case. It's just that when we load up on a medium which
443 has duplicate chains, we need to free one of the chains because it's not necessary any more.
445 thisEUN = nftl->EUNtable[thisVUC];
446 DEBUG(MTD_DEBUG_LEVEL1,"Want to erase\n");
448 /* For each block in the old chain (except the targetEUN of course),
449 free it and make it available for future use */
450 while (thisEUN <= nftl->lastEUN && thisEUN != targetEUN) {
453 EUNtmp = nftl->ReplUnitTable[thisEUN];
455 if (NFTL_formatblock(nftl, thisEUN) < 0) {
456 /* could not erase : mark block as reserved
458 nftl->ReplUnitTable[thisEUN] = BLOCK_RESERVED;
460 /* correctly erased : mark it as free */
461 nftl->ReplUnitTable[thisEUN] = BLOCK_FREE;
467 /* Make this the new start of chain for thisVUC */
468 nftl->ReplUnitTable[targetEUN] = BLOCK_NIL;
469 nftl->EUNtable[thisVUC] = targetEUN;
474 static u16 NFTL_makefreeblock( struct NFTLrecord *nftl , unsigned pendingblock)
476 /* This is the part that needs some cleverness applied.
477 For now, I'm doing the minimum applicable to actually
478 get the thing to work.
479 Wear-levelling and other clever stuff needs to be implemented
480 and we also need to do some assessment of the results when
481 the system loses power half-way through the routine.
483 u16 LongestChain = 0;
484 u16 ChainLength = 0, thislen;
487 for (chain = 0; chain < le32_to_cpu(nftl->MediaHdr.FormattedSize) / nftl->EraseSize; chain++) {
488 EUN = nftl->EUNtable[chain];
491 while (EUN <= nftl->lastEUN) {
493 //printk("VUC %d reaches len %d with EUN %d\n", chain, thislen, EUN);
494 EUN = nftl->ReplUnitTable[EUN] & 0x7fff;
495 if (thislen > 0xff00) {
496 printk("Endless loop in Virtual Chain %d: Unit %x\n",
499 if (thislen > 0xff10) {
500 /* Actually, don't return failure. Just ignore this chain and
507 if (thislen > ChainLength) {
508 //printk("New longest chain is %d with length %d\n", chain, thislen);
509 ChainLength = thislen;
510 LongestChain = chain;
514 if (ChainLength < 2) {
515 printk(KERN_WARNING "No Virtual Unit Chains available for folding. "
516 "Failing request\n");
520 return NFTL_foldchain (nftl, LongestChain, pendingblock);
523 /* NFTL_findwriteunit: Return the unit number into which we can write
524 for this block. Make it available if it isn't already
526 static inline u16 NFTL_findwriteunit(struct NFTLrecord *nftl, unsigned block)
529 u16 thisVUC = block / (nftl->EraseSize / 512);
530 struct mtd_info *mtd = nftl->mbd.mtd;
531 unsigned int writeEUN;
532 unsigned long blockofs = (block * 512) & (nftl->EraseSize -1);
534 int silly, silly2 = 3;
538 /* Scan the media to find a unit in the VUC which has
539 a free space for the block in question.
542 /* This condition catches the 0x[7f]fff cases, as well as
543 being a sanity check for past-end-of-media access
546 writeEUN = nftl->EUNtable[thisVUC];
548 while (writeEUN <= nftl->lastEUN) {
556 (writeEUN * nftl->EraseSize) + blockofs,
557 8, &retlen, (char *)&bci);
559 DEBUG(MTD_DEBUG_LEVEL2, "Status of block %d in EUN %d is %x\n",
560 block , writeEUN, le16_to_cpu(bci.Status));
562 status = bci.Status | bci.Status1;
572 // Invalid block. Don't use it any more. Must implement.
578 "Infinite loop in Virtual Unit Chain 0x%x\n",
583 /* Skip to next block in chain */
584 writeEUN = nftl->ReplUnitTable[writeEUN];
587 /* OK. We didn't find one in the existing chain, or there
588 is no existing chain. */
590 /* Try to find an already-free block */
591 writeEUN = NFTL_findfreeblock(nftl, 0);
593 if (writeEUN == BLOCK_NIL) {
594 /* That didn't work - there were no free blocks just
595 waiting to be picked up. We're going to have to fold
596 a chain to make room.
599 /* First remember the start of this chain */
600 //u16 startEUN = nftl->EUNtable[thisVUC];
602 //printk("Write to VirtualUnitChain %d, calling makefreeblock()\n", thisVUC);
603 writeEUN = NFTL_makefreeblock(nftl, 0xffff);
605 if (writeEUN == BLOCK_NIL) {
606 /* OK, we accept that the above comment is
607 lying - there may have been free blocks
608 last time we called NFTL_findfreeblock(),
609 but they are reserved for when we're
610 desperate. Well, now we're desperate.
612 DEBUG(MTD_DEBUG_LEVEL1, "Using desperate==1 to find free EUN to accommodate write to VUC %d\n", thisVUC);
613 writeEUN = NFTL_findfreeblock(nftl, 1);
615 if (writeEUN == BLOCK_NIL) {
616 /* Ouch. This should never happen - we should
617 always be able to make some room somehow.
618 If we get here, we've allocated more storage
619 space than actual media, or our makefreeblock
620 routine is missing something.
622 printk(KERN_WARNING "Cannot make free space.\n");
625 //printk("Restarting scan\n");
630 /* We've found a free block. Insert it into the chain. */
632 if (lastEUN != BLOCK_NIL) {
633 thisVUC |= 0x8000; /* It's a replacement block */
635 /* The first block in a new chain */
636 nftl->EUNtable[thisVUC] = writeEUN;
639 /* set up the actual EUN we're writing into */
640 /* Both in our cache... */
641 nftl->ReplUnitTable[writeEUN] = BLOCK_NIL;
643 /* ... and on the flash itself */
644 nftl_read_oob(mtd, writeEUN * nftl->EraseSize + 8, 8,
645 &retlen, (char *)&oob.u);
647 oob.u.a.VirtUnitNum = oob.u.a.SpareVirtUnitNum = cpu_to_le16(thisVUC);
649 nftl_write_oob(mtd, writeEUN * nftl->EraseSize + 8, 8,
650 &retlen, (char *)&oob.u);
652 /* we link the new block to the chain only after the
653 block is ready. It avoids the case where the chain
654 could point to a free block */
655 if (lastEUN != BLOCK_NIL) {
656 /* Both in our cache... */
657 nftl->ReplUnitTable[lastEUN] = writeEUN;
658 /* ... and on the flash itself */
659 nftl_read_oob(mtd, (lastEUN * nftl->EraseSize) + 8,
660 8, &retlen, (char *)&oob.u);
662 oob.u.a.ReplUnitNum = oob.u.a.SpareReplUnitNum
663 = cpu_to_le16(writeEUN);
665 nftl_write_oob(mtd, (lastEUN * nftl->EraseSize) + 8,
666 8, &retlen, (char *)&oob.u);
673 printk(KERN_WARNING "Error folding to make room for Virtual Unit Chain 0x%x\n",
678 static int nftl_writeblock(struct mtd_blktrans_dev *mbd, unsigned long block,
681 struct NFTLrecord *nftl = (void *)mbd;
683 unsigned long blockofs = (block * 512) & (nftl->EraseSize - 1);
687 writeEUN = NFTL_findwriteunit(nftl, block);
689 if (writeEUN == BLOCK_NIL) {
691 "NFTL_writeblock(): Cannot find block to write to\n");
692 /* If we _still_ haven't got a block to use, we're screwed */
696 memset(&oob, 0xff, sizeof(struct nftl_oob));
697 oob.b.Status = oob.b.Status1 = SECTOR_USED;
699 nftl_write(nftl->mbd.mtd, (writeEUN * nftl->EraseSize) + blockofs,
700 512, &retlen, (char *)buffer, (char *)&oob);
703 #endif /* CONFIG_NFTL_RW */
705 static int nftl_readblock(struct mtd_blktrans_dev *mbd, unsigned long block,
708 struct NFTLrecord *nftl = (void *)mbd;
709 struct mtd_info *mtd = nftl->mbd.mtd;
711 u16 thisEUN = nftl->EUNtable[block / (nftl->EraseSize / 512)];
712 unsigned long blockofs = (block * 512) & (nftl->EraseSize - 1);
714 int silly = MAX_LOOPS;
718 lastgoodEUN = BLOCK_NIL;
720 if (thisEUN != BLOCK_NIL) {
721 while (thisEUN < nftl->nb_blocks) {
722 if (nftl_read_oob(mtd, (thisEUN * nftl->EraseSize) +
723 blockofs, 8, &retlen,
725 status = SECTOR_IGNORE;
727 status = bci.Status | bci.Status1;
731 /* no modification of a sector should follow a free sector */
734 lastgoodEUN = BLOCK_NIL;
737 lastgoodEUN = thisEUN;
742 printk("Unknown status for block %ld in EUN %d: %x\n",
743 block, thisEUN, status);
748 printk(KERN_WARNING "Infinite loop in Virtual Unit Chain 0x%lx\n",
749 block / (nftl->EraseSize / 512));
752 thisEUN = nftl->ReplUnitTable[thisEUN];
757 if (lastgoodEUN == BLOCK_NIL) {
758 /* the requested block is not on the media, return all 0x00 */
759 memset(buffer, 0, 512);
761 loff_t ptr = (lastgoodEUN * nftl->EraseSize) + blockofs;
763 int res = mtd->read(mtd, ptr, 512, &retlen, buffer);
765 if (res < 0 && res != -EUCLEAN)
771 static int nftl_getgeo(struct mtd_blktrans_dev *dev, struct hd_geometry *geo)
773 struct NFTLrecord *nftl = (void *)dev;
775 geo->heads = nftl->heads;
776 geo->sectors = nftl->sectors;
777 geo->cylinders = nftl->cylinders;
782 /****************************************************************************
786 ****************************************************************************/
789 static struct mtd_blktrans_ops nftl_tr = {
792 .part_bits = NFTL_PARTN_BITS,
794 .getgeo = nftl_getgeo,
795 .readsect = nftl_readblock,
796 #ifdef CONFIG_NFTL_RW
797 .writesect = nftl_writeblock,
799 .add_mtd = nftl_add_mtd,
800 .remove_dev = nftl_remove_dev,
801 .owner = THIS_MODULE,
804 static int __init init_nftl(void)
806 return register_mtd_blktrans(&nftl_tr);
809 static void __exit cleanup_nftl(void)
811 deregister_mtd_blktrans(&nftl_tr);
814 module_init(init_nftl);
815 module_exit(cleanup_nftl);
817 MODULE_LICENSE("GPL");
818 MODULE_AUTHOR("David Woodhouse <dwmw2@infradead.org>, Fabrice Bellard <fabrice.bellard@netgem.com> et al.");
819 MODULE_DESCRIPTION("Support code for NAND Flash Translation Layer, used on M-Systems DiskOnChip 2000 and Millennium");