]>
Commit | Line | Data |
---|---|---|
83d290c5 | 1 | // SPDX-License-Identifier: GPL-2.0+ |
9eefe2a2 SR |
2 | /* |
3 | * This file is part of UBIFS. | |
4 | * | |
5 | * Copyright (C) 2006-2008 Nokia Corporation. | |
6 | * | |
9eefe2a2 SR |
7 | * Authors: Adrian Hunter |
8 | * Artem Bityutskiy (Битюцкий Артём) | |
9 | */ | |
10 | ||
11 | /* | |
12 | * This file contains miscelanious TNC-related functions shared betweend | |
13 | * different files. This file does not form any logically separate TNC | |
14 | * sub-system. The file was created because there is a lot of TNC code and | |
15 | * putting it all in one file would make that file too big and unreadable. | |
16 | */ | |
17 | ||
ff94bc40 HS |
18 | #ifdef __UBOOT__ |
19 | #include <linux/err.h> | |
20 | #endif | |
9eefe2a2 SR |
21 | #include "ubifs.h" |
22 | ||
23 | /** | |
24 | * ubifs_tnc_levelorder_next - next TNC tree element in levelorder traversal. | |
25 | * @zr: root of the subtree to traverse | |
26 | * @znode: previous znode | |
27 | * | |
28 | * This function implements levelorder TNC traversal. The LNC is ignored. | |
29 | * Returns the next element or %NULL if @znode is already the last one. | |
30 | */ | |
31 | struct ubifs_znode *ubifs_tnc_levelorder_next(struct ubifs_znode *zr, | |
32 | struct ubifs_znode *znode) | |
33 | { | |
34 | int level, iip, level_search = 0; | |
35 | struct ubifs_znode *zn; | |
36 | ||
37 | ubifs_assert(zr); | |
38 | ||
39 | if (unlikely(!znode)) | |
40 | return zr; | |
41 | ||
42 | if (unlikely(znode == zr)) { | |
43 | if (znode->level == 0) | |
44 | return NULL; | |
45 | return ubifs_tnc_find_child(zr, 0); | |
46 | } | |
47 | ||
48 | level = znode->level; | |
49 | ||
50 | iip = znode->iip; | |
51 | while (1) { | |
52 | ubifs_assert(znode->level <= zr->level); | |
53 | ||
54 | /* | |
55 | * First walk up until there is a znode with next branch to | |
56 | * look at. | |
57 | */ | |
58 | while (znode->parent != zr && iip >= znode->parent->child_cnt) { | |
59 | znode = znode->parent; | |
60 | iip = znode->iip; | |
61 | } | |
62 | ||
63 | if (unlikely(znode->parent == zr && | |
64 | iip >= znode->parent->child_cnt)) { | |
65 | /* This level is done, switch to the lower one */ | |
66 | level -= 1; | |
67 | if (level_search || level < 0) | |
68 | /* | |
69 | * We were already looking for znode at lower | |
70 | * level ('level_search'). As we are here | |
71 | * again, it just does not exist. Or all levels | |
72 | * were finished ('level < 0'). | |
73 | */ | |
74 | return NULL; | |
75 | ||
76 | level_search = 1; | |
77 | iip = -1; | |
78 | znode = ubifs_tnc_find_child(zr, 0); | |
79 | ubifs_assert(znode); | |
80 | } | |
81 | ||
82 | /* Switch to the next index */ | |
83 | zn = ubifs_tnc_find_child(znode->parent, iip + 1); | |
84 | if (!zn) { | |
85 | /* No more children to look at, we have walk up */ | |
86 | iip = znode->parent->child_cnt; | |
87 | continue; | |
88 | } | |
89 | ||
90 | /* Walk back down to the level we came from ('level') */ | |
91 | while (zn->level != level) { | |
92 | znode = zn; | |
93 | zn = ubifs_tnc_find_child(zn, 0); | |
94 | if (!zn) { | |
95 | /* | |
96 | * This path is not too deep so it does not | |
97 | * reach 'level'. Try next path. | |
98 | */ | |
99 | iip = znode->iip; | |
100 | break; | |
101 | } | |
102 | } | |
103 | ||
104 | if (zn) { | |
105 | ubifs_assert(zn->level >= 0); | |
106 | return zn; | |
107 | } | |
108 | } | |
109 | } | |
110 | ||
111 | /** | |
112 | * ubifs_search_zbranch - search znode branch. | |
113 | * @c: UBIFS file-system description object | |
114 | * @znode: znode to search in | |
115 | * @key: key to search for | |
116 | * @n: znode branch slot number is returned here | |
117 | * | |
118 | * This is a helper function which search branch with key @key in @znode using | |
119 | * binary search. The result of the search may be: | |
120 | * o exact match, then %1 is returned, and the slot number of the branch is | |
121 | * stored in @n; | |
122 | * o no exact match, then %0 is returned and the slot number of the left | |
123 | * closest branch is returned in @n; the slot if all keys in this znode are | |
124 | * greater than @key, then %-1 is returned in @n. | |
125 | */ | |
126 | int ubifs_search_zbranch(const struct ubifs_info *c, | |
127 | const struct ubifs_znode *znode, | |
128 | const union ubifs_key *key, int *n) | |
129 | { | |
130 | int beg = 0, end = znode->child_cnt, uninitialized_var(mid); | |
131 | int uninitialized_var(cmp); | |
132 | const struct ubifs_zbranch *zbr = &znode->zbranch[0]; | |
133 | ||
134 | ubifs_assert(end > beg); | |
135 | ||
136 | while (end > beg) { | |
137 | mid = (beg + end) >> 1; | |
138 | cmp = keys_cmp(c, key, &zbr[mid].key); | |
139 | if (cmp > 0) | |
140 | beg = mid + 1; | |
141 | else if (cmp < 0) | |
142 | end = mid; | |
143 | else { | |
144 | *n = mid; | |
145 | return 1; | |
146 | } | |
147 | } | |
148 | ||
149 | *n = end - 1; | |
150 | ||
151 | /* The insert point is after *n */ | |
152 | ubifs_assert(*n >= -1 && *n < znode->child_cnt); | |
153 | if (*n == -1) | |
154 | ubifs_assert(keys_cmp(c, key, &zbr[0].key) < 0); | |
155 | else | |
156 | ubifs_assert(keys_cmp(c, key, &zbr[*n].key) > 0); | |
157 | if (*n + 1 < znode->child_cnt) | |
158 | ubifs_assert(keys_cmp(c, key, &zbr[*n + 1].key) < 0); | |
159 | ||
160 | return 0; | |
161 | } | |
162 | ||
163 | /** | |
164 | * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal. | |
165 | * @znode: znode to start at (root of the sub-tree to traverse) | |
166 | * | |
167 | * Find the lowest leftmost znode in a subtree of the TNC tree. The LNC is | |
168 | * ignored. | |
169 | */ | |
170 | struct ubifs_znode *ubifs_tnc_postorder_first(struct ubifs_znode *znode) | |
171 | { | |
172 | if (unlikely(!znode)) | |
173 | return NULL; | |
174 | ||
175 | while (znode->level > 0) { | |
176 | struct ubifs_znode *child; | |
177 | ||
178 | child = ubifs_tnc_find_child(znode, 0); | |
179 | if (!child) | |
180 | return znode; | |
181 | znode = child; | |
182 | } | |
183 | ||
184 | return znode; | |
185 | } | |
186 | ||
187 | /** | |
188 | * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal. | |
189 | * @znode: previous znode | |
190 | * | |
191 | * This function implements postorder TNC traversal. The LNC is ignored. | |
192 | * Returns the next element or %NULL if @znode is already the last one. | |
193 | */ | |
194 | struct ubifs_znode *ubifs_tnc_postorder_next(struct ubifs_znode *znode) | |
195 | { | |
196 | struct ubifs_znode *zn; | |
197 | ||
198 | ubifs_assert(znode); | |
199 | if (unlikely(!znode->parent)) | |
200 | return NULL; | |
201 | ||
202 | /* Switch to the next index in the parent */ | |
203 | zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1); | |
204 | if (!zn) | |
205 | /* This is in fact the last child, return parent */ | |
206 | return znode->parent; | |
207 | ||
208 | /* Go to the first znode in this new subtree */ | |
209 | return ubifs_tnc_postorder_first(zn); | |
210 | } | |
211 | ||
ff94bc40 HS |
212 | /** |
213 | * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree. | |
214 | * @znode: znode defining subtree to destroy | |
215 | * | |
216 | * This function destroys subtree of the TNC tree. Returns number of clean | |
217 | * znodes in the subtree. | |
218 | */ | |
219 | long ubifs_destroy_tnc_subtree(struct ubifs_znode *znode) | |
220 | { | |
221 | struct ubifs_znode *zn = ubifs_tnc_postorder_first(znode); | |
222 | long clean_freed = 0; | |
223 | int n; | |
224 | ||
225 | ubifs_assert(zn); | |
226 | while (1) { | |
227 | for (n = 0; n < zn->child_cnt; n++) { | |
228 | if (!zn->zbranch[n].znode) | |
229 | continue; | |
230 | ||
231 | if (zn->level > 0 && | |
232 | !ubifs_zn_dirty(zn->zbranch[n].znode)) | |
233 | clean_freed += 1; | |
234 | ||
235 | cond_resched(); | |
236 | kfree(zn->zbranch[n].znode); | |
237 | } | |
238 | ||
239 | if (zn == znode) { | |
240 | if (!ubifs_zn_dirty(zn)) | |
241 | clean_freed += 1; | |
242 | kfree(zn); | |
243 | return clean_freed; | |
244 | } | |
245 | ||
246 | zn = ubifs_tnc_postorder_next(zn); | |
247 | } | |
248 | } | |
249 | ||
9eefe2a2 SR |
250 | /** |
251 | * read_znode - read an indexing node from flash and fill znode. | |
252 | * @c: UBIFS file-system description object | |
253 | * @lnum: LEB of the indexing node to read | |
254 | * @offs: node offset | |
255 | * @len: node length | |
256 | * @znode: znode to read to | |
257 | * | |
258 | * This function reads an indexing node from the flash media and fills znode | |
259 | * with the read data. Returns zero in case of success and a negative error | |
260 | * code in case of failure. The read indexing node is validated and if anything | |
261 | * is wrong with it, this function prints complaint messages and returns | |
262 | * %-EINVAL. | |
263 | */ | |
264 | static int read_znode(struct ubifs_info *c, int lnum, int offs, int len, | |
265 | struct ubifs_znode *znode) | |
266 | { | |
267 | int i, err, type, cmp; | |
268 | struct ubifs_idx_node *idx; | |
269 | ||
270 | idx = kmalloc(c->max_idx_node_sz, GFP_NOFS); | |
271 | if (!idx) | |
272 | return -ENOMEM; | |
273 | ||
274 | err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs); | |
275 | if (err < 0) { | |
276 | kfree(idx); | |
277 | return err; | |
278 | } | |
279 | ||
280 | znode->child_cnt = le16_to_cpu(idx->child_cnt); | |
281 | znode->level = le16_to_cpu(idx->level); | |
282 | ||
283 | dbg_tnc("LEB %d:%d, level %d, %d branch", | |
284 | lnum, offs, znode->level, znode->child_cnt); | |
285 | ||
286 | if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) { | |
0195a7bb | 287 | ubifs_err(c, "current fanout %d, branch count %d", |
ff94bc40 | 288 | c->fanout, znode->child_cnt); |
0195a7bb | 289 | ubifs_err(c, "max levels %d, znode level %d", |
ff94bc40 | 290 | UBIFS_MAX_LEVELS, znode->level); |
9eefe2a2 SR |
291 | err = 1; |
292 | goto out_dump; | |
293 | } | |
294 | ||
295 | for (i = 0; i < znode->child_cnt; i++) { | |
296 | const struct ubifs_branch *br = ubifs_idx_branch(c, idx, i); | |
297 | struct ubifs_zbranch *zbr = &znode->zbranch[i]; | |
298 | ||
299 | key_read(c, &br->key, &zbr->key); | |
300 | zbr->lnum = le32_to_cpu(br->lnum); | |
301 | zbr->offs = le32_to_cpu(br->offs); | |
302 | zbr->len = le32_to_cpu(br->len); | |
303 | zbr->znode = NULL; | |
304 | ||
305 | /* Validate branch */ | |
306 | ||
307 | if (zbr->lnum < c->main_first || | |
308 | zbr->lnum >= c->leb_cnt || zbr->offs < 0 || | |
309 | zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) { | |
0195a7bb | 310 | ubifs_err(c, "bad branch %d", i); |
9eefe2a2 SR |
311 | err = 2; |
312 | goto out_dump; | |
313 | } | |
314 | ||
315 | switch (key_type(c, &zbr->key)) { | |
316 | case UBIFS_INO_KEY: | |
317 | case UBIFS_DATA_KEY: | |
318 | case UBIFS_DENT_KEY: | |
319 | case UBIFS_XENT_KEY: | |
320 | break; | |
321 | default: | |
0195a7bb | 322 | ubifs_err(c, "bad key type at slot %d: %d", |
ff94bc40 | 323 | i, key_type(c, &zbr->key)); |
9eefe2a2 SR |
324 | err = 3; |
325 | goto out_dump; | |
326 | } | |
327 | ||
328 | if (znode->level) | |
329 | continue; | |
330 | ||
331 | type = key_type(c, &zbr->key); | |
332 | if (c->ranges[type].max_len == 0) { | |
333 | if (zbr->len != c->ranges[type].len) { | |
0195a7bb | 334 | ubifs_err(c, "bad target node (type %d) length (%d)", |
ff94bc40 | 335 | type, zbr->len); |
0195a7bb | 336 | ubifs_err(c, "have to be %d", c->ranges[type].len); |
9eefe2a2 SR |
337 | err = 4; |
338 | goto out_dump; | |
339 | } | |
340 | } else if (zbr->len < c->ranges[type].min_len || | |
341 | zbr->len > c->ranges[type].max_len) { | |
0195a7bb | 342 | ubifs_err(c, "bad target node (type %d) length (%d)", |
ff94bc40 | 343 | type, zbr->len); |
0195a7bb | 344 | ubifs_err(c, "have to be in range of %d-%d", |
ff94bc40 HS |
345 | c->ranges[type].min_len, |
346 | c->ranges[type].max_len); | |
9eefe2a2 SR |
347 | err = 5; |
348 | goto out_dump; | |
349 | } | |
350 | } | |
351 | ||
352 | /* | |
353 | * Ensure that the next key is greater or equivalent to the | |
354 | * previous one. | |
355 | */ | |
356 | for (i = 0; i < znode->child_cnt - 1; i++) { | |
357 | const union ubifs_key *key1, *key2; | |
358 | ||
359 | key1 = &znode->zbranch[i].key; | |
360 | key2 = &znode->zbranch[i + 1].key; | |
361 | ||
362 | cmp = keys_cmp(c, key1, key2); | |
363 | if (cmp > 0) { | |
0195a7bb | 364 | ubifs_err(c, "bad key order (keys %d and %d)", i, i + 1); |
9eefe2a2 SR |
365 | err = 6; |
366 | goto out_dump; | |
367 | } else if (cmp == 0 && !is_hash_key(c, key1)) { | |
368 | /* These can only be keys with colliding hash */ | |
0195a7bb | 369 | ubifs_err(c, "keys %d and %d are not hashed but equivalent", |
ff94bc40 | 370 | i, i + 1); |
9eefe2a2 SR |
371 | err = 7; |
372 | goto out_dump; | |
373 | } | |
374 | } | |
375 | ||
376 | kfree(idx); | |
377 | return 0; | |
378 | ||
379 | out_dump: | |
0195a7bb | 380 | ubifs_err(c, "bad indexing node at LEB %d:%d, error %d", lnum, offs, err); |
ff94bc40 | 381 | ubifs_dump_node(c, idx); |
9eefe2a2 SR |
382 | kfree(idx); |
383 | return -EINVAL; | |
384 | } | |
385 | ||
386 | /** | |
387 | * ubifs_load_znode - load znode to TNC cache. | |
388 | * @c: UBIFS file-system description object | |
389 | * @zbr: znode branch | |
390 | * @parent: znode's parent | |
391 | * @iip: index in parent | |
392 | * | |
393 | * This function loads znode pointed to by @zbr into the TNC cache and | |
394 | * returns pointer to it in case of success and a negative error code in case | |
395 | * of failure. | |
396 | */ | |
397 | struct ubifs_znode *ubifs_load_znode(struct ubifs_info *c, | |
398 | struct ubifs_zbranch *zbr, | |
399 | struct ubifs_znode *parent, int iip) | |
400 | { | |
401 | int err; | |
402 | struct ubifs_znode *znode; | |
403 | ||
404 | ubifs_assert(!zbr->znode); | |
405 | /* | |
406 | * A slab cache is not presently used for znodes because the znode size | |
407 | * depends on the fanout which is stored in the superblock. | |
408 | */ | |
409 | znode = kzalloc(c->max_znode_sz, GFP_NOFS); | |
410 | if (!znode) | |
411 | return ERR_PTR(-ENOMEM); | |
412 | ||
413 | err = read_znode(c, zbr->lnum, zbr->offs, zbr->len, znode); | |
414 | if (err) | |
415 | goto out; | |
416 | ||
ff94bc40 HS |
417 | atomic_long_inc(&c->clean_zn_cnt); |
418 | ||
419 | /* | |
420 | * Increment the global clean znode counter as well. It is OK that | |
421 | * global and per-FS clean znode counters may be inconsistent for some | |
422 | * short time (because we might be preempted at this point), the global | |
423 | * one is only used in shrinker. | |
424 | */ | |
425 | atomic_long_inc(&ubifs_clean_zn_cnt); | |
426 | ||
9eefe2a2 SR |
427 | zbr->znode = znode; |
428 | znode->parent = parent; | |
429 | znode->time = get_seconds(); | |
430 | znode->iip = iip; | |
431 | ||
432 | return znode; | |
433 | ||
434 | out: | |
435 | kfree(znode); | |
436 | return ERR_PTR(err); | |
437 | } | |
438 | ||
439 | /** | |
440 | * ubifs_tnc_read_node - read a leaf node from the flash media. | |
441 | * @c: UBIFS file-system description object | |
442 | * @zbr: key and position of the node | |
443 | * @node: node is returned here | |
444 | * | |
445 | * This function reads a node defined by @zbr from the flash media. Returns | |
446 | * zero in case of success or a negative negative error code in case of | |
447 | * failure. | |
448 | */ | |
449 | int ubifs_tnc_read_node(struct ubifs_info *c, struct ubifs_zbranch *zbr, | |
450 | void *node) | |
451 | { | |
452 | union ubifs_key key1, *key = &zbr->key; | |
453 | int err, type = key_type(c, key); | |
ff94bc40 | 454 | struct ubifs_wbuf *wbuf; |
9eefe2a2 | 455 | |
ff94bc40 HS |
456 | /* |
457 | * 'zbr' has to point to on-flash node. The node may sit in a bud and | |
458 | * may even be in a write buffer, so we have to take care about this. | |
459 | */ | |
460 | wbuf = ubifs_get_wbuf(c, zbr->lnum); | |
461 | if (wbuf) | |
462 | err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len, | |
463 | zbr->lnum, zbr->offs); | |
464 | else | |
465 | err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum, | |
466 | zbr->offs); | |
9eefe2a2 SR |
467 | |
468 | if (err) { | |
ff94bc40 | 469 | dbg_tnck(key, "key "); |
9eefe2a2 SR |
470 | return err; |
471 | } | |
472 | ||
473 | /* Make sure the key of the read node is correct */ | |
474 | key_read(c, node + UBIFS_KEY_OFFSET, &key1); | |
475 | if (!keys_eq(c, key, &key1)) { | |
0195a7bb | 476 | ubifs_err(c, "bad key in node at LEB %d:%d", |
9eefe2a2 | 477 | zbr->lnum, zbr->offs); |
ff94bc40 HS |
478 | dbg_tnck(key, "looked for key "); |
479 | dbg_tnck(&key1, "but found node's key "); | |
480 | ubifs_dump_node(c, node); | |
9eefe2a2 SR |
481 | return -EINVAL; |
482 | } | |
483 | ||
484 | return 0; | |
485 | } |