Blame view
fs/jffs2/nodelist.c
21.7 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 |
/* * JFFS2 -- Journalling Flash File System, Version 2. * |
c00c310ea [JFFS2] Tidy up l... |
4 |
* Copyright © 2001-2007 Red Hat, Inc. |
1da177e4c Linux-2.6.12-rc2 |
5 6 7 8 9 |
* * Created by David Woodhouse <dwmw2@infradead.org> * * For licensing information, see the file 'LICENCE' in this directory. * |
1da177e4c Linux-2.6.12-rc2 |
10 11 12 13 14 15 16 17 |
*/ #include <linux/kernel.h> #include <linux/sched.h> #include <linux/fs.h> #include <linux/mtd/mtd.h> #include <linux/rbtree.h> #include <linux/crc32.h> |
1da177e4c Linux-2.6.12-rc2 |
18 19 |
#include <linux/pagemap.h> #include "nodelist.h" |
90a18fab4 make fs/jffs2/nod... |
20 21 |
static void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this); |
1da177e4c Linux-2.6.12-rc2 |
22 23 24 |
void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list) { struct jffs2_full_dirent **prev = list; |
182ec4eee [JFFS2] Clean up ... |
25 |
|
733802d97 [JFFS2] Debug cod... |
26 27 |
dbg_dentlist("add dirent \"%s\", ino #%u ", new->name, new->ino); |
1da177e4c Linux-2.6.12-rc2 |
28 29 30 31 32 |
while ((*prev) && (*prev)->nhash <= new->nhash) { if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) { /* Duplicate. Free one */ if (new->version < (*prev)->version) { |
15953580e [JFFS2] Improve g... |
33 34 |
dbg_dentlist("Eep! Marking new dirent node obsolete, old is \"%s\", ino #%u ", |
e0d601373 [JFFS2] Debug cod... |
35 |
(*prev)->name, (*prev)->ino); |
1da177e4c Linux-2.6.12-rc2 |
36 37 38 |
jffs2_mark_node_obsolete(c, new->raw); jffs2_free_full_dirent(new); } else { |
15953580e [JFFS2] Improve g... |
39 40 |
dbg_dentlist("marking old dirent \"%s\", ino #%u obsolete ", |
e0d601373 [JFFS2] Debug cod... |
41 |
(*prev)->name, (*prev)->ino); |
1da177e4c Linux-2.6.12-rc2 |
42 |
new->next = (*prev)->next; |
15953580e [JFFS2] Improve g... |
43 44 45 46 |
/* It may have been a 'placeholder' deletion dirent, if jffs2_can_mark_obsolete() (see jffs2_do_unlink()) */ if ((*prev)->raw) jffs2_mark_node_obsolete(c, ((*prev)->raw)); |
1da177e4c Linux-2.6.12-rc2 |
47 48 49 |
jffs2_free_full_dirent(*prev); *prev = new; } |
e0d601373 [JFFS2] Debug cod... |
50 |
return; |
1da177e4c Linux-2.6.12-rc2 |
51 52 53 54 55 |
} prev = &((*prev)->next); } new->next = *prev; *prev = new; |
1da177e4c Linux-2.6.12-rc2 |
56 |
} |
61c4b2377 [JFFS2] Handle in... |
57 |
uint32_t jffs2_truncate_fragtree(struct jffs2_sb_info *c, struct rb_root *list, uint32_t size) |
1e900979a [JFFS2] Move anot... |
58 59 |
{ struct jffs2_node_frag *frag = jffs2_lookup_node_frag(list, size); |
733802d97 [JFFS2] Debug cod... |
60 61 |
dbg_fragtree("truncating fragtree to 0x%08x bytes ", size); |
1e900979a [JFFS2] Move anot... |
62 63 64 |
/* We know frag->ofs <= size. That's what lookup does for us */ if (frag && frag->ofs != size) { |
1e0da3cb6 [JFFS2] Build fra... |
65 |
if (frag->ofs+frag->size > size) { |
1e900979a [JFFS2] Move anot... |
66 67 68 69 70 71 |
frag->size = size - frag->ofs; } frag = frag_next(frag); } while (frag && frag->ofs >= size) { struct jffs2_node_frag *next = frag_next(frag); |
1e900979a [JFFS2] Move anot... |
72 73 74 75 |
frag_erase(frag, list); jffs2_obsolete_node_frag(c, frag); frag = next; } |
1e0da3cb6 [JFFS2] Build fra... |
76 77 |
if (size == 0) |
61c4b2377 [JFFS2] Handle in... |
78 |
return 0; |
1e0da3cb6 [JFFS2] Build fra... |
79 |
|
1e0da3cb6 [JFFS2] Build fra... |
80 |
frag = frag_last(list); |
61c4b2377 [JFFS2] Handle in... |
81 82 83 84 85 86 87 88 89 |
/* Sanity check for truncation to longer than we started with... */ if (!frag) return 0; if (frag->ofs + frag->size < size) return frag->ofs + frag->size; /* If the last fragment starts at the RAM page boundary, it is * REF_PRISTINE irrespective of its size. */ |
f0507530c [JFFS2] Solve BUG... |
90 |
if (frag->node && (frag->ofs & (PAGE_CACHE_SIZE - 1)) == 0) { |
733802d97 [JFFS2] Debug cod... |
91 92 |
dbg_fragtree2("marking the last fragment 0x%08x-0x%08x REF_PRISTINE. ", |
182ec4eee [JFFS2] Clean up ... |
93 |
frag->ofs, frag->ofs + frag->size); |
1e0da3cb6 [JFFS2] Build fra... |
94 95 |
frag->node->raw->flash_offset = ref_offset(frag->node->raw) | REF_PRISTINE; } |
61c4b2377 [JFFS2] Handle in... |
96 |
return size; |
1e900979a [JFFS2] Move anot... |
97 |
} |
90a18fab4 make fs/jffs2/nod... |
98 99 |
static void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this) |
1da177e4c Linux-2.6.12-rc2 |
100 |
{ |
f97117d15 [JFFS2] Move scat... |
101 102 103 104 |
if (this->node) { this->node->frags--; if (!this->node->frags) { /* The node has no valid frags left. It's totally obsoleted */ |
733802d97 [JFFS2] Debug cod... |
105 106 |
dbg_fragtree2("marking old node @0x%08x (0x%04x-0x%04x) obsolete ", |
e0d601373 [JFFS2] Debug cod... |
107 |
ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size); |
f97117d15 [JFFS2] Move scat... |
108 109 110 |
jffs2_mark_node_obsolete(c, this->node->raw); jffs2_free_full_dnode(this->node); } else { |
733802d97 [JFFS2] Debug cod... |
111 112 |
dbg_fragtree2("marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d ", |
e0d601373 [JFFS2] Debug cod... |
113 |
ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, this->node->frags); |
f97117d15 [JFFS2] Move scat... |
114 115 |
mark_ref_normal(this->node->raw); } |
182ec4eee [JFFS2] Clean up ... |
116 |
|
f97117d15 [JFFS2] Move scat... |
117 118 |
} jffs2_free_node_frag(this); |
1da177e4c Linux-2.6.12-rc2 |
119 |
} |
f97117d15 [JFFS2] Move scat... |
120 |
static void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base) |
1da177e4c Linux-2.6.12-rc2 |
121 |
{ |
f97117d15 [JFFS2] Move scat... |
122 123 |
struct rb_node *parent = &base->rb; struct rb_node **link = &parent; |
9dee7503c [JFFS2] Optimise ... |
124 |
|
733802d97 [JFFS2] Debug cod... |
125 126 |
dbg_fragtree2("insert frag (0x%04x-0x%04x) ", newfrag->ofs, newfrag->ofs + newfrag->size); |
9dee7503c [JFFS2] Optimise ... |
127 |
|
f97117d15 [JFFS2] Move scat... |
128 129 130 |
while (*link) { parent = *link; base = rb_entry(parent, struct jffs2_node_frag, rb); |
182ec4eee [JFFS2] Clean up ... |
131 |
|
f97117d15 [JFFS2] Move scat... |
132 133 134 135 |
if (newfrag->ofs > base->ofs) link = &base->rb.rb_right; else if (newfrag->ofs < base->ofs) link = &base->rb.rb_left; |
9dee7503c [JFFS2] Optimise ... |
136 |
else { |
e0d601373 [JFFS2] Debug cod... |
137 138 |
JFFS2_ERROR("duplicate frag at %08x (%p,%p) ", newfrag->ofs, newfrag, base); |
f97117d15 [JFFS2] Move scat... |
139 |
BUG(); |
9dee7503c [JFFS2] Optimise ... |
140 |
} |
1da177e4c Linux-2.6.12-rc2 |
141 |
} |
f97117d15 [JFFS2] Move scat... |
142 143 |
rb_link_node(&newfrag->rb, &base->rb, link); |
1da177e4c Linux-2.6.12-rc2 |
144 |
} |
1e0da3cb6 [JFFS2] Build fra... |
145 146 147 |
/* * Allocate and initializes a new fragment. */ |
858119e15 [PATCH] Unlinline... |
148 |
static struct jffs2_node_frag * new_fragment(struct jffs2_full_dnode *fn, uint32_t ofs, uint32_t size) |
1e0da3cb6 [JFFS2] Build fra... |
149 150 |
{ struct jffs2_node_frag *newfrag; |
182ec4eee [JFFS2] Clean up ... |
151 |
|
1e0da3cb6 [JFFS2] Build fra... |
152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 |
newfrag = jffs2_alloc_node_frag(); if (likely(newfrag)) { newfrag->ofs = ofs; newfrag->size = size; newfrag->node = fn; } else { JFFS2_ERROR("cannot allocate a jffs2_node_frag object "); } return newfrag; } /* * Called when there is no overlapping fragment exist. Inserts a hole before the new * fragment and inserts the new fragment to the fragtree. */ static int no_overlapping_node(struct jffs2_sb_info *c, struct rb_root *root, struct jffs2_node_frag *newfrag, struct jffs2_node_frag *this, uint32_t lastend) { if (lastend < newfrag->node->ofs) { /* put a hole in before the new fragment */ struct jffs2_node_frag *holefrag; holefrag= new_fragment(NULL, lastend, newfrag->node->ofs - lastend); if (unlikely(!holefrag)) { jffs2_free_node_frag(newfrag); return -ENOMEM; } if (this) { |
182ec4eee [JFFS2] Clean up ... |
184 |
/* By definition, the 'this' node has no right-hand child, |
1e0da3cb6 [JFFS2] Build fra... |
185 186 |
because there are no frags with offset greater than it. So that's where we want to put the hole */ |
733802d97 [JFFS2] Debug cod... |
187 188 |
dbg_fragtree2("add hole frag %#04x-%#04x on the right of the new frag. ", |
1e0da3cb6 [JFFS2] Build fra... |
189 190 191 |
holefrag->ofs, holefrag->ofs + holefrag->size); rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right); } else { |
733802d97 [JFFS2] Debug cod... |
192 193 |
dbg_fragtree2("Add hole frag %#04x-%#04x to the root of the tree. ", |
1e0da3cb6 [JFFS2] Build fra... |
194 195 196 197 198 199 |
holefrag->ofs, holefrag->ofs + holefrag->size); rb_link_node(&holefrag->rb, NULL, &root->rb_node); } rb_insert_color(&holefrag->rb, root); this = holefrag; } |
182ec4eee [JFFS2] Clean up ... |
200 |
|
1e0da3cb6 [JFFS2] Build fra... |
201 |
if (this) { |
182ec4eee [JFFS2] Clean up ... |
202 |
/* By definition, the 'this' node has no right-hand child, |
1e0da3cb6 [JFFS2] Build fra... |
203 204 |
because there are no frags with offset greater than it. So that's where we want to put new fragment */ |
733802d97 [JFFS2] Debug cod... |
205 206 |
dbg_fragtree2("add the new node at the right "); |
182ec4eee [JFFS2] Clean up ... |
207 |
rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right); |
1e0da3cb6 [JFFS2] Build fra... |
208 |
} else { |
733802d97 [JFFS2] Debug cod... |
209 210 |
dbg_fragtree2("insert the new node at the root of the tree "); |
1e0da3cb6 [JFFS2] Build fra... |
211 212 213 214 215 216 |
rb_link_node(&newfrag->rb, NULL, &root->rb_node); } rb_insert_color(&newfrag->rb, root); return 0; } |
f97117d15 [JFFS2] Move scat... |
217 |
/* Doesn't set inode->i_size */ |
1e0da3cb6 [JFFS2] Build fra... |
218 |
static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info *c, struct rb_root *root, struct jffs2_node_frag *newfrag) |
1da177e4c Linux-2.6.12-rc2 |
219 |
{ |
f97117d15 [JFFS2] Move scat... |
220 221 |
struct jffs2_node_frag *this; uint32_t lastend; |
1da177e4c Linux-2.6.12-rc2 |
222 |
|
f97117d15 [JFFS2] Move scat... |
223 |
/* Skip all the nodes which are completed before this one starts */ |
1e0da3cb6 [JFFS2] Build fra... |
224 |
this = jffs2_lookup_node_frag(root, newfrag->node->ofs); |
1da177e4c Linux-2.6.12-rc2 |
225 |
|
f97117d15 [JFFS2] Move scat... |
226 |
if (this) { |
733802d97 [JFFS2] Debug cod... |
227 228 |
dbg_fragtree2("lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p) ", |
e0d601373 [JFFS2] Debug cod... |
229 |
this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this); |
f97117d15 [JFFS2] Move scat... |
230 231 |
lastend = this->ofs + this->size; } else { |
733802d97 [JFFS2] Debug cod... |
232 233 |
dbg_fragtree2("lookup gave no frag "); |
f97117d15 [JFFS2] Move scat... |
234 |
lastend = 0; |
1da177e4c Linux-2.6.12-rc2 |
235 |
} |
182ec4eee [JFFS2] Clean up ... |
236 |
|
1e0da3cb6 [JFFS2] Build fra... |
237 |
/* See if we ran off the end of the fragtree */ |
f97117d15 [JFFS2] Move scat... |
238 239 240 241 242 243 244 245 246 247 248 249 |
if (lastend <= newfrag->ofs) { /* We did */ /* Check if 'this' node was on the same page as the new node. If so, both 'this' and the new node get marked REF_NORMAL so the GC can take a look. */ if (lastend && (lastend-1) >> PAGE_CACHE_SHIFT == newfrag->ofs >> PAGE_CACHE_SHIFT) { if (this->node) mark_ref_normal(this->node->raw); mark_ref_normal(newfrag->node->raw); } |
1da177e4c Linux-2.6.12-rc2 |
250 |
|
1e0da3cb6 [JFFS2] Build fra... |
251 |
return no_overlapping_node(c, root, newfrag, this, lastend); |
dae6227f7 [JFFS2] Split a l... |
252 |
} |
dae6227f7 [JFFS2] Split a l... |
253 |
|
1e0da3cb6 [JFFS2] Build fra... |
254 |
if (this->node) |
733802d97 [JFFS2] Debug cod... |
255 256 |
dbg_fragtree2("dealing with frag %u-%u, phys %#08x(%d). ", |
1e0da3cb6 [JFFS2] Build fra... |
257 258 259 |
this->ofs, this->ofs + this->size, ref_offset(this->node->raw), ref_flags(this->node->raw)); else |
733802d97 [JFFS2] Debug cod... |
260 261 |
dbg_fragtree2("dealing with hole frag %u-%u. ", |
1e0da3cb6 [JFFS2] Build fra... |
262 |
this->ofs, this->ofs + this->size); |
dae6227f7 [JFFS2] Split a l... |
263 |
|
f97117d15 [JFFS2] Move scat... |
264 |
/* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes, |
182ec4eee [JFFS2] Clean up ... |
265 |
* - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs |
dae6227f7 [JFFS2] Split a l... |
266 |
*/ |
f97117d15 [JFFS2] Move scat... |
267 268 269 270 271 272 273 274 275 276 277 |
if (newfrag->ofs > this->ofs) { /* This node isn't completely obsoleted. The start of it remains valid */ /* Mark the new node and the partially covered node REF_NORMAL -- let the GC take a look at them */ mark_ref_normal(newfrag->node->raw); if (this->node) mark_ref_normal(this->node->raw); if (this->ofs + this->size > newfrag->ofs + newfrag->size) { /* The new node splits 'this' frag into two */ |
1e0da3cb6 [JFFS2] Build fra... |
278 |
struct jffs2_node_frag *newfrag2; |
f97117d15 [JFFS2] Move scat... |
279 |
if (this->node) |
733802d97 [JFFS2] Debug cod... |
280 281 |
dbg_fragtree2("split old frag 0x%04x-0x%04x, phys 0x%08x ", |
e0d601373 [JFFS2] Debug cod... |
282 |
this->ofs, this->ofs+this->size, ref_offset(this->node->raw)); |
182ec4eee [JFFS2] Clean up ... |
283 |
else |
733802d97 [JFFS2] Debug cod... |
284 285 |
dbg_fragtree2("split old hole frag 0x%04x-0x%04x ", |
8d5df4095 [JFFS2] More mess... |
286 |
this->ofs, this->ofs+this->size); |
182ec4eee [JFFS2] Clean up ... |
287 |
|
f97117d15 [JFFS2] Move scat... |
288 |
/* New second frag pointing to this's node */ |
1e0da3cb6 [JFFS2] Build fra... |
289 290 291 292 |
newfrag2 = new_fragment(this->node, newfrag->ofs + newfrag->size, this->ofs + this->size - newfrag->ofs - newfrag->size); if (unlikely(!newfrag2)) return -ENOMEM; |
f97117d15 [JFFS2] Move scat... |
293 294 295 296 297 298 299 300 301 302 303 304 305 |
if (this->node) this->node->frags++; /* Adjust size of original 'this' */ this->size = newfrag->ofs - this->ofs; /* Now, we know there's no node with offset greater than this->ofs but smaller than newfrag2->ofs or newfrag->ofs, for obvious reasons. So we can do a tree insert from 'this' to insert newfrag, and a tree insert from newfrag to insert newfrag2. */ jffs2_fragtree_insert(newfrag, this); |
1e0da3cb6 [JFFS2] Build fra... |
306 |
rb_insert_color(&newfrag->rb, root); |
182ec4eee [JFFS2] Clean up ... |
307 |
|
f97117d15 [JFFS2] Move scat... |
308 |
jffs2_fragtree_insert(newfrag2, newfrag); |
1e0da3cb6 [JFFS2] Build fra... |
309 |
rb_insert_color(&newfrag2->rb, root); |
182ec4eee [JFFS2] Clean up ... |
310 |
|
f97117d15 [JFFS2] Move scat... |
311 |
return 0; |
dae6227f7 [JFFS2] Split a l... |
312 |
} |
f97117d15 [JFFS2] Move scat... |
313 314 |
/* New node just reduces 'this' frag in size, doesn't split it */ this->size = newfrag->ofs - this->ofs; |
dae6227f7 [JFFS2] Split a l... |
315 |
|
f97117d15 [JFFS2] Move scat... |
316 317 |
/* Again, we know it lives down here in the tree */ jffs2_fragtree_insert(newfrag, this); |
1e0da3cb6 [JFFS2] Build fra... |
318 |
rb_insert_color(&newfrag->rb, root); |
f97117d15 [JFFS2] Move scat... |
319 |
} else { |
182ec4eee [JFFS2] Clean up ... |
320 |
/* New frag starts at the same point as 'this' used to. Replace |
f97117d15 [JFFS2] Move scat... |
321 |
it in the tree without doing a delete and insertion */ |
733802d97 [JFFS2] Debug cod... |
322 323 |
dbg_fragtree2("inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d ", |
e0d601373 [JFFS2] Debug cod... |
324 |
newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, this, this->ofs, this->ofs+this->size); |
182ec4eee [JFFS2] Clean up ... |
325 |
|
1e0da3cb6 [JFFS2] Build fra... |
326 |
rb_replace_node(&this->rb, &newfrag->rb, root); |
182ec4eee [JFFS2] Clean up ... |
327 |
|
f97117d15 [JFFS2] Move scat... |
328 |
if (newfrag->ofs + newfrag->size >= this->ofs+this->size) { |
733802d97 [JFFS2] Debug cod... |
329 330 |
dbg_fragtree2("obsoleting node frag %p (%x-%x) ", this, this->ofs, this->ofs+this->size); |
f97117d15 [JFFS2] Move scat... |
331 |
jffs2_obsolete_node_frag(c, this); |
dae6227f7 [JFFS2] Split a l... |
332 |
} else { |
f97117d15 [JFFS2] Move scat... |
333 334 335 336 |
this->ofs += newfrag->size; this->size -= newfrag->size; jffs2_fragtree_insert(this, newfrag); |
1e0da3cb6 [JFFS2] Build fra... |
337 |
rb_insert_color(&this->rb, root); |
f97117d15 [JFFS2] Move scat... |
338 |
return 0; |
dae6227f7 [JFFS2] Split a l... |
339 |
} |
dae6227f7 [JFFS2] Split a l... |
340 |
} |
f97117d15 [JFFS2] Move scat... |
341 |
/* OK, now we have newfrag added in the correct place in the tree, but |
182ec4eee [JFFS2] Clean up ... |
342 |
frag_next(newfrag) may be a fragment which is overlapped by it |
f97117d15 [JFFS2] Move scat... |
343 344 345 |
*/ while ((this = frag_next(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) { /* 'this' frag is obsoleted completely. */ |
733802d97 [JFFS2] Debug cod... |
346 347 |
dbg_fragtree2("obsoleting node frag %p (%x-%x) and removing from tree ", |
e0d601373 [JFFS2] Debug cod... |
348 |
this, this->ofs, this->ofs+this->size); |
1e0da3cb6 [JFFS2] Build fra... |
349 |
rb_erase(&this->rb, root); |
f97117d15 [JFFS2] Move scat... |
350 |
jffs2_obsolete_node_frag(c, this); |
dae6227f7 [JFFS2] Split a l... |
351 |
} |
182ec4eee [JFFS2] Clean up ... |
352 |
/* Now we're pointing at the first frag which isn't totally obsoleted by |
f97117d15 [JFFS2] Move scat... |
353 |
the new frag */ |
dae6227f7 [JFFS2] Split a l... |
354 |
|
1e0da3cb6 [JFFS2] Build fra... |
355 |
if (!this || newfrag->ofs + newfrag->size == this->ofs) |
f97117d15 [JFFS2] Move scat... |
356 |
return 0; |
1e0da3cb6 [JFFS2] Build fra... |
357 |
|
f97117d15 [JFFS2] Move scat... |
358 359 360 361 362 363 364 365 |
/* Still some overlap but we don't need to move it in the tree */ this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size); this->ofs = newfrag->ofs + newfrag->size; /* And mark them REF_NORMAL so the GC takes a look at them */ if (this->node) mark_ref_normal(this->node->raw); mark_ref_normal(newfrag->node->raw); |
dae6227f7 [JFFS2] Split a l... |
366 367 368 |
return 0; } |
182ec4eee [JFFS2] Clean up ... |
369 |
/* |
1e0da3cb6 [JFFS2] Build fra... |
370 371 |
* Given an inode, probably with existing tree of fragments, add the new node * to the fragment tree. |
dae6227f7 [JFFS2] Split a l... |
372 |
*/ |
f97117d15 [JFFS2] Move scat... |
373 |
int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn) |
dae6227f7 [JFFS2] Split a l... |
374 |
{ |
f97117d15 [JFFS2] Move scat... |
375 376 |
int ret; struct jffs2_node_frag *newfrag; |
dae6227f7 [JFFS2] Split a l... |
377 |
|
f97117d15 [JFFS2] Move scat... |
378 379 |
if (unlikely(!fn->size)) return 0; |
dae6227f7 [JFFS2] Split a l... |
380 |
|
1e0da3cb6 [JFFS2] Build fra... |
381 |
newfrag = new_fragment(fn, fn->ofs, fn->size); |
f97117d15 [JFFS2] Move scat... |
382 383 |
if (unlikely(!newfrag)) return -ENOMEM; |
1e0da3cb6 [JFFS2] Build fra... |
384 |
newfrag->node->frags = 1; |
1da177e4c Linux-2.6.12-rc2 |
385 |
|
733802d97 [JFFS2] Debug cod... |
386 387 |
dbg_fragtree("adding node %#04x-%#04x @0x%08x on flash, newfrag *%p ", |
e0d601373 [JFFS2] Debug cod... |
388 |
fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag); |
182ec4eee [JFFS2] Clean up ... |
389 |
|
f97117d15 [JFFS2] Move scat... |
390 391 392 393 394 395 396 397 398 399 |
ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag); if (unlikely(ret)) return ret; /* If we now share a page with other nodes, mark either previous or next node REF_NORMAL, as appropriate. */ if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) { struct jffs2_node_frag *prev = frag_prev(newfrag); mark_ref_normal(fn->raw); |
182ec4eee [JFFS2] Clean up ... |
400 |
/* If we don't start at zero there's _always_ a previous */ |
f97117d15 [JFFS2] Move scat... |
401 402 403 |
if (prev->node) mark_ref_normal(prev->node->raw); } |
1da177e4c Linux-2.6.12-rc2 |
404 |
|
f97117d15 [JFFS2] Move scat... |
405 406 |
if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) { struct jffs2_node_frag *next = frag_next(newfrag); |
182ec4eee [JFFS2] Clean up ... |
407 |
|
f97117d15 [JFFS2] Move scat... |
408 409 410 411 |
if (next) { mark_ref_normal(fn->raw); if (next->node) mark_ref_normal(next->node->raw); |
1da177e4c Linux-2.6.12-rc2 |
412 |
} |
1da177e4c Linux-2.6.12-rc2 |
413 |
} |
f97117d15 [JFFS2] Move scat... |
414 |
jffs2_dbg_fragtree_paranoia_check_nolock(f); |
1e0da3cb6 [JFFS2] Build fra... |
415 416 417 |
return 0; } |
1da177e4c Linux-2.6.12-rc2 |
418 419 420 421 422 423 424 425 426 427 |
void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state) { spin_lock(&c->inocache_lock); ic->state = state; wake_up(&c->inocache_wq); spin_unlock(&c->inocache_lock); } /* During mount, this needs no locking. During normal operation, its callers want to do other stuff while still holding the inocache_lock. |
182ec4eee [JFFS2] Clean up ... |
428 |
Rather than introducing special case get_ino_cache functions or |
1da177e4c Linux-2.6.12-rc2 |
429 |
callbacks, we just let the caller do the locking itself. */ |
182ec4eee [JFFS2] Clean up ... |
430 |
|
1da177e4c Linux-2.6.12-rc2 |
431 432 433 |
struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino) { struct jffs2_inode_cache *ret; |
65e5a0e18 jffs2: Dynamicall... |
434 |
ret = c->inocache_list[ino % c->inocache_hashsize]; |
1da177e4c Linux-2.6.12-rc2 |
435 436 437 |
while (ret && ret->ino < ino) { ret = ret->next; } |
182ec4eee [JFFS2] Clean up ... |
438 |
|
1da177e4c Linux-2.6.12-rc2 |
439 440 |
if (ret && ret->ino != ino) ret = NULL; |
1da177e4c Linux-2.6.12-rc2 |
441 442 443 444 445 446 |
return ret; } void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new) { struct jffs2_inode_cache **prev; |
7d27c8143 [JFFS2] Whitespac... |
447 |
|
1da177e4c Linux-2.6.12-rc2 |
448 |
spin_lock(&c->inocache_lock); |
7d27c8143 [JFFS2] Whitespac... |
449 450 |
if (!new->ino) new->ino = ++c->highest_ino; |
733802d97 [JFFS2] Debug cod... |
451 452 |
dbg_inocache("add %p (ino #%u) ", new, new->ino); |
7d27c8143 [JFFS2] Whitespac... |
453 |
|
65e5a0e18 jffs2: Dynamicall... |
454 |
prev = &c->inocache_list[new->ino % c->inocache_hashsize]; |
1da177e4c Linux-2.6.12-rc2 |
455 456 457 458 459 460 461 462 463 464 465 466 467 |
while ((*prev) && (*prev)->ino < new->ino) { prev = &(*prev)->next; } new->next = *prev; *prev = new; spin_unlock(&c->inocache_lock); } void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old) { struct jffs2_inode_cache **prev; |
e0d601373 [JFFS2] Debug cod... |
468 |
|
355ed4e14 [JFFS2][XATTR] Fi... |
469 470 471 |
#ifdef CONFIG_JFFS2_FS_XATTR BUG_ON(old->xref); #endif |
733802d97 [JFFS2] Debug cod... |
472 473 |
dbg_inocache("del %p (ino #%u) ", old, old->ino); |
1da177e4c Linux-2.6.12-rc2 |
474 |
spin_lock(&c->inocache_lock); |
182ec4eee [JFFS2] Clean up ... |
475 |
|
65e5a0e18 jffs2: Dynamicall... |
476 |
prev = &c->inocache_list[old->ino % c->inocache_hashsize]; |
182ec4eee [JFFS2] Clean up ... |
477 |
|
1da177e4c Linux-2.6.12-rc2 |
478 479 480 481 482 483 |
while ((*prev) && (*prev)->ino < old->ino) { prev = &(*prev)->next; } if ((*prev) == old) { *prev = old->next; } |
67e345d17 [JFFS2] Prevent i... |
484 485 |
/* Free it now unless it's in READING or CLEARING state, which are the transitions upon read_inode() and clear_inode(). The |
182ec4eee [JFFS2] Clean up ... |
486 |
rest of the time we know nobody else is looking at it, and |
67e345d17 [JFFS2] Prevent i... |
487 488 489 490 |
if it's held by read_inode() or clear_inode() they'll free it for themselves. */ if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING) jffs2_free_inode_cache(old); |
1da177e4c Linux-2.6.12-rc2 |
491 492 493 494 495 496 497 |
spin_unlock(&c->inocache_lock); } void jffs2_free_ino_caches(struct jffs2_sb_info *c) { int i; struct jffs2_inode_cache *this, *next; |
182ec4eee [JFFS2] Clean up ... |
498 |
|
65e5a0e18 jffs2: Dynamicall... |
499 |
for (i=0; i < c->inocache_hashsize; i++) { |
1da177e4c Linux-2.6.12-rc2 |
500 501 502 |
this = c->inocache_list[i]; while (this) { next = this->next; |
aa98d7cf5 [JFFS2][XATTR] XA... |
503 |
jffs2_xattr_free_inode(c, this); |
1da177e4c Linux-2.6.12-rc2 |
504 505 506 507 508 509 510 511 512 513 514 515 516 517 |
jffs2_free_inode_cache(this); this = next; } c->inocache_list[i] = NULL; } } void jffs2_free_raw_node_refs(struct jffs2_sb_info *c) { int i; struct jffs2_raw_node_ref *this, *next; for (i=0; i<c->nr_blocks; i++) { this = c->blocks[i].first_node; |
2f785402f [JFFS2] Reduce vi... |
518 |
while (this) { |
9bfeb691e [JFFS2] Switch to... |
519 520 521 522 523 524 |
if (this[REFS_PER_BLOCK].flash_offset == REF_LINK_NODE) next = this[REFS_PER_BLOCK].next_in_ino; else next = NULL; jffs2_free_refblock(this); |
1da177e4c Linux-2.6.12-rc2 |
525 526 527 528 529 |
this = next; } c->blocks[i].first_node = c->blocks[i].last_node = NULL; } } |
182ec4eee [JFFS2] Clean up ... |
530 |
|
1da177e4c Linux-2.6.12-rc2 |
531 532 |
struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset) { |
182ec4eee [JFFS2] Clean up ... |
533 |
/* The common case in lookup is that there will be a node |
1da177e4c Linux-2.6.12-rc2 |
534 535 536 537 |
which precisely matches. So we go looking for that first */ struct rb_node *next; struct jffs2_node_frag *prev = NULL; struct jffs2_node_frag *frag = NULL; |
733802d97 [JFFS2] Debug cod... |
538 539 |
dbg_fragtree2("root %p, offset %d ", fragtree, offset); |
1da177e4c Linux-2.6.12-rc2 |
540 541 542 543 544 |
next = fragtree->rb_node; while(next) { frag = rb_entry(next, struct jffs2_node_frag, rb); |
1da177e4c Linux-2.6.12-rc2 |
545 |
if (frag->ofs + frag->size <= offset) { |
1da177e4c Linux-2.6.12-rc2 |
546 547 548 549 550 |
/* Remember the closest smaller match on the way down */ if (!prev || frag->ofs > prev->ofs) prev = frag; next = frag->rb.rb_right; } else if (frag->ofs > offset) { |
1da177e4c Linux-2.6.12-rc2 |
551 552 |
next = frag->rb.rb_left; } else { |
1da177e4c Linux-2.6.12-rc2 |
553 554 555 556 557 558 559 560 |
return frag; } } /* Exact match not found. Go back up looking at each parent, and return the closest smaller one */ if (prev) |
733802d97 [JFFS2] Debug cod... |
561 562 |
dbg_fragtree2("no match. Returning frag %#04x-%#04x, closest previous ", |
e0d601373 [JFFS2] Debug cod... |
563 |
prev->ofs, prev->ofs+prev->size); |
182ec4eee [JFFS2] Clean up ... |
564 |
else |
733802d97 [JFFS2] Debug cod... |
565 566 |
dbg_fragtree2("returning NULL, empty fragtree "); |
182ec4eee [JFFS2] Clean up ... |
567 |
|
1da177e4c Linux-2.6.12-rc2 |
568 569 570 571 572 573 574 575 576 577 578 579 |
return prev; } /* Pass 'c' argument to indicate that nodes should be marked obsolete as they're killed. */ void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c) { struct jffs2_node_frag *frag; struct jffs2_node_frag *parent; if (!root->rb_node) return; |
733802d97 [JFFS2] Debug cod... |
580 581 |
dbg_fragtree("killing "); |
182ec4eee [JFFS2] Clean up ... |
582 |
|
1da177e4c Linux-2.6.12-rc2 |
583 |
frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb)); |
1da177e4c Linux-2.6.12-rc2 |
584 585 |
while(frag) { if (frag->rb.rb_left) { |
1da177e4c Linux-2.6.12-rc2 |
586 587 588 589 |
frag = frag_left(frag); continue; } if (frag->rb.rb_right) { |
1da177e4c Linux-2.6.12-rc2 |
590 591 592 |
frag = frag_right(frag); continue; } |
1da177e4c Linux-2.6.12-rc2 |
593 |
if (frag->node && !(--frag->node->frags)) { |
182ec4eee [JFFS2] Clean up ... |
594 |
/* Not a hole, and it's the final remaining frag |
1da177e4c Linux-2.6.12-rc2 |
595 596 597 |
of this node. Free the node */ if (c) jffs2_mark_node_obsolete(c, frag->node->raw); |
182ec4eee [JFFS2] Clean up ... |
598 |
|
1da177e4c Linux-2.6.12-rc2 |
599 600 601 602 603 604 |
jffs2_free_full_dnode(frag->node); } parent = frag_parent(frag); if (parent) { if (frag_left(parent) == frag) parent->rb.rb_left = NULL; |
182ec4eee [JFFS2] Clean up ... |
605 |
else |
1da177e4c Linux-2.6.12-rc2 |
606 607 608 609 610 611 612 613 614 |
parent->rb.rb_right = NULL; } jffs2_free_node_frag(frag); frag = parent; cond_resched(); } } |
f1f9671bd [JFFS2] Introduce... |
615 |
|
2f785402f [JFFS2] Reduce vi... |
616 617 618 619 |
struct jffs2_raw_node_ref *jffs2_link_node_ref(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb, uint32_t ofs, uint32_t len, struct jffs2_inode_cache *ic) |
f1f9671bd [JFFS2] Introduce... |
620 |
{ |
2f785402f [JFFS2] Reduce vi... |
621 |
struct jffs2_raw_node_ref *ref; |
9bfeb691e [JFFS2] Switch to... |
622 623 624 625 626 627 628 629 630 631 632 633 634 635 |
BUG_ON(!jeb->allocated_refs); jeb->allocated_refs--; ref = jeb->last_node; dbg_noderef("Last node at %p is (%08x,%p) ", ref, ref->flash_offset, ref->next_in_ino); while (ref->flash_offset != REF_EMPTY_NODE) { if (ref->flash_offset == REF_LINK_NODE) ref = ref->next_in_ino; else ref++; |
2f785402f [JFFS2] Reduce vi... |
636 |
} |
9bfeb691e [JFFS2] Switch to... |
637 638 639 |
dbg_noderef("New ref is %p (%08x becomes %08x,%p) len 0x%x ", ref, ref->flash_offset, ofs, ref->next_in_ino, len); |
2f785402f [JFFS2] Reduce vi... |
640 |
ref->flash_offset = ofs; |
9bfeb691e [JFFS2] Switch to... |
641 |
if (!jeb->first_node) { |
f1f9671bd [JFFS2] Introduce... |
642 |
jeb->first_node = ref; |
9bfeb691e [JFFS2] Switch to... |
643 644 645 646 647 648 649 650 651 652 |
BUG_ON(ref_offset(ref) != jeb->offset); } else if (unlikely(ref_offset(ref) != jeb->offset + c->sector_size - jeb->free_size)) { uint32_t last_len = ref_totlen(c, jeb, jeb->last_node); JFFS2_ERROR("Adding new ref %p at (0x%08x-0x%08x) not immediately after previous (0x%08x-0x%08x) ", ref, ref_offset(ref), ref_offset(ref)+len, ref_offset(jeb->last_node), ref_offset(jeb->last_node)+last_len); BUG(); |
ca89a517f [JFFS2] Finally e... |
653 |
} |
f1f9671bd [JFFS2] Introduce... |
654 |
jeb->last_node = ref; |
fcb757871 [JFFS2] Extend jf... |
655 656 657 658 659 660 |
if (ic) { ref->next_in_ino = ic->nodes; ic->nodes = ref; } else { ref->next_in_ino = NULL; } |
f1f9671bd [JFFS2] Introduce... |
661 662 663 664 665 666 667 668 669 670 671 672 673 674 |
switch(ref_flags(ref)) { case REF_UNCHECKED: c->unchecked_size += len; jeb->unchecked_size += len; break; case REF_NORMAL: case REF_PRISTINE: c->used_size += len; jeb->used_size += len; break; case REF_OBSOLETE: c->dirty_size += len; |
3b79673cf [JFFS2] Fix accou... |
675 |
jeb->dirty_size += len; |
f1f9671bd [JFFS2] Introduce... |
676 677 678 679 |
break; } c->free_size -= len; jeb->free_size -= len; |
ca89a517f [JFFS2] Finally e... |
680 681 682 683 684 |
#ifdef TEST_TOTLEN /* Set (and test) __totlen field... for now */ ref->__totlen = len; ref_totlen(c, jeb, ref); #endif |
2f785402f [JFFS2] Reduce vi... |
685 |
return ref; |
f1f9671bd [JFFS2] Introduce... |
686 |
} |
68270995f [JFFS2] Introduce... |
687 |
|
2f785402f [JFFS2] Reduce vi... |
688 |
/* No locking, no reservation of 'ref'. Do not use on a live file system */ |
68270995f [JFFS2] Introduce... |
689 690 691 |
int jffs2_scan_dirty_space(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb, uint32_t size) { |
ca89a517f [JFFS2] Finally e... |
692 693 |
if (!size) return 0; |
9bfeb691e [JFFS2] Switch to... |
694 695 696 697 |
if (unlikely(size > jeb->free_size)) { printk(KERN_CRIT "Dirty space 0x%x larger then free_size 0x%x (wasted 0x%x) ", size, jeb->free_size, jeb->wasted_size); |
ca89a517f [JFFS2] Finally e... |
698 699 |
BUG(); } |
9bfeb691e [JFFS2] Switch to... |
700 |
/* REF_EMPTY_NODE is !obsolete, so that works OK */ |
2ebf09c24 [JFFS2] Fix oops ... |
701 |
if (jeb->last_node && ref_obsolete(jeb->last_node)) { |
ca89a517f [JFFS2] Finally e... |
702 703 704 705 706 707 708 709 |
#ifdef TEST_TOTLEN jeb->last_node->__totlen += size; #endif c->dirty_size += size; c->free_size -= size; jeb->dirty_size += size; jeb->free_size -= size; } else { |
2f785402f [JFFS2] Reduce vi... |
710 711 |
uint32_t ofs = jeb->offset + c->sector_size - jeb->free_size; ofs |= REF_OBSOLETE; |
ca89a517f [JFFS2] Finally e... |
712 |
|
2f785402f [JFFS2] Reduce vi... |
713 |
jffs2_link_node_ref(c, jeb, ofs, size, NULL); |
ca89a517f [JFFS2] Finally e... |
714 |
} |
68270995f [JFFS2] Introduce... |
715 716 717 |
return 0; } |
ca89a517f [JFFS2] Finally e... |
718 719 720 721 722 723 724 |
/* Calculate totlen from surrounding nodes or eraseblock */ static inline uint32_t __ref_totlen(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb, struct jffs2_raw_node_ref *ref) { uint32_t ref_end; |
99988f7bb [JFFS2] Introduce... |
725 |
struct jffs2_raw_node_ref *next_ref = ref_next(ref); |
ca89a517f [JFFS2] Finally e... |
726 |
|
99988f7bb [JFFS2] Introduce... |
727 728 |
if (next_ref) ref_end = ref_offset(next_ref); |
ca89a517f [JFFS2] Finally e... |
729 730 731 732 733 |
else { if (!jeb) jeb = &c->blocks[ref->flash_offset / c->sector_size]; /* Last node in block. Use free_space */ |
9bfeb691e [JFFS2] Switch to... |
734 |
if (unlikely(ref != jeb->last_node)) { |
ca89a517f [JFFS2] Finally e... |
735 736 737 738 739 740 741 742 743 744 745 746 747 748 |
printk(KERN_CRIT "ref %p @0x%08x is not jeb->last_node (%p @0x%08x) ", ref, ref_offset(ref), jeb->last_node, jeb->last_node?ref_offset(jeb->last_node):0); BUG(); } ref_end = jeb->offset + c->sector_size - jeb->free_size; } return ref_end - ref_offset(ref); } uint32_t __jffs2_ref_totlen(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb, struct jffs2_raw_node_ref *ref) { uint32_t ret; |
ca89a517f [JFFS2] Finally e... |
749 |
ret = __ref_totlen(c, jeb, ref); |
9bfeb691e [JFFS2] Switch to... |
750 |
|
ca89a517f [JFFS2] Finally e... |
751 |
#ifdef TEST_TOTLEN |
9bfeb691e [JFFS2] Switch to... |
752 753 754 |
if (unlikely(ret != ref->__totlen)) { if (!jeb) jeb = &c->blocks[ref->flash_offset / c->sector_size]; |
ca89a517f [JFFS2] Finally e... |
755 756 757 758 |
printk(KERN_CRIT "Totlen for ref at %p (0x%08x-0x%08x) miscalculated as 0x%x instead of %x ", ref, ref_offset(ref), ref_offset(ref)+ref->__totlen, ret, ref->__totlen); |
99988f7bb [JFFS2] Introduce... |
759 760 761 762 |
if (ref_next(ref)) { printk(KERN_CRIT "next %p (0x%08x-0x%08x) ", ref_next(ref), ref_offset(ref_next(ref)), ref_offset(ref_next(ref))+ref->__totlen); |
ca89a517f [JFFS2] Finally e... |
763 |
} else |
99988f7bb [JFFS2] Introduce... |
764 765 |
printk(KERN_CRIT "No next ref. jeb->last_node is %p ", jeb->last_node); |
ca89a517f [JFFS2] Finally e... |
766 767 768 |
printk(KERN_CRIT "jeb->wasted_size %x, dirty_size %x, used_size %x, free_size %x ", jeb->wasted_size, jeb->dirty_size, jeb->used_size, jeb->free_size); |
9bfeb691e [JFFS2] Switch to... |
769 |
|
ca89a517f [JFFS2] Finally e... |
770 771 772 |
#if defined(JFFS2_DBG_DUMPS) || defined(JFFS2_DBG_PARANOIA_CHECKS) __jffs2_dbg_dump_node_refs_nolock(c, jeb); #endif |
9bfeb691e [JFFS2] Switch to... |
773 |
|
ca89a517f [JFFS2] Finally e... |
774 |
WARN_ON(1); |
9bfeb691e [JFFS2] Switch to... |
775 776 |
ret = ref->__totlen; |
ca89a517f [JFFS2] Finally e... |
777 778 779 780 |
} #endif /* TEST_TOTLEN */ return ret; } |