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