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
610int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first,
611 int *lpt_lebs, int *big_lpt)
612{
613 int lnum, err = 0, node_sz, iopos, i, j, cnt, len, alen, row;
614 int blnum, boffs, bsz, bcnt;
615 struct ubifs_pnode *pnode = NULL;
616 struct ubifs_nnode *nnode = NULL;
617 void *buf = NULL, *p;
618 struct ubifs_lpt_lprops *ltab = NULL;
619 int *lsave = NULL;
620
621 err = calc_dflt_lpt_geom(c, main_lebs, big_lpt);
622 if (err)
623 return err;
624 *lpt_lebs = c->lpt_lebs;
625
626
627 c->lpt_first = lpt_first;
628
629 c->lpt_last = lpt_first + c->lpt_lebs - 1;
630
631 c->main_first = c->leb_cnt - *main_lebs;
632
633 lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_KERNEL);
634 pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_KERNEL);
635 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_KERNEL);
636 buf = vmalloc(c->leb_size);
637 ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
638 c->lpt_lebs));
639 if (!pnode || !nnode || !buf || !ltab || !lsave) {
640 err = -ENOMEM;
641 goto out;
642 }
643
644 ubifs_assert(c, !c->ltab);
645 c->ltab = ltab;
646
647
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
658 cnt = c->pnode_cnt;
659
660
661
662
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
679 ubifs_pack_pnode(c, p, pnode);
680 p += c->pnode_sz;
681 len = c->pnode_sz;
682 pnode->num += 1;
683
684
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
694
695
696 blnum = lnum;
697 boffs = 0;
698 bcnt = cnt;
699 bsz = c->pnode_sz;
700
701
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 = ubifs_leb_change(c, lnum++, buf, alen);
708 if (err)
709 goto out;
710 p = buf;
711 len = 0;
712 }
713 ubifs_pack_pnode(c, p, pnode);
714 p += c->pnode_sz;
715 len += c->pnode_sz;
716
717
718
719
720
721 pnode->num += 1;
722 }
723
724 row = 0;
725 for (i = UBIFS_LPT_FANOUT; cnt > i; i <<= UBIFS_LPT_FANOUT_SHIFT)
726 row += 1;
727
728 while (1) {
729
730 cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT);
731 for (i = 0; i < cnt; i++) {
732 if (len + c->nnode_sz > c->leb_size) {
733 alen = ALIGN(len, c->min_io_size);
734 set_ltab(c, lnum, c->leb_size - alen,
735 alen - len);
736 memset(p, 0xff, alen - len);
737 err = ubifs_leb_change(c, lnum++, buf, alen);
738 if (err)
739 goto out;
740 p = buf;
741 len = 0;
742 }
743
744 if (cnt == 1) {
745 c->lpt_lnum = lnum;
746 c->lpt_offs = len;
747 }
748
749 for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
750 if (bcnt) {
751 if (boffs + bsz > c->leb_size) {
752 blnum += 1;
753 boffs = 0;
754 }
755 nnode->nbranch[j].lnum = blnum;
756 nnode->nbranch[j].offs = boffs;
757 boffs += bsz;
758 bcnt--;
759 } else {
760 nnode->nbranch[j].lnum = 0;
761 nnode->nbranch[j].offs = 0;
762 }
763 }
764 nnode->num = calc_nnode_num(row, i);
765 ubifs_pack_nnode(c, p, nnode);
766 p += c->nnode_sz;
767 len += c->nnode_sz;
768 }
769
770 if (cnt == 1)
771 break;
772
773 bcnt = cnt;
774 bsz = c->nnode_sz;
775 row -= 1;
776 }
777
778 if (*big_lpt) {
779
780 if (len + c->lsave_sz > c->leb_size) {
781 alen = ALIGN(len, c->min_io_size);
782 set_ltab(c, lnum, c->leb_size - alen, alen - len);
783 memset(p, 0xff, alen - len);
784 err = ubifs_leb_change(c, lnum++, buf, alen);
785 if (err)
786 goto out;
787 p = buf;
788 len = 0;
789 }
790
791 c->lsave_lnum = lnum;
792 c->lsave_offs = len;
793
794 for (i = 0; i < c->lsave_cnt && i < *main_lebs; i++)
795 lsave[i] = c->main_first + i;
796 for (; i < c->lsave_cnt; i++)
797 lsave[i] = c->main_first;
798
799 ubifs_pack_lsave(c, p, lsave);
800 p += c->lsave_sz;
801 len += c->lsave_sz;
802 }
803
804
805 if (len + c->ltab_sz > c->leb_size) {
806 alen = ALIGN(len, c->min_io_size);
807 set_ltab(c, lnum, c->leb_size - alen, alen - len);
808 memset(p, 0xff, alen - len);
809 err = ubifs_leb_change(c, lnum++, buf, alen);
810 if (err)
811 goto out;
812 p = buf;
813 len = 0;
814 }
815
816 c->ltab_lnum = lnum;
817 c->ltab_offs = len;
818
819
820 len += c->ltab_sz;
821 alen = ALIGN(len, c->min_io_size);
822 set_ltab(c, lnum, c->leb_size - alen, alen - len);
823
824 ubifs_pack_ltab(c, p, ltab);
825 p += c->ltab_sz;
826
827
828 memset(p, 0xff, alen - len);
829 err = ubifs_leb_change(c, lnum, buf, alen);
830 if (err)
831 goto out;
832
833 c->nhead_lnum = lnum;
834 c->nhead_offs = ALIGN(len, c->min_io_size);
835
836 dbg_lp("space_bits %d", c->space_bits);
837 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
838 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
839 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
840 dbg_lp("pcnt_bits %d", c->pcnt_bits);
841 dbg_lp("lnum_bits %d", c->lnum_bits);
842 dbg_lp("pnode_sz %d", c->pnode_sz);
843 dbg_lp("nnode_sz %d", c->nnode_sz);
844 dbg_lp("ltab_sz %d", c->ltab_sz);
845 dbg_lp("lsave_sz %d", c->lsave_sz);
846 dbg_lp("lsave_cnt %d", c->lsave_cnt);
847 dbg_lp("lpt_hght %d", c->lpt_hght);
848 dbg_lp("big_lpt %d", c->big_lpt);
849 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
850 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
851 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
852 if (c->big_lpt)
853 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
854out:
855 c->ltab = NULL;
856 kfree(lsave);
857 vfree(ltab);
858 vfree(buf);
859 kfree(nnode);
860 kfree(pnode);
861 return err;
862}
863
864
865
866
867
868
869
870
871
872static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)
873{
874 int i;
875
876 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
877 int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;
878 int lnum = pnode->lprops[i].lnum;
879
880 if (!lnum)
881 return;
882 ubifs_add_to_cat(c, &pnode->lprops[i], cat);
883 }
884}
885
886
887
888
889
890
891
892
893
894
895
896static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,
897 struct ubifs_pnode *new_pnode)
898{
899 int i;
900
901 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
902 if (!new_pnode->lprops[i].lnum)
903 return;
904 ubifs_replace_cat(c, &old_pnode->lprops[i],
905 &new_pnode->lprops[i]);
906 }
907}
908
909
910
911
912
913
914
915
916
917static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len)
918{
919 int pos = 0;
920 uint8_t *addr = buf;
921 uint16_t crc, calc_crc;
922
923 crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);
924 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
925 len - UBIFS_LPT_CRC_BYTES);
926 if (crc != calc_crc) {
927 ubifs_err(c, "invalid crc in LPT node: crc %hx calc %hx",
928 crc, calc_crc);
929 dump_stack();
930 return -EINVAL;
931 }
932 return 0;
933}
934
935
936
937
938
939
940
941
942
943
944static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr,
945 int *pos, int type)
946{
947 int node_type;
948
949 node_type = ubifs_unpack_bits(c, addr, pos, UBIFS_LPT_TYPE_BITS);
950 if (node_type != type) {
951 ubifs_err(c, "invalid type (%d) in LPT node type %d",
952 node_type, type);
953 dump_stack();
954 return -EINVAL;
955 }
956 return 0;
957}
958
959
960
961
962
963
964
965
966
967static int unpack_pnode(const struct ubifs_info *c, void *buf,
968 struct ubifs_pnode *pnode)
969{
970 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
971 int i, pos = 0, err;
972
973 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_PNODE);
974 if (err)
975 return err;
976 if (c->big_lpt)
977 pnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
978 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
979 struct ubifs_lprops * const lprops = &pnode->lprops[i];
980
981 lprops->free = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);
982 lprops->free <<= 3;
983 lprops->dirty = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);
984 lprops->dirty <<= 3;
985
986 if (ubifs_unpack_bits(c, &addr, &pos, 1))
987 lprops->flags = LPROPS_INDEX;
988 else
989 lprops->flags = 0;
990 lprops->flags |= ubifs_categorize_lprops(c, lprops);
991 }
992 err = check_lpt_crc(c, buf, c->pnode_sz);
993 return err;
994}
995
996
997
998
999
1000
1001
1002
1003
1004int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,
1005 struct ubifs_nnode *nnode)
1006{
1007 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1008 int i, pos = 0, err;
1009
1010 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_NNODE);
1011 if (err)
1012 return err;
1013 if (c->big_lpt)
1014 nnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
1015 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1016 int lnum;
1017
1018 lnum = ubifs_unpack_bits(c, &addr, &pos, c->lpt_lnum_bits) +
1019 c->lpt_first;
1020 if (lnum == c->lpt_last + 1)
1021 lnum = 0;
1022 nnode->nbranch[i].lnum = lnum;
1023 nnode->nbranch[i].offs = ubifs_unpack_bits(c, &addr, &pos,
1024 c->lpt_offs_bits);
1025 }
1026 err = check_lpt_crc(c, buf, c->nnode_sz);
1027 return err;
1028}
1029
1030
1031
1032
1033
1034
1035
1036
1037static int unpack_ltab(const struct ubifs_info *c, void *buf)
1038{
1039 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1040 int i, pos = 0, err;
1041
1042 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LTAB);
1043 if (err)
1044 return err;
1045 for (i = 0; i < c->lpt_lebs; i++) {
1046 int free = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);
1047 int dirty = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);
1048
1049 if (free < 0 || free > c->leb_size || dirty < 0 ||
1050 dirty > c->leb_size || free + dirty > c->leb_size)
1051 return -EINVAL;
1052
1053 c->ltab[i].free = free;
1054 c->ltab[i].dirty = dirty;
1055 c->ltab[i].tgc = 0;
1056 c->ltab[i].cmt = 0;
1057 }
1058 err = check_lpt_crc(c, buf, c->ltab_sz);
1059 return err;
1060}
1061
1062
1063
1064
1065
1066
1067
1068
1069static int unpack_lsave(const struct ubifs_info *c, void *buf)
1070{
1071 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1072 int i, pos = 0, err;
1073
1074 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LSAVE);
1075 if (err)
1076 return err;
1077 for (i = 0; i < c->lsave_cnt; i++) {
1078 int lnum = ubifs_unpack_bits(c, &addr, &pos, c->lnum_bits);
1079
1080 if (lnum < c->main_first || lnum >= c->leb_cnt)
1081 return -EINVAL;
1082 c->lsave[i] = lnum;
1083 }
1084 err = check_lpt_crc(c, buf, c->lsave_sz);
1085 return err;
1086}
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,
1098 struct ubifs_nnode *parent, int iip)
1099{
1100 int i, lvl, max_offs;
1101
1102 if (c->big_lpt) {
1103 int num = calc_nnode_num_from_parent(c, parent, iip);
1104
1105 if (nnode->num != num)
1106 return -EINVAL;
1107 }
1108 lvl = parent ? parent->level - 1 : c->lpt_hght;
1109 if (lvl < 1)
1110 return -EINVAL;
1111 if (lvl == 1)
1112 max_offs = c->leb_size - c->pnode_sz;
1113 else
1114 max_offs = c->leb_size - c->nnode_sz;
1115 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1116 int lnum = nnode->nbranch[i].lnum;
1117 int offs = nnode->nbranch[i].offs;
1118
1119 if (lnum == 0) {
1120 if (offs != 0)
1121 return -EINVAL;
1122 continue;
1123 }
1124 if (lnum < c->lpt_first || lnum > c->lpt_last)
1125 return -EINVAL;
1126 if (offs < 0 || offs > max_offs)
1127 return -EINVAL;
1128 }
1129 return 0;
1130}
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,
1142 struct ubifs_nnode *parent, int iip)
1143{
1144 int i;
1145
1146 if (c->big_lpt) {
1147 int num = calc_pnode_num_from_parent(c, parent, iip);
1148
1149 if (pnode->num != num)
1150 return -EINVAL;
1151 }
1152 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1153 int free = pnode->lprops[i].free;
1154 int dirty = pnode->lprops[i].dirty;
1155
1156 if (free < 0 || free > c->leb_size || free % c->min_io_size ||
1157 (free & 7))
1158 return -EINVAL;
1159 if (dirty < 0 || dirty > c->leb_size || (dirty & 7))
1160 return -EINVAL;
1161 if (dirty + free > c->leb_size)
1162 return -EINVAL;
1163 }
1164 return 0;
1165}
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175static void set_pnode_lnum(const struct ubifs_info *c,
1176 struct ubifs_pnode *pnode)
1177{
1178 int i, lnum;
1179
1180 lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;
1181 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1182 if (lnum >= c->leb_cnt)
1183 return;
1184 pnode->lprops[i].lnum = lnum++;
1185 }
1186}
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
1197{
1198 struct ubifs_nbranch *branch = NULL;
1199 struct ubifs_nnode *nnode = NULL;
1200 void *buf = c->lpt_nod_buf;
1201 int err, lnum, offs;
1202
1203 if (parent) {
1204 branch = &parent->nbranch[iip];
1205 lnum = branch->lnum;
1206 offs = branch->offs;
1207 } else {
1208 lnum = c->lpt_lnum;
1209 offs = c->lpt_offs;
1210 }
1211 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
1212 if (!nnode) {
1213 err = -ENOMEM;
1214 goto out;
1215 }
1216 if (lnum == 0) {
1217
1218
1219
1220
1221
1222
1223 if (c->big_lpt)
1224 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1225 } else {
1226 err = ubifs_leb_read(c, lnum, buf, offs, c->nnode_sz, 1);
1227 if (err)
1228 goto out;
1229 err = ubifs_unpack_nnode(c, buf, nnode);
1230 if (err)
1231 goto out;
1232 }
1233 err = validate_nnode(c, nnode, parent, iip);
1234 if (err)
1235 goto out;
1236 if (!c->big_lpt)
1237 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1238 if (parent) {
1239 branch->nnode = nnode;
1240 nnode->level = parent->level - 1;
1241 } else {
1242 c->nroot = nnode;
1243 nnode->level = c->lpt_hght;
1244 }
1245 nnode->parent = parent;
1246 nnode->iip = iip;
1247 return 0;
1248
1249out:
1250 ubifs_err(c, "error %d reading nnode at %d:%d", err, lnum, offs);
1251 dump_stack();
1252 kfree(nnode);
1253 return err;
1254}
1255
1256
1257
1258
1259
1260
1261
1262
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 return -ENOMEM;
1277
1278 if (lnum == 0) {
1279
1280
1281
1282
1283
1284 int i;
1285
1286 if (c->big_lpt)
1287 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1288 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1289 struct ubifs_lprops * const lprops = &pnode->lprops[i];
1290
1291 lprops->free = c->leb_size;
1292 lprops->flags = ubifs_categorize_lprops(c, lprops);
1293 }
1294 } else {
1295 err = ubifs_leb_read(c, lnum, buf, offs, c->pnode_sz, 1);
1296 if (err)
1297 goto out;
1298 err = unpack_pnode(c, buf, pnode);
1299 if (err)
1300 goto out;
1301 }
1302 err = validate_pnode(c, pnode, parent, iip);
1303 if (err)
1304 goto out;
1305 if (!c->big_lpt)
1306 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1307 branch->pnode = pnode;
1308 pnode->parent = parent;
1309 pnode->iip = iip;
1310 set_pnode_lnum(c, pnode);
1311 c->pnodes_have += 1;
1312 return 0;
1313
1314out:
1315 ubifs_err(c, "error %d reading pnode at %d:%d", err, lnum, offs);
1316 ubifs_dump_pnode(c, pnode, parent, iip);
1317 dump_stack();
1318 ubifs_err(c, "calc num: %d", calc_pnode_num_from_parent(c, parent, iip));
1319 kfree(pnode);
1320 return err;
1321}
1322
1323
1324
1325
1326
1327
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 = ubifs_leb_read(c, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz, 1);
1338 if (err)
1339 goto out;
1340 err = unpack_ltab(c, buf);
1341out:
1342 vfree(buf);
1343 return err;
1344}
1345
1346
1347
1348
1349
1350
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 = ubifs_leb_read(c, c->lsave_lnum, buf, c->lsave_offs,
1361 c->lsave_sz, 1);
1362 if (err)
1363 goto out;
1364 err = unpack_lsave(c, buf);
1365 if (err)
1366 goto out;
1367 for (i = 0; i < c->lsave_cnt; i++) {
1368 int lnum = c->lsave[i];
1369 struct ubifs_lprops *lprops;
1370
1371
1372
1373
1374
1375 if (lnum >= c->leb_cnt)
1376 continue;
1377 lprops = ubifs_lpt_lookup(c, lnum);
1378 if (IS_ERR(lprops)) {
1379 err = PTR_ERR(lprops);
1380 goto out;
1381 }
1382 }
1383out:
1384 vfree(buf);
1385 return err;
1386}
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,
1398 struct ubifs_nnode *parent, int iip)
1399{
1400 struct ubifs_nbranch *branch;
1401 struct ubifs_nnode *nnode;
1402 int err;
1403
1404 branch = &parent->nbranch[iip];
1405 nnode = branch->nnode;
1406 if (nnode)
1407 return nnode;
1408 err = ubifs_read_nnode(c, parent, iip);
1409 if (err)
1410 return ERR_PTR(err);
1411 return branch->nnode;
1412}
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,
1424 struct ubifs_nnode *parent, int iip)
1425{
1426 struct ubifs_nbranch *branch;
1427 struct ubifs_pnode *pnode;
1428 int err;
1429
1430 branch = &parent->nbranch[iip];
1431 pnode = branch->pnode;
1432 if (pnode)
1433 return pnode;
1434 err = read_pnode(c, parent, iip);
1435 if (err)
1436 return ERR_PTR(err);
1437 update_cats(c, branch->pnode);
1438 return branch->pnode;
1439}
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)
1450{
1451 int err, i, h, iip, shft;
1452 struct ubifs_nnode *nnode;
1453 struct ubifs_pnode *pnode;
1454
1455 if (!c->nroot) {
1456 err = ubifs_read_nnode(c, NULL, 0);
1457 if (err)
1458 return ERR_PTR(err);
1459 }
1460 nnode = c->nroot;
1461 i = lnum - c->main_first;
1462 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1463 for (h = 1; h < c->lpt_hght; h++) {
1464 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1465 shft -= UBIFS_LPT_FANOUT_SHIFT;
1466 nnode = ubifs_get_nnode(c, nnode, iip);
1467 if (IS_ERR(nnode))
1468 return ERR_CAST(nnode);
1469 }
1470 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1471 pnode = ubifs_get_pnode(c, nnode, iip);
1472 if (IS_ERR(pnode))
1473 return ERR_CAST(pnode);
1474 iip = (i & (UBIFS_LPT_FANOUT - 1));
1475 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1476 pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1477 pnode->lprops[iip].flags);
1478 return &pnode->lprops[iip];
1479}
1480
1481
1482
1483
1484
1485
1486
1487
1488static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,
1489 struct ubifs_nnode *nnode)
1490{
1491 struct ubifs_nnode *n;
1492 int i;
1493
1494 if (!test_bit(COW_CNODE, &nnode->flags)) {
1495
1496 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
1497 c->dirty_nn_cnt += 1;
1498 ubifs_add_nnode_dirt(c, nnode);
1499 }
1500 return nnode;
1501 }
1502
1503
1504 n = kmemdup(nnode, sizeof(struct ubifs_nnode), GFP_NOFS);
1505 if (unlikely(!n))
1506 return ERR_PTR(-ENOMEM);
1507
1508 n->cnext = NULL;
1509 __set_bit(DIRTY_CNODE, &n->flags);
1510 __clear_bit(COW_CNODE, &n->flags);
1511
1512
1513 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1514 struct ubifs_nbranch *branch = &n->nbranch[i];
1515
1516 if (branch->cnode)
1517 branch->cnode->parent = n;
1518 }
1519
1520 ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &nnode->flags));
1521 __set_bit(OBSOLETE_CNODE, &nnode->flags);
1522
1523 c->dirty_nn_cnt += 1;
1524 ubifs_add_nnode_dirt(c, nnode);
1525 if (nnode->parent)
1526 nnode->parent->nbranch[n->iip].nnode = n;
1527 else
1528 c->nroot = n;
1529 return n;
1530}
1531
1532
1533
1534
1535
1536
1537
1538
1539static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,
1540 struct ubifs_pnode *pnode)
1541{
1542 struct ubifs_pnode *p;
1543
1544 if (!test_bit(COW_CNODE, &pnode->flags)) {
1545
1546 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
1547 c->dirty_pn_cnt += 1;
1548 add_pnode_dirt(c, pnode);
1549 }
1550 return pnode;
1551 }
1552
1553
1554 p = kmemdup(pnode, sizeof(struct ubifs_pnode), GFP_NOFS);
1555 if (unlikely(!p))
1556 return ERR_PTR(-ENOMEM);
1557
1558 p->cnext = NULL;
1559 __set_bit(DIRTY_CNODE, &p->flags);
1560 __clear_bit(COW_CNODE, &p->flags);
1561 replace_cats(c, pnode, p);
1562
1563 ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &pnode->flags));
1564 __set_bit(OBSOLETE_CNODE, &pnode->flags);
1565
1566 c->dirty_pn_cnt += 1;
1567 add_pnode_dirt(c, pnode);
1568 pnode->parent->nbranch[p->iip].pnode = p;
1569 return p;
1570}
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)
1581{
1582 int err, i, h, iip, shft;
1583 struct ubifs_nnode *nnode;
1584 struct ubifs_pnode *pnode;
1585
1586 if (!c->nroot) {
1587 err = ubifs_read_nnode(c, NULL, 0);
1588 if (err)
1589 return ERR_PTR(err);
1590 }
1591 nnode = c->nroot;
1592 nnode = dirty_cow_nnode(c, nnode);
1593 if (IS_ERR(nnode))
1594 return ERR_CAST(nnode);
1595 i = lnum - c->main_first;
1596 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1597 for (h = 1; h < c->lpt_hght; h++) {
1598 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1599 shft -= UBIFS_LPT_FANOUT_SHIFT;
1600 nnode = ubifs_get_nnode(c, nnode, iip);
1601 if (IS_ERR(nnode))
1602 return ERR_CAST(nnode);
1603 nnode = dirty_cow_nnode(c, nnode);
1604 if (IS_ERR(nnode))
1605 return ERR_CAST(nnode);
1606 }
1607 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1608 pnode = ubifs_get_pnode(c, nnode, iip);
1609 if (IS_ERR(pnode))
1610 return ERR_CAST(pnode);
1611 pnode = dirty_cow_pnode(c, pnode);
1612 if (IS_ERR(pnode))
1613 return ERR_CAST(pnode);
1614 iip = (i & (UBIFS_LPT_FANOUT - 1));
1615 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1616 pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1617 pnode->lprops[iip].flags);
1618 ubifs_assert(c, test_bit(DIRTY_CNODE, &pnode->flags));
1619 return &pnode->lprops[iip];
1620}
1621
1622
1623
1624
1625
1626
1627
1628static int lpt_init_rd(struct ubifs_info *c)
1629{
1630 int err, i;
1631
1632 c->ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
1633 c->lpt_lebs));
1634 if (!c->ltab)
1635 return -ENOMEM;
1636
1637 i = max_t(int, c->nnode_sz, c->pnode_sz);
1638 c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);
1639 if (!c->lpt_nod_buf)
1640 return -ENOMEM;
1641
1642 for (i = 0; i < LPROPS_HEAP_CNT; i++) {
1643 c->lpt_heap[i].arr = kmalloc_array(LPT_HEAP_SZ,
1644 sizeof(void *),
1645 GFP_KERNEL);
1646 if (!c->lpt_heap[i].arr)
1647 return -ENOMEM;
1648 c->lpt_heap[i].cnt = 0;
1649 c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;
1650 }
1651
1652 c->dirty_idx.arr = kmalloc_array(LPT_HEAP_SZ, sizeof(void *),
1653 GFP_KERNEL);
1654 if (!c->dirty_idx.arr)
1655 return -ENOMEM;
1656 c->dirty_idx.cnt = 0;
1657 c->dirty_idx.max_cnt = LPT_HEAP_SZ;
1658
1659 err = read_ltab(c);
1660 if (err)
1661 return err;
1662
1663 dbg_lp("space_bits %d", c->space_bits);
1664 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
1665 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
1666 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
1667 dbg_lp("pcnt_bits %d", c->pcnt_bits);
1668 dbg_lp("lnum_bits %d", c->lnum_bits);
1669 dbg_lp("pnode_sz %d", c->pnode_sz);
1670 dbg_lp("nnode_sz %d", c->nnode_sz);
1671 dbg_lp("ltab_sz %d", c->ltab_sz);
1672 dbg_lp("lsave_sz %d", c->lsave_sz);
1673 dbg_lp("lsave_cnt %d", c->lsave_cnt);
1674 dbg_lp("lpt_hght %d", c->lpt_hght);
1675 dbg_lp("big_lpt %d", c->big_lpt);
1676 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
1677 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
1678 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
1679 if (c->big_lpt)
1680 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
1681
1682 return 0;
1683}
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693static int lpt_init_wr(struct ubifs_info *c)
1694{
1695 int err, i;
1696
1697 c->ltab_cmt = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
1698 c->lpt_lebs));
1699 if (!c->ltab_cmt)
1700 return -ENOMEM;
1701
1702 c->lpt_buf = vmalloc(c->leb_size);
1703 if (!c->lpt_buf)
1704 return -ENOMEM;
1705
1706 if (c->big_lpt) {
1707 c->lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_NOFS);
1708 if (!c->lsave)
1709 return -ENOMEM;
1710 err = read_lsave(c);
1711 if (err)
1712 return err;
1713 }
1714
1715 for (i = 0; i < c->lpt_lebs; i++)
1716 if (c->ltab[i].free == c->leb_size) {
1717 err = ubifs_leb_unmap(c, i + c->lpt_first);
1718 if (err)
1719 return err;
1720 }
1721
1722 return 0;
1723}
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)
1738{
1739 int err;
1740
1741 if (rd) {
1742 err = lpt_init_rd(c);
1743 if (err)
1744 goto out_err;
1745 }
1746
1747 if (wr) {
1748 err = lpt_init_wr(c);
1749 if (err)
1750 goto out_err;
1751 }
1752
1753 return 0;
1754
1755out_err:
1756 if (wr)
1757 ubifs_lpt_free(c, 1);
1758 if (rd)
1759 ubifs_lpt_free(c, 0);
1760 return err;
1761}
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774struct lpt_scan_node {
1775 union {
1776 struct ubifs_nnode nnode;
1777 struct ubifs_pnode pnode;
1778 struct ubifs_cnode cnode;
1779 };
1780 int in_tree;
1781 union {
1782 struct ubifs_nnode *nnode;
1783 struct ubifs_pnode *pnode;
1784 struct ubifs_cnode *cnode;
1785 } ptr;
1786};
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c,
1799 struct lpt_scan_node *path,
1800 struct ubifs_nnode *parent, int iip)
1801{
1802 struct ubifs_nbranch *branch;
1803 struct ubifs_nnode *nnode;
1804 void *buf = c->lpt_nod_buf;
1805 int err;
1806
1807 branch = &parent->nbranch[iip];
1808 nnode = branch->nnode;
1809 if (nnode) {
1810 path->in_tree = 1;
1811 path->ptr.nnode = nnode;
1812 return nnode;
1813 }
1814 nnode = &path->nnode;
1815 path->in_tree = 0;
1816 path->ptr.nnode = nnode;
1817 memset(nnode, 0, sizeof(struct ubifs_nnode));
1818 if (branch->lnum == 0) {
1819
1820
1821
1822
1823
1824
1825 if (c->big_lpt)
1826 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1827 } else {
1828 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
1829 c->nnode_sz, 1);
1830 if (err)
1831 return ERR_PTR(err);
1832 err = ubifs_unpack_nnode(c, buf, nnode);
1833 if (err)
1834 return ERR_PTR(err);
1835 }
1836 err = validate_nnode(c, nnode, parent, iip);
1837 if (err)
1838 return ERR_PTR(err);
1839 if (!c->big_lpt)
1840 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1841 nnode->level = parent->level - 1;
1842 nnode->parent = parent;
1843 nnode->iip = iip;
1844 return nnode;
1845}
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c,
1858 struct lpt_scan_node *path,
1859 struct ubifs_nnode *parent, int iip)
1860{
1861 struct ubifs_nbranch *branch;
1862 struct ubifs_pnode *pnode;
1863 void *buf = c->lpt_nod_buf;
1864 int err;
1865
1866 branch = &parent->nbranch[iip];
1867 pnode = branch->pnode;
1868 if (pnode) {
1869 path->in_tree = 1;
1870 path->ptr.pnode = pnode;
1871 return pnode;
1872 }
1873 pnode = &path->pnode;
1874 path->in_tree = 0;
1875 path->ptr.pnode = pnode;
1876 memset(pnode, 0, sizeof(struct ubifs_pnode));
1877 if (branch->lnum == 0) {
1878
1879
1880
1881
1882
1883 int i;
1884
1885 if (c->big_lpt)
1886 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1887 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1888 struct ubifs_lprops * const lprops = &pnode->lprops[i];
1889
1890 lprops->free = c->leb_size;
1891 lprops->flags = ubifs_categorize_lprops(c, lprops);
1892 }
1893 } else {
1894 ubifs_assert(c, branch->lnum >= c->lpt_first &&
1895 branch->lnum <= c->lpt_last);
1896 ubifs_assert(c, branch->offs >= 0 && branch->offs < c->leb_size);
1897 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
1898 c->pnode_sz, 1);
1899 if (err)
1900 return ERR_PTR(err);
1901 err = unpack_pnode(c, buf, pnode);
1902 if (err)
1903 return ERR_PTR(err);
1904 }
1905 err = validate_pnode(c, pnode, parent, iip);
1906 if (err)
1907 return ERR_PTR(err);
1908 if (!c->big_lpt)
1909 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1910 pnode->parent = parent;
1911 pnode->iip = iip;
1912 set_pnode_lnum(c, pnode);
1913 return pnode;
1914}
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum,
1927 ubifs_lpt_scan_callback scan_cb, void *data)
1928{
1929 int err = 0, i, h, iip, shft;
1930 struct ubifs_nnode *nnode;
1931 struct ubifs_pnode *pnode;
1932 struct lpt_scan_node *path;
1933
1934 if (start_lnum == -1) {
1935 start_lnum = end_lnum + 1;
1936 if (start_lnum >= c->leb_cnt)
1937 start_lnum = c->main_first;
1938 }
1939
1940 ubifs_assert(c, start_lnum >= c->main_first && start_lnum < c->leb_cnt);
1941 ubifs_assert(c, end_lnum >= c->main_first && end_lnum < c->leb_cnt);
1942
1943 if (!c->nroot) {
1944 err = ubifs_read_nnode(c, NULL, 0);
1945 if (err)
1946 return err;
1947 }
1948
1949 path = kmalloc_array(c->lpt_hght + 1, sizeof(struct lpt_scan_node),
1950 GFP_NOFS);
1951 if (!path)
1952 return -ENOMEM;
1953
1954 path[0].ptr.nnode = c->nroot;
1955 path[0].in_tree = 1;
1956again:
1957
1958 nnode = c->nroot;
1959 i = start_lnum - c->main_first;
1960 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1961 for (h = 1; h < c->lpt_hght; h++) {
1962 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1963 shft -= UBIFS_LPT_FANOUT_SHIFT;
1964 nnode = scan_get_nnode(c, path + h, nnode, iip);
1965 if (IS_ERR(nnode)) {
1966 err = PTR_ERR(nnode);
1967 goto out;
1968 }
1969 }
1970 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1971 pnode = scan_get_pnode(c, path + h, nnode, iip);
1972 if (IS_ERR(pnode)) {
1973 err = PTR_ERR(pnode);
1974 goto out;
1975 }
1976 iip = (i & (UBIFS_LPT_FANOUT - 1));
1977
1978
1979 while (1) {
1980 struct ubifs_lprops *lprops = &pnode->lprops[iip];
1981 int ret, lnum = lprops->lnum;
1982
1983 ret = scan_cb(c, lprops, path[h].in_tree, data);
1984 if (ret < 0) {
1985 err = ret;
1986 goto out;
1987 }
1988 if (ret & LPT_SCAN_ADD) {
1989
1990 for (h = 1; h < c->lpt_hght; h++) {
1991 const size_t sz = sizeof(struct ubifs_nnode);
1992 struct ubifs_nnode *parent;
1993
1994 if (path[h].in_tree)
1995 continue;
1996 nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS);
1997 if (!nnode) {
1998 err = -ENOMEM;
1999 goto out;
2000 }
2001 parent = nnode->parent;
2002 parent->nbranch[nnode->iip].nnode = nnode;
2003 path[h].ptr.nnode = nnode;
2004 path[h].in_tree = 1;
2005 path[h + 1].cnode.parent = nnode;
2006 }
2007 if (path[h].in_tree)
2008 ubifs_ensure_cat(c, lprops);
2009 else {
2010 const size_t sz = sizeof(struct ubifs_pnode);
2011 struct ubifs_nnode *parent;
2012
2013 pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS);
2014 if (!pnode) {
2015 err = -ENOMEM;
2016 goto out;
2017 }
2018 parent = pnode->parent;
2019 parent->nbranch[pnode->iip].pnode = pnode;
2020 path[h].ptr.pnode = pnode;
2021 path[h].in_tree = 1;
2022 update_cats(c, pnode);
2023 c->pnodes_have += 1;
2024 }
2025 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)
2026 c->nroot, 0, 0);
2027 if (err)
2028 goto out;
2029 err = dbg_check_cats(c);
2030 if (err)
2031 goto out;
2032 }
2033 if (ret & LPT_SCAN_STOP) {
2034 err = 0;
2035 break;
2036 }
2037
2038 if (lnum == end_lnum) {
2039
2040
2041
2042
2043 err = -ENOSPC;
2044 goto out;
2045 }
2046 if (lnum + 1 >= c->leb_cnt) {
2047
2048 start_lnum = c->main_first;
2049 goto again;
2050 }
2051 if (iip + 1 < UBIFS_LPT_FANOUT) {
2052
2053 iip += 1;
2054 continue;
2055 }
2056
2057 iip = pnode->iip;
2058 while (1) {
2059 h -= 1;
2060 ubifs_assert(c, h >= 0);
2061 nnode = path[h].ptr.nnode;
2062 if (iip + 1 < UBIFS_LPT_FANOUT)
2063 break;
2064 iip = nnode->iip;
2065 }
2066
2067 iip += 1;
2068
2069 h += 1;
2070 for (; h < c->lpt_hght; h++) {
2071 nnode = scan_get_nnode(c, path + h, nnode, iip);
2072 if (IS_ERR(nnode)) {
2073 err = PTR_ERR(nnode);
2074 goto out;
2075 }
2076 iip = 0;
2077 }
2078 pnode = scan_get_pnode(c, path + h, nnode, iip);
2079 if (IS_ERR(pnode)) {
2080 err = PTR_ERR(pnode);
2081 goto out;
2082 }
2083 iip = 0;
2084 }
2085out:
2086 kfree(path);
2087 return err;
2088}
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode,
2099 int col)
2100{
2101 int i;
2102
2103 if (pnode->num != col) {
2104 ubifs_err(c, "pnode num %d expected %d parent num %d iip %d",
2105 pnode->num, col, pnode->parent->num, pnode->iip);
2106 return -EINVAL;
2107 }
2108 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
2109 struct ubifs_lprops *lp, *lprops = &pnode->lprops[i];
2110 int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i +
2111 c->main_first;
2112 int found, cat = lprops->flags & LPROPS_CAT_MASK;
2113 struct ubifs_lpt_heap *heap;
2114 struct list_head *list = NULL;
2115
2116 if (lnum >= c->leb_cnt)
2117 continue;
2118 if (lprops->lnum != lnum) {
2119 ubifs_err(c, "bad LEB number %d expected %d",
2120 lprops->lnum, lnum);
2121 return -EINVAL;
2122 }
2123 if (lprops->flags & LPROPS_TAKEN) {
2124 if (cat != LPROPS_UNCAT) {
2125 ubifs_err(c, "LEB %d taken but not uncat %d",
2126 lprops->lnum, cat);
2127 return -EINVAL;
2128 }
2129 continue;
2130 }
2131 if (lprops->flags & LPROPS_INDEX) {
2132 switch (cat) {
2133 case LPROPS_UNCAT:
2134 case LPROPS_DIRTY_IDX:
2135 case LPROPS_FRDI_IDX:
2136 break;
2137 default:
2138 ubifs_err(c, "LEB %d index but cat %d",
2139 lprops->lnum, cat);
2140 return -EINVAL;
2141 }
2142 } else {
2143 switch (cat) {
2144 case LPROPS_UNCAT:
2145 case LPROPS_DIRTY:
2146 case LPROPS_FREE:
2147 case LPROPS_EMPTY:
2148 case LPROPS_FREEABLE:
2149 break;
2150 default:
2151 ubifs_err(c, "LEB %d not index but cat %d",
2152 lprops->lnum, cat);
2153 return -EINVAL;
2154 }
2155 }
2156 switch (cat) {
2157 case LPROPS_UNCAT:
2158 list = &c->uncat_list;
2159 break;
2160 case LPROPS_EMPTY:
2161 list = &c->empty_list;
2162 break;
2163 case LPROPS_FREEABLE:
2164 list = &c->freeable_list;
2165 break;
2166 case LPROPS_FRDI_IDX:
2167 list = &c->frdi_idx_list;
2168 break;
2169 }
2170 found = 0;
2171 switch (cat) {
2172 case LPROPS_DIRTY:
2173 case LPROPS_DIRTY_IDX:
2174 case LPROPS_FREE:
2175 heap = &c->lpt_heap[cat - 1];
2176 if (lprops->hpos < heap->cnt &&
2177 heap->arr[lprops->hpos] == lprops)
2178 found = 1;
2179 break;
2180 case LPROPS_UNCAT:
2181 case LPROPS_EMPTY:
2182 case LPROPS_FREEABLE:
2183 case LPROPS_FRDI_IDX:
2184 list_for_each_entry(lp, list, list)
2185 if (lprops == lp) {
2186 found = 1;
2187 break;
2188 }
2189 break;
2190 }
2191 if (!found) {
2192 ubifs_err(c, "LEB %d cat %d not found in cat heap/list",
2193 lprops->lnum, cat);
2194 return -EINVAL;
2195 }
2196 switch (cat) {
2197 case LPROPS_EMPTY:
2198 if (lprops->free != c->leb_size) {
2199 ubifs_err(c, "LEB %d cat %d free %d dirty %d",
2200 lprops->lnum, cat, lprops->free,
2201 lprops->dirty);
2202 return -EINVAL;
2203 }
2204 break;
2205 case LPROPS_FREEABLE:
2206 case LPROPS_FRDI_IDX:
2207 if (lprops->free + lprops->dirty != c->leb_size) {
2208 ubifs_err(c, "LEB %d cat %d free %d dirty %d",
2209 lprops->lnum, cat, lprops->free,
2210 lprops->dirty);
2211 return -EINVAL;
2212 }
2213 break;
2214 }
2215 }
2216 return 0;
2217}
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode,
2229 int row, int col)
2230{
2231 struct ubifs_nnode *nnode, *nn;
2232 struct ubifs_cnode *cn;
2233 int num, iip = 0, err;
2234
2235 if (!dbg_is_chk_lprops(c))
2236 return 0;
2237
2238 while (cnode) {
2239 ubifs_assert(c, row >= 0);
2240 nnode = cnode->parent;
2241 if (cnode->level) {
2242
2243 num = calc_nnode_num(row, col);
2244 if (cnode->num != num) {
2245 ubifs_err(c, "nnode num %d expected %d parent num %d iip %d",
2246 cnode->num, num,
2247 (nnode ? nnode->num : 0), cnode->iip);
2248 return -EINVAL;
2249 }
2250 nn = (struct ubifs_nnode *)cnode;
2251 while (iip < UBIFS_LPT_FANOUT) {
2252 cn = nn->nbranch[iip].cnode;
2253 if (cn) {
2254
2255 row += 1;
2256 col <<= UBIFS_LPT_FANOUT_SHIFT;
2257 col += iip;
2258 iip = 0;
2259 cnode = cn;
2260 break;
2261 }
2262
2263 iip += 1;
2264 }
2265 if (iip < UBIFS_LPT_FANOUT)
2266 continue;
2267 } else {
2268 struct ubifs_pnode *pnode;
2269
2270
2271 pnode = (struct ubifs_pnode *)cnode;
2272 err = dbg_chk_pnode(c, pnode, col);
2273 if (err)
2274 return err;
2275 }
2276
2277 row -= 1;
2278 col >>= UBIFS_LPT_FANOUT_SHIFT;
2279 iip = cnode->iip + 1;
2280 cnode = (struct ubifs_cnode *)nnode;
2281 }
2282 return 0;
2283}
2284