projects/linux·blob master · refs

1995 lines · 50.6 KiB

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