~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/ubifs/lpt_commit.c

Version: ~ [ linux-5.16-rc3 ] ~ [ linux-5.15.5 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.82 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.162 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.218 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.256 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.291 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.293 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp