1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * This file is part of UBIFS.
4 *
5 * Copyright (C) 2006-2008 Nokia Corporation.
6 *
7 * Authors: Adrian Hunter
8 * Artem Bityutskiy (Битюцкий Артём)
9 */
10
11 /*
12 * This file implements commit-related functionality of the LEB properties
13 * subsystem.
14 */
15
16 #ifndef __UBOOT__
17 #include <linux/crc16.h>
18 #include <linux/slab.h>
19 #include <linux/random.h>
20 #else
21 #include <linux/compat.h>
22 #include <linux/err.h>
23 #include "crc16.h"
24 #endif
25 #include "ubifs.h"
26
27 #ifndef __UBOOT__
28 static int dbg_populate_lsave(struct ubifs_info *c);
29 #endif
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 */
first_dirty_cnode(struct ubifs_nnode * nnode)38 static 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 */
next_dirty_cnode(struct ubifs_cnode * cnode)68 static 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 */
get_cnodes_to_commit(struct ubifs_info * c)95 static 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_CNODE, &cnode->flags));
113 __set_bit(COW_CNODE, &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 */
upd_ltab(struct ubifs_info * c,int lnum,int free,int dirty)136 static 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 */
alloc_lpt_leb(struct ubifs_info * c,int * lnum)156 static 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 }
180 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 */
layout_cnodes(struct ubifs_info * c)189 static 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
194 err = dbg_chk_lpt_sz(c, 0, 0);
195 if (err)
196 return err;
197 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;
210 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
211 }
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;
218 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
219 }
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);
232 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
233 err = alloc_lpt_leb(c, &lnum);
234 if (err)
235 goto no_space;
236 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;
245 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
246 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;
253 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
254 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;
266 dbg_chk_lpt_sz(c, 1, len);
267 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);
275 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
276 err = alloc_lpt_leb(c, &lnum);
277 if (err)
278 goto no_space;
279 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;
287 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
288 }
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);
295 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
296 err = alloc_lpt_leb(c, &lnum);
297 if (err)
298 goto no_space;
299 offs = 0;
300 ubifs_assert(lnum >= c->lpt_first &&
301 lnum <= c->lpt_last);
302 }
303 c->ltab_lnum = lnum;
304 c->ltab_offs = offs;
305 offs += c->ltab_sz;
306 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
307 }
308
309 alen = ALIGN(offs, c->min_io_size);
310 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
311 dbg_chk_lpt_sz(c, 4, alen - offs);
312 err = dbg_chk_lpt_sz(c, 3, alen);
313 if (err)
314 return err;
315 return 0;
316
317 no_space:
318 ubifs_err(c, "LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
319 lnum, offs, len, done_ltab, done_lsave);
320 ubifs_dump_lpt_info(c);
321 ubifs_dump_lpt_lebs(c);
322 dump_stack();
323 return err;
324 }
325
326 #ifndef __UBOOT__
327 /**
328 * realloc_lpt_leb - allocate an LPT LEB that is empty.
329 * @c: UBIFS file-system description object
330 * @lnum: LEB number is passed and returned here
331 *
332 * This function duplicates exactly the results of the function alloc_lpt_leb.
333 * It is used during end commit to reallocate the same LEB numbers that were
334 * allocated by alloc_lpt_leb during start commit.
335 *
336 * This function finds the next LEB that was allocated by the alloc_lpt_leb
337 * function starting from @lnum. If a LEB is found it is returned in @lnum and
338 * the function returns %0. Otherwise the function returns -ENOSPC.
339 * Note however, that LPT is designed never to run out of space.
340 */
realloc_lpt_leb(struct ubifs_info * c,int * lnum)341 static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
342 {
343 int i, n;
344
345 n = *lnum - c->lpt_first + 1;
346 for (i = n; i < c->lpt_lebs; i++)
347 if (c->ltab[i].cmt) {
348 c->ltab[i].cmt = 0;
349 *lnum = i + c->lpt_first;
350 return 0;
351 }
352
353 for (i = 0; i < n; i++)
354 if (c->ltab[i].cmt) {
355 c->ltab[i].cmt = 0;
356 *lnum = i + c->lpt_first;
357 return 0;
358 }
359 return -ENOSPC;
360 }
361
362 /**
363 * write_cnodes - write cnodes for commit.
364 * @c: UBIFS file-system description object
365 *
366 * This function returns %0 on success and a negative error code on failure.
367 */
write_cnodes(struct ubifs_info * c)368 static int write_cnodes(struct ubifs_info *c)
369 {
370 int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
371 struct ubifs_cnode *cnode;
372 void *buf = c->lpt_buf;
373
374 cnode = c->lpt_cnext;
375 if (!cnode)
376 return 0;
377 lnum = c->nhead_lnum;
378 offs = c->nhead_offs;
379 from = offs;
380 /* Ensure empty LEB is unmapped */
381 if (offs == 0) {
382 err = ubifs_leb_unmap(c, lnum);
383 if (err)
384 return err;
385 }
386 /* Try to place lsave and ltab nicely */
387 done_lsave = !c->big_lpt;
388 done_ltab = 0;
389 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
390 done_lsave = 1;
391 ubifs_pack_lsave(c, buf + offs, c->lsave);
392 offs += c->lsave_sz;
393 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
394 }
395
396 if (offs + c->ltab_sz <= c->leb_size) {
397 done_ltab = 1;
398 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
399 offs += c->ltab_sz;
400 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
401 }
402
403 /* Loop for each cnode */
404 do {
405 if (cnode->level)
406 len = c->nnode_sz;
407 else
408 len = c->pnode_sz;
409 while (offs + len > c->leb_size) {
410 wlen = offs - from;
411 if (wlen) {
412 alen = ALIGN(wlen, c->min_io_size);
413 memset(buf + offs, 0xff, alen - wlen);
414 err = ubifs_leb_write(c, lnum, buf + from, from,
415 alen);
416 if (err)
417 return err;
418 }
419 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
420 err = realloc_lpt_leb(c, &lnum);
421 if (err)
422 goto no_space;
423 offs = from = 0;
424 ubifs_assert(lnum >= c->lpt_first &&
425 lnum <= c->lpt_last);
426 err = ubifs_leb_unmap(c, lnum);
427 if (err)
428 return err;
429 /* Try to place lsave and ltab nicely */
430 if (!done_lsave) {
431 done_lsave = 1;
432 ubifs_pack_lsave(c, buf + offs, c->lsave);
433 offs += c->lsave_sz;
434 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
435 continue;
436 }
437 if (!done_ltab) {
438 done_ltab = 1;
439 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
440 offs += c->ltab_sz;
441 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
442 continue;
443 }
444 break;
445 }
446 if (cnode->level)
447 ubifs_pack_nnode(c, buf + offs,
448 (struct ubifs_nnode *)cnode);
449 else
450 ubifs_pack_pnode(c, buf + offs,
451 (struct ubifs_pnode *)cnode);
452 /*
453 * The reason for the barriers is the same as in case of TNC.
454 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
455 * 'dirty_cow_pnode()' are the functions for which this is
456 * important.
457 */
458 clear_bit(DIRTY_CNODE, &cnode->flags);
459 smp_mb__before_atomic();
460 clear_bit(COW_CNODE, &cnode->flags);
461 smp_mb__after_atomic();
462 offs += len;
463 dbg_chk_lpt_sz(c, 1, len);
464 cnode = cnode->cnext;
465 } while (cnode && cnode != c->lpt_cnext);
466
467 /* Make sure to place LPT's save table */
468 if (!done_lsave) {
469 if (offs + c->lsave_sz > c->leb_size) {
470 wlen = offs - from;
471 alen = ALIGN(wlen, c->min_io_size);
472 memset(buf + offs, 0xff, alen - wlen);
473 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
474 if (err)
475 return err;
476 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
477 err = realloc_lpt_leb(c, &lnum);
478 if (err)
479 goto no_space;
480 offs = from = 0;
481 ubifs_assert(lnum >= c->lpt_first &&
482 lnum <= c->lpt_last);
483 err = ubifs_leb_unmap(c, lnum);
484 if (err)
485 return err;
486 }
487 done_lsave = 1;
488 ubifs_pack_lsave(c, buf + offs, c->lsave);
489 offs += c->lsave_sz;
490 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
491 }
492
493 /* Make sure to place LPT's own lprops table */
494 if (!done_ltab) {
495 if (offs + c->ltab_sz > c->leb_size) {
496 wlen = offs - from;
497 alen = ALIGN(wlen, c->min_io_size);
498 memset(buf + offs, 0xff, alen - wlen);
499 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
500 if (err)
501 return err;
502 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
503 err = realloc_lpt_leb(c, &lnum);
504 if (err)
505 goto no_space;
506 offs = from = 0;
507 ubifs_assert(lnum >= c->lpt_first &&
508 lnum <= c->lpt_last);
509 err = ubifs_leb_unmap(c, lnum);
510 if (err)
511 return err;
512 }
513 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
514 offs += c->ltab_sz;
515 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
516 }
517
518 /* Write remaining data in buffer */
519 wlen = offs - from;
520 alen = ALIGN(wlen, c->min_io_size);
521 memset(buf + offs, 0xff, alen - wlen);
522 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
523 if (err)
524 return err;
525
526 dbg_chk_lpt_sz(c, 4, alen - wlen);
527 err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));
528 if (err)
529 return err;
530
531 c->nhead_lnum = lnum;
532 c->nhead_offs = ALIGN(offs, c->min_io_size);
533
534 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
535 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
536 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
537 if (c->big_lpt)
538 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
539
540 return 0;
541
542 no_space:
543 ubifs_err(c, "LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
544 lnum, offs, len, done_ltab, done_lsave);
545 ubifs_dump_lpt_info(c);
546 ubifs_dump_lpt_lebs(c);
547 dump_stack();
548 return err;
549 }
550 #endif
551
552 /**
553 * next_pnode_to_dirty - find next pnode to dirty.
554 * @c: UBIFS file-system description object
555 * @pnode: pnode
556 *
557 * This function returns the next pnode to dirty or %NULL if there are no more
558 * pnodes. Note that pnodes that have never been written (lnum == 0) are
559 * skipped.
560 */
next_pnode_to_dirty(struct ubifs_info * c,struct ubifs_pnode * pnode)561 static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,
562 struct ubifs_pnode *pnode)
563 {
564 struct ubifs_nnode *nnode;
565 int iip;
566
567 /* Try to go right */
568 nnode = pnode->parent;
569 for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
570 if (nnode->nbranch[iip].lnum)
571 return ubifs_get_pnode(c, nnode, iip);
572 }
573
574 /* Go up while can't go right */
575 do {
576 iip = nnode->iip + 1;
577 nnode = nnode->parent;
578 if (!nnode)
579 return NULL;
580 for (; iip < UBIFS_LPT_FANOUT; iip++) {
581 if (nnode->nbranch[iip].lnum)
582 break;
583 }
584 } while (iip >= UBIFS_LPT_FANOUT);
585
586 /* Go right */
587 nnode = ubifs_get_nnode(c, nnode, iip);
588 if (IS_ERR(nnode))
589 return (void *)nnode;
590
591 /* Go down to level 1 */
592 while (nnode->level > 1) {
593 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {
594 if (nnode->nbranch[iip].lnum)
595 break;
596 }
597 if (iip >= UBIFS_LPT_FANOUT) {
598 /*
599 * Should not happen, but we need to keep going
600 * if it does.
601 */
602 iip = 0;
603 }
604 nnode = ubifs_get_nnode(c, nnode, iip);
605 if (IS_ERR(nnode))
606 return (void *)nnode;
607 }
608
609 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)
610 if (nnode->nbranch[iip].lnum)
611 break;
612 if (iip >= UBIFS_LPT_FANOUT)
613 /* Should not happen, but we need to keep going if it does */
614 iip = 0;
615 return ubifs_get_pnode(c, nnode, iip);
616 }
617
618 /**
619 * pnode_lookup - lookup a pnode in the LPT.
620 * @c: UBIFS file-system description object
621 * @i: pnode number (0 to main_lebs - 1)
622 *
623 * This function returns a pointer to the pnode on success or a negative
624 * error code on failure.
625 */
pnode_lookup(struct ubifs_info * c,int i)626 static struct ubifs_pnode *pnode_lookup(struct ubifs_info *c, int i)
627 {
628 int err, h, iip, shft;
629 struct ubifs_nnode *nnode;
630
631 if (!c->nroot) {
632 err = ubifs_read_nnode(c, NULL, 0);
633 if (err)
634 return ERR_PTR(err);
635 }
636 i <<= UBIFS_LPT_FANOUT_SHIFT;
637 nnode = c->nroot;
638 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
639 for (h = 1; h < c->lpt_hght; h++) {
640 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
641 shft -= UBIFS_LPT_FANOUT_SHIFT;
642 nnode = ubifs_get_nnode(c, nnode, iip);
643 if (IS_ERR(nnode))
644 return ERR_CAST(nnode);
645 }
646 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
647 return ubifs_get_pnode(c, nnode, iip);
648 }
649
650 /**
651 * add_pnode_dirt - add dirty space to LPT LEB properties.
652 * @c: UBIFS file-system description object
653 * @pnode: pnode for which to add dirt
654 */
add_pnode_dirt(struct ubifs_info * c,struct ubifs_pnode * pnode)655 static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
656 {
657 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
658 c->pnode_sz);
659 }
660
661 /**
662 * do_make_pnode_dirty - mark a pnode dirty.
663 * @c: UBIFS file-system description object
664 * @pnode: pnode to mark dirty
665 */
do_make_pnode_dirty(struct ubifs_info * c,struct ubifs_pnode * pnode)666 static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
667 {
668 /* Assumes cnext list is empty i.e. not called during commit */
669 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
670 struct ubifs_nnode *nnode;
671
672 c->dirty_pn_cnt += 1;
673 add_pnode_dirt(c, pnode);
674 /* Mark parent and ancestors dirty too */
675 nnode = pnode->parent;
676 while (nnode) {
677 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
678 c->dirty_nn_cnt += 1;
679 ubifs_add_nnode_dirt(c, nnode);
680 nnode = nnode->parent;
681 } else
682 break;
683 }
684 }
685 }
686
687 /**
688 * make_tree_dirty - mark the entire LEB properties tree dirty.
689 * @c: UBIFS file-system description object
690 *
691 * This function is used by the "small" LPT model to cause the entire LEB
692 * properties tree to be written. The "small" LPT model does not use LPT
693 * garbage collection because it is more efficient to write the entire tree
694 * (because it is small).
695 *
696 * This function returns %0 on success and a negative error code on failure.
697 */
make_tree_dirty(struct ubifs_info * c)698 static int make_tree_dirty(struct ubifs_info *c)
699 {
700 struct ubifs_pnode *pnode;
701
702 pnode = pnode_lookup(c, 0);
703 if (IS_ERR(pnode))
704 return PTR_ERR(pnode);
705
706 while (pnode) {
707 do_make_pnode_dirty(c, pnode);
708 pnode = next_pnode_to_dirty(c, pnode);
709 if (IS_ERR(pnode))
710 return PTR_ERR(pnode);
711 }
712 return 0;
713 }
714
715 /**
716 * need_write_all - determine if the LPT area is running out of free space.
717 * @c: UBIFS file-system description object
718 *
719 * This function returns %1 if the LPT area is running out of free space and %0
720 * if it is not.
721 */
need_write_all(struct ubifs_info * c)722 static int need_write_all(struct ubifs_info *c)
723 {
724 long long free = 0;
725 int i;
726
727 for (i = 0; i < c->lpt_lebs; i++) {
728 if (i + c->lpt_first == c->nhead_lnum)
729 free += c->leb_size - c->nhead_offs;
730 else if (c->ltab[i].free == c->leb_size)
731 free += c->leb_size;
732 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
733 free += c->leb_size;
734 }
735 /* Less than twice the size left */
736 if (free <= c->lpt_sz * 2)
737 return 1;
738 return 0;
739 }
740
741 /**
742 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
743 * @c: UBIFS file-system description object
744 *
745 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
746 * free space and so may be reused as soon as the next commit is completed.
747 * This function is called during start commit to mark LPT LEBs for trivial GC.
748 */
lpt_tgc_start(struct ubifs_info * c)749 static void lpt_tgc_start(struct ubifs_info *c)
750 {
751 int i;
752
753 for (i = 0; i < c->lpt_lebs; i++) {
754 if (i + c->lpt_first == c->nhead_lnum)
755 continue;
756 if (c->ltab[i].dirty > 0 &&
757 c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
758 c->ltab[i].tgc = 1;
759 c->ltab[i].free = c->leb_size;
760 c->ltab[i].dirty = 0;
761 dbg_lp("LEB %d", i + c->lpt_first);
762 }
763 }
764 }
765
766 /**
767 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
768 * @c: UBIFS file-system description object
769 *
770 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
771 * free space and so may be reused as soon as the next commit is completed.
772 * This function is called after the commit is completed (master node has been
773 * written) and un-maps LPT LEBs that were marked for trivial GC.
774 */
lpt_tgc_end(struct ubifs_info * c)775 static int lpt_tgc_end(struct ubifs_info *c)
776 {
777 int i, err;
778
779 for (i = 0; i < c->lpt_lebs; i++)
780 if (c->ltab[i].tgc) {
781 err = ubifs_leb_unmap(c, i + c->lpt_first);
782 if (err)
783 return err;
784 c->ltab[i].tgc = 0;
785 dbg_lp("LEB %d", i + c->lpt_first);
786 }
787 return 0;
788 }
789
790 /**
791 * populate_lsave - fill the lsave array with important LEB numbers.
792 * @c: the UBIFS file-system description object
793 *
794 * This function is only called for the "big" model. It records a small number
795 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
796 * most important to least important): empty, freeable, freeable index, dirty
797 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
798 * their pnodes into memory. That will stop us from having to scan the LPT
799 * straight away. For the "small" model we assume that scanning the LPT is no
800 * big deal.
801 */
populate_lsave(struct ubifs_info * c)802 static void populate_lsave(struct ubifs_info *c)
803 {
804 struct ubifs_lprops *lprops;
805 struct ubifs_lpt_heap *heap;
806 int i, cnt = 0;
807
808 ubifs_assert(c->big_lpt);
809 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
810 c->lpt_drty_flgs |= LSAVE_DIRTY;
811 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
812 }
813
814 #ifndef __UBOOT__
815 if (dbg_populate_lsave(c))
816 return;
817 #endif
818
819 list_for_each_entry(lprops, &c->empty_list, list) {
820 c->lsave[cnt++] = lprops->lnum;
821 if (cnt >= c->lsave_cnt)
822 return;
823 }
824 list_for_each_entry(lprops, &c->freeable_list, list) {
825 c->lsave[cnt++] = lprops->lnum;
826 if (cnt >= c->lsave_cnt)
827 return;
828 }
829 list_for_each_entry(lprops, &c->frdi_idx_list, list) {
830 c->lsave[cnt++] = lprops->lnum;
831 if (cnt >= c->lsave_cnt)
832 return;
833 }
834 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
835 for (i = 0; i < heap->cnt; i++) {
836 c->lsave[cnt++] = heap->arr[i]->lnum;
837 if (cnt >= c->lsave_cnt)
838 return;
839 }
840 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
841 for (i = 0; i < heap->cnt; i++) {
842 c->lsave[cnt++] = heap->arr[i]->lnum;
843 if (cnt >= c->lsave_cnt)
844 return;
845 }
846 heap = &c->lpt_heap[LPROPS_FREE - 1];
847 for (i = 0; i < heap->cnt; i++) {
848 c->lsave[cnt++] = heap->arr[i]->lnum;
849 if (cnt >= c->lsave_cnt)
850 return;
851 }
852 /* Fill it up completely */
853 while (cnt < c->lsave_cnt)
854 c->lsave[cnt++] = c->main_first;
855 }
856
857 /**
858 * nnode_lookup - lookup a nnode in the LPT.
859 * @c: UBIFS file-system description object
860 * @i: nnode number
861 *
862 * This function returns a pointer to the nnode on success or a negative
863 * error code on failure.
864 */
nnode_lookup(struct ubifs_info * c,int i)865 static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
866 {
867 int err, iip;
868 struct ubifs_nnode *nnode;
869
870 if (!c->nroot) {
871 err = ubifs_read_nnode(c, NULL, 0);
872 if (err)
873 return ERR_PTR(err);
874 }
875 nnode = c->nroot;
876 while (1) {
877 iip = i & (UBIFS_LPT_FANOUT - 1);
878 i >>= UBIFS_LPT_FANOUT_SHIFT;
879 if (!i)
880 break;
881 nnode = ubifs_get_nnode(c, nnode, iip);
882 if (IS_ERR(nnode))
883 return nnode;
884 }
885 return nnode;
886 }
887
888 /**
889 * make_nnode_dirty - find a nnode and, if found, make it dirty.
890 * @c: UBIFS file-system description object
891 * @node_num: nnode number of nnode to make dirty
892 * @lnum: LEB number where nnode was written
893 * @offs: offset where nnode was written
894 *
895 * This function is used by LPT garbage collection. LPT garbage collection is
896 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
897 * simply involves marking all the nodes in the LEB being garbage-collected as
898 * dirty. The dirty nodes are written next commit, after which the LEB is free
899 * to be reused.
900 *
901 * This function returns %0 on success and a negative error code on failure.
902 */
make_nnode_dirty(struct ubifs_info * c,int node_num,int lnum,int offs)903 static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
904 int offs)
905 {
906 struct ubifs_nnode *nnode;
907
908 nnode = nnode_lookup(c, node_num);
909 if (IS_ERR(nnode))
910 return PTR_ERR(nnode);
911 if (nnode->parent) {
912 struct ubifs_nbranch *branch;
913
914 branch = &nnode->parent->nbranch[nnode->iip];
915 if (branch->lnum != lnum || branch->offs != offs)
916 return 0; /* nnode is obsolete */
917 } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
918 return 0; /* nnode is obsolete */
919 /* Assumes cnext list is empty i.e. not called during commit */
920 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
921 c->dirty_nn_cnt += 1;
922 ubifs_add_nnode_dirt(c, nnode);
923 /* Mark parent and ancestors dirty too */
924 nnode = nnode->parent;
925 while (nnode) {
926 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
927 c->dirty_nn_cnt += 1;
928 ubifs_add_nnode_dirt(c, nnode);
929 nnode = nnode->parent;
930 } else
931 break;
932 }
933 }
934 return 0;
935 }
936
937 /**
938 * make_pnode_dirty - find a pnode and, if found, make it dirty.
939 * @c: UBIFS file-system description object
940 * @node_num: pnode number of pnode to make dirty
941 * @lnum: LEB number where pnode was written
942 * @offs: offset where pnode was written
943 *
944 * This function is used by LPT garbage collection. LPT garbage collection is
945 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
946 * simply involves marking all the nodes in the LEB being garbage-collected as
947 * dirty. The dirty nodes are written next commit, after which the LEB is free
948 * to be reused.
949 *
950 * This function returns %0 on success and a negative error code on failure.
951 */
make_pnode_dirty(struct ubifs_info * c,int node_num,int lnum,int offs)952 static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
953 int offs)
954 {
955 struct ubifs_pnode *pnode;
956 struct ubifs_nbranch *branch;
957
958 pnode = pnode_lookup(c, node_num);
959 if (IS_ERR(pnode))
960 return PTR_ERR(pnode);
961 branch = &pnode->parent->nbranch[pnode->iip];
962 if (branch->lnum != lnum || branch->offs != offs)
963 return 0;
964 do_make_pnode_dirty(c, pnode);
965 return 0;
966 }
967
968 /**
969 * make_ltab_dirty - make ltab node dirty.
970 * @c: UBIFS file-system description object
971 * @lnum: LEB number where ltab was written
972 * @offs: offset where ltab was written
973 *
974 * This function is used by LPT garbage collection. LPT garbage collection is
975 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
976 * simply involves marking all the nodes in the LEB being garbage-collected as
977 * dirty. The dirty nodes are written next commit, after which the LEB is free
978 * to be reused.
979 *
980 * This function returns %0 on success and a negative error code on failure.
981 */
make_ltab_dirty(struct ubifs_info * c,int lnum,int offs)982 static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
983 {
984 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
985 return 0; /* This ltab node is obsolete */
986 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
987 c->lpt_drty_flgs |= LTAB_DIRTY;
988 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
989 }
990 return 0;
991 }
992
993 /**
994 * make_lsave_dirty - make lsave node dirty.
995 * @c: UBIFS file-system description object
996 * @lnum: LEB number where lsave was written
997 * @offs: offset where lsave was written
998 *
999 * This function is used by LPT garbage collection. LPT garbage collection is
1000 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1001 * simply involves marking all the nodes in the LEB being garbage-collected as
1002 * dirty. The dirty nodes are written next commit, after which the LEB is free
1003 * to be reused.
1004 *
1005 * This function returns %0 on success and a negative error code on failure.
1006 */
make_lsave_dirty(struct ubifs_info * c,int lnum,int offs)1007 static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1008 {
1009 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1010 return 0; /* This lsave node is obsolete */
1011 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
1012 c->lpt_drty_flgs |= LSAVE_DIRTY;
1013 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
1014 }
1015 return 0;
1016 }
1017
1018 /**
1019 * make_node_dirty - make node dirty.
1020 * @c: UBIFS file-system description object
1021 * @node_type: LPT node type
1022 * @node_num: node number
1023 * @lnum: LEB number where node was written
1024 * @offs: offset where node was written
1025 *
1026 * This function is used by LPT garbage collection. LPT garbage collection is
1027 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1028 * simply involves marking all the nodes in the LEB being garbage-collected as
1029 * dirty. The dirty nodes are written next commit, after which the LEB is free
1030 * to be reused.
1031 *
1032 * This function returns %0 on success and a negative error code on failure.
1033 */
make_node_dirty(struct ubifs_info * c,int node_type,int node_num,int lnum,int offs)1034 static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
1035 int lnum, int offs)
1036 {
1037 switch (node_type) {
1038 case UBIFS_LPT_NNODE:
1039 return make_nnode_dirty(c, node_num, lnum, offs);
1040 case UBIFS_LPT_PNODE:
1041 return make_pnode_dirty(c, node_num, lnum, offs);
1042 case UBIFS_LPT_LTAB:
1043 return make_ltab_dirty(c, lnum, offs);
1044 case UBIFS_LPT_LSAVE:
1045 return make_lsave_dirty(c, lnum, offs);
1046 }
1047 return -EINVAL;
1048 }
1049
1050 /**
1051 * get_lpt_node_len - return the length of a node based on its type.
1052 * @c: UBIFS file-system description object
1053 * @node_type: LPT node type
1054 */
get_lpt_node_len(const struct ubifs_info * c,int node_type)1055 static int get_lpt_node_len(const struct ubifs_info *c, int node_type)
1056 {
1057 switch (node_type) {
1058 case UBIFS_LPT_NNODE:
1059 return c->nnode_sz;
1060 case UBIFS_LPT_PNODE:
1061 return c->pnode_sz;
1062 case UBIFS_LPT_LTAB:
1063 return c->ltab_sz;
1064 case UBIFS_LPT_LSAVE:
1065 return c->lsave_sz;
1066 }
1067 return 0;
1068 }
1069
1070 /**
1071 * get_pad_len - return the length of padding in a buffer.
1072 * @c: UBIFS file-system description object
1073 * @buf: buffer
1074 * @len: length of buffer
1075 */
get_pad_len(const struct ubifs_info * c,uint8_t * buf,int len)1076 static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)
1077 {
1078 int offs, pad_len;
1079
1080 if (c->min_io_size == 1)
1081 return 0;
1082 offs = c->leb_size - len;
1083 pad_len = ALIGN(offs, c->min_io_size) - offs;
1084 return pad_len;
1085 }
1086
1087 /**
1088 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1089 * @c: UBIFS file-system description object
1090 * @buf: buffer
1091 * @node_num: node number is returned here
1092 */
get_lpt_node_type(const struct ubifs_info * c,uint8_t * buf,int * node_num)1093 static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,
1094 int *node_num)
1095 {
1096 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1097 int pos = 0, node_type;
1098
1099 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1100 *node_num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1101 return node_type;
1102 }
1103
1104 /**
1105 * is_a_node - determine if a buffer contains a node.
1106 * @c: UBIFS file-system description object
1107 * @buf: buffer
1108 * @len: length of buffer
1109 *
1110 * This function returns %1 if the buffer contains a node or %0 if it does not.
1111 */
is_a_node(const struct ubifs_info * c,uint8_t * buf,int len)1112 static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)
1113 {
1114 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1115 int pos = 0, node_type, node_len;
1116 uint16_t crc, calc_crc;
1117
1118 if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1119 return 0;
1120 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1121 if (node_type == UBIFS_LPT_NOT_A_NODE)
1122 return 0;
1123 node_len = get_lpt_node_len(c, node_type);
1124 if (!node_len || node_len > len)
1125 return 0;
1126 pos = 0;
1127 addr = buf;
1128 crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
1129 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1130 node_len - UBIFS_LPT_CRC_BYTES);
1131 if (crc != calc_crc)
1132 return 0;
1133 return 1;
1134 }
1135
1136 /**
1137 * lpt_gc_lnum - garbage collect a LPT LEB.
1138 * @c: UBIFS file-system description object
1139 * @lnum: LEB number to garbage collect
1140 *
1141 * LPT garbage collection is used only for the "big" LPT model
1142 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1143 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1144 * next commit, after which the LEB is free to be reused.
1145 *
1146 * This function returns %0 on success and a negative error code on failure.
1147 */
lpt_gc_lnum(struct ubifs_info * c,int lnum)1148 static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1149 {
1150 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1151 void *buf = c->lpt_buf;
1152
1153 dbg_lp("LEB %d", lnum);
1154
1155 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1156 if (err)
1157 return err;
1158
1159 while (1) {
1160 if (!is_a_node(c, buf, len)) {
1161 int pad_len;
1162
1163 pad_len = get_pad_len(c, buf, len);
1164 if (pad_len) {
1165 buf += pad_len;
1166 len -= pad_len;
1167 continue;
1168 }
1169 return 0;
1170 }
1171 node_type = get_lpt_node_type(c, buf, &node_num);
1172 node_len = get_lpt_node_len(c, node_type);
1173 offs = c->leb_size - len;
1174 ubifs_assert(node_len != 0);
1175 mutex_lock(&c->lp_mutex);
1176 err = make_node_dirty(c, node_type, node_num, lnum, offs);
1177 mutex_unlock(&c->lp_mutex);
1178 if (err)
1179 return err;
1180 buf += node_len;
1181 len -= node_len;
1182 }
1183 return 0;
1184 }
1185
1186 /**
1187 * lpt_gc - LPT garbage collection.
1188 * @c: UBIFS file-system description object
1189 *
1190 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1191 * Returns %0 on success and a negative error code on failure.
1192 */
lpt_gc(struct ubifs_info * c)1193 static int lpt_gc(struct ubifs_info *c)
1194 {
1195 int i, lnum = -1, dirty = 0;
1196
1197 mutex_lock(&c->lp_mutex);
1198 for (i = 0; i < c->lpt_lebs; i++) {
1199 ubifs_assert(!c->ltab[i].tgc);
1200 if (i + c->lpt_first == c->nhead_lnum ||
1201 c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1202 continue;
1203 if (c->ltab[i].dirty > dirty) {
1204 dirty = c->ltab[i].dirty;
1205 lnum = i + c->lpt_first;
1206 }
1207 }
1208 mutex_unlock(&c->lp_mutex);
1209 if (lnum == -1)
1210 return -ENOSPC;
1211 return lpt_gc_lnum(c, lnum);
1212 }
1213
1214 /**
1215 * ubifs_lpt_start_commit - UBIFS commit starts.
1216 * @c: the UBIFS file-system description object
1217 *
1218 * This function has to be called when UBIFS starts the commit operation.
1219 * This function "freezes" all currently dirty LEB properties and does not
1220 * change them anymore. Further changes are saved and tracked separately
1221 * because they are not part of this commit. This function returns zero in case
1222 * of success and a negative error code in case of failure.
1223 */
ubifs_lpt_start_commit(struct ubifs_info * c)1224 int ubifs_lpt_start_commit(struct ubifs_info *c)
1225 {
1226 int err, cnt;
1227
1228 dbg_lp("");
1229
1230 mutex_lock(&c->lp_mutex);
1231 err = dbg_chk_lpt_free_spc(c);
1232 if (err)
1233 goto out;
1234 err = dbg_check_ltab(c);
1235 if (err)
1236 goto out;
1237
1238 if (c->check_lpt_free) {
1239 /*
1240 * We ensure there is enough free space in
1241 * ubifs_lpt_post_commit() by marking nodes dirty. That
1242 * information is lost when we unmount, so we also need
1243 * to check free space once after mounting also.
1244 */
1245 c->check_lpt_free = 0;
1246 while (need_write_all(c)) {
1247 mutex_unlock(&c->lp_mutex);
1248 err = lpt_gc(c);
1249 if (err)
1250 return err;
1251 mutex_lock(&c->lp_mutex);
1252 }
1253 }
1254
1255 lpt_tgc_start(c);
1256
1257 if (!c->dirty_pn_cnt) {
1258 dbg_cmt("no cnodes to commit");
1259 err = 0;
1260 goto out;
1261 }
1262
1263 if (!c->big_lpt && need_write_all(c)) {
1264 /* If needed, write everything */
1265 err = make_tree_dirty(c);
1266 if (err)
1267 goto out;
1268 lpt_tgc_start(c);
1269 }
1270
1271 if (c->big_lpt)
1272 populate_lsave(c);
1273
1274 cnt = get_cnodes_to_commit(c);
1275 ubifs_assert(cnt != 0);
1276
1277 err = layout_cnodes(c);
1278 if (err)
1279 goto out;
1280
1281 /* Copy the LPT's own lprops for end commit to write */
1282 memcpy(c->ltab_cmt, c->ltab,
1283 sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1284 c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1285
1286 out:
1287 mutex_unlock(&c->lp_mutex);
1288 return err;
1289 }
1290
1291 /**
1292 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1293 * @c: UBIFS file-system description object
1294 */
free_obsolete_cnodes(struct ubifs_info * c)1295 static void free_obsolete_cnodes(struct ubifs_info *c)
1296 {
1297 struct ubifs_cnode *cnode, *cnext;
1298
1299 cnext = c->lpt_cnext;
1300 if (!cnext)
1301 return;
1302 do {
1303 cnode = cnext;
1304 cnext = cnode->cnext;
1305 if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1306 kfree(cnode);
1307 else
1308 cnode->cnext = NULL;
1309 } while (cnext != c->lpt_cnext);
1310 c->lpt_cnext = NULL;
1311 }
1312
1313 #ifndef __UBOOT__
1314 /**
1315 * ubifs_lpt_end_commit - finish the commit operation.
1316 * @c: the UBIFS file-system description object
1317 *
1318 * This function has to be called when the commit operation finishes. It
1319 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1320 * the media. Returns zero in case of success and a negative error code in case
1321 * of failure.
1322 */
ubifs_lpt_end_commit(struct ubifs_info * c)1323 int ubifs_lpt_end_commit(struct ubifs_info *c)
1324 {
1325 int err;
1326
1327 dbg_lp("");
1328
1329 if (!c->lpt_cnext)
1330 return 0;
1331
1332 err = write_cnodes(c);
1333 if (err)
1334 return err;
1335
1336 mutex_lock(&c->lp_mutex);
1337 free_obsolete_cnodes(c);
1338 mutex_unlock(&c->lp_mutex);
1339
1340 return 0;
1341 }
1342 #endif
1343
1344 /**
1345 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1346 * @c: UBIFS file-system description object
1347 *
1348 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1349 * commit for the "big" LPT model.
1350 */
ubifs_lpt_post_commit(struct ubifs_info * c)1351 int ubifs_lpt_post_commit(struct ubifs_info *c)
1352 {
1353 int err;
1354
1355 mutex_lock(&c->lp_mutex);
1356 err = lpt_tgc_end(c);
1357 if (err)
1358 goto out;
1359 if (c->big_lpt)
1360 while (need_write_all(c)) {
1361 mutex_unlock(&c->lp_mutex);
1362 err = lpt_gc(c);
1363 if (err)
1364 return err;
1365 mutex_lock(&c->lp_mutex);
1366 }
1367 out:
1368 mutex_unlock(&c->lp_mutex);
1369 return err;
1370 }
1371
1372 /**
1373 * first_nnode - find the first nnode in memory.
1374 * @c: UBIFS file-system description object
1375 * @hght: height of tree where nnode found is returned here
1376 *
1377 * This function returns a pointer to the nnode found or %NULL if no nnode is
1378 * found. This function is a helper to 'ubifs_lpt_free()'.
1379 */
first_nnode(struct ubifs_info * c,int * hght)1380 static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1381 {
1382 struct ubifs_nnode *nnode;
1383 int h, i, found;
1384
1385 nnode = c->nroot;
1386 *hght = 0;
1387 if (!nnode)
1388 return NULL;
1389 for (h = 1; h < c->lpt_hght; h++) {
1390 found = 0;
1391 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1392 if (nnode->nbranch[i].nnode) {
1393 found = 1;
1394 nnode = nnode->nbranch[i].nnode;
1395 *hght = h;
1396 break;
1397 }
1398 }
1399 if (!found)
1400 break;
1401 }
1402 return nnode;
1403 }
1404
1405 /**
1406 * next_nnode - find the next nnode in memory.
1407 * @c: UBIFS file-system description object
1408 * @nnode: nnode from which to start.
1409 * @hght: height of tree where nnode is, is passed and returned here
1410 *
1411 * This function returns a pointer to the nnode found or %NULL if no nnode is
1412 * found. This function is a helper to 'ubifs_lpt_free()'.
1413 */
next_nnode(struct ubifs_info * c,struct ubifs_nnode * nnode,int * hght)1414 static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1415 struct ubifs_nnode *nnode, int *hght)
1416 {
1417 struct ubifs_nnode *parent;
1418 int iip, h, i, found;
1419
1420 parent = nnode->parent;
1421 if (!parent)
1422 return NULL;
1423 if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1424 *hght -= 1;
1425 return parent;
1426 }
1427 for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1428 nnode = parent->nbranch[iip].nnode;
1429 if (nnode)
1430 break;
1431 }
1432 if (!nnode) {
1433 *hght -= 1;
1434 return parent;
1435 }
1436 for (h = *hght + 1; h < c->lpt_hght; h++) {
1437 found = 0;
1438 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1439 if (nnode->nbranch[i].nnode) {
1440 found = 1;
1441 nnode = nnode->nbranch[i].nnode;
1442 *hght = h;
1443 break;
1444 }
1445 }
1446 if (!found)
1447 break;
1448 }
1449 return nnode;
1450 }
1451
1452 /**
1453 * ubifs_lpt_free - free resources owned by the LPT.
1454 * @c: UBIFS file-system description object
1455 * @wr_only: free only resources used for writing
1456 */
ubifs_lpt_free(struct ubifs_info * c,int wr_only)1457 void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1458 {
1459 struct ubifs_nnode *nnode;
1460 int i, hght;
1461
1462 /* Free write-only things first */
1463
1464 free_obsolete_cnodes(c); /* Leftover from a failed commit */
1465
1466 vfree(c->ltab_cmt);
1467 c->ltab_cmt = NULL;
1468 vfree(c->lpt_buf);
1469 c->lpt_buf = NULL;
1470 kfree(c->lsave);
1471 c->lsave = NULL;
1472
1473 if (wr_only)
1474 return;
1475
1476 /* Now free the rest */
1477
1478 nnode = first_nnode(c, &hght);
1479 while (nnode) {
1480 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1481 kfree(nnode->nbranch[i].nnode);
1482 nnode = next_nnode(c, nnode, &hght);
1483 }
1484 for (i = 0; i < LPROPS_HEAP_CNT; i++)
1485 kfree(c->lpt_heap[i].arr);
1486 kfree(c->dirty_idx.arr);
1487 kfree(c->nroot);
1488 vfree(c->ltab);
1489 kfree(c->lpt_nod_buf);
1490 }
1491
1492 #ifndef __UBOOT__
1493 /*
1494 * Everything below is related to debugging.
1495 */
1496
1497 /**
1498 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
1499 * @buf: buffer
1500 * @len: buffer length
1501 */
dbg_is_all_ff(uint8_t * buf,int len)1502 static int dbg_is_all_ff(uint8_t *buf, int len)
1503 {
1504 int i;
1505
1506 for (i = 0; i < len; i++)
1507 if (buf[i] != 0xff)
1508 return 0;
1509 return 1;
1510 }
1511
1512 /**
1513 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1514 * @c: the UBIFS file-system description object
1515 * @lnum: LEB number where nnode was written
1516 * @offs: offset where nnode was written
1517 */
dbg_is_nnode_dirty(struct ubifs_info * c,int lnum,int offs)1518 static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1519 {
1520 struct ubifs_nnode *nnode;
1521 int hght;
1522
1523 /* Entire tree is in memory so first_nnode / next_nnode are OK */
1524 nnode = first_nnode(c, &hght);
1525 for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1526 struct ubifs_nbranch *branch;
1527
1528 cond_resched();
1529 if (nnode->parent) {
1530 branch = &nnode->parent->nbranch[nnode->iip];
1531 if (branch->lnum != lnum || branch->offs != offs)
1532 continue;
1533 if (test_bit(DIRTY_CNODE, &nnode->flags))
1534 return 1;
1535 return 0;
1536 } else {
1537 if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1538 continue;
1539 if (test_bit(DIRTY_CNODE, &nnode->flags))
1540 return 1;
1541 return 0;
1542 }
1543 }
1544 return 1;
1545 }
1546
1547 /**
1548 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1549 * @c: the UBIFS file-system description object
1550 * @lnum: LEB number where pnode was written
1551 * @offs: offset where pnode was written
1552 */
dbg_is_pnode_dirty(struct ubifs_info * c,int lnum,int offs)1553 static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1554 {
1555 int i, cnt;
1556
1557 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1558 for (i = 0; i < cnt; i++) {
1559 struct ubifs_pnode *pnode;
1560 struct ubifs_nbranch *branch;
1561
1562 cond_resched();
1563 pnode = pnode_lookup(c, i);
1564 if (IS_ERR(pnode))
1565 return PTR_ERR(pnode);
1566 branch = &pnode->parent->nbranch[pnode->iip];
1567 if (branch->lnum != lnum || branch->offs != offs)
1568 continue;
1569 if (test_bit(DIRTY_CNODE, &pnode->flags))
1570 return 1;
1571 return 0;
1572 }
1573 return 1;
1574 }
1575
1576 /**
1577 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1578 * @c: the UBIFS file-system description object
1579 * @lnum: LEB number where ltab node was written
1580 * @offs: offset where ltab node was written
1581 */
dbg_is_ltab_dirty(struct ubifs_info * c,int lnum,int offs)1582 static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1583 {
1584 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1585 return 1;
1586 return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1587 }
1588
1589 /**
1590 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1591 * @c: the UBIFS file-system description object
1592 * @lnum: LEB number where lsave node was written
1593 * @offs: offset where lsave node was written
1594 */
dbg_is_lsave_dirty(struct ubifs_info * c,int lnum,int offs)1595 static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1596 {
1597 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1598 return 1;
1599 return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1600 }
1601
1602 /**
1603 * dbg_is_node_dirty - determine if a node is dirty.
1604 * @c: the UBIFS file-system description object
1605 * @node_type: node type
1606 * @lnum: LEB number where node was written
1607 * @offs: offset where node was written
1608 */
dbg_is_node_dirty(struct ubifs_info * c,int node_type,int lnum,int offs)1609 static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1610 int offs)
1611 {
1612 switch (node_type) {
1613 case UBIFS_LPT_NNODE:
1614 return dbg_is_nnode_dirty(c, lnum, offs);
1615 case UBIFS_LPT_PNODE:
1616 return dbg_is_pnode_dirty(c, lnum, offs);
1617 case UBIFS_LPT_LTAB:
1618 return dbg_is_ltab_dirty(c, lnum, offs);
1619 case UBIFS_LPT_LSAVE:
1620 return dbg_is_lsave_dirty(c, lnum, offs);
1621 }
1622 return 1;
1623 }
1624
1625 /**
1626 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1627 * @c: the UBIFS file-system description object
1628 * @lnum: LEB number where node was written
1629 * @offs: offset where node was written
1630 *
1631 * This function returns %0 on success and a negative error code on failure.
1632 */
dbg_check_ltab_lnum(struct ubifs_info * c,int lnum)1633 static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1634 {
1635 int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1636 int ret;
1637 void *buf, *p;
1638
1639 if (!dbg_is_chk_lprops(c))
1640 return 0;
1641
1642 buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
1643 if (!buf) {
1644 ubifs_err(c, "cannot allocate memory for ltab checking");
1645 return 0;
1646 }
1647
1648 dbg_lp("LEB %d", lnum);
1649
1650 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1651 if (err)
1652 goto out;
1653
1654 while (1) {
1655 if (!is_a_node(c, p, len)) {
1656 int i, pad_len;
1657
1658 pad_len = get_pad_len(c, p, len);
1659 if (pad_len) {
1660 p += pad_len;
1661 len -= pad_len;
1662 dirty += pad_len;
1663 continue;
1664 }
1665 if (!dbg_is_all_ff(p, len)) {
1666 ubifs_err(c, "invalid empty space in LEB %d at %d",
1667 lnum, c->leb_size - len);
1668 err = -EINVAL;
1669 }
1670 i = lnum - c->lpt_first;
1671 if (len != c->ltab[i].free) {
1672 ubifs_err(c, "invalid free space in LEB %d (free %d, expected %d)",
1673 lnum, len, c->ltab[i].free);
1674 err = -EINVAL;
1675 }
1676 if (dirty != c->ltab[i].dirty) {
1677 ubifs_err(c, "invalid dirty space in LEB %d (dirty %d, expected %d)",
1678 lnum, dirty, c->ltab[i].dirty);
1679 err = -EINVAL;
1680 }
1681 goto out;
1682 }
1683 node_type = get_lpt_node_type(c, p, &node_num);
1684 node_len = get_lpt_node_len(c, node_type);
1685 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1686 if (ret == 1)
1687 dirty += node_len;
1688 p += node_len;
1689 len -= node_len;
1690 }
1691
1692 err = 0;
1693 out:
1694 vfree(buf);
1695 return err;
1696 }
1697
1698 /**
1699 * dbg_check_ltab - check the free and dirty space in the ltab.
1700 * @c: the UBIFS file-system description object
1701 *
1702 * This function returns %0 on success and a negative error code on failure.
1703 */
dbg_check_ltab(struct ubifs_info * c)1704 int dbg_check_ltab(struct ubifs_info *c)
1705 {
1706 int lnum, err, i, cnt;
1707
1708 if (!dbg_is_chk_lprops(c))
1709 return 0;
1710
1711 /* Bring the entire tree into memory */
1712 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1713 for (i = 0; i < cnt; i++) {
1714 struct ubifs_pnode *pnode;
1715
1716 pnode = pnode_lookup(c, i);
1717 if (IS_ERR(pnode))
1718 return PTR_ERR(pnode);
1719 cond_resched();
1720 }
1721
1722 /* Check nodes */
1723 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1724 if (err)
1725 return err;
1726
1727 /* Check each LEB */
1728 for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1729 err = dbg_check_ltab_lnum(c, lnum);
1730 if (err) {
1731 ubifs_err(c, "failed at LEB %d", lnum);
1732 return err;
1733 }
1734 }
1735
1736 dbg_lp("succeeded");
1737 return 0;
1738 }
1739
1740 /**
1741 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1742 * @c: the UBIFS file-system description object
1743 *
1744 * This function returns %0 on success and a negative error code on failure.
1745 */
dbg_chk_lpt_free_spc(struct ubifs_info * c)1746 int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1747 {
1748 long long free = 0;
1749 int i;
1750
1751 if (!dbg_is_chk_lprops(c))
1752 return 0;
1753
1754 for (i = 0; i < c->lpt_lebs; i++) {
1755 if (c->ltab[i].tgc || c->ltab[i].cmt)
1756 continue;
1757 if (i + c->lpt_first == c->nhead_lnum)
1758 free += c->leb_size - c->nhead_offs;
1759 else if (c->ltab[i].free == c->leb_size)
1760 free += c->leb_size;
1761 }
1762 if (free < c->lpt_sz) {
1763 ubifs_err(c, "LPT space error: free %lld lpt_sz %lld",
1764 free, c->lpt_sz);
1765 ubifs_dump_lpt_info(c);
1766 ubifs_dump_lpt_lebs(c);
1767 dump_stack();
1768 return -EINVAL;
1769 }
1770 return 0;
1771 }
1772
1773 /**
1774 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1775 * @c: the UBIFS file-system description object
1776 * @action: what to do
1777 * @len: length written
1778 *
1779 * This function returns %0 on success and a negative error code on failure.
1780 * The @action argument may be one of:
1781 * o %0 - LPT debugging checking starts, initialize debugging variables;
1782 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1783 * o %2 - switched to a different LEB and wasted @len bytes;
1784 * o %3 - check that we've written the right number of bytes.
1785 * o %4 - wasted @len bytes;
1786 */
dbg_chk_lpt_sz(struct ubifs_info * c,int action,int len)1787 int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1788 {
1789 struct ubifs_debug_info *d = c->dbg;
1790 long long chk_lpt_sz, lpt_sz;
1791 int err = 0;
1792
1793 if (!dbg_is_chk_lprops(c))
1794 return 0;
1795
1796 switch (action) {
1797 case 0:
1798 d->chk_lpt_sz = 0;
1799 d->chk_lpt_sz2 = 0;
1800 d->chk_lpt_lebs = 0;
1801 d->chk_lpt_wastage = 0;
1802 if (c->dirty_pn_cnt > c->pnode_cnt) {
1803 ubifs_err(c, "dirty pnodes %d exceed max %d",
1804 c->dirty_pn_cnt, c->pnode_cnt);
1805 err = -EINVAL;
1806 }
1807 if (c->dirty_nn_cnt > c->nnode_cnt) {
1808 ubifs_err(c, "dirty nnodes %d exceed max %d",
1809 c->dirty_nn_cnt, c->nnode_cnt);
1810 err = -EINVAL;
1811 }
1812 return err;
1813 case 1:
1814 d->chk_lpt_sz += len;
1815 return 0;
1816 case 2:
1817 d->chk_lpt_sz += len;
1818 d->chk_lpt_wastage += len;
1819 d->chk_lpt_lebs += 1;
1820 return 0;
1821 case 3:
1822 chk_lpt_sz = c->leb_size;
1823 chk_lpt_sz *= d->chk_lpt_lebs;
1824 chk_lpt_sz += len - c->nhead_offs;
1825 if (d->chk_lpt_sz != chk_lpt_sz) {
1826 ubifs_err(c, "LPT wrote %lld but space used was %lld",
1827 d->chk_lpt_sz, chk_lpt_sz);
1828 err = -EINVAL;
1829 }
1830 if (d->chk_lpt_sz > c->lpt_sz) {
1831 ubifs_err(c, "LPT wrote %lld but lpt_sz is %lld",
1832 d->chk_lpt_sz, c->lpt_sz);
1833 err = -EINVAL;
1834 }
1835 if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
1836 ubifs_err(c, "LPT layout size %lld but wrote %lld",
1837 d->chk_lpt_sz, d->chk_lpt_sz2);
1838 err = -EINVAL;
1839 }
1840 if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
1841 ubifs_err(c, "LPT new nhead offs: expected %d was %d",
1842 d->new_nhead_offs, len);
1843 err = -EINVAL;
1844 }
1845 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1846 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1847 lpt_sz += c->ltab_sz;
1848 if (c->big_lpt)
1849 lpt_sz += c->lsave_sz;
1850 if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
1851 ubifs_err(c, "LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1852 d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
1853 err = -EINVAL;
1854 }
1855 if (err) {
1856 ubifs_dump_lpt_info(c);
1857 ubifs_dump_lpt_lebs(c);
1858 dump_stack();
1859 }
1860 d->chk_lpt_sz2 = d->chk_lpt_sz;
1861 d->chk_lpt_sz = 0;
1862 d->chk_lpt_wastage = 0;
1863 d->chk_lpt_lebs = 0;
1864 d->new_nhead_offs = len;
1865 return err;
1866 case 4:
1867 d->chk_lpt_sz += len;
1868 d->chk_lpt_wastage += len;
1869 return 0;
1870 default:
1871 return -EINVAL;
1872 }
1873 }
1874
1875 /**
1876 * ubifs_dump_lpt_leb - dump an LPT LEB.
1877 * @c: UBIFS file-system description object
1878 * @lnum: LEB number to dump
1879 *
1880 * This function dumps an LEB from LPT area. Nodes in this area are very
1881 * different to nodes in the main area (e.g., they do not have common headers,
1882 * they do not have 8-byte alignments, etc), so we have a separate function to
1883 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1884 */
dump_lpt_leb(const struct ubifs_info * c,int lnum)1885 static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1886 {
1887 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1888 void *buf, *p;
1889
1890 pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
1891 buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
1892 if (!buf) {
1893 ubifs_err(c, "cannot allocate memory to dump LPT");
1894 return;
1895 }
1896
1897 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1898 if (err)
1899 goto out;
1900
1901 while (1) {
1902 offs = c->leb_size - len;
1903 if (!is_a_node(c, p, len)) {
1904 int pad_len;
1905
1906 pad_len = get_pad_len(c, p, len);
1907 if (pad_len) {
1908 pr_err("LEB %d:%d, pad %d bytes\n",
1909 lnum, offs, pad_len);
1910 p += pad_len;
1911 len -= pad_len;
1912 continue;
1913 }
1914 if (len)
1915 pr_err("LEB %d:%d, free %d bytes\n",
1916 lnum, offs, len);
1917 break;
1918 }
1919
1920 node_type = get_lpt_node_type(c, p, &node_num);
1921 switch (node_type) {
1922 case UBIFS_LPT_PNODE:
1923 {
1924 node_len = c->pnode_sz;
1925 if (c->big_lpt)
1926 pr_err("LEB %d:%d, pnode num %d\n",
1927 lnum, offs, node_num);
1928 else
1929 pr_err("LEB %d:%d, pnode\n", lnum, offs);
1930 break;
1931 }
1932 case UBIFS_LPT_NNODE:
1933 {
1934 int i;
1935 struct ubifs_nnode nnode;
1936
1937 node_len = c->nnode_sz;
1938 if (c->big_lpt)
1939 pr_err("LEB %d:%d, nnode num %d, ",
1940 lnum, offs, node_num);
1941 else
1942 pr_err("LEB %d:%d, nnode, ",
1943 lnum, offs);
1944 err = ubifs_unpack_nnode(c, p, &nnode);
1945 if (err) {
1946 pr_err("failed to unpack_node, error %d\n",
1947 err);
1948 break;
1949 }
1950 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1951 pr_cont("%d:%d", nnode.nbranch[i].lnum,
1952 nnode.nbranch[i].offs);
1953 if (i != UBIFS_LPT_FANOUT - 1)
1954 pr_cont(", ");
1955 }
1956 pr_cont("\n");
1957 break;
1958 }
1959 case UBIFS_LPT_LTAB:
1960 node_len = c->ltab_sz;
1961 pr_err("LEB %d:%d, ltab\n", lnum, offs);
1962 break;
1963 case UBIFS_LPT_LSAVE:
1964 node_len = c->lsave_sz;
1965 pr_err("LEB %d:%d, lsave len\n", lnum, offs);
1966 break;
1967 default:
1968 ubifs_err(c, "LPT node type %d not recognized", node_type);
1969 goto out;
1970 }
1971
1972 p += node_len;
1973 len -= node_len;
1974 }
1975
1976 pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
1977 out:
1978 vfree(buf);
1979 return;
1980 }
1981
1982 /**
1983 * ubifs_dump_lpt_lebs - dump LPT lebs.
1984 * @c: UBIFS file-system description object
1985 *
1986 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1987 * locked.
1988 */
ubifs_dump_lpt_lebs(const struct ubifs_info * c)1989 void ubifs_dump_lpt_lebs(const struct ubifs_info *c)
1990 {
1991 int i;
1992
1993 pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);
1994 for (i = 0; i < c->lpt_lebs; i++)
1995 dump_lpt_leb(c, i + c->lpt_first);
1996 pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);
1997 }
1998
1999 /**
2000 * dbg_populate_lsave - debugging version of 'populate_lsave()'
2001 * @c: UBIFS file-system description object
2002 *
2003 * This is a debugging version for 'populate_lsave()' which populates lsave
2004 * with random LEBs instead of useful LEBs, which is good for test coverage.
2005 * Returns zero if lsave has not been populated (this debugging feature is
2006 * disabled) an non-zero if lsave has been populated.
2007 */
dbg_populate_lsave(struct ubifs_info * c)2008 static int dbg_populate_lsave(struct ubifs_info *c)
2009 {
2010 struct ubifs_lprops *lprops;
2011 struct ubifs_lpt_heap *heap;
2012 int i;
2013
2014 if (!dbg_is_chk_gen(c))
2015 return 0;
2016 if (prandom_u32() & 3)
2017 return 0;
2018
2019 for (i = 0; i < c->lsave_cnt; i++)
2020 c->lsave[i] = c->main_first;
2021
2022 list_for_each_entry(lprops, &c->empty_list, list)
2023 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
2024 list_for_each_entry(lprops, &c->freeable_list, list)
2025 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
2026 list_for_each_entry(lprops, &c->frdi_idx_list, list)
2027 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
2028
2029 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
2030 for (i = 0; i < heap->cnt; i++)
2031 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
2032 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
2033 for (i = 0; i < heap->cnt; i++)
2034 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
2035 heap = &c->lpt_heap[LPROPS_FREE - 1];
2036 for (i = 0; i < heap->cnt; i++)
2037 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
2038
2039 return 1;
2040 }
2041 #endif
2042