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