aboutsummaryrefslogtreecommitdiffstats
path: root/fs/jffs2/nodelist.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/jffs2/nodelist.c')
-rw-r--r--fs/jffs2/nodelist.c681
1 files changed, 681 insertions, 0 deletions
diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
new file mode 100644
index 000000000000..cd6a8bd13e0b
--- /dev/null
+++ b/fs/jffs2/nodelist.c
@@ -0,0 +1,681 @@
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.90 2004/12/08 17:59:20 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
24void 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*/
61static 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
72static 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
84static 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' */
96static 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
110int 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)
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
458void 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
471struct 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
489void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
490{
491 struct jffs2_inode_cache **prev;
492 D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
493 spin_lock(&c->inocache_lock);
494
495 prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
496
497 while ((*prev) && (*prev)->ino < new->ino) {
498 prev = &(*prev)->next;
499 }
500 new->next = *prev;
501 *prev = new;
502
503 spin_unlock(&c->inocache_lock);
504}
505
506void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
507{
508 struct jffs2_inode_cache **prev;
509 D2(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
510 spin_lock(&c->inocache_lock);
511
512 prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
513
514 while ((*prev) && (*prev)->ino < old->ino) {
515 prev = &(*prev)->next;
516 }
517 if ((*prev) == old) {
518 *prev = old->next;
519 }
520
521 spin_unlock(&c->inocache_lock);
522}
523
524void jffs2_free_ino_caches(struct jffs2_sb_info *c)
525{
526 int i;
527 struct jffs2_inode_cache *this, *next;
528
529 for (i=0; i<INOCACHE_HASHSIZE; i++) {
530 this = c->inocache_list[i];
531 while (this) {
532 next = this->next;
533 D2(printk(KERN_DEBUG "jffs2_free_ino_caches: Freeing ino #%u at %p\n", this->ino, this));
534 jffs2_free_inode_cache(this);
535 this = next;
536 }
537 c->inocache_list[i] = NULL;
538 }
539}
540
541void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
542{
543 int i;
544 struct jffs2_raw_node_ref *this, *next;
545
546 for (i=0; i<c->nr_blocks; i++) {
547 this = c->blocks[i].first_node;
548 while(this) {
549 next = this->next_phys;
550 jffs2_free_raw_node_ref(this);
551 this = next;
552 }
553 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
554 }
555}
556
557struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
558{
559 /* The common case in lookup is that there will be a node
560 which precisely matches. So we go looking for that first */
561 struct rb_node *next;
562 struct jffs2_node_frag *prev = NULL;
563 struct jffs2_node_frag *frag = NULL;
564
565 D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
566
567 next = fragtree->rb_node;
568
569 while(next) {
570 frag = rb_entry(next, struct jffs2_node_frag, rb);
571
572 D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
573 frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
574 if (frag->ofs + frag->size <= offset) {
575 D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
576 frag->ofs, frag->ofs+frag->size));
577 /* Remember the closest smaller match on the way down */
578 if (!prev || frag->ofs > prev->ofs)
579 prev = frag;
580 next = frag->rb.rb_right;
581 } else if (frag->ofs > offset) {
582 D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
583 frag->ofs, frag->ofs+frag->size));
584 next = frag->rb.rb_left;
585 } else {
586 D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n",
587 frag->ofs, frag->ofs+frag->size));
588 return frag;
589 }
590 }
591
592 /* Exact match not found. Go back up looking at each parent,
593 and return the closest smaller one */
594
595 if (prev)
596 D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
597 prev->ofs, prev->ofs+prev->size));
598 else
599 D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
600
601 return prev;
602}
603
604/* Pass 'c' argument to indicate that nodes should be marked obsolete as
605 they're killed. */
606void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
607{
608 struct jffs2_node_frag *frag;
609 struct jffs2_node_frag *parent;
610
611 if (!root->rb_node)
612 return;
613
614 frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
615
616 while(frag) {
617 if (frag->rb.rb_left) {
618 D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
619 frag, frag->ofs, frag->ofs+frag->size));
620 frag = frag_left(frag);
621 continue;
622 }
623 if (frag->rb.rb_right) {
624 D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
625 frag, frag->ofs, frag->ofs+frag->size));
626 frag = frag_right(frag);
627 continue;
628 }
629
630 D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
631 frag->ofs, frag->ofs+frag->size, frag->node,
632 frag->node?frag->node->frags:0));
633
634 if (frag->node && !(--frag->node->frags)) {
635 /* Not a hole, and it's the final remaining frag
636 of this node. Free the node */
637 if (c)
638 jffs2_mark_node_obsolete(c, frag->node->raw);
639
640 jffs2_free_full_dnode(frag->node);
641 }
642 parent = frag_parent(frag);
643 if (parent) {
644 if (frag_left(parent) == frag)
645 parent->rb.rb_left = NULL;
646 else
647 parent->rb.rb_right = NULL;
648 }
649
650 jffs2_free_node_frag(frag);
651 frag = parent;
652
653 cond_resched();
654 }
655}
656
657void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
658{
659 struct rb_node *parent = &base->rb;
660 struct rb_node **link = &parent;
661
662 D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
663 newfrag->ofs, newfrag->ofs+newfrag->size, base));
664
665 while (*link) {
666 parent = *link;
667 base = rb_entry(parent, struct jffs2_node_frag, rb);
668
669 D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs));
670 if (newfrag->ofs > base->ofs)
671 link = &base->rb.rb_right;
672 else if (newfrag->ofs < base->ofs)
673 link = &base->rb.rb_left;
674 else {
675 printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
676 BUG();
677 }
678 }
679
680 rb_link_node(&newfrag->rb, &base->rb, link);
681}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-02 21:34:56 -0500