blob: 8cbfb82480252d3f3abebf0d3a14beb3cc2a9b4a [file] [log] [blame]
Artem Bityutskiy7d4e9cc2009-03-20 19:11:12 +02001/*
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002 * This file is part of UBIFS.
3 *
4 * Copyright (C) 2006-2008 Nokia Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 * more details.
14 *
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
21 */
22
23/*
24 * This file implements commit-related functionality of the LEB properties
25 * subsystem.
26 */
27
28#include <linux/crc16.h>
29#include "ubifs.h"
30
31/**
32 * first_dirty_cnode - find first dirty cnode.
33 * @c: UBIFS file-system description object
34 * @nnode: nnode at which to start
35 *
36 * This function returns the first dirty cnode or %NULL if there is not one.
37 */
38static struct ubifs_cnode *first_dirty_cnode(struct ubifs_nnode *nnode)
39{
40 ubifs_assert(nnode);
41 while (1) {
42 int i, cont = 0;
43
44 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
45 struct ubifs_cnode *cnode;
46
47 cnode = nnode->nbranch[i].cnode;
48 if (cnode &&
49 test_bit(DIRTY_CNODE, &cnode->flags)) {
50 if (cnode->level == 0)
51 return cnode;
52 nnode = (struct ubifs_nnode *)cnode;
53 cont = 1;
54 break;
55 }
56 }
57 if (!cont)
58 return (struct ubifs_cnode *)nnode;
59 }
60}
61
62/**
63 * next_dirty_cnode - find next dirty cnode.
64 * @cnode: cnode from which to begin searching
65 *
66 * This function returns the next dirty cnode or %NULL if there is not one.
67 */
68static struct ubifs_cnode *next_dirty_cnode(struct ubifs_cnode *cnode)
69{
70 struct ubifs_nnode *nnode;
71 int i;
72
73 ubifs_assert(cnode);
74 nnode = cnode->parent;
75 if (!nnode)
76 return NULL;
77 for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {
78 cnode = nnode->nbranch[i].cnode;
79 if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {
80 if (cnode->level == 0)
81 return cnode; /* cnode is a pnode */
82 /* cnode is a nnode */
83 return first_dirty_cnode((struct ubifs_nnode *)cnode);
84 }
85 }
86 return (struct ubifs_cnode *)nnode;
87}
88
89/**
90 * get_cnodes_to_commit - create list of dirty cnodes to commit.
91 * @c: UBIFS file-system description object
92 *
93 * This function returns the number of cnodes to commit.
94 */
95static int get_cnodes_to_commit(struct ubifs_info *c)
96{
97 struct ubifs_cnode *cnode, *cnext;
98 int cnt = 0;
99
100 if (!c->nroot)
101 return 0;
102
103 if (!test_bit(DIRTY_CNODE, &c->nroot->flags))
104 return 0;
105
106 c->lpt_cnext = first_dirty_cnode(c->nroot);
107 cnode = c->lpt_cnext;
108 if (!cnode)
109 return 0;
110 cnt += 1;
111 while (1) {
112 ubifs_assert(!test_bit(COW_ZNODE, &cnode->flags));
113 __set_bit(COW_ZNODE, &cnode->flags);
114 cnext = next_dirty_cnode(cnode);
115 if (!cnext) {
116 cnode->cnext = c->lpt_cnext;
117 break;
118 }
119 cnode->cnext = cnext;
120 cnode = cnext;
121 cnt += 1;
122 }
123 dbg_cmt("committing %d cnodes", cnt);
124 dbg_lp("committing %d cnodes", cnt);
125 ubifs_assert(cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);
126 return cnt;
127}
128
129/**
130 * upd_ltab - update LPT LEB properties.
131 * @c: UBIFS file-system description object
132 * @lnum: LEB number
133 * @free: amount of free space
134 * @dirty: amount of dirty space to add
135 */
136static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
137{
138 dbg_lp("LEB %d free %d dirty %d to %d +%d",
139 lnum, c->ltab[lnum - c->lpt_first].free,
140 c->ltab[lnum - c->lpt_first].dirty, free, dirty);
141 ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
142 c->ltab[lnum - c->lpt_first].free = free;
143 c->ltab[lnum - c->lpt_first].dirty += dirty;
144}
145
146/**
147 * alloc_lpt_leb - allocate an LPT LEB that is empty.
148 * @c: UBIFS file-system description object
149 * @lnum: LEB number is passed and returned here
150 *
151 * This function finds the next empty LEB in the ltab starting from @lnum. If a
152 * an empty LEB is found it is returned in @lnum and the function returns %0.
153 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed
154 * never to run out of space.
155 */
156static int alloc_lpt_leb(struct ubifs_info *c, int *lnum)
157{
158 int i, n;
159
160 n = *lnum - c->lpt_first + 1;
161 for (i = n; i < c->lpt_lebs; i++) {
162 if (c->ltab[i].tgc || c->ltab[i].cmt)
163 continue;
164 if (c->ltab[i].free == c->leb_size) {
165 c->ltab[i].cmt = 1;
166 *lnum = i + c->lpt_first;
167 return 0;
168 }
169 }
170
171 for (i = 0; i < n; i++) {
172 if (c->ltab[i].tgc || c->ltab[i].cmt)
173 continue;
174 if (c->ltab[i].free == c->leb_size) {
175 c->ltab[i].cmt = 1;
176 *lnum = i + c->lpt_first;
177 return 0;
178 }
179 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300180 return -ENOSPC;
181}
182
183/**
184 * layout_cnodes - layout cnodes for commit.
185 * @c: UBIFS file-system description object
186 *
187 * This function returns %0 on success and a negative error code on failure.
188 */
189static int layout_cnodes(struct ubifs_info *c)
190{
191 int lnum, offs, len, alen, done_lsave, done_ltab, err;
192 struct ubifs_cnode *cnode;
193
Adrian Hunter73944a62008-09-12 18:13:31 +0300194 err = dbg_chk_lpt_sz(c, 0, 0);
195 if (err)
196 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300197 cnode = c->lpt_cnext;
198 if (!cnode)
199 return 0;
200 lnum = c->nhead_lnum;
201 offs = c->nhead_offs;
202 /* Try to place lsave and ltab nicely */
203 done_lsave = !c->big_lpt;
204 done_ltab = 0;
205 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
206 done_lsave = 1;
207 c->lsave_lnum = lnum;
208 c->lsave_offs = offs;
209 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300210 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300211 }
212
213 if (offs + c->ltab_sz <= c->leb_size) {
214 done_ltab = 1;
215 c->ltab_lnum = lnum;
216 c->ltab_offs = offs;
217 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300218 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300219 }
220
221 do {
222 if (cnode->level) {
223 len = c->nnode_sz;
224 c->dirty_nn_cnt -= 1;
225 } else {
226 len = c->pnode_sz;
227 c->dirty_pn_cnt -= 1;
228 }
229 while (offs + len > c->leb_size) {
230 alen = ALIGN(offs, c->min_io_size);
231 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200232 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300233 err = alloc_lpt_leb(c, &lnum);
234 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300235 goto no_space;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300236 offs = 0;
237 ubifs_assert(lnum >= c->lpt_first &&
238 lnum <= c->lpt_last);
239 /* Try to place lsave and ltab nicely */
240 if (!done_lsave) {
241 done_lsave = 1;
242 c->lsave_lnum = lnum;
243 c->lsave_offs = offs;
244 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300245 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300246 continue;
247 }
248 if (!done_ltab) {
249 done_ltab = 1;
250 c->ltab_lnum = lnum;
251 c->ltab_offs = offs;
252 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300253 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300254 continue;
255 }
256 break;
257 }
258 if (cnode->parent) {
259 cnode->parent->nbranch[cnode->iip].lnum = lnum;
260 cnode->parent->nbranch[cnode->iip].offs = offs;
261 } else {
262 c->lpt_lnum = lnum;
263 c->lpt_offs = offs;
264 }
265 offs += len;
Adrian Hunter73944a62008-09-12 18:13:31 +0300266 dbg_chk_lpt_sz(c, 1, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300267 cnode = cnode->cnext;
268 } while (cnode && cnode != c->lpt_cnext);
269
270 /* Make sure to place LPT's save table */
271 if (!done_lsave) {
272 if (offs + c->lsave_sz > c->leb_size) {
273 alen = ALIGN(offs, c->min_io_size);
274 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200275 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300276 err = alloc_lpt_leb(c, &lnum);
277 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300278 goto no_space;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300279 offs = 0;
280 ubifs_assert(lnum >= c->lpt_first &&
281 lnum <= c->lpt_last);
282 }
283 done_lsave = 1;
284 c->lsave_lnum = lnum;
285 c->lsave_offs = offs;
286 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300287 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300288 }
289
290 /* Make sure to place LPT's own lprops table */
291 if (!done_ltab) {
292 if (offs + c->ltab_sz > c->leb_size) {
293 alen = ALIGN(offs, c->min_io_size);
294 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200295 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300296 err = alloc_lpt_leb(c, &lnum);
297 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300298 goto no_space;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300299 offs = 0;
300 ubifs_assert(lnum >= c->lpt_first &&
301 lnum <= c->lpt_last);
302 }
303 done_ltab = 1;
304 c->ltab_lnum = lnum;
305 c->ltab_offs = offs;
306 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300307 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300308 }
309
310 alen = ALIGN(offs, c->min_io_size);
311 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter73944a62008-09-12 18:13:31 +0300312 dbg_chk_lpt_sz(c, 4, alen - offs);
313 err = dbg_chk_lpt_sz(c, 3, alen);
314 if (err)
315 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300316 return 0;
Adrian Hunter73944a62008-09-12 18:13:31 +0300317
318no_space:
319 ubifs_err("LPT out of space");
320 dbg_err("LPT out of space at LEB %d:%d needing %d, done_ltab %d, "
321 "done_lsave %d", lnum, offs, len, done_ltab, done_lsave);
322 dbg_dump_lpt_info(c);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +0200323 dbg_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +0200324 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +0300325 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300326}
327
328/**
329 * realloc_lpt_leb - allocate an LPT LEB that is empty.
330 * @c: UBIFS file-system description object
331 * @lnum: LEB number is passed and returned here
332 *
333 * This function duplicates exactly the results of the function alloc_lpt_leb.
334 * It is used during end commit to reallocate the same LEB numbers that were
335 * allocated by alloc_lpt_leb during start commit.
336 *
337 * This function finds the next LEB that was allocated by the alloc_lpt_leb
338 * function starting from @lnum. If a LEB is found it is returned in @lnum and
339 * the function returns %0. Otherwise the function returns -ENOSPC.
340 * Note however, that LPT is designed never to run out of space.
341 */
342static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
343{
344 int i, n;
345
346 n = *lnum - c->lpt_first + 1;
347 for (i = n; i < c->lpt_lebs; i++)
348 if (c->ltab[i].cmt) {
349 c->ltab[i].cmt = 0;
350 *lnum = i + c->lpt_first;
351 return 0;
352 }
353
354 for (i = 0; i < n; i++)
355 if (c->ltab[i].cmt) {
356 c->ltab[i].cmt = 0;
357 *lnum = i + c->lpt_first;
358 return 0;
359 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300360 return -ENOSPC;
361}
362
363/**
364 * write_cnodes - write cnodes for commit.
365 * @c: UBIFS file-system description object
366 *
367 * This function returns %0 on success and a negative error code on failure.
368 */
369static int write_cnodes(struct ubifs_info *c)
370{
371 int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
372 struct ubifs_cnode *cnode;
373 void *buf = c->lpt_buf;
374
375 cnode = c->lpt_cnext;
376 if (!cnode)
377 return 0;
378 lnum = c->nhead_lnum;
379 offs = c->nhead_offs;
380 from = offs;
381 /* Ensure empty LEB is unmapped */
382 if (offs == 0) {
383 err = ubifs_leb_unmap(c, lnum);
384 if (err)
385 return err;
386 }
387 /* Try to place lsave and ltab nicely */
388 done_lsave = !c->big_lpt;
389 done_ltab = 0;
390 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
391 done_lsave = 1;
392 ubifs_pack_lsave(c, buf + offs, c->lsave);
393 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300394 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300395 }
396
397 if (offs + c->ltab_sz <= c->leb_size) {
398 done_ltab = 1;
399 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
400 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300401 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300402 }
403
404 /* Loop for each cnode */
405 do {
406 if (cnode->level)
407 len = c->nnode_sz;
408 else
409 len = c->pnode_sz;
410 while (offs + len > c->leb_size) {
411 wlen = offs - from;
412 if (wlen) {
413 alen = ALIGN(wlen, c->min_io_size);
414 memset(buf + offs, 0xff, alen - wlen);
415 err = ubifs_leb_write(c, lnum, buf + from, from,
416 alen, UBI_SHORTTERM);
417 if (err)
418 return err;
419 }
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200420 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300421 err = realloc_lpt_leb(c, &lnum);
422 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300423 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200424 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300425 ubifs_assert(lnum >= c->lpt_first &&
426 lnum <= c->lpt_last);
427 err = ubifs_leb_unmap(c, lnum);
428 if (err)
429 return err;
430 /* Try to place lsave and ltab nicely */
431 if (!done_lsave) {
432 done_lsave = 1;
433 ubifs_pack_lsave(c, buf + offs, c->lsave);
434 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300435 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300436 continue;
437 }
438 if (!done_ltab) {
439 done_ltab = 1;
440 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
441 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300442 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300443 continue;
444 }
445 break;
446 }
447 if (cnode->level)
448 ubifs_pack_nnode(c, buf + offs,
449 (struct ubifs_nnode *)cnode);
450 else
451 ubifs_pack_pnode(c, buf + offs,
452 (struct ubifs_pnode *)cnode);
453 /*
454 * The reason for the barriers is the same as in case of TNC.
455 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
456 * 'dirty_cow_pnode()' are the functions for which this is
457 * important.
458 */
459 clear_bit(DIRTY_CNODE, &cnode->flags);
460 smp_mb__before_clear_bit();
461 clear_bit(COW_ZNODE, &cnode->flags);
462 smp_mb__after_clear_bit();
463 offs += len;
Adrian Hunter73944a62008-09-12 18:13:31 +0300464 dbg_chk_lpt_sz(c, 1, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300465 cnode = cnode->cnext;
466 } while (cnode && cnode != c->lpt_cnext);
467
468 /* Make sure to place LPT's save table */
469 if (!done_lsave) {
470 if (offs + c->lsave_sz > c->leb_size) {
471 wlen = offs - from;
472 alen = ALIGN(wlen, c->min_io_size);
473 memset(buf + offs, 0xff, alen - wlen);
474 err = ubifs_leb_write(c, lnum, buf + from, from, alen,
475 UBI_SHORTTERM);
476 if (err)
477 return err;
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200478 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300479 err = realloc_lpt_leb(c, &lnum);
480 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300481 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200482 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300483 ubifs_assert(lnum >= c->lpt_first &&
484 lnum <= c->lpt_last);
485 err = ubifs_leb_unmap(c, lnum);
486 if (err)
487 return err;
488 }
489 done_lsave = 1;
490 ubifs_pack_lsave(c, buf + offs, c->lsave);
491 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300492 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300493 }
494
495 /* Make sure to place LPT's own lprops table */
496 if (!done_ltab) {
497 if (offs + c->ltab_sz > c->leb_size) {
498 wlen = offs - from;
499 alen = ALIGN(wlen, c->min_io_size);
500 memset(buf + offs, 0xff, alen - wlen);
501 err = ubifs_leb_write(c, lnum, buf + from, from, alen,
502 UBI_SHORTTERM);
503 if (err)
504 return err;
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200505 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300506 err = realloc_lpt_leb(c, &lnum);
507 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300508 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200509 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300510 ubifs_assert(lnum >= c->lpt_first &&
511 lnum <= c->lpt_last);
512 err = ubifs_leb_unmap(c, lnum);
513 if (err)
514 return err;
515 }
516 done_ltab = 1;
517 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
518 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300519 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300520 }
521
522 /* Write remaining data in buffer */
523 wlen = offs - from;
524 alen = ALIGN(wlen, c->min_io_size);
525 memset(buf + offs, 0xff, alen - wlen);
526 err = ubifs_leb_write(c, lnum, buf + from, from, alen, UBI_SHORTTERM);
527 if (err)
528 return err;
Adrian Hunter73944a62008-09-12 18:13:31 +0300529
530 dbg_chk_lpt_sz(c, 4, alen - wlen);
531 err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));
532 if (err)
533 return err;
534
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300535 c->nhead_lnum = lnum;
536 c->nhead_offs = ALIGN(offs, c->min_io_size);
537
538 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
539 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
540 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
541 if (c->big_lpt)
542 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
Adrian Hunter73944a62008-09-12 18:13:31 +0300543
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300544 return 0;
Adrian Hunter73944a62008-09-12 18:13:31 +0300545
546no_space:
547 ubifs_err("LPT out of space mismatch");
548 dbg_err("LPT out of space mismatch at LEB %d:%d needing %d, done_ltab "
Artem Bityutskiyf92b9822008-12-28 11:34:26 +0200549 "%d, done_lsave %d", lnum, offs, len, done_ltab, done_lsave);
Adrian Hunter73944a62008-09-12 18:13:31 +0300550 dbg_dump_lpt_info(c);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +0200551 dbg_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +0200552 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +0300553 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300554}
555
556/**
Adrian Hunter4a29d202009-01-27 15:22:54 +0200557 * next_pnode_to_dirty - find next pnode to dirty.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300558 * @c: UBIFS file-system description object
559 * @pnode: pnode
560 *
Adrian Hunter4a29d202009-01-27 15:22:54 +0200561 * This function returns the next pnode to dirty or %NULL if there are no more
562 * pnodes. Note that pnodes that have never been written (lnum == 0) are
563 * skipped.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300564 */
Adrian Hunter4a29d202009-01-27 15:22:54 +0200565static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,
566 struct ubifs_pnode *pnode)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300567{
568 struct ubifs_nnode *nnode;
569 int iip;
570
571 /* Try to go right */
572 nnode = pnode->parent;
Adrian Hunter4a29d202009-01-27 15:22:54 +0200573 for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300574 if (nnode->nbranch[iip].lnum)
575 return ubifs_get_pnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300576 }
577
578 /* Go up while can't go right */
579 do {
580 iip = nnode->iip + 1;
581 nnode = nnode->parent;
582 if (!nnode)
583 return NULL;
Adrian Hunter4a29d202009-01-27 15:22:54 +0200584 for (; iip < UBIFS_LPT_FANOUT; iip++) {
585 if (nnode->nbranch[iip].lnum)
586 break;
587 }
588 } while (iip >= UBIFS_LPT_FANOUT);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300589
590 /* Go right */
591 nnode = ubifs_get_nnode(c, nnode, iip);
592 if (IS_ERR(nnode))
593 return (void *)nnode;
594
595 /* Go down to level 1 */
596 while (nnode->level > 1) {
Adrian Hunter4a29d202009-01-27 15:22:54 +0200597 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {
598 if (nnode->nbranch[iip].lnum)
599 break;
600 }
601 if (iip >= UBIFS_LPT_FANOUT) {
602 /*
603 * Should not happen, but we need to keep going
604 * if it does.
605 */
606 iip = 0;
607 }
608 nnode = ubifs_get_nnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300609 if (IS_ERR(nnode))
610 return (void *)nnode;
611 }
612
Adrian Hunter4a29d202009-01-27 15:22:54 +0200613 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)
614 if (nnode->nbranch[iip].lnum)
615 break;
616 if (iip >= UBIFS_LPT_FANOUT)
617 /* Should not happen, but we need to keep going if it does */
618 iip = 0;
619 return ubifs_get_pnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300620}
621
622/**
623 * pnode_lookup - lookup a pnode in the LPT.
624 * @c: UBIFS file-system description object
625 * @i: pnode number (0 to main_lebs - 1)
626 *
627 * This function returns a pointer to the pnode on success or a negative
628 * error code on failure.
629 */
630static struct ubifs_pnode *pnode_lookup(struct ubifs_info *c, int i)
631{
632 int err, h, iip, shft;
633 struct ubifs_nnode *nnode;
634
635 if (!c->nroot) {
636 err = ubifs_read_nnode(c, NULL, 0);
637 if (err)
638 return ERR_PTR(err);
639 }
640 i <<= UBIFS_LPT_FANOUT_SHIFT;
641 nnode = c->nroot;
642 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
643 for (h = 1; h < c->lpt_hght; h++) {
644 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
645 shft -= UBIFS_LPT_FANOUT_SHIFT;
646 nnode = ubifs_get_nnode(c, nnode, iip);
647 if (IS_ERR(nnode))
648 return ERR_PTR(PTR_ERR(nnode));
649 }
650 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
651 return ubifs_get_pnode(c, nnode, iip);
652}
653
654/**
655 * add_pnode_dirt - add dirty space to LPT LEB properties.
656 * @c: UBIFS file-system description object
657 * @pnode: pnode for which to add dirt
658 */
659static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
660{
661 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
662 c->pnode_sz);
663}
664
665/**
666 * do_make_pnode_dirty - mark a pnode dirty.
667 * @c: UBIFS file-system description object
668 * @pnode: pnode to mark dirty
669 */
670static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
671{
672 /* Assumes cnext list is empty i.e. not called during commit */
673 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
674 struct ubifs_nnode *nnode;
675
676 c->dirty_pn_cnt += 1;
677 add_pnode_dirt(c, pnode);
678 /* Mark parent and ancestors dirty too */
679 nnode = pnode->parent;
680 while (nnode) {
681 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
682 c->dirty_nn_cnt += 1;
683 ubifs_add_nnode_dirt(c, nnode);
684 nnode = nnode->parent;
685 } else
686 break;
687 }
688 }
689}
690
691/**
692 * make_tree_dirty - mark the entire LEB properties tree dirty.
693 * @c: UBIFS file-system description object
694 *
695 * This function is used by the "small" LPT model to cause the entire LEB
696 * properties tree to be written. The "small" LPT model does not use LPT
697 * garbage collection because it is more efficient to write the entire tree
698 * (because it is small).
699 *
700 * This function returns %0 on success and a negative error code on failure.
701 */
702static int make_tree_dirty(struct ubifs_info *c)
703{
704 struct ubifs_pnode *pnode;
705
706 pnode = pnode_lookup(c, 0);
707 while (pnode) {
708 do_make_pnode_dirty(c, pnode);
Adrian Hunter4a29d202009-01-27 15:22:54 +0200709 pnode = next_pnode_to_dirty(c, pnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300710 if (IS_ERR(pnode))
711 return PTR_ERR(pnode);
712 }
713 return 0;
714}
715
716/**
717 * need_write_all - determine if the LPT area is running out of free space.
718 * @c: UBIFS file-system description object
719 *
720 * This function returns %1 if the LPT area is running out of free space and %0
721 * if it is not.
722 */
723static int need_write_all(struct ubifs_info *c)
724{
725 long long free = 0;
726 int i;
727
728 for (i = 0; i < c->lpt_lebs; i++) {
729 if (i + c->lpt_first == c->nhead_lnum)
730 free += c->leb_size - c->nhead_offs;
731 else if (c->ltab[i].free == c->leb_size)
732 free += c->leb_size;
733 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
734 free += c->leb_size;
735 }
736 /* Less than twice the size left */
737 if (free <= c->lpt_sz * 2)
738 return 1;
739 return 0;
740}
741
742/**
743 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
744 * @c: UBIFS file-system description object
745 *
746 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
747 * free space and so may be reused as soon as the next commit is completed.
748 * This function is called during start commit to mark LPT LEBs for trivial GC.
749 */
750static void lpt_tgc_start(struct ubifs_info *c)
751{
752 int i;
753
754 for (i = 0; i < c->lpt_lebs; i++) {
755 if (i + c->lpt_first == c->nhead_lnum)
756 continue;
757 if (c->ltab[i].dirty > 0 &&
758 c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
759 c->ltab[i].tgc = 1;
760 c->ltab[i].free = c->leb_size;
761 c->ltab[i].dirty = 0;
762 dbg_lp("LEB %d", i + c->lpt_first);
763 }
764 }
765}
766
767/**
768 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
769 * @c: UBIFS file-system description object
770 *
771 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
772 * free space and so may be reused as soon as the next commit is completed.
773 * This function is called after the commit is completed (master node has been
Artem Bityutskiy80736d42008-12-30 17:44:02 +0200774 * written) and un-maps LPT LEBs that were marked for trivial GC.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300775 */
776static int lpt_tgc_end(struct ubifs_info *c)
777{
778 int i, err;
779
780 for (i = 0; i < c->lpt_lebs; i++)
781 if (c->ltab[i].tgc) {
782 err = ubifs_leb_unmap(c, i + c->lpt_first);
783 if (err)
784 return err;
785 c->ltab[i].tgc = 0;
786 dbg_lp("LEB %d", i + c->lpt_first);
787 }
788 return 0;
789}
790
791/**
792 * populate_lsave - fill the lsave array with important LEB numbers.
793 * @c: the UBIFS file-system description object
794 *
795 * This function is only called for the "big" model. It records a small number
796 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
797 * most important to least important): empty, freeable, freeable index, dirty
798 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
799 * their pnodes into memory. That will stop us from having to scan the LPT
800 * straight away. For the "small" model we assume that scanning the LPT is no
801 * big deal.
802 */
803static void populate_lsave(struct ubifs_info *c)
804{
805 struct ubifs_lprops *lprops;
806 struct ubifs_lpt_heap *heap;
807 int i, cnt = 0;
808
809 ubifs_assert(c->big_lpt);
810 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
811 c->lpt_drty_flgs |= LSAVE_DIRTY;
812 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
813 }
814 list_for_each_entry(lprops, &c->empty_list, list) {
815 c->lsave[cnt++] = lprops->lnum;
816 if (cnt >= c->lsave_cnt)
817 return;
818 }
819 list_for_each_entry(lprops, &c->freeable_list, list) {
820 c->lsave[cnt++] = lprops->lnum;
821 if (cnt >= c->lsave_cnt)
822 return;
823 }
824 list_for_each_entry(lprops, &c->frdi_idx_list, list) {
825 c->lsave[cnt++] = lprops->lnum;
826 if (cnt >= c->lsave_cnt)
827 return;
828 }
829 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
830 for (i = 0; i < heap->cnt; i++) {
831 c->lsave[cnt++] = heap->arr[i]->lnum;
832 if (cnt >= c->lsave_cnt)
833 return;
834 }
835 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
836 for (i = 0; i < heap->cnt; i++) {
837 c->lsave[cnt++] = heap->arr[i]->lnum;
838 if (cnt >= c->lsave_cnt)
839 return;
840 }
841 heap = &c->lpt_heap[LPROPS_FREE - 1];
842 for (i = 0; i < heap->cnt; i++) {
843 c->lsave[cnt++] = heap->arr[i]->lnum;
844 if (cnt >= c->lsave_cnt)
845 return;
846 }
847 /* Fill it up completely */
848 while (cnt < c->lsave_cnt)
849 c->lsave[cnt++] = c->main_first;
850}
851
852/**
853 * nnode_lookup - lookup a nnode in the LPT.
854 * @c: UBIFS file-system description object
855 * @i: nnode number
856 *
857 * This function returns a pointer to the nnode on success or a negative
858 * error code on failure.
859 */
860static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
861{
862 int err, iip;
863 struct ubifs_nnode *nnode;
864
865 if (!c->nroot) {
866 err = ubifs_read_nnode(c, NULL, 0);
867 if (err)
868 return ERR_PTR(err);
869 }
870 nnode = c->nroot;
871 while (1) {
872 iip = i & (UBIFS_LPT_FANOUT - 1);
873 i >>= UBIFS_LPT_FANOUT_SHIFT;
874 if (!i)
875 break;
876 nnode = ubifs_get_nnode(c, nnode, iip);
877 if (IS_ERR(nnode))
878 return nnode;
879 }
880 return nnode;
881}
882
883/**
884 * make_nnode_dirty - find a nnode and, if found, make it dirty.
885 * @c: UBIFS file-system description object
886 * @node_num: nnode number of nnode to make dirty
887 * @lnum: LEB number where nnode was written
888 * @offs: offset where nnode was written
889 *
890 * This function is used by LPT garbage collection. LPT garbage collection is
891 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
892 * simply involves marking all the nodes in the LEB being garbage-collected as
893 * dirty. The dirty nodes are written next commit, after which the LEB is free
894 * to be reused.
895 *
896 * This function returns %0 on success and a negative error code on failure.
897 */
898static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
899 int offs)
900{
901 struct ubifs_nnode *nnode;
902
903 nnode = nnode_lookup(c, node_num);
904 if (IS_ERR(nnode))
905 return PTR_ERR(nnode);
906 if (nnode->parent) {
907 struct ubifs_nbranch *branch;
908
909 branch = &nnode->parent->nbranch[nnode->iip];
910 if (branch->lnum != lnum || branch->offs != offs)
911 return 0; /* nnode is obsolete */
912 } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
913 return 0; /* nnode is obsolete */
914 /* Assumes cnext list is empty i.e. not called during commit */
915 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
916 c->dirty_nn_cnt += 1;
917 ubifs_add_nnode_dirt(c, nnode);
918 /* Mark parent and ancestors dirty too */
919 nnode = nnode->parent;
920 while (nnode) {
921 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
922 c->dirty_nn_cnt += 1;
923 ubifs_add_nnode_dirt(c, nnode);
924 nnode = nnode->parent;
925 } else
926 break;
927 }
928 }
929 return 0;
930}
931
932/**
933 * make_pnode_dirty - find a pnode and, if found, make it dirty.
934 * @c: UBIFS file-system description object
935 * @node_num: pnode number of pnode to make dirty
936 * @lnum: LEB number where pnode was written
937 * @offs: offset where pnode was written
938 *
939 * This function is used by LPT garbage collection. LPT garbage collection is
940 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
941 * simply involves marking all the nodes in the LEB being garbage-collected as
942 * dirty. The dirty nodes are written next commit, after which the LEB is free
943 * to be reused.
944 *
945 * This function returns %0 on success and a negative error code on failure.
946 */
947static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
948 int offs)
949{
950 struct ubifs_pnode *pnode;
951 struct ubifs_nbranch *branch;
952
953 pnode = pnode_lookup(c, node_num);
954 if (IS_ERR(pnode))
955 return PTR_ERR(pnode);
956 branch = &pnode->parent->nbranch[pnode->iip];
957 if (branch->lnum != lnum || branch->offs != offs)
958 return 0;
959 do_make_pnode_dirty(c, pnode);
960 return 0;
961}
962
963/**
964 * make_ltab_dirty - make ltab node dirty.
965 * @c: UBIFS file-system description object
966 * @lnum: LEB number where ltab was written
967 * @offs: offset where ltab was written
968 *
969 * This function is used by LPT garbage collection. LPT garbage collection is
970 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
971 * simply involves marking all the nodes in the LEB being garbage-collected as
972 * dirty. The dirty nodes are written next commit, after which the LEB is free
973 * to be reused.
974 *
975 * This function returns %0 on success and a negative error code on failure.
976 */
977static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
978{
979 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
980 return 0; /* This ltab node is obsolete */
981 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
982 c->lpt_drty_flgs |= LTAB_DIRTY;
983 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
984 }
985 return 0;
986}
987
988/**
989 * make_lsave_dirty - make lsave node dirty.
990 * @c: UBIFS file-system description object
991 * @lnum: LEB number where lsave was written
992 * @offs: offset where lsave was written
993 *
994 * This function is used by LPT garbage collection. LPT garbage collection is
995 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
996 * simply involves marking all the nodes in the LEB being garbage-collected as
997 * dirty. The dirty nodes are written next commit, after which the LEB is free
998 * to be reused.
999 *
1000 * This function returns %0 on success and a negative error code on failure.
1001 */
1002static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1003{
1004 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1005 return 0; /* This lsave node is obsolete */
1006 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
1007 c->lpt_drty_flgs |= LSAVE_DIRTY;
1008 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
1009 }
1010 return 0;
1011}
1012
1013/**
1014 * make_node_dirty - make node dirty.
1015 * @c: UBIFS file-system description object
1016 * @node_type: LPT node type
1017 * @node_num: node number
1018 * @lnum: LEB number where node was written
1019 * @offs: offset where node was written
1020 *
1021 * This function is used by LPT garbage collection. LPT garbage collection is
1022 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1023 * simply involves marking all the nodes in the LEB being garbage-collected as
1024 * dirty. The dirty nodes are written next commit, after which the LEB is free
1025 * to be reused.
1026 *
1027 * This function returns %0 on success and a negative error code on failure.
1028 */
1029static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
1030 int lnum, int offs)
1031{
1032 switch (node_type) {
1033 case UBIFS_LPT_NNODE:
1034 return make_nnode_dirty(c, node_num, lnum, offs);
1035 case UBIFS_LPT_PNODE:
1036 return make_pnode_dirty(c, node_num, lnum, offs);
1037 case UBIFS_LPT_LTAB:
1038 return make_ltab_dirty(c, lnum, offs);
1039 case UBIFS_LPT_LSAVE:
1040 return make_lsave_dirty(c, lnum, offs);
1041 }
1042 return -EINVAL;
1043}
1044
1045/**
1046 * get_lpt_node_len - return the length of a node based on its type.
1047 * @c: UBIFS file-system description object
1048 * @node_type: LPT node type
1049 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001050static int get_lpt_node_len(const struct ubifs_info *c, int node_type)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001051{
1052 switch (node_type) {
1053 case UBIFS_LPT_NNODE:
1054 return c->nnode_sz;
1055 case UBIFS_LPT_PNODE:
1056 return c->pnode_sz;
1057 case UBIFS_LPT_LTAB:
1058 return c->ltab_sz;
1059 case UBIFS_LPT_LSAVE:
1060 return c->lsave_sz;
1061 }
1062 return 0;
1063}
1064
1065/**
1066 * get_pad_len - return the length of padding in a buffer.
1067 * @c: UBIFS file-system description object
1068 * @buf: buffer
1069 * @len: length of buffer
1070 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001071static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001072{
1073 int offs, pad_len;
1074
1075 if (c->min_io_size == 1)
1076 return 0;
1077 offs = c->leb_size - len;
1078 pad_len = ALIGN(offs, c->min_io_size) - offs;
1079 return pad_len;
1080}
1081
1082/**
1083 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1084 * @c: UBIFS file-system description object
1085 * @buf: buffer
1086 * @node_num: node number is returned here
1087 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001088static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,
1089 int *node_num)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001090{
1091 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1092 int pos = 0, node_type;
1093
1094 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1095 *node_num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1096 return node_type;
1097}
1098
1099/**
1100 * is_a_node - determine if a buffer contains a node.
1101 * @c: UBIFS file-system description object
1102 * @buf: buffer
1103 * @len: length of buffer
1104 *
1105 * This function returns %1 if the buffer contains a node or %0 if it does not.
1106 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001107static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001108{
1109 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1110 int pos = 0, node_type, node_len;
1111 uint16_t crc, calc_crc;
1112
Adrian Hunterbe2f6bd2008-09-26 12:52:21 +03001113 if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1114 return 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001115 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1116 if (node_type == UBIFS_LPT_NOT_A_NODE)
1117 return 0;
1118 node_len = get_lpt_node_len(c, node_type);
1119 if (!node_len || node_len > len)
1120 return 0;
1121 pos = 0;
1122 addr = buf;
1123 crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
1124 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1125 node_len - UBIFS_LPT_CRC_BYTES);
1126 if (crc != calc_crc)
1127 return 0;
1128 return 1;
1129}
1130
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001131/**
1132 * lpt_gc_lnum - garbage collect a LPT LEB.
1133 * @c: UBIFS file-system description object
1134 * @lnum: LEB number to garbage collect
1135 *
1136 * LPT garbage collection is used only for the "big" LPT model
1137 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1138 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1139 * next commit, after which the LEB is free to be reused.
1140 *
1141 * This function returns %0 on success and a negative error code on failure.
1142 */
1143static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1144{
1145 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1146 void *buf = c->lpt_buf;
1147
1148 dbg_lp("LEB %d", lnum);
1149 err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1150 if (err) {
1151 ubifs_err("cannot read LEB %d, error %d", lnum, err);
1152 return err;
1153 }
1154 while (1) {
1155 if (!is_a_node(c, buf, len)) {
1156 int pad_len;
1157
1158 pad_len = get_pad_len(c, buf, len);
1159 if (pad_len) {
1160 buf += pad_len;
1161 len -= pad_len;
1162 continue;
1163 }
1164 return 0;
1165 }
1166 node_type = get_lpt_node_type(c, buf, &node_num);
1167 node_len = get_lpt_node_len(c, node_type);
1168 offs = c->leb_size - len;
1169 ubifs_assert(node_len != 0);
1170 mutex_lock(&c->lp_mutex);
1171 err = make_node_dirty(c, node_type, node_num, lnum, offs);
1172 mutex_unlock(&c->lp_mutex);
1173 if (err)
1174 return err;
1175 buf += node_len;
1176 len -= node_len;
1177 }
1178 return 0;
1179}
1180
1181/**
1182 * lpt_gc - LPT garbage collection.
1183 * @c: UBIFS file-system description object
1184 *
1185 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1186 * Returns %0 on success and a negative error code on failure.
1187 */
1188static int lpt_gc(struct ubifs_info *c)
1189{
1190 int i, lnum = -1, dirty = 0;
1191
1192 mutex_lock(&c->lp_mutex);
1193 for (i = 0; i < c->lpt_lebs; i++) {
1194 ubifs_assert(!c->ltab[i].tgc);
1195 if (i + c->lpt_first == c->nhead_lnum ||
1196 c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1197 continue;
1198 if (c->ltab[i].dirty > dirty) {
1199 dirty = c->ltab[i].dirty;
1200 lnum = i + c->lpt_first;
1201 }
1202 }
1203 mutex_unlock(&c->lp_mutex);
1204 if (lnum == -1)
1205 return -ENOSPC;
1206 return lpt_gc_lnum(c, lnum);
1207}
1208
1209/**
1210 * ubifs_lpt_start_commit - UBIFS commit starts.
1211 * @c: the UBIFS file-system description object
1212 *
1213 * This function has to be called when UBIFS starts the commit operation.
1214 * This function "freezes" all currently dirty LEB properties and does not
1215 * change them anymore. Further changes are saved and tracked separately
1216 * because they are not part of this commit. This function returns zero in case
1217 * of success and a negative error code in case of failure.
1218 */
1219int ubifs_lpt_start_commit(struct ubifs_info *c)
1220{
1221 int err, cnt;
1222
1223 dbg_lp("");
1224
1225 mutex_lock(&c->lp_mutex);
Adrian Hunter73944a62008-09-12 18:13:31 +03001226 err = dbg_chk_lpt_free_spc(c);
1227 if (err)
1228 goto out;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001229 err = dbg_check_ltab(c);
1230 if (err)
1231 goto out;
1232
1233 if (c->check_lpt_free) {
1234 /*
1235 * We ensure there is enough free space in
1236 * ubifs_lpt_post_commit() by marking nodes dirty. That
1237 * information is lost when we unmount, so we also need
1238 * to check free space once after mounting also.
1239 */
1240 c->check_lpt_free = 0;
1241 while (need_write_all(c)) {
1242 mutex_unlock(&c->lp_mutex);
1243 err = lpt_gc(c);
1244 if (err)
1245 return err;
1246 mutex_lock(&c->lp_mutex);
1247 }
1248 }
1249
1250 lpt_tgc_start(c);
1251
1252 if (!c->dirty_pn_cnt) {
1253 dbg_cmt("no cnodes to commit");
1254 err = 0;
1255 goto out;
1256 }
1257
1258 if (!c->big_lpt && need_write_all(c)) {
1259 /* If needed, write everything */
1260 err = make_tree_dirty(c);
1261 if (err)
1262 goto out;
1263 lpt_tgc_start(c);
1264 }
1265
1266 if (c->big_lpt)
1267 populate_lsave(c);
1268
1269 cnt = get_cnodes_to_commit(c);
1270 ubifs_assert(cnt != 0);
1271
1272 err = layout_cnodes(c);
1273 if (err)
1274 goto out;
1275
1276 /* Copy the LPT's own lprops for end commit to write */
1277 memcpy(c->ltab_cmt, c->ltab,
1278 sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1279 c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1280
1281out:
1282 mutex_unlock(&c->lp_mutex);
1283 return err;
1284}
1285
1286/**
1287 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1288 * @c: UBIFS file-system description object
1289 */
1290static void free_obsolete_cnodes(struct ubifs_info *c)
1291{
1292 struct ubifs_cnode *cnode, *cnext;
1293
1294 cnext = c->lpt_cnext;
1295 if (!cnext)
1296 return;
1297 do {
1298 cnode = cnext;
1299 cnext = cnode->cnext;
1300 if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1301 kfree(cnode);
1302 else
1303 cnode->cnext = NULL;
1304 } while (cnext != c->lpt_cnext);
1305 c->lpt_cnext = NULL;
1306}
1307
1308/**
1309 * ubifs_lpt_end_commit - finish the commit operation.
1310 * @c: the UBIFS file-system description object
1311 *
1312 * This function has to be called when the commit operation finishes. It
1313 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1314 * the media. Returns zero in case of success and a negative error code in case
1315 * of failure.
1316 */
1317int ubifs_lpt_end_commit(struct ubifs_info *c)
1318{
1319 int err;
1320
1321 dbg_lp("");
1322
1323 if (!c->lpt_cnext)
1324 return 0;
1325
1326 err = write_cnodes(c);
1327 if (err)
1328 return err;
1329
1330 mutex_lock(&c->lp_mutex);
1331 free_obsolete_cnodes(c);
1332 mutex_unlock(&c->lp_mutex);
1333
1334 return 0;
1335}
1336
1337/**
1338 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1339 * @c: UBIFS file-system description object
1340 *
1341 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1342 * commit for the "big" LPT model.
1343 */
1344int ubifs_lpt_post_commit(struct ubifs_info *c)
1345{
1346 int err;
1347
1348 mutex_lock(&c->lp_mutex);
1349 err = lpt_tgc_end(c);
1350 if (err)
1351 goto out;
1352 if (c->big_lpt)
1353 while (need_write_all(c)) {
1354 mutex_unlock(&c->lp_mutex);
1355 err = lpt_gc(c);
1356 if (err)
1357 return err;
1358 mutex_lock(&c->lp_mutex);
1359 }
1360out:
1361 mutex_unlock(&c->lp_mutex);
1362 return err;
1363}
1364
1365/**
1366 * first_nnode - find the first nnode in memory.
1367 * @c: UBIFS file-system description object
1368 * @hght: height of tree where nnode found is returned here
1369 *
1370 * This function returns a pointer to the nnode found or %NULL if no nnode is
1371 * found. This function is a helper to 'ubifs_lpt_free()'.
1372 */
1373static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1374{
1375 struct ubifs_nnode *nnode;
1376 int h, i, found;
1377
1378 nnode = c->nroot;
1379 *hght = 0;
1380 if (!nnode)
1381 return NULL;
1382 for (h = 1; h < c->lpt_hght; h++) {
1383 found = 0;
1384 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1385 if (nnode->nbranch[i].nnode) {
1386 found = 1;
1387 nnode = nnode->nbranch[i].nnode;
1388 *hght = h;
1389 break;
1390 }
1391 }
1392 if (!found)
1393 break;
1394 }
1395 return nnode;
1396}
1397
1398/**
1399 * next_nnode - find the next nnode in memory.
1400 * @c: UBIFS file-system description object
1401 * @nnode: nnode from which to start.
1402 * @hght: height of tree where nnode is, is passed and returned here
1403 *
1404 * This function returns a pointer to the nnode found or %NULL if no nnode is
1405 * found. This function is a helper to 'ubifs_lpt_free()'.
1406 */
1407static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1408 struct ubifs_nnode *nnode, int *hght)
1409{
1410 struct ubifs_nnode *parent;
1411 int iip, h, i, found;
1412
1413 parent = nnode->parent;
1414 if (!parent)
1415 return NULL;
1416 if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1417 *hght -= 1;
1418 return parent;
1419 }
1420 for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1421 nnode = parent->nbranch[iip].nnode;
1422 if (nnode)
1423 break;
1424 }
1425 if (!nnode) {
1426 *hght -= 1;
1427 return parent;
1428 }
1429 for (h = *hght + 1; h < c->lpt_hght; h++) {
1430 found = 0;
1431 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1432 if (nnode->nbranch[i].nnode) {
1433 found = 1;
1434 nnode = nnode->nbranch[i].nnode;
1435 *hght = h;
1436 break;
1437 }
1438 }
1439 if (!found)
1440 break;
1441 }
1442 return nnode;
1443}
1444
1445/**
1446 * ubifs_lpt_free - free resources owned by the LPT.
1447 * @c: UBIFS file-system description object
1448 * @wr_only: free only resources used for writing
1449 */
1450void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1451{
1452 struct ubifs_nnode *nnode;
1453 int i, hght;
1454
1455 /* Free write-only things first */
1456
1457 free_obsolete_cnodes(c); /* Leftover from a failed commit */
1458
1459 vfree(c->ltab_cmt);
1460 c->ltab_cmt = NULL;
1461 vfree(c->lpt_buf);
1462 c->lpt_buf = NULL;
1463 kfree(c->lsave);
1464 c->lsave = NULL;
1465
1466 if (wr_only)
1467 return;
1468
1469 /* Now free the rest */
1470
1471 nnode = first_nnode(c, &hght);
1472 while (nnode) {
1473 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1474 kfree(nnode->nbranch[i].nnode);
1475 nnode = next_nnode(c, nnode, &hght);
1476 }
1477 for (i = 0; i < LPROPS_HEAP_CNT; i++)
1478 kfree(c->lpt_heap[i].arr);
1479 kfree(c->dirty_idx.arr);
1480 kfree(c->nroot);
1481 vfree(c->ltab);
1482 kfree(c->lpt_nod_buf);
1483}
1484
1485#ifdef CONFIG_UBIFS_FS_DEBUG
1486
1487/**
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001488 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001489 * @buf: buffer
1490 * @len: buffer length
1491 */
1492static int dbg_is_all_ff(uint8_t *buf, int len)
1493{
1494 int i;
1495
1496 for (i = 0; i < len; i++)
1497 if (buf[i] != 0xff)
1498 return 0;
1499 return 1;
1500}
1501
1502/**
1503 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1504 * @c: the UBIFS file-system description object
1505 * @lnum: LEB number where nnode was written
1506 * @offs: offset where nnode was written
1507 */
1508static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1509{
1510 struct ubifs_nnode *nnode;
1511 int hght;
1512
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001513 /* Entire tree is in memory so first_nnode / next_nnode are OK */
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001514 nnode = first_nnode(c, &hght);
1515 for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1516 struct ubifs_nbranch *branch;
1517
1518 cond_resched();
1519 if (nnode->parent) {
1520 branch = &nnode->parent->nbranch[nnode->iip];
1521 if (branch->lnum != lnum || branch->offs != offs)
1522 continue;
1523 if (test_bit(DIRTY_CNODE, &nnode->flags))
1524 return 1;
1525 return 0;
1526 } else {
1527 if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1528 continue;
1529 if (test_bit(DIRTY_CNODE, &nnode->flags))
1530 return 1;
1531 return 0;
1532 }
1533 }
1534 return 1;
1535}
1536
1537/**
1538 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1539 * @c: the UBIFS file-system description object
1540 * @lnum: LEB number where pnode was written
1541 * @offs: offset where pnode was written
1542 */
1543static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1544{
1545 int i, cnt;
1546
1547 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1548 for (i = 0; i < cnt; i++) {
1549 struct ubifs_pnode *pnode;
1550 struct ubifs_nbranch *branch;
1551
1552 cond_resched();
1553 pnode = pnode_lookup(c, i);
1554 if (IS_ERR(pnode))
1555 return PTR_ERR(pnode);
1556 branch = &pnode->parent->nbranch[pnode->iip];
1557 if (branch->lnum != lnum || branch->offs != offs)
1558 continue;
1559 if (test_bit(DIRTY_CNODE, &pnode->flags))
1560 return 1;
1561 return 0;
1562 }
1563 return 1;
1564}
1565
1566/**
1567 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1568 * @c: the UBIFS file-system description object
1569 * @lnum: LEB number where ltab node was written
1570 * @offs: offset where ltab node was written
1571 */
1572static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1573{
1574 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1575 return 1;
1576 return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1577}
1578
1579/**
1580 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1581 * @c: the UBIFS file-system description object
1582 * @lnum: LEB number where lsave node was written
1583 * @offs: offset where lsave node was written
1584 */
1585static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1586{
1587 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1588 return 1;
1589 return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1590}
1591
1592/**
1593 * dbg_is_node_dirty - determine if a node is dirty.
1594 * @c: the UBIFS file-system description object
1595 * @node_type: node type
1596 * @lnum: LEB number where node was written
1597 * @offs: offset where node was written
1598 */
1599static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1600 int offs)
1601{
1602 switch (node_type) {
1603 case UBIFS_LPT_NNODE:
1604 return dbg_is_nnode_dirty(c, lnum, offs);
1605 case UBIFS_LPT_PNODE:
1606 return dbg_is_pnode_dirty(c, lnum, offs);
1607 case UBIFS_LPT_LTAB:
1608 return dbg_is_ltab_dirty(c, lnum, offs);
1609 case UBIFS_LPT_LSAVE:
1610 return dbg_is_lsave_dirty(c, lnum, offs);
1611 }
1612 return 1;
1613}
1614
1615/**
1616 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1617 * @c: the UBIFS file-system description object
1618 * @lnum: LEB number where node was written
1619 * @offs: offset where node was written
1620 *
1621 * This function returns %0 on success and a negative error code on failure.
1622 */
1623static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1624{
1625 int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1626 int ret;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001627 void *buf = c->dbg->buf;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001628
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001629 if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
1630 return 0;
1631
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001632 dbg_lp("LEB %d", lnum);
1633 err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1634 if (err) {
1635 dbg_msg("ubi_read failed, LEB %d, error %d", lnum, err);
1636 return err;
1637 }
1638 while (1) {
1639 if (!is_a_node(c, buf, len)) {
1640 int i, pad_len;
1641
1642 pad_len = get_pad_len(c, buf, len);
1643 if (pad_len) {
1644 buf += pad_len;
1645 len -= pad_len;
1646 dirty += pad_len;
1647 continue;
1648 }
1649 if (!dbg_is_all_ff(buf, len)) {
1650 dbg_msg("invalid empty space in LEB %d at %d",
1651 lnum, c->leb_size - len);
1652 err = -EINVAL;
1653 }
1654 i = lnum - c->lpt_first;
1655 if (len != c->ltab[i].free) {
1656 dbg_msg("invalid free space in LEB %d "
1657 "(free %d, expected %d)",
1658 lnum, len, c->ltab[i].free);
1659 err = -EINVAL;
1660 }
1661 if (dirty != c->ltab[i].dirty) {
1662 dbg_msg("invalid dirty space in LEB %d "
1663 "(dirty %d, expected %d)",
1664 lnum, dirty, c->ltab[i].dirty);
1665 err = -EINVAL;
1666 }
1667 return err;
1668 }
1669 node_type = get_lpt_node_type(c, buf, &node_num);
1670 node_len = get_lpt_node_len(c, node_type);
1671 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1672 if (ret == 1)
1673 dirty += node_len;
1674 buf += node_len;
1675 len -= node_len;
1676 }
1677}
1678
1679/**
1680 * dbg_check_ltab - check the free and dirty space in the ltab.
1681 * @c: the UBIFS file-system description object
1682 *
1683 * This function returns %0 on success and a negative error code on failure.
1684 */
1685int dbg_check_ltab(struct ubifs_info *c)
1686{
1687 int lnum, err, i, cnt;
1688
1689 if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
1690 return 0;
1691
1692 /* Bring the entire tree into memory */
1693 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1694 for (i = 0; i < cnt; i++) {
1695 struct ubifs_pnode *pnode;
1696
1697 pnode = pnode_lookup(c, i);
1698 if (IS_ERR(pnode))
1699 return PTR_ERR(pnode);
1700 cond_resched();
1701 }
1702
1703 /* Check nodes */
1704 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1705 if (err)
1706 return err;
1707
1708 /* Check each LEB */
1709 for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1710 err = dbg_check_ltab_lnum(c, lnum);
1711 if (err) {
1712 dbg_err("failed at LEB %d", lnum);
1713 return err;
1714 }
1715 }
1716
1717 dbg_lp("succeeded");
1718 return 0;
1719}
1720
Adrian Hunter73944a62008-09-12 18:13:31 +03001721/**
1722 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1723 * @c: the UBIFS file-system description object
1724 *
1725 * This function returns %0 on success and a negative error code on failure.
1726 */
1727int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1728{
1729 long long free = 0;
1730 int i;
1731
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001732 if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
1733 return 0;
1734
Adrian Hunter73944a62008-09-12 18:13:31 +03001735 for (i = 0; i < c->lpt_lebs; i++) {
1736 if (c->ltab[i].tgc || c->ltab[i].cmt)
1737 continue;
1738 if (i + c->lpt_first == c->nhead_lnum)
1739 free += c->leb_size - c->nhead_offs;
1740 else if (c->ltab[i].free == c->leb_size)
1741 free += c->leb_size;
1742 }
1743 if (free < c->lpt_sz) {
1744 dbg_err("LPT space error: free %lld lpt_sz %lld",
1745 free, c->lpt_sz);
1746 dbg_dump_lpt_info(c);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001747 dbg_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001748 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +03001749 return -EINVAL;
1750 }
1751 return 0;
1752}
1753
1754/**
1755 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1756 * @c: the UBIFS file-system description object
Adrian Hunter2bc275e2009-02-05 13:08:11 +02001757 * @action: what to do
Adrian Hunter73944a62008-09-12 18:13:31 +03001758 * @len: length written
1759 *
1760 * This function returns %0 on success and a negative error code on failure.
Adrian Hunter2bc275e2009-02-05 13:08:11 +02001761 * The @action argument may be one of:
1762 * o %0 - LPT debugging checking starts, initialize debugging variables;
1763 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1764 * o %2 - switched to a different LEB and wasted @len bytes;
1765 * o %3 - check that we've written the right number of bytes.
1766 * o %4 - wasted @len bytes;
Adrian Hunter73944a62008-09-12 18:13:31 +03001767 */
1768int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1769{
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001770 struct ubifs_debug_info *d = c->dbg;
Adrian Hunter73944a62008-09-12 18:13:31 +03001771 long long chk_lpt_sz, lpt_sz;
1772 int err = 0;
1773
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001774 if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
1775 return 0;
1776
Adrian Hunter73944a62008-09-12 18:13:31 +03001777 switch (action) {
1778 case 0:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001779 d->chk_lpt_sz = 0;
1780 d->chk_lpt_sz2 = 0;
1781 d->chk_lpt_lebs = 0;
1782 d->chk_lpt_wastage = 0;
Adrian Hunter73944a62008-09-12 18:13:31 +03001783 if (c->dirty_pn_cnt > c->pnode_cnt) {
1784 dbg_err("dirty pnodes %d exceed max %d",
1785 c->dirty_pn_cnt, c->pnode_cnt);
1786 err = -EINVAL;
1787 }
1788 if (c->dirty_nn_cnt > c->nnode_cnt) {
1789 dbg_err("dirty nnodes %d exceed max %d",
1790 c->dirty_nn_cnt, c->nnode_cnt);
1791 err = -EINVAL;
1792 }
1793 return err;
1794 case 1:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001795 d->chk_lpt_sz += len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001796 return 0;
1797 case 2:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001798 d->chk_lpt_sz += len;
1799 d->chk_lpt_wastage += len;
1800 d->chk_lpt_lebs += 1;
Adrian Hunter73944a62008-09-12 18:13:31 +03001801 return 0;
1802 case 3:
1803 chk_lpt_sz = c->leb_size;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001804 chk_lpt_sz *= d->chk_lpt_lebs;
Adrian Hunter73944a62008-09-12 18:13:31 +03001805 chk_lpt_sz += len - c->nhead_offs;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001806 if (d->chk_lpt_sz != chk_lpt_sz) {
Adrian Hunter73944a62008-09-12 18:13:31 +03001807 dbg_err("LPT wrote %lld but space used was %lld",
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001808 d->chk_lpt_sz, chk_lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001809 err = -EINVAL;
1810 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001811 if (d->chk_lpt_sz > c->lpt_sz) {
Adrian Hunter73944a62008-09-12 18:13:31 +03001812 dbg_err("LPT wrote %lld but lpt_sz is %lld",
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001813 d->chk_lpt_sz, c->lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001814 err = -EINVAL;
1815 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001816 if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
Adrian Hunter73944a62008-09-12 18:13:31 +03001817 dbg_err("LPT layout size %lld but wrote %lld",
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001818 d->chk_lpt_sz, d->chk_lpt_sz2);
Adrian Hunter73944a62008-09-12 18:13:31 +03001819 err = -EINVAL;
1820 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001821 if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
Adrian Hunter73944a62008-09-12 18:13:31 +03001822 dbg_err("LPT new nhead offs: expected %d was %d",
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001823 d->new_nhead_offs, len);
Adrian Hunter73944a62008-09-12 18:13:31 +03001824 err = -EINVAL;
1825 }
1826 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1827 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1828 lpt_sz += c->ltab_sz;
1829 if (c->big_lpt)
1830 lpt_sz += c->lsave_sz;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001831 if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
Adrian Hunter73944a62008-09-12 18:13:31 +03001832 dbg_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001833 d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001834 err = -EINVAL;
1835 }
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001836 if (err) {
Adrian Hunter73944a62008-09-12 18:13:31 +03001837 dbg_dump_lpt_info(c);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001838 dbg_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001839 dump_stack();
1840 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001841 d->chk_lpt_sz2 = d->chk_lpt_sz;
1842 d->chk_lpt_sz = 0;
1843 d->chk_lpt_wastage = 0;
1844 d->chk_lpt_lebs = 0;
1845 d->new_nhead_offs = len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001846 return err;
1847 case 4:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001848 d->chk_lpt_sz += len;
1849 d->chk_lpt_wastage += len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001850 return 0;
1851 default:
1852 return -EINVAL;
1853 }
1854}
1855
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001856/**
1857 * dbg_dump_lpt_leb - dump an LPT LEB.
1858 * @c: UBIFS file-system description object
1859 * @lnum: LEB number to dump
1860 *
1861 * This function dumps an LEB from LPT area. Nodes in this area are very
1862 * different to nodes in the main area (e.g., they do not have common headers,
1863 * they do not have 8-byte alignments, etc), so we have a separate function to
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001864 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001865 */
1866static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1867{
1868 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1869 void *buf = c->dbg->buf;
1870
1871 printk(KERN_DEBUG "(pid %d) start dumping LEB %d\n",
1872 current->pid, lnum);
1873 err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1874 if (err) {
1875 ubifs_err("cannot read LEB %d, error %d", lnum, err);
1876 return;
1877 }
1878 while (1) {
1879 offs = c->leb_size - len;
1880 if (!is_a_node(c, buf, len)) {
1881 int pad_len;
1882
1883 pad_len = get_pad_len(c, buf, len);
1884 if (pad_len) {
1885 printk(KERN_DEBUG "LEB %d:%d, pad %d bytes\n",
1886 lnum, offs, pad_len);
1887 buf += pad_len;
1888 len -= pad_len;
1889 continue;
1890 }
1891 if (len)
1892 printk(KERN_DEBUG "LEB %d:%d, free %d bytes\n",
1893 lnum, offs, len);
1894 break;
1895 }
1896
1897 node_type = get_lpt_node_type(c, buf, &node_num);
1898 switch (node_type) {
1899 case UBIFS_LPT_PNODE:
1900 {
1901 node_len = c->pnode_sz;
1902 if (c->big_lpt)
1903 printk(KERN_DEBUG "LEB %d:%d, pnode num %d\n",
1904 lnum, offs, node_num);
1905 else
1906 printk(KERN_DEBUG "LEB %d:%d, pnode\n",
1907 lnum, offs);
1908 break;
1909 }
1910 case UBIFS_LPT_NNODE:
1911 {
1912 int i;
1913 struct ubifs_nnode nnode;
1914
1915 node_len = c->nnode_sz;
1916 if (c->big_lpt)
1917 printk(KERN_DEBUG "LEB %d:%d, nnode num %d, ",
1918 lnum, offs, node_num);
1919 else
1920 printk(KERN_DEBUG "LEB %d:%d, nnode, ",
1921 lnum, offs);
1922 err = ubifs_unpack_nnode(c, buf, &nnode);
1923 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
Artem Bityutskiyc9927c32009-03-16 09:42:03 +02001924 printk(KERN_CONT "%d:%d", nnode.nbranch[i].lnum,
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001925 nnode.nbranch[i].offs);
1926 if (i != UBIFS_LPT_FANOUT - 1)
Artem Bityutskiyc9927c32009-03-16 09:42:03 +02001927 printk(KERN_CONT ", ");
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001928 }
Artem Bityutskiyc9927c32009-03-16 09:42:03 +02001929 printk(KERN_CONT "\n");
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001930 break;
1931 }
1932 case UBIFS_LPT_LTAB:
1933 node_len = c->ltab_sz;
1934 printk(KERN_DEBUG "LEB %d:%d, ltab\n",
1935 lnum, offs);
1936 break;
1937 case UBIFS_LPT_LSAVE:
1938 node_len = c->lsave_sz;
1939 printk(KERN_DEBUG "LEB %d:%d, lsave len\n", lnum, offs);
1940 break;
1941 default:
1942 ubifs_err("LPT node type %d not recognized", node_type);
1943 return;
1944 }
1945
1946 buf += node_len;
1947 len -= node_len;
1948 }
1949
1950 printk(KERN_DEBUG "(pid %d) finish dumping LEB %d\n",
1951 current->pid, lnum);
1952}
1953
1954/**
1955 * dbg_dump_lpt_lebs - dump LPT lebs.
1956 * @c: UBIFS file-system description object
1957 *
1958 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1959 * locked.
1960 */
1961void dbg_dump_lpt_lebs(const struct ubifs_info *c)
1962{
1963 int i;
1964
1965 printk(KERN_DEBUG "(pid %d) start dumping all LPT LEBs\n",
1966 current->pid);
1967 for (i = 0; i < c->lpt_lebs; i++)
1968 dump_lpt_leb(c, i + c->lpt_first);
1969 printk(KERN_DEBUG "(pid %d) finish dumping all LPT LEBs\n",
1970 current->pid);
1971}
1972
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001973#endif /* CONFIG_UBIFS_FS_DEBUG */