1 /*
2 This file is part of UFFS, the Ultra-low-cost Flash File System.
3
4 Copyright (C) 2005-2009 Ricky Zheng <[email protected]>
5
6 UFFS is free software; you can redistribute it and/or modify it under
7 the GNU Library General Public License as published by the Free Software
8 Foundation; either version 2 of the License, or (at your option) any
9 later version.
10
11 UFFS is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 or GNU Library General Public License, as applicable, for more details.
15
16 You should have received a copy of the GNU General Public License
17 and GNU Library General Public License along with UFFS; if not, write
18 to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA.
20
21 As a special exception, if other files instantiate templates or use
22 macros or inline functions from this file, or you compile this file
23 and link it with other works to produce a work based on this file,
24 this file does not by itself cause the resulting work to be covered
25 by the GNU General Public License. However the source code for this
26 file must still be made available in accordance with section (3) of
27 the GNU General Public License v2.
28
29 This exception does not invalidate any other reasons why a work based
30 on this file might be covered by the GNU General Public License.
31 */
32
33 /**
34 * \file uffs_tree.c
35 * \brief seting up uffs tree data structure
36 * \author Ricky Zheng, created 13th May, 2005
37 */
38
39 #include "uffs_config.h"
40 #include "uffs/uffs_public.h"
41 #include "uffs/uffs_os.h"
42 #include "uffs/uffs_pool.h"
43 #include "uffs/uffs_flash.h"
44 #include "uffs/uffs_badblock.h"
45
46 #include <string.h>
47
48 #define TPOOL(dev) &(dev->mem.tree_pool)
49
50 #define PFX "tree: "
51
52 static void uffs_InsertToFileEntry(uffs_Device *dev, TreeNode *node);
53 static void uffs_InsertToDirEntry(uffs_Device *dev, TreeNode *node);
54 static void uffs_InsertToDataEntry(uffs_Device *dev, TreeNode *node);
55
56 static TreeNode * uffs_TreeGetErasedNodeNoCheck(uffs_Device *dev);
57
58
59 struct BlockTypeStatSt {
60 int dir;
61 int file;
62 int data;
63 };
64
65 /**
66 * \brief initialize tree buffers
67 * \param[in] dev uffs device
68 */
uffs_TreeInit(uffs_Device * dev)69 URET uffs_TreeInit(uffs_Device *dev)
70 {
71 int size;
72 int num;
73 uffs_Pool *pool;
74 int i;
75
76 size = sizeof(TreeNode);
77 num = dev->par.end - dev->par.start + 1;
78
79 pool = &(dev->mem.tree_pool);
80
81 if (dev->mem.tree_nodes_pool_size == 0) {
82 if (dev->mem.malloc) {
83 dev->mem.tree_nodes_pool_buf = dev->mem.malloc(dev, size * num);
84 if (dev->mem.tree_nodes_pool_buf)
85 dev->mem.tree_nodes_pool_size = size * num;
86 }
87 }
88 if (size * num > dev->mem.tree_nodes_pool_size) {
89 uffs_Perror(UFFS_MSG_DEAD,
90 "Tree buffer require %d but only %d available.",
91 size * num, dev->mem.tree_nodes_pool_size);
92 memset(pool, 0, sizeof(uffs_Pool));
93 return U_FAIL;
94 }
95 uffs_Perror(UFFS_MSG_NOISY, "alloc tree nodes %d bytes.", size * num);
96
97 uffs_PoolInit(pool, dev->mem.tree_nodes_pool_buf,
98 dev->mem.tree_nodes_pool_size, size, num);
99
100 dev->tree.erased = NULL;
101 dev->tree.erased_tail = NULL;
102 dev->tree.erased_count = 0;
103 dev->tree.bad = NULL;
104 dev->tree.bad_count = 0;
105
106 for (i = 0; i < DIR_NODE_ENTRY_LEN; i++) {
107 dev->tree.dir_entry[i] = EMPTY_NODE;
108 }
109
110 for (i = 0; i < FILE_NODE_ENTRY_LEN; i++) {
111 dev->tree.file_entry[i] = EMPTY_NODE;
112 }
113
114 for (i = 0; i < DATA_NODE_ENTRY_LEN; i++) {
115 dev->tree.data_entry[i] = EMPTY_NODE;
116 }
117
118 dev->tree.max_serial = ROOT_DIR_SERIAL;
119
120 return U_SUCC;
121 }
122 /**
123 * \brief release tree buffers, call this function when unmount
124 * \param[in] dev uffs device
125 */
uffs_TreeRelease(uffs_Device * dev)126 URET uffs_TreeRelease(uffs_Device *dev)
127 {
128 uffs_Pool *pool;
129
130 pool = &(dev->mem.tree_pool);
131 if (pool->mem && dev->mem.free) {
132 dev->mem.free(dev, pool->mem);
133 pool->mem = NULL;
134 dev->mem.tree_nodes_pool_size = 0;
135 }
136 uffs_PoolRelease(pool);
137 memset(pool, 0, sizeof(uffs_Pool));
138
139 return U_SUCC;
140 }
141
_GetBlockFromNode(u8 type,TreeNode * node)142 static u16 _GetBlockFromNode(u8 type, TreeNode *node)
143 {
144 switch (type) {
145 case UFFS_TYPE_DIR:
146 return node->u.dir.block;
147 case UFFS_TYPE_FILE:
148 return node->u.file.block;
149 case UFFS_TYPE_DATA:
150 return node->u.data.block;
151 }
152 uffs_Perror(UFFS_MSG_SERIOUS, "unkown type, X-block");
153 return UFFS_INVALID_BLOCK;
154 }
155
156 #if 0
157 static u16 _GetParentFromNode(u8 type, TreeNode *node)
158 {
159 switch (type) {
160 case UFFS_TYPE_DIR:
161 return node->u.dir.parent;
162 case UFFS_TYPE_FILE:
163 return node->u.file.parent;
164 case UFFS_TYPE_DATA:
165 return node->u.data.parent;
166 }
167 uffs_Perror(UFFS_MSG_SERIOUS, "unkown type, X-parent");
168 return INVALID_UFFS_SERIAL;
169 }
170
171
172 static u16 _GetSerialFromNode(u8 type, TreeNode *node)
173 {
174 switch (type) {
175 case UFFS_TYPE_DIR:
176 return node->u.dir.serial;
177 case UFFS_TYPE_FILE:
178 return node->u.file.serial;
179 case UFFS_TYPE_DATA:
180 return node->u.data.serial;
181 }
182 uffs_Perror(UFFS_MSG_SERIOUS, "unkown type, X-serial");
183 return INVALID_UFFS_SERIAL;
184 }
185 #endif
186
187 /**
188 * insert a TreeNode *node to tree
189 * \param[in] dev uffs device
190 * \param[in] type type of node
191 * \param[in] node node to be insert to
192 */
uffs_InsertNodeToTree(uffs_Device * dev,u8 type,TreeNode * node)193 void uffs_InsertNodeToTree(uffs_Device *dev, u8 type, TreeNode *node)
194 {
195 switch (type) {
196 case UFFS_TYPE_DIR:
197 uffs_InsertToDirEntry(dev, node);
198 break;
199 case UFFS_TYPE_FILE:
200 uffs_InsertToFileEntry(dev, node);
201 break;
202 case UFFS_TYPE_DATA:
203 uffs_InsertToDataEntry(dev, node);
204 break;
205 default:
206 uffs_Perror(UFFS_MSG_SERIOUS,
207 "unkown type, can't insert to tree");
208 break;
209 }
210 }
211
212 /**
213 * find a node from tree
214 * \param[in] dev uffs device
215 * \param[in] type type of node
216 * \param[in] parent parent serial num
217 * \param[in] serial serial num
218 */
uffs_FindFromTree(uffs_Device * dev,u8 type,u16 parent,u16 serial)219 TreeNode * uffs_FindFromTree(uffs_Device *dev,
220 u8 type, u16 parent, u16 serial)
221 {
222 switch (type) {
223 case UFFS_TYPE_DIR:
224 return uffs_TreeFindDirNode(dev, serial);
225 case UFFS_TYPE_FILE:
226 return uffs_TreeFindFileNode(dev, serial);
227 case UFFS_TYPE_DATA:
228 return uffs_TreeFindDataNode(dev, parent, serial);
229 }
230 uffs_Perror(UFFS_MSG_SERIOUS,
231 "unkown type, can't find node");
232 return NULL;
233 }
234
235
236
_BuildValidTreeNode(uffs_Device * dev,TreeNode * node,uffs_BlockInfo * bc,struct BlockTypeStatSt * st)237 static URET _BuildValidTreeNode(uffs_Device *dev,
238 TreeNode *node, //!< empty node
239 uffs_BlockInfo *bc,
240 struct BlockTypeStatSt *st)
241 {
242 uffs_Tags *tag;
243 TreeNode *node_alt;
244 u16 block, parent, serial, block_alt, block_save;
245 uffs_BlockInfo *bc_alt;
246 u8 type;
247 int page;
248 UBOOL needToInsertToTree = U_FALSE;
249 uffs_Buf *buf = NULL;
250 uffs_FileInfo *info;
251 u16 data_sum = 0;
252
253 // check the first page on the block ...
254 uffs_BlockInfoLoad(dev, bc, 0);
255
256 tag = GET_TAG(bc, 0); //get first page's tag
257
258 if (!TAG_IS_DIRTY(tag)) {
259 // should never go here ... unless mark dirty page failed ?
260 uffs_Perror(UFFS_MSG_NORMAL,
261 "First page is clean in a non-erased block ?");
262 return U_FAIL;
263 }
264
265 if (!TAG_IS_VALID(tag)) {
266 //first page is invalid ? should be erased now!
267 uffs_Perror(UFFS_MSG_NORMAL,
268 "first page in block %d is invalid, will be erased now!",
269 bc->block);
270 goto process_invalid_block;
271 }
272
273 block = bc->block;
274 parent = TAG_PARENT(tag);
275 serial = TAG_SERIAL(tag);
276 type = TAG_TYPE(tag);
277
278 // check if there is an 'alternative block'
279 // (node which has the same serial number) in tree ?
280 node_alt = uffs_FindFromTree(dev, type, parent, serial);
281
282 if (node_alt != NULL) {
283 //find a alternate node ! need to check the timestamp !
284
285 block_alt = _GetBlockFromNode(type, node_alt);
286
287 uffs_Perror(UFFS_MSG_NORMAL,
288 "Process unclean block (%d vs %d)", block, block_alt);
289
290 if (block_alt == INVALID_UFFS_SERIAL) {
291 uffs_Perror(UFFS_MSG_SERIOUS, "invalid block ?");
292 return U_FAIL;
293 }
294
295 bc_alt = uffs_BlockInfoGet(dev, block_alt);
296 if (bc_alt == NULL) {
297 uffs_Perror(UFFS_MSG_SERIOUS, "can't get block info ");
298 return U_FAIL;
299 }
300 uffs_BlockInfoLoad(dev, bc_alt, 0);
301 if (uffs_IsSrcNewerThanObj (
302 TAG_BLOCK_TS(tag),
303 TAG_BLOCK_TS(GET_TAG(bc_alt, 0))) == U_TRUE) {
304
305 //the node is newer than node_alt, so keep node_alt, and erase node
306 uffs_FlashEraseBlock(dev, block);
307 node->u.list.block = block;
308 if (HAVE_BADBLOCK(dev))
309 uffs_BadBlockProcess(dev, node);
310 else
311 uffs_TreeInsertToErasedListTail(dev, node);
312
313 uffs_BlockInfoPut(dev, bc_alt); //put back bc_alt before we return.
314 return U_SUCC;
315 }
316 else {
317 //the node is older than node_alt, so keep node, and erase node_alt
318 //we use node as erased node to insert to erased list
319
320 block_save = _GetBlockFromNode(type, node_alt);
321 uffs_FlashEraseBlock(dev, block_save);
322 node->u.list.block = block_save;
323 if (HAVE_BADBLOCK(dev))
324 uffs_BadBlockProcess(dev, node);
325 else
326 uffs_TreeInsertToErasedListTail(dev, node);
327
328 //put back bc_alt because we don't need it anymore.
329 uffs_BlockInfoPut(dev, bc_alt);
330
331 //use node_alt to store new informations in following
332 node = node_alt;
333
334 needToInsertToTree = U_FALSE;
335 }
336 }
337 else {
338 needToInsertToTree = U_TRUE;
339 }
340
341 if (type == UFFS_TYPE_DIR || type == UFFS_TYPE_FILE) {
342 buf = uffs_BufClone(dev, NULL);
343 if (buf == NULL)
344 return U_FAIL;
345 uffs_BlockInfoLoad(dev, bc, UFFS_ALL_PAGES);
346 page = uffs_FindPageInBlockWithPageId(dev, bc, 0);
347 if (page == UFFS_INVALID_PAGE) {
348 uffs_BufFreeClone(dev, buf);
349 uffs_Perror(UFFS_MSG_SERIOUS,
350 "Can't find any valid page for page_id=0 ? invalid block !"
351 "this might be caused by the tag layout change.\n");
352 goto process_invalid_block;
353 }
354 page = uffs_FindBestPageInBlock(dev, bc, page);
355 uffs_FlashReadPage(dev, block, page, buf, U_FALSE);
356 info = (uffs_FileInfo *) (buf->data);
357 data_sum = uffs_MakeSum16(info->name, info->name_len);
358 uffs_BufFreeClone(dev, buf);
359 }
360
361 switch (type) {
362 case UFFS_TYPE_DIR:
363 node->u.dir.block = bc->block;
364 node->u.dir.checksum = data_sum;
365 node->u.dir.parent = TAG_PARENT(tag);
366 node->u.dir.serial = TAG_SERIAL(tag);
367 st->dir++;
368 break;
369 case UFFS_TYPE_FILE:
370 node->u.file.block = bc->block;
371 node->u.file.checksum = data_sum;
372 node->u.file.parent = TAG_PARENT(tag);
373 node->u.file.serial = TAG_SERIAL(tag);
374 node->u.file.len = uffs_GetBlockFileDataLength(dev, bc, UFFS_TYPE_FILE);
375 st->file++;
376 break;
377 case UFFS_TYPE_DATA:
378 node->u.data.block = bc->block;
379 node->u.data.parent = TAG_PARENT(tag);
380 node->u.data.serial = TAG_SERIAL(tag);
381 node->u.data.len = uffs_GetBlockFileDataLength(dev, bc, UFFS_TYPE_DATA);
382 st->data++;
383 break;
384 }
385
386 if (needToInsertToTree == U_TRUE) {
387 uffs_InsertNodeToTree(dev, type, node);
388 }
389
390 return U_SUCC;
391
392 process_invalid_block:
393 /* erase the invalid block */
394 uffs_FlashEraseBlock(dev, bc->block);
395
396 node->u.list.block = bc->block;
397
398 if (HAVE_BADBLOCK(dev))
399 uffs_BadBlockProcess(dev, node);
400 else
401 uffs_TreeInsertToErasedListTail(dev, node);
402
403 return U_SUCC;
404 }
405
406
_ScanAndFixUnCleanPage(uffs_Device * dev,uffs_BlockInfo * bc)407 static URET _ScanAndFixUnCleanPage(uffs_Device *dev, uffs_BlockInfo *bc)
408 {
409 int page;
410 uffs_Tags *tag;
411 struct uffs_MiniHeaderSt header;
412
413 /* in most case, the valid block contents fewer free page,
414 so it's better scan from the last page ... to page 1.
415 note: scanning page 0 is not necessary, will check it later.
416
417 The worse case: read (pages_per_block - 1) * (mini header + spares) !
418 most case: read one spare.
419 */
420 for (page = dev->attr->pages_per_block - 1; page > 0; page--) {
421 uffs_BlockInfoLoad(dev, bc, page);
422 tag = GET_TAG(bc, page);
423
424 if (TAG_IS_SEALED(tag))
425 break; // tag sealed, no unclean page in this block.
426
427 if (TAG_IS_DIRTY(tag) || TAG_IS_VALID(tag)) { // tag not sealed but dirty/valid ?
428 uffs_Perror(UFFS_MSG_NORMAL,
429 "unclean page found, block %d page %d",
430 bc->block, page);
431
432 // ok, an unclean page found.
433 // This unclean page can be identified by tag.
434 // We can leave it as it is, but performing a block recover would be good ?
435 // There won't be another unclean page in this block ... stop here.
436 break;
437 }
438
439 // now we have a clean tag (all 0xFF ?). Need to check mini header to see if it's an unclean page.
440 if (uffs_LoadMiniHeader(dev, bc->block, page, &header) == U_FAIL)
441 return U_FAIL;
442
443 if (header.status != 0xFF) {
444 // page data is dirty? this is an unclean page and we should explicitly mark tag as 'dirty and invalid'.
445 // This writing does not violate "no partial program" claim, because we are writing to a clean page spare.
446 uffs_Perror(UFFS_MSG_NORMAL,
447 "unclean page found, block %d page %d, mark it.",
448 bc->block, page);
449 uffs_FlashMarkDirtyPage(dev, bc, page);
450 }
451 }
452
453 return U_SUCC;
454 }
455
456
_BuildTreeStepOne(uffs_Device * dev)457 static URET _BuildTreeStepOne(uffs_Device *dev)
458 {
459 int block_lt;
460 uffs_BlockInfo *bc = NULL;
461 TreeNode *node;
462 struct uffs_TreeSt *tree;
463 uffs_Pool *pool;
464 struct uffs_MiniHeaderSt header;
465 URET ret = U_SUCC;
466 struct BlockTypeStatSt st = {0, 0, 0};
467
468 tree = &(dev->tree);
469 pool = TPOOL(dev);
470
471 tree->bad = NULL;
472 tree->bad_count = 0;
473 tree->erased = NULL;
474 tree->erased_tail = NULL;
475 tree->erased_count = 0;
476
477 uffs_Perror(UFFS_MSG_NOISY, "build tree step one");
478
479 // printf("s:%d e:%d\n", dev->par.start, dev->par.end);
480 for (block_lt = dev->par.start; block_lt <= dev->par.end; block_lt++) {
481 bc = uffs_BlockInfoGet(dev, block_lt);
482 if (bc == NULL) {
483 uffs_Perror(UFFS_MSG_SERIOUS, "step one:fail to get block info");
484 ret = U_FAIL;
485 break;
486 }
487 node = (TreeNode *)uffs_PoolGet(pool);
488 if (node == NULL) {
489 uffs_Perror(UFFS_MSG_SERIOUS, "insufficient tree node!");
490 ret = U_FAIL;
491 break;
492 }
493
494 // Need to check bad block at first !
495 if (uffs_FlashIsBadBlock(dev, block_lt) == U_TRUE) {
496 node->u.list.block = block_lt;
497 uffs_TreeInsertToBadBlockList(dev, node);
498 uffs_Perror(UFFS_MSG_NORMAL, "found bad block %d", block_lt);
499 }
500 else if (uffs_IsPageErased(dev, bc, 0) == U_TRUE) { //@ read one spare: 0
501 // page 0 tag shows it's an erased block, we need to check the mini header status to make sure it is clean.
502 if (uffs_LoadMiniHeader(dev, block_lt, 0, &header) == U_FAIL) {
503 uffs_Perror(UFFS_MSG_SERIOUS,
504 "I/O error when reading mini header !"
505 "block %d page %d",
506 block_lt, 0);
507 ret = U_FAIL;
508 break;
509 }
510
511 if (header.status != 0xFF) {
512 // page 0 tag is clean but page data is dirty ???
513 // this block should be erased immediately !
514 uffs_FlashEraseBlock(dev, block_lt);
515 }
516 node->u.list.block = block_lt;
517 if (HAVE_BADBLOCK(dev)) {
518 uffs_Perror(UFFS_MSG_NORMAL,
519 "New bad block (%d) discovered.", block_lt);
520 uffs_BadBlockProcess(dev, node);
521 }
522 else {
523 // page 0 is clean does not means all pages in this block are clean,
524 // need to check this block later before use it.
525 uffs_TreeInsertToErasedListTailEx(dev, node, 1);
526 }
527 }
528 else {
529
530 // this block have valid data page(s).
531
532 ret = _ScanAndFixUnCleanPage(dev, bc);
533 if (ret == U_FAIL)
534 break;
535
536 ret = _BuildValidTreeNode(dev, node, bc, &st);
537 if (ret == U_FAIL)
538 break;
539
540 }
541 uffs_BlockInfoPut(dev, bc);
542 } //end of for
543
544 if(ret == U_FAIL)
545 uffs_BlockInfoPut(dev, bc);
546
547 uffs_Perror(UFFS_MSG_NORMAL,
548 "DIR %d, FILE %d, DATA %d", st.dir, st.file, st.data);
549
550 return ret;
551 }
552
_BuildTreeStepTwo(uffs_Device * dev)553 static URET _BuildTreeStepTwo(uffs_Device *dev)
554 {
555 //Randomise the start point of erased block to implement wear levelling
556 u32 startCount = 0;
557 u32 endPoint;
558 TreeNode *node;
559
560 uffs_Perror(UFFS_MSG_NOISY, "build tree step two");
561
562 endPoint = uffs_GetCurDateTime() % (dev->tree.erased_count + 1);
563 while (startCount < endPoint) {
564 node = uffs_TreeGetErasedNodeNoCheck(dev);
565 if (node == NULL) {
566 uffs_Perror(UFFS_MSG_SERIOUS, "No erased block ?");
567 return U_FAIL;
568 }
569 uffs_TreeInsertToErasedListTailEx(dev, node, -1);
570 startCount++;
571 }
572
573 return U_SUCC;
574 }
575
uffs_TreeFindFileNode(uffs_Device * dev,u16 serial)576 TreeNode * uffs_TreeFindFileNode(uffs_Device *dev, u16 serial)
577 {
578 int hash;
579 u16 x;
580 TreeNode *node;
581 struct uffs_TreeSt *tree = &(dev->tree);
582
583 hash = serial & FILE_NODE_HASH_MASK;
584 x = tree->file_entry[hash];
585 while (x != EMPTY_NODE) {
586 node = FROM_IDX(x, TPOOL(dev));
587 if (node->u.file.serial == serial) {
588 return node;
589 }
590 else {
591 x = node->hash_next;
592 }
593 }
594 return NULL;
595 }
596
597 /** add a node into suspend list */
uffs_TreeSuspendAdd(uffs_Device * dev,TreeNode * node)598 void uffs_TreeSuspendAdd(uffs_Device *dev, TreeNode *node)
599 {
600 node->u.list.next = dev->tree.suspend;
601 node->u.list.prev = NULL;
602
603 if (dev->tree.suspend)
604 dev->tree.suspend->u.list.prev = node;
605 dev->tree.suspend = node;
606 }
607
608 /** search suspend list */
uffs_TreeFindSuspendNode(uffs_Device * dev,u16 serial)609 TreeNode * uffs_TreeFindSuspendNode(uffs_Device *dev, u16 serial)
610 {
611 TreeNode *node = dev->tree.suspend;
612 while (node) {
613 if (node->u.list.u.serial == serial)
614 break;
615
616 node = node->u.list.next;
617 }
618
619 return node;
620 }
621
622 /** remove a node from suspend list */
uffs_TreeRemoveSuspendNode(uffs_Device * dev,TreeNode * node)623 void uffs_TreeRemoveSuspendNode(uffs_Device *dev, TreeNode *node)
624 {
625 if (node->u.list.prev)
626 node->u.list.prev->u.list.next = node->u.list.next;
627 if (node->u.list.next)
628 node->u.list.next->u.list.prev = node->u.list.prev;
629 if (node == dev->tree.suspend)
630 dev->tree.suspend = NULL;
631 }
632
uffs_TreeFindFileNodeWithParent(uffs_Device * dev,u16 parent)633 TreeNode * uffs_TreeFindFileNodeWithParent(uffs_Device *dev, u16 parent)
634 {
635 int hash;
636 u16 x;
637 TreeNode *node;
638 struct uffs_TreeSt *tree = &(dev->tree);
639
640 for (hash = 0; hash < FILE_NODE_ENTRY_LEN; hash++) {
641 x = tree->file_entry[hash];
642 while (x != EMPTY_NODE) {
643 node = FROM_IDX(x, TPOOL(dev));
644 if (node->u.file.parent == parent) {
645 return node;
646 }
647 else {
648 x = node->hash_next;
649 }
650 }
651 }
652
653 return NULL;
654 }
655
uffs_TreeFindDirNode(uffs_Device * dev,u16 serial)656 TreeNode * uffs_TreeFindDirNode(uffs_Device *dev, u16 serial)
657 {
658 int hash;
659 u16 x;
660 TreeNode *node;
661 struct uffs_TreeSt *tree = &(dev->tree);
662
663 hash = serial & DIR_NODE_HASH_MASK;
664 x = tree->dir_entry[hash];
665 while (x != EMPTY_NODE) {
666 node = FROM_IDX(x, TPOOL(dev));
667 if (node->u.dir.serial == serial) {
668 return node;
669 }
670 else {
671 x = node->hash_next;
672 }
673 }
674 return NULL;
675 }
676
uffs_TreeFindDirNodeWithParent(uffs_Device * dev,u16 parent)677 TreeNode * uffs_TreeFindDirNodeWithParent(uffs_Device *dev, u16 parent)
678 {
679 int hash;
680 u16 x;
681 TreeNode *node;
682 struct uffs_TreeSt *tree = &(dev->tree);
683
684 for (hash = 0; hash < DIR_NODE_ENTRY_LEN; hash++) {
685 x = tree->dir_entry[hash];
686 while (x != EMPTY_NODE) {
687 node = FROM_IDX(x, TPOOL(dev));
688 if (node->u.dir.parent == parent) {
689 return node;
690 }
691 else {
692 x = node->hash_next;
693 }
694 }
695 }
696
697 return NULL;
698 }
699
uffs_TreeFindFileNodeByName(uffs_Device * dev,const char * name,u32 len,u16 sum,u16 parent)700 TreeNode * uffs_TreeFindFileNodeByName(uffs_Device *dev,
701 const char *name,
702 u32 len,
703 u16 sum, u16 parent)
704 {
705 int i;
706 u16 x;
707 TreeNode *node;
708 struct uffs_TreeSt *tree = &(dev->tree);
709
710 for (i = 0; i < FILE_NODE_ENTRY_LEN; i++) {
711 x = tree->file_entry[i];
712 while (x != EMPTY_NODE) {
713 node = FROM_IDX(x, TPOOL(dev));
714 if (node->u.file.checksum == sum && node->u.file.parent == parent) {
715 //read file name from flash, and compare...
716 if (uffs_TreeCompareFileName(dev, name, len, sum,
717 node, UFFS_TYPE_FILE) == U_TRUE) {
718 //Got it!
719 return node;
720 }
721 }
722 x = node->hash_next;
723 }
724 }
725
726 return NULL;
727 }
728
uffs_TreeFindDataNode(uffs_Device * dev,u16 parent,u16 serial)729 TreeNode * uffs_TreeFindDataNode(uffs_Device *dev, u16 parent, u16 serial)
730 {
731 int hash;
732 TreeNode *node;
733 struct uffs_TreeSt *tree = &(dev->tree);
734 u16 x;
735
736 hash = GET_DATA_HASH(parent, serial);
737 x = tree->data_entry[hash];
738 while(x != EMPTY_NODE) {
739 node = FROM_IDX(x, TPOOL(dev));
740
741 if(node->u.data.parent == parent &&
742 node->u.data.serial == serial)
743 return node;
744
745 x = node->hash_next;
746 }
747
748 return NULL;
749 }
750
uffs_TreeFindDirNodeByBlock(uffs_Device * dev,u16 block)751 TreeNode * uffs_TreeFindDirNodeByBlock(uffs_Device *dev, u16 block)
752 {
753 int hash;
754 TreeNode *node;
755 struct uffs_TreeSt *tree = &(dev->tree);
756 u16 x;
757
758 for (hash = 0; hash < DIR_NODE_ENTRY_LEN; hash++) {
759 x = tree->dir_entry[hash];
760 while (x != EMPTY_NODE) {
761 node = FROM_IDX(x, TPOOL(dev));
762 if (node->u.dir.block == block)
763 return node;
764 x = node->hash_next;
765 }
766 }
767
768 return NULL;
769 }
770
uffs_TreeFindErasedNodeByBlock(uffs_Device * dev,u16 block)771 TreeNode * uffs_TreeFindErasedNodeByBlock(uffs_Device *dev, u16 block)
772 {
773 TreeNode *node;
774 node = dev->tree.erased;
775
776 while (node) {
777 if (node->u.list.block == block)
778 return node;
779 node = node->u.list.next;
780 }
781
782 return NULL;
783 }
784
uffs_TreeFindBadNodeByBlock(uffs_Device * dev,u16 block)785 TreeNode * uffs_TreeFindBadNodeByBlock(uffs_Device *dev, u16 block)
786 {
787 TreeNode *node;
788 node = dev->tree.bad;
789
790 while (node) {
791 if (node->u.list.block == block)
792 return node;
793 node = node->u.list.next;
794 }
795
796 return NULL;
797 }
798
uffs_TreeFindFileNodeByBlock(uffs_Device * dev,u16 block)799 TreeNode * uffs_TreeFindFileNodeByBlock(uffs_Device *dev, u16 block)
800 {
801 int hash;
802 TreeNode *node;
803 struct uffs_TreeSt *tree = &(dev->tree);
804 u16 x;
805
806 for (hash = 0; hash < FILE_NODE_ENTRY_LEN; hash++) {
807 x = tree->file_entry[hash];
808 while (x != EMPTY_NODE) {
809 node = FROM_IDX(x, TPOOL(dev));
810 if (node->u.file.block == block)
811 return node;
812 x = node->hash_next;
813 }
814 }
815
816 return NULL;
817 }
818
uffs_TreeFindDataNodeByBlock(uffs_Device * dev,u16 block)819 TreeNode * uffs_TreeFindDataNodeByBlock(uffs_Device *dev, u16 block)
820 {
821 int hash;
822 TreeNode *node;
823 struct uffs_TreeSt *tree = &(dev->tree);
824 u16 x;
825
826 for (hash = 0; hash < DATA_NODE_ENTRY_LEN; hash++) {
827 x = tree->data_entry[hash];
828 while (x != EMPTY_NODE) {
829 node = FROM_IDX(x, TPOOL(dev));
830 if (node->u.data.block == block)
831 return node;
832 x = node->hash_next;
833 }
834 }
835
836 return NULL;
837 }
838
uffs_TreeFindNodeByBlock(uffs_Device * dev,u16 block,int * region)839 TreeNode * uffs_TreeFindNodeByBlock(uffs_Device *dev, u16 block, int *region)
840 {
841 TreeNode *node = NULL;
842
843 if (*region & SEARCH_REGION_DATA) {
844 node = uffs_TreeFindDataNodeByBlock(dev, block);
845 if (node) {
846 *region &= SEARCH_REGION_DATA;
847 return node;
848 }
849 }
850 if (*region & SEARCH_REGION_FILE) {
851 node = uffs_TreeFindFileNodeByBlock(dev, block);
852 if (node) {
853 *region &= SEARCH_REGION_FILE;
854 return node;
855 }
856 }
857 if (*region & SEARCH_REGION_DIR) {
858 node = uffs_TreeFindDirNodeByBlock(dev, block);
859 if (node) {
860 *region &= SEARCH_REGION_DIR;
861 return node;
862 }
863 }
864 if (*region & SEARCH_REGION_ERASED) {
865 node = uffs_TreeFindErasedNodeByBlock(dev, block);
866 if (node) {
867 *region &= SEARCH_REGION_ERASED;
868 return node;
869 }
870 }
871 if (*region & SEARCH_REGION_BAD) {
872 node = uffs_TreeFindBadNodeByBlock(dev, block);
873 if (node) {
874 *region &= SEARCH_REGION_BAD;
875 return node;
876 }
877 }
878
879 return node;
880 }
881
uffs_TreeFindDirNodeByName(uffs_Device * dev,const char * name,u32 len,u16 sum,u16 parent)882 TreeNode * uffs_TreeFindDirNodeByName(uffs_Device *dev,
883 const char *name, u32 len,
884 u16 sum, u16 parent)
885 {
886 int i;
887 u16 x;
888 TreeNode *node;
889 struct uffs_TreeSt *tree = &(dev->tree);
890
891 for (i = 0; i < DIR_NODE_ENTRY_LEN; i++) {
892 x = tree->dir_entry[i];
893 while (x != EMPTY_NODE) {
894 node = FROM_IDX(x, TPOOL(dev));
895 if (node->u.dir.checksum == sum &&
896 node->u.dir.parent == parent) {
897 //read file name from flash, and compare...
898 if (uffs_TreeCompareFileName(dev, name, len, sum,
899 node, UFFS_TYPE_DIR) == U_TRUE) {
900 //Got it!
901 return node;
902 }
903 }
904 x = node->hash_next;
905 }
906 }
907
908 return NULL;
909
910 }
911
uffs_CompareFileName(const char * src,int src_len,const char * des)912 UBOOL uffs_CompareFileName(const char *src, int src_len, const char *des)
913 {
914 while (src_len-- > 0) {
915 if(*src++ != *des++)
916 return U_FALSE;
917 }
918
919 return U_TRUE;
920 }
921
922 /** compare [name] with tree [node] represented object name by loading
923 uffs_FileInfo from storage */
uffs_TreeCompareFileName(uffs_Device * dev,const char * name,u32 len,u16 sum,TreeNode * node,int type)924 UBOOL uffs_TreeCompareFileName(uffs_Device *dev,
925 const char *name, u32 len, u16 sum,
926 TreeNode *node, int type)
927 {
928 UBOOL matched = U_FALSE;
929 uffs_FileInfo *fi;
930 uffs_Buf *buf;
931 u16 data_sum;
932
933 buf = uffs_BufGetEx(dev, type, node, 0, 0);
934 if (buf == NULL) {
935 uffs_Perror(UFFS_MSG_SERIOUS, "can't get buf !\n ");
936 goto ext;
937 }
938 fi = (uffs_FileInfo *)(buf->data);
939 data_sum = uffs_MakeSum16(fi->name, fi->name_len);
940
941 if (data_sum != sum) {
942 uffs_Perror(UFFS_MSG_NORMAL,
943 "the obj's sum in storage is different with given sum!");
944 goto ext;
945 }
946
947 if (fi->name_len == len) {
948 if(uffs_CompareFileName(fi->name, fi->name_len, name) == U_TRUE) {
949 matched = U_TRUE;
950 }
951 }
952 ext:
953 if (buf)
954 uffs_BufPut(dev, buf);
955
956 return matched;
957 }
958
959
960 /* calculate file length, etc */
_BuildTreeStepThree(uffs_Device * dev)961 static URET _BuildTreeStepThree(uffs_Device *dev)
962 {
963 int i;
964 u16 x;
965 TreeNode *work;
966 TreeNode *node;
967 struct uffs_TreeSt *tree;
968 uffs_Pool *pool;
969 u16 blockSave;
970
971 TreeNode *cache = NULL;
972 u16 cacheSerial = INVALID_UFFS_SERIAL;
973
974 tree = &(dev->tree);
975 pool = TPOOL(dev);
976
977 uffs_Perror(UFFS_MSG_NOISY, "build tree step three");
978
979 for (i = 0; i < DATA_NODE_ENTRY_LEN; i++) {
980 x = tree->data_entry[i];
981 while (x != EMPTY_NODE) {
982 work = FROM_IDX(x, pool);
983 if (work->u.data.parent == cacheSerial) {
984 node = cache;
985 }
986 else {
987 node = uffs_TreeFindFileNode(dev, work->u.data.parent);
988 cache = node;
989 cacheSerial = work->u.data.parent;
990 }
991 if (node == NULL) {
992 x = work->hash_next;
993 //this data block does not belong to any file ?
994 //should be erased.
995 uffs_Perror(UFFS_MSG_NORMAL,
996 "find a orphan data block:%d, "
997 "parent:%d, serial:%d, will be erased!",
998 work->u.data.block,
999 work->u.data.parent, work->u.data.serial);
1000
1001 uffs_BreakFromEntry(dev, UFFS_TYPE_DATA, work);
1002 blockSave = work->u.data.block;
1003 work->u.list.block = blockSave;
1004 uffs_FlashEraseBlock(dev, blockSave);
1005 if (HAVE_BADBLOCK(dev))
1006 uffs_BadBlockProcess(dev, work);
1007 else
1008 uffs_TreeInsertToErasedListTail(dev, work);
1009 }
1010 else {
1011 node->u.file.len += work->u.data.len;
1012 x = work->hash_next;
1013 }
1014 }
1015 }
1016
1017 return U_SUCC;
1018 }
1019
1020 /**
1021 * \brief build tree structure from flash
1022 * \param[in] dev uffs device
1023 */
uffs_BuildTree(uffs_Device * dev)1024 URET uffs_BuildTree(uffs_Device *dev)
1025 {
1026 URET ret;
1027
1028 /***** step one: scan all page spares, classify DIR/FILE/DATA nodes,
1029 check bad blocks/uncompleted(conflicted) blocks as well *****/
1030
1031 /* if the disk is big and full filled of data this step could be
1032 the most time consuming .... */
1033
1034 ret = _BuildTreeStepOne(dev);
1035 if (ret != U_SUCC) {
1036 uffs_Perror(UFFS_MSG_SERIOUS, "build tree step one fail!");
1037 return ret;
1038 }
1039
1040 /***** step two: randomize the erased blocks, for ware-leveling purpose *****/
1041 /* this step is very fast :) */
1042 ret = _BuildTreeStepTwo(dev);
1043 if (ret != U_SUCC) {
1044 uffs_Perror(UFFS_MSG_SERIOUS, "build tree step two fail!");
1045 return ret;
1046 }
1047
1048 /***** step three: check DATA nodes, find orphan nodes and erase them *****/
1049 /* if there are a lot of files and disk is fully filled, this step
1050 could be very time consuming ... */
1051 ret = _BuildTreeStepThree(dev);
1052 if (ret != U_SUCC) {
1053 uffs_Perror(UFFS_MSG_SERIOUS, "build tree step three fail!");
1054 return ret;
1055 }
1056
1057 return U_SUCC;
1058 }
1059
1060 /**
1061 * find a free file or dir serial NO
1062 * \param[in] dev uffs device
1063 * \return if no free serial found, return #INVALID_UFFS_SERIAL
1064 */
uffs_FindFreeFsnSerial(uffs_Device * dev)1065 u16 uffs_FindFreeFsnSerial(uffs_Device *dev)
1066 {
1067 u16 i;
1068 TreeNode *node;
1069
1070 //TODO!! Do we need a faster serial number generating method?
1071 // it depends on how often creating files or directories
1072
1073 for (i = ROOT_DIR_SERIAL + 1; i < MAX_UFFS_FSN; i++) {
1074 node = uffs_TreeFindDirNode(dev, i);
1075 if (node == NULL) {
1076 node = uffs_TreeFindFileNode(dev, i);
1077 if (node == NULL) {
1078 node = uffs_TreeFindSuspendNode(dev, i);
1079 if (node == NULL)
1080 return i;
1081 }
1082 }
1083 }
1084
1085 return INVALID_UFFS_SERIAL;
1086 }
1087
uffs_TreeGetErasedNodeNoCheck(uffs_Device * dev)1088 static TreeNode * uffs_TreeGetErasedNodeNoCheck(uffs_Device *dev)
1089 {
1090 TreeNode *node = NULL;
1091 if (dev->tree.erased) {
1092 node = dev->tree.erased;
1093 dev->tree.erased->u.list.prev = NULL;
1094 dev->tree.erased = dev->tree.erased->u.list.next;
1095 if(dev->tree.erased == NULL)
1096 dev->tree.erased_tail = NULL;
1097 dev->tree.erased_count--;
1098 }
1099
1100 return node;
1101 }
1102
uffs_TreeGetErasedNode(uffs_Device * dev)1103 TreeNode * uffs_TreeGetErasedNode(uffs_Device *dev)
1104 {
1105 TreeNode *node = uffs_TreeGetErasedNodeNoCheck(dev);
1106 u16 block;
1107
1108 if (node && node->u.list.u.need_check) {
1109 block = node->u.list.block;
1110 if (uffs_FlashCheckErasedBlock(dev, block) != U_SUCC) {
1111 // Hmm, this block is not fully erased ? erase it immediately.
1112 uffs_FlashEraseBlock(dev, block);
1113 node->u.list.u.need_check = 0;
1114 }
1115 }
1116 return node;
1117 }
1118
_InsertToEntry(uffs_Device * dev,u16 * entry,int hash,TreeNode * node)1119 static void _InsertToEntry(uffs_Device *dev, u16 *entry,
1120 int hash, TreeNode *node)
1121 {
1122 node->hash_next = entry[hash];
1123 node->hash_prev = EMPTY_NODE;
1124 if (entry[hash] != EMPTY_NODE) {
1125 FROM_IDX(entry[hash], TPOOL(dev))->hash_prev = TO_IDX(node, TPOOL(dev));
1126 }
1127 entry[hash] = TO_IDX(node, TPOOL(dev));
1128 }
1129
1130
1131 /**
1132 * break the node from entry
1133 */
uffs_BreakFromEntry(uffs_Device * dev,u8 type,TreeNode * node)1134 void uffs_BreakFromEntry(uffs_Device *dev, u8 type, TreeNode *node)
1135 {
1136 u16 *entry;
1137 int hash;
1138 TreeNode *work;
1139
1140 switch (type) {
1141 case UFFS_TYPE_DIR:
1142 hash = GET_DIR_HASH(node->u.dir.serial);
1143 entry = &(dev->tree.dir_entry[hash]);
1144 break;
1145 case UFFS_TYPE_FILE:
1146 hash = GET_FILE_HASH(node->u.file.serial);
1147 entry = &(dev->tree.file_entry[hash]);
1148 break;
1149 case UFFS_TYPE_DATA:
1150 hash = GET_DATA_HASH(node->u.data.parent, node->u.data.serial);
1151 entry = &(dev->tree.data_entry[hash]);
1152 break;
1153 default:
1154 uffs_Perror(UFFS_MSG_SERIOUS, "unknown type when break...");
1155 return;
1156 }
1157
1158 if (node->hash_prev != EMPTY_NODE) {
1159 work = FROM_IDX(node->hash_prev, &(dev->mem.tree_pool));
1160 work->hash_next = node->hash_next;
1161 }
1162 if (node->hash_next != EMPTY_NODE) {
1163 work = FROM_IDX(node->hash_next, &(dev->mem.tree_pool));
1164 work->hash_prev = node->hash_prev;
1165 }
1166
1167 if (*entry == TO_IDX(node, &(dev->mem.tree_pool))) {
1168 *entry = node->hash_next;
1169 }
1170 }
1171
uffs_InsertToFileEntry(uffs_Device * dev,TreeNode * node)1172 static void uffs_InsertToFileEntry(uffs_Device *dev, TreeNode *node)
1173 {
1174 _InsertToEntry(dev, dev->tree.file_entry,
1175 GET_FILE_HASH(node->u.file.serial),
1176 node);
1177 }
1178
uffs_InsertToDirEntry(uffs_Device * dev,TreeNode * node)1179 static void uffs_InsertToDirEntry(uffs_Device *dev, TreeNode *node)
1180 {
1181 _InsertToEntry(dev, dev->tree.dir_entry,
1182 GET_DIR_HASH(node->u.dir.serial),
1183 node);
1184 }
1185
uffs_InsertToDataEntry(uffs_Device * dev,TreeNode * node)1186 static void uffs_InsertToDataEntry(uffs_Device *dev, TreeNode *node)
1187 {
1188 _InsertToEntry(dev, dev->tree.data_entry,
1189 GET_DATA_HASH(node->u.data.parent, node->u.data.serial),
1190 node);
1191 }
1192
uffs_InsertToErasedListHead(uffs_Device * dev,TreeNode * node)1193 void uffs_InsertToErasedListHead(uffs_Device *dev, TreeNode *node)
1194 {
1195 struct uffs_TreeSt *tree;
1196 tree = &(dev->tree);
1197
1198 node->u.list.next = tree->erased;
1199 node->u.list.prev = NULL;
1200
1201 if (tree->erased) {
1202 tree->erased->u.list.prev = node;
1203 }
1204
1205 tree->erased = node;
1206 if (node->u.list.next == tree->erased_tail) {
1207 tree->erased_tail = node;
1208 }
1209 tree->erased_count++;
1210 }
1211
1212 /**
1213 * insert node to erased list.
1214 * \param need_check: 0 - no need to check later
1215 * 1 - need to check later
1216 * < 0 - keep 'node->u.list.need_check' value
1217 */
uffs_TreeInsertToErasedListTailEx(uffs_Device * dev,TreeNode * node,int need_check)1218 void uffs_TreeInsertToErasedListTailEx(uffs_Device *dev, TreeNode *node, int need_check)
1219 {
1220 struct uffs_TreeSt *tree;
1221 tree = &(dev->tree);
1222
1223 if (need_check >= 0)
1224 node->u.list.u.need_check = need_check;
1225
1226 node->u.list.next = NULL;
1227 node->u.list.prev = tree->erased_tail;
1228 if (tree->erased_tail) {
1229 tree->erased_tail->u.list.next = node;
1230 }
1231
1232 tree->erased_tail = node;
1233 if(tree->erased == NULL) {
1234 tree->erased = node;
1235 }
1236 tree->erased_count++;
1237 }
1238
uffs_TreeInsertToErasedListTail(uffs_Device * dev,TreeNode * node)1239 void uffs_TreeInsertToErasedListTail(uffs_Device *dev, TreeNode *node)
1240 {
1241 // this function is called after the block is erased, so don't need to check.
1242 uffs_TreeInsertToErasedListTailEx(dev, node, 0);
1243 }
1244
uffs_TreeInsertToBadBlockList(uffs_Device * dev,TreeNode * node)1245 void uffs_TreeInsertToBadBlockList(uffs_Device *dev, TreeNode *node)
1246 {
1247 struct uffs_TreeSt *tree;
1248
1249 tree = &(dev->tree);
1250 node->u.list.prev = NULL;
1251 node->u.list.next = tree->bad;
1252
1253 if (tree->bad) {
1254 tree->bad->u.list.prev = node;
1255 }
1256
1257 tree->bad = node;
1258 tree->bad_count++;
1259 }
1260
1261 /**
1262 * set tree node block value
1263 */
uffs_TreeSetNodeBlock(u8 type,TreeNode * node,u16 block)1264 void uffs_TreeSetNodeBlock(u8 type, TreeNode *node, u16 block)
1265 {
1266 switch (type) {
1267 case UFFS_TYPE_FILE:
1268 node->u.file.block = block;
1269 break;
1270 case UFFS_TYPE_DIR:
1271 node->u.dir.block = block;
1272 break;
1273 case UFFS_TYPE_DATA:
1274 node->u.data.block = block;
1275 break;
1276 }
1277 }
1278
1279