blob: d9c02928e992dc9f00bdb7f2fd5ae75bdd32e4e6 [file] [log] [blame]
Artem Bityutskiy7d4e9cc2009-03-20 19:11:12 +02001/*
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002 * 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>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090029#include <linux/slab.h>
Artem Bityutskiy8d7819b2011-06-03 08:53:35 +030030#include <linux/random.h>
Artem Bityutskiy1e517642008-07-14 19:08:37 +030031#include "ubifs.h"
32
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +030033static int dbg_populate_lsave(struct ubifs_info *c);
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +030034
Artem Bityutskiy1e517642008-07-14 19:08:37 +030035/**
36 * first_dirty_cnode - find first dirty cnode.
37 * @c: UBIFS file-system description object
38 * @nnode: nnode at which to start
39 *
40 * This function returns the first dirty cnode or %NULL if there is not one.
41 */
42static struct ubifs_cnode *first_dirty_cnode(struct ubifs_nnode *nnode)
43{
44 ubifs_assert(nnode);
45 while (1) {
46 int i, cont = 0;
47
48 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
49 struct ubifs_cnode *cnode;
50
51 cnode = nnode->nbranch[i].cnode;
52 if (cnode &&
53 test_bit(DIRTY_CNODE, &cnode->flags)) {
54 if (cnode->level == 0)
55 return cnode;
56 nnode = (struct ubifs_nnode *)cnode;
57 cont = 1;
58 break;
59 }
60 }
61 if (!cont)
62 return (struct ubifs_cnode *)nnode;
63 }
64}
65
66/**
67 * next_dirty_cnode - find next dirty cnode.
68 * @cnode: cnode from which to begin searching
69 *
70 * This function returns the next dirty cnode or %NULL if there is not one.
71 */
72static struct ubifs_cnode *next_dirty_cnode(struct ubifs_cnode *cnode)
73{
74 struct ubifs_nnode *nnode;
75 int i;
76
77 ubifs_assert(cnode);
78 nnode = cnode->parent;
79 if (!nnode)
80 return NULL;
81 for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {
82 cnode = nnode->nbranch[i].cnode;
83 if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {
84 if (cnode->level == 0)
85 return cnode; /* cnode is a pnode */
86 /* cnode is a nnode */
87 return first_dirty_cnode((struct ubifs_nnode *)cnode);
88 }
89 }
90 return (struct ubifs_cnode *)nnode;
91}
92
93/**
94 * get_cnodes_to_commit - create list of dirty cnodes to commit.
95 * @c: UBIFS file-system description object
96 *
97 * This function returns the number of cnodes to commit.
98 */
99static int get_cnodes_to_commit(struct ubifs_info *c)
100{
101 struct ubifs_cnode *cnode, *cnext;
102 int cnt = 0;
103
104 if (!c->nroot)
105 return 0;
106
107 if (!test_bit(DIRTY_CNODE, &c->nroot->flags))
108 return 0;
109
110 c->lpt_cnext = first_dirty_cnode(c->nroot);
111 cnode = c->lpt_cnext;
112 if (!cnode)
113 return 0;
114 cnt += 1;
115 while (1) {
Artem Bityutskiy37662442011-05-30 14:51:20 +0300116 ubifs_assert(!test_bit(COW_CNODE, &cnode->flags));
117 __set_bit(COW_CNODE, &cnode->flags);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300118 cnext = next_dirty_cnode(cnode);
119 if (!cnext) {
120 cnode->cnext = c->lpt_cnext;
121 break;
122 }
123 cnode->cnext = cnext;
124 cnode = cnext;
125 cnt += 1;
126 }
127 dbg_cmt("committing %d cnodes", cnt);
128 dbg_lp("committing %d cnodes", cnt);
129 ubifs_assert(cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);
130 return cnt;
131}
132
133/**
134 * upd_ltab - update LPT LEB properties.
135 * @c: UBIFS file-system description object
136 * @lnum: LEB number
137 * @free: amount of free space
138 * @dirty: amount of dirty space to add
139 */
140static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
141{
142 dbg_lp("LEB %d free %d dirty %d to %d +%d",
143 lnum, c->ltab[lnum - c->lpt_first].free,
144 c->ltab[lnum - c->lpt_first].dirty, free, dirty);
145 ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
146 c->ltab[lnum - c->lpt_first].free = free;
147 c->ltab[lnum - c->lpt_first].dirty += dirty;
148}
149
150/**
151 * alloc_lpt_leb - allocate an LPT LEB that is empty.
152 * @c: UBIFS file-system description object
153 * @lnum: LEB number is passed and returned here
154 *
155 * This function finds the next empty LEB in the ltab starting from @lnum. If a
156 * an empty LEB is found it is returned in @lnum and the function returns %0.
157 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed
158 * never to run out of space.
159 */
160static int alloc_lpt_leb(struct ubifs_info *c, int *lnum)
161{
162 int i, n;
163
164 n = *lnum - c->lpt_first + 1;
165 for (i = n; i < c->lpt_lebs; i++) {
166 if (c->ltab[i].tgc || c->ltab[i].cmt)
167 continue;
168 if (c->ltab[i].free == c->leb_size) {
169 c->ltab[i].cmt = 1;
170 *lnum = i + c->lpt_first;
171 return 0;
172 }
173 }
174
175 for (i = 0; i < n; i++) {
176 if (c->ltab[i].tgc || c->ltab[i].cmt)
177 continue;
178 if (c->ltab[i].free == c->leb_size) {
179 c->ltab[i].cmt = 1;
180 *lnum = i + c->lpt_first;
181 return 0;
182 }
183 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300184 return -ENOSPC;
185}
186
187/**
188 * layout_cnodes - layout cnodes for commit.
189 * @c: UBIFS file-system description object
190 *
191 * This function returns %0 on success and a negative error code on failure.
192 */
193static int layout_cnodes(struct ubifs_info *c)
194{
195 int lnum, offs, len, alen, done_lsave, done_ltab, err;
196 struct ubifs_cnode *cnode;
197
Adrian Hunter73944a62008-09-12 18:13:31 +0300198 err = dbg_chk_lpt_sz(c, 0, 0);
199 if (err)
200 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300201 cnode = c->lpt_cnext;
202 if (!cnode)
203 return 0;
204 lnum = c->nhead_lnum;
205 offs = c->nhead_offs;
206 /* Try to place lsave and ltab nicely */
207 done_lsave = !c->big_lpt;
208 done_ltab = 0;
209 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
210 done_lsave = 1;
211 c->lsave_lnum = lnum;
212 c->lsave_offs = offs;
213 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300214 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300215 }
216
217 if (offs + c->ltab_sz <= c->leb_size) {
218 done_ltab = 1;
219 c->ltab_lnum = lnum;
220 c->ltab_offs = offs;
221 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300222 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300223 }
224
225 do {
226 if (cnode->level) {
227 len = c->nnode_sz;
228 c->dirty_nn_cnt -= 1;
229 } else {
230 len = c->pnode_sz;
231 c->dirty_pn_cnt -= 1;
232 }
233 while (offs + len > c->leb_size) {
234 alen = ALIGN(offs, c->min_io_size);
235 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200236 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300237 err = alloc_lpt_leb(c, &lnum);
238 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300239 goto no_space;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300240 offs = 0;
241 ubifs_assert(lnum >= c->lpt_first &&
242 lnum <= c->lpt_last);
243 /* Try to place lsave and ltab nicely */
244 if (!done_lsave) {
245 done_lsave = 1;
246 c->lsave_lnum = lnum;
247 c->lsave_offs = offs;
248 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300249 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300250 continue;
251 }
252 if (!done_ltab) {
253 done_ltab = 1;
254 c->ltab_lnum = lnum;
255 c->ltab_offs = offs;
256 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300257 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300258 continue;
259 }
260 break;
261 }
262 if (cnode->parent) {
263 cnode->parent->nbranch[cnode->iip].lnum = lnum;
264 cnode->parent->nbranch[cnode->iip].offs = offs;
265 } else {
266 c->lpt_lnum = lnum;
267 c->lpt_offs = offs;
268 }
269 offs += len;
Adrian Hunter73944a62008-09-12 18:13:31 +0300270 dbg_chk_lpt_sz(c, 1, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300271 cnode = cnode->cnext;
272 } while (cnode && cnode != c->lpt_cnext);
273
274 /* Make sure to place LPT's save table */
275 if (!done_lsave) {
276 if (offs + c->lsave_sz > c->leb_size) {
277 alen = ALIGN(offs, c->min_io_size);
278 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200279 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300280 err = alloc_lpt_leb(c, &lnum);
281 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300282 goto no_space;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300283 offs = 0;
284 ubifs_assert(lnum >= c->lpt_first &&
285 lnum <= c->lpt_last);
286 }
287 done_lsave = 1;
288 c->lsave_lnum = lnum;
289 c->lsave_offs = offs;
290 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300291 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300292 }
293
294 /* Make sure to place LPT's own lprops table */
295 if (!done_ltab) {
296 if (offs + c->ltab_sz > c->leb_size) {
297 alen = ALIGN(offs, c->min_io_size);
298 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200299 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300300 err = alloc_lpt_leb(c, &lnum);
301 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300302 goto no_space;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300303 offs = 0;
304 ubifs_assert(lnum >= c->lpt_first &&
305 lnum <= c->lpt_last);
306 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300307 c->ltab_lnum = lnum;
308 c->ltab_offs = offs;
309 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300310 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300311 }
312
313 alen = ALIGN(offs, c->min_io_size);
314 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter73944a62008-09-12 18:13:31 +0300315 dbg_chk_lpt_sz(c, 4, alen - offs);
316 err = dbg_chk_lpt_sz(c, 3, alen);
317 if (err)
318 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300319 return 0;
Adrian Hunter73944a62008-09-12 18:13:31 +0300320
321no_space:
Artem Bityutskiy79fda512012-08-27 13:34:09 +0300322 ubifs_err("LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
323 lnum, offs, len, done_ltab, done_lsave);
Artem Bityutskiyedf6be22012-05-16 19:15:56 +0300324 ubifs_dump_lpt_info(c);
325 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +0200326 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +0300327 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300328}
329
330/**
331 * realloc_lpt_leb - allocate an LPT LEB that is empty.
332 * @c: UBIFS file-system description object
333 * @lnum: LEB number is passed and returned here
334 *
335 * This function duplicates exactly the results of the function alloc_lpt_leb.
336 * It is used during end commit to reallocate the same LEB numbers that were
337 * allocated by alloc_lpt_leb during start commit.
338 *
339 * This function finds the next LEB that was allocated by the alloc_lpt_leb
340 * function starting from @lnum. If a LEB is found it is returned in @lnum and
341 * the function returns %0. Otherwise the function returns -ENOSPC.
342 * Note however, that LPT is designed never to run out of space.
343 */
344static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
345{
346 int i, n;
347
348 n = *lnum - c->lpt_first + 1;
349 for (i = n; i < c->lpt_lebs; i++)
350 if (c->ltab[i].cmt) {
351 c->ltab[i].cmt = 0;
352 *lnum = i + c->lpt_first;
353 return 0;
354 }
355
356 for (i = 0; i < n; i++)
357 if (c->ltab[i].cmt) {
358 c->ltab[i].cmt = 0;
359 *lnum = i + c->lpt_first;
360 return 0;
361 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300362 return -ENOSPC;
363}
364
365/**
366 * write_cnodes - write cnodes for commit.
367 * @c: UBIFS file-system description object
368 *
369 * This function returns %0 on success and a negative error code on failure.
370 */
371static int write_cnodes(struct ubifs_info *c)
372{
373 int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
374 struct ubifs_cnode *cnode;
375 void *buf = c->lpt_buf;
376
377 cnode = c->lpt_cnext;
378 if (!cnode)
379 return 0;
380 lnum = c->nhead_lnum;
381 offs = c->nhead_offs;
382 from = offs;
383 /* Ensure empty LEB is unmapped */
384 if (offs == 0) {
385 err = ubifs_leb_unmap(c, lnum);
386 if (err)
387 return err;
388 }
389 /* Try to place lsave and ltab nicely */
390 done_lsave = !c->big_lpt;
391 done_ltab = 0;
392 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
393 done_lsave = 1;
394 ubifs_pack_lsave(c, buf + offs, c->lsave);
395 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300396 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300397 }
398
399 if (offs + c->ltab_sz <= c->leb_size) {
400 done_ltab = 1;
401 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
402 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300403 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300404 }
405
406 /* Loop for each cnode */
407 do {
408 if (cnode->level)
409 len = c->nnode_sz;
410 else
411 len = c->pnode_sz;
412 while (offs + len > c->leb_size) {
413 wlen = offs - from;
414 if (wlen) {
415 alen = ALIGN(wlen, c->min_io_size);
416 memset(buf + offs, 0xff, alen - wlen);
417 err = ubifs_leb_write(c, lnum, buf + from, from,
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200418 alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300419 if (err)
420 return err;
421 }
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200422 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300423 err = realloc_lpt_leb(c, &lnum);
424 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300425 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200426 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300427 ubifs_assert(lnum >= c->lpt_first &&
428 lnum <= c->lpt_last);
429 err = ubifs_leb_unmap(c, lnum);
430 if (err)
431 return err;
432 /* Try to place lsave and ltab nicely */
433 if (!done_lsave) {
434 done_lsave = 1;
435 ubifs_pack_lsave(c, buf + offs, c->lsave);
436 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300437 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300438 continue;
439 }
440 if (!done_ltab) {
441 done_ltab = 1;
442 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
443 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300444 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300445 continue;
446 }
447 break;
448 }
449 if (cnode->level)
450 ubifs_pack_nnode(c, buf + offs,
451 (struct ubifs_nnode *)cnode);
452 else
453 ubifs_pack_pnode(c, buf + offs,
454 (struct ubifs_pnode *)cnode);
455 /*
456 * The reason for the barriers is the same as in case of TNC.
457 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
458 * 'dirty_cow_pnode()' are the functions for which this is
459 * important.
460 */
461 clear_bit(DIRTY_CNODE, &cnode->flags);
Peter Zijlstra4e857c52014-03-17 18:06:10 +0100462 smp_mb__before_atomic();
Artem Bityutskiy37662442011-05-30 14:51:20 +0300463 clear_bit(COW_CNODE, &cnode->flags);
Peter Zijlstra4e857c52014-03-17 18:06:10 +0100464 smp_mb__after_atomic();
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300465 offs += len;
Adrian Hunter73944a62008-09-12 18:13:31 +0300466 dbg_chk_lpt_sz(c, 1, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300467 cnode = cnode->cnext;
468 } while (cnode && cnode != c->lpt_cnext);
469
470 /* Make sure to place LPT's save table */
471 if (!done_lsave) {
472 if (offs + c->lsave_sz > c->leb_size) {
473 wlen = offs - from;
474 alen = ALIGN(wlen, c->min_io_size);
475 memset(buf + offs, 0xff, alen - wlen);
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200476 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300477 if (err)
478 return err;
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200479 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300480 err = realloc_lpt_leb(c, &lnum);
481 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300482 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200483 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300484 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;
Adrian Hunter73944a62008-09-12 18:13:31 +0300493 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300494 }
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);
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200502 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300503 if (err)
504 return err;
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200505 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300506 err = realloc_lpt_leb(c, &lnum);
507 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300508 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200509 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300510 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 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300516 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
517 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300518 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300519 }
520
521 /* Write remaining data in buffer */
522 wlen = offs - from;
523 alen = ALIGN(wlen, c->min_io_size);
524 memset(buf + offs, 0xff, alen - wlen);
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200525 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300526 if (err)
527 return err;
Adrian Hunter73944a62008-09-12 18:13:31 +0300528
529 dbg_chk_lpt_sz(c, 4, alen - wlen);
530 err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));
531 if (err)
532 return err;
533
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300534 c->nhead_lnum = lnum;
535 c->nhead_offs = ALIGN(offs, c->min_io_size);
536
537 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
538 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
539 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
540 if (c->big_lpt)
541 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
Adrian Hunter73944a62008-09-12 18:13:31 +0300542
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300543 return 0;
Adrian Hunter73944a62008-09-12 18:13:31 +0300544
545no_space:
Artem Bityutskiy79fda512012-08-27 13:34:09 +0300546 ubifs_err("LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
547 lnum, offs, len, done_ltab, done_lsave);
Artem Bityutskiyedf6be22012-05-16 19:15:56 +0300548 ubifs_dump_lpt_info(c);
549 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +0200550 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +0300551 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300552}
553
554/**
Adrian Hunter4a29d202009-01-27 15:22:54 +0200555 * next_pnode_to_dirty - find next pnode to dirty.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300556 * @c: UBIFS file-system description object
557 * @pnode: pnode
558 *
Adrian Hunter4a29d202009-01-27 15:22:54 +0200559 * This function returns the next pnode to dirty or %NULL if there are no more
560 * pnodes. Note that pnodes that have never been written (lnum == 0) are
561 * skipped.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300562 */
Adrian Hunter4a29d202009-01-27 15:22:54 +0200563static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,
564 struct ubifs_pnode *pnode)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300565{
566 struct ubifs_nnode *nnode;
567 int iip;
568
569 /* Try to go right */
570 nnode = pnode->parent;
Adrian Hunter4a29d202009-01-27 15:22:54 +0200571 for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300572 if (nnode->nbranch[iip].lnum)
573 return ubifs_get_pnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300574 }
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;
Adrian Hunter4a29d202009-01-27 15:22:54 +0200582 for (; iip < UBIFS_LPT_FANOUT; iip++) {
583 if (nnode->nbranch[iip].lnum)
584 break;
585 }
Artem Bityutskiyc4361572011-03-25 15:27:40 +0200586 } while (iip >= UBIFS_LPT_FANOUT);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300587
588 /* Go right */
589 nnode = ubifs_get_nnode(c, nnode, iip);
590 if (IS_ERR(nnode))
591 return (void *)nnode;
592
593 /* Go down to level 1 */
594 while (nnode->level > 1) {
Adrian Hunter4a29d202009-01-27 15:22:54 +0200595 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {
596 if (nnode->nbranch[iip].lnum)
597 break;
598 }
599 if (iip >= UBIFS_LPT_FANOUT) {
600 /*
601 * Should not happen, but we need to keep going
602 * if it does.
603 */
604 iip = 0;
605 }
606 nnode = ubifs_get_nnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300607 if (IS_ERR(nnode))
608 return (void *)nnode;
609 }
610
Adrian Hunter4a29d202009-01-27 15:22:54 +0200611 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)
612 if (nnode->nbranch[iip].lnum)
613 break;
614 if (iip >= UBIFS_LPT_FANOUT)
615 /* Should not happen, but we need to keep going if it does */
616 iip = 0;
617 return ubifs_get_pnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300618}
619
620/**
621 * pnode_lookup - lookup a pnode in the LPT.
622 * @c: UBIFS file-system description object
623 * @i: pnode number (0 to main_lebs - 1)
624 *
625 * This function returns a pointer to the pnode on success or a negative
626 * error code on failure.
627 */
628static struct ubifs_pnode *pnode_lookup(struct ubifs_info *c, int i)
629{
630 int err, h, iip, shft;
631 struct ubifs_nnode *nnode;
632
633 if (!c->nroot) {
634 err = ubifs_read_nnode(c, NULL, 0);
635 if (err)
636 return ERR_PTR(err);
637 }
638 i <<= UBIFS_LPT_FANOUT_SHIFT;
639 nnode = c->nroot;
640 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
641 for (h = 1; h < c->lpt_hght; h++) {
642 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
643 shft -= UBIFS_LPT_FANOUT_SHIFT;
644 nnode = ubifs_get_nnode(c, nnode, iip);
645 if (IS_ERR(nnode))
Julia Lawall6da51562010-05-22 12:00:21 +0200646 return ERR_CAST(nnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300647 }
648 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
649 return ubifs_get_pnode(c, nnode, iip);
650}
651
652/**
653 * add_pnode_dirt - add dirty space to LPT LEB properties.
654 * @c: UBIFS file-system description object
655 * @pnode: pnode for which to add dirt
656 */
657static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
658{
659 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
660 c->pnode_sz);
661}
662
663/**
664 * do_make_pnode_dirty - mark a pnode dirty.
665 * @c: UBIFS file-system description object
666 * @pnode: pnode to mark dirty
667 */
668static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
669{
670 /* Assumes cnext list is empty i.e. not called during commit */
671 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
672 struct ubifs_nnode *nnode;
673
674 c->dirty_pn_cnt += 1;
675 add_pnode_dirt(c, pnode);
676 /* Mark parent and ancestors dirty too */
677 nnode = pnode->parent;
678 while (nnode) {
679 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
680 c->dirty_nn_cnt += 1;
681 ubifs_add_nnode_dirt(c, nnode);
682 nnode = nnode->parent;
683 } else
684 break;
685 }
686 }
687}
688
689/**
690 * make_tree_dirty - mark the entire LEB properties tree dirty.
691 * @c: UBIFS file-system description object
692 *
693 * This function is used by the "small" LPT model to cause the entire LEB
694 * properties tree to be written. The "small" LPT model does not use LPT
695 * garbage collection because it is more efficient to write the entire tree
696 * (because it is small).
697 *
698 * This function returns %0 on success and a negative error code on failure.
699 */
700static int make_tree_dirty(struct ubifs_info *c)
701{
702 struct ubifs_pnode *pnode;
703
704 pnode = pnode_lookup(c, 0);
Vasiliy Kulikov8c893a52010-09-05 22:33:04 +0400705 if (IS_ERR(pnode))
706 return PTR_ERR(pnode);
707
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300708 while (pnode) {
709 do_make_pnode_dirty(c, pnode);
Adrian Hunter4a29d202009-01-27 15:22:54 +0200710 pnode = next_pnode_to_dirty(c, pnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300711 if (IS_ERR(pnode))
712 return PTR_ERR(pnode);
713 }
714 return 0;
715}
716
717/**
718 * need_write_all - determine if the LPT area is running out of free space.
719 * @c: UBIFS file-system description object
720 *
721 * This function returns %1 if the LPT area is running out of free space and %0
722 * if it is not.
723 */
724static int need_write_all(struct ubifs_info *c)
725{
726 long long free = 0;
727 int i;
728
729 for (i = 0; i < c->lpt_lebs; i++) {
730 if (i + c->lpt_first == c->nhead_lnum)
731 free += c->leb_size - c->nhead_offs;
732 else if (c->ltab[i].free == c->leb_size)
733 free += c->leb_size;
734 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
735 free += c->leb_size;
736 }
737 /* Less than twice the size left */
738 if (free <= c->lpt_sz * 2)
739 return 1;
740 return 0;
741}
742
743/**
744 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
745 * @c: UBIFS file-system description object
746 *
747 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
748 * free space and so may be reused as soon as the next commit is completed.
749 * This function is called during start commit to mark LPT LEBs for trivial GC.
750 */
751static void lpt_tgc_start(struct ubifs_info *c)
752{
753 int i;
754
755 for (i = 0; i < c->lpt_lebs; i++) {
756 if (i + c->lpt_first == c->nhead_lnum)
757 continue;
758 if (c->ltab[i].dirty > 0 &&
759 c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
760 c->ltab[i].tgc = 1;
761 c->ltab[i].free = c->leb_size;
762 c->ltab[i].dirty = 0;
763 dbg_lp("LEB %d", i + c->lpt_first);
764 }
765 }
766}
767
768/**
769 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
770 * @c: UBIFS file-system description object
771 *
772 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
773 * free space and so may be reused as soon as the next commit is completed.
774 * This function is called after the commit is completed (master node has been
Artem Bityutskiy80736d42008-12-30 17:44:02 +0200775 * written) and un-maps LPT LEBs that were marked for trivial GC.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300776 */
777static int lpt_tgc_end(struct ubifs_info *c)
778{
779 int i, err;
780
781 for (i = 0; i < c->lpt_lebs; i++)
782 if (c->ltab[i].tgc) {
783 err = ubifs_leb_unmap(c, i + c->lpt_first);
784 if (err)
785 return err;
786 c->ltab[i].tgc = 0;
787 dbg_lp("LEB %d", i + c->lpt_first);
788 }
789 return 0;
790}
791
792/**
793 * populate_lsave - fill the lsave array with important LEB numbers.
794 * @c: the UBIFS file-system description object
795 *
796 * This function is only called for the "big" model. It records a small number
797 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
798 * most important to least important): empty, freeable, freeable index, dirty
799 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
800 * their pnodes into memory. That will stop us from having to scan the LPT
801 * straight away. For the "small" model we assume that scanning the LPT is no
802 * big deal.
803 */
804static void populate_lsave(struct ubifs_info *c)
805{
806 struct ubifs_lprops *lprops;
807 struct ubifs_lpt_heap *heap;
808 int i, cnt = 0;
809
810 ubifs_assert(c->big_lpt);
811 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
812 c->lpt_drty_flgs |= LSAVE_DIRTY;
813 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
814 }
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +0300815
816 if (dbg_populate_lsave(c))
817 return;
818
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300819 list_for_each_entry(lprops, &c->empty_list, list) {
820 c->lsave[cnt++] = lprops->lnum;
821 if (cnt >= c->lsave_cnt)
822 return;
823 }
824 list_for_each_entry(lprops, &c->freeable_list, list) {
825 c->lsave[cnt++] = lprops->lnum;
826 if (cnt >= c->lsave_cnt)
827 return;
828 }
829 list_for_each_entry(lprops, &c->frdi_idx_list, list) {
830 c->lsave[cnt++] = lprops->lnum;
831 if (cnt >= c->lsave_cnt)
832 return;
833 }
834 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
835 for (i = 0; i < heap->cnt; i++) {
836 c->lsave[cnt++] = heap->arr[i]->lnum;
837 if (cnt >= c->lsave_cnt)
838 return;
839 }
840 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
841 for (i = 0; i < heap->cnt; i++) {
842 c->lsave[cnt++] = heap->arr[i]->lnum;
843 if (cnt >= c->lsave_cnt)
844 return;
845 }
846 heap = &c->lpt_heap[LPROPS_FREE - 1];
847 for (i = 0; i < heap->cnt; i++) {
848 c->lsave[cnt++] = heap->arr[i]->lnum;
849 if (cnt >= c->lsave_cnt)
850 return;
851 }
852 /* Fill it up completely */
853 while (cnt < c->lsave_cnt)
854 c->lsave[cnt++] = c->main_first;
855}
856
857/**
858 * nnode_lookup - lookup a nnode in the LPT.
859 * @c: UBIFS file-system description object
860 * @i: nnode number
861 *
862 * This function returns a pointer to the nnode on success or a negative
863 * error code on failure.
864 */
865static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
866{
867 int err, iip;
868 struct ubifs_nnode *nnode;
869
870 if (!c->nroot) {
871 err = ubifs_read_nnode(c, NULL, 0);
872 if (err)
873 return ERR_PTR(err);
874 }
875 nnode = c->nroot;
876 while (1) {
877 iip = i & (UBIFS_LPT_FANOUT - 1);
878 i >>= UBIFS_LPT_FANOUT_SHIFT;
879 if (!i)
880 break;
881 nnode = ubifs_get_nnode(c, nnode, iip);
882 if (IS_ERR(nnode))
883 return nnode;
884 }
885 return nnode;
886}
887
888/**
889 * make_nnode_dirty - find a nnode and, if found, make it dirty.
890 * @c: UBIFS file-system description object
891 * @node_num: nnode number of nnode to make dirty
892 * @lnum: LEB number where nnode was written
893 * @offs: offset where nnode was written
894 *
895 * This function is used by LPT garbage collection. LPT garbage collection is
896 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
897 * simply involves marking all the nodes in the LEB being garbage-collected as
898 * dirty. The dirty nodes are written next commit, after which the LEB is free
899 * to be reused.
900 *
901 * This function returns %0 on success and a negative error code on failure.
902 */
903static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
904 int offs)
905{
906 struct ubifs_nnode *nnode;
907
908 nnode = nnode_lookup(c, node_num);
909 if (IS_ERR(nnode))
910 return PTR_ERR(nnode);
911 if (nnode->parent) {
912 struct ubifs_nbranch *branch;
913
914 branch = &nnode->parent->nbranch[nnode->iip];
915 if (branch->lnum != lnum || branch->offs != offs)
916 return 0; /* nnode is obsolete */
917 } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
918 return 0; /* nnode is obsolete */
919 /* Assumes cnext list is empty i.e. not called during commit */
920 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
921 c->dirty_nn_cnt += 1;
922 ubifs_add_nnode_dirt(c, nnode);
923 /* Mark parent and ancestors dirty too */
924 nnode = nnode->parent;
925 while (nnode) {
926 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
927 c->dirty_nn_cnt += 1;
928 ubifs_add_nnode_dirt(c, nnode);
929 nnode = nnode->parent;
930 } else
931 break;
932 }
933 }
934 return 0;
935}
936
937/**
938 * make_pnode_dirty - find a pnode and, if found, make it dirty.
939 * @c: UBIFS file-system description object
940 * @node_num: pnode number of pnode to make dirty
941 * @lnum: LEB number where pnode was written
942 * @offs: offset where pnode was written
943 *
944 * This function is used by LPT garbage collection. LPT garbage collection is
945 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
946 * simply involves marking all the nodes in the LEB being garbage-collected as
947 * dirty. The dirty nodes are written next commit, after which the LEB is free
948 * to be reused.
949 *
950 * This function returns %0 on success and a negative error code on failure.
951 */
952static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
953 int offs)
954{
955 struct ubifs_pnode *pnode;
956 struct ubifs_nbranch *branch;
957
958 pnode = pnode_lookup(c, node_num);
959 if (IS_ERR(pnode))
960 return PTR_ERR(pnode);
961 branch = &pnode->parent->nbranch[pnode->iip];
962 if (branch->lnum != lnum || branch->offs != offs)
963 return 0;
964 do_make_pnode_dirty(c, pnode);
965 return 0;
966}
967
968/**
969 * make_ltab_dirty - make ltab node dirty.
970 * @c: UBIFS file-system description object
971 * @lnum: LEB number where ltab was written
972 * @offs: offset where ltab 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 */
982static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
983{
984 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
985 return 0; /* This ltab node is obsolete */
986 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
987 c->lpt_drty_flgs |= LTAB_DIRTY;
988 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
989 }
990 return 0;
991}
992
993/**
994 * make_lsave_dirty - make lsave node dirty.
995 * @c: UBIFS file-system description object
996 * @lnum: LEB number where lsave was written
997 * @offs: offset where lsave 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 */
1007static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1008{
1009 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1010 return 0; /* This lsave node is obsolete */
1011 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
1012 c->lpt_drty_flgs |= LSAVE_DIRTY;
1013 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
1014 }
1015 return 0;
1016}
1017
1018/**
1019 * make_node_dirty - make node dirty.
1020 * @c: UBIFS file-system description object
1021 * @node_type: LPT node type
1022 * @node_num: node number
1023 * @lnum: LEB number where node was written
1024 * @offs: offset where node was written
1025 *
1026 * This function is used by LPT garbage collection. LPT garbage collection is
1027 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1028 * simply involves marking all the nodes in the LEB being garbage-collected as
1029 * dirty. The dirty nodes are written next commit, after which the LEB is free
1030 * to be reused.
1031 *
1032 * This function returns %0 on success and a negative error code on failure.
1033 */
1034static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
1035 int lnum, int offs)
1036{
1037 switch (node_type) {
1038 case UBIFS_LPT_NNODE:
1039 return make_nnode_dirty(c, node_num, lnum, offs);
1040 case UBIFS_LPT_PNODE:
1041 return make_pnode_dirty(c, node_num, lnum, offs);
1042 case UBIFS_LPT_LTAB:
1043 return make_ltab_dirty(c, lnum, offs);
1044 case UBIFS_LPT_LSAVE:
1045 return make_lsave_dirty(c, lnum, offs);
1046 }
1047 return -EINVAL;
1048}
1049
1050/**
1051 * get_lpt_node_len - return the length of a node based on its type.
1052 * @c: UBIFS file-system description object
1053 * @node_type: LPT node type
1054 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001055static int get_lpt_node_len(const struct ubifs_info *c, int node_type)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001056{
1057 switch (node_type) {
1058 case UBIFS_LPT_NNODE:
1059 return c->nnode_sz;
1060 case UBIFS_LPT_PNODE:
1061 return c->pnode_sz;
1062 case UBIFS_LPT_LTAB:
1063 return c->ltab_sz;
1064 case UBIFS_LPT_LSAVE:
1065 return c->lsave_sz;
1066 }
1067 return 0;
1068}
1069
1070/**
1071 * get_pad_len - return the length of padding in a buffer.
1072 * @c: UBIFS file-system description object
1073 * @buf: buffer
1074 * @len: length of buffer
1075 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001076static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001077{
1078 int offs, pad_len;
1079
1080 if (c->min_io_size == 1)
1081 return 0;
1082 offs = c->leb_size - len;
1083 pad_len = ALIGN(offs, c->min_io_size) - offs;
1084 return pad_len;
1085}
1086
1087/**
1088 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1089 * @c: UBIFS file-system description object
1090 * @buf: buffer
1091 * @node_num: node number is returned here
1092 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001093static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,
1094 int *node_num)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001095{
1096 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1097 int pos = 0, node_type;
1098
1099 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1100 *node_num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1101 return node_type;
1102}
1103
1104/**
1105 * is_a_node - determine if a buffer contains a node.
1106 * @c: UBIFS file-system description object
1107 * @buf: buffer
1108 * @len: length of buffer
1109 *
1110 * This function returns %1 if the buffer contains a node or %0 if it does not.
1111 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001112static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001113{
1114 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1115 int pos = 0, node_type, node_len;
1116 uint16_t crc, calc_crc;
1117
Adrian Hunterbe2f6bd2008-09-26 12:52:21 +03001118 if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1119 return 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001120 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1121 if (node_type == UBIFS_LPT_NOT_A_NODE)
1122 return 0;
1123 node_len = get_lpt_node_len(c, node_type);
1124 if (!node_len || node_len > len)
1125 return 0;
1126 pos = 0;
1127 addr = buf;
1128 crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
1129 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1130 node_len - UBIFS_LPT_CRC_BYTES);
1131 if (crc != calc_crc)
1132 return 0;
1133 return 1;
1134}
1135
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001136/**
1137 * lpt_gc_lnum - garbage collect a LPT LEB.
1138 * @c: UBIFS file-system description object
1139 * @lnum: LEB number to garbage collect
1140 *
1141 * LPT garbage collection is used only for the "big" LPT model
1142 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1143 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1144 * next commit, after which the LEB is free to be reused.
1145 *
1146 * This function returns %0 on success and a negative error code on failure.
1147 */
1148static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1149{
1150 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1151 void *buf = c->lpt_buf;
1152
1153 dbg_lp("LEB %d", lnum);
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001154
1155 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1156 if (err)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001157 return err;
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001158
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001159 while (1) {
1160 if (!is_a_node(c, buf, len)) {
1161 int pad_len;
1162
1163 pad_len = get_pad_len(c, buf, len);
1164 if (pad_len) {
1165 buf += pad_len;
1166 len -= pad_len;
1167 continue;
1168 }
1169 return 0;
1170 }
1171 node_type = get_lpt_node_type(c, buf, &node_num);
1172 node_len = get_lpt_node_len(c, node_type);
1173 offs = c->leb_size - len;
1174 ubifs_assert(node_len != 0);
1175 mutex_lock(&c->lp_mutex);
1176 err = make_node_dirty(c, node_type, node_num, lnum, offs);
1177 mutex_unlock(&c->lp_mutex);
1178 if (err)
1179 return err;
1180 buf += node_len;
1181 len -= node_len;
1182 }
1183 return 0;
1184}
1185
1186/**
1187 * lpt_gc - LPT garbage collection.
1188 * @c: UBIFS file-system description object
1189 *
1190 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1191 * Returns %0 on success and a negative error code on failure.
1192 */
1193static int lpt_gc(struct ubifs_info *c)
1194{
1195 int i, lnum = -1, dirty = 0;
1196
1197 mutex_lock(&c->lp_mutex);
1198 for (i = 0; i < c->lpt_lebs; i++) {
1199 ubifs_assert(!c->ltab[i].tgc);
1200 if (i + c->lpt_first == c->nhead_lnum ||
1201 c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1202 continue;
1203 if (c->ltab[i].dirty > dirty) {
1204 dirty = c->ltab[i].dirty;
1205 lnum = i + c->lpt_first;
1206 }
1207 }
1208 mutex_unlock(&c->lp_mutex);
1209 if (lnum == -1)
1210 return -ENOSPC;
1211 return lpt_gc_lnum(c, lnum);
1212}
1213
1214/**
1215 * ubifs_lpt_start_commit - UBIFS commit starts.
1216 * @c: the UBIFS file-system description object
1217 *
1218 * This function has to be called when UBIFS starts the commit operation.
1219 * This function "freezes" all currently dirty LEB properties and does not
1220 * change them anymore. Further changes are saved and tracked separately
1221 * because they are not part of this commit. This function returns zero in case
1222 * of success and a negative error code in case of failure.
1223 */
1224int ubifs_lpt_start_commit(struct ubifs_info *c)
1225{
1226 int err, cnt;
1227
1228 dbg_lp("");
1229
1230 mutex_lock(&c->lp_mutex);
Adrian Hunter73944a62008-09-12 18:13:31 +03001231 err = dbg_chk_lpt_free_spc(c);
1232 if (err)
1233 goto out;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001234 err = dbg_check_ltab(c);
1235 if (err)
1236 goto out;
1237
1238 if (c->check_lpt_free) {
1239 /*
1240 * We ensure there is enough free space in
1241 * ubifs_lpt_post_commit() by marking nodes dirty. That
1242 * information is lost when we unmount, so we also need
1243 * to check free space once after mounting also.
1244 */
1245 c->check_lpt_free = 0;
1246 while (need_write_all(c)) {
1247 mutex_unlock(&c->lp_mutex);
1248 err = lpt_gc(c);
1249 if (err)
1250 return err;
1251 mutex_lock(&c->lp_mutex);
1252 }
1253 }
1254
1255 lpt_tgc_start(c);
1256
1257 if (!c->dirty_pn_cnt) {
1258 dbg_cmt("no cnodes to commit");
1259 err = 0;
1260 goto out;
1261 }
1262
1263 if (!c->big_lpt && need_write_all(c)) {
1264 /* If needed, write everything */
1265 err = make_tree_dirty(c);
1266 if (err)
1267 goto out;
1268 lpt_tgc_start(c);
1269 }
1270
1271 if (c->big_lpt)
1272 populate_lsave(c);
1273
1274 cnt = get_cnodes_to_commit(c);
1275 ubifs_assert(cnt != 0);
1276
1277 err = layout_cnodes(c);
1278 if (err)
1279 goto out;
1280
1281 /* Copy the LPT's own lprops for end commit to write */
1282 memcpy(c->ltab_cmt, c->ltab,
1283 sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1284 c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1285
1286out:
1287 mutex_unlock(&c->lp_mutex);
1288 return err;
1289}
1290
1291/**
1292 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1293 * @c: UBIFS file-system description object
1294 */
1295static void free_obsolete_cnodes(struct ubifs_info *c)
1296{
1297 struct ubifs_cnode *cnode, *cnext;
1298
1299 cnext = c->lpt_cnext;
1300 if (!cnext)
1301 return;
1302 do {
1303 cnode = cnext;
1304 cnext = cnode->cnext;
1305 if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1306 kfree(cnode);
1307 else
1308 cnode->cnext = NULL;
1309 } while (cnext != c->lpt_cnext);
1310 c->lpt_cnext = NULL;
1311}
1312
1313/**
1314 * ubifs_lpt_end_commit - finish the commit operation.
1315 * @c: the UBIFS file-system description object
1316 *
1317 * This function has to be called when the commit operation finishes. It
1318 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1319 * the media. Returns zero in case of success and a negative error code in case
1320 * of failure.
1321 */
1322int ubifs_lpt_end_commit(struct ubifs_info *c)
1323{
1324 int err;
1325
1326 dbg_lp("");
1327
1328 if (!c->lpt_cnext)
1329 return 0;
1330
1331 err = write_cnodes(c);
1332 if (err)
1333 return err;
1334
1335 mutex_lock(&c->lp_mutex);
1336 free_obsolete_cnodes(c);
1337 mutex_unlock(&c->lp_mutex);
1338
1339 return 0;
1340}
1341
1342/**
1343 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1344 * @c: UBIFS file-system description object
1345 *
1346 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1347 * commit for the "big" LPT model.
1348 */
1349int ubifs_lpt_post_commit(struct ubifs_info *c)
1350{
1351 int err;
1352
1353 mutex_lock(&c->lp_mutex);
1354 err = lpt_tgc_end(c);
1355 if (err)
1356 goto out;
1357 if (c->big_lpt)
1358 while (need_write_all(c)) {
1359 mutex_unlock(&c->lp_mutex);
1360 err = lpt_gc(c);
1361 if (err)
1362 return err;
1363 mutex_lock(&c->lp_mutex);
1364 }
1365out:
1366 mutex_unlock(&c->lp_mutex);
1367 return err;
1368}
1369
1370/**
1371 * first_nnode - find the first nnode in memory.
1372 * @c: UBIFS file-system description object
1373 * @hght: height of tree where nnode found is returned here
1374 *
1375 * This function returns a pointer to the nnode found or %NULL if no nnode is
1376 * found. This function is a helper to 'ubifs_lpt_free()'.
1377 */
1378static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1379{
1380 struct ubifs_nnode *nnode;
1381 int h, i, found;
1382
1383 nnode = c->nroot;
1384 *hght = 0;
1385 if (!nnode)
1386 return NULL;
1387 for (h = 1; h < c->lpt_hght; h++) {
1388 found = 0;
1389 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1390 if (nnode->nbranch[i].nnode) {
1391 found = 1;
1392 nnode = nnode->nbranch[i].nnode;
1393 *hght = h;
1394 break;
1395 }
1396 }
1397 if (!found)
1398 break;
1399 }
1400 return nnode;
1401}
1402
1403/**
1404 * next_nnode - find the next nnode in memory.
1405 * @c: UBIFS file-system description object
1406 * @nnode: nnode from which to start.
1407 * @hght: height of tree where nnode is, is passed and returned here
1408 *
1409 * This function returns a pointer to the nnode found or %NULL if no nnode is
1410 * found. This function is a helper to 'ubifs_lpt_free()'.
1411 */
1412static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1413 struct ubifs_nnode *nnode, int *hght)
1414{
1415 struct ubifs_nnode *parent;
1416 int iip, h, i, found;
1417
1418 parent = nnode->parent;
1419 if (!parent)
1420 return NULL;
1421 if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1422 *hght -= 1;
1423 return parent;
1424 }
1425 for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1426 nnode = parent->nbranch[iip].nnode;
1427 if (nnode)
1428 break;
1429 }
1430 if (!nnode) {
1431 *hght -= 1;
1432 return parent;
1433 }
1434 for (h = *hght + 1; h < c->lpt_hght; h++) {
1435 found = 0;
1436 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1437 if (nnode->nbranch[i].nnode) {
1438 found = 1;
1439 nnode = nnode->nbranch[i].nnode;
1440 *hght = h;
1441 break;
1442 }
1443 }
1444 if (!found)
1445 break;
1446 }
1447 return nnode;
1448}
1449
1450/**
1451 * ubifs_lpt_free - free resources owned by the LPT.
1452 * @c: UBIFS file-system description object
1453 * @wr_only: free only resources used for writing
1454 */
1455void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1456{
1457 struct ubifs_nnode *nnode;
1458 int i, hght;
1459
1460 /* Free write-only things first */
1461
1462 free_obsolete_cnodes(c); /* Leftover from a failed commit */
1463
1464 vfree(c->ltab_cmt);
1465 c->ltab_cmt = NULL;
1466 vfree(c->lpt_buf);
1467 c->lpt_buf = NULL;
1468 kfree(c->lsave);
1469 c->lsave = NULL;
1470
1471 if (wr_only)
1472 return;
1473
1474 /* Now free the rest */
1475
1476 nnode = first_nnode(c, &hght);
1477 while (nnode) {
1478 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1479 kfree(nnode->nbranch[i].nnode);
1480 nnode = next_nnode(c, nnode, &hght);
1481 }
1482 for (i = 0; i < LPROPS_HEAP_CNT; i++)
1483 kfree(c->lpt_heap[i].arr);
1484 kfree(c->dirty_idx.arr);
1485 kfree(c->nroot);
1486 vfree(c->ltab);
1487 kfree(c->lpt_nod_buf);
1488}
1489
Artem Bityutskiyf70b7e52012-05-16 19:53:46 +03001490/*
1491 * Everything below is related to debugging.
1492 */
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001493
1494/**
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001495 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001496 * @buf: buffer
1497 * @len: buffer length
1498 */
1499static int dbg_is_all_ff(uint8_t *buf, int len)
1500{
1501 int i;
1502
1503 for (i = 0; i < len; i++)
1504 if (buf[i] != 0xff)
1505 return 0;
1506 return 1;
1507}
1508
1509/**
1510 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1511 * @c: the UBIFS file-system description object
1512 * @lnum: LEB number where nnode was written
1513 * @offs: offset where nnode was written
1514 */
1515static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1516{
1517 struct ubifs_nnode *nnode;
1518 int hght;
1519
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001520 /* Entire tree is in memory so first_nnode / next_nnode are OK */
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001521 nnode = first_nnode(c, &hght);
1522 for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1523 struct ubifs_nbranch *branch;
1524
1525 cond_resched();
1526 if (nnode->parent) {
1527 branch = &nnode->parent->nbranch[nnode->iip];
1528 if (branch->lnum != lnum || branch->offs != offs)
1529 continue;
1530 if (test_bit(DIRTY_CNODE, &nnode->flags))
1531 return 1;
1532 return 0;
1533 } else {
1534 if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1535 continue;
1536 if (test_bit(DIRTY_CNODE, &nnode->flags))
1537 return 1;
1538 return 0;
1539 }
1540 }
1541 return 1;
1542}
1543
1544/**
1545 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1546 * @c: the UBIFS file-system description object
1547 * @lnum: LEB number where pnode was written
1548 * @offs: offset where pnode was written
1549 */
1550static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1551{
1552 int i, cnt;
1553
1554 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1555 for (i = 0; i < cnt; i++) {
1556 struct ubifs_pnode *pnode;
1557 struct ubifs_nbranch *branch;
1558
1559 cond_resched();
1560 pnode = pnode_lookup(c, i);
1561 if (IS_ERR(pnode))
1562 return PTR_ERR(pnode);
1563 branch = &pnode->parent->nbranch[pnode->iip];
1564 if (branch->lnum != lnum || branch->offs != offs)
1565 continue;
1566 if (test_bit(DIRTY_CNODE, &pnode->flags))
1567 return 1;
1568 return 0;
1569 }
1570 return 1;
1571}
1572
1573/**
1574 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1575 * @c: the UBIFS file-system description object
1576 * @lnum: LEB number where ltab node was written
1577 * @offs: offset where ltab node was written
1578 */
1579static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1580{
1581 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1582 return 1;
1583 return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1584}
1585
1586/**
1587 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1588 * @c: the UBIFS file-system description object
1589 * @lnum: LEB number where lsave node was written
1590 * @offs: offset where lsave node was written
1591 */
1592static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1593{
1594 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1595 return 1;
1596 return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1597}
1598
1599/**
1600 * dbg_is_node_dirty - determine if a node is dirty.
1601 * @c: the UBIFS file-system description object
1602 * @node_type: node type
1603 * @lnum: LEB number where node was written
1604 * @offs: offset where node was written
1605 */
1606static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1607 int offs)
1608{
1609 switch (node_type) {
1610 case UBIFS_LPT_NNODE:
1611 return dbg_is_nnode_dirty(c, lnum, offs);
1612 case UBIFS_LPT_PNODE:
1613 return dbg_is_pnode_dirty(c, lnum, offs);
1614 case UBIFS_LPT_LTAB:
1615 return dbg_is_ltab_dirty(c, lnum, offs);
1616 case UBIFS_LPT_LSAVE:
1617 return dbg_is_lsave_dirty(c, lnum, offs);
1618 }
1619 return 1;
1620}
1621
1622/**
1623 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1624 * @c: the UBIFS file-system description object
1625 * @lnum: LEB number where node was written
1626 * @offs: offset where node was written
1627 *
1628 * This function returns %0 on success and a negative error code on failure.
1629 */
1630static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1631{
1632 int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1633 int ret;
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001634 void *buf, *p;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001635
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001636 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001637 return 0;
1638
Artem Bityutskiyfc5e58c2011-03-24 16:14:26 +02001639 buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001640 if (!buf) {
1641 ubifs_err("cannot allocate memory for ltab checking");
1642 return 0;
1643 }
1644
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001645 dbg_lp("LEB %d", lnum);
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001646
1647 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1648 if (err)
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001649 goto out;
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001650
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001651 while (1) {
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001652 if (!is_a_node(c, p, len)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001653 int i, pad_len;
1654
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001655 pad_len = get_pad_len(c, p, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001656 if (pad_len) {
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001657 p += pad_len;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001658 len -= pad_len;
1659 dirty += pad_len;
1660 continue;
1661 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001662 if (!dbg_is_all_ff(p, len)) {
Artem Bityutskiy3668b702012-08-27 16:56:58 +03001663 ubifs_err("invalid empty space in LEB %d at %d",
1664 lnum, c->leb_size - len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001665 err = -EINVAL;
1666 }
1667 i = lnum - c->lpt_first;
1668 if (len != c->ltab[i].free) {
Artem Bityutskiy3668b702012-08-27 16:56:58 +03001669 ubifs_err("invalid free space in LEB %d (free %d, expected %d)",
1670 lnum, len, c->ltab[i].free);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001671 err = -EINVAL;
1672 }
1673 if (dirty != c->ltab[i].dirty) {
Artem Bityutskiy3668b702012-08-27 16:56:58 +03001674 ubifs_err("invalid dirty space in LEB %d (dirty %d, expected %d)",
1675 lnum, dirty, c->ltab[i].dirty);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001676 err = -EINVAL;
1677 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001678 goto out;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001679 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001680 node_type = get_lpt_node_type(c, p, &node_num);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001681 node_len = get_lpt_node_len(c, node_type);
1682 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1683 if (ret == 1)
1684 dirty += node_len;
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001685 p += node_len;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001686 len -= node_len;
1687 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001688
1689 err = 0;
1690out:
1691 vfree(buf);
1692 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001693}
1694
1695/**
1696 * dbg_check_ltab - check the free and dirty space in the ltab.
1697 * @c: the UBIFS file-system description object
1698 *
1699 * This function returns %0 on success and a negative error code on failure.
1700 */
1701int dbg_check_ltab(struct ubifs_info *c)
1702{
1703 int lnum, err, i, cnt;
1704
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001705 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001706 return 0;
1707
1708 /* Bring the entire tree into memory */
1709 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1710 for (i = 0; i < cnt; i++) {
1711 struct ubifs_pnode *pnode;
1712
1713 pnode = pnode_lookup(c, i);
1714 if (IS_ERR(pnode))
1715 return PTR_ERR(pnode);
1716 cond_resched();
1717 }
1718
1719 /* Check nodes */
1720 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1721 if (err)
1722 return err;
1723
1724 /* Check each LEB */
1725 for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1726 err = dbg_check_ltab_lnum(c, lnum);
1727 if (err) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001728 ubifs_err("failed at LEB %d", lnum);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001729 return err;
1730 }
1731 }
1732
1733 dbg_lp("succeeded");
1734 return 0;
1735}
1736
Adrian Hunter73944a62008-09-12 18:13:31 +03001737/**
1738 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1739 * @c: the UBIFS file-system description object
1740 *
1741 * This function returns %0 on success and a negative error code on failure.
1742 */
1743int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1744{
1745 long long free = 0;
1746 int i;
1747
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001748 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001749 return 0;
1750
Adrian Hunter73944a62008-09-12 18:13:31 +03001751 for (i = 0; i < c->lpt_lebs; i++) {
1752 if (c->ltab[i].tgc || c->ltab[i].cmt)
1753 continue;
1754 if (i + c->lpt_first == c->nhead_lnum)
1755 free += c->leb_size - c->nhead_offs;
1756 else if (c->ltab[i].free == c->leb_size)
1757 free += c->leb_size;
1758 }
1759 if (free < c->lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001760 ubifs_err("LPT space error: free %lld lpt_sz %lld",
1761 free, c->lpt_sz);
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001762 ubifs_dump_lpt_info(c);
1763 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001764 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +03001765 return -EINVAL;
1766 }
1767 return 0;
1768}
1769
1770/**
1771 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1772 * @c: the UBIFS file-system description object
Adrian Hunter2bc275e2009-02-05 13:08:11 +02001773 * @action: what to do
Adrian Hunter73944a62008-09-12 18:13:31 +03001774 * @len: length written
1775 *
1776 * This function returns %0 on success and a negative error code on failure.
Adrian Hunter2bc275e2009-02-05 13:08:11 +02001777 * The @action argument may be one of:
1778 * o %0 - LPT debugging checking starts, initialize debugging variables;
1779 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1780 * o %2 - switched to a different LEB and wasted @len bytes;
1781 * o %3 - check that we've written the right number of bytes.
1782 * o %4 - wasted @len bytes;
Adrian Hunter73944a62008-09-12 18:13:31 +03001783 */
1784int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1785{
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001786 struct ubifs_debug_info *d = c->dbg;
Adrian Hunter73944a62008-09-12 18:13:31 +03001787 long long chk_lpt_sz, lpt_sz;
1788 int err = 0;
1789
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001790 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001791 return 0;
1792
Adrian Hunter73944a62008-09-12 18:13:31 +03001793 switch (action) {
1794 case 0:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001795 d->chk_lpt_sz = 0;
1796 d->chk_lpt_sz2 = 0;
1797 d->chk_lpt_lebs = 0;
1798 d->chk_lpt_wastage = 0;
Adrian Hunter73944a62008-09-12 18:13:31 +03001799 if (c->dirty_pn_cnt > c->pnode_cnt) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001800 ubifs_err("dirty pnodes %d exceed max %d",
1801 c->dirty_pn_cnt, c->pnode_cnt);
Adrian Hunter73944a62008-09-12 18:13:31 +03001802 err = -EINVAL;
1803 }
1804 if (c->dirty_nn_cnt > c->nnode_cnt) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001805 ubifs_err("dirty nnodes %d exceed max %d",
1806 c->dirty_nn_cnt, c->nnode_cnt);
Adrian Hunter73944a62008-09-12 18:13:31 +03001807 err = -EINVAL;
1808 }
1809 return err;
1810 case 1:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001811 d->chk_lpt_sz += len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001812 return 0;
1813 case 2:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001814 d->chk_lpt_sz += len;
1815 d->chk_lpt_wastage += len;
1816 d->chk_lpt_lebs += 1;
Adrian Hunter73944a62008-09-12 18:13:31 +03001817 return 0;
1818 case 3:
1819 chk_lpt_sz = c->leb_size;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001820 chk_lpt_sz *= d->chk_lpt_lebs;
Adrian Hunter73944a62008-09-12 18:13:31 +03001821 chk_lpt_sz += len - c->nhead_offs;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001822 if (d->chk_lpt_sz != chk_lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001823 ubifs_err("LPT wrote %lld but space used was %lld",
1824 d->chk_lpt_sz, chk_lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001825 err = -EINVAL;
1826 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001827 if (d->chk_lpt_sz > c->lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001828 ubifs_err("LPT wrote %lld but lpt_sz is %lld",
1829 d->chk_lpt_sz, c->lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001830 err = -EINVAL;
1831 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001832 if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001833 ubifs_err("LPT layout size %lld but wrote %lld",
1834 d->chk_lpt_sz, d->chk_lpt_sz2);
Adrian Hunter73944a62008-09-12 18:13:31 +03001835 err = -EINVAL;
1836 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001837 if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001838 ubifs_err("LPT new nhead offs: expected %d was %d",
1839 d->new_nhead_offs, len);
Adrian Hunter73944a62008-09-12 18:13:31 +03001840 err = -EINVAL;
1841 }
1842 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1843 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1844 lpt_sz += c->ltab_sz;
1845 if (c->big_lpt)
1846 lpt_sz += c->lsave_sz;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001847 if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001848 ubifs_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1849 d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001850 err = -EINVAL;
1851 }
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001852 if (err) {
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001853 ubifs_dump_lpt_info(c);
1854 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001855 dump_stack();
1856 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001857 d->chk_lpt_sz2 = d->chk_lpt_sz;
1858 d->chk_lpt_sz = 0;
1859 d->chk_lpt_wastage = 0;
1860 d->chk_lpt_lebs = 0;
1861 d->new_nhead_offs = len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001862 return err;
1863 case 4:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001864 d->chk_lpt_sz += len;
1865 d->chk_lpt_wastage += len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001866 return 0;
1867 default:
1868 return -EINVAL;
1869 }
1870}
1871
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001872/**
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001873 * ubifs_dump_lpt_leb - dump an LPT LEB.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001874 * @c: UBIFS file-system description object
1875 * @lnum: LEB number to dump
1876 *
1877 * This function dumps an LEB from LPT area. Nodes in this area are very
1878 * different to nodes in the main area (e.g., they do not have common headers,
1879 * they do not have 8-byte alignments, etc), so we have a separate function to
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001880 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001881 */
1882static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1883{
1884 int err, len = c->leb_size, node_type, node_num, node_len, offs;
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001885 void *buf, *p;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001886
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001887 pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
Artem Bityutskiyfc5e58c2011-03-24 16:14:26 +02001888 buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001889 if (!buf) {
1890 ubifs_err("cannot allocate memory to dump LPT");
1891 return;
1892 }
1893
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001894 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1895 if (err)
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001896 goto out;
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001897
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001898 while (1) {
1899 offs = c->leb_size - len;
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001900 if (!is_a_node(c, p, len)) {
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001901 int pad_len;
1902
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001903 pad_len = get_pad_len(c, p, len);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001904 if (pad_len) {
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001905 pr_err("LEB %d:%d, pad %d bytes\n",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001906 lnum, offs, pad_len);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001907 p += pad_len;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001908 len -= pad_len;
1909 continue;
1910 }
1911 if (len)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001912 pr_err("LEB %d:%d, free %d bytes\n",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001913 lnum, offs, len);
1914 break;
1915 }
1916
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001917 node_type = get_lpt_node_type(c, p, &node_num);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001918 switch (node_type) {
1919 case UBIFS_LPT_PNODE:
1920 {
1921 node_len = c->pnode_sz;
1922 if (c->big_lpt)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001923 pr_err("LEB %d:%d, pnode num %d\n",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001924 lnum, offs, node_num);
1925 else
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001926 pr_err("LEB %d:%d, pnode\n", lnum, offs);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001927 break;
1928 }
1929 case UBIFS_LPT_NNODE:
1930 {
1931 int i;
1932 struct ubifs_nnode nnode;
1933
1934 node_len = c->nnode_sz;
1935 if (c->big_lpt)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001936 pr_err("LEB %d:%d, nnode num %d, ",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001937 lnum, offs, node_num);
1938 else
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001939 pr_err("LEB %d:%d, nnode, ",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001940 lnum, offs);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001941 err = ubifs_unpack_nnode(c, p, &nnode);
hujianyang5a957412014-06-11 10:40:10 +08001942 if (err) {
1943 pr_err("failed to unpack_node, error %d\n",
1944 err);
1945 break;
1946 }
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001947 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001948 pr_cont("%d:%d", nnode.nbranch[i].lnum,
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001949 nnode.nbranch[i].offs);
1950 if (i != UBIFS_LPT_FANOUT - 1)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001951 pr_cont(", ");
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001952 }
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001953 pr_cont("\n");
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001954 break;
1955 }
1956 case UBIFS_LPT_LTAB:
1957 node_len = c->ltab_sz;
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001958 pr_err("LEB %d:%d, ltab\n", lnum, offs);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001959 break;
1960 case UBIFS_LPT_LSAVE:
1961 node_len = c->lsave_sz;
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001962 pr_err("LEB %d:%d, lsave len\n", lnum, offs);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001963 break;
1964 default:
1965 ubifs_err("LPT node type %d not recognized", node_type);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001966 goto out;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001967 }
1968
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001969 p += node_len;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001970 len -= node_len;
1971 }
1972
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001973 pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001974out:
1975 vfree(buf);
1976 return;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001977}
1978
1979/**
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001980 * ubifs_dump_lpt_lebs - dump LPT lebs.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001981 * @c: UBIFS file-system description object
1982 *
1983 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1984 * locked.
1985 */
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001986void ubifs_dump_lpt_lebs(const struct ubifs_info *c)
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001987{
1988 int i;
1989
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001990 pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001991 for (i = 0; i < c->lpt_lebs; i++)
1992 dump_lpt_leb(c, i + c->lpt_first);
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001993 pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001994}
1995
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03001996/**
1997 * dbg_populate_lsave - debugging version of 'populate_lsave()'
1998 * @c: UBIFS file-system description object
1999 *
2000 * This is a debugging version for 'populate_lsave()' which populates lsave
2001 * with random LEBs instead of useful LEBs, which is good for test coverage.
2002 * Returns zero if lsave has not been populated (this debugging feature is
2003 * disabled) an non-zero if lsave has been populated.
2004 */
2005static int dbg_populate_lsave(struct ubifs_info *c)
2006{
2007 struct ubifs_lprops *lprops;
2008 struct ubifs_lpt_heap *heap;
2009 int i;
2010
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03002011 if (!dbg_is_chk_gen(c))
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002012 return 0;
Akinobu Mita3d251a52013-01-03 21:19:09 +09002013 if (prandom_u32() & 3)
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002014 return 0;
2015
2016 for (i = 0; i < c->lsave_cnt; i++)
2017 c->lsave[i] = c->main_first;
2018
2019 list_for_each_entry(lprops, &c->empty_list, list)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002020 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002021 list_for_each_entry(lprops, &c->freeable_list, list)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002022 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002023 list_for_each_entry(lprops, &c->frdi_idx_list, list)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002024 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002025
2026 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
2027 for (i = 0; i < heap->cnt; i++)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002028 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002029 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
2030 for (i = 0; i < heap->cnt; i++)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002031 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002032 heap = &c->lpt_heap[LPROPS_FREE - 1];
2033 for (i = 0; i < heap->cnt; i++)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002034 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002035
2036 return 1;
2037}