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, nnode: (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, nnode: 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, action: 0, len: 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, action: 1, len: 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, action: 1, len: 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, free: c->leb_size - alen, dirty: alen - offs);
225 dbg_chk_lpt_sz(c, action: 2, len: c->leb_size - offs);
226 err = alloc_lpt_leb(c, lnum: &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, action: 1, len: 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, action: 1, len: 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, action: 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, free: c->leb_size - alen, dirty: alen - offs);
268 dbg_chk_lpt_sz(c, action: 2, len: c->leb_size - offs);
269 err = alloc_lpt_leb(c, lnum: &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, action: 1, len: 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, free: c->leb_size - alen, dirty: alen - offs);
288 dbg_chk_lpt_sz(c, action: 2, len: c->leb_size - offs);
289 err = alloc_lpt_leb(c, lnum: &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, action: 1, len: c->ltab_sz);
300 }
301
302 alen = ALIGN(offs, c->min_io_size);
303 upd_ltab(c, lnum, free: c->leb_size - alen, dirty: alen - offs);
304 dbg_chk_lpt_sz(c, action: 4, len: alen - offs);
305 err = dbg_chk_lpt_sz(c, action: 3, len: alen);
306 if (err)
307 return err;
308 return 0;
309
310no_space:
311 ubifs_err(c, fmt: "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: buf + offs, lsave: c->lsave);
384 offs += c->lsave_sz;
385 dbg_chk_lpt_sz(c, action: 1, len: c->lsave_sz);
386 }
387
388 if (offs + c->ltab_sz <= c->leb_size) {
389 done_ltab = 1;
390 ubifs_pack_ltab(c, buf: buf + offs, ltab: c->ltab_cmt);
391 offs += c->ltab_sz;
392 dbg_chk_lpt_sz(c, action: 1, len: 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: buf + from, offs: from,
407 len: alen);
408 if (err)
409 return err;
410 }
411 dbg_chk_lpt_sz(c, action: 2, len: c->leb_size - offs);
412 err = realloc_lpt_leb(c, lnum: &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: buf + offs, lsave: c->lsave);
425 offs += c->lsave_sz;
426 dbg_chk_lpt_sz(c, action: 1, len: c->lsave_sz);
427 continue;
428 }
429 if (!done_ltab) {
430 done_ltab = 1;
431 ubifs_pack_ltab(c, buf: buf + offs, ltab: c->ltab_cmt);
432 offs += c->ltab_sz;
433 dbg_chk_lpt_sz(c, action: 1, len: c->ltab_sz);
434 continue;
435 }
436 break;
437 }
438 if (cnode->level)
439 ubifs_pack_nnode(c, buf: buf + offs,
440 nnode: (struct ubifs_nnode *)cnode);
441 else
442 ubifs_pack_pnode(c, buf: buf + offs,
443 pnode: (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(nr: DIRTY_CNODE, addr: &cnode->flags);
451 smp_mb__before_atomic();
452 clear_bit(nr: COW_CNODE, addr: &cnode->flags);
453 smp_mb__after_atomic();
454 offs += len;
455 dbg_chk_lpt_sz(c, action: 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: buf + from, offs: from, len: alen);
466 if (err)
467 return err;
468 dbg_chk_lpt_sz(c, action: 2, len: c->leb_size - offs);
469 err = realloc_lpt_leb(c, lnum: &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: buf + offs, lsave: c->lsave);
481 offs += c->lsave_sz;
482 dbg_chk_lpt_sz(c, action: 1, len: 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: buf + from, offs: from, len: alen);
492 if (err)
493 return err;
494 dbg_chk_lpt_sz(c, action: 2, len: c->leb_size - offs);
495 err = realloc_lpt_leb(c, lnum: &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: buf + offs, ltab: c->ltab_cmt);
506 offs += c->ltab_sz;
507 dbg_chk_lpt_sz(c, action: 1, len: 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: buf + from, offs: from, len: alen);
515 if (err)
516 return err;
517
518 dbg_chk_lpt_sz(c, action: 4, len: alen - wlen);
519 err = dbg_chk_lpt_sz(c, action: 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, fmt: "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, parent: 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, parent: nnode, iip);
579 if (IS_ERR(ptr: nnode))
580 return (void *)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, parent: nnode, iip);
596 if (IS_ERR(ptr: nnode))
597 return (void *)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, parent: 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, lnum: pnode->parent->nbranch[pnode->iip].lnum,
617 dirty: 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(nr: DIRTY_CNODE, addr: &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(nr: DIRTY_CNODE, addr: &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, i: 0);
662 if (IS_ERR(ptr: pnode))
663 return PTR_ERR(ptr: pnode);
664
665 while (pnode) {
666 do_make_pnode_dirty(c, pnode);
667 pnode = next_pnode_to_dirty(c, pnode);
668 if (IS_ERR(ptr: pnode))
669 return PTR_ERR(ptr: 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, lnum: 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, lnum: c->lsave_lnum, dirty: 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, iip: 0);
829 if (err)
830 return ERR_PTR(error: 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, parent: nnode, iip);
839 if (IS_ERR(ptr: 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, i: node_num);
866 if (IS_ERR(ptr: nnode))
867 return PTR_ERR(ptr: 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(nr: DIRTY_CNODE, addr: &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(nr: DIRTY_CNODE, addr: &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, i: node_num);
916 if (IS_ERR(ptr: pnode))
917 return PTR_ERR(ptr: 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, lnum: c->ltab_lnum, dirty: 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, lnum: c->lsave_lnum, dirty: 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: &addr, pos: &pos, UBIFS_LPT_TYPE_BITS);
1057 *node_num = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: 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: &addr, pos: &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: &addr, pos: &pos, UBIFS_LPT_CRC_BITS);
1086 calc_crc = crc16(crc: -1, buffer: buf + UBIFS_LPT_CRC_BYTES,
1087 len: 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, offs: 0, len: c->leb_size, even_ebadmsg: 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: &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(lock: &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(lock: &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(lock: &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, hash: 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(lock: &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(objp: 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(lock: &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(lock: &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(lock: &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(addr: c->ltab_cmt);
1426 c->ltab_cmt = NULL;
1427 vfree(addr: c->lpt_buf);
1428 c->lpt_buf = NULL;
1429 kfree(objp: 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: &hght);
1438 while (nnode) {
1439 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1440 kfree(objp: nnode->nbranch[i].nnode);
1441 nnode = next_nnode(c, nnode, hght: &hght);
1442 }
1443 for (i = 0; i < LPROPS_HEAP_CNT; i++)
1444 kfree(objp: c->lpt_heap[i].arr);
1445 kfree(objp: c->dirty_idx.arr);
1446 kfree(objp: c->nroot);
1447 vfree(addr: c->ltab);
1448 kfree(objp: 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: &hght);
1483 for (; nnode; nnode = next_nnode(c, nnode, hght: &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(ptr: pnode))
1523 return PTR_ERR(ptr: 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(size: c->leb_size, GFP_NOFS);
1600 if (!buf) {
1601 ubifs_err(c, fmt: "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, offs: 0, len: c->leb_size, even_ebadmsg: 1);
1608 if (err)
1609 goto out;
1610
1611 while (1) {
1612 if (!is_a_node(c, buf: p, len)) {
1613 int i, pad_len;
1614
1615 pad_len = get_pad_len(c, buf: 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(buf: p, len)) {
1623 ubifs_err(c, fmt: "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, fmt: "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, fmt: "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, buf: p, node_num: &node_num);
1641 node_len = get_lpt_node_len(c, node_type);
1642 ret = dbg_is_node_dirty(c, node_type, lnum, offs: c->leb_size - len);
1643 if (ret == 1)
1644 dirty += node_len;
1645 p += node_len;
1646 len -= node_len;
1647 }
1648
1649 err = 0;
1650out:
1651 vfree(addr: buf);
1652 return err;
1653}
1654
1655/**
1656 * dbg_check_ltab - check the free and dirty space in the ltab.
1657 * @c: the UBIFS file-system description object
1658 *
1659 * This function returns %0 on success and a negative error code on failure.
1660 */
1661int dbg_check_ltab(struct ubifs_info *c)
1662{
1663 int lnum, err, i, cnt;
1664
1665 if (!dbg_is_chk_lprops(c))
1666 return 0;
1667
1668 /* Bring the entire tree into memory */
1669 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1670 for (i = 0; i < cnt; i++) {
1671 struct ubifs_pnode *pnode;
1672
1673 pnode = ubifs_pnode_lookup(c, i);
1674 if (IS_ERR(ptr: pnode))
1675 return PTR_ERR(ptr: pnode);
1676 cond_resched();
1677 }
1678
1679 /* Check nodes */
1680 err = dbg_check_lpt_nodes(c, cnode: (struct ubifs_cnode *)c->nroot, row: 0, col: 0);
1681 if (err)
1682 return err;
1683
1684 /* Check each LEB */
1685 for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1686 err = dbg_check_ltab_lnum(c, lnum);
1687 if (err) {
1688 ubifs_err(c, fmt: "failed at LEB %d", lnum);
1689 return err;
1690 }
1691 }
1692
1693 dbg_lp("succeeded");
1694 return 0;
1695}
1696
1697/**
1698 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1699 * @c: the UBIFS file-system description object
1700 *
1701 * This function returns %0 on success and a negative error code on failure.
1702 */
1703int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1704{
1705 long long free = 0;
1706 int i;
1707
1708 if (!dbg_is_chk_lprops(c))
1709 return 0;
1710
1711 for (i = 0; i < c->lpt_lebs; i++) {
1712 if (c->ltab[i].tgc || c->ltab[i].cmt)
1713 continue;
1714 if (i + c->lpt_first == c->nhead_lnum)
1715 free += c->leb_size - c->nhead_offs;
1716 else if (c->ltab[i].free == c->leb_size)
1717 free += c->leb_size;
1718 }
1719 if (free < c->lpt_sz) {
1720 ubifs_err(c, fmt: "LPT space error: free %lld lpt_sz %lld",
1721 free, c->lpt_sz);
1722 ubifs_dump_lpt_info(c);
1723 ubifs_dump_lpt_lebs(c);
1724 dump_stack();
1725 return -EINVAL;
1726 }
1727 return 0;
1728}
1729
1730/**
1731 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1732 * @c: the UBIFS file-system description object
1733 * @action: what to do
1734 * @len: length written
1735 *
1736 * This function returns %0 on success and a negative error code on failure.
1737 * The @action argument may be one of:
1738 * o %0 - LPT debugging checking starts, initialize debugging variables;
1739 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1740 * o %2 - switched to a different LEB and wasted @len bytes;
1741 * o %3 - check that we've written the right number of bytes.
1742 * o %4 - wasted @len bytes;
1743 */
1744int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1745{
1746 struct ubifs_debug_info *d = c->dbg;
1747 long long chk_lpt_sz, lpt_sz;
1748 int err = 0;
1749
1750 if (!dbg_is_chk_lprops(c))
1751 return 0;
1752
1753 switch (action) {
1754 case 0:
1755 d->chk_lpt_sz = 0;
1756 d->chk_lpt_sz2 = 0;
1757 d->chk_lpt_lebs = 0;
1758 d->chk_lpt_wastage = 0;
1759 if (c->dirty_pn_cnt > c->pnode_cnt) {
1760 ubifs_err(c, fmt: "dirty pnodes %d exceed max %d",
1761 c->dirty_pn_cnt, c->pnode_cnt);
1762 err = -EINVAL;
1763 }
1764 if (c->dirty_nn_cnt > c->nnode_cnt) {
1765 ubifs_err(c, fmt: "dirty nnodes %d exceed max %d",
1766 c->dirty_nn_cnt, c->nnode_cnt);
1767 err = -EINVAL;
1768 }
1769 return err;
1770 case 1:
1771 d->chk_lpt_sz += len;
1772 return 0;
1773 case 2:
1774 d->chk_lpt_sz += len;
1775 d->chk_lpt_wastage += len;
1776 d->chk_lpt_lebs += 1;
1777 return 0;
1778 case 3:
1779 chk_lpt_sz = c->leb_size;
1780 chk_lpt_sz *= d->chk_lpt_lebs;
1781 chk_lpt_sz += len - c->nhead_offs;
1782 if (d->chk_lpt_sz != chk_lpt_sz) {
1783 ubifs_err(c, fmt: "LPT wrote %lld but space used was %lld",
1784 d->chk_lpt_sz, chk_lpt_sz);
1785 err = -EINVAL;
1786 }
1787 if (d->chk_lpt_sz > c->lpt_sz) {
1788 ubifs_err(c, fmt: "LPT wrote %lld but lpt_sz is %lld",
1789 d->chk_lpt_sz, c->lpt_sz);
1790 err = -EINVAL;
1791 }
1792 if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
1793 ubifs_err(c, fmt: "LPT layout size %lld but wrote %lld",
1794 d->chk_lpt_sz, d->chk_lpt_sz2);
1795 err = -EINVAL;
1796 }
1797 if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
1798 ubifs_err(c, fmt: "LPT new nhead offs: expected %d was %d",
1799 d->new_nhead_offs, len);
1800 err = -EINVAL;
1801 }
1802 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1803 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1804 lpt_sz += c->ltab_sz;
1805 if (c->big_lpt)
1806 lpt_sz += c->lsave_sz;
1807 if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
1808 ubifs_err(c, fmt: "LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1809 d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
1810 err = -EINVAL;
1811 }
1812 if (err) {
1813 ubifs_dump_lpt_info(c);
1814 ubifs_dump_lpt_lebs(c);
1815 dump_stack();
1816 }
1817 d->chk_lpt_sz2 = d->chk_lpt_sz;
1818 d->chk_lpt_sz = 0;
1819 d->chk_lpt_wastage = 0;
1820 d->chk_lpt_lebs = 0;
1821 d->new_nhead_offs = len;
1822 return err;
1823 case 4:
1824 d->chk_lpt_sz += len;
1825 d->chk_lpt_wastage += len;
1826 return 0;
1827 default:
1828 return -EINVAL;
1829 }
1830}
1831
1832/**
1833 * dump_lpt_leb - dump an LPT LEB.
1834 * @c: UBIFS file-system description object
1835 * @lnum: LEB number to dump
1836 *
1837 * This function dumps an LEB from LPT area. Nodes in this area are very
1838 * different to nodes in the main area (e.g., they do not have common headers,
1839 * they do not have 8-byte alignments, etc), so we have a separate function to
1840 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1841 */
1842static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1843{
1844 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1845 void *buf, *p;
1846
1847 pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
1848 buf = p = __vmalloc(size: c->leb_size, GFP_NOFS);
1849 if (!buf) {
1850 ubifs_err(c, fmt: "cannot allocate memory to dump LPT");
1851 return;
1852 }
1853
1854 err = ubifs_leb_read(c, lnum, buf, offs: 0, len: c->leb_size, even_ebadmsg: 1);
1855 if (err)
1856 goto out;
1857
1858 while (1) {
1859 offs = c->leb_size - len;
1860 if (!is_a_node(c, buf: p, len)) {
1861 int pad_len;
1862
1863 pad_len = get_pad_len(c, buf: p, len);
1864 if (pad_len) {
1865 pr_err("LEB %d:%d, pad %d bytes\n",
1866 lnum, offs, pad_len);
1867 p += pad_len;
1868 len -= pad_len;
1869 continue;
1870 }
1871 if (len)
1872 pr_err("LEB %d:%d, free %d bytes\n",
1873 lnum, offs, len);
1874 break;
1875 }
1876
1877 node_type = get_lpt_node_type(c, buf: p, node_num: &node_num);
1878 switch (node_type) {
1879 case UBIFS_LPT_PNODE:
1880 {
1881 node_len = c->pnode_sz;
1882 if (c->big_lpt)
1883 pr_err("LEB %d:%d, pnode num %d\n",
1884 lnum, offs, node_num);
1885 else
1886 pr_err("LEB %d:%d, pnode\n", lnum, offs);
1887 break;
1888 }
1889 case UBIFS_LPT_NNODE:
1890 {
1891 int i;
1892 struct ubifs_nnode nnode;
1893
1894 node_len = c->nnode_sz;
1895 if (c->big_lpt)
1896 pr_err("LEB %d:%d, nnode num %d, ",
1897 lnum, offs, node_num);
1898 else
1899 pr_err("LEB %d:%d, nnode, ",
1900 lnum, offs);
1901 err = ubifs_unpack_nnode(c, buf: p, nnode: &nnode);
1902 if (err) {
1903 pr_err("failed to unpack_node, error %d\n",
1904 err);
1905 break;
1906 }
1907 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1908 pr_cont("%d:%d", nnode.nbranch[i].lnum,
1909 nnode.nbranch[i].offs);
1910 if (i != UBIFS_LPT_FANOUT - 1)
1911 pr_cont(", ");
1912 }
1913 pr_cont("\n");
1914 break;
1915 }
1916 case UBIFS_LPT_LTAB:
1917 node_len = c->ltab_sz;
1918 pr_err("LEB %d:%d, ltab\n", lnum, offs);
1919 break;
1920 case UBIFS_LPT_LSAVE:
1921 node_len = c->lsave_sz;
1922 pr_err("LEB %d:%d, lsave len\n", lnum, offs);
1923 break;
1924 default:
1925 ubifs_err(c, fmt: "LPT node type %d not recognized", node_type);
1926 goto out;
1927 }
1928
1929 p += node_len;
1930 len -= node_len;
1931 }
1932
1933 pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
1934out:
1935 vfree(addr: buf);
1936 return;
1937}
1938
1939/**
1940 * ubifs_dump_lpt_lebs - dump LPT lebs.
1941 * @c: UBIFS file-system description object
1942 *
1943 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1944 * locked.
1945 */
1946void ubifs_dump_lpt_lebs(const struct ubifs_info *c)
1947{
1948 int i;
1949
1950 pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);
1951 for (i = 0; i < c->lpt_lebs; i++)
1952 dump_lpt_leb(c, lnum: i + c->lpt_first);
1953 pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);
1954}
1955
1956/**
1957 * dbg_populate_lsave - debugging version of 'populate_lsave()'
1958 * @c: UBIFS file-system description object
1959 *
1960 * This is a debugging version for 'populate_lsave()' which populates lsave
1961 * with random LEBs instead of useful LEBs, which is good for test coverage.
1962 * Returns zero if lsave has not been populated (this debugging feature is
1963 * disabled) an non-zero if lsave has been populated.
1964 */
1965static int dbg_populate_lsave(struct ubifs_info *c)
1966{
1967 struct ubifs_lprops *lprops;
1968 struct ubifs_lpt_heap *heap;
1969 int i;
1970
1971 if (!dbg_is_chk_gen(c))
1972 return 0;
1973 if (get_random_u32_below(ceil: 4))
1974 return 0;
1975
1976 for (i = 0; i < c->lsave_cnt; i++)
1977 c->lsave[i] = c->main_first;
1978
1979 list_for_each_entry(lprops, &c->empty_list, list)
1980 c->lsave[get_random_u32_below(ceil: c->lsave_cnt)] = lprops->lnum;
1981 list_for_each_entry(lprops, &c->freeable_list, list)
1982 c->lsave[get_random_u32_below(ceil: c->lsave_cnt)] = lprops->lnum;
1983 list_for_each_entry(lprops, &c->frdi_idx_list, list)
1984 c->lsave[get_random_u32_below(ceil: c->lsave_cnt)] = lprops->lnum;
1985
1986 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
1987 for (i = 0; i < heap->cnt; i++)
1988 c->lsave[get_random_u32_below(ceil: c->lsave_cnt)] = heap->arr[i]->lnum;
1989 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
1990 for (i = 0; i < heap->cnt; i++)
1991 c->lsave[get_random_u32_below(ceil: c->lsave_cnt)] = heap->arr[i]->lnum;
1992 heap = &c->lpt_heap[LPROPS_FREE - 1];
1993 for (i = 0; i < heap->cnt; i++)
1994 c->lsave[get_random_u32_below(ceil: c->lsave_cnt)] = heap->arr[i]->lnum;
1995
1996 return 1;
1997}
1998

source code of linux/fs/ubifs/lpt_commit.c