← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to fs/ubifs/lpt.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
ImportĀ upstreamĀ versionĀ 3.2.0

Show diffs side-by-side

added added

removed removed

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