blob: b2792e84d2452fd37e27991b42c1ab5754044de4 [file] [log] [blame]
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001/*
2 * This file is part of UBIFS.
3 *
4 * Copyright (C) 2006-2008 Nokia Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 * more details.
14 *
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
21 */
22
23/*
24 * This file implements the LEB properties tree (LPT) area. The LPT area
25 * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and
26 * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits
27 * between the log and the orphan area.
28 *
29 * The LPT area is like a miniature self-contained file system. It is required
30 * that it never runs out of space, is fast to access and update, and scales
31 * logarithmically. The LEB properties tree is implemented as a wandering tree
32 * much like the TNC, and the LPT area has its own garbage collection.
33 *
34 * The LPT has two slightly different forms called the "small model" and the
35 * "big model". The small model is used when the entire LEB properties table
36 * can be written into a single eraseblock. In that case, garbage collection
37 * consists of just writing the whole table, which therefore makes all other
38 * eraseblocks reusable. In the case of the big model, dirty eraseblocks are
Artem Bityutskiy45e12d92008-10-31 11:42:18 +020039 * selected for garbage collection, which consists of marking the clean nodes in
Artem Bityutskiy1e517642008-07-14 19:08:37 +030040 * that LEB as dirty, and then only the dirty nodes are written out. Also, in
41 * the case of the big model, a table of LEB numbers is saved so that the entire
42 * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
43 * mounted.
44 */
45
Artem Bityutskiy1e517642008-07-14 19:08:37 +030046#include "ubifs.h"
Artem Bityutskiy4d61db42008-12-18 14:06:51 +020047#include <linux/crc16.h>
48#include <linux/math64.h>
Artem Bityutskiy1e517642008-07-14 19:08:37 +030049
50/**
51 * do_calc_lpt_geom - calculate sizes for the LPT area.
52 * @c: the UBIFS file-system description object
53 *
54 * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
55 * properties of the flash and whether LPT is "big" (c->big_lpt).
56 */
57static void do_calc_lpt_geom(struct ubifs_info *c)
58{
59 int i, n, bits, per_leb_wastage, max_pnode_cnt;
60 long long sz, tot_wastage;
61
62 n = c->main_lebs + c->max_leb_cnt - c->leb_cnt;
63 max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
64
65 c->lpt_hght = 1;
66 n = UBIFS_LPT_FANOUT;
67 while (n < max_pnode_cnt) {
68 c->lpt_hght += 1;
69 n <<= UBIFS_LPT_FANOUT_SHIFT;
70 }
71
72 c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
73
74 n = DIV_ROUND_UP(c->pnode_cnt, UBIFS_LPT_FANOUT);
75 c->nnode_cnt = n;
76 for (i = 1; i < c->lpt_hght; i++) {
77 n = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
78 c->nnode_cnt += n;
79 }
80
81 c->space_bits = fls(c->leb_size) - 3;
82 c->lpt_lnum_bits = fls(c->lpt_lebs);
83 c->lpt_offs_bits = fls(c->leb_size - 1);
84 c->lpt_spc_bits = fls(c->leb_size);
85
86 n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT);
87 c->pcnt_bits = fls(n - 1);
88
89 c->lnum_bits = fls(c->max_leb_cnt - 1);
90
91 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
92 (c->big_lpt ? c->pcnt_bits : 0) +
93 (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;
94 c->pnode_sz = (bits + 7) / 8;
95
96 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
97 (c->big_lpt ? c->pcnt_bits : 0) +
98 (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;
99 c->nnode_sz = (bits + 7) / 8;
100
101 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
102 c->lpt_lebs * c->lpt_spc_bits * 2;
103 c->ltab_sz = (bits + 7) / 8;
104
105 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
106 c->lnum_bits * c->lsave_cnt;
107 c->lsave_sz = (bits + 7) / 8;
108
109 /* Calculate the minimum LPT size */
110 c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
111 c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
112 c->lpt_sz += c->ltab_sz;
Adrian Hunter73944a62008-09-12 18:13:31 +0300113 if (c->big_lpt)
114 c->lpt_sz += c->lsave_sz;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300115
116 /* Add wastage */
117 sz = c->lpt_sz;
118 per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);
119 sz += per_leb_wastage;
120 tot_wastage = per_leb_wastage;
121 while (sz > c->leb_size) {
122 sz += per_leb_wastage;
123 sz -= c->leb_size;
124 tot_wastage += per_leb_wastage;
125 }
126 tot_wastage += ALIGN(sz, c->min_io_size) - sz;
127 c->lpt_sz += tot_wastage;
128}
129
130/**
131 * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
132 * @c: the UBIFS file-system description object
133 *
134 * This function returns %0 on success and a negative error code on failure.
135 */
136int ubifs_calc_lpt_geom(struct ubifs_info *c)
137{
138 int lebs_needed;
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200139 long long sz;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300140
141 do_calc_lpt_geom(c);
142
143 /* Verify that lpt_lebs is big enough */
144 sz = c->lpt_sz * 2; /* Must have at least 2 times the size */
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200145 lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300146 if (lebs_needed > c->lpt_lebs) {
147 ubifs_err("too few LPT LEBs");
148 return -EINVAL;
149 }
150
151 /* Verify that ltab fits in a single LEB (since ltab is a single node */
152 if (c->ltab_sz > c->leb_size) {
153 ubifs_err("LPT ltab too big");
154 return -EINVAL;
155 }
156
157 c->check_lpt_free = c->big_lpt;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300158 return 0;
159}
160
161/**
162 * calc_dflt_lpt_geom - calculate default LPT geometry.
163 * @c: the UBIFS file-system description object
164 * @main_lebs: number of main area LEBs is passed and returned here
165 * @big_lpt: whether the LPT area is "big" is returned here
166 *
167 * The size of the LPT area depends on parameters that themselves are dependent
168 * on the size of the LPT area. This function, successively recalculates the LPT
169 * area geometry until the parameters and resultant geometry are consistent.
170 *
171 * This function returns %0 on success and a negative error code on failure.
172 */
173static int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs,
174 int *big_lpt)
175{
176 int i, lebs_needed;
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200177 long long sz;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300178
179 /* Start by assuming the minimum number of LPT LEBs */
180 c->lpt_lebs = UBIFS_MIN_LPT_LEBS;
181 c->main_lebs = *main_lebs - c->lpt_lebs;
182 if (c->main_lebs <= 0)
183 return -EINVAL;
184
185 /* And assume we will use the small LPT model */
186 c->big_lpt = 0;
187
188 /*
189 * Calculate the geometry based on assumptions above and then see if it
190 * makes sense
191 */
192 do_calc_lpt_geom(c);
193
194 /* Small LPT model must have lpt_sz < leb_size */
195 if (c->lpt_sz > c->leb_size) {
196 /* Nope, so try again using big LPT model */
197 c->big_lpt = 1;
198 do_calc_lpt_geom(c);
199 }
200
201 /* Now check there are enough LPT LEBs */
202 for (i = 0; i < 64 ; i++) {
203 sz = c->lpt_sz * 4; /* Allow 4 times the size */
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200204 lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300205 if (lebs_needed > c->lpt_lebs) {
206 /* Not enough LPT LEBs so try again with more */
207 c->lpt_lebs = lebs_needed;
208 c->main_lebs = *main_lebs - c->lpt_lebs;
209 if (c->main_lebs <= 0)
210 return -EINVAL;
211 do_calc_lpt_geom(c);
212 continue;
213 }
214 if (c->ltab_sz > c->leb_size) {
215 ubifs_err("LPT ltab too big");
216 return -EINVAL;
217 }
218 *main_lebs = c->main_lebs;
219 *big_lpt = c->big_lpt;
220 return 0;
221 }
222 return -EINVAL;
223}
224
225/**
226 * pack_bits - pack bit fields end-to-end.
227 * @addr: address at which to pack (passed and next address returned)
228 * @pos: bit position at which to pack (passed and next position returned)
229 * @val: value to pack
230 * @nrbits: number of bits of value to pack (1-32)
231 */
232static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits)
233{
234 uint8_t *p = *addr;
235 int b = *pos;
236
237 ubifs_assert(nrbits > 0);
238 ubifs_assert(nrbits <= 32);
239 ubifs_assert(*pos >= 0);
240 ubifs_assert(*pos < 8);
241 ubifs_assert((val >> nrbits) == 0 || nrbits == 32);
242 if (b) {
243 *p |= ((uint8_t)val) << b;
244 nrbits += b;
245 if (nrbits > 8) {
246 *++p = (uint8_t)(val >>= (8 - b));
247 if (nrbits > 16) {
248 *++p = (uint8_t)(val >>= 8);
249 if (nrbits > 24) {
250 *++p = (uint8_t)(val >>= 8);
251 if (nrbits > 32)
252 *++p = (uint8_t)(val >>= 8);
253 }
254 }
255 }
256 } else {
257 *p = (uint8_t)val;
258 if (nrbits > 8) {
259 *++p = (uint8_t)(val >>= 8);
260 if (nrbits > 16) {
261 *++p = (uint8_t)(val >>= 8);
262 if (nrbits > 24)
263 *++p = (uint8_t)(val >>= 8);
264 }
265 }
266 }
267 b = nrbits & 7;
268 if (b == 0)
269 p++;
270 *addr = p;
271 *pos = b;
272}
273
274/**
275 * ubifs_unpack_bits - unpack bit fields.
276 * @addr: address at which to unpack (passed and next address returned)
277 * @pos: bit position at which to unpack (passed and next position returned)
278 * @nrbits: number of bits of value to unpack (1-32)
279 *
280 * This functions returns the value unpacked.
281 */
282uint32_t ubifs_unpack_bits(uint8_t **addr, int *pos, int nrbits)
283{
284 const int k = 32 - nrbits;
285 uint8_t *p = *addr;
286 int b = *pos;
Adrian Hunter727d2dc2008-10-17 16:52:10 +0300287 uint32_t uninitialized_var(val);
288 const int bytes = (nrbits + b + 7) >> 3;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300289
290 ubifs_assert(nrbits > 0);
291 ubifs_assert(nrbits <= 32);
292 ubifs_assert(*pos >= 0);
293 ubifs_assert(*pos < 8);
294 if (b) {
Adrian Hunter727d2dc2008-10-17 16:52:10 +0300295 switch (bytes) {
296 case 2:
297 val = p[1];
298 break;
299 case 3:
300 val = p[1] | ((uint32_t)p[2] << 8);
301 break;
302 case 4:
303 val = p[1] | ((uint32_t)p[2] << 8) |
304 ((uint32_t)p[3] << 16);
305 break;
306 case 5:
307 val = p[1] | ((uint32_t)p[2] << 8) |
308 ((uint32_t)p[3] << 16) |
309 ((uint32_t)p[4] << 24);
310 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300311 val <<= (8 - b);
312 val |= *p >> b;
313 nrbits += b;
Adrian Hunter727d2dc2008-10-17 16:52:10 +0300314 } else {
315 switch (bytes) {
316 case 1:
317 val = p[0];
318 break;
319 case 2:
320 val = p[0] | ((uint32_t)p[1] << 8);
321 break;
322 case 3:
323 val = p[0] | ((uint32_t)p[1] << 8) |
324 ((uint32_t)p[2] << 16);
325 break;
326 case 4:
327 val = p[0] | ((uint32_t)p[1] << 8) |
328 ((uint32_t)p[2] << 16) |
329 ((uint32_t)p[3] << 24);
330 break;
331 }
332 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300333 val <<= k;
334 val >>= k;
335 b = nrbits & 7;
Adrian Hunter727d2dc2008-10-17 16:52:10 +0300336 p += nrbits >> 3;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300337 *addr = p;
338 *pos = b;
339 ubifs_assert((val >> nrbits) == 0 || nrbits - b == 32);
340 return val;
341}
342
343/**
344 * ubifs_pack_pnode - pack all the bit fields of a pnode.
345 * @c: UBIFS file-system description object
346 * @buf: buffer into which to pack
347 * @pnode: pnode to pack
348 */
349void ubifs_pack_pnode(struct ubifs_info *c, void *buf,
350 struct ubifs_pnode *pnode)
351{
352 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
353 int i, pos = 0;
354 uint16_t crc;
355
356 pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS);
357 if (c->big_lpt)
358 pack_bits(&addr, &pos, pnode->num, c->pcnt_bits);
359 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
360 pack_bits(&addr, &pos, pnode->lprops[i].free >> 3,
361 c->space_bits);
362 pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3,
363 c->space_bits);
364 if (pnode->lprops[i].flags & LPROPS_INDEX)
365 pack_bits(&addr, &pos, 1, 1);
366 else
367 pack_bits(&addr, &pos, 0, 1);
368 }
369 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
370 c->pnode_sz - UBIFS_LPT_CRC_BYTES);
371 addr = buf;
372 pos = 0;
373 pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
374}
375
376/**
377 * ubifs_pack_nnode - pack all the bit fields of a nnode.
378 * @c: UBIFS file-system description object
379 * @buf: buffer into which to pack
380 * @nnode: nnode to pack
381 */
382void ubifs_pack_nnode(struct ubifs_info *c, void *buf,
383 struct ubifs_nnode *nnode)
384{
385 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
386 int i, pos = 0;
387 uint16_t crc;
388
389 pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS);
390 if (c->big_lpt)
391 pack_bits(&addr, &pos, nnode->num, c->pcnt_bits);
392 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
393 int lnum = nnode->nbranch[i].lnum;
394
395 if (lnum == 0)
396 lnum = c->lpt_last + 1;
397 pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits);
398 pack_bits(&addr, &pos, nnode->nbranch[i].offs,
399 c->lpt_offs_bits);
400 }
401 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
402 c->nnode_sz - UBIFS_LPT_CRC_BYTES);
403 addr = buf;
404 pos = 0;
405 pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
406}
407
408/**
409 * ubifs_pack_ltab - pack the LPT's own lprops table.
410 * @c: UBIFS file-system description object
411 * @buf: buffer into which to pack
412 * @ltab: LPT's own lprops table to pack
413 */
414void ubifs_pack_ltab(struct ubifs_info *c, void *buf,
415 struct ubifs_lpt_lprops *ltab)
416{
417 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
418 int i, pos = 0;
419 uint16_t crc;
420
421 pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS);
422 for (i = 0; i < c->lpt_lebs; i++) {
423 pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits);
424 pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits);
425 }
426 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
427 c->ltab_sz - UBIFS_LPT_CRC_BYTES);
428 addr = buf;
429 pos = 0;
430 pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
431}
432
433/**
434 * ubifs_pack_lsave - pack the LPT's save table.
435 * @c: UBIFS file-system description object
436 * @buf: buffer into which to pack
437 * @lsave: LPT's save table to pack
438 */
439void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave)
440{
441 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
442 int i, pos = 0;
443 uint16_t crc;
444
445 pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS);
446 for (i = 0; i < c->lsave_cnt; i++)
447 pack_bits(&addr, &pos, lsave[i], c->lnum_bits);
448 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
449 c->lsave_sz - UBIFS_LPT_CRC_BYTES);
450 addr = buf;
451 pos = 0;
452 pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
453}
454
455/**
456 * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
457 * @c: UBIFS file-system description object
458 * @lnum: LEB number to which to add dirty space
459 * @dirty: amount of dirty space to add
460 */
461void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty)
462{
463 if (!dirty || !lnum)
464 return;
465 dbg_lp("LEB %d add %d to %d",
466 lnum, dirty, c->ltab[lnum - c->lpt_first].dirty);
467 ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
468 c->ltab[lnum - c->lpt_first].dirty += dirty;
469}
470
471/**
472 * set_ltab - set LPT LEB properties.
473 * @c: UBIFS file-system description object
474 * @lnum: LEB number
475 * @free: amount of free space
476 * @dirty: amount of dirty space
477 */
478static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
479{
480 dbg_lp("LEB %d free %d dirty %d to %d %d",
481 lnum, c->ltab[lnum - c->lpt_first].free,
482 c->ltab[lnum - c->lpt_first].dirty, free, dirty);
483 ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
484 c->ltab[lnum - c->lpt_first].free = free;
485 c->ltab[lnum - c->lpt_first].dirty = dirty;
486}
487
488/**
489 * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
490 * @c: UBIFS file-system description object
491 * @nnode: nnode for which to add dirt
492 */
493void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode)
494{
495 struct ubifs_nnode *np = nnode->parent;
496
497 if (np)
498 ubifs_add_lpt_dirt(c, np->nbranch[nnode->iip].lnum,
499 c->nnode_sz);
500 else {
501 ubifs_add_lpt_dirt(c, c->lpt_lnum, c->nnode_sz);
502 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
503 c->lpt_drty_flgs |= LTAB_DIRTY;
504 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
505 }
506 }
507}
508
509/**
510 * add_pnode_dirt - add dirty space to LPT LEB properties.
511 * @c: UBIFS file-system description object
512 * @pnode: pnode for which to add dirt
513 */
514static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
515{
516 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
517 c->pnode_sz);
518}
519
520/**
521 * calc_nnode_num - calculate nnode number.
522 * @row: the row in the tree (root is zero)
523 * @col: the column in the row (leftmost is zero)
524 *
525 * The nnode number is a number that uniquely identifies a nnode and can be used
526 * easily to traverse the tree from the root to that nnode.
527 *
528 * This function calculates and returns the nnode number for the nnode at @row
529 * and @col.
530 */
531static int calc_nnode_num(int row, int col)
532{
533 int num, bits;
534
535 num = 1;
536 while (row--) {
537 bits = (col & (UBIFS_LPT_FANOUT - 1));
538 col >>= UBIFS_LPT_FANOUT_SHIFT;
539 num <<= UBIFS_LPT_FANOUT_SHIFT;
540 num |= bits;
541 }
542 return num;
543}
544
545/**
546 * calc_nnode_num_from_parent - calculate nnode number.
547 * @c: UBIFS file-system description object
548 * @parent: parent nnode
549 * @iip: index in parent
550 *
551 * The nnode number is a number that uniquely identifies a nnode and can be used
552 * easily to traverse the tree from the root to that nnode.
553 *
554 * This function calculates and returns the nnode number based on the parent's
555 * nnode number and the index in parent.
556 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +0200557static int calc_nnode_num_from_parent(const struct ubifs_info *c,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300558 struct ubifs_nnode *parent, int iip)
559{
560 int num, shft;
561
562 if (!parent)
563 return 1;
564 shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT;
565 num = parent->num ^ (1 << shft);
566 num |= (UBIFS_LPT_FANOUT + iip) << shft;
567 return num;
568}
569
570/**
571 * calc_pnode_num_from_parent - calculate pnode number.
572 * @c: UBIFS file-system description object
573 * @parent: parent nnode
574 * @iip: index in parent
575 *
576 * The pnode number is a number that uniquely identifies a pnode and can be used
577 * easily to traverse the tree from the root to that pnode.
578 *
579 * This function calculates and returns the pnode number based on the parent's
580 * nnode number and the index in parent.
581 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +0200582static int calc_pnode_num_from_parent(const struct ubifs_info *c,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300583 struct ubifs_nnode *parent, int iip)
584{
585 int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0;
586
587 for (i = 0; i < n; i++) {
588 num <<= UBIFS_LPT_FANOUT_SHIFT;
589 num |= pnum & (UBIFS_LPT_FANOUT - 1);
590 pnum >>= UBIFS_LPT_FANOUT_SHIFT;
591 }
592 num <<= UBIFS_LPT_FANOUT_SHIFT;
593 num |= iip;
594 return num;
595}
596
597/**
598 * ubifs_create_dflt_lpt - create default LPT.
599 * @c: UBIFS file-system description object
600 * @main_lebs: number of main area LEBs is passed and returned here
601 * @lpt_first: LEB number of first LPT LEB
602 * @lpt_lebs: number of LEBs for LPT is passed and returned here
603 * @big_lpt: use big LPT model is passed and returned here
604 *
605 * This function returns %0 on success and a negative error code on failure.
606 */
607int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first,
608 int *lpt_lebs, int *big_lpt)
609{
610 int lnum, err = 0, node_sz, iopos, i, j, cnt, len, alen, row;
611 int blnum, boffs, bsz, bcnt;
612 struct ubifs_pnode *pnode = NULL;
613 struct ubifs_nnode *nnode = NULL;
614 void *buf = NULL, *p;
615 struct ubifs_lpt_lprops *ltab = NULL;
616 int *lsave = NULL;
617
618 err = calc_dflt_lpt_geom(c, main_lebs, big_lpt);
619 if (err)
620 return err;
621 *lpt_lebs = c->lpt_lebs;
622
623 /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */
624 c->lpt_first = lpt_first;
625 /* Needed by 'set_ltab()' */
626 c->lpt_last = lpt_first + c->lpt_lebs - 1;
627 /* Needed by 'ubifs_pack_lsave()' */
628 c->main_first = c->leb_cnt - *main_lebs;
629
630 lsave = kmalloc(sizeof(int) * c->lsave_cnt, GFP_KERNEL);
631 pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_KERNEL);
632 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_KERNEL);
633 buf = vmalloc(c->leb_size);
634 ltab = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
635 if (!pnode || !nnode || !buf || !ltab || !lsave) {
636 err = -ENOMEM;
637 goto out;
638 }
639
640 ubifs_assert(!c->ltab);
641 c->ltab = ltab; /* Needed by set_ltab */
642
643 /* Initialize LPT's own lprops */
644 for (i = 0; i < c->lpt_lebs; i++) {
645 ltab[i].free = c->leb_size;
646 ltab[i].dirty = 0;
647 ltab[i].tgc = 0;
648 ltab[i].cmt = 0;
649 }
650
651 lnum = lpt_first;
652 p = buf;
653 /* Number of leaf nodes (pnodes) */
654 cnt = c->pnode_cnt;
655
656 /*
657 * The first pnode contains the LEB properties for the LEBs that contain
658 * the root inode node and the root index node of the index tree.
659 */
660 node_sz = ALIGN(ubifs_idx_node_sz(c, 1), 8);
661 iopos = ALIGN(node_sz, c->min_io_size);
662 pnode->lprops[0].free = c->leb_size - iopos;
663 pnode->lprops[0].dirty = iopos - node_sz;
664 pnode->lprops[0].flags = LPROPS_INDEX;
665
666 node_sz = UBIFS_INO_NODE_SZ;
667 iopos = ALIGN(node_sz, c->min_io_size);
668 pnode->lprops[1].free = c->leb_size - iopos;
669 pnode->lprops[1].dirty = iopos - node_sz;
670
671 for (i = 2; i < UBIFS_LPT_FANOUT; i++)
672 pnode->lprops[i].free = c->leb_size;
673
674 /* Add first pnode */
675 ubifs_pack_pnode(c, p, pnode);
676 p += c->pnode_sz;
677 len = c->pnode_sz;
678 pnode->num += 1;
679
680 /* Reset pnode values for remaining pnodes */
681 pnode->lprops[0].free = c->leb_size;
682 pnode->lprops[0].dirty = 0;
683 pnode->lprops[0].flags = 0;
684
685 pnode->lprops[1].free = c->leb_size;
686 pnode->lprops[1].dirty = 0;
687
688 /*
689 * To calculate the internal node branches, we keep information about
690 * the level below.
691 */
692 blnum = lnum; /* LEB number of level below */
693 boffs = 0; /* Offset of level below */
694 bcnt = cnt; /* Number of nodes in level below */
695 bsz = c->pnode_sz; /* Size of nodes in level below */
696
697 /* Add all remaining pnodes */
698 for (i = 1; i < cnt; i++) {
699 if (len + c->pnode_sz > c->leb_size) {
700 alen = ALIGN(len, c->min_io_size);
701 set_ltab(c, lnum, c->leb_size - alen, alen - len);
702 memset(p, 0xff, alen - len);
703 err = ubi_leb_change(c->ubi, lnum++, buf, alen,
704 UBI_SHORTTERM);
705 if (err)
706 goto out;
707 p = buf;
708 len = 0;
709 }
710 ubifs_pack_pnode(c, p, pnode);
711 p += c->pnode_sz;
712 len += c->pnode_sz;
713 /*
714 * pnodes are simply numbered left to right starting at zero,
715 * which means the pnode number can be used easily to traverse
716 * down the tree to the corresponding pnode.
717 */
718 pnode->num += 1;
719 }
720
721 row = 0;
722 for (i = UBIFS_LPT_FANOUT; cnt > i; i <<= UBIFS_LPT_FANOUT_SHIFT)
723 row += 1;
724 /* Add all nnodes, one level at a time */
725 while (1) {
726 /* Number of internal nodes (nnodes) at next level */
727 cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT);
728 for (i = 0; i < cnt; i++) {
729 if (len + c->nnode_sz > c->leb_size) {
730 alen = ALIGN(len, c->min_io_size);
731 set_ltab(c, lnum, c->leb_size - alen,
732 alen - len);
733 memset(p, 0xff, alen - len);
734 err = ubi_leb_change(c->ubi, lnum++, buf, alen,
735 UBI_SHORTTERM);
736 if (err)
737 goto out;
738 p = buf;
739 len = 0;
740 }
741 /* Only 1 nnode at this level, so it is the root */
742 if (cnt == 1) {
743 c->lpt_lnum = lnum;
744 c->lpt_offs = len;
745 }
746 /* Set branches to the level below */
747 for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
748 if (bcnt) {
749 if (boffs + bsz > c->leb_size) {
750 blnum += 1;
751 boffs = 0;
752 }
753 nnode->nbranch[j].lnum = blnum;
754 nnode->nbranch[j].offs = boffs;
755 boffs += bsz;
756 bcnt--;
757 } else {
758 nnode->nbranch[j].lnum = 0;
759 nnode->nbranch[j].offs = 0;
760 }
761 }
762 nnode->num = calc_nnode_num(row, i);
763 ubifs_pack_nnode(c, p, nnode);
764 p += c->nnode_sz;
765 len += c->nnode_sz;
766 }
767 /* Only 1 nnode at this level, so it is the root */
768 if (cnt == 1)
769 break;
770 /* Update the information about the level below */
771 bcnt = cnt;
772 bsz = c->nnode_sz;
773 row -= 1;
774 }
775
776 if (*big_lpt) {
777 /* Need to add LPT's save table */
778 if (len + c->lsave_sz > c->leb_size) {
779 alen = ALIGN(len, c->min_io_size);
780 set_ltab(c, lnum, c->leb_size - alen, alen - len);
781 memset(p, 0xff, alen - len);
782 err = ubi_leb_change(c->ubi, lnum++, buf, alen,
783 UBI_SHORTTERM);
784 if (err)
785 goto out;
786 p = buf;
787 len = 0;
788 }
789
790 c->lsave_lnum = lnum;
791 c->lsave_offs = len;
792
793 for (i = 0; i < c->lsave_cnt && i < *main_lebs; i++)
794 lsave[i] = c->main_first + i;
795 for (; i < c->lsave_cnt; i++)
796 lsave[i] = c->main_first;
797
798 ubifs_pack_lsave(c, p, lsave);
799 p += c->lsave_sz;
800 len += c->lsave_sz;
801 }
802
803 /* Need to add LPT's own LEB properties table */
804 if (len + c->ltab_sz > c->leb_size) {
805 alen = ALIGN(len, c->min_io_size);
806 set_ltab(c, lnum, c->leb_size - alen, alen - len);
807 memset(p, 0xff, alen - len);
808 err = ubi_leb_change(c->ubi, lnum++, buf, alen, UBI_SHORTTERM);
809 if (err)
810 goto out;
811 p = buf;
812 len = 0;
813 }
814
815 c->ltab_lnum = lnum;
816 c->ltab_offs = len;
817
818 /* Update ltab before packing it */
819 len += c->ltab_sz;
820 alen = ALIGN(len, c->min_io_size);
821 set_ltab(c, lnum, c->leb_size - alen, alen - len);
822
823 ubifs_pack_ltab(c, p, ltab);
824 p += c->ltab_sz;
825
826 /* Write remaining buffer */
827 memset(p, 0xff, alen - len);
828 err = ubi_leb_change(c->ubi, lnum, buf, alen, UBI_SHORTTERM);
829 if (err)
830 goto out;
831
832 c->nhead_lnum = lnum;
833 c->nhead_offs = ALIGN(len, c->min_io_size);
834
835 dbg_lp("space_bits %d", c->space_bits);
836 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
837 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
838 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
839 dbg_lp("pcnt_bits %d", c->pcnt_bits);
840 dbg_lp("lnum_bits %d", c->lnum_bits);
841 dbg_lp("pnode_sz %d", c->pnode_sz);
842 dbg_lp("nnode_sz %d", c->nnode_sz);
843 dbg_lp("ltab_sz %d", c->ltab_sz);
844 dbg_lp("lsave_sz %d", c->lsave_sz);
845 dbg_lp("lsave_cnt %d", c->lsave_cnt);
846 dbg_lp("lpt_hght %d", c->lpt_hght);
847 dbg_lp("big_lpt %d", c->big_lpt);
848 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
849 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
850 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
851 if (c->big_lpt)
852 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
853out:
854 c->ltab = NULL;
855 kfree(lsave);
856 vfree(ltab);
857 vfree(buf);
858 kfree(nnode);
859 kfree(pnode);
860 return err;
861}
862
863/**
864 * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
865 * @c: UBIFS file-system description object
866 * @pnode: pnode
867 *
868 * When a pnode is loaded into memory, the LEB properties it contains are added,
869 * by this function, to the LEB category lists and heaps.
870 */
871static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)
872{
873 int i;
874
875 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
876 int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;
877 int lnum = pnode->lprops[i].lnum;
878
879 if (!lnum)
880 return;
881 ubifs_add_to_cat(c, &pnode->lprops[i], cat);
882 }
883}
884
885/**
886 * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
887 * @c: UBIFS file-system description object
888 * @old_pnode: pnode copied
889 * @new_pnode: pnode copy
890 *
891 * During commit it is sometimes necessary to copy a pnode
892 * (see dirty_cow_pnode). When that happens, references in
893 * category lists and heaps must be replaced. This function does that.
894 */
895static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,
896 struct ubifs_pnode *new_pnode)
897{
898 int i;
899
900 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
901 if (!new_pnode->lprops[i].lnum)
902 return;
903 ubifs_replace_cat(c, &old_pnode->lprops[i],
904 &new_pnode->lprops[i]);
905 }
906}
907
908/**
909 * check_lpt_crc - check LPT node crc is correct.
910 * @c: UBIFS file-system description object
911 * @buf: buffer containing node
912 * @len: length of node
913 *
914 * This function returns %0 on success and a negative error code on failure.
915 */
916static int check_lpt_crc(void *buf, int len)
917{
918 int pos = 0;
919 uint8_t *addr = buf;
920 uint16_t crc, calc_crc;
921
922 crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
923 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
924 len - UBIFS_LPT_CRC_BYTES);
925 if (crc != calc_crc) {
926 ubifs_err("invalid crc in LPT node: crc %hx calc %hx", crc,
927 calc_crc);
928 dbg_dump_stack();
929 return -EINVAL;
930 }
931 return 0;
932}
933
934/**
935 * check_lpt_type - check LPT node type is correct.
936 * @c: UBIFS file-system description object
937 * @addr: address of type bit field is passed and returned updated here
938 * @pos: position of type bit field is passed and returned updated here
939 * @type: expected type
940 *
941 * This function returns %0 on success and a negative error code on failure.
942 */
943static int check_lpt_type(uint8_t **addr, int *pos, int type)
944{
945 int node_type;
946
947 node_type = ubifs_unpack_bits(addr, pos, UBIFS_LPT_TYPE_BITS);
948 if (node_type != type) {
949 ubifs_err("invalid type (%d) in LPT node type %d", node_type,
950 type);
951 dbg_dump_stack();
952 return -EINVAL;
953 }
954 return 0;
955}
956
957/**
958 * unpack_pnode - unpack a pnode.
959 * @c: UBIFS file-system description object
960 * @buf: buffer containing packed pnode to unpack
961 * @pnode: pnode structure to fill
962 *
963 * This function returns %0 on success and a negative error code on failure.
964 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +0200965static int unpack_pnode(const struct ubifs_info *c, void *buf,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300966 struct ubifs_pnode *pnode)
967{
968 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
969 int i, pos = 0, err;
970
971 err = check_lpt_type(&addr, &pos, UBIFS_LPT_PNODE);
972 if (err)
973 return err;
974 if (c->big_lpt)
975 pnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
976 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
977 struct ubifs_lprops * const lprops = &pnode->lprops[i];
978
979 lprops->free = ubifs_unpack_bits(&addr, &pos, c->space_bits);
980 lprops->free <<= 3;
981 lprops->dirty = ubifs_unpack_bits(&addr, &pos, c->space_bits);
982 lprops->dirty <<= 3;
983
984 if (ubifs_unpack_bits(&addr, &pos, 1))
985 lprops->flags = LPROPS_INDEX;
986 else
987 lprops->flags = 0;
988 lprops->flags |= ubifs_categorize_lprops(c, lprops);
989 }
990 err = check_lpt_crc(buf, c->pnode_sz);
991 return err;
992}
993
994/**
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +0200995 * ubifs_unpack_nnode - unpack a nnode.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300996 * @c: UBIFS file-system description object
997 * @buf: buffer containing packed nnode to unpack
998 * @nnode: nnode structure to fill
999 *
1000 * This function returns %0 on success and a negative error code on failure.
1001 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001002int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,
1003 struct ubifs_nnode *nnode)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001004{
1005 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1006 int i, pos = 0, err;
1007
1008 err = check_lpt_type(&addr, &pos, UBIFS_LPT_NNODE);
1009 if (err)
1010 return err;
1011 if (c->big_lpt)
1012 nnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1013 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1014 int lnum;
1015
1016 lnum = ubifs_unpack_bits(&addr, &pos, c->lpt_lnum_bits) +
1017 c->lpt_first;
1018 if (lnum == c->lpt_last + 1)
1019 lnum = 0;
1020 nnode->nbranch[i].lnum = lnum;
1021 nnode->nbranch[i].offs = ubifs_unpack_bits(&addr, &pos,
1022 c->lpt_offs_bits);
1023 }
1024 err = check_lpt_crc(buf, c->nnode_sz);
1025 return err;
1026}
1027
1028/**
1029 * unpack_ltab - unpack the LPT's own lprops table.
1030 * @c: UBIFS file-system description object
1031 * @buf: buffer from which to unpack
1032 *
1033 * This function returns %0 on success and a negative error code on failure.
1034 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001035static int unpack_ltab(const struct ubifs_info *c, void *buf)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001036{
1037 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1038 int i, pos = 0, err;
1039
1040 err = check_lpt_type(&addr, &pos, UBIFS_LPT_LTAB);
1041 if (err)
1042 return err;
1043 for (i = 0; i < c->lpt_lebs; i++) {
1044 int free = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits);
1045 int dirty = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits);
1046
1047 if (free < 0 || free > c->leb_size || dirty < 0 ||
1048 dirty > c->leb_size || free + dirty > c->leb_size)
1049 return -EINVAL;
1050
1051 c->ltab[i].free = free;
1052 c->ltab[i].dirty = dirty;
1053 c->ltab[i].tgc = 0;
1054 c->ltab[i].cmt = 0;
1055 }
1056 err = check_lpt_crc(buf, c->ltab_sz);
1057 return err;
1058}
1059
1060/**
1061 * unpack_lsave - unpack the LPT's save table.
1062 * @c: UBIFS file-system description object
1063 * @buf: buffer from which to unpack
1064 *
1065 * This function returns %0 on success and a negative error code on failure.
1066 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001067static int unpack_lsave(const struct ubifs_info *c, void *buf)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001068{
1069 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1070 int i, pos = 0, err;
1071
1072 err = check_lpt_type(&addr, &pos, UBIFS_LPT_LSAVE);
1073 if (err)
1074 return err;
1075 for (i = 0; i < c->lsave_cnt; i++) {
1076 int lnum = ubifs_unpack_bits(&addr, &pos, c->lnum_bits);
1077
1078 if (lnum < c->main_first || lnum >= c->leb_cnt)
1079 return -EINVAL;
1080 c->lsave[i] = lnum;
1081 }
1082 err = check_lpt_crc(buf, c->lsave_sz);
1083 return err;
1084}
1085
1086/**
1087 * validate_nnode - validate a nnode.
1088 * @c: UBIFS file-system description object
1089 * @nnode: nnode to validate
1090 * @parent: parent nnode (or NULL for the root nnode)
1091 * @iip: index in parent
1092 *
1093 * This function returns %0 on success and a negative error code on failure.
1094 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001095static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001096 struct ubifs_nnode *parent, int iip)
1097{
1098 int i, lvl, max_offs;
1099
1100 if (c->big_lpt) {
1101 int num = calc_nnode_num_from_parent(c, parent, iip);
1102
1103 if (nnode->num != num)
1104 return -EINVAL;
1105 }
1106 lvl = parent ? parent->level - 1 : c->lpt_hght;
1107 if (lvl < 1)
1108 return -EINVAL;
1109 if (lvl == 1)
1110 max_offs = c->leb_size - c->pnode_sz;
1111 else
1112 max_offs = c->leb_size - c->nnode_sz;
1113 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1114 int lnum = nnode->nbranch[i].lnum;
1115 int offs = nnode->nbranch[i].offs;
1116
1117 if (lnum == 0) {
1118 if (offs != 0)
1119 return -EINVAL;
1120 continue;
1121 }
1122 if (lnum < c->lpt_first || lnum > c->lpt_last)
1123 return -EINVAL;
1124 if (offs < 0 || offs > max_offs)
1125 return -EINVAL;
1126 }
1127 return 0;
1128}
1129
1130/**
1131 * validate_pnode - validate a pnode.
1132 * @c: UBIFS file-system description object
1133 * @pnode: pnode to validate
1134 * @parent: parent nnode
1135 * @iip: index in parent
1136 *
1137 * This function returns %0 on success and a negative error code on failure.
1138 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001139static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001140 struct ubifs_nnode *parent, int iip)
1141{
1142 int i;
1143
1144 if (c->big_lpt) {
1145 int num = calc_pnode_num_from_parent(c, parent, iip);
1146
1147 if (pnode->num != num)
1148 return -EINVAL;
1149 }
1150 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1151 int free = pnode->lprops[i].free;
1152 int dirty = pnode->lprops[i].dirty;
1153
1154 if (free < 0 || free > c->leb_size || free % c->min_io_size ||
1155 (free & 7))
1156 return -EINVAL;
1157 if (dirty < 0 || dirty > c->leb_size || (dirty & 7))
1158 return -EINVAL;
1159 if (dirty + free > c->leb_size)
1160 return -EINVAL;
1161 }
1162 return 0;
1163}
1164
1165/**
1166 * set_pnode_lnum - set LEB numbers on a pnode.
1167 * @c: UBIFS file-system description object
1168 * @pnode: pnode to update
1169 *
1170 * This function calculates the LEB numbers for the LEB properties it contains
1171 * based on the pnode number.
1172 */
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001173static void set_pnode_lnum(const struct ubifs_info *c,
1174 struct ubifs_pnode *pnode)
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001175{
1176 int i, lnum;
1177
1178 lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;
1179 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1180 if (lnum >= c->leb_cnt)
1181 return;
1182 pnode->lprops[i].lnum = lnum++;
1183 }
1184}
1185
1186/**
1187 * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
1188 * @c: UBIFS file-system description object
1189 * @parent: parent nnode (or NULL for the root)
1190 * @iip: index in parent
1191 *
1192 * This function returns %0 on success and a negative error code on failure.
1193 */
1194int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
1195{
1196 struct ubifs_nbranch *branch = NULL;
1197 struct ubifs_nnode *nnode = NULL;
1198 void *buf = c->lpt_nod_buf;
1199 int err, lnum, offs;
1200
1201 if (parent) {
1202 branch = &parent->nbranch[iip];
1203 lnum = branch->lnum;
1204 offs = branch->offs;
1205 } else {
1206 lnum = c->lpt_lnum;
1207 offs = c->lpt_offs;
1208 }
1209 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
1210 if (!nnode) {
1211 err = -ENOMEM;
1212 goto out;
1213 }
1214 if (lnum == 0) {
1215 /*
1216 * This nnode was not written which just means that the LEB
1217 * properties in the subtree below it describe empty LEBs. We
1218 * make the nnode as though we had read it, which in fact means
1219 * doing almost nothing.
1220 */
1221 if (c->big_lpt)
1222 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1223 } else {
1224 err = ubi_read(c->ubi, lnum, buf, offs, c->nnode_sz);
1225 if (err)
1226 goto out;
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001227 err = ubifs_unpack_nnode(c, buf, nnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001228 if (err)
1229 goto out;
1230 }
1231 err = validate_nnode(c, nnode, parent, iip);
1232 if (err)
1233 goto out;
1234 if (!c->big_lpt)
1235 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1236 if (parent) {
1237 branch->nnode = nnode;
1238 nnode->level = parent->level - 1;
1239 } else {
1240 c->nroot = nnode;
1241 nnode->level = c->lpt_hght;
1242 }
1243 nnode->parent = parent;
1244 nnode->iip = iip;
1245 return 0;
1246
1247out:
1248 ubifs_err("error %d reading nnode at %d:%d", err, lnum, offs);
1249 kfree(nnode);
1250 return err;
1251}
1252
1253/**
1254 * read_pnode - read a pnode from flash and link it to the tree in memory.
1255 * @c: UBIFS file-system description object
1256 * @parent: parent nnode
1257 * @iip: index in parent
1258 *
1259 * This function returns %0 on success and a negative error code on failure.
1260 */
1261static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
1262{
1263 struct ubifs_nbranch *branch;
1264 struct ubifs_pnode *pnode = NULL;
1265 void *buf = c->lpt_nod_buf;
1266 int err, lnum, offs;
1267
1268 branch = &parent->nbranch[iip];
1269 lnum = branch->lnum;
1270 offs = branch->offs;
1271 pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
1272 if (!pnode) {
1273 err = -ENOMEM;
1274 goto out;
1275 }
1276 if (lnum == 0) {
1277 /*
1278 * This pnode was not written which just means that the LEB
1279 * properties in it describe empty LEBs. We make the pnode as
1280 * though we had read it.
1281 */
1282 int i;
1283
1284 if (c->big_lpt)
1285 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1286 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1287 struct ubifs_lprops * const lprops = &pnode->lprops[i];
1288
1289 lprops->free = c->leb_size;
1290 lprops->flags = ubifs_categorize_lprops(c, lprops);
1291 }
1292 } else {
1293 err = ubi_read(c->ubi, lnum, buf, offs, c->pnode_sz);
1294 if (err)
1295 goto out;
1296 err = unpack_pnode(c, buf, pnode);
1297 if (err)
1298 goto out;
1299 }
1300 err = validate_pnode(c, pnode, parent, iip);
1301 if (err)
1302 goto out;
1303 if (!c->big_lpt)
1304 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1305 branch->pnode = pnode;
1306 pnode->parent = parent;
1307 pnode->iip = iip;
1308 set_pnode_lnum(c, pnode);
1309 c->pnodes_have += 1;
1310 return 0;
1311
1312out:
1313 ubifs_err("error %d reading pnode at %d:%d", err, lnum, offs);
1314 dbg_dump_pnode(c, pnode, parent, iip);
1315 dbg_msg("calc num: %d", calc_pnode_num_from_parent(c, parent, iip));
1316 kfree(pnode);
1317 return err;
1318}
1319
1320/**
1321 * read_ltab - read LPT's own lprops table.
1322 * @c: UBIFS file-system description object
1323 *
1324 * This function returns %0 on success and a negative error code on failure.
1325 */
1326static int read_ltab(struct ubifs_info *c)
1327{
1328 int err;
1329 void *buf;
1330
1331 buf = vmalloc(c->ltab_sz);
1332 if (!buf)
1333 return -ENOMEM;
1334 err = ubi_read(c->ubi, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz);
1335 if (err)
1336 goto out;
1337 err = unpack_ltab(c, buf);
1338out:
1339 vfree(buf);
1340 return err;
1341}
1342
1343/**
1344 * read_lsave - read LPT's save table.
1345 * @c: UBIFS file-system description object
1346 *
1347 * This function returns %0 on success and a negative error code on failure.
1348 */
1349static int read_lsave(struct ubifs_info *c)
1350{
1351 int err, i;
1352 void *buf;
1353
1354 buf = vmalloc(c->lsave_sz);
1355 if (!buf)
1356 return -ENOMEM;
1357 err = ubi_read(c->ubi, c->lsave_lnum, buf, c->lsave_offs, c->lsave_sz);
1358 if (err)
1359 goto out;
1360 err = unpack_lsave(c, buf);
1361 if (err)
1362 goto out;
1363 for (i = 0; i < c->lsave_cnt; i++) {
1364 int lnum = c->lsave[i];
1365
1366 /*
1367 * Due to automatic resizing, the values in the lsave table
1368 * could be beyond the volume size - just ignore them.
1369 */
1370 if (lnum >= c->leb_cnt)
1371 continue;
1372 ubifs_lpt_lookup(c, lnum);
1373 }
1374out:
1375 vfree(buf);
1376 return err;
1377}
1378
1379/**
1380 * ubifs_get_nnode - get a nnode.
1381 * @c: UBIFS file-system description object
1382 * @parent: parent nnode (or NULL for the root)
1383 * @iip: index in parent
1384 *
1385 * This function returns a pointer to the nnode on success or a negative error
1386 * code on failure.
1387 */
1388struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,
1389 struct ubifs_nnode *parent, int iip)
1390{
1391 struct ubifs_nbranch *branch;
1392 struct ubifs_nnode *nnode;
1393 int err;
1394
1395 branch = &parent->nbranch[iip];
1396 nnode = branch->nnode;
1397 if (nnode)
1398 return nnode;
1399 err = ubifs_read_nnode(c, parent, iip);
1400 if (err)
1401 return ERR_PTR(err);
1402 return branch->nnode;
1403}
1404
1405/**
1406 * ubifs_get_pnode - get a pnode.
1407 * @c: UBIFS file-system description object
1408 * @parent: parent nnode
1409 * @iip: index in parent
1410 *
1411 * This function returns a pointer to the pnode on success or a negative error
1412 * code on failure.
1413 */
1414struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,
1415 struct ubifs_nnode *parent, int iip)
1416{
1417 struct ubifs_nbranch *branch;
1418 struct ubifs_pnode *pnode;
1419 int err;
1420
1421 branch = &parent->nbranch[iip];
1422 pnode = branch->pnode;
1423 if (pnode)
1424 return pnode;
1425 err = read_pnode(c, parent, iip);
1426 if (err)
1427 return ERR_PTR(err);
1428 update_cats(c, branch->pnode);
1429 return branch->pnode;
1430}
1431
1432/**
1433 * ubifs_lpt_lookup - lookup LEB properties in the LPT.
1434 * @c: UBIFS file-system description object
1435 * @lnum: LEB number to lookup
1436 *
1437 * This function returns a pointer to the LEB properties on success or a
1438 * negative error code on failure.
1439 */
1440struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)
1441{
1442 int err, i, h, iip, shft;
1443 struct ubifs_nnode *nnode;
1444 struct ubifs_pnode *pnode;
1445
1446 if (!c->nroot) {
1447 err = ubifs_read_nnode(c, NULL, 0);
1448 if (err)
1449 return ERR_PTR(err);
1450 }
1451 nnode = c->nroot;
1452 i = lnum - c->main_first;
1453 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1454 for (h = 1; h < c->lpt_hght; h++) {
1455 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1456 shft -= UBIFS_LPT_FANOUT_SHIFT;
1457 nnode = ubifs_get_nnode(c, nnode, iip);
1458 if (IS_ERR(nnode))
1459 return ERR_PTR(PTR_ERR(nnode));
1460 }
1461 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1462 shft -= UBIFS_LPT_FANOUT_SHIFT;
1463 pnode = ubifs_get_pnode(c, nnode, iip);
1464 if (IS_ERR(pnode))
1465 return ERR_PTR(PTR_ERR(pnode));
1466 iip = (i & (UBIFS_LPT_FANOUT - 1));
1467 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1468 pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1469 pnode->lprops[iip].flags);
1470 return &pnode->lprops[iip];
1471}
1472
1473/**
1474 * dirty_cow_nnode - ensure a nnode is not being committed.
1475 * @c: UBIFS file-system description object
1476 * @nnode: nnode to check
1477 *
1478 * Returns dirtied nnode on success or negative error code on failure.
1479 */
1480static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,
1481 struct ubifs_nnode *nnode)
1482{
1483 struct ubifs_nnode *n;
1484 int i;
1485
1486 if (!test_bit(COW_CNODE, &nnode->flags)) {
1487 /* nnode is not being committed */
1488 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
1489 c->dirty_nn_cnt += 1;
1490 ubifs_add_nnode_dirt(c, nnode);
1491 }
1492 return nnode;
1493 }
1494
1495 /* nnode is being committed, so copy it */
1496 n = kmalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
1497 if (unlikely(!n))
1498 return ERR_PTR(-ENOMEM);
1499
1500 memcpy(n, nnode, sizeof(struct ubifs_nnode));
1501 n->cnext = NULL;
1502 __set_bit(DIRTY_CNODE, &n->flags);
1503 __clear_bit(COW_CNODE, &n->flags);
1504
1505 /* The children now have new parent */
1506 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1507 struct ubifs_nbranch *branch = &n->nbranch[i];
1508
1509 if (branch->cnode)
1510 branch->cnode->parent = n;
1511 }
1512
1513 ubifs_assert(!test_bit(OBSOLETE_CNODE, &nnode->flags));
1514 __set_bit(OBSOLETE_CNODE, &nnode->flags);
1515
1516 c->dirty_nn_cnt += 1;
1517 ubifs_add_nnode_dirt(c, nnode);
1518 if (nnode->parent)
1519 nnode->parent->nbranch[n->iip].nnode = n;
1520 else
1521 c->nroot = n;
1522 return n;
1523}
1524
1525/**
1526 * dirty_cow_pnode - ensure a pnode is not being committed.
1527 * @c: UBIFS file-system description object
1528 * @pnode: pnode to check
1529 *
1530 * Returns dirtied pnode on success or negative error code on failure.
1531 */
1532static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,
1533 struct ubifs_pnode *pnode)
1534{
1535 struct ubifs_pnode *p;
1536
1537 if (!test_bit(COW_CNODE, &pnode->flags)) {
1538 /* pnode is not being committed */
1539 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
1540 c->dirty_pn_cnt += 1;
1541 add_pnode_dirt(c, pnode);
1542 }
1543 return pnode;
1544 }
1545
1546 /* pnode is being committed, so copy it */
1547 p = kmalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
1548 if (unlikely(!p))
1549 return ERR_PTR(-ENOMEM);
1550
1551 memcpy(p, pnode, sizeof(struct ubifs_pnode));
1552 p->cnext = NULL;
1553 __set_bit(DIRTY_CNODE, &p->flags);
1554 __clear_bit(COW_CNODE, &p->flags);
1555 replace_cats(c, pnode, p);
1556
1557 ubifs_assert(!test_bit(OBSOLETE_CNODE, &pnode->flags));
1558 __set_bit(OBSOLETE_CNODE, &pnode->flags);
1559
1560 c->dirty_pn_cnt += 1;
1561 add_pnode_dirt(c, pnode);
1562 pnode->parent->nbranch[p->iip].pnode = p;
1563 return p;
1564}
1565
1566/**
1567 * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
1568 * @c: UBIFS file-system description object
1569 * @lnum: LEB number to lookup
1570 *
1571 * This function returns a pointer to the LEB properties on success or a
1572 * negative error code on failure.
1573 */
1574struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)
1575{
1576 int err, i, h, iip, shft;
1577 struct ubifs_nnode *nnode;
1578 struct ubifs_pnode *pnode;
1579
1580 if (!c->nroot) {
1581 err = ubifs_read_nnode(c, NULL, 0);
1582 if (err)
1583 return ERR_PTR(err);
1584 }
1585 nnode = c->nroot;
1586 nnode = dirty_cow_nnode(c, nnode);
1587 if (IS_ERR(nnode))
1588 return ERR_PTR(PTR_ERR(nnode));
1589 i = lnum - c->main_first;
1590 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1591 for (h = 1; h < c->lpt_hght; h++) {
1592 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1593 shft -= UBIFS_LPT_FANOUT_SHIFT;
1594 nnode = ubifs_get_nnode(c, nnode, iip);
1595 if (IS_ERR(nnode))
1596 return ERR_PTR(PTR_ERR(nnode));
1597 nnode = dirty_cow_nnode(c, nnode);
1598 if (IS_ERR(nnode))
1599 return ERR_PTR(PTR_ERR(nnode));
1600 }
1601 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1602 shft -= UBIFS_LPT_FANOUT_SHIFT;
1603 pnode = ubifs_get_pnode(c, nnode, iip);
1604 if (IS_ERR(pnode))
1605 return ERR_PTR(PTR_ERR(pnode));
1606 pnode = dirty_cow_pnode(c, pnode);
1607 if (IS_ERR(pnode))
1608 return ERR_PTR(PTR_ERR(pnode));
1609 iip = (i & (UBIFS_LPT_FANOUT - 1));
1610 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1611 pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1612 pnode->lprops[iip].flags);
1613 ubifs_assert(test_bit(DIRTY_CNODE, &pnode->flags));
1614 return &pnode->lprops[iip];
1615}
1616
1617/**
1618 * lpt_init_rd - initialize the LPT for reading.
1619 * @c: UBIFS file-system description object
1620 *
1621 * This function returns %0 on success and a negative error code on failure.
1622 */
1623static int lpt_init_rd(struct ubifs_info *c)
1624{
1625 int err, i;
1626
1627 c->ltab = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1628 if (!c->ltab)
1629 return -ENOMEM;
1630
1631 i = max_t(int, c->nnode_sz, c->pnode_sz);
1632 c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);
1633 if (!c->lpt_nod_buf)
1634 return -ENOMEM;
1635
1636 for (i = 0; i < LPROPS_HEAP_CNT; i++) {
1637 c->lpt_heap[i].arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ,
1638 GFP_KERNEL);
1639 if (!c->lpt_heap[i].arr)
1640 return -ENOMEM;
1641 c->lpt_heap[i].cnt = 0;
1642 c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;
1643 }
1644
1645 c->dirty_idx.arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ, GFP_KERNEL);
1646 if (!c->dirty_idx.arr)
1647 return -ENOMEM;
1648 c->dirty_idx.cnt = 0;
1649 c->dirty_idx.max_cnt = LPT_HEAP_SZ;
1650
1651 err = read_ltab(c);
1652 if (err)
1653 return err;
1654
1655 dbg_lp("space_bits %d", c->space_bits);
1656 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
1657 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
1658 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
1659 dbg_lp("pcnt_bits %d", c->pcnt_bits);
1660 dbg_lp("lnum_bits %d", c->lnum_bits);
1661 dbg_lp("pnode_sz %d", c->pnode_sz);
1662 dbg_lp("nnode_sz %d", c->nnode_sz);
1663 dbg_lp("ltab_sz %d", c->ltab_sz);
1664 dbg_lp("lsave_sz %d", c->lsave_sz);
1665 dbg_lp("lsave_cnt %d", c->lsave_cnt);
1666 dbg_lp("lpt_hght %d", c->lpt_hght);
1667 dbg_lp("big_lpt %d", c->big_lpt);
1668 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
1669 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
1670 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
1671 if (c->big_lpt)
1672 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
1673
1674 return 0;
1675}
1676
1677/**
1678 * lpt_init_wr - initialize the LPT for writing.
1679 * @c: UBIFS file-system description object
1680 *
1681 * 'lpt_init_rd()' must have been called already.
1682 *
1683 * This function returns %0 on success and a negative error code on failure.
1684 */
1685static int lpt_init_wr(struct ubifs_info *c)
1686{
1687 int err, i;
1688
1689 c->ltab_cmt = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1690 if (!c->ltab_cmt)
1691 return -ENOMEM;
1692
1693 c->lpt_buf = vmalloc(c->leb_size);
1694 if (!c->lpt_buf)
1695 return -ENOMEM;
1696
1697 if (c->big_lpt) {
1698 c->lsave = kmalloc(sizeof(int) * c->lsave_cnt, GFP_NOFS);
1699 if (!c->lsave)
1700 return -ENOMEM;
1701 err = read_lsave(c);
1702 if (err)
1703 return err;
1704 }
1705
1706 for (i = 0; i < c->lpt_lebs; i++)
1707 if (c->ltab[i].free == c->leb_size) {
1708 err = ubifs_leb_unmap(c, i + c->lpt_first);
1709 if (err)
1710 return err;
1711 }
1712
1713 return 0;
1714}
1715
1716/**
1717 * ubifs_lpt_init - initialize the LPT.
1718 * @c: UBIFS file-system description object
1719 * @rd: whether to initialize lpt for reading
1720 * @wr: whether to initialize lpt for writing
1721 *
1722 * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
1723 * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
1724 * true.
1725 *
1726 * This function returns %0 on success and a negative error code on failure.
1727 */
1728int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)
1729{
1730 int err;
1731
1732 if (rd) {
1733 err = lpt_init_rd(c);
1734 if (err)
1735 return err;
1736 }
1737
1738 if (wr) {
1739 err = lpt_init_wr(c);
1740 if (err)
1741 return err;
1742 }
1743
1744 return 0;
1745}
1746
1747/**
1748 * struct lpt_scan_node - somewhere to put nodes while we scan LPT.
1749 * @nnode: where to keep a nnode
1750 * @pnode: where to keep a pnode
1751 * @cnode: where to keep a cnode
1752 * @in_tree: is the node in the tree in memory
1753 * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in
1754 * the tree
1755 * @ptr.pnode: ditto for pnode
1756 * @ptr.cnode: ditto for cnode
1757 */
1758struct lpt_scan_node {
1759 union {
1760 struct ubifs_nnode nnode;
1761 struct ubifs_pnode pnode;
1762 struct ubifs_cnode cnode;
1763 };
1764 int in_tree;
1765 union {
1766 struct ubifs_nnode *nnode;
1767 struct ubifs_pnode *pnode;
1768 struct ubifs_cnode *cnode;
1769 } ptr;
1770};
1771
1772/**
1773 * scan_get_nnode - for the scan, get a nnode from either the tree or flash.
1774 * @c: the UBIFS file-system description object
1775 * @path: where to put the nnode
1776 * @parent: parent of the nnode
1777 * @iip: index in parent of the nnode
1778 *
1779 * This function returns a pointer to the nnode on success or a negative error
1780 * code on failure.
1781 */
1782static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c,
1783 struct lpt_scan_node *path,
1784 struct ubifs_nnode *parent, int iip)
1785{
1786 struct ubifs_nbranch *branch;
1787 struct ubifs_nnode *nnode;
1788 void *buf = c->lpt_nod_buf;
1789 int err;
1790
1791 branch = &parent->nbranch[iip];
1792 nnode = branch->nnode;
1793 if (nnode) {
1794 path->in_tree = 1;
1795 path->ptr.nnode = nnode;
1796 return nnode;
1797 }
1798 nnode = &path->nnode;
1799 path->in_tree = 0;
1800 path->ptr.nnode = nnode;
1801 memset(nnode, 0, sizeof(struct ubifs_nnode));
1802 if (branch->lnum == 0) {
1803 /*
1804 * This nnode was not written which just means that the LEB
1805 * properties in the subtree below it describe empty LEBs. We
1806 * make the nnode as though we had read it, which in fact means
1807 * doing almost nothing.
1808 */
1809 if (c->big_lpt)
1810 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1811 } else {
1812 err = ubi_read(c->ubi, branch->lnum, buf, branch->offs,
1813 c->nnode_sz);
1814 if (err)
1815 return ERR_PTR(err);
Artem Bityutskiy2ba5f7a2008-10-31 17:32:30 +02001816 err = ubifs_unpack_nnode(c, buf, nnode);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001817 if (err)
1818 return ERR_PTR(err);
1819 }
1820 err = validate_nnode(c, nnode, parent, iip);
1821 if (err)
1822 return ERR_PTR(err);
1823 if (!c->big_lpt)
1824 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1825 nnode->level = parent->level - 1;
1826 nnode->parent = parent;
1827 nnode->iip = iip;
1828 return nnode;
1829}
1830
1831/**
1832 * scan_get_pnode - for the scan, get a pnode from either the tree or flash.
1833 * @c: the UBIFS file-system description object
1834 * @path: where to put the pnode
1835 * @parent: parent of the pnode
1836 * @iip: index in parent of the pnode
1837 *
1838 * This function returns a pointer to the pnode on success or a negative error
1839 * code on failure.
1840 */
1841static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c,
1842 struct lpt_scan_node *path,
1843 struct ubifs_nnode *parent, int iip)
1844{
1845 struct ubifs_nbranch *branch;
1846 struct ubifs_pnode *pnode;
1847 void *buf = c->lpt_nod_buf;
1848 int err;
1849
1850 branch = &parent->nbranch[iip];
1851 pnode = branch->pnode;
1852 if (pnode) {
1853 path->in_tree = 1;
1854 path->ptr.pnode = pnode;
1855 return pnode;
1856 }
1857 pnode = &path->pnode;
1858 path->in_tree = 0;
1859 path->ptr.pnode = pnode;
1860 memset(pnode, 0, sizeof(struct ubifs_pnode));
1861 if (branch->lnum == 0) {
1862 /*
1863 * This pnode was not written which just means that the LEB
1864 * properties in it describe empty LEBs. We make the pnode as
1865 * though we had read it.
1866 */
1867 int i;
1868
1869 if (c->big_lpt)
1870 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1871 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1872 struct ubifs_lprops * const lprops = &pnode->lprops[i];
1873
1874 lprops->free = c->leb_size;
1875 lprops->flags = ubifs_categorize_lprops(c, lprops);
1876 }
1877 } else {
1878 ubifs_assert(branch->lnum >= c->lpt_first &&
1879 branch->lnum <= c->lpt_last);
1880 ubifs_assert(branch->offs >= 0 && branch->offs < c->leb_size);
1881 err = ubi_read(c->ubi, branch->lnum, buf, branch->offs,
1882 c->pnode_sz);
1883 if (err)
1884 return ERR_PTR(err);
1885 err = unpack_pnode(c, buf, pnode);
1886 if (err)
1887 return ERR_PTR(err);
1888 }
1889 err = validate_pnode(c, pnode, parent, iip);
1890 if (err)
1891 return ERR_PTR(err);
1892 if (!c->big_lpt)
1893 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1894 pnode->parent = parent;
1895 pnode->iip = iip;
1896 set_pnode_lnum(c, pnode);
1897 return pnode;
1898}
1899
1900/**
1901 * ubifs_lpt_scan_nolock - scan the LPT.
1902 * @c: the UBIFS file-system description object
1903 * @start_lnum: LEB number from which to start scanning
1904 * @end_lnum: LEB number at which to stop scanning
1905 * @scan_cb: callback function called for each lprops
1906 * @data: data to be passed to the callback function
1907 *
1908 * This function returns %0 on success and a negative error code on failure.
1909 */
1910int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum,
1911 ubifs_lpt_scan_callback scan_cb, void *data)
1912{
1913 int err = 0, i, h, iip, shft;
1914 struct ubifs_nnode *nnode;
1915 struct ubifs_pnode *pnode;
1916 struct lpt_scan_node *path;
1917
1918 if (start_lnum == -1) {
1919 start_lnum = end_lnum + 1;
1920 if (start_lnum >= c->leb_cnt)
1921 start_lnum = c->main_first;
1922 }
1923
1924 ubifs_assert(start_lnum >= c->main_first && start_lnum < c->leb_cnt);
1925 ubifs_assert(end_lnum >= c->main_first && end_lnum < c->leb_cnt);
1926
1927 if (!c->nroot) {
1928 err = ubifs_read_nnode(c, NULL, 0);
1929 if (err)
1930 return err;
1931 }
1932
1933 path = kmalloc(sizeof(struct lpt_scan_node) * (c->lpt_hght + 1),
1934 GFP_NOFS);
1935 if (!path)
1936 return -ENOMEM;
1937
1938 path[0].ptr.nnode = c->nroot;
1939 path[0].in_tree = 1;
1940again:
1941 /* Descend to the pnode containing start_lnum */
1942 nnode = c->nroot;
1943 i = start_lnum - c->main_first;
1944 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1945 for (h = 1; h < c->lpt_hght; h++) {
1946 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1947 shft -= UBIFS_LPT_FANOUT_SHIFT;
1948 nnode = scan_get_nnode(c, path + h, nnode, iip);
1949 if (IS_ERR(nnode)) {
1950 err = PTR_ERR(nnode);
1951 goto out;
1952 }
1953 }
1954 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1955 shft -= UBIFS_LPT_FANOUT_SHIFT;
1956 pnode = scan_get_pnode(c, path + h, nnode, iip);
1957 if (IS_ERR(pnode)) {
1958 err = PTR_ERR(pnode);
1959 goto out;
1960 }
1961 iip = (i & (UBIFS_LPT_FANOUT - 1));
1962
1963 /* Loop for each lprops */
1964 while (1) {
1965 struct ubifs_lprops *lprops = &pnode->lprops[iip];
1966 int ret, lnum = lprops->lnum;
1967
1968 ret = scan_cb(c, lprops, path[h].in_tree, data);
1969 if (ret < 0) {
1970 err = ret;
1971 goto out;
1972 }
1973 if (ret & LPT_SCAN_ADD) {
1974 /* Add all the nodes in path to the tree in memory */
1975 for (h = 1; h < c->lpt_hght; h++) {
1976 const size_t sz = sizeof(struct ubifs_nnode);
1977 struct ubifs_nnode *parent;
1978
1979 if (path[h].in_tree)
1980 continue;
1981 nnode = kmalloc(sz, GFP_NOFS);
1982 if (!nnode) {
1983 err = -ENOMEM;
1984 goto out;
1985 }
1986 memcpy(nnode, &path[h].nnode, sz);
1987 parent = nnode->parent;
1988 parent->nbranch[nnode->iip].nnode = nnode;
1989 path[h].ptr.nnode = nnode;
1990 path[h].in_tree = 1;
1991 path[h + 1].cnode.parent = nnode;
1992 }
1993 if (path[h].in_tree)
1994 ubifs_ensure_cat(c, lprops);
1995 else {
1996 const size_t sz = sizeof(struct ubifs_pnode);
1997 struct ubifs_nnode *parent;
1998
1999 pnode = kmalloc(sz, GFP_NOFS);
2000 if (!pnode) {
2001 err = -ENOMEM;
2002 goto out;
2003 }
2004 memcpy(pnode, &path[h].pnode, sz);
2005 parent = pnode->parent;
2006 parent->nbranch[pnode->iip].pnode = pnode;
2007 path[h].ptr.pnode = pnode;
2008 path[h].in_tree = 1;
2009 update_cats(c, pnode);
2010 c->pnodes_have += 1;
2011 }
2012 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)
2013 c->nroot, 0, 0);
2014 if (err)
2015 goto out;
2016 err = dbg_check_cats(c);
2017 if (err)
2018 goto out;
2019 }
2020 if (ret & LPT_SCAN_STOP) {
2021 err = 0;
2022 break;
2023 }
2024 /* Get the next lprops */
2025 if (lnum == end_lnum) {
2026 /*
2027 * We got to the end without finding what we were
2028 * looking for
2029 */
2030 err = -ENOSPC;
2031 goto out;
2032 }
2033 if (lnum + 1 >= c->leb_cnt) {
2034 /* Wrap-around to the beginning */
2035 start_lnum = c->main_first;
2036 goto again;
2037 }
2038 if (iip + 1 < UBIFS_LPT_FANOUT) {
2039 /* Next lprops is in the same pnode */
2040 iip += 1;
2041 continue;
2042 }
2043 /* We need to get the next pnode. Go up until we can go right */
2044 iip = pnode->iip;
2045 while (1) {
2046 h -= 1;
2047 ubifs_assert(h >= 0);
2048 nnode = path[h].ptr.nnode;
2049 if (iip + 1 < UBIFS_LPT_FANOUT)
2050 break;
2051 iip = nnode->iip;
2052 }
2053 /* Go right */
2054 iip += 1;
2055 /* Descend to the pnode */
2056 h += 1;
2057 for (; h < c->lpt_hght; h++) {
2058 nnode = scan_get_nnode(c, path + h, nnode, iip);
2059 if (IS_ERR(nnode)) {
2060 err = PTR_ERR(nnode);
2061 goto out;
2062 }
2063 iip = 0;
2064 }
2065 pnode = scan_get_pnode(c, path + h, nnode, iip);
2066 if (IS_ERR(pnode)) {
2067 err = PTR_ERR(pnode);
2068 goto out;
2069 }
2070 iip = 0;
2071 }
2072out:
2073 kfree(path);
2074 return err;
2075}
2076
2077#ifdef CONFIG_UBIFS_FS_DEBUG
2078
2079/**
2080 * dbg_chk_pnode - check a pnode.
2081 * @c: the UBIFS file-system description object
2082 * @pnode: pnode to check
2083 * @col: pnode column
2084 *
2085 * This function returns %0 on success and a negative error code on failure.
2086 */
2087static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode,
2088 int col)
2089{
2090 int i;
2091
2092 if (pnode->num != col) {
2093 dbg_err("pnode num %d expected %d parent num %d iip %d",
2094 pnode->num, col, pnode->parent->num, pnode->iip);
2095 return -EINVAL;
2096 }
2097 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
2098 struct ubifs_lprops *lp, *lprops = &pnode->lprops[i];
2099 int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i +
2100 c->main_first;
2101 int found, cat = lprops->flags & LPROPS_CAT_MASK;
2102 struct ubifs_lpt_heap *heap;
2103 struct list_head *list = NULL;
2104
2105 if (lnum >= c->leb_cnt)
2106 continue;
2107 if (lprops->lnum != lnum) {
2108 dbg_err("bad LEB number %d expected %d",
2109 lprops->lnum, lnum);
2110 return -EINVAL;
2111 }
2112 if (lprops->flags & LPROPS_TAKEN) {
2113 if (cat != LPROPS_UNCAT) {
2114 dbg_err("LEB %d taken but not uncat %d",
2115 lprops->lnum, cat);
2116 return -EINVAL;
2117 }
2118 continue;
2119 }
2120 if (lprops->flags & LPROPS_INDEX) {
2121 switch (cat) {
2122 case LPROPS_UNCAT:
2123 case LPROPS_DIRTY_IDX:
2124 case LPROPS_FRDI_IDX:
2125 break;
2126 default:
2127 dbg_err("LEB %d index but cat %d",
2128 lprops->lnum, cat);
2129 return -EINVAL;
2130 }
2131 } else {
2132 switch (cat) {
2133 case LPROPS_UNCAT:
2134 case LPROPS_DIRTY:
2135 case LPROPS_FREE:
2136 case LPROPS_EMPTY:
2137 case LPROPS_FREEABLE:
2138 break;
2139 default:
2140 dbg_err("LEB %d not index but cat %d",
2141 lprops->lnum, cat);
2142 return -EINVAL;
2143 }
2144 }
2145 switch (cat) {
2146 case LPROPS_UNCAT:
2147 list = &c->uncat_list;
2148 break;
2149 case LPROPS_EMPTY:
2150 list = &c->empty_list;
2151 break;
2152 case LPROPS_FREEABLE:
2153 list = &c->freeable_list;
2154 break;
2155 case LPROPS_FRDI_IDX:
2156 list = &c->frdi_idx_list;
2157 break;
2158 }
2159 found = 0;
2160 switch (cat) {
2161 case LPROPS_DIRTY:
2162 case LPROPS_DIRTY_IDX:
2163 case LPROPS_FREE:
2164 heap = &c->lpt_heap[cat - 1];
2165 if (lprops->hpos < heap->cnt &&
2166 heap->arr[lprops->hpos] == lprops)
2167 found = 1;
2168 break;
2169 case LPROPS_UNCAT:
2170 case LPROPS_EMPTY:
2171 case LPROPS_FREEABLE:
2172 case LPROPS_FRDI_IDX:
2173 list_for_each_entry(lp, list, list)
2174 if (lprops == lp) {
2175 found = 1;
2176 break;
2177 }
2178 break;
2179 }
2180 if (!found) {
2181 dbg_err("LEB %d cat %d not found in cat heap/list",
2182 lprops->lnum, cat);
2183 return -EINVAL;
2184 }
2185 switch (cat) {
2186 case LPROPS_EMPTY:
2187 if (lprops->free != c->leb_size) {
2188 dbg_err("LEB %d cat %d free %d dirty %d",
2189 lprops->lnum, cat, lprops->free,
2190 lprops->dirty);
2191 return -EINVAL;
2192 }
2193 case LPROPS_FREEABLE:
2194 case LPROPS_FRDI_IDX:
2195 if (lprops->free + lprops->dirty != c->leb_size) {
2196 dbg_err("LEB %d cat %d free %d dirty %d",
2197 lprops->lnum, cat, lprops->free,
2198 lprops->dirty);
2199 return -EINVAL;
2200 }
2201 }
2202 }
2203 return 0;
2204}
2205
2206/**
2207 * dbg_check_lpt_nodes - check nnodes and pnodes.
2208 * @c: the UBIFS file-system description object
2209 * @cnode: next cnode (nnode or pnode) to check
2210 * @row: row of cnode (root is zero)
2211 * @col: column of cnode (leftmost is zero)
2212 *
2213 * This function returns %0 on success and a negative error code on failure.
2214 */
2215int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode,
2216 int row, int col)
2217{
2218 struct ubifs_nnode *nnode, *nn;
2219 struct ubifs_cnode *cn;
2220 int num, iip = 0, err;
2221
2222 if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
2223 return 0;
2224
2225 while (cnode) {
2226 ubifs_assert(row >= 0);
2227 nnode = cnode->parent;
2228 if (cnode->level) {
2229 /* cnode is a nnode */
2230 num = calc_nnode_num(row, col);
2231 if (cnode->num != num) {
2232 dbg_err("nnode num %d expected %d "
2233 "parent num %d iip %d", cnode->num, num,
2234 (nnode ? nnode->num : 0), cnode->iip);
2235 return -EINVAL;
2236 }
2237 nn = (struct ubifs_nnode *)cnode;
2238 while (iip < UBIFS_LPT_FANOUT) {
2239 cn = nn->nbranch[iip].cnode;
2240 if (cn) {
2241 /* Go down */
2242 row += 1;
2243 col <<= UBIFS_LPT_FANOUT_SHIFT;
2244 col += iip;
2245 iip = 0;
2246 cnode = cn;
2247 break;
2248 }
2249 /* Go right */
2250 iip += 1;
2251 }
2252 if (iip < UBIFS_LPT_FANOUT)
2253 continue;
2254 } else {
2255 struct ubifs_pnode *pnode;
2256
2257 /* cnode is a pnode */
2258 pnode = (struct ubifs_pnode *)cnode;
2259 err = dbg_chk_pnode(c, pnode, col);
2260 if (err)
2261 return err;
2262 }
2263 /* Go up and to the right */
2264 row -= 1;
2265 col >>= UBIFS_LPT_FANOUT_SHIFT;
2266 iip = cnode->iip + 1;
2267 cnode = (struct ubifs_cnode *)nnode;
2268 }
2269 return 0;
2270}
2271
2272#endif /* CONFIG_UBIFS_FS_DEBUG */