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