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