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