?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[JFFS2] Whitespace cleanup. Fix missing debug message
[linux-2.6/openmoko-kernel/knife-kernel.git] / fs / jffs2 / nodelist.c
blob8a8e4b86382477c2a2a8ba2bcff9fd04ef02953a
1 /*
2 * JFFS2 -- Journalling Flash File System, Version 2.
3 *
4 * Copyright (C) 2001-2003 Red Hat, Inc.
5 *
6 * Created by David Woodhouse <dwmw2@infradead.org>
7 *
8 * For licensing information, see the file 'LICENCE' in this directory.
9 *
10 * $Id: nodelist.c,v 1.94 2005/04/13 13:22:35 dwmw2 Exp $
11 *
12 */
13
14 #include <linux/kernel.h>
15 #include <linux/sched.h>
16 #include <linux/fs.h>
17 #include <linux/mtd/mtd.h>
18 #include <linux/rbtree.h>
19 #include <linux/crc32.h>
20 #include <linux/slab.h>
21 #include <linux/pagemap.h>
22 #include "nodelist.h"
23
24 void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list)
25 {
26 struct jffs2_full_dirent **prev = list;
27 D1(printk(KERN_DEBUG "jffs2_add_fd_to_list( %p, %p (->%p))\n", new, list, *list));
28
29 while ((*prev) && (*prev)->nhash <= new->nhash) {
30 if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) {
31 /* Duplicate. Free one */
32 if (new->version < (*prev)->version) {
33 D1(printk(KERN_DEBUG "Eep! Marking new dirent node obsolete\n"));
34 D1(printk(KERN_DEBUG "New dirent is \"%s\"->ino #%u. Old is \"%s\"->ino #%u\n", new->name, new->ino, (*prev)->name, (*prev)->ino));
35 jffs2_mark_node_obsolete(c, new->raw);
36 jffs2_free_full_dirent(new);
37 } else {
38 D1(printk(KERN_DEBUG "Marking old dirent node (ino #%u) obsolete\n", (*prev)->ino));
39 new->next = (*prev)->next;
40 jffs2_mark_node_obsolete(c, ((*prev)->raw));
41 jffs2_free_full_dirent(*prev);
42 *prev = new;
43 }
44 goto out;
45 }
46 prev = &((*prev)->next);
47 }
48 new->next = *prev;
49 *prev = new;
50
51 out:
52 D2(while(*list) {
53 printk(KERN_DEBUG "Dirent \"%s\" (hash 0x%08x, ino #%u\n", (*list)->name, (*list)->nhash, (*list)->ino);
54 list = &(*list)->next;
55 });
56 }
57
58 /* Put a new tmp_dnode_info into the list, keeping the list in
59 order of increasing version
60 */
61 static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list)
62 {
63 struct jffs2_tmp_dnode_info **prev = list;
64
65 while ((*prev) && (*prev)->version < tn->version) {
66 prev = &((*prev)->next);
67 }
68 tn->next = (*prev);
69 *prev = tn;
70 }
71
72 static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info *tn)
73 {
74 struct jffs2_tmp_dnode_info *next;
75
76 while (tn) {
77 next = tn;
78 tn = tn->next;
79 jffs2_free_full_dnode(next->fn);
80 jffs2_free_tmp_dnode_info(next);
81 }
82 }
83
84 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
85 {
86 struct jffs2_full_dirent *next;
87
88 while (fd) {
89 next = fd->next;
90 jffs2_free_full_dirent(fd);
91 fd = next;
92 }
93 }
94
95 /* Returns first valid node after 'ref'. May return 'ref' */
96 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
97 {
98 while (ref && ref->next_in_ino) {
99 if (!ref_obsolete(ref))
100 return ref;
101 D1(printk(KERN_DEBUG "node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref)));
102 ref = ref->next_in_ino;
103 }
104 return NULL;
105 }
106
107 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
108 with this ino, returning the former in order of version */
109
110 int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
111 struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp,
112 uint32_t *highest_version, uint32_t *latest_mctime,
113 uint32_t *mctime_ver)
114 {
115 struct jffs2_raw_node_ref *ref, *valid_ref;
116 struct jffs2_tmp_dnode_info *tn, *ret_tn = NULL;
117 struct jffs2_full_dirent *fd, *ret_fd = NULL;
118 union jffs2_node_union node;
119 size_t retlen;
120 int err;
121
122 *mctime_ver = 0;
123
124 D1(printk(KERN_DEBUG "jffs2_get_inode_nodes(): ino #%u\n", f->inocache->ino));
125
126 spin_lock(&c->erase_completion_lock);
127
128 valid_ref = jffs2_first_valid_node(f->inocache->nodes);
129
130 if (!valid_ref && (f->inocache->ino != 1))
131 printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino);
132
133 while (valid_ref) {
134 /* We can hold a pointer to a non-obsolete node without the spinlock,
135 but _obsolete_ nodes may disappear at any time, if the block
136 they're in gets erased. So if we mark 'ref' obsolete while we're
137 not holding the lock, it can go away immediately. For that reason,
138 we find the next valid node first, before processing 'ref'.
139 */
140 ref = valid_ref;
141 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
142 spin_unlock(&c->erase_completion_lock);
143
144 cond_resched();
145
146 /* FIXME: point() */
147 err = jffs2_flash_read(c, (ref_offset(ref)),
148 min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node)),
149 &retlen, (void *)&node);
150 if (err) {
151 printk(KERN_WARNING "error %d reading node at 0x%08x in get_inode_nodes()\n", err, ref_offset(ref));
152 goto free_out;
153 }
154
155
156 /* Check we've managed to read at least the common node header */
157 if (retlen < min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node.u))) {
158 printk(KERN_WARNING "short read in get_inode_nodes()\n");
159 err = -EIO;
160 goto free_out;
161 }
162
163 switch (je16_to_cpu(node.u.nodetype)) {
164 case JFFS2_NODETYPE_DIRENT:
165 D1(printk(KERN_DEBUG "Node at %08x (%d) is a dirent node\n", ref_offset(ref), ref_flags(ref)));
166 if (ref_flags(ref) == REF_UNCHECKED) {
167 printk(KERN_WARNING "BUG: Dirent node at 0x%08x never got checked? How?\n", ref_offset(ref));
168 BUG();
169 }
170 if (retlen < sizeof(node.d)) {
171 printk(KERN_WARNING "short read in get_inode_nodes()\n");
172 err = -EIO;
173 goto free_out;
174 }
175 /* sanity check */
176 if (PAD((node.d.nsize + sizeof (node.d))) != PAD(je32_to_cpu (node.d.totlen))) {
177 printk(KERN_NOTICE "jffs2_get_inode_nodes(): Illegal nsize in node at 0x%08x: nsize 0x%02x, totlen %04x\n",
178 ref_offset(ref), node.d.nsize, je32_to_cpu(node.d.totlen));
179 jffs2_mark_node_obsolete(c, ref);
180 spin_lock(&c->erase_completion_lock);
181 continue;
182 }
183 if (je32_to_cpu(node.d.version) > *highest_version)
184 *highest_version = je32_to_cpu(node.d.version);
185 if (ref_obsolete(ref)) {
186 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
187 printk(KERN_ERR "Dirent node at 0x%08x became obsolete while we weren't looking\n",
188 ref_offset(ref));
189 BUG();
190 }
191
192 fd = jffs2_alloc_full_dirent(node.d.nsize+1);
193 if (!fd) {
194 err = -ENOMEM;
195 goto free_out;
196 }
197 fd->raw = ref;
198 fd->version = je32_to_cpu(node.d.version);
199 fd->ino = je32_to_cpu(node.d.ino);
200 fd->type = node.d.type;
201
202 /* Pick out the mctime of the latest dirent */
203 if(fd->version > *mctime_ver) {
204 *mctime_ver = fd->version;
205 *latest_mctime = je32_to_cpu(node.d.mctime);
206 }
207
208 /* memcpy as much of the name as possible from the raw
209 dirent we've already read from the flash
210 */
211 if (retlen > sizeof(struct jffs2_raw_dirent))
212 memcpy(&fd->name[0], &node.d.name[0], min_t(uint32_t, node.d.nsize, (retlen-sizeof(struct jffs2_raw_dirent))));
213
214 /* Do we need to copy any more of the name directly
215 from the flash?
216 */
217 if (node.d.nsize + sizeof(struct jffs2_raw_dirent) > retlen) {
218 /* FIXME: point() */
219 int already = retlen - sizeof(struct jffs2_raw_dirent);
220
221 err = jffs2_flash_read(c, (ref_offset(ref)) + retlen,
222 node.d.nsize - already, &retlen, &fd->name[already]);
223 if (!err && retlen != node.d.nsize - already)
224 err = -EIO;
225
226 if (err) {
227 printk(KERN_WARNING "Read remainder of name in jffs2_get_inode_nodes(): error %d\n", err);
228 jffs2_free_full_dirent(fd);
229 goto free_out;
230 }
231 }
232 fd->nhash = full_name_hash(fd->name, node.d.nsize);
233 fd->next = NULL;
234 fd->name[node.d.nsize] = '\0';
235 /* Wheee. We now have a complete jffs2_full_dirent structure, with
236 the name in it and everything. Link it into the list
237 */
238 D1(printk(KERN_DEBUG "Adding fd \"%s\", ino #%u\n", fd->name, fd->ino));
239 jffs2_add_fd_to_list(c, fd, &ret_fd);
240 break;
241
242 case JFFS2_NODETYPE_INODE:
243 D1(printk(KERN_DEBUG "Node at %08x (%d) is a data node\n", ref_offset(ref), ref_flags(ref)));
244 if (retlen < sizeof(node.i)) {
245 printk(KERN_WARNING "read too short for dnode\n");
246 err = -EIO;
247 goto free_out;
248 }
249 if (je32_to_cpu(node.i.version) > *highest_version)
250 *highest_version = je32_to_cpu(node.i.version);
251 D1(printk(KERN_DEBUG "version %d, highest_version now %d\n", je32_to_cpu(node.i.version), *highest_version));
252
253 if (ref_obsolete(ref)) {
254 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
255 printk(KERN_ERR "Inode node at 0x%08x became obsolete while we weren't looking\n",
256 ref_offset(ref));
257 BUG();
258 }
259
260 /* If we've never checked the CRCs on this node, check them now. */
261 if (ref_flags(ref) == REF_UNCHECKED) {
262 uint32_t crc, len;
263 struct jffs2_eraseblock *jeb;
264
265 crc = crc32(0, &node, sizeof(node.i)-8);
266 if (crc != je32_to_cpu(node.i.node_crc)) {
267 printk(KERN_NOTICE "jffs2_get_inode_nodes(): CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n",
268 ref_offset(ref), je32_to_cpu(node.i.node_crc), crc);
269 jffs2_mark_node_obsolete(c, ref);
270 spin_lock(&c->erase_completion_lock);
271 continue;
272 }
273
274 /* sanity checks */
275 if ( je32_to_cpu(node.i.offset) > je32_to_cpu(node.i.isize) ||
276 PAD(je32_to_cpu(node.i.csize) + sizeof (node.i)) != PAD(je32_to_cpu(node.i.totlen))) {
277 printk(KERN_NOTICE "jffs2_get_inode_nodes(): Inode corrupted at 0x%08x, totlen %d, #ino %d, version %d, isize %d, csize %d, dsize %d \n",
278 ref_offset(ref), je32_to_cpu(node.i.totlen), je32_to_cpu(node.i.ino),
279 je32_to_cpu(node.i.version), je32_to_cpu(node.i.isize),
280 je32_to_cpu(node.i.csize), je32_to_cpu(node.i.dsize));
281 jffs2_mark_node_obsolete(c, ref);
282 spin_lock(&c->erase_completion_lock);
283 continue;
284 }
285
286 if (node.i.compr != JFFS2_COMPR_ZERO && je32_to_cpu(node.i.csize)) {
287 unsigned char *buf=NULL;
288 uint32_t pointed = 0;
289 #ifndef __ECOS
290 if (c->mtd->point) {
291 err = c->mtd->point (c->mtd, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize),
292 &retlen, &buf);
293 if (!err && retlen < je32_to_cpu(node.i.csize)) {
294 D1(printk(KERN_DEBUG "MTD point returned len too short: 0x%zx\n", retlen));
295 c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize));
296 } else if (err){
297 D1(printk(KERN_DEBUG "MTD point failed %d\n", err));
298 } else
299 pointed = 1; /* succefully pointed to device */
300 }
301 #endif
302 if(!pointed){
303 buf = kmalloc(je32_to_cpu(node.i.csize), GFP_KERNEL);
304 if (!buf)
305 return -ENOMEM;
306
307 err = jffs2_flash_read(c, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize),
308 &retlen, buf);
309 if (!err && retlen != je32_to_cpu(node.i.csize))
310 err = -EIO;
311 if (err) {
312 kfree(buf);
313 return err;
314 }
315 }
316 crc = crc32(0, buf, je32_to_cpu(node.i.csize));
317 if(!pointed)
318 kfree(buf);
319 #ifndef __ECOS
320 else
321 c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize));
322 #endif
323
324 if (crc != je32_to_cpu(node.i.data_crc)) {
325 printk(KERN_NOTICE "jffs2_get_inode_nodes(): Data CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n",
326 ref_offset(ref), je32_to_cpu(node.i.data_crc), crc);
327 jffs2_mark_node_obsolete(c, ref);
328 spin_lock(&c->erase_completion_lock);
329 continue;
330 }
331
332 }
333
334 /* Mark the node as having been checked and fix the accounting accordingly */
335 spin_lock(&c->erase_completion_lock);
336 jeb = &c->blocks[ref->flash_offset / c->sector_size];
337 len = ref_totlen(c, jeb, ref);
338
339 jeb->used_size += len;
340 jeb->unchecked_size -= len;
341 c->used_size += len;
342 c->unchecked_size -= len;
343
344 /* If node covers at least a whole page, or if it starts at the
345 beginning of a page and runs to the end of the file, or if
346 it's a hole node, mark it REF_PRISTINE, else REF_NORMAL.
347
348 If it's actually overlapped, it'll get made NORMAL (or OBSOLETE)
349 when the overlapping node(s) get added to the tree anyway.
350 */
351 if ((je32_to_cpu(node.i.dsize) >= PAGE_CACHE_SIZE) ||
352 ( ((je32_to_cpu(node.i.offset)&(PAGE_CACHE_SIZE-1))==0) &&
353 (je32_to_cpu(node.i.dsize)+je32_to_cpu(node.i.offset) == je32_to_cpu(node.i.isize)))) {
354 D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_PRISTINE\n", ref_offset(ref)));
355 ref->flash_offset = ref_offset(ref) | REF_PRISTINE;
356 } else {
357 D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_NORMAL\n", ref_offset(ref)));
358 ref->flash_offset = ref_offset(ref) | REF_NORMAL;
359 }
360 spin_unlock(&c->erase_completion_lock);
361 }
362
363 tn = jffs2_alloc_tmp_dnode_info();
364 if (!tn) {
365 D1(printk(KERN_DEBUG "alloc tn failed\n"));
366 err = -ENOMEM;
367 goto free_out;
368 }
369
370 tn->fn = jffs2_alloc_full_dnode();
371 if (!tn->fn) {
372 D1(printk(KERN_DEBUG "alloc fn failed\n"));
373 err = -ENOMEM;
374 jffs2_free_tmp_dnode_info(tn);
375 goto free_out;
376 }
377 tn->version = je32_to_cpu(node.i.version);
378 tn->fn->ofs = je32_to_cpu(node.i.offset);
379 /* There was a bug where we wrote hole nodes out with
380 csize/dsize swapped. Deal with it */
381 if (node.i.compr == JFFS2_COMPR_ZERO && !je32_to_cpu(node.i.dsize) && je32_to_cpu(node.i.csize))
382 tn->fn->size = je32_to_cpu(node.i.csize);
383 else // normal case...
384 tn->fn->size = je32_to_cpu(node.i.dsize);
385 tn->fn->raw = ref;
386 D1(printk(KERN_DEBUG "dnode @%08x: ver %u, offset %04x, dsize %04x\n",
387 ref_offset(ref), je32_to_cpu(node.i.version),
388 je32_to_cpu(node.i.offset), je32_to_cpu(node.i.dsize)));
389 jffs2_add_tn_to_list(tn, &ret_tn);
390 break;
391
392 default:
393 if (ref_flags(ref) == REF_UNCHECKED) {
394 struct jffs2_eraseblock *jeb;
395 uint32_t len;
396
397 printk(KERN_ERR "Eep. Unknown node type %04x at %08x was marked REF_UNCHECKED\n",
398 je16_to_cpu(node.u.nodetype), ref_offset(ref));
399
400 /* Mark the node as having been checked and fix the accounting accordingly */
401 spin_lock(&c->erase_completion_lock);
402 jeb = &c->blocks[ref->flash_offset / c->sector_size];
403 len = ref_totlen(c, jeb, ref);
404
405 jeb->used_size += len;
406 jeb->unchecked_size -= len;
407 c->used_size += len;
408 c->unchecked_size -= len;
409
410 mark_ref_normal(ref);
411 spin_unlock(&c->erase_completion_lock);
412 }
413 node.u.nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(node.u.nodetype));
414 if (crc32(0, &node, sizeof(struct jffs2_unknown_node)-4) != je32_to_cpu(node.u.hdr_crc)) {
415 /* Hmmm. This should have been caught at scan time. */
416 printk(KERN_ERR "Node header CRC failed at %08x. But it must have been OK earlier.\n",
417 ref_offset(ref));
418 printk(KERN_ERR "Node was: { %04x, %04x, %08x, %08x }\n",
419 je16_to_cpu(node.u.magic), je16_to_cpu(node.u.nodetype), je32_to_cpu(node.u.totlen),
420 je32_to_cpu(node.u.hdr_crc));
421 jffs2_mark_node_obsolete(c, ref);
422 } else switch(je16_to_cpu(node.u.nodetype) & JFFS2_COMPAT_MASK) {
423 case JFFS2_FEATURE_INCOMPAT:
424 printk(KERN_NOTICE "Unknown INCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
425 /* EEP */
426 BUG();
427 break;
428 case JFFS2_FEATURE_ROCOMPAT:
429 printk(KERN_NOTICE "Unknown ROCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
430 if (!(c->flags & JFFS2_SB_FLAG_RO))
431 BUG();
432 break;
433 case JFFS2_FEATURE_RWCOMPAT_COPY:
434 printk(KERN_NOTICE "Unknown RWCOMPAT_COPY nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
435 break;
436 case JFFS2_FEATURE_RWCOMPAT_DELETE:
437 printk(KERN_NOTICE "Unknown RWCOMPAT_DELETE nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
438 jffs2_mark_node_obsolete(c, ref);
439 break;
440 }
441
442 }
443 spin_lock(&c->erase_completion_lock);
444
445 }
446 spin_unlock(&c->erase_completion_lock);
447 *tnp = ret_tn;
448 *fdp = ret_fd;
449
450 return 0;
451
452 free_out:
453 jffs2_free_tmp_dnode_info_list(ret_tn);
454 jffs2_free_full_dirent_list(ret_fd);
455 return err;
456 }
457
458 void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state)
459 {
460 spin_lock(&c->inocache_lock);
461 ic->state = state;
462 wake_up(&c->inocache_wq);
463 spin_unlock(&c->inocache_lock);
464 }
465
466 /* During mount, this needs no locking. During normal operation, its
467 callers want to do other stuff while still holding the inocache_lock.
468 Rather than introducing special case get_ino_cache functions or
469 callbacks, we just let the caller do the locking itself. */
470
471 struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
472 {
473 struct jffs2_inode_cache *ret;
474
475 D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino));
476
477 ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
478 while (ret && ret->ino < ino) {
479 ret = ret->next;
480 }
481
482 if (ret && ret->ino != ino)
483 ret = NULL;
484
485 D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino));
486 return ret;
487 }
488
489 void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
490 {
491 struct jffs2_inode_cache **prev;
492
493 spin_lock(&c->inocache_lock);
494 if (!new->ino)
495 new->ino = ++c->highest_ino;
496
497 D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
498
499 prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
500
501 while ((*prev) && (*prev)->ino < new->ino) {
502 prev = &(*prev)->next;
503 }
504 new->next = *prev;
505 *prev = new;
506
507 spin_unlock(&c->inocache_lock);
508 }
509
510 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
511 {
512 struct jffs2_inode_cache **prev;
513 D1(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
514 spin_lock(&c->inocache_lock);
515
516 prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
517
518 while ((*prev) && (*prev)->ino < old->ino) {
519 prev = &(*prev)->next;
520 }
521 if ((*prev) == old) {
522 *prev = old->next;
523 }
524
525 /* Free it now unless it's in READING or CLEARING state, which
526 are the transitions upon read_inode() and clear_inode(). The
527 rest of the time we know nobody else is looking at it, and
528 if it's held by read_inode() or clear_inode() they'll free it
529 for themselves. */
530 if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
531 jffs2_free_inode_cache(old);
532
533 spin_unlock(&c->inocache_lock);
534 }
535
536 void jffs2_free_ino_caches(struct jffs2_sb_info *c)
537 {
538 int i;
539 struct jffs2_inode_cache *this, *next;
540
541 for (i=0; i<INOCACHE_HASHSIZE; i++) {
542 this = c->inocache_list[i];
543 while (this) {
544 next = this->next;
545 jffs2_free_inode_cache(this);
546 this = next;
547 }
548 c->inocache_list[i] = NULL;
549 }
550 }
551
552 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
553 {
554 int i;
555 struct jffs2_raw_node_ref *this, *next;
556
557 for (i=0; i<c->nr_blocks; i++) {
558 this = c->blocks[i].first_node;
559 while(this) {
560 next = this->next_phys;
561 jffs2_free_raw_node_ref(this);
562 this = next;
563 }
564 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
565 }
566 }
567
568 struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
569 {
570 /* The common case in lookup is that there will be a node
571 which precisely matches. So we go looking for that first */
572 struct rb_node *next;
573 struct jffs2_node_frag *prev = NULL;
574 struct jffs2_node_frag *frag = NULL;
575
576 D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
577
578 next = fragtree->rb_node;
579
580 while(next) {
581 frag = rb_entry(next, struct jffs2_node_frag, rb);
582
583 D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
584 frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
585 if (frag->ofs + frag->size <= offset) {
586 D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
587 frag->ofs, frag->ofs+frag->size));
588 /* Remember the closest smaller match on the way down */
589 if (!prev || frag->ofs > prev->ofs)
590 prev = frag;
591 next = frag->rb.rb_right;
592 } else if (frag->ofs > offset) {
593 D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
594 frag->ofs, frag->ofs+frag->size));
595 next = frag->rb.rb_left;
596 } else {
597 D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n",
598 frag->ofs, frag->ofs+frag->size));
599 return frag;
600 }
601 }
602
603 /* Exact match not found. Go back up looking at each parent,
604 and return the closest smaller one */
605
606 if (prev)
607 D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
608 prev->ofs, prev->ofs+prev->size));
609 else
610 D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
611
612 return prev;
613 }
614
615 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
616 they're killed. */
617 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
618 {
619 struct jffs2_node_frag *frag;
620 struct jffs2_node_frag *parent;
621
622 if (!root->rb_node)
623 return;
624
625 frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
626
627 while(frag) {
628 if (frag->rb.rb_left) {
629 D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
630 frag, frag->ofs, frag->ofs+frag->size));
631 frag = frag_left(frag);
632 continue;
633 }
634 if (frag->rb.rb_right) {
635 D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
636 frag, frag->ofs, frag->ofs+frag->size));
637 frag = frag_right(frag);
638 continue;
639 }
640
641 D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
642 frag->ofs, frag->ofs+frag->size, frag->node,
643 frag->node?frag->node->frags:0));
644
645 if (frag->node && !(--frag->node->frags)) {
646 /* Not a hole, and it's the final remaining frag
647 of this node. Free the node */
648 if (c)
649 jffs2_mark_node_obsolete(c, frag->node->raw);
650
651 jffs2_free_full_dnode(frag->node);
652 }
653 parent = frag_parent(frag);
654 if (parent) {
655 if (frag_left(parent) == frag)
656 parent->rb.rb_left = NULL;
657 else
658 parent->rb.rb_right = NULL;
659 }
660
661 jffs2_free_node_frag(frag);
662 frag = parent;
663
664 cond_resched();
665 }
666 }
667
668 void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
669 {
670 struct rb_node *parent = &base->rb;
671 struct rb_node **link = &parent;
672
673 D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
674 newfrag->ofs, newfrag->ofs+newfrag->size, base));
675
676 while (*link) {
677 parent = *link;
678 base = rb_entry(parent, struct jffs2_node_frag, rb);
679
680 D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs));
681 if (newfrag->ofs > base->ofs)
682 link = &base->rb.rb_right;
683 else if (newfrag->ofs < base->ofs)
684 link = &base->rb.rb_left;
685 else {
686 printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
687 BUG();
688 }
689 }
690
691 rb_link_node(&newfrag->rb, &base->rb, link);
692 }
Community contributions to the Openmoko Kernel