nodelist.c (733802d974e5af42acb7cd61b16c0ce6dd03b7ed) nodelist.c (182ec4eee397543101a6db8906ed88727d3f7e53)
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 *
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.114 2005/09/21 13:28:35 dedekind Exp $
10 * $Id: nodelist.c,v 1.115 2005/11/07 11:14:40 gleixner 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;
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
27
28 dbg_dentlist("add dirent \"%s\", ino #%u\n", new->name, new->ino);
29
30 while ((*prev) && (*prev)->nhash <= new->nhash) {
31 if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) {
32 /* Duplicate. Free one */
33 if (new->version < (*prev)->version) {
34 dbg_dentlist("Eep! Marking new dirent node is obsolete, old is \"%s\", ino #%u\n",
35 (*prev)->name, (*prev)->ino);

--- 34 unchanged lines hidden (view full) ---

70 frag_erase(frag, list);
71 jffs2_obsolete_node_frag(c, frag);
72 frag = next;
73 }
74
75 if (size == 0)
76 return;
77
28 dbg_dentlist("add dirent \"%s\", ino #%u\n", new->name, new->ino);
29
30 while ((*prev) && (*prev)->nhash <= new->nhash) {
31 if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) {
32 /* Duplicate. Free one */
33 if (new->version < (*prev)->version) {
34 dbg_dentlist("Eep! Marking new dirent node is obsolete, old is \"%s\", ino #%u\n",
35 (*prev)->name, (*prev)->ino);

--- 34 unchanged lines hidden (view full) ---

70 frag_erase(frag, list);
71 jffs2_obsolete_node_frag(c, frag);
72 frag = next;
73 }
74
75 if (size == 0)
76 return;
77
78 /*
78 /*
79 * If the last fragment starts at the RAM page boundary, it is
80 * REF_PRISTINE irrespective of its size.
81 */
82 frag = frag_last(list);
83 if (frag->node && (frag->ofs & (PAGE_CACHE_SIZE - 1)) == 0) {
84 dbg_fragtree2("marking the last fragment 0x%08x-0x%08x REF_PRISTINE.\n",
79 * If the last fragment starts at the RAM page boundary, it is
80 * REF_PRISTINE irrespective of its size.
81 */
82 frag = frag_last(list);
83 if (frag->node && (frag->ofs & (PAGE_CACHE_SIZE - 1)) == 0) {
84 dbg_fragtree2("marking the last fragment 0x%08x-0x%08x REF_PRISTINE.\n",
85 frag->ofs, frag->ofs + frag->size);
85 frag->ofs, frag->ofs + frag->size);
86 frag->node->raw->flash_offset = ref_offset(frag->node->raw) | REF_PRISTINE;
87 }
88}
89
90void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this)
91{
92 if (this->node) {
93 this->node->frags--;
94 if (!this->node->frags) {
95 /* The node has no valid frags left. It's totally obsoleted */
96 dbg_fragtree2("marking old node @0x%08x (0x%04x-0x%04x) obsolete\n",
97 ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size);
98 jffs2_mark_node_obsolete(c, this->node->raw);
99 jffs2_free_full_dnode(this->node);
100 } else {
101 dbg_fragtree2("marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n",
102 ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, this->node->frags);
103 mark_ref_normal(this->node->raw);
104 }
86 frag->node->raw->flash_offset = ref_offset(frag->node->raw) | REF_PRISTINE;
87 }
88}
89
90void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this)
91{
92 if (this->node) {
93 this->node->frags--;
94 if (!this->node->frags) {
95 /* The node has no valid frags left. It's totally obsoleted */
96 dbg_fragtree2("marking old node @0x%08x (0x%04x-0x%04x) obsolete\n",
97 ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size);
98 jffs2_mark_node_obsolete(c, this->node->raw);
99 jffs2_free_full_dnode(this->node);
100 } else {
101 dbg_fragtree2("marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n",
102 ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, this->node->frags);
103 mark_ref_normal(this->node->raw);
104 }
105
105
106 }
107 jffs2_free_node_frag(this);
108}
109
110static void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
111{
112 struct rb_node *parent = &base->rb;
113 struct rb_node **link = &parent;
114
115 dbg_fragtree2("insert frag (0x%04x-0x%04x)\n", newfrag->ofs, newfrag->ofs + newfrag->size);
116
117 while (*link) {
118 parent = *link;
119 base = rb_entry(parent, struct jffs2_node_frag, rb);
106 }
107 jffs2_free_node_frag(this);
108}
109
110static void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
111{
112 struct rb_node *parent = &base->rb;
113 struct rb_node **link = &parent;
114
115 dbg_fragtree2("insert frag (0x%04x-0x%04x)\n", newfrag->ofs, newfrag->ofs + newfrag->size);
116
117 while (*link) {
118 parent = *link;
119 base = rb_entry(parent, struct jffs2_node_frag, rb);
120
120
121 if (newfrag->ofs > base->ofs)
122 link = &base->rb.rb_right;
123 else if (newfrag->ofs < base->ofs)
124 link = &base->rb.rb_left;
125 else {
126 JFFS2_ERROR("duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
127 BUG();
128 }
129 }
130
131 rb_link_node(&newfrag->rb, &base->rb, link);
132}
133
134/*
135 * Allocate and initializes a new fragment.
136 */
137static inline struct jffs2_node_frag * new_fragment(struct jffs2_full_dnode *fn, uint32_t ofs, uint32_t size)
138{
139 struct jffs2_node_frag *newfrag;
121 if (newfrag->ofs > base->ofs)
122 link = &base->rb.rb_right;
123 else if (newfrag->ofs < base->ofs)
124 link = &base->rb.rb_left;
125 else {
126 JFFS2_ERROR("duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
127 BUG();
128 }
129 }
130
131 rb_link_node(&newfrag->rb, &base->rb, link);
132}
133
134/*
135 * Allocate and initializes a new fragment.
136 */
137static inline struct jffs2_node_frag * new_fragment(struct jffs2_full_dnode *fn, uint32_t ofs, uint32_t size)
138{
139 struct jffs2_node_frag *newfrag;
140
140
141 newfrag = jffs2_alloc_node_frag();
142 if (likely(newfrag)) {
143 newfrag->ofs = ofs;
144 newfrag->size = size;
145 newfrag->node = fn;
146 } else {
147 JFFS2_ERROR("cannot allocate a jffs2_node_frag object\n");
148 }

--- 15 unchanged lines hidden (view full) ---

164
165 holefrag= new_fragment(NULL, lastend, newfrag->node->ofs - lastend);
166 if (unlikely(!holefrag)) {
167 jffs2_free_node_frag(newfrag);
168 return -ENOMEM;
169 }
170
171 if (this) {
141 newfrag = jffs2_alloc_node_frag();
142 if (likely(newfrag)) {
143 newfrag->ofs = ofs;
144 newfrag->size = size;
145 newfrag->node = fn;
146 } else {
147 JFFS2_ERROR("cannot allocate a jffs2_node_frag object\n");
148 }

--- 15 unchanged lines hidden (view full) ---

164
165 holefrag= new_fragment(NULL, lastend, newfrag->node->ofs - lastend);
166 if (unlikely(!holefrag)) {
167 jffs2_free_node_frag(newfrag);
168 return -ENOMEM;
169 }
170
171 if (this) {
172 /* By definition, the 'this' node has no right-hand child,
172 /* By definition, the 'this' node has no right-hand child,
173 because there are no frags with offset greater than it.
174 So that's where we want to put the hole */
175 dbg_fragtree2("add hole frag %#04x-%#04x on the right of the new frag.\n",
176 holefrag->ofs, holefrag->ofs + holefrag->size);
177 rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
178 } else {
179 dbg_fragtree2("Add hole frag %#04x-%#04x to the root of the tree.\n",
180 holefrag->ofs, holefrag->ofs + holefrag->size);
181 rb_link_node(&holefrag->rb, NULL, &root->rb_node);
182 }
183 rb_insert_color(&holefrag->rb, root);
184 this = holefrag;
185 }
173 because there are no frags with offset greater than it.
174 So that's where we want to put the hole */
175 dbg_fragtree2("add hole frag %#04x-%#04x on the right of the new frag.\n",
176 holefrag->ofs, holefrag->ofs + holefrag->size);
177 rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
178 } else {
179 dbg_fragtree2("Add hole frag %#04x-%#04x to the root of the tree.\n",
180 holefrag->ofs, holefrag->ofs + holefrag->size);
181 rb_link_node(&holefrag->rb, NULL, &root->rb_node);
182 }
183 rb_insert_color(&holefrag->rb, root);
184 this = holefrag;
185 }
186
186
187 if (this) {
187 if (this) {
188 /* By definition, the 'this' node has no right-hand child,
188 /* By definition, the 'this' node has no right-hand child,
189 because there are no frags with offset greater than it.
190 So that's where we want to put new fragment */
191 dbg_fragtree2("add the new node at the right\n");
189 because there are no frags with offset greater than it.
190 So that's where we want to put new fragment */
191 dbg_fragtree2("add the new node at the right\n");
192 rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
192 rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
193 } else {
194 dbg_fragtree2("insert the new node at the root of the tree\n");
195 rb_link_node(&newfrag->rb, NULL, &root->rb_node);
196 }
197 rb_insert_color(&newfrag->rb, root);
198
199 return 0;
200}

--- 10 unchanged lines hidden (view full) ---

211 if (this) {
212 dbg_fragtree2("lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
213 this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);
214 lastend = this->ofs + this->size;
215 } else {
216 dbg_fragtree2("lookup gave no frag\n");
217 lastend = 0;
218 }
193 } else {
194 dbg_fragtree2("insert the new node at the root of the tree\n");
195 rb_link_node(&newfrag->rb, NULL, &root->rb_node);
196 }
197 rb_insert_color(&newfrag->rb, root);
198
199 return 0;
200}

--- 10 unchanged lines hidden (view full) ---

211 if (this) {
212 dbg_fragtree2("lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
213 this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);
214 lastend = this->ofs + this->size;
215 } else {
216 dbg_fragtree2("lookup gave no frag\n");
217 lastend = 0;
218 }
219
219
220 /* See if we ran off the end of the fragtree */
221 if (lastend <= newfrag->ofs) {
222 /* We did */
223
224 /* Check if 'this' node was on the same page as the new node.
225 If so, both 'this' and the new node get marked REF_NORMAL so
226 the GC can take a look.
227 */

--- 10 unchanged lines hidden (view full) ---

238 dbg_fragtree2("dealing with frag %u-%u, phys %#08x(%d).\n",
239 this->ofs, this->ofs + this->size,
240 ref_offset(this->node->raw), ref_flags(this->node->raw));
241 else
242 dbg_fragtree2("dealing with hole frag %u-%u.\n",
243 this->ofs, this->ofs + this->size);
244
245 /* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes,
220 /* See if we ran off the end of the fragtree */
221 if (lastend <= newfrag->ofs) {
222 /* We did */
223
224 /* Check if 'this' node was on the same page as the new node.
225 If so, both 'this' and the new node get marked REF_NORMAL so
226 the GC can take a look.
227 */

--- 10 unchanged lines hidden (view full) ---

238 dbg_fragtree2("dealing with frag %u-%u, phys %#08x(%d).\n",
239 this->ofs, this->ofs + this->size,
240 ref_offset(this->node->raw), ref_flags(this->node->raw));
241 else
242 dbg_fragtree2("dealing with hole frag %u-%u.\n",
243 this->ofs, this->ofs + this->size);
244
245 /* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes,
246 * - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs
246 * - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs
247 */
248 if (newfrag->ofs > this->ofs) {
249 /* This node isn't completely obsoleted. The start of it remains valid */
250
251 /* Mark the new node and the partially covered node REF_NORMAL -- let
252 the GC take a look at them */
253 mark_ref_normal(newfrag->node->raw);
254 if (this->node)
255 mark_ref_normal(this->node->raw);
256
257 if (this->ofs + this->size > newfrag->ofs + newfrag->size) {
258 /* The new node splits 'this' frag into two */
259 struct jffs2_node_frag *newfrag2;
260
261 if (this->node)
262 dbg_fragtree2("split old frag 0x%04x-0x%04x, phys 0x%08x\n",
263 this->ofs, this->ofs+this->size, ref_offset(this->node->raw));
247 */
248 if (newfrag->ofs > this->ofs) {
249 /* This node isn't completely obsoleted. The start of it remains valid */
250
251 /* Mark the new node and the partially covered node REF_NORMAL -- let
252 the GC take a look at them */
253 mark_ref_normal(newfrag->node->raw);
254 if (this->node)
255 mark_ref_normal(this->node->raw);
256
257 if (this->ofs + this->size > newfrag->ofs + newfrag->size) {
258 /* The new node splits 'this' frag into two */
259 struct jffs2_node_frag *newfrag2;
260
261 if (this->node)
262 dbg_fragtree2("split old frag 0x%04x-0x%04x, phys 0x%08x\n",
263 this->ofs, this->ofs+this->size, ref_offset(this->node->raw));
264 else
264 else
265 dbg_fragtree2("split old hole frag 0x%04x-0x%04x\n",
266 this->ofs, this->ofs+this->size);
265 dbg_fragtree2("split old hole frag 0x%04x-0x%04x\n",
266 this->ofs, this->ofs+this->size);
267
267
268 /* New second frag pointing to this's node */
269 newfrag2 = new_fragment(this->node, newfrag->ofs + newfrag->size,
270 this->ofs + this->size - newfrag->ofs - newfrag->size);
271 if (unlikely(!newfrag2))
272 return -ENOMEM;
273 if (this->node)
274 this->node->frags++;
275
276 /* Adjust size of original 'this' */
277 this->size = newfrag->ofs - this->ofs;
278
279 /* Now, we know there's no node with offset
280 greater than this->ofs but smaller than
281 newfrag2->ofs or newfrag->ofs, for obvious
282 reasons. So we can do a tree insert from
283 'this' to insert newfrag, and a tree insert
284 from newfrag to insert newfrag2. */
285 jffs2_fragtree_insert(newfrag, this);
286 rb_insert_color(&newfrag->rb, root);
268 /* New second frag pointing to this's node */
269 newfrag2 = new_fragment(this->node, newfrag->ofs + newfrag->size,
270 this->ofs + this->size - newfrag->ofs - newfrag->size);
271 if (unlikely(!newfrag2))
272 return -ENOMEM;
273 if (this->node)
274 this->node->frags++;
275
276 /* Adjust size of original 'this' */
277 this->size = newfrag->ofs - this->ofs;
278
279 /* Now, we know there's no node with offset
280 greater than this->ofs but smaller than
281 newfrag2->ofs or newfrag->ofs, for obvious
282 reasons. So we can do a tree insert from
283 'this' to insert newfrag, and a tree insert
284 from newfrag to insert newfrag2. */
285 jffs2_fragtree_insert(newfrag, this);
286 rb_insert_color(&newfrag->rb, root);
287
287
288 jffs2_fragtree_insert(newfrag2, newfrag);
289 rb_insert_color(&newfrag2->rb, root);
288 jffs2_fragtree_insert(newfrag2, newfrag);
289 rb_insert_color(&newfrag2->rb, root);
290
290
291 return 0;
292 }
293 /* New node just reduces 'this' frag in size, doesn't split it */
294 this->size = newfrag->ofs - this->ofs;
295
296 /* Again, we know it lives down here in the tree */
297 jffs2_fragtree_insert(newfrag, this);
298 rb_insert_color(&newfrag->rb, root);
299 } else {
291 return 0;
292 }
293 /* New node just reduces 'this' frag in size, doesn't split it */
294 this->size = newfrag->ofs - this->ofs;
295
296 /* Again, we know it lives down here in the tree */
297 jffs2_fragtree_insert(newfrag, this);
298 rb_insert_color(&newfrag->rb, root);
299 } else {
300 /* New frag starts at the same point as 'this' used to. Replace
300 /* New frag starts at the same point as 'this' used to. Replace
301 it in the tree without doing a delete and insertion */
302 dbg_fragtree2("inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d\n",
303 newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, this, this->ofs, this->ofs+this->size);
301 it in the tree without doing a delete and insertion */
302 dbg_fragtree2("inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d\n",
303 newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, this, this->ofs, this->ofs+this->size);
304
304
305 rb_replace_node(&this->rb, &newfrag->rb, root);
305 rb_replace_node(&this->rb, &newfrag->rb, root);
306
306
307 if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {
308 dbg_fragtree2("obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size);
309 jffs2_obsolete_node_frag(c, this);
310 } else {
311 this->ofs += newfrag->size;
312 this->size -= newfrag->size;
313
314 jffs2_fragtree_insert(this, newfrag);
315 rb_insert_color(&this->rb, root);
316 return 0;
317 }
318 }
319 /* OK, now we have newfrag added in the correct place in the tree, but
307 if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {
308 dbg_fragtree2("obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size);
309 jffs2_obsolete_node_frag(c, this);
310 } else {
311 this->ofs += newfrag->size;
312 this->size -= newfrag->size;
313
314 jffs2_fragtree_insert(this, newfrag);
315 rb_insert_color(&this->rb, root);
316 return 0;
317 }
318 }
319 /* OK, now we have newfrag added in the correct place in the tree, but
320 frag_next(newfrag) may be a fragment which is overlapped by it
320 frag_next(newfrag) may be a fragment which is overlapped by it
321 */
322 while ((this = frag_next(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) {
323 /* 'this' frag is obsoleted completely. */
324 dbg_fragtree2("obsoleting node frag %p (%x-%x) and removing from tree\n",
325 this, this->ofs, this->ofs+this->size);
326 rb_erase(&this->rb, root);
327 jffs2_obsolete_node_frag(c, this);
328 }
321 */
322 while ((this = frag_next(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) {
323 /* 'this' frag is obsoleted completely. */
324 dbg_fragtree2("obsoleting node frag %p (%x-%x) and removing from tree\n",
325 this, this->ofs, this->ofs+this->size);
326 rb_erase(&this->rb, root);
327 jffs2_obsolete_node_frag(c, this);
328 }
329 /* Now we're pointing at the first frag which isn't totally obsoleted by
329 /* Now we're pointing at the first frag which isn't totally obsoleted by
330 the new frag */
331
332 if (!this || newfrag->ofs + newfrag->size == this->ofs)
333 return 0;
334
335 /* Still some overlap but we don't need to move it in the tree */
336 this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);
337 this->ofs = newfrag->ofs + newfrag->size;
338
339 /* And mark them REF_NORMAL so the GC takes a look at them */
340 if (this->node)
341 mark_ref_normal(this->node->raw);
342 mark_ref_normal(newfrag->node->raw);
343
344 return 0;
345}
346
330 the new frag */
331
332 if (!this || newfrag->ofs + newfrag->size == this->ofs)
333 return 0;
334
335 /* Still some overlap but we don't need to move it in the tree */
336 this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);
337 this->ofs = newfrag->ofs + newfrag->size;
338
339 /* And mark them REF_NORMAL so the GC takes a look at them */
340 if (this->node)
341 mark_ref_normal(this->node->raw);
342 mark_ref_normal(newfrag->node->raw);
343
344 return 0;
345}
346
347/*
347/*
348 * Given an inode, probably with existing tree of fragments, add the new node
349 * to the fragment tree.
350 */
351int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn)
352{
353 int ret;
354 struct jffs2_node_frag *newfrag;
355
356 if (unlikely(!fn->size))
357 return 0;
358
359 newfrag = new_fragment(fn, fn->ofs, fn->size);
360 if (unlikely(!newfrag))
361 return -ENOMEM;
362 newfrag->node->frags = 1;
363
364 dbg_fragtree("adding node %#04x-%#04x @0x%08x on flash, newfrag *%p\n",
365 fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag);
348 * Given an inode, probably with existing tree of fragments, add the new node
349 * to the fragment tree.
350 */
351int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn)
352{
353 int ret;
354 struct jffs2_node_frag *newfrag;
355
356 if (unlikely(!fn->size))
357 return 0;
358
359 newfrag = new_fragment(fn, fn->ofs, fn->size);
360 if (unlikely(!newfrag))
361 return -ENOMEM;
362 newfrag->node->frags = 1;
363
364 dbg_fragtree("adding node %#04x-%#04x @0x%08x on flash, newfrag *%p\n",
365 fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag);
366
366
367 ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag);
368 if (unlikely(ret))
369 return ret;
370
371 /* If we now share a page with other nodes, mark either previous
372 or next node REF_NORMAL, as appropriate. */
373 if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) {
374 struct jffs2_node_frag *prev = frag_prev(newfrag);
375
376 mark_ref_normal(fn->raw);
367 ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag);
368 if (unlikely(ret))
369 return ret;
370
371 /* If we now share a page with other nodes, mark either previous
372 or next node REF_NORMAL, as appropriate. */
373 if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) {
374 struct jffs2_node_frag *prev = frag_prev(newfrag);
375
376 mark_ref_normal(fn->raw);
377 /* If we don't start at zero there's _always_ a previous */
377 /* If we don't start at zero there's _always_ a previous */
378 if (prev->node)
379 mark_ref_normal(prev->node->raw);
380 }
381
382 if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) {
383 struct jffs2_node_frag *next = frag_next(newfrag);
378 if (prev->node)
379 mark_ref_normal(prev->node->raw);
380 }
381
382 if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) {
383 struct jffs2_node_frag *next = frag_next(newfrag);
384
384
385 if (next) {
386 mark_ref_normal(fn->raw);
387 if (next->node)
388 mark_ref_normal(next->node->raw);
389 }
390 }
391 jffs2_dbg_fragtree_paranoia_check_nolock(f);
392

--- 14 unchanged lines hidden (view full) ---

407 struct jffs2_eraseblock *jeb;
408 unsigned char *buffer;
409 uint32_t crc, ofs, retlen, len;
410
411 BUG_ON(tn->csize == 0);
412
413 if (!jffs2_is_writebuffered(c))
414 goto adj_acc;
385 if (next) {
386 mark_ref_normal(fn->raw);
387 if (next->node)
388 mark_ref_normal(next->node->raw);
389 }
390 }
391 jffs2_dbg_fragtree_paranoia_check_nolock(f);
392

--- 14 unchanged lines hidden (view full) ---

407 struct jffs2_eraseblock *jeb;
408 unsigned char *buffer;
409 uint32_t crc, ofs, retlen, len;
410
411 BUG_ON(tn->csize == 0);
412
413 if (!jffs2_is_writebuffered(c))
414 goto adj_acc;
415
415
416 /* Calculate how many bytes were already checked */
417 ofs = ref_offset(ref) + sizeof(struct jffs2_raw_inode);
418 len = ofs % c->wbuf_pagesize;
419 if (likely(len))
420 len = c->wbuf_pagesize - len;
421
422 if (len >= tn->csize) {
423 dbg_readinode("no need to check node at %#08x, data length %u, data starts at %#08x - it has already been checked.\n",
424 ref_offset(ref), tn->csize, ofs);
425 goto adj_acc;
426 }
416 /* Calculate how many bytes were already checked */
417 ofs = ref_offset(ref) + sizeof(struct jffs2_raw_inode);
418 len = ofs % c->wbuf_pagesize;
419 if (likely(len))
420 len = c->wbuf_pagesize - len;
421
422 if (len >= tn->csize) {
423 dbg_readinode("no need to check node at %#08x, data length %u, data starts at %#08x - it has already been checked.\n",
424 ref_offset(ref), tn->csize, ofs);
425 goto adj_acc;
426 }
427
427
428 ofs += len;
429 len = tn->csize - len;
428 ofs += len;
429 len = tn->csize - len;
430
430
431 dbg_readinode("check node at %#08x, data length %u, partial CRC %#08x, correct CRC %#08x, data starts at %#08x, start checking from %#08x - %u bytes.\n",
432 ref_offset(ref), tn->csize, tn->partial_crc, tn->data_crc, ofs - len, ofs, len);
431 dbg_readinode("check node at %#08x, data length %u, partial CRC %#08x, correct CRC %#08x, data starts at %#08x, start checking from %#08x - %u bytes.\n",
432 ref_offset(ref), tn->csize, tn->partial_crc, tn->data_crc, ofs - len, ofs, len);
433
433
434#ifndef __ECOS
435 /* TODO: instead, incapsulate point() stuff to jffs2_flash_read(),
436 * adding and jffs2_flash_read_end() interface. */
437 if (c->mtd->point) {
438 err = c->mtd->point(c->mtd, ofs, len, &retlen, &buffer);
439 if (!err && retlen < tn->csize) {
440 JFFS2_WARNING("MTD point returned len too short: %u instead of %u.\n", retlen, tn->csize);
441 c->mtd->unpoint(c->mtd, buffer, ofs, len);
442 } else if (err)
443 JFFS2_WARNING("MTD point failed: error code %d.\n", err);
444 else
445 pointed = 1; /* succefully pointed to device */
446 }
447#endif
434#ifndef __ECOS
435 /* TODO: instead, incapsulate point() stuff to jffs2_flash_read(),
436 * adding and jffs2_flash_read_end() interface. */
437 if (c->mtd->point) {
438 err = c->mtd->point(c->mtd, ofs, len, &retlen, &buffer);
439 if (!err && retlen < tn->csize) {
440 JFFS2_WARNING("MTD point returned len too short: %u instead of %u.\n", retlen, tn->csize);
441 c->mtd->unpoint(c->mtd, buffer, ofs, len);
442 } else if (err)
443 JFFS2_WARNING("MTD point failed: error code %d.\n", err);
444 else
445 pointed = 1; /* succefully pointed to device */
446 }
447#endif
448
448
449 if (!pointed) {
450 buffer = kmalloc(len, GFP_KERNEL);
451 if (unlikely(!buffer))
452 return -ENOMEM;
449 if (!pointed) {
450 buffer = kmalloc(len, GFP_KERNEL);
451 if (unlikely(!buffer))
452 return -ENOMEM;
453
453
454 /* TODO: this is very frequent pattern, make it a separate
455 * routine */
456 err = jffs2_flash_read(c, ofs, len, &retlen, buffer);
457 if (err) {
458 JFFS2_ERROR("can not read %d bytes from 0x%08x, error code: %d.\n", len, ofs, err);
459 goto free_out;
460 }
454 /* TODO: this is very frequent pattern, make it a separate
455 * routine */
456 err = jffs2_flash_read(c, ofs, len, &retlen, buffer);
457 if (err) {
458 JFFS2_ERROR("can not read %d bytes from 0x%08x, error code: %d.\n", len, ofs, err);
459 goto free_out;
460 }
461
461
462 if (retlen != len) {
463 JFFS2_ERROR("short read at %#08x: %d instead of %d.\n", ofs, retlen, len);
464 err = -EIO;
465 goto free_out;
466 }
467 }
468
469 /* Continue calculating CRC */

--- 10 unchanged lines hidden (view full) ---

480 ofs, tn->data_crc, crc);
481 return 1;
482 }
483
484adj_acc:
485 jeb = &c->blocks[ref->flash_offset / c->sector_size];
486 len = ref_totlen(c, jeb, ref);
487
462 if (retlen != len) {
463 JFFS2_ERROR("short read at %#08x: %d instead of %d.\n", ofs, retlen, len);
464 err = -EIO;
465 goto free_out;
466 }
467 }
468
469 /* Continue calculating CRC */

--- 10 unchanged lines hidden (view full) ---

480 ofs, tn->data_crc, crc);
481 return 1;
482 }
483
484adj_acc:
485 jeb = &c->blocks[ref->flash_offset / c->sector_size];
486 len = ref_totlen(c, jeb, ref);
487
488 /*
488 /*
489 * Mark the node as having been checked and fix the
490 * accounting accordingly.
491 */
492 spin_lock(&c->erase_completion_lock);
493 jeb->used_size += len;
494 jeb->unchecked_size -= len;
495 c->used_size += len;
496 c->unchecked_size -= len;

--- 14 unchanged lines hidden (view full) ---

511/*
512 * Helper function for jffs2_add_older_frag_to_fragtree().
513 *
514 * Checks the node if we are in the checking stage.
515 */
516static inline int check_node(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_tmp_dnode_info *tn)
517{
518 int ret;
489 * Mark the node as having been checked and fix the
490 * accounting accordingly.
491 */
492 spin_lock(&c->erase_completion_lock);
493 jeb->used_size += len;
494 jeb->unchecked_size -= len;
495 c->used_size += len;
496 c->unchecked_size -= len;

--- 14 unchanged lines hidden (view full) ---

511/*
512 * Helper function for jffs2_add_older_frag_to_fragtree().
513 *
514 * Checks the node if we are in the checking stage.
515 */
516static inline int check_node(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_tmp_dnode_info *tn)
517{
518 int ret;
519
519
520 BUG_ON(ref_obsolete(tn->fn->raw));
521
522 /* We only check the data CRC of unchecked nodes */
523 if (ref_flags(tn->fn->raw) != REF_UNCHECKED)
524 return 0;
520 BUG_ON(ref_obsolete(tn->fn->raw));
521
522 /* We only check the data CRC of unchecked nodes */
523 if (ref_flags(tn->fn->raw) != REF_UNCHECKED)
524 return 0;
525
525
526 dbg_fragtree2("check node %#04x-%#04x, phys offs %#08x.\n",
527 tn->fn->ofs, tn->fn->ofs + tn->fn->size, ref_offset(tn->fn->raw));
528
529 ret = check_node_data(c, tn);
530 if (unlikely(ret < 0)) {
531 JFFS2_ERROR("check_node_data() returned error: %d.\n",
532 ret);
533 } else if (unlikely(ret > 0)) {
534 dbg_fragtree2("CRC error, mark it obsolete.\n");
535 jffs2_mark_node_obsolete(c, tn->fn->raw);
536 }
537
538 return ret;
539}
540
526 dbg_fragtree2("check node %#04x-%#04x, phys offs %#08x.\n",
527 tn->fn->ofs, tn->fn->ofs + tn->fn->size, ref_offset(tn->fn->raw));
528
529 ret = check_node_data(c, tn);
530 if (unlikely(ret < 0)) {
531 JFFS2_ERROR("check_node_data() returned error: %d.\n",
532 ret);
533 } else if (unlikely(ret > 0)) {
534 dbg_fragtree2("CRC error, mark it obsolete.\n");
535 jffs2_mark_node_obsolete(c, tn->fn->raw);
536 }
537
538 return ret;
539}
540
541/*
541/*
542 * Helper function for jffs2_add_older_frag_to_fragtree().
543 *
544 * Called when the new fragment that is being inserted
545 * splits a hole fragment.
546 */
547static int split_hole(struct jffs2_sb_info *c, struct rb_root *root,
548 struct jffs2_node_frag *newfrag, struct jffs2_node_frag *hole)
549{
550 dbg_fragtree2("fragment %#04x-%#04x splits the hole %#04x-%#04x\n",
551 newfrag->ofs, newfrag->ofs + newfrag->size, hole->ofs, hole->ofs + hole->size);
552
553 if (hole->ofs == newfrag->ofs) {
542 * Helper function for jffs2_add_older_frag_to_fragtree().
543 *
544 * Called when the new fragment that is being inserted
545 * splits a hole fragment.
546 */
547static int split_hole(struct jffs2_sb_info *c, struct rb_root *root,
548 struct jffs2_node_frag *newfrag, struct jffs2_node_frag *hole)
549{
550 dbg_fragtree2("fragment %#04x-%#04x splits the hole %#04x-%#04x\n",
551 newfrag->ofs, newfrag->ofs + newfrag->size, hole->ofs, hole->ofs + hole->size);
552
553 if (hole->ofs == newfrag->ofs) {
554 /*
554 /*
555 * Well, the new fragment actually starts at the same offset as
556 * the hole.
557 */
558 if (hole->ofs + hole->size > newfrag->ofs + newfrag->size) {
555 * Well, the new fragment actually starts at the same offset as
556 * the hole.
557 */
558 if (hole->ofs + hole->size > newfrag->ofs + newfrag->size) {
559 /*
559 /*
560 * We replace the overlapped left part of the hole by
561 * the new node.
562 */
560 * We replace the overlapped left part of the hole by
561 * the new node.
562 */
563
563
564 dbg_fragtree2("insert fragment %#04x-%#04x and cut the left part of the hole\n",
565 newfrag->ofs, newfrag->ofs + newfrag->size);
566 rb_replace_node(&hole->rb, &newfrag->rb, root);
564 dbg_fragtree2("insert fragment %#04x-%#04x and cut the left part of the hole\n",
565 newfrag->ofs, newfrag->ofs + newfrag->size);
566 rb_replace_node(&hole->rb, &newfrag->rb, root);
567
567
568 hole->ofs += newfrag->size;
569 hole->size -= newfrag->size;
568 hole->ofs += newfrag->size;
569 hole->size -= newfrag->size;
570
571 /*
570
571 /*
572 * We know that 'hole' should be the right hand
573 * fragment.
574 */
575 jffs2_fragtree_insert(hole, newfrag);
576 rb_insert_color(&hole->rb, root);
577 } else {
572 * We know that 'hole' should be the right hand
573 * fragment.
574 */
575 jffs2_fragtree_insert(hole, newfrag);
576 rb_insert_color(&hole->rb, root);
577 } else {
578 /*
578 /*
579 * Ah, the new fragment is of the same size as the hole.
580 * Relace the hole by it.
581 */
582 dbg_fragtree2("insert fragment %#04x-%#04x and overwrite hole\n",
583 newfrag->ofs, newfrag->ofs + newfrag->size);
584 rb_replace_node(&hole->rb, &newfrag->rb, root);
585 jffs2_free_node_frag(hole);
586 }
587 } else {
588 /* The new fragment lefts some hole space at the left */
579 * Ah, the new fragment is of the same size as the hole.
580 * Relace the hole by it.
581 */
582 dbg_fragtree2("insert fragment %#04x-%#04x and overwrite hole\n",
583 newfrag->ofs, newfrag->ofs + newfrag->size);
584 rb_replace_node(&hole->rb, &newfrag->rb, root);
585 jffs2_free_node_frag(hole);
586 }
587 } else {
588 /* The new fragment lefts some hole space at the left */
589
589
590 struct jffs2_node_frag * newfrag2 = NULL;
591
592 if (hole->ofs + hole->size > newfrag->ofs + newfrag->size) {
593 /* The new frag also lefts some space at the right */
594 newfrag2 = new_fragment(NULL, newfrag->ofs +
595 newfrag->size, hole->ofs + hole->size
596 - newfrag->ofs - newfrag->size);
597 if (unlikely(!newfrag2)) {
598 jffs2_free_node_frag(newfrag);
599 return -ENOMEM;
600 }
601 }
602
603 hole->size = newfrag->ofs - hole->ofs;
604 dbg_fragtree2("left the hole %#04x-%#04x at the left and inserd fragment %#04x-%#04x\n",
605 hole->ofs, hole->ofs + hole->size, newfrag->ofs, newfrag->ofs + newfrag->size);
606
607 jffs2_fragtree_insert(newfrag, hole);
608 rb_insert_color(&newfrag->rb, root);
590 struct jffs2_node_frag * newfrag2 = NULL;
591
592 if (hole->ofs + hole->size > newfrag->ofs + newfrag->size) {
593 /* The new frag also lefts some space at the right */
594 newfrag2 = new_fragment(NULL, newfrag->ofs +
595 newfrag->size, hole->ofs + hole->size
596 - newfrag->ofs - newfrag->size);
597 if (unlikely(!newfrag2)) {
598 jffs2_free_node_frag(newfrag);
599 return -ENOMEM;
600 }
601 }
602
603 hole->size = newfrag->ofs - hole->ofs;
604 dbg_fragtree2("left the hole %#04x-%#04x at the left and inserd fragment %#04x-%#04x\n",
605 hole->ofs, hole->ofs + hole->size, newfrag->ofs, newfrag->ofs + newfrag->size);
606
607 jffs2_fragtree_insert(newfrag, hole);
608 rb_insert_color(&newfrag->rb, root);
609
609
610 if (newfrag2) {
611 dbg_fragtree2("left the hole %#04x-%#04x at the right\n",
612 newfrag2->ofs, newfrag2->ofs + newfrag2->size);
613 jffs2_fragtree_insert(newfrag2, newfrag);
614 rb_insert_color(&newfrag2->rb, root);
615 }
616 }
617

--- 31 unchanged lines hidden (view full) ---

649 this = jffs2_lookup_node_frag(root, fn_ofs);
650 if (this)
651 dbg_fragtree2("'this' found %#04x-%#04x (%s)\n", this->ofs, this->ofs + this->size, this->node ? "data" : "hole");
652
653 if (this)
654 lastend = this->ofs + this->size;
655 else
656 lastend = 0;
610 if (newfrag2) {
611 dbg_fragtree2("left the hole %#04x-%#04x at the right\n",
612 newfrag2->ofs, newfrag2->ofs + newfrag2->size);
613 jffs2_fragtree_insert(newfrag2, newfrag);
614 rb_insert_color(&newfrag2->rb, root);
615 }
616 }
617

--- 31 unchanged lines hidden (view full) ---

649 this = jffs2_lookup_node_frag(root, fn_ofs);
650 if (this)
651 dbg_fragtree2("'this' found %#04x-%#04x (%s)\n", this->ofs, this->ofs + this->size, this->node ? "data" : "hole");
652
653 if (this)
654 lastend = this->ofs + this->size;
655 else
656 lastend = 0;
657
657
658 /* Detect the preliminary type of node */
659 if (fn->size >= PAGE_CACHE_SIZE)
660 ref_flag = REF_PRISTINE;
661 else
662 ref_flag = REF_NORMAL;
658 /* Detect the preliminary type of node */
659 if (fn->size >= PAGE_CACHE_SIZE)
660 ref_flag = REF_PRISTINE;
661 else
662 ref_flag = REF_NORMAL;
663
663
664 /* See if we ran off the end of the root */
665 if (lastend <= fn_ofs) {
666 /* We did */
664 /* See if we ran off the end of the root */
665 if (lastend <= fn_ofs) {
666 /* We did */
667
668 /*
667
668 /*
669 * We are going to insert the new node into the
670 * fragment tree, so check it.
671 */
672 err = check_node(c, f, tn);
673 if (err != 0)
674 return err;
675
676 fn->frags = 1;

--- 9 unchanged lines hidden (view full) ---

686 }
687
688 goto out_ok;
689 }
690
691 fn->frags = 0;
692
693 while (1) {
669 * We are going to insert the new node into the
670 * fragment tree, so check it.
671 */
672 err = check_node(c, f, tn);
673 if (err != 0)
674 return err;
675
676 fn->frags = 1;

--- 9 unchanged lines hidden (view full) ---

686 }
687
688 goto out_ok;
689 }
690
691 fn->frags = 0;
692
693 while (1) {
694 /*
694 /*
695 * Here we have:
696 * fn_ofs < this->ofs + this->size && fn_ofs >= this->ofs.
695 * Here we have:
696 * fn_ofs < this->ofs + this->size && fn_ofs >= this->ofs.
697 *
697 *
698 * Remember, 'this' has higher version, any non-hole node
699 * which is already in the fragtree is newer then the newly
700 * inserted.
701 */
702 if (!this->node) {
698 * Remember, 'this' has higher version, any non-hole node
699 * which is already in the fragtree is newer then the newly
700 * inserted.
701 */
702 if (!this->node) {
703 /*
703 /*
704 * 'this' is the hole fragment, so at least the
705 * beginning of the new fragment is valid.
706 */
704 * 'this' is the hole fragment, so at least the
705 * beginning of the new fragment is valid.
706 */
707
708 /*
707
708 /*
709 * We are going to insert the new node into the
710 * fragment tree, so check it.
711 */
712 if (!checked) {
713 err = check_node(c, f, tn);
714 if (unlikely(err != 0))
715 return err;
716 checked = 1;
717 }
709 * We are going to insert the new node into the
710 * fragment tree, so check it.
711 */
712 if (!checked) {
713 err = check_node(c, f, tn);
714 if (unlikely(err != 0))
715 return err;
716 checked = 1;
717 }
718
718
719 if (this->ofs + this->size >= fn_ofs + fn_size) {
720 /* We split the hole on two parts */
721
722 fn->frags += 1;
723 newfrag = new_fragment(fn, fn_ofs, fn_size);
724 if (unlikely(!newfrag))
725 return -ENOMEM;
726
727 err = split_hole(c, root, newfrag, this);
728 if (unlikely(err))
729 return err;
730 goto out_ok;
731 }
732
719 if (this->ofs + this->size >= fn_ofs + fn_size) {
720 /* We split the hole on two parts */
721
722 fn->frags += 1;
723 newfrag = new_fragment(fn, fn_ofs, fn_size);
724 if (unlikely(!newfrag))
725 return -ENOMEM;
726
727 err = split_hole(c, root, newfrag, this);
728 if (unlikely(err))
729 return err;
730 goto out_ok;
731 }
732
733 /*
733 /*
734 * The beginning of the new fragment is valid since it
735 * overlaps the hole node.
736 */
737
738 ref_flag = REF_NORMAL;
739
740 fn->frags += 1;
741 newfrag = new_fragment(fn, fn_ofs,
742 this->ofs + this->size - fn_ofs);
743 if (unlikely(!newfrag))
744 return -ENOMEM;
734 * The beginning of the new fragment is valid since it
735 * overlaps the hole node.
736 */
737
738 ref_flag = REF_NORMAL;
739
740 fn->frags += 1;
741 newfrag = new_fragment(fn, fn_ofs,
742 this->ofs + this->size - fn_ofs);
743 if (unlikely(!newfrag))
744 return -ENOMEM;
745
745
746 if (fn_ofs == this->ofs) {
746 if (fn_ofs == this->ofs) {
747 /*
747 /*
748 * The new node starts at the same offset as
749 * the hole and supersieds the hole.
750 */
751 dbg_fragtree2("add the new fragment instead of hole %#04x-%#04x, refcnt %d\n",
752 fn_ofs, fn_ofs + this->ofs + this->size - fn_ofs, fn->frags);
753
754 rb_replace_node(&this->rb, &newfrag->rb, root);
755 jffs2_free_node_frag(this);
756 } else {
748 * The new node starts at the same offset as
749 * the hole and supersieds the hole.
750 */
751 dbg_fragtree2("add the new fragment instead of hole %#04x-%#04x, refcnt %d\n",
752 fn_ofs, fn_ofs + this->ofs + this->size - fn_ofs, fn->frags);
753
754 rb_replace_node(&this->rb, &newfrag->rb, root);
755 jffs2_free_node_frag(this);
756 } else {
757 /*
757 /*
758 * The hole becomes shorter as its right part
759 * is supersieded by the new fragment.
760 */
761 dbg_fragtree2("reduce size of hole %#04x-%#04x to %#04x-%#04x\n",
762 this->ofs, this->ofs + this->size, this->ofs, this->ofs + this->size - newfrag->size);
758 * The hole becomes shorter as its right part
759 * is supersieded by the new fragment.
760 */
761 dbg_fragtree2("reduce size of hole %#04x-%#04x to %#04x-%#04x\n",
762 this->ofs, this->ofs + this->size, this->ofs, this->ofs + this->size - newfrag->size);
763
763
764 dbg_fragtree2("add new fragment %#04x-%#04x, refcnt %d\n", fn_ofs,
765 fn_ofs + this->ofs + this->size - fn_ofs, fn->frags);
764 dbg_fragtree2("add new fragment %#04x-%#04x, refcnt %d\n", fn_ofs,
765 fn_ofs + this->ofs + this->size - fn_ofs, fn->frags);
766
766
767 this->size -= newfrag->size;
768 jffs2_fragtree_insert(newfrag, this);
769 rb_insert_color(&newfrag->rb, root);
770 }
767 this->size -= newfrag->size;
768 jffs2_fragtree_insert(newfrag, this);
769 rb_insert_color(&newfrag->rb, root);
770 }
771
771
772 fn_ofs += newfrag->size;
773 fn_size -= newfrag->size;
774 this = rb_entry(rb_next(&newfrag->rb),
775 struct jffs2_node_frag, rb);
776
777 dbg_fragtree2("switch to the next 'this' fragment: %#04x-%#04x %s\n",
778 this->ofs, this->ofs + this->size, this->node ? "(data)" : "(hole)");
779 }
780
772 fn_ofs += newfrag->size;
773 fn_size -= newfrag->size;
774 this = rb_entry(rb_next(&newfrag->rb),
775 struct jffs2_node_frag, rb);
776
777 dbg_fragtree2("switch to the next 'this' fragment: %#04x-%#04x %s\n",
778 this->ofs, this->ofs + this->size, this->node ? "(data)" : "(hole)");
779 }
780
781 /*
781 /*
782 * 'This' node is not the hole so it obsoletes the new fragment
783 * either fully or partially.
784 */
785 if (this->ofs + this->size >= fn_ofs + fn_size) {
786 /* The new node is obsolete, drop it */
787 if (fn->frags == 0) {
788 dbg_fragtree2("%#04x-%#04x is obsolete, mark it obsolete\n", fn_ofs, fn_ofs + fn_size);
789 ref_flag = REF_OBSOLETE;
790 }
791 goto out_ok;
792 } else {
793 struct jffs2_node_frag *new_this;
782 * 'This' node is not the hole so it obsoletes the new fragment
783 * either fully or partially.
784 */
785 if (this->ofs + this->size >= fn_ofs + fn_size) {
786 /* The new node is obsolete, drop it */
787 if (fn->frags == 0) {
788 dbg_fragtree2("%#04x-%#04x is obsolete, mark it obsolete\n", fn_ofs, fn_ofs + fn_size);
789 ref_flag = REF_OBSOLETE;
790 }
791 goto out_ok;
792 } else {
793 struct jffs2_node_frag *new_this;
794
794
795 /* 'This' node obsoletes the beginning of the new node */
796 dbg_fragtree2("the beginning %#04x-%#04x is obsolete\n", fn_ofs, this->ofs + this->size);
797
798 ref_flag = REF_NORMAL;
795 /* 'This' node obsoletes the beginning of the new node */
796 dbg_fragtree2("the beginning %#04x-%#04x is obsolete\n", fn_ofs, this->ofs + this->size);
797
798 ref_flag = REF_NORMAL;
799
799
800 fn_size -= this->ofs + this->size - fn_ofs;
801 fn_ofs = this->ofs + this->size;
802 dbg_fragtree2("now considering %#04x-%#04x\n", fn_ofs, fn_ofs + fn_size);
800 fn_size -= this->ofs + this->size - fn_ofs;
801 fn_ofs = this->ofs + this->size;
802 dbg_fragtree2("now considering %#04x-%#04x\n", fn_ofs, fn_ofs + fn_size);
803
803
804 new_this = rb_entry(rb_next(&this->rb), struct jffs2_node_frag, rb);
805 if (!new_this) {
804 new_this = rb_entry(rb_next(&this->rb), struct jffs2_node_frag, rb);
805 if (!new_this) {
806 /*
806 /*
807 * There is no next fragment. Add the rest of
808 * the new node as the right-hand child.
809 */
810 if (!checked) {
811 err = check_node(c, f, tn);
812 if (unlikely(err != 0))
813 return err;
814 checked = 1;
815 }
807 * There is no next fragment. Add the rest of
808 * the new node as the right-hand child.
809 */
810 if (!checked) {
811 err = check_node(c, f, tn);
812 if (unlikely(err != 0))
813 return err;
814 checked = 1;
815 }
816
816
817 fn->frags += 1;
818 newfrag = new_fragment(fn, fn_ofs, fn_size);
819 if (unlikely(!newfrag))
820 return -ENOMEM;
821
822 dbg_fragtree2("there are no more fragments, insert %#04x-%#04x\n",
823 newfrag->ofs, newfrag->ofs + newfrag->size);
817 fn->frags += 1;
818 newfrag = new_fragment(fn, fn_ofs, fn_size);
819 if (unlikely(!newfrag))
820 return -ENOMEM;
821
822 dbg_fragtree2("there are no more fragments, insert %#04x-%#04x\n",
823 newfrag->ofs, newfrag->ofs + newfrag->size);
824 rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
824 rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
825 rb_insert_color(&newfrag->rb, root);
826 goto out_ok;
827 } else {
828 this = new_this;
829 dbg_fragtree2("switch to the next 'this' fragment: %#04x-%#04x %s\n",
830 this->ofs, this->ofs + this->size, this->node ? "(data)" : "(hole)");
831 }
832 }

--- 24 unchanged lines hidden (view full) ---

857 spin_lock(&c->inocache_lock);
858 ic->state = state;
859 wake_up(&c->inocache_wq);
860 spin_unlock(&c->inocache_lock);
861}
862
863/* During mount, this needs no locking. During normal operation, its
864 callers want to do other stuff while still holding the inocache_lock.
825 rb_insert_color(&newfrag->rb, root);
826 goto out_ok;
827 } else {
828 this = new_this;
829 dbg_fragtree2("switch to the next 'this' fragment: %#04x-%#04x %s\n",
830 this->ofs, this->ofs + this->size, this->node ? "(data)" : "(hole)");
831 }
832 }

--- 24 unchanged lines hidden (view full) ---

857 spin_lock(&c->inocache_lock);
858 ic->state = state;
859 wake_up(&c->inocache_wq);
860 spin_unlock(&c->inocache_lock);
861}
862
863/* During mount, this needs no locking. During normal operation, its
864 callers want to do other stuff while still holding the inocache_lock.
865 Rather than introducing special case get_ino_cache functions or
865 Rather than introducing special case get_ino_cache functions or
866 callbacks, we just let the caller do the locking itself. */
866 callbacks, we just let the caller do the locking itself. */
867
867
868struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
869{
870 struct jffs2_inode_cache *ret;
871
872 ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
873 while (ret && ret->ino < ino) {
874 ret = ret->next;
875 }
868struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
869{
870 struct jffs2_inode_cache *ret;
871
872 ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
873 while (ret && ret->ino < ino) {
874 ret = ret->next;
875 }
876
876
877 if (ret && ret->ino != ino)
878 ret = NULL;
879
880 return ret;
881}
882
883void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
884{

--- 17 unchanged lines hidden (view full) ---

902}
903
904void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
905{
906 struct jffs2_inode_cache **prev;
907
908 dbg_inocache("del %p (ino #%u)\n", old, old->ino);
909 spin_lock(&c->inocache_lock);
877 if (ret && ret->ino != ino)
878 ret = NULL;
879
880 return ret;
881}
882
883void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
884{

--- 17 unchanged lines hidden (view full) ---

902}
903
904void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
905{
906 struct jffs2_inode_cache **prev;
907
908 dbg_inocache("del %p (ino #%u)\n", old, old->ino);
909 spin_lock(&c->inocache_lock);
910
910
911 prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
911 prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
912
912
913 while ((*prev) && (*prev)->ino < old->ino) {
914 prev = &(*prev)->next;
915 }
916 if ((*prev) == old) {
917 *prev = old->next;
918 }
919
920 /* Free it now unless it's in READING or CLEARING state, which
921 are the transitions upon read_inode() and clear_inode(). The
913 while ((*prev) && (*prev)->ino < old->ino) {
914 prev = &(*prev)->next;
915 }
916 if ((*prev) == old) {
917 *prev = old->next;
918 }
919
920 /* Free it now unless it's in READING or CLEARING state, which
921 are the transitions upon read_inode() and clear_inode(). The
922 rest of the time we know nobody else is looking at it, and
922 rest of the time we know nobody else is looking at it, and
923 if it's held by read_inode() or clear_inode() they'll free it
924 for themselves. */
925 if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
926 jffs2_free_inode_cache(old);
927
928 spin_unlock(&c->inocache_lock);
929}
930
931void jffs2_free_ino_caches(struct jffs2_sb_info *c)
932{
933 int i;
934 struct jffs2_inode_cache *this, *next;
923 if it's held by read_inode() or clear_inode() they'll free it
924 for themselves. */
925 if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
926 jffs2_free_inode_cache(old);
927
928 spin_unlock(&c->inocache_lock);
929}
930
931void jffs2_free_ino_caches(struct jffs2_sb_info *c)
932{
933 int i;
934 struct jffs2_inode_cache *this, *next;
935
935
936 for (i=0; i<INOCACHE_HASHSIZE; i++) {
937 this = c->inocache_list[i];
938 while (this) {
939 next = this->next;
940 jffs2_free_inode_cache(this);
941 this = next;
942 }
943 c->inocache_list[i] = NULL;

--- 10 unchanged lines hidden (view full) ---

954 while(this) {
955 next = this->next_phys;
956 jffs2_free_raw_node_ref(this);
957 this = next;
958 }
959 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
960 }
961}
936 for (i=0; i<INOCACHE_HASHSIZE; i++) {
937 this = c->inocache_list[i];
938 while (this) {
939 next = this->next;
940 jffs2_free_inode_cache(this);
941 this = next;
942 }
943 c->inocache_list[i] = NULL;

--- 10 unchanged lines hidden (view full) ---

954 while(this) {
955 next = this->next_phys;
956 jffs2_free_raw_node_ref(this);
957 this = next;
958 }
959 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
960 }
961}
962
962
963struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
964{
963struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
964{
965 /* The common case in lookup is that there will be a node
965 /* The common case in lookup is that there will be a node
966 which precisely matches. So we go looking for that first */
967 struct rb_node *next;
968 struct jffs2_node_frag *prev = NULL;
969 struct jffs2_node_frag *frag = NULL;
970
971 dbg_fragtree2("root %p, offset %d\n", fragtree, offset);
972
973 next = fragtree->rb_node;

--- 14 unchanged lines hidden (view full) ---

988 }
989
990 /* Exact match not found. Go back up looking at each parent,
991 and return the closest smaller one */
992
993 if (prev)
994 dbg_fragtree2("no match. Returning frag %#04x-%#04x, closest previous\n",
995 prev->ofs, prev->ofs+prev->size);
966 which precisely matches. So we go looking for that first */
967 struct rb_node *next;
968 struct jffs2_node_frag *prev = NULL;
969 struct jffs2_node_frag *frag = NULL;
970
971 dbg_fragtree2("root %p, offset %d\n", fragtree, offset);
972
973 next = fragtree->rb_node;

--- 14 unchanged lines hidden (view full) ---

988 }
989
990 /* Exact match not found. Go back up looking at each parent,
991 and return the closest smaller one */
992
993 if (prev)
994 dbg_fragtree2("no match. Returning frag %#04x-%#04x, closest previous\n",
995 prev->ofs, prev->ofs+prev->size);
996 else
996 else
997 dbg_fragtree2("returning NULL, empty fragtree\n");
997 dbg_fragtree2("returning NULL, empty fragtree\n");
998
998
999 return prev;
1000}
1001
1002/* Pass 'c' argument to indicate that nodes should be marked obsolete as
1003 they're killed. */
1004void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
1005{
1006 struct jffs2_node_frag *frag;
1007 struct jffs2_node_frag *parent;
1008
1009 if (!root->rb_node)
1010 return;
1011
1012 dbg_fragtree("killing\n");
999 return prev;
1000}
1001
1002/* Pass 'c' argument to indicate that nodes should be marked obsolete as
1003 they're killed. */
1004void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
1005{
1006 struct jffs2_node_frag *frag;
1007 struct jffs2_node_frag *parent;
1008
1009 if (!root->rb_node)
1010 return;
1011
1012 dbg_fragtree("killing\n");
1013
1013
1014 frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
1015 while(frag) {
1016 if (frag->rb.rb_left) {
1017 frag = frag_left(frag);
1018 continue;
1019 }
1020 if (frag->rb.rb_right) {
1021 frag = frag_right(frag);
1022 continue;
1023 }
1024
1025 if (frag->node && !(--frag->node->frags)) {
1014 frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
1015 while(frag) {
1016 if (frag->rb.rb_left) {
1017 frag = frag_left(frag);
1018 continue;
1019 }
1020 if (frag->rb.rb_right) {
1021 frag = frag_right(frag);
1022 continue;
1023 }
1024
1025 if (frag->node && !(--frag->node->frags)) {
1026 /* Not a hole, and it's the final remaining frag
1026 /* Not a hole, and it's the final remaining frag
1027 of this node. Free the node */
1028 if (c)
1029 jffs2_mark_node_obsolete(c, frag->node->raw);
1027 of this node. Free the node */
1028 if (c)
1029 jffs2_mark_node_obsolete(c, frag->node->raw);
1030
1030
1031 jffs2_free_full_dnode(frag->node);
1032 }
1033 parent = frag_parent(frag);
1034 if (parent) {
1035 if (frag_left(parent) == frag)
1036 parent->rb.rb_left = NULL;
1031 jffs2_free_full_dnode(frag->node);
1032 }
1033 parent = frag_parent(frag);
1034 if (parent) {
1035 if (frag_left(parent) == frag)
1036 parent->rb.rb_left = NULL;
1037 else
1037 else
1038 parent->rb.rb_right = NULL;
1039 }
1040
1041 jffs2_free_node_frag(frag);
1042 frag = parent;
1043
1044 cond_resched();
1045 }
1046}
1038 parent->rb.rb_right = NULL;
1039 }
1040
1041 jffs2_free_node_frag(frag);
1042 frag = parent;
1043
1044 cond_resched();
1045 }
1046}