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