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