LCOV - code coverage report
Current view: top level - libubifs - lpt_commit.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 605 752 80.5 %
Date: 2024-06-05 20:10:43 Functions: 37 39 94.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13