11e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/* 21e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This file is part of UBIFS. 31e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 41e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Copyright (C) 2006-2008 Nokia Corporation. 51e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 61e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This program is free software; you can redistribute it and/or modify it 71e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * under the terms of the GNU General Public License version 2 as published by 81e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * the Free Software Foundation. 91e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 101e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This program is distributed in the hope that it will be useful, but WITHOUT 111e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 121e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 131e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * more details. 141e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 151e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * You should have received a copy of the GNU General Public License along with 161e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * this program; if not, write to the Free Software Foundation, Inc., 51 171e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 181e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 191e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Authors: Adrian Hunter 201e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Artem Bityutskiy (Битюцкий Артём) 211e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 221e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 231e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/* 241e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This file contains miscelanious TNC-related functions shared betweend 251e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * different files. This file does not form any logically separate TNC 261e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * sub-system. The file was created because there is a lot of TNC code and 271e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * putting it all in one file would make that file too big and unreadable. 281e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 291e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 301e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy#include "ubifs.h" 311e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 321e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 331e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_tnc_levelorder_next - next TNC tree element in levelorder traversal. 341e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @zr: root of the subtree to traverse 351e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @znode: previous znode 361e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 371e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This function implements levelorder TNC traversal. The LNC is ignored. 381e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Returns the next element or %NULL if @znode is already the last one. 391e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 401e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiystruct ubifs_znode *ubifs_tnc_levelorder_next(struct ubifs_znode *zr, 411e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *znode) 421e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 431e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int level, iip, level_search = 0; 441e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *zn; 451e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 461e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(zr); 471e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 481e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (unlikely(!znode)) 491e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return zr; 501e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 511e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (unlikely(znode == zr)) { 521e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (znode->level == 0) 531e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return NULL; 541e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return ubifs_tnc_find_child(zr, 0); 551e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 561e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 571e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy level = znode->level; 581e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 591e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy iip = znode->iip; 601e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy while (1) { 611e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(znode->level <= zr->level); 621e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 631e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 641e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * First walk up until there is a znode with next branch to 651e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * look at. 661e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 671e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy while (znode->parent != zr && iip >= znode->parent->child_cnt) { 681e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode = znode->parent; 691e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy iip = znode->iip; 701e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 711e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 721e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (unlikely(znode->parent == zr && 731e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy iip >= znode->parent->child_cnt)) { 741e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* This level is done, switch to the lower one */ 751e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy level -= 1; 761e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (level_search || level < 0) 771e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 781e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * We were already looking for znode at lower 791e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * level ('level_search'). As we are here 801e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * again, it just does not exist. Or all levels 811e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * were finished ('level < 0'). 821e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 831e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return NULL; 841e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 851e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy level_search = 1; 861e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy iip = -1; 871e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode = ubifs_tnc_find_child(zr, 0); 881e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(znode); 891e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 901e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 911e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* Switch to the next index */ 921e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zn = ubifs_tnc_find_child(znode->parent, iip + 1); 931e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!zn) { 941e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* No more children to look at, we have walk up */ 951e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy iip = znode->parent->child_cnt; 961e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy continue; 971e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 981e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 991e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* Walk back down to the level we came from ('level') */ 1001e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy while (zn->level != level) { 1011e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode = zn; 1021e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zn = ubifs_tnc_find_child(zn, 0); 1031e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!zn) { 1041e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 1051e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This path is not too deep so it does not 1061e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * reach 'level'. Try next path. 1071e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 1081e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy iip = znode->iip; 1091e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy break; 1101e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1111e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1121e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1131e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (zn) { 1141e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(zn->level >= 0); 1151e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return zn; 1161e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1171e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1181e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 1191e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1201e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 1211e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_search_zbranch - search znode branch. 1221e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @c: UBIFS file-system description object 1231e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @znode: znode to search in 1241e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @key: key to search for 1251e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @n: znode branch slot number is returned here 1261e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 1271e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This is a helper function which search branch with key @key in @znode using 1281e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * binary search. The result of the search may be: 1291e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * o exact match, then %1 is returned, and the slot number of the branch is 1301e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * stored in @n; 1311e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * o no exact match, then %0 is returned and the slot number of the left 1321e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * closest branch is returned in @n; the slot if all keys in this znode are 1331e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * greater than @key, then %-1 is returned in @n. 1341e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 1351e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiyint ubifs_search_zbranch(const struct ubifs_info *c, 1361e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy const struct ubifs_znode *znode, 1371e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy const union ubifs_key *key, int *n) 1381e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 1391e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int beg = 0, end = znode->child_cnt, uninitialized_var(mid); 1401e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int uninitialized_var(cmp); 1411e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy const struct ubifs_zbranch *zbr = &znode->zbranch[0]; 1421e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1431e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(end > beg); 1441e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1451e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy while (end > beg) { 1461e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy mid = (beg + end) >> 1; 1471e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy cmp = keys_cmp(c, key, &zbr[mid].key); 1481e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (cmp > 0) 1491e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy beg = mid + 1; 1501e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy else if (cmp < 0) 1511e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy end = mid; 1521e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy else { 1531e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy *n = mid; 1541e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return 1; 1551e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1561e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1571e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1581e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy *n = end - 1; 1591e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1601e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* The insert point is after *n */ 1611e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(*n >= -1 && *n < znode->child_cnt); 1621e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (*n == -1) 1631e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(keys_cmp(c, key, &zbr[0].key) < 0); 1641e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy else 1651e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(keys_cmp(c, key, &zbr[*n].key) > 0); 1661e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (*n + 1 < znode->child_cnt) 1671e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(keys_cmp(c, key, &zbr[*n + 1].key) < 0); 1681e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1691e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return 0; 1701e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 1711e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1721e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 1731e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal. 1741e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @znode: znode to start at (root of the sub-tree to traverse) 1751e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 1761e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Find the lowest leftmost znode in a subtree of the TNC tree. The LNC is 1771e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ignored. 1781e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 1791e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiystruct ubifs_znode *ubifs_tnc_postorder_first(struct ubifs_znode *znode) 1801e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 1811e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (unlikely(!znode)) 1821e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return NULL; 1831e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1841e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy while (znode->level > 0) { 1851e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *child; 1861e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1871e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy child = ubifs_tnc_find_child(znode, 0); 1881e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!child) 1891e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return znode; 1901e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode = child; 1911e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 1921e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1931e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return znode; 1941e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 1951e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 1961e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 1971e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal. 1981e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @znode: previous znode 1991e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 2001e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This function implements postorder TNC traversal. The LNC is ignored. 2011e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Returns the next element or %NULL if @znode is already the last one. 2021e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 2031e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiystruct ubifs_znode *ubifs_tnc_postorder_next(struct ubifs_znode *znode) 2041e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 2051e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *zn; 2061e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2071e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(znode); 2081e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (unlikely(!znode->parent)) 2091e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return NULL; 2101e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2111e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* Switch to the next index in the parent */ 2121e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1); 2131e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!zn) 2141e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* This is in fact the last child, return parent */ 2151e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return znode->parent; 2161e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2171e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* Go to the first znode in this new subtree */ 2181e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return ubifs_tnc_postorder_first(zn); 2191e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 2201e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2211e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 2221e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree. 2231e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @znode: znode defining subtree to destroy 2241e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 2251e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This function destroys subtree of the TNC tree. Returns number of clean 2261e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * znodes in the subtree. 2271e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 2281e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiylong ubifs_destroy_tnc_subtree(struct ubifs_znode *znode) 2291e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 2301e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *zn = ubifs_tnc_postorder_first(znode); 2311e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy long clean_freed = 0; 2321e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int n; 2331e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2341e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(zn); 2351e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy while (1) { 2361e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy for (n = 0; n < zn->child_cnt; n++) { 2371e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!zn->zbranch[n].znode) 2381e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy continue; 2391e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2401e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (zn->level > 0 && 2411e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy !ubifs_zn_dirty(zn->zbranch[n].znode)) 2421e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy clean_freed += 1; 2431e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2441e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy cond_resched(); 2451e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy kfree(zn->zbranch[n].znode); 2461e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 2471e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2481e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (zn == znode) { 2491e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!ubifs_zn_dirty(zn)) 2501e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy clean_freed += 1; 2511e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy kfree(zn); 2521e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return clean_freed; 2531e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 2541e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2551e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zn = ubifs_tnc_postorder_next(zn); 2561e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 2571e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 2581e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2591e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 2601e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * read_znode - read an indexing node from flash and fill znode. 2611e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @c: UBIFS file-system description object 2621e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @lnum: LEB of the indexing node to read 2631e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @offs: node offset 2641e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @len: node length 2651e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @znode: znode to read to 2661e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 2671e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This function reads an indexing node from the flash media and fills znode 2681e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * with the read data. Returns zero in case of success and a negative error 2691e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * code in case of failure. The read indexing node is validated and if anything 2701e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * is wrong with it, this function prints complaint messages and returns 2711e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * %-EINVAL. 2721e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 2731e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiystatic int read_znode(struct ubifs_info *c, int lnum, int offs, int len, 2741e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *znode) 2751e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 2761e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int i, err, type, cmp; 2771e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_idx_node *idx; 2781e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2791e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy idx = kmalloc(c->max_idx_node_sz, GFP_NOFS); 2801e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!idx) 2811e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return -ENOMEM; 2821e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2831e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs); 2841e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (err < 0) { 2851e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy kfree(idx); 2861e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return err; 2871e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 2881e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2891e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode->child_cnt = le16_to_cpu(idx->child_cnt); 2901e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode->level = le16_to_cpu(idx->level); 2911e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2921e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy dbg_tnc("LEB %d:%d, level %d, %d branch", 2931e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy lnum, offs, znode->level, znode->child_cnt); 2941e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 2951e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) { 296a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("current fanout %d, branch count %d", 297a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy c->fanout, znode->child_cnt); 298a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("max levels %d, znode level %d", 299a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy UBIFS_MAX_LEVELS, znode->level); 3001e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 1; 3011e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3021e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3031e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3041e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy for (i = 0; i < znode->child_cnt; i++) { 3051e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy const struct ubifs_branch *br = ubifs_idx_branch(c, idx, i); 3061e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_zbranch *zbr = &znode->zbranch[i]; 3071e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3081e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy key_read(c, &br->key, &zbr->key); 3091e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->lnum = le32_to_cpu(br->lnum); 3101e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->offs = le32_to_cpu(br->offs); 3111e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->len = le32_to_cpu(br->len); 3121e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->znode = NULL; 3131e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3141e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* Validate branch */ 3151e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3161e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (zbr->lnum < c->main_first || 3171e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->lnum >= c->leb_cnt || zbr->offs < 0 || 3181e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) { 319a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("bad branch %d", i); 3201e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 2; 3211e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3221e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3231e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3241e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy switch (key_type(c, &zbr->key)) { 3251e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy case UBIFS_INO_KEY: 3261e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy case UBIFS_DATA_KEY: 3271e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy case UBIFS_DENT_KEY: 3281e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy case UBIFS_XENT_KEY: 3291e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy break; 3301e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy default: 3313668b70fcf1fdc6799abf15f70fe3f50f407ec82Artem Bityutskiy ubifs_err("bad key type at slot %d: %d", 3323668b70fcf1fdc6799abf15f70fe3f50f407ec82Artem Bityutskiy i, key_type(c, &zbr->key)); 3331e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 3; 3341e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3351e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3361e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3371e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (znode->level) 3381e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy continue; 3391e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3401e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy type = key_type(c, &zbr->key); 3411e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (c->ranges[type].max_len == 0) { 3421e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (zbr->len != c->ranges[type].len) { 343a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("bad target node (type %d) length (%d)", 344a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy type, zbr->len); 345a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("have to be %d", c->ranges[type].len); 3461e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 4; 3471e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3481e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3491e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } else if (zbr->len < c->ranges[type].min_len || 3501e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->len > c->ranges[type].max_len) { 351a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("bad target node (type %d) length (%d)", 352a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy type, zbr->len); 353a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("have to be in range of %d-%d", 354a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy c->ranges[type].min_len, 355a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy c->ranges[type].max_len); 3561e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 5; 3571e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3581e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3591e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3601e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3611e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 3621e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Ensure that the next key is greater or equivalent to the 3631e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * previous one. 3641e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 3651e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy for (i = 0; i < znode->child_cnt - 1; i++) { 3661e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy const union ubifs_key *key1, *key2; 3671e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3681e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy key1 = &znode->zbranch[i].key; 3691e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy key2 = &znode->zbranch[i + 1].key; 3701e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3711e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy cmp = keys_cmp(c, key1, key2); 3721e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (cmp > 0) { 373a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("bad key order (keys %d and %d)", i, i + 1); 3741e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 6; 3751e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3761e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } else if (cmp == 0 && !is_hash_key(c, key1)) { 3771e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* These can only be keys with colliding hash */ 378a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy ubifs_err("keys %d and %d are not hashed but equivalent", 379a6aae4dd0ffad299a33d122f8a339b399bee5381Artem Bityutskiy i, i + 1); 3801e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = 7; 3811e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out_dump; 3821e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3831e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 3841e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3851e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy kfree(idx); 3861e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return 0; 3871e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3881e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiyout_dump: 3891e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_err("bad indexing node at LEB %d:%d, error %d", lnum, offs, err); 390edf6be245fd34a4438646375cecb11f5feb92646Artem Bityutskiy ubifs_dump_node(c, idx); 3911e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy kfree(idx); 3921e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return -EINVAL; 3931e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 3941e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 3951e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 3961e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_load_znode - load znode to TNC cache. 3971e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @c: UBIFS file-system description object 3981e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @zbr: znode branch 3991e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @parent: znode's parent 4001e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @iip: index in parent 4011e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 4021e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This function loads znode pointed to by @zbr into the TNC cache and 4031e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * returns pointer to it in case of success and a negative error code in case 4041e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * of failure. 4051e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 4061e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiystruct ubifs_znode *ubifs_load_znode(struct ubifs_info *c, 4071e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_zbranch *zbr, 4081e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *parent, int iip) 4091e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 4101e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int err; 4111e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_znode *znode; 4121e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4131e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_assert(!zbr->znode); 4141e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 4151e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * A slab cache is not presently used for znodes because the znode size 4161e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * depends on the fanout which is stored in the superblock. 4171e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 4181e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode = kzalloc(c->max_znode_sz, GFP_NOFS); 4191e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (!znode) 4201e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return ERR_PTR(-ENOMEM); 4211e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4221e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = read_znode(c, zbr->lnum, zbr->offs, zbr->len, znode); 4231e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (err) 4241e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy goto out; 4251e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4261e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy atomic_long_inc(&c->clean_zn_cnt); 4271e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4281e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 4291e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * Increment the global clean znode counter as well. It is OK that 4301e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * global and per-FS clean znode counters may be inconsistent for some 4311e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * short time (because we might be preempted at this point), the global 4321e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * one is only used in shrinker. 4331e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 4341e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy atomic_long_inc(&ubifs_clean_zn_cnt); 4351e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4361e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->znode = znode; 4371e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode->parent = parent; 4381e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode->time = get_seconds(); 4391e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy znode->iip = iip; 4401e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4411e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return znode; 4421e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4431e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiyout: 4441e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy kfree(znode); 4451e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return ERR_PTR(err); 4461e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 4471e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4481e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy/** 4491e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * ubifs_tnc_read_node - read a leaf node from the flash media. 4501e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @c: UBIFS file-system description object 4511e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @zbr: key and position of the node 4521e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * @node: node is returned here 4531e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 4541e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * This function reads a node defined by @zbr from the flash media. Returns 4551e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * zero in case of success or a negative negative error code in case of 4561e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * failure. 4571e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 4581e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiyint ubifs_tnc_read_node(struct ubifs_info *c, struct ubifs_zbranch *zbr, 4591e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy void *node) 4601e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy{ 4611e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy union ubifs_key key1, *key = &zbr->key; 4621e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy int err, type = key_type(c, key); 4631e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy struct ubifs_wbuf *wbuf; 4641e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4651e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* 4661e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * 'zbr' has to point to on-flash node. The node may sit in a bud and 4671e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy * may even be in a write buffer, so we have to take care about this. 4681e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy */ 4691e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy wbuf = ubifs_get_wbuf(c, zbr->lnum); 4701e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (wbuf) 4711e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len, 4721e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->lnum, zbr->offs); 4731e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy else 4741e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum, 4751e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->offs); 4761e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4771e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy if (err) { 478515315a123af641a9533e4ff0f178c470dc08fc7Artem Bityutskiy dbg_tnck(key, "key "); 4791e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return err; 4801e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 4811e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4821e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy /* Make sure the key of the read node is correct */ 4832094c334fdebbcceddf21f97cb16b144707af56eAdrian Hunter key_read(c, node + UBIFS_KEY_OFFSET, &key1); 4842094c334fdebbcceddf21f97cb16b144707af56eAdrian Hunter if (!keys_eq(c, key, &key1)) { 4851e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy ubifs_err("bad key in node at LEB %d:%d", 4861e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy zbr->lnum, zbr->offs); 487515315a123af641a9533e4ff0f178c470dc08fc7Artem Bityutskiy dbg_tnck(key, "looked for key "); 488515315a123af641a9533e4ff0f178c470dc08fc7Artem Bityutskiy dbg_tnck(&key1, "but found node's key "); 489edf6be245fd34a4438646375cecb11f5feb92646Artem Bityutskiy ubifs_dump_node(c, node); 4901e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return -EINVAL; 4911e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy } 4921e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy 4931e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy return 0; 4941e51764a3c2ac05a23a22b2a95ddee4d9bffb16dArtem Bityutskiy} 495