embox

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.102 2005/07/28 12:45:10 dedekind Exp $
11
 *
12
 */
13

14
#include <linux/kernel.h>
15
#include <linux/sched.h>
16
#include <linux/fs.h>
17
#include <linux/mtd/mtd.h>
18
#include <linux/rbtree.h>
19
#include <linux/crc32.h>
20
#include <linux/slab.h>
21
#include <linux/pagemap.h>
22
#include "nodelist.h"
23

24
void jffs2_add_fd_to_list(struct jffs2_sb_info *c,
25
		struct jffs2_full_dirent *new, struct jffs2_full_dirent **list) {
26
	struct jffs2_full_dirent **prev = list;
27

28
	JFFS2_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 &&
32
				!strcmp((const char *) (*prev)->name,
33
						(const char *) new->name)) {
34
			/* Duplicate. Free one */
35
			if (new->version < (*prev)->version) {
36
				JFFS2_DBG_DENTLIST("Eep! Marking new dirent node is obsolete, old is \"%s\", ino #%u\n",
37
					(*prev)->name, (*prev)->ino);
38
				jffs2_mark_node_obsolete(c, new->raw);
39
				jffs2_free_full_dirent(new);
40
			} else {
41
				JFFS2_DBG_DENTLIST("marking old dirent \"%s\", ino #%u bsolete\n",
42
					(*prev)->name, (*prev)->ino);
43
				new->next = (*prev)->next;
44
				jffs2_mark_node_obsolete(c, ((*prev)->raw));
45
				jffs2_free_full_dirent(*prev);
46
				*prev = new;
47
			}
48
			return;
49
		}
50
		prev = &((*prev)->next);
51
	}
52
	new->next = *prev;
53
	*prev = new;
54
}
55

56
void jffs2_obsolete_node_frag(struct jffs2_sb_info *c,
57
							struct jffs2_node_frag *this) {
58
	if (this->node) {
59
		this->node->frags--;
60
		if (!this->node->frags) {
61
			/* The node has no valid frags left. It's totally obsoleted */
62
			JFFS2_DBG_FRAGTREE2("marking old node @0x%08x (0x%04x-0x%04x) obsolete\n",
63
				ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size);
64
			jffs2_mark_node_obsolete(c, this->node->raw);
65
			jffs2_free_full_dnode(this->node);
66
		} else {
67
			JFFS2_DBG_FRAGTREE2("marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n",
68
				ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, this->node->frags);
69
			mark_ref_normal(this->node->raw);
70
		}
71

72
	}
73
	jffs2_free_node_frag(this);
74
}
75

76
static void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag,
77
									struct jffs2_node_frag *base) {
78
	struct rb_node *parent = &base->rb;
79
	struct rb_node **link = &parent;
80

81
	JFFS2_DBG_FRAGTREE2("insert frag (0x%04x-0x%04x)\n", newfrag->ofs, newfrag->ofs + newfrag->size);
82

83
	while (*link) {
84
		parent = *link;
85
		base = rb_entry(parent, struct jffs2_node_frag, rb);
86

87
		JFFS2_DBG_FRAGTREE2("considering frag at 0x%08x\n", base->ofs);
88
		if (newfrag->ofs > base->ofs) {
89
			link = &base->rb.rb_right;
90
		} else if (newfrag->ofs < base->ofs) {
91
			link = &base->rb.rb_left;
92
		} else {
93
			JFFS2_ERROR("duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
94
			BUG();
95
		}
96
	}
97

98
	rb_link_node(&newfrag->rb, &base->rb, link);
99
}
100

101
/* Doesn't set inode->i_size */
102
static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info *c,
103
		struct rb_root *list, struct jffs2_node_frag *newfrag) {
104
	struct jffs2_node_frag *this;
105
	uint32_t lastend;
106

107
	/* Skip all the nodes which are completed before this one starts */
108
	this = jffs2_lookup_node_frag(list, newfrag->node->ofs);
109

110
	if (this) {
111
		JFFS2_DBG_FRAGTREE2("lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
112
			  this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);
113
		lastend = this->ofs + this->size;
114
	} else {
115
		JFFS2_DBG_FRAGTREE2("lookup gave no frag\n");
116
		lastend = 0;
117
	}
118

119
	/* See if we ran off the end of the list */
120
	if (lastend <= newfrag->ofs) {
121
		/* We did */
122

123
		/* Check if 'this' node was on the same page as the new node.
124
		 * If so, both 'this' and the new node get marked REF_NORMAL so
125
		 * the GC can take a look.
126
		 */
127
		if (lastend && (lastend-1) >> PAGE_CACHE_SHIFT ==
128
				newfrag->ofs >> PAGE_CACHE_SHIFT) {
129
			if (this->node) {
130
				mark_ref_normal(this->node->raw);
131
			}
132
			mark_ref_normal(newfrag->node->raw);
133
		}
134

135
		if (lastend < newfrag->node->ofs) {
136
			/* ... and we need to put a hole in before the new node */
137
			struct jffs2_node_frag *holefrag = jffs2_alloc_node_frag();
138
			if (!holefrag) {
139
				jffs2_free_node_frag(newfrag);
140
				return -ENOMEM;
141
			}
142
			holefrag->ofs = lastend;
143
			holefrag->size = newfrag->node->ofs - lastend;
144
			holefrag->node = NULL;
145
			if (this) {
146
				/* By definition, the 'this' node has no right-hand child,
147
				 * because there are no frags with offset greater than it.
148
				 * So that's where we want to put the hole
149
				 */
150
				JFFS2_DBG_FRAGTREE2("adding hole frag (%p) on right of node at (%p)\n", holefrag, this);
151
				rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
152
			} else {
153
				JFFS2_DBG_FRAGTREE2("adding hole frag (%p) at root of tree\n", holefrag);
154
				rb_link_node(&holefrag->rb, NULL, &list->rb_node);
155
			}
156
			rb_insert_color(&holefrag->rb, list);
157
			this = holefrag;
158
		}
159
		if (this) {
160
			/* By definition, the 'this' node has no right-hand child,
161
			 * because there are no frags with offset greater than it.
162
			 * So that's where we want to put new fragment
163
			 */
164
			JFFS2_DBG_FRAGTREE2("adding new frag (%p) on right of node at (%p)\n", newfrag, this);
165
			rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
166
		} else {
167
			JFFS2_DBG_FRAGTREE2("adding new frag (%p) at root of tree\n", newfrag);
168
			rb_link_node(&newfrag->rb, NULL, &list->rb_node);
169
		}
170
		rb_insert_color(&newfrag->rb, list);
171
		return 0;
172
	}
173

174
	JFFS2_DBG_FRAGTREE2("dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
175
		  this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);
176

177
	/* OK. 'this' is pointing at the first frag that
178
	 * newfrag->ofs at least partially obsoletes,
179
	 * - i.e. newfrag->ofs < this->ofs+this->size
180
	 * && newfrag->ofs >= this->ofs
181
	 */
182
	if (newfrag->ofs > this->ofs) {
183
		/* This node isn't completely obsoleted.
184
		 * The start of it remains valid
185
		 */
186

187
		/* Mark the new node and the partially covered node REF_NORMAL -- let
188
		   the GC take a look at them */
189
		mark_ref_normal(newfrag->node->raw);
190
		if (this->node) {
191
			mark_ref_normal(this->node->raw);
192
		}
193

194
		if (this->ofs + this->size > newfrag->ofs + newfrag->size) {
195
			/* The new node splits 'this' frag into two */
196
			struct jffs2_node_frag *newfrag2 = jffs2_alloc_node_frag();
197
			if (!newfrag2) {
198
				jffs2_free_node_frag(newfrag);
199
				return -ENOMEM;
200
			}
201
			/* New second frag pointing to this's node */
202
			newfrag2->ofs = newfrag->ofs + newfrag->size;
203
			newfrag2->size = (this->ofs+this->size) - newfrag2->ofs;
204
			newfrag2->node = this->node;
205
			if (this->node) {
206
				this->node->frags++;
207
			}
208

209
			/* Adjust size of original 'this' */
210
			this->size = newfrag->ofs - this->ofs;
211

212
			/* Now, we know there's no node with offset
213
			 * greater than this->ofs but smaller than
214
			 * newfrag2->ofs or newfrag->ofs, for obvious
215
			 * reasons. So we can do a tree insert from
216
			 * 'this' to insert newfrag, and a tree insert
217
			 * from newfrag to insert newfrag2.
218
			 */
219
			jffs2_fragtree_insert(newfrag, this);
220
			rb_insert_color(&newfrag->rb, list);
221

222
			jffs2_fragtree_insert(newfrag2, newfrag);
223
			rb_insert_color(&newfrag2->rb, list);
224

225
			return 0;
226
		}
227
		/* New node just reduces 'this' frag in size, doesn't split it */
228
		this->size = newfrag->ofs - this->ofs;
229

230
		/* Again, we know it lives down here in the tree */
231
		jffs2_fragtree_insert(newfrag, this);
232
		rb_insert_color(&newfrag->rb, list);
233
	} else {
234
		/* New frag starts at the same point as 'this' used to. Replace
235
		 * it in the tree without doing a delete and insertion
236
		 */
237
		JFFS2_DBG_FRAGTREE2("inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d\n",
238
			  newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, this, this->ofs, this->ofs+this->size);
239

240
		rb_replace_node(&this->rb, &newfrag->rb, list);
241

242
		if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {
243
			JFFS2_DBG_FRAGTREE2("obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size);
244
			jffs2_obsolete_node_frag(c, this);
245
		} else {
246
			this->ofs += newfrag->size;
247
			this->size -= newfrag->size;
248

249
			jffs2_fragtree_insert(this, newfrag);
250
			rb_insert_color(&this->rb, list);
251
			return 0;
252
		}
253
	}
254
	/* OK, now we have newfrag added in the correct place in the tree, but
255
	 * frag_next(newfrag) may be a fragment which is overlapped by it
256
	 */
257
	while ((this = frag_next(newfrag)) &&
258
			newfrag->ofs + newfrag->size >= this->ofs + this->size) {
259
		/* 'this' frag is obsoleted completely. */
260
		JFFS2_DBG_FRAGTREE2("obsoleting node frag %p (%x-%x) and removing from tree\n",
261
			this, this->ofs, this->ofs+this->size);
262
		rb_erase(&this->rb, list);
263
		jffs2_obsolete_node_frag(c, this);
264
	}
265
	/* Now we're pointing at the first frag which isn't totally obsoleted by
266
	 * the new frag
267
	 */
268

269
	if (!this || newfrag->ofs + newfrag->size == this->ofs) {
270
		return 0;
271
	}
272
	/* Still some overlap but we don't need to move it in the tree */
273
	this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);
274
	this->ofs = newfrag->ofs + newfrag->size;
275

276
	/* And mark them REF_NORMAL so the GC takes a look at them */
277
	if (this->node) {
278
		mark_ref_normal(this->node->raw);
279
	}
280
	mark_ref_normal(newfrag->node->raw);
281

282
	return 0;
283
}
284

285
/**
286
 * Given an inode, probably with existing list of fragments, add the new node
287
 * to the fragment list.
288
 */
289
int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c,
290
		struct jffs2_inode_info *f, struct jffs2_full_dnode *fn) {
291
	int ret;
292
	struct jffs2_node_frag *newfrag;
293

294
	if (unlikely(!fn->size)) {
295
		return 0;
296
	}
297

298
	newfrag = jffs2_alloc_node_frag();
299
	if (unlikely(!newfrag)) {
300
		return -ENOMEM;
301
	}
302

303
	JFFS2_DBG_FRAGTREE("adding node %#04x-%#04x @0x%08x on flash, newfrag *%p\n",
304
		  fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag);
305

306
	newfrag->ofs = fn->ofs;
307
	newfrag->size = fn->size;
308
	newfrag->node = fn;
309
	newfrag->node->frags = 1;
310

311
	ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag);
312
	if (unlikely(ret)) {
313
		return ret;
314
	}
315

316
	/* If we now share a page with other nodes, mark either previous
317
	 * or next node REF_NORMAL, as appropriate.
318
	 */
319
	if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) {
320
		struct jffs2_node_frag *prev = frag_prev(newfrag);
321

322
		mark_ref_normal(fn->raw);
323
		/* If we don't start at zero there's _always_ a previous */
324
		if (prev->node) {
325
			mark_ref_normal(prev->node->raw);
326
		}
327
	}
328

329
	if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) {
330
		struct jffs2_node_frag *next = frag_next(newfrag);
331

332
		if (next) {
333
			mark_ref_normal(fn->raw);
334
			if (next->node) {
335
				mark_ref_normal(next->node->raw);
336
			}
337
		}
338
	}
339
	jffs2_dbg_fragtree_paranoia_check_nolock(f);
340
	jffs2_dbg_dump_fragtree_nolock(f);
341
	return 0;
342
}
343

344

345
void jffs2_set_inocache_state(struct jffs2_sb_info *c,
346
		struct jffs2_inode_cache *ic, int state) {
347
	spin_lock(&c->inocache_lock);
348
	ic->state = state;
349
	wake_up(&c->inocache_wq);
350
	spin_unlock(&c->inocache_lock);
351
}
352

353
/**
354
 * During mount, this needs no locking. During normal operation, its
355
 * callers want to do other stuff while still holding the inocache_lock.
356
 * Rather than introducing special case get_ino_cache functions or
357
 * callbacks, we just let the caller do the locking itself.
358
 */
359

360
struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c,
361
														uint32_t ino) {
362
	struct jffs2_inode_cache *ret;
363

364
	ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
365
	while (ret && ret->ino < ino) {
366
		ret = ret->next;
367
	}
368

369
	if (ret && ret->ino != ino) {
370
		ret = NULL;
371
	}
372

373
	return ret;
374
}
375

376
void jffs2_add_ino_cache (struct jffs2_sb_info *c,
377
					struct jffs2_inode_cache *new) {
378
	struct jffs2_inode_cache **prev;
379

380
	spin_lock(&c->inocache_lock);
381
	if (!new->ino) {
382
		new->ino = ++c->highest_ino;
383
	}
384

385
	JFFS2_DBG_INOCACHE("add %p (ino #%u)\n", new, new->ino);
386

387
	prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
388

389
	while ((*prev) && (*prev)->ino < new->ino) {
390
		prev = &(*prev)->next;
391
	}
392
	new->next = *prev;
393
	*prev = new;
394

395
	spin_unlock(&c->inocache_lock);
396
}
397

398
void jffs2_del_ino_cache(struct jffs2_sb_info *c,
399
					struct jffs2_inode_cache *old) {
400
	struct jffs2_inode_cache **prev;
401

402
	JFFS2_DBG_INOCACHE("del %p (ino #%u)\n", old, old->ino);
403
	spin_lock(&c->inocache_lock);
404

405
	prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
406

407
	while ((*prev) && (*prev)->ino < old->ino) {
408
		prev = &(*prev)->next;
409
	}
410
	if ((*prev) == old) {
411
		*prev = old->next;
412
	}
413

414
	/* Free it now unless it's in READING or CLEARING state, which
415
	 * are the transitions upon read_inode() and clear_inode(). The
416
	 * rest of the time we know nobody else is looking at it, and
417
	 * if it's held by read_inode() or clear_inode() they'll free it
418
	 * for themselves.
419
	 */
420
	if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING) {
421
		jffs2_free_inode_cache(old);
422
	}
423

424
	spin_unlock(&c->inocache_lock);
425
}
426

427
void jffs2_free_ino_caches(struct jffs2_sb_info *c) {
428
	int i;
429
	struct jffs2_inode_cache *this, *next;
430

431
	for (i=0; i<INOCACHE_HASHSIZE; i++) {
432
		this = c->inocache_list[i];
433
		while (this) {
434
			next = this->next;
435
			jffs2_free_inode_cache(this);
436
			this = next;
437
		}
438
		c->inocache_list[i] = NULL;
439
	}
440
}
441

442
void jffs2_free_raw_node_refs(struct jffs2_sb_info *c) {
443
	int i;
444
	struct jffs2_raw_node_ref *this, *next;
445

446
	for (i=0; i<c->nr_blocks; i++) {
447
		this = c->blocks[i].first_node;
448
		while(this) {
449
			next = this->next_phys;
450
			jffs2_free_raw_node_ref(this);
451
			this = next;
452
		}
453
		c->blocks[i].first_node = c->blocks[i].last_node = NULL;
454
	}
455
}
456

457
struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree,
458
															uint32_t offset) {
459
	/* The common case in lookup is that there will be a node
460
	 * which precisely matches. So we go looking for that first
461
	 */
462
	struct rb_node *next;
463
	struct jffs2_node_frag *prev = NULL;
464
	struct jffs2_node_frag *frag = NULL;
465

466
	JFFS2_DBG_FRAGTREE2("root %p, offset %d\n", fragtree, offset);
467

468
	next = fragtree->rb_node;
469

470
	while(next) {
471
		frag = rb_entry(next, struct jffs2_node_frag, rb);
472

473
		JFFS2_DBG_FRAGTREE2("considering frag %#04x-%#04x (%p). left %p, right %p\n",
474
			  frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right);
475
		if (frag->ofs + frag->size <= offset) {
476
			JFFS2_DBG_FRAGTREE2("going right from frag %#04x-%#04x, before the region we care about\n",
477
				  frag->ofs, frag->ofs+frag->size);
478
			/* Remember the closest smaller match on the way down */
479
			if (!prev || frag->ofs > prev->ofs) {
480
				prev = frag;
481
			}
482
			next = frag->rb.rb_right;
483
		} else if (frag->ofs > offset) {
484
			JFFS2_DBG_FRAGTREE2("going left from frag %#04x-%#04x, after the region we care about\n",
485
				  frag->ofs, frag->ofs+frag->size);
486
			next = frag->rb.rb_left;
487
		} else {
488
			JFFS2_DBG_FRAGTREE2("returning frag %#04x-%#04x, matched\n",
489
				  frag->ofs, frag->ofs+frag->size);
490
			return frag;
491
		}
492
	}
493

494
	/* Exact match not found. Go back up looking at each parent,
495
	 * and return the closest smaller one
496
	 */
497

498
	if (prev) {
499
		JFFS2_DBG_FRAGTREE2("no match. Returning frag %#04x-%#04x, closest previous\n",
500
			  prev->ofs, prev->ofs+prev->size);
501
	} else {
502
		JFFS2_DBG_FRAGTREE2("returning NULL, empty fragtree\n");
503
	}
504

505
	return prev;
506
}
507

508
/**
509
 * Pass 'c' argument to indicate that nodes should be marked obsolete as
510
 * they're killed.
511
 */
512
void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c) {
513
	struct jffs2_node_frag *frag;
514
	struct jffs2_node_frag *parent;
515

516
	if (!root->rb_node) {
517
		return;
518
	}
519

520
	JFFS2_DBG_FRAGTREE("killing\n");
521

522
	frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
523
	while(frag) {
524
		if (frag->rb.rb_left) {
525
			JFFS2_DBG_FRAGTREE2("going left from frag (%p) %#04x-%#04x\n",
526
				frag, frag->ofs, frag->ofs+frag->size);
527
			frag = frag_left(frag);
528
			continue;
529
		}
530
		if (frag->rb.rb_right) {
531
			JFFS2_DBG_FRAGTREE2("going right from frag (%p) %#04x-%#04x\n",
532
				  frag, frag->ofs, frag->ofs+frag->size);
533
			frag = frag_right(frag);
534
			continue;
535
		}
536

537
		JFFS2_DBG_FRAGTREE2("frag %#04x-%#04x: node %p, frags %d\n",
538
			  frag->ofs, frag->ofs+frag->size, frag->node, frag->node?frag->node->frags:0);
539

540
		if (frag->node && !(--frag->node->frags)) {
541
			/* Not a hole, and it's the final remaining frag
542
			 * of this node. Free the node
543
			 */
544
			if (c) {
545
				jffs2_mark_node_obsolete(c, frag->node->raw);
546
			}
547

548
			jffs2_free_full_dnode(frag->node);
549
		}
550
		parent = frag_parent(frag);
551
		if (parent) {
552
			if (frag_left(parent) == frag) {
553
				parent->rb.rb_left = NULL;
554
			} else {
555
				parent->rb.rb_right = NULL;
556
			}
557
		}
558

559
		jffs2_free_node_frag(frag);
560
		frag = parent;
561

562
		cond_resched();
563
	}
564
}
565