blob: 45d4e96a6bac0fe36f67b268ada5fea066627eee [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 }
307 done_ltab = 1;
308 c->ltab_lnum = lnum;
309 c->ltab_offs = offs;
310 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300311 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300312 }
313
314 alen = ALIGN(offs, c->min_io_size);
315 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
Adrian Hunter73944a62008-09-12 18:13:31 +0300316 dbg_chk_lpt_sz(c, 4, alen - offs);
317 err = dbg_chk_lpt_sz(c, 3, alen);
318 if (err)
319 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300320 return 0;
Adrian Hunter73944a62008-09-12 18:13:31 +0300321
322no_space:
Artem Bityutskiy79fda512012-08-27 13:34:09 +0300323 ubifs_err("LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
324 lnum, offs, len, done_ltab, done_lsave);
Artem Bityutskiyedf6be22012-05-16 19:15:56 +0300325 ubifs_dump_lpt_info(c);
326 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +0200327 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +0300328 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300329}
330
331/**
332 * realloc_lpt_leb - allocate an LPT LEB that is empty.
333 * @c: UBIFS file-system description object
334 * @lnum: LEB number is passed and returned here
335 *
336 * This function duplicates exactly the results of the function alloc_lpt_leb.
337 * It is used during end commit to reallocate the same LEB numbers that were
338 * allocated by alloc_lpt_leb during start commit.
339 *
340 * This function finds the next LEB that was allocated by the alloc_lpt_leb
341 * function starting from @lnum. If a LEB is found it is returned in @lnum and
342 * the function returns %0. Otherwise the function returns -ENOSPC.
343 * Note however, that LPT is designed never to run out of space.
344 */
345static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
346{
347 int i, n;
348
349 n = *lnum - c->lpt_first + 1;
350 for (i = n; i < c->lpt_lebs; i++)
351 if (c->ltab[i].cmt) {
352 c->ltab[i].cmt = 0;
353 *lnum = i + c->lpt_first;
354 return 0;
355 }
356
357 for (i = 0; i < n; i++)
358 if (c->ltab[i].cmt) {
359 c->ltab[i].cmt = 0;
360 *lnum = i + c->lpt_first;
361 return 0;
362 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300363 return -ENOSPC;
364}
365
366/**
367 * write_cnodes - write cnodes for commit.
368 * @c: UBIFS file-system description object
369 *
370 * This function returns %0 on success and a negative error code on failure.
371 */
372static int write_cnodes(struct ubifs_info *c)
373{
374 int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
375 struct ubifs_cnode *cnode;
376 void *buf = c->lpt_buf;
377
378 cnode = c->lpt_cnext;
379 if (!cnode)
380 return 0;
381 lnum = c->nhead_lnum;
382 offs = c->nhead_offs;
383 from = offs;
384 /* Ensure empty LEB is unmapped */
385 if (offs == 0) {
386 err = ubifs_leb_unmap(c, lnum);
387 if (err)
388 return err;
389 }
390 /* Try to place lsave and ltab nicely */
391 done_lsave = !c->big_lpt;
392 done_ltab = 0;
393 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
394 done_lsave = 1;
395 ubifs_pack_lsave(c, buf + offs, c->lsave);
396 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300397 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300398 }
399
400 if (offs + c->ltab_sz <= c->leb_size) {
401 done_ltab = 1;
402 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
403 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300404 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300405 }
406
407 /* Loop for each cnode */
408 do {
409 if (cnode->level)
410 len = c->nnode_sz;
411 else
412 len = c->pnode_sz;
413 while (offs + len > c->leb_size) {
414 wlen = offs - from;
415 if (wlen) {
416 alen = ALIGN(wlen, c->min_io_size);
417 memset(buf + offs, 0xff, alen - wlen);
418 err = ubifs_leb_write(c, lnum, buf + from, from,
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200419 alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300420 if (err)
421 return err;
422 }
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200423 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300424 err = realloc_lpt_leb(c, &lnum);
425 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300426 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200427 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300428 ubifs_assert(lnum >= c->lpt_first &&
429 lnum <= c->lpt_last);
430 err = ubifs_leb_unmap(c, lnum);
431 if (err)
432 return err;
433 /* Try to place lsave and ltab nicely */
434 if (!done_lsave) {
435 done_lsave = 1;
436 ubifs_pack_lsave(c, buf + offs, c->lsave);
437 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300438 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300439 continue;
440 }
441 if (!done_ltab) {
442 done_ltab = 1;
443 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
444 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300445 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300446 continue;
447 }
448 break;
449 }
450 if (cnode->level)
451 ubifs_pack_nnode(c, buf + offs,
452 (struct ubifs_nnode *)cnode);
453 else
454 ubifs_pack_pnode(c, buf + offs,
455 (struct ubifs_pnode *)cnode);
456 /*
457 * The reason for the barriers is the same as in case of TNC.
458 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
459 * 'dirty_cow_pnode()' are the functions for which this is
460 * important.
461 */
462 clear_bit(DIRTY_CNODE, &cnode->flags);
Peter Zijlstra4e857c52014-03-17 18:06:10 +0100463 smp_mb__before_atomic();
Artem Bityutskiy37662442011-05-30 14:51:20 +0300464 clear_bit(COW_CNODE, &cnode->flags);
Peter Zijlstra4e857c52014-03-17 18:06:10 +0100465 smp_mb__after_atomic();
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300466 offs += len;
Adrian Hunter73944a62008-09-12 18:13:31 +0300467 dbg_chk_lpt_sz(c, 1, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300468 cnode = cnode->cnext;
469 } while (cnode && cnode != c->lpt_cnext);
470
471 /* Make sure to place LPT's save table */
472 if (!done_lsave) {
473 if (offs + c->lsave_sz > c->leb_size) {
474 wlen = offs - from;
475 alen = ALIGN(wlen, c->min_io_size);
476 memset(buf + offs, 0xff, alen - wlen);
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200477 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300478 if (err)
479 return err;
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200480 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300481 err = realloc_lpt_leb(c, &lnum);
482 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300483 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200484 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300485 ubifs_assert(lnum >= c->lpt_first &&
486 lnum <= c->lpt_last);
487 err = ubifs_leb_unmap(c, lnum);
488 if (err)
489 return err;
490 }
491 done_lsave = 1;
492 ubifs_pack_lsave(c, buf + offs, c->lsave);
493 offs += c->lsave_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300494 dbg_chk_lpt_sz(c, 1, c->lsave_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300495 }
496
497 /* Make sure to place LPT's own lprops table */
498 if (!done_ltab) {
499 if (offs + c->ltab_sz > c->leb_size) {
500 wlen = offs - from;
501 alen = ALIGN(wlen, c->min_io_size);
502 memset(buf + offs, 0xff, alen - wlen);
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200503 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300504 if (err)
505 return err;
Adrian Hunter2bc275e2009-02-05 13:08:11 +0200506 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300507 err = realloc_lpt_leb(c, &lnum);
508 if (err)
Adrian Hunter73944a62008-09-12 18:13:31 +0300509 goto no_space;
Artem Bityutskiy0a6fb8d92009-03-14 16:35:27 +0200510 offs = from = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300511 ubifs_assert(lnum >= c->lpt_first &&
512 lnum <= c->lpt_last);
513 err = ubifs_leb_unmap(c, lnum);
514 if (err)
515 return err;
516 }
517 done_ltab = 1;
518 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
519 offs += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300520 dbg_chk_lpt_sz(c, 1, c->ltab_sz);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300521 }
522
523 /* Write remaining data in buffer */
524 wlen = offs - from;
525 alen = ALIGN(wlen, c->min_io_size);
526 memset(buf + offs, 0xff, alen - wlen);
Richard Weinbergerb36a2612012-05-14 17:55:51 +0200527 err = ubifs_leb_write(c, lnum, buf + from, from, alen);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300528 if (err)
529 return err;
Adrian Hunter73944a62008-09-12 18:13:31 +0300530
531 dbg_chk_lpt_sz(c, 4, alen - wlen);
532 err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));
533 if (err)
534 return err;
535
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300536 c->nhead_lnum = lnum;
537 c->nhead_offs = ALIGN(offs, c->min_io_size);
538
539 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
540 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
541 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
542 if (c->big_lpt)
543 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
Adrian Hunter73944a62008-09-12 18:13:31 +0300544
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300545 return 0;
Adrian Hunter73944a62008-09-12 18:13:31 +0300546
547no_space:
Artem Bityutskiy79fda512012-08-27 13:34:09 +0300548 ubifs_err("LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
549 lnum, offs, len, done_ltab, done_lsave);
Artem Bityutskiyedf6be22012-05-16 19:15:56 +0300550 ubifs_dump_lpt_info(c);
551 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +0200552 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +0300553 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300554}
555
556/**
Adrian Hunter4a29d202009-01-27 15:22:54 +0200557 * next_pnode_to_dirty - find next pnode to dirty.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300558 * @c: UBIFS file-system description object
559 * @pnode: pnode
560 *
Adrian Hunter4a29d202009-01-27 15:22:54 +0200561 * This function returns the next pnode to dirty or %NULL if there are no more
562 * pnodes. Note that pnodes that have never been written (lnum == 0) are
563 * skipped.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300564 */
Adrian Hunter4a29d202009-01-27 15:22:54 +0200565static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,
566 struct ubifs_pnode *pnode)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300567{
568 struct ubifs_nnode *nnode;
569 int iip;
570
571 /* Try to go right */
572 nnode = pnode->parent;
Adrian Hunter4a29d202009-01-27 15:22:54 +0200573 for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300574 if (nnode->nbranch[iip].lnum)
575 return ubifs_get_pnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300576 }
577
578 /* Go up while can't go right */
579 do {
580 iip = nnode->iip + 1;
581 nnode = nnode->parent;
582 if (!nnode)
583 return NULL;
Adrian Hunter4a29d202009-01-27 15:22:54 +0200584 for (; iip < UBIFS_LPT_FANOUT; iip++) {
585 if (nnode->nbranch[iip].lnum)
586 break;
587 }
Artem Bityutskiyc4361572011-03-25 15:27:40 +0200588 } while (iip >= UBIFS_LPT_FANOUT);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300589
590 /* Go right */
591 nnode = ubifs_get_nnode(c, nnode, iip);
592 if (IS_ERR(nnode))
593 return (void *)nnode;
594
595 /* Go down to level 1 */
596 while (nnode->level > 1) {
Adrian Hunter4a29d202009-01-27 15:22:54 +0200597 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {
598 if (nnode->nbranch[iip].lnum)
599 break;
600 }
601 if (iip >= UBIFS_LPT_FANOUT) {
602 /*
603 * Should not happen, but we need to keep going
604 * if it does.
605 */
606 iip = 0;
607 }
608 nnode = ubifs_get_nnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300609 if (IS_ERR(nnode))
610 return (void *)nnode;
611 }
612
Adrian Hunter4a29d202009-01-27 15:22:54 +0200613 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)
614 if (nnode->nbranch[iip].lnum)
615 break;
616 if (iip >= UBIFS_LPT_FANOUT)
617 /* Should not happen, but we need to keep going if it does */
618 iip = 0;
619 return ubifs_get_pnode(c, nnode, iip);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300620}
621
622/**
623 * pnode_lookup - lookup a pnode in the LPT.
624 * @c: UBIFS file-system description object
625 * @i: pnode number (0 to main_lebs - 1)
626 *
627 * This function returns a pointer to the pnode on success or a negative
628 * error code on failure.
629 */
630static struct ubifs_pnode *pnode_lookup(struct ubifs_info *c, int i)
631{
632 int err, h, iip, shft;
633 struct ubifs_nnode *nnode;
634
635 if (!c->nroot) {
636 err = ubifs_read_nnode(c, NULL, 0);
637 if (err)
638 return ERR_PTR(err);
639 }
640 i <<= UBIFS_LPT_FANOUT_SHIFT;
641 nnode = c->nroot;
642 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
643 for (h = 1; h < c->lpt_hght; h++) {
644 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
645 shft -= UBIFS_LPT_FANOUT_SHIFT;
646 nnode = ubifs_get_nnode(c, nnode, iip);
647 if (IS_ERR(nnode))
Julia Lawall6da51562010-05-22 12:00:21 +0200648 return ERR_CAST(nnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300649 }
650 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
651 return ubifs_get_pnode(c, nnode, iip);
652}
653
654/**
655 * add_pnode_dirt - add dirty space to LPT LEB properties.
656 * @c: UBIFS file-system description object
657 * @pnode: pnode for which to add dirt
658 */
659static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
660{
661 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
662 c->pnode_sz);
663}
664
665/**
666 * do_make_pnode_dirty - mark a pnode dirty.
667 * @c: UBIFS file-system description object
668 * @pnode: pnode to mark dirty
669 */
670static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
671{
672 /* Assumes cnext list is empty i.e. not called during commit */
673 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
674 struct ubifs_nnode *nnode;
675
676 c->dirty_pn_cnt += 1;
677 add_pnode_dirt(c, pnode);
678 /* Mark parent and ancestors dirty too */
679 nnode = pnode->parent;
680 while (nnode) {
681 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
682 c->dirty_nn_cnt += 1;
683 ubifs_add_nnode_dirt(c, nnode);
684 nnode = nnode->parent;
685 } else
686 break;
687 }
688 }
689}
690
691/**
692 * make_tree_dirty - mark the entire LEB properties tree dirty.
693 * @c: UBIFS file-system description object
694 *
695 * This function is used by the "small" LPT model to cause the entire LEB
696 * properties tree to be written. The "small" LPT model does not use LPT
697 * garbage collection because it is more efficient to write the entire tree
698 * (because it is small).
699 *
700 * This function returns %0 on success and a negative error code on failure.
701 */
702static int make_tree_dirty(struct ubifs_info *c)
703{
704 struct ubifs_pnode *pnode;
705
706 pnode = pnode_lookup(c, 0);
Vasiliy Kulikov8c893a52010-09-05 22:33:04 +0400707 if (IS_ERR(pnode))
708 return PTR_ERR(pnode);
709
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300710 while (pnode) {
711 do_make_pnode_dirty(c, pnode);
Adrian Hunter4a29d202009-01-27 15:22:54 +0200712 pnode = next_pnode_to_dirty(c, pnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300713 if (IS_ERR(pnode))
714 return PTR_ERR(pnode);
715 }
716 return 0;
717}
718
719/**
720 * need_write_all - determine if the LPT area is running out of free space.
721 * @c: UBIFS file-system description object
722 *
723 * This function returns %1 if the LPT area is running out of free space and %0
724 * if it is not.
725 */
726static int need_write_all(struct ubifs_info *c)
727{
728 long long free = 0;
729 int i;
730
731 for (i = 0; i < c->lpt_lebs; i++) {
732 if (i + c->lpt_first == c->nhead_lnum)
733 free += c->leb_size - c->nhead_offs;
734 else if (c->ltab[i].free == c->leb_size)
735 free += c->leb_size;
736 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
737 free += c->leb_size;
738 }
739 /* Less than twice the size left */
740 if (free <= c->lpt_sz * 2)
741 return 1;
742 return 0;
743}
744
745/**
746 * lpt_tgc_start - start 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 during start commit to mark LPT LEBs for trivial GC.
752 */
753static void lpt_tgc_start(struct ubifs_info *c)
754{
755 int i;
756
757 for (i = 0; i < c->lpt_lebs; i++) {
758 if (i + c->lpt_first == c->nhead_lnum)
759 continue;
760 if (c->ltab[i].dirty > 0 &&
761 c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
762 c->ltab[i].tgc = 1;
763 c->ltab[i].free = c->leb_size;
764 c->ltab[i].dirty = 0;
765 dbg_lp("LEB %d", i + c->lpt_first);
766 }
767 }
768}
769
770/**
771 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
772 * @c: UBIFS file-system description object
773 *
774 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
775 * free space and so may be reused as soon as the next commit is completed.
776 * This function is called after the commit is completed (master node has been
Artem Bityutskiy80736d42008-12-30 17:44:02 +0200777 * written) and un-maps LPT LEBs that were marked for trivial GC.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300778 */
779static int lpt_tgc_end(struct ubifs_info *c)
780{
781 int i, err;
782
783 for (i = 0; i < c->lpt_lebs; i++)
784 if (c->ltab[i].tgc) {
785 err = ubifs_leb_unmap(c, i + c->lpt_first);
786 if (err)
787 return err;
788 c->ltab[i].tgc = 0;
789 dbg_lp("LEB %d", i + c->lpt_first);
790 }
791 return 0;
792}
793
794/**
795 * populate_lsave - fill the lsave array with important LEB numbers.
796 * @c: the UBIFS file-system description object
797 *
798 * This function is only called for the "big" model. It records a small number
799 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
800 * most important to least important): empty, freeable, freeable index, dirty
801 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
802 * their pnodes into memory. That will stop us from having to scan the LPT
803 * straight away. For the "small" model we assume that scanning the LPT is no
804 * big deal.
805 */
806static void populate_lsave(struct ubifs_info *c)
807{
808 struct ubifs_lprops *lprops;
809 struct ubifs_lpt_heap *heap;
810 int i, cnt = 0;
811
812 ubifs_assert(c->big_lpt);
813 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
814 c->lpt_drty_flgs |= LSAVE_DIRTY;
815 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
816 }
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +0300817
818 if (dbg_populate_lsave(c))
819 return;
820
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300821 list_for_each_entry(lprops, &c->empty_list, list) {
822 c->lsave[cnt++] = lprops->lnum;
823 if (cnt >= c->lsave_cnt)
824 return;
825 }
826 list_for_each_entry(lprops, &c->freeable_list, list) {
827 c->lsave[cnt++] = lprops->lnum;
828 if (cnt >= c->lsave_cnt)
829 return;
830 }
831 list_for_each_entry(lprops, &c->frdi_idx_list, list) {
832 c->lsave[cnt++] = lprops->lnum;
833 if (cnt >= c->lsave_cnt)
834 return;
835 }
836 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
837 for (i = 0; i < heap->cnt; i++) {
838 c->lsave[cnt++] = heap->arr[i]->lnum;
839 if (cnt >= c->lsave_cnt)
840 return;
841 }
842 heap = &c->lpt_heap[LPROPS_DIRTY - 1];
843 for (i = 0; i < heap->cnt; i++) {
844 c->lsave[cnt++] = heap->arr[i]->lnum;
845 if (cnt >= c->lsave_cnt)
846 return;
847 }
848 heap = &c->lpt_heap[LPROPS_FREE - 1];
849 for (i = 0; i < heap->cnt; i++) {
850 c->lsave[cnt++] = heap->arr[i]->lnum;
851 if (cnt >= c->lsave_cnt)
852 return;
853 }
854 /* Fill it up completely */
855 while (cnt < c->lsave_cnt)
856 c->lsave[cnt++] = c->main_first;
857}
858
859/**
860 * nnode_lookup - lookup a nnode in the LPT.
861 * @c: UBIFS file-system description object
862 * @i: nnode number
863 *
864 * This function returns a pointer to the nnode on success or a negative
865 * error code on failure.
866 */
867static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
868{
869 int err, iip;
870 struct ubifs_nnode *nnode;
871
872 if (!c->nroot) {
873 err = ubifs_read_nnode(c, NULL, 0);
874 if (err)
875 return ERR_PTR(err);
876 }
877 nnode = c->nroot;
878 while (1) {
879 iip = i & (UBIFS_LPT_FANOUT - 1);
880 i >>= UBIFS_LPT_FANOUT_SHIFT;
881 if (!i)
882 break;
883 nnode = ubifs_get_nnode(c, nnode, iip);
884 if (IS_ERR(nnode))
885 return nnode;
886 }
887 return nnode;
888}
889
890/**
891 * make_nnode_dirty - find a nnode and, if found, make it dirty.
892 * @c: UBIFS file-system description object
893 * @node_num: nnode number of nnode to make dirty
894 * @lnum: LEB number where nnode was written
895 * @offs: offset where nnode was written
896 *
897 * This function is used by LPT garbage collection. LPT garbage collection is
898 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
899 * simply involves marking all the nodes in the LEB being garbage-collected as
900 * dirty. The dirty nodes are written next commit, after which the LEB is free
901 * to be reused.
902 *
903 * This function returns %0 on success and a negative error code on failure.
904 */
905static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
906 int offs)
907{
908 struct ubifs_nnode *nnode;
909
910 nnode = nnode_lookup(c, node_num);
911 if (IS_ERR(nnode))
912 return PTR_ERR(nnode);
913 if (nnode->parent) {
914 struct ubifs_nbranch *branch;
915
916 branch = &nnode->parent->nbranch[nnode->iip];
917 if (branch->lnum != lnum || branch->offs != offs)
918 return 0; /* nnode is obsolete */
919 } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
920 return 0; /* nnode is obsolete */
921 /* Assumes cnext list is empty i.e. not called during commit */
922 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
923 c->dirty_nn_cnt += 1;
924 ubifs_add_nnode_dirt(c, nnode);
925 /* Mark parent and ancestors dirty too */
926 nnode = nnode->parent;
927 while (nnode) {
928 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
929 c->dirty_nn_cnt += 1;
930 ubifs_add_nnode_dirt(c, nnode);
931 nnode = nnode->parent;
932 } else
933 break;
934 }
935 }
936 return 0;
937}
938
939/**
940 * make_pnode_dirty - find a pnode and, if found, make it dirty.
941 * @c: UBIFS file-system description object
942 * @node_num: pnode number of pnode to make dirty
943 * @lnum: LEB number where pnode was written
944 * @offs: offset where pnode was written
945 *
946 * This function is used by LPT garbage collection. LPT garbage collection is
947 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
948 * simply involves marking all the nodes in the LEB being garbage-collected as
949 * dirty. The dirty nodes are written next commit, after which the LEB is free
950 * to be reused.
951 *
952 * This function returns %0 on success and a negative error code on failure.
953 */
954static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
955 int offs)
956{
957 struct ubifs_pnode *pnode;
958 struct ubifs_nbranch *branch;
959
960 pnode = pnode_lookup(c, node_num);
961 if (IS_ERR(pnode))
962 return PTR_ERR(pnode);
963 branch = &pnode->parent->nbranch[pnode->iip];
964 if (branch->lnum != lnum || branch->offs != offs)
965 return 0;
966 do_make_pnode_dirty(c, pnode);
967 return 0;
968}
969
970/**
971 * make_ltab_dirty - make ltab node dirty.
972 * @c: UBIFS file-system description object
973 * @lnum: LEB number where ltab was written
974 * @offs: offset where ltab was written
975 *
976 * This function is used by LPT garbage collection. LPT garbage collection is
977 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
978 * simply involves marking all the nodes in the LEB being garbage-collected as
979 * dirty. The dirty nodes are written next commit, after which the LEB is free
980 * to be reused.
981 *
982 * This function returns %0 on success and a negative error code on failure.
983 */
984static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
985{
986 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
987 return 0; /* This ltab node is obsolete */
988 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
989 c->lpt_drty_flgs |= LTAB_DIRTY;
990 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
991 }
992 return 0;
993}
994
995/**
996 * make_lsave_dirty - make lsave node dirty.
997 * @c: UBIFS file-system description object
998 * @lnum: LEB number where lsave was written
999 * @offs: offset where lsave was written
1000 *
1001 * This function is used by LPT garbage collection. LPT garbage collection is
1002 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1003 * simply involves marking all the nodes in the LEB being garbage-collected as
1004 * dirty. The dirty nodes are written next commit, after which the LEB is free
1005 * to be reused.
1006 *
1007 * This function returns %0 on success and a negative error code on failure.
1008 */
1009static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1010{
1011 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1012 return 0; /* This lsave node is obsolete */
1013 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
1014 c->lpt_drty_flgs |= LSAVE_DIRTY;
1015 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
1016 }
1017 return 0;
1018}
1019
1020/**
1021 * make_node_dirty - make node dirty.
1022 * @c: UBIFS file-system description object
1023 * @node_type: LPT node type
1024 * @node_num: node number
1025 * @lnum: LEB number where node was written
1026 * @offs: offset where node was written
1027 *
1028 * This function is used by LPT garbage collection. LPT garbage collection is
1029 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1030 * simply involves marking all the nodes in the LEB being garbage-collected as
1031 * dirty. The dirty nodes are written next commit, after which the LEB is free
1032 * to be reused.
1033 *
1034 * This function returns %0 on success and a negative error code on failure.
1035 */
1036static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
1037 int lnum, int offs)
1038{
1039 switch (node_type) {
1040 case UBIFS_LPT_NNODE:
1041 return make_nnode_dirty(c, node_num, lnum, offs);
1042 case UBIFS_LPT_PNODE:
1043 return make_pnode_dirty(c, node_num, lnum, offs);
1044 case UBIFS_LPT_LTAB:
1045 return make_ltab_dirty(c, lnum, offs);
1046 case UBIFS_LPT_LSAVE:
1047 return make_lsave_dirty(c, lnum, offs);
1048 }
1049 return -EINVAL;
1050}
1051
1052/**
1053 * get_lpt_node_len - return the length of a node based on its type.
1054 * @c: UBIFS file-system description object
1055 * @node_type: LPT node type
1056 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001057static int get_lpt_node_len(const struct ubifs_info *c, int node_type)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001058{
1059 switch (node_type) {
1060 case UBIFS_LPT_NNODE:
1061 return c->nnode_sz;
1062 case UBIFS_LPT_PNODE:
1063 return c->pnode_sz;
1064 case UBIFS_LPT_LTAB:
1065 return c->ltab_sz;
1066 case UBIFS_LPT_LSAVE:
1067 return c->lsave_sz;
1068 }
1069 return 0;
1070}
1071
1072/**
1073 * get_pad_len - return the length of padding in a buffer.
1074 * @c: UBIFS file-system description object
1075 * @buf: buffer
1076 * @len: length of buffer
1077 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001078static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001079{
1080 int offs, pad_len;
1081
1082 if (c->min_io_size == 1)
1083 return 0;
1084 offs = c->leb_size - len;
1085 pad_len = ALIGN(offs, c->min_io_size) - offs;
1086 return pad_len;
1087}
1088
1089/**
1090 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1091 * @c: UBIFS file-system description object
1092 * @buf: buffer
1093 * @node_num: node number is returned here
1094 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001095static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,
1096 int *node_num)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001097{
1098 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1099 int pos = 0, node_type;
1100
1101 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1102 *node_num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1103 return node_type;
1104}
1105
1106/**
1107 * is_a_node - determine if a buffer contains a node.
1108 * @c: UBIFS file-system description object
1109 * @buf: buffer
1110 * @len: length of buffer
1111 *
1112 * This function returns %1 if the buffer contains a node or %0 if it does not.
1113 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001114static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001115{
1116 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1117 int pos = 0, node_type, node_len;
1118 uint16_t crc, calc_crc;
1119
Adrian Hunterbe2f6bd2008-09-26 12:52:21 +03001120 if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1121 return 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001122 node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1123 if (node_type == UBIFS_LPT_NOT_A_NODE)
1124 return 0;
1125 node_len = get_lpt_node_len(c, node_type);
1126 if (!node_len || node_len > len)
1127 return 0;
1128 pos = 0;
1129 addr = buf;
1130 crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
1131 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1132 node_len - UBIFS_LPT_CRC_BYTES);
1133 if (crc != calc_crc)
1134 return 0;
1135 return 1;
1136}
1137
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001138/**
1139 * lpt_gc_lnum - garbage collect a LPT LEB.
1140 * @c: UBIFS file-system description object
1141 * @lnum: LEB number to garbage collect
1142 *
1143 * LPT garbage collection is used only for the "big" LPT model
1144 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1145 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1146 * next commit, after which the LEB is free to be reused.
1147 *
1148 * This function returns %0 on success and a negative error code on failure.
1149 */
1150static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1151{
1152 int err, len = c->leb_size, node_type, node_num, node_len, offs;
1153 void *buf = c->lpt_buf;
1154
1155 dbg_lp("LEB %d", lnum);
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001156
1157 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1158 if (err)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001159 return err;
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001160
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001161 while (1) {
1162 if (!is_a_node(c, buf, len)) {
1163 int pad_len;
1164
1165 pad_len = get_pad_len(c, buf, len);
1166 if (pad_len) {
1167 buf += pad_len;
1168 len -= pad_len;
1169 continue;
1170 }
1171 return 0;
1172 }
1173 node_type = get_lpt_node_type(c, buf, &node_num);
1174 node_len = get_lpt_node_len(c, node_type);
1175 offs = c->leb_size - len;
1176 ubifs_assert(node_len != 0);
1177 mutex_lock(&c->lp_mutex);
1178 err = make_node_dirty(c, node_type, node_num, lnum, offs);
1179 mutex_unlock(&c->lp_mutex);
1180 if (err)
1181 return err;
1182 buf += node_len;
1183 len -= node_len;
1184 }
1185 return 0;
1186}
1187
1188/**
1189 * lpt_gc - LPT garbage collection.
1190 * @c: UBIFS file-system description object
1191 *
1192 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1193 * Returns %0 on success and a negative error code on failure.
1194 */
1195static int lpt_gc(struct ubifs_info *c)
1196{
1197 int i, lnum = -1, dirty = 0;
1198
1199 mutex_lock(&c->lp_mutex);
1200 for (i = 0; i < c->lpt_lebs; i++) {
1201 ubifs_assert(!c->ltab[i].tgc);
1202 if (i + c->lpt_first == c->nhead_lnum ||
1203 c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1204 continue;
1205 if (c->ltab[i].dirty > dirty) {
1206 dirty = c->ltab[i].dirty;
1207 lnum = i + c->lpt_first;
1208 }
1209 }
1210 mutex_unlock(&c->lp_mutex);
1211 if (lnum == -1)
1212 return -ENOSPC;
1213 return lpt_gc_lnum(c, lnum);
1214}
1215
1216/**
1217 * ubifs_lpt_start_commit - UBIFS commit starts.
1218 * @c: the UBIFS file-system description object
1219 *
1220 * This function has to be called when UBIFS starts the commit operation.
1221 * This function "freezes" all currently dirty LEB properties and does not
1222 * change them anymore. Further changes are saved and tracked separately
1223 * because they are not part of this commit. This function returns zero in case
1224 * of success and a negative error code in case of failure.
1225 */
1226int ubifs_lpt_start_commit(struct ubifs_info *c)
1227{
1228 int err, cnt;
1229
1230 dbg_lp("");
1231
1232 mutex_lock(&c->lp_mutex);
Adrian Hunter73944a62008-09-12 18:13:31 +03001233 err = dbg_chk_lpt_free_spc(c);
1234 if (err)
1235 goto out;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001236 err = dbg_check_ltab(c);
1237 if (err)
1238 goto out;
1239
1240 if (c->check_lpt_free) {
1241 /*
1242 * We ensure there is enough free space in
1243 * ubifs_lpt_post_commit() by marking nodes dirty. That
1244 * information is lost when we unmount, so we also need
1245 * to check free space once after mounting also.
1246 */
1247 c->check_lpt_free = 0;
1248 while (need_write_all(c)) {
1249 mutex_unlock(&c->lp_mutex);
1250 err = lpt_gc(c);
1251 if (err)
1252 return err;
1253 mutex_lock(&c->lp_mutex);
1254 }
1255 }
1256
1257 lpt_tgc_start(c);
1258
1259 if (!c->dirty_pn_cnt) {
1260 dbg_cmt("no cnodes to commit");
1261 err = 0;
1262 goto out;
1263 }
1264
1265 if (!c->big_lpt && need_write_all(c)) {
1266 /* If needed, write everything */
1267 err = make_tree_dirty(c);
1268 if (err)
1269 goto out;
1270 lpt_tgc_start(c);
1271 }
1272
1273 if (c->big_lpt)
1274 populate_lsave(c);
1275
1276 cnt = get_cnodes_to_commit(c);
1277 ubifs_assert(cnt != 0);
1278
1279 err = layout_cnodes(c);
1280 if (err)
1281 goto out;
1282
1283 /* Copy the LPT's own lprops for end commit to write */
1284 memcpy(c->ltab_cmt, c->ltab,
1285 sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1286 c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1287
1288out:
1289 mutex_unlock(&c->lp_mutex);
1290 return err;
1291}
1292
1293/**
1294 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1295 * @c: UBIFS file-system description object
1296 */
1297static void free_obsolete_cnodes(struct ubifs_info *c)
1298{
1299 struct ubifs_cnode *cnode, *cnext;
1300
1301 cnext = c->lpt_cnext;
1302 if (!cnext)
1303 return;
1304 do {
1305 cnode = cnext;
1306 cnext = cnode->cnext;
1307 if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1308 kfree(cnode);
1309 else
1310 cnode->cnext = NULL;
1311 } while (cnext != c->lpt_cnext);
1312 c->lpt_cnext = NULL;
1313}
1314
1315/**
1316 * ubifs_lpt_end_commit - finish the commit operation.
1317 * @c: the UBIFS file-system description object
1318 *
1319 * This function has to be called when the commit operation finishes. It
1320 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1321 * the media. Returns zero in case of success and a negative error code in case
1322 * of failure.
1323 */
1324int ubifs_lpt_end_commit(struct ubifs_info *c)
1325{
1326 int err;
1327
1328 dbg_lp("");
1329
1330 if (!c->lpt_cnext)
1331 return 0;
1332
1333 err = write_cnodes(c);
1334 if (err)
1335 return err;
1336
1337 mutex_lock(&c->lp_mutex);
1338 free_obsolete_cnodes(c);
1339 mutex_unlock(&c->lp_mutex);
1340
1341 return 0;
1342}
1343
1344/**
1345 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1346 * @c: UBIFS file-system description object
1347 *
1348 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1349 * commit for the "big" LPT model.
1350 */
1351int ubifs_lpt_post_commit(struct ubifs_info *c)
1352{
1353 int err;
1354
1355 mutex_lock(&c->lp_mutex);
1356 err = lpt_tgc_end(c);
1357 if (err)
1358 goto out;
1359 if (c->big_lpt)
1360 while (need_write_all(c)) {
1361 mutex_unlock(&c->lp_mutex);
1362 err = lpt_gc(c);
1363 if (err)
1364 return err;
1365 mutex_lock(&c->lp_mutex);
1366 }
1367out:
1368 mutex_unlock(&c->lp_mutex);
1369 return err;
1370}
1371
1372/**
1373 * first_nnode - find the first nnode in memory.
1374 * @c: UBIFS file-system description object
1375 * @hght: height of tree where nnode found is returned here
1376 *
1377 * This function returns a pointer to the nnode found or %NULL if no nnode is
1378 * found. This function is a helper to 'ubifs_lpt_free()'.
1379 */
1380static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1381{
1382 struct ubifs_nnode *nnode;
1383 int h, i, found;
1384
1385 nnode = c->nroot;
1386 *hght = 0;
1387 if (!nnode)
1388 return NULL;
1389 for (h = 1; h < c->lpt_hght; h++) {
1390 found = 0;
1391 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1392 if (nnode->nbranch[i].nnode) {
1393 found = 1;
1394 nnode = nnode->nbranch[i].nnode;
1395 *hght = h;
1396 break;
1397 }
1398 }
1399 if (!found)
1400 break;
1401 }
1402 return nnode;
1403}
1404
1405/**
1406 * next_nnode - find the next nnode in memory.
1407 * @c: UBIFS file-system description object
1408 * @nnode: nnode from which to start.
1409 * @hght: height of tree where nnode is, is passed and returned here
1410 *
1411 * This function returns a pointer to the nnode found or %NULL if no nnode is
1412 * found. This function is a helper to 'ubifs_lpt_free()'.
1413 */
1414static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1415 struct ubifs_nnode *nnode, int *hght)
1416{
1417 struct ubifs_nnode *parent;
1418 int iip, h, i, found;
1419
1420 parent = nnode->parent;
1421 if (!parent)
1422 return NULL;
1423 if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1424 *hght -= 1;
1425 return parent;
1426 }
1427 for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1428 nnode = parent->nbranch[iip].nnode;
1429 if (nnode)
1430 break;
1431 }
1432 if (!nnode) {
1433 *hght -= 1;
1434 return parent;
1435 }
1436 for (h = *hght + 1; h < c->lpt_hght; h++) {
1437 found = 0;
1438 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1439 if (nnode->nbranch[i].nnode) {
1440 found = 1;
1441 nnode = nnode->nbranch[i].nnode;
1442 *hght = h;
1443 break;
1444 }
1445 }
1446 if (!found)
1447 break;
1448 }
1449 return nnode;
1450}
1451
1452/**
1453 * ubifs_lpt_free - free resources owned by the LPT.
1454 * @c: UBIFS file-system description object
1455 * @wr_only: free only resources used for writing
1456 */
1457void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1458{
1459 struct ubifs_nnode *nnode;
1460 int i, hght;
1461
1462 /* Free write-only things first */
1463
1464 free_obsolete_cnodes(c); /* Leftover from a failed commit */
1465
1466 vfree(c->ltab_cmt);
1467 c->ltab_cmt = NULL;
1468 vfree(c->lpt_buf);
1469 c->lpt_buf = NULL;
1470 kfree(c->lsave);
1471 c->lsave = NULL;
1472
1473 if (wr_only)
1474 return;
1475
1476 /* Now free the rest */
1477
1478 nnode = first_nnode(c, &hght);
1479 while (nnode) {
1480 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1481 kfree(nnode->nbranch[i].nnode);
1482 nnode = next_nnode(c, nnode, &hght);
1483 }
1484 for (i = 0; i < LPROPS_HEAP_CNT; i++)
1485 kfree(c->lpt_heap[i].arr);
1486 kfree(c->dirty_idx.arr);
1487 kfree(c->nroot);
1488 vfree(c->ltab);
1489 kfree(c->lpt_nod_buf);
1490}
1491
Artem Bityutskiyf70b7e52012-05-16 19:53:46 +03001492/*
1493 * Everything below is related to debugging.
1494 */
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001495
1496/**
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001497 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001498 * @buf: buffer
1499 * @len: buffer length
1500 */
1501static int dbg_is_all_ff(uint8_t *buf, int len)
1502{
1503 int i;
1504
1505 for (i = 0; i < len; i++)
1506 if (buf[i] != 0xff)
1507 return 0;
1508 return 1;
1509}
1510
1511/**
1512 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1513 * @c: the UBIFS file-system description object
1514 * @lnum: LEB number where nnode was written
1515 * @offs: offset where nnode was written
1516 */
1517static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1518{
1519 struct ubifs_nnode *nnode;
1520 int hght;
1521
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001522 /* Entire tree is in memory so first_nnode / next_nnode are OK */
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001523 nnode = first_nnode(c, &hght);
1524 for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1525 struct ubifs_nbranch *branch;
1526
1527 cond_resched();
1528 if (nnode->parent) {
1529 branch = &nnode->parent->nbranch[nnode->iip];
1530 if (branch->lnum != lnum || branch->offs != offs)
1531 continue;
1532 if (test_bit(DIRTY_CNODE, &nnode->flags))
1533 return 1;
1534 return 0;
1535 } else {
1536 if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1537 continue;
1538 if (test_bit(DIRTY_CNODE, &nnode->flags))
1539 return 1;
1540 return 0;
1541 }
1542 }
1543 return 1;
1544}
1545
1546/**
1547 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1548 * @c: the UBIFS file-system description object
1549 * @lnum: LEB number where pnode was written
1550 * @offs: offset where pnode was written
1551 */
1552static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1553{
1554 int i, cnt;
1555
1556 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1557 for (i = 0; i < cnt; i++) {
1558 struct ubifs_pnode *pnode;
1559 struct ubifs_nbranch *branch;
1560
1561 cond_resched();
1562 pnode = pnode_lookup(c, i);
1563 if (IS_ERR(pnode))
1564 return PTR_ERR(pnode);
1565 branch = &pnode->parent->nbranch[pnode->iip];
1566 if (branch->lnum != lnum || branch->offs != offs)
1567 continue;
1568 if (test_bit(DIRTY_CNODE, &pnode->flags))
1569 return 1;
1570 return 0;
1571 }
1572 return 1;
1573}
1574
1575/**
1576 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1577 * @c: the UBIFS file-system description object
1578 * @lnum: LEB number where ltab node was written
1579 * @offs: offset where ltab node was written
1580 */
1581static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1582{
1583 if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1584 return 1;
1585 return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1586}
1587
1588/**
1589 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1590 * @c: the UBIFS file-system description object
1591 * @lnum: LEB number where lsave node was written
1592 * @offs: offset where lsave node was written
1593 */
1594static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1595{
1596 if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1597 return 1;
1598 return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1599}
1600
1601/**
1602 * dbg_is_node_dirty - determine if a node is dirty.
1603 * @c: the UBIFS file-system description object
1604 * @node_type: node type
1605 * @lnum: LEB number where node was written
1606 * @offs: offset where node was written
1607 */
1608static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1609 int offs)
1610{
1611 switch (node_type) {
1612 case UBIFS_LPT_NNODE:
1613 return dbg_is_nnode_dirty(c, lnum, offs);
1614 case UBIFS_LPT_PNODE:
1615 return dbg_is_pnode_dirty(c, lnum, offs);
1616 case UBIFS_LPT_LTAB:
1617 return dbg_is_ltab_dirty(c, lnum, offs);
1618 case UBIFS_LPT_LSAVE:
1619 return dbg_is_lsave_dirty(c, lnum, offs);
1620 }
1621 return 1;
1622}
1623
1624/**
1625 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1626 * @c: the UBIFS file-system description object
1627 * @lnum: LEB number where node was written
1628 * @offs: offset where node was written
1629 *
1630 * This function returns %0 on success and a negative error code on failure.
1631 */
1632static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1633{
1634 int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1635 int ret;
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001636 void *buf, *p;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001637
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001638 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001639 return 0;
1640
Artem Bityutskiyfc5e58c2011-03-24 16:14:26 +02001641 buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001642 if (!buf) {
1643 ubifs_err("cannot allocate memory for ltab checking");
1644 return 0;
1645 }
1646
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001647 dbg_lp("LEB %d", lnum);
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001648
1649 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1650 if (err)
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001651 goto out;
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001652
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001653 while (1) {
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001654 if (!is_a_node(c, p, len)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001655 int i, pad_len;
1656
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001657 pad_len = get_pad_len(c, p, len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001658 if (pad_len) {
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001659 p += pad_len;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001660 len -= pad_len;
1661 dirty += pad_len;
1662 continue;
1663 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001664 if (!dbg_is_all_ff(p, len)) {
Artem Bityutskiy3668b702012-08-27 16:56:58 +03001665 ubifs_err("invalid empty space in LEB %d at %d",
1666 lnum, c->leb_size - len);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001667 err = -EINVAL;
1668 }
1669 i = lnum - c->lpt_first;
1670 if (len != c->ltab[i].free) {
Artem Bityutskiy3668b702012-08-27 16:56:58 +03001671 ubifs_err("invalid free space in LEB %d (free %d, expected %d)",
1672 lnum, len, c->ltab[i].free);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001673 err = -EINVAL;
1674 }
1675 if (dirty != c->ltab[i].dirty) {
Artem Bityutskiy3668b702012-08-27 16:56:58 +03001676 ubifs_err("invalid dirty space in LEB %d (dirty %d, expected %d)",
1677 lnum, dirty, c->ltab[i].dirty);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001678 err = -EINVAL;
1679 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001680 goto out;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001681 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001682 node_type = get_lpt_node_type(c, p, &node_num);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001683 node_len = get_lpt_node_len(c, node_type);
1684 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1685 if (ret == 1)
1686 dirty += node_len;
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001687 p += node_len;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001688 len -= node_len;
1689 }
Artem Bityutskiy6fb324a2011-03-11 15:56:38 +02001690
1691 err = 0;
1692out:
1693 vfree(buf);
1694 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001695}
1696
1697/**
1698 * dbg_check_ltab - check the free and dirty space in the ltab.
1699 * @c: the UBIFS file-system description object
1700 *
1701 * This function returns %0 on success and a negative error code on failure.
1702 */
1703int dbg_check_ltab(struct ubifs_info *c)
1704{
1705 int lnum, err, i, cnt;
1706
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001707 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001708 return 0;
1709
1710 /* Bring the entire tree into memory */
1711 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1712 for (i = 0; i < cnt; i++) {
1713 struct ubifs_pnode *pnode;
1714
1715 pnode = pnode_lookup(c, i);
1716 if (IS_ERR(pnode))
1717 return PTR_ERR(pnode);
1718 cond_resched();
1719 }
1720
1721 /* Check nodes */
1722 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1723 if (err)
1724 return err;
1725
1726 /* Check each LEB */
1727 for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1728 err = dbg_check_ltab_lnum(c, lnum);
1729 if (err) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001730 ubifs_err("failed at LEB %d", lnum);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001731 return err;
1732 }
1733 }
1734
1735 dbg_lp("succeeded");
1736 return 0;
1737}
1738
Adrian Hunter73944a62008-09-12 18:13:31 +03001739/**
1740 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1741 * @c: the UBIFS file-system description object
1742 *
1743 * This function returns %0 on success and a negative error code on failure.
1744 */
1745int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1746{
1747 long long free = 0;
1748 int i;
1749
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001750 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001751 return 0;
1752
Adrian Hunter73944a62008-09-12 18:13:31 +03001753 for (i = 0; i < c->lpt_lebs; i++) {
1754 if (c->ltab[i].tgc || c->ltab[i].cmt)
1755 continue;
1756 if (i + c->lpt_first == c->nhead_lnum)
1757 free += c->leb_size - c->nhead_offs;
1758 else if (c->ltab[i].free == c->leb_size)
1759 free += c->leb_size;
1760 }
1761 if (free < c->lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001762 ubifs_err("LPT space error: free %lld lpt_sz %lld",
1763 free, c->lpt_sz);
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001764 ubifs_dump_lpt_info(c);
1765 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001766 dump_stack();
Adrian Hunter73944a62008-09-12 18:13:31 +03001767 return -EINVAL;
1768 }
1769 return 0;
1770}
1771
1772/**
1773 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1774 * @c: the UBIFS file-system description object
Adrian Hunter2bc275e2009-02-05 13:08:11 +02001775 * @action: what to do
Adrian Hunter73944a62008-09-12 18:13:31 +03001776 * @len: length written
1777 *
1778 * This function returns %0 on success and a negative error code on failure.
Adrian Hunter2bc275e2009-02-05 13:08:11 +02001779 * The @action argument may be one of:
1780 * o %0 - LPT debugging checking starts, initialize debugging variables;
1781 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1782 * o %2 - switched to a different LEB and wasted @len bytes;
1783 * o %3 - check that we've written the right number of bytes.
1784 * o %4 - wasted @len bytes;
Adrian Hunter73944a62008-09-12 18:13:31 +03001785 */
1786int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1787{
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001788 struct ubifs_debug_info *d = c->dbg;
Adrian Hunter73944a62008-09-12 18:13:31 +03001789 long long chk_lpt_sz, lpt_sz;
1790 int err = 0;
1791
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03001792 if (!dbg_is_chk_lprops(c))
Artem Bityutskiy45e12d92008-10-31 11:42:18 +02001793 return 0;
1794
Adrian Hunter73944a62008-09-12 18:13:31 +03001795 switch (action) {
1796 case 0:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001797 d->chk_lpt_sz = 0;
1798 d->chk_lpt_sz2 = 0;
1799 d->chk_lpt_lebs = 0;
1800 d->chk_lpt_wastage = 0;
Adrian Hunter73944a62008-09-12 18:13:31 +03001801 if (c->dirty_pn_cnt > c->pnode_cnt) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001802 ubifs_err("dirty pnodes %d exceed max %d",
1803 c->dirty_pn_cnt, c->pnode_cnt);
Adrian Hunter73944a62008-09-12 18:13:31 +03001804 err = -EINVAL;
1805 }
1806 if (c->dirty_nn_cnt > c->nnode_cnt) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001807 ubifs_err("dirty nnodes %d exceed max %d",
1808 c->dirty_nn_cnt, c->nnode_cnt);
Adrian Hunter73944a62008-09-12 18:13:31 +03001809 err = -EINVAL;
1810 }
1811 return err;
1812 case 1:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001813 d->chk_lpt_sz += len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001814 return 0;
1815 case 2:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001816 d->chk_lpt_sz += len;
1817 d->chk_lpt_wastage += len;
1818 d->chk_lpt_lebs += 1;
Adrian Hunter73944a62008-09-12 18:13:31 +03001819 return 0;
1820 case 3:
1821 chk_lpt_sz = c->leb_size;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001822 chk_lpt_sz *= d->chk_lpt_lebs;
Adrian Hunter73944a62008-09-12 18:13:31 +03001823 chk_lpt_sz += len - c->nhead_offs;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001824 if (d->chk_lpt_sz != chk_lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001825 ubifs_err("LPT wrote %lld but space used was %lld",
1826 d->chk_lpt_sz, chk_lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001827 err = -EINVAL;
1828 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001829 if (d->chk_lpt_sz > c->lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001830 ubifs_err("LPT wrote %lld but lpt_sz is %lld",
1831 d->chk_lpt_sz, c->lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001832 err = -EINVAL;
1833 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001834 if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001835 ubifs_err("LPT layout size %lld but wrote %lld",
1836 d->chk_lpt_sz, d->chk_lpt_sz2);
Adrian Hunter73944a62008-09-12 18:13:31 +03001837 err = -EINVAL;
1838 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001839 if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001840 ubifs_err("LPT new nhead offs: expected %d was %d",
1841 d->new_nhead_offs, len);
Adrian Hunter73944a62008-09-12 18:13:31 +03001842 err = -EINVAL;
1843 }
1844 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1845 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1846 lpt_sz += c->ltab_sz;
1847 if (c->big_lpt)
1848 lpt_sz += c->lsave_sz;
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001849 if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
Artem Bityutskiya6aae4d2012-05-16 20:11:23 +03001850 ubifs_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1851 d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
Adrian Hunter73944a62008-09-12 18:13:31 +03001852 err = -EINVAL;
1853 }
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001854 if (err) {
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001855 ubifs_dump_lpt_info(c);
1856 ubifs_dump_lpt_lebs(c);
Artem Bityutskiy787845b2008-10-31 12:17:42 +02001857 dump_stack();
1858 }
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001859 d->chk_lpt_sz2 = d->chk_lpt_sz;
1860 d->chk_lpt_sz = 0;
1861 d->chk_lpt_wastage = 0;
1862 d->chk_lpt_lebs = 0;
1863 d->new_nhead_offs = len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001864 return err;
1865 case 4:
Artem Bityutskiy17c2f9f2008-10-17 13:31:39 +03001866 d->chk_lpt_sz += len;
1867 d->chk_lpt_wastage += len;
Adrian Hunter73944a62008-09-12 18:13:31 +03001868 return 0;
1869 default:
1870 return -EINVAL;
1871 }
1872}
1873
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001874/**
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001875 * ubifs_dump_lpt_leb - dump an LPT LEB.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001876 * @c: UBIFS file-system description object
1877 * @lnum: LEB number to dump
1878 *
1879 * This function dumps an LEB from LPT area. Nodes in this area are very
1880 * different to nodes in the main area (e.g., they do not have common headers,
1881 * they do not have 8-byte alignments, etc), so we have a separate function to
Artem Bityutskiy80736d42008-12-30 17:44:02 +02001882 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001883 */
1884static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1885{
1886 int err, len = c->leb_size, node_type, node_num, node_len, offs;
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001887 void *buf, *p;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001888
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001889 pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
Artem Bityutskiyfc5e58c2011-03-24 16:14:26 +02001890 buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001891 if (!buf) {
1892 ubifs_err("cannot allocate memory to dump LPT");
1893 return;
1894 }
1895
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001896 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1897 if (err)
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001898 goto out;
Artem Bityutskiyd3048202011-06-03 14:03:25 +03001899
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001900 while (1) {
1901 offs = c->leb_size - len;
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001902 if (!is_a_node(c, p, len)) {
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001903 int pad_len;
1904
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001905 pad_len = get_pad_len(c, p, len);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001906 if (pad_len) {
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001907 pr_err("LEB %d:%d, pad %d bytes\n",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001908 lnum, offs, pad_len);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001909 p += pad_len;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001910 len -= pad_len;
1911 continue;
1912 }
1913 if (len)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001914 pr_err("LEB %d:%d, free %d bytes\n",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001915 lnum, offs, len);
1916 break;
1917 }
1918
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001919 node_type = get_lpt_node_type(c, p, &node_num);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001920 switch (node_type) {
1921 case UBIFS_LPT_PNODE:
1922 {
1923 node_len = c->pnode_sz;
1924 if (c->big_lpt)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001925 pr_err("LEB %d:%d, pnode num %d\n",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001926 lnum, offs, node_num);
1927 else
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001928 pr_err("LEB %d:%d, pnode\n", lnum, offs);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001929 break;
1930 }
1931 case UBIFS_LPT_NNODE:
1932 {
1933 int i;
1934 struct ubifs_nnode nnode;
1935
1936 node_len = c->nnode_sz;
1937 if (c->big_lpt)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001938 pr_err("LEB %d:%d, nnode num %d, ",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001939 lnum, offs, node_num);
1940 else
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001941 pr_err("LEB %d:%d, nnode, ",
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001942 lnum, offs);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001943 err = ubifs_unpack_nnode(c, p, &nnode);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001944 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001945 pr_cont("%d:%d", nnode.nbranch[i].lnum,
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001946 nnode.nbranch[i].offs);
1947 if (i != UBIFS_LPT_FANOUT - 1)
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001948 pr_cont(", ");
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001949 }
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001950 pr_cont("\n");
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001951 break;
1952 }
1953 case UBIFS_LPT_LTAB:
1954 node_len = c->ltab_sz;
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001955 pr_err("LEB %d:%d, ltab\n", lnum, offs);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001956 break;
1957 case UBIFS_LPT_LSAVE:
1958 node_len = c->lsave_sz;
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001959 pr_err("LEB %d:%d, lsave len\n", lnum, offs);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001960 break;
1961 default:
1962 ubifs_err("LPT node type %d not recognized", node_type);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001963 goto out;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001964 }
1965
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001966 p += node_len;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001967 len -= node_len;
1968 }
1969
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001970 pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
Artem Bityutskiycab95d42011-03-11 16:58:39 +02001971out:
1972 vfree(buf);
1973 return;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001974}
1975
1976/**
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001977 * ubifs_dump_lpt_lebs - dump LPT lebs.
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001978 * @c: UBIFS file-system description object
1979 *
1980 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1981 * locked.
1982 */
Artem Bityutskiyedf6be22012-05-16 19:15:56 +03001983void ubifs_dump_lpt_lebs(const struct ubifs_info *c)
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001984{
1985 int i;
1986
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001987 pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001988 for (i = 0; i < c->lpt_lebs; i++)
1989 dump_lpt_leb(c, i + c->lpt_first);
Artem Bityutskiy6b38d032012-08-27 13:56:19 +03001990 pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001991}
1992
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03001993/**
1994 * dbg_populate_lsave - debugging version of 'populate_lsave()'
1995 * @c: UBIFS file-system description object
1996 *
1997 * This is a debugging version for 'populate_lsave()' which populates lsave
1998 * with random LEBs instead of useful LEBs, which is good for test coverage.
1999 * Returns zero if lsave has not been populated (this debugging feature is
2000 * disabled) an non-zero if lsave has been populated.
2001 */
2002static int dbg_populate_lsave(struct ubifs_info *c)
2003{
2004 struct ubifs_lprops *lprops;
2005 struct ubifs_lpt_heap *heap;
2006 int i;
2007
Artem Bityutskiy2b1844a2011-06-03 08:31:29 +03002008 if (!dbg_is_chk_gen(c))
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002009 return 0;
Akinobu Mita3d251a52013-01-03 21:19:09 +09002010 if (prandom_u32() & 3)
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002011 return 0;
2012
2013 for (i = 0; i < c->lsave_cnt; i++)
2014 c->lsave[i] = c->main_first;
2015
2016 list_for_each_entry(lprops, &c->empty_list, list)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002017 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002018 list_for_each_entry(lprops, &c->freeable_list, list)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002019 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002020 list_for_each_entry(lprops, &c->frdi_idx_list, list)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002021 c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002022
2023 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
2024 for (i = 0; i < heap->cnt; i++)
Akinobu Mita3d251a52013-01-03 21:19:09 +09002025 c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
Artem Bityutskiycdd8ad62011-04-05 15:43:44 +03002026 heap = &c->lpt_heap[LPROPS_DIRTY - 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_FREE - 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
2033 return 1;
2034}