LCOV - code coverage report
Current view: top level - libubifs - tnc_misc.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 130 142 91.5 %
Date: 2024-06-05 20:10:43 Functions: 7 8 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // SPDX-License-Identifier: GPL-2.0-only
       2             : /*
       3             :  * This file is part of UBIFS.
       4             :  *
       5             :  * Copyright (C) 2006-2008 Nokia Corporation.
       6             :  *
       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             : 
      18             : #include "linux_err.h"
      19             : #include "bitops.h"
      20             : #include "kmem.h"
      21             : #include "ubifs.h"
      22             : #include "defs.h"
      23             : #include "debug.h"
      24             : #include "key.h"
      25             : #include "misc.h"
      26             : 
      27             : /**
      28             :  * ubifs_search_zbranch - search znode branch.
      29             :  * @c: UBIFS file-system description object
      30             :  * @znode: znode to search in
      31             :  * @key: key to search for
      32             :  * @n: znode branch slot number is returned here
      33             :  *
      34             :  * This is a helper function which search branch with key @key in @znode using
      35             :  * binary search. The result of the search may be:
      36             :  *   o exact match, then %1 is returned, and the slot number of the branch is
      37             :  *     stored in @n;
      38             :  *   o no exact match, then %0 is returned and the slot number of the left
      39             :  *     closest branch is returned in @n; the slot if all keys in this znode are
      40             :  *     greater than @key, then %-1 is returned in @n.
      41             :  */
      42 55851721955 : int ubifs_search_zbranch(const struct ubifs_info *c,
      43             :                          const struct ubifs_znode *znode,
      44             :                          const union ubifs_key *key, int *n)
      45             : {
      46 55851721955 :         int beg = 0, end = znode->child_cnt, mid;
      47             :         int cmp;
      48 55851721955 :         const struct ubifs_zbranch *zbr = &znode->zbranch[0];
      49             : 
      50 55851721955 :         if (!end) {
      51             :                 /* Different with linux kernel, TNC could become empty. */
      52           0 :                 *n = -1;
      53           0 :                 return 0;
      54             :         }
      55             : 
      56 55851721955 :         ubifs_assert(c, end > beg);
      57             : 
      58 >19107*10^7 :         while (end > beg) {
      59 >14225*10^7 :                 mid = (beg + end) >> 1;
      60 >14225*10^7 :                 cmp = keys_cmp(c, key, &zbr[mid].key);
      61             :                 if (cmp > 0)
      62 72829694804 :                         beg = mid + 1;
      63 69424269388 :                 else if (cmp < 0)
      64             :                         end = mid;
      65             :                 else {
      66  7029829231 :                         *n = mid;
      67  7029829231 :                         return 1;
      68             :                 }
      69             :         }
      70             : 
      71 48821892724 :         *n = end - 1;
      72             : 
      73             :         /* The insert point is after *n */
      74 48821892724 :         ubifs_assert(c, *n >= -1 && *n < znode->child_cnt);
      75 48821892724 :         if (*n == -1)
      76   393874766 :                 ubifs_assert(c, keys_cmp(c, key, &zbr[0].key) < 0);
      77             :         else
      78 48428017958 :                 ubifs_assert(c, keys_cmp(c, key, &zbr[*n].key) > 0);
      79 48821892724 :         if (*n + 1 < znode->child_cnt)
      80 37467544433 :                 ubifs_assert(c, keys_cmp(c, key, &zbr[*n + 1].key) < 0);
      81             : 
      82             :         return 0;
      83             : }
      84             : 
      85             : /**
      86             :  * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal.
      87             :  * @znode: znode to start at (root of the sub-tree to traverse)
      88             :  *
      89             :  * Find the lowest leftmost znode in a subtree of the TNC tree. The LNC is
      90             :  * ignored.
      91             :  */
      92           0 : struct ubifs_znode *ubifs_tnc_postorder_first(struct ubifs_znode *znode)
      93             : {
      94        1933 :         if (unlikely(!znode))
      95             :                 return NULL;
      96             : 
      97   567162990 :         while (znode->level > 0) {
      98             :                 struct ubifs_znode *child;
      99             : 
     100   111784912 :                 child = ubifs_tnc_find_child(znode, 0);
     101   111784912 :                 if (!child)
     102             :                         return znode;
     103             :                 znode = child;
     104             :         }
     105             : 
     106             :         return znode;
     107             : }
     108             : 
     109             : /**
     110             :  * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal.
     111             :  * @c: UBIFS file-system description object
     112             :  * @znode: previous znode
     113             :  *
     114             :  * This function implements postorder TNC traversal. The LNC is ignored.
     115             :  * Returns the next element or %NULL if @znode is already the last one.
     116             :  */
     117   567161057 : struct ubifs_znode *ubifs_tnc_postorder_next(const struct ubifs_info *c,
     118             :                                              struct ubifs_znode *znode)
     119             : {
     120             :         struct ubifs_znode *zn;
     121             : 
     122   567161057 :         ubifs_assert(c, znode);
     123   567161057 :         if (unlikely(!znode->parent))
     124             :                 return NULL;
     125             : 
     126             :         /* Switch to the next index in the parent */
     127  1134322114 :         zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1);
     128   567161057 :         if (!zn)
     129             :                 /* This is in fact the last child, return parent */
     130             :                 return znode->parent;
     131             : 
     132             :         /* Go to the first znode in this new subtree */
     133             :         return ubifs_tnc_postorder_first(zn);
     134             : }
     135             : 
     136             : /**
     137             :  * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree.
     138             :  * @c: UBIFS file-system description object
     139             :  * @znode: znode defining subtree to destroy
     140             :  *
     141             :  * This function destroys subtree of the TNC tree. Returns number of clean
     142             :  * znodes in the subtree.
     143             :  */
     144        1933 : long ubifs_destroy_tnc_subtree(const struct ubifs_info *c,
     145             :                                struct ubifs_znode *znode)
     146             : {
     147             :         struct ubifs_znode *zn = ubifs_tnc_postorder_first(znode);
     148             :         long clean_freed = 0;
     149             :         int n;
     150             : 
     151           0 :         ubifs_assert(c, zn);
     152             :         while (1) {
     153  4190923056 :                 for (n = 0; n < zn->child_cnt; n++) {
     154  3056599009 :                         if (!zn->zbranch[n].znode)
     155  2489102557 :                                 continue;
     156             : 
     157  1134657509 :                         if (zn->level > 0 &&
     158  1134322114 :                             !ubifs_zn_dirty(zn->zbranch[n].znode))
     159   567026874 :                                 clean_freed += 1;
     160             : 
     161             :                         cond_resched();
     162   567496452 :                         kfree(zn->zbranch[n].znode);
     163             :                 }
     164             : 
     165   567162990 :                 if (zn == znode) {
     166        1933 :                         if (!ubifs_zn_dirty(zn))
     167        1888 :                                 clean_freed += 1;
     168        1933 :                         kfree(zn);
     169        1933 :                         return clean_freed;
     170             :                 }
     171             : 
     172   567161057 :                 zn = ubifs_tnc_postorder_next(c, zn);
     173             :         }
     174             : }
     175             : 
     176             : /**
     177             :  * ubifs_destroy_tnc_tree - destroy all znodes connected to the TNC tree.
     178             :  * @c: UBIFS file-system description object
     179             :  *
     180             :  * This function destroys the whole TNC tree and updates clean global znode
     181             :  * count.
     182             :  */
     183        1951 : void ubifs_destroy_tnc_tree(struct ubifs_info *c)
     184             : {
     185             :         long n, freed;
     186             : 
     187        1951 :         if (!c->zroot.znode)
     188             :                 return;
     189             : 
     190        1933 :         n = atomic_long_read(&c->clean_zn_cnt);
     191        1933 :         freed = ubifs_destroy_tnc_subtree(c, c->zroot.znode);
     192        1933 :         ubifs_assert(c, freed == n);
     193        3866 :         atomic_long_sub(n, &ubifs_clean_zn_cnt);
     194             : 
     195        1933 :         c->zroot.znode = NULL;
     196             : }
     197             : 
     198             : /**
     199             :  * read_znode - read an indexing node from flash and fill znode.
     200             :  * @c: UBIFS file-system description object
     201             :  * @zzbr: the zbranch describing the node to read
     202             :  * @znode: znode to read to
     203             :  *
     204             :  * This function reads an indexing node from the flash media and fills znode
     205             :  * with the read data. Returns zero in case of success and a negative error
     206             :  * code in case of failure. The read indexing node is validated and if anything
     207             :  * is wrong with it, this function prints complaint messages and returns
     208             :  * %-EINVAL.
     209             :  */
     210   567496017 : static int read_znode(struct ubifs_info *c, struct ubifs_zbranch *zzbr,
     211             :                       struct ubifs_znode *znode)
     212             : {
     213   567496017 :         int lnum = zzbr->lnum;
     214   567496017 :         int offs = zzbr->offs;
     215   567496017 :         int len = zzbr->len;
     216             :         int i, err, type, cmp;
     217             :         struct ubifs_idx_node *idx;
     218             : 
     219   567496017 :         idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);
     220   567496017 :         if (!idx)
     221             :                 return -ENOMEM;
     222             : 
     223   567496017 :         err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
     224   567496017 :         if (err < 0) {
     225         298 :                 if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED))
     226             :                         set_failure_reason_callback(c, FR_TNC_CORRUPTED);
     227         298 :                 kfree(idx);
     228             :                 return err;
     229             :         }
     230             : 
     231   567495719 :         err = ubifs_node_check_hash(c, idx, zzbr->hash);
     232             :         if (err) {
     233             :                 ubifs_bad_hash(c, idx, zzbr->hash, lnum, offs);
     234             :                 kfree(idx);
     235             :                 return err;
     236             :         }
     237             : 
     238   567495719 :         znode->child_cnt = le16_to_cpu(idx->child_cnt);
     239   567495719 :         znode->level = le16_to_cpu(idx->level);
     240             : 
     241   567495719 :         dbg_tnc("LEB %d:%d, level %d, %d branch",
     242             :                 lnum, offs, znode->level, znode->child_cnt);
     243             : 
     244   567495719 :         if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) {
     245           0 :                 ubifs_err(c, "current fanout %d, branch count %d",
     246             :                           c->fanout, znode->child_cnt);
     247           0 :                 ubifs_err(c, "max levels %d, znode level %d",
     248             :                           UBIFS_MAX_LEVELS, znode->level);
     249             :                 err = 1;
     250             :                 goto out_dump;
     251             :         }
     252             : 
     253  3059129393 :         for (i = 0; i < znode->child_cnt; i++) {
     254  3059129449 :                 struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
     255  3059129449 :                 struct ubifs_zbranch *zbr = &znode->zbranch[i];
     256             : 
     257  6118258898 :                 key_read(c, &br->key, &zbr->key);
     258  3059129449 :                 zbr->lnum = le32_to_cpu(br->lnum);
     259  3059129449 :                 zbr->offs = le32_to_cpu(br->offs);
     260  3059129449 :                 zbr->len  = le32_to_cpu(br->len);
     261  9177388347 :                 ubifs_copy_hash(c, ubifs_branch_hash(c, br), zbr->hash);
     262  3059129449 :                 zbr->znode = NULL;
     263             : 
     264             :                 /* Validate branch */
     265             : 
     266  6118258898 :                 if (zbr->lnum < c->main_first ||
     267  9177388347 :                     zbr->lnum >= c->leb_cnt || zbr->offs < 0 ||
     268  6118258898 :                     zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) {
     269          18 :                         ubifs_err(c, "bad branch %d", i);
     270             :                         err = 2;
     271             :                         goto out_dump;
     272             :                 }
     273             : 
     274  6118258862 :                 switch (key_type(c, &zbr->key)) {
     275             :                 case UBIFS_INO_KEY:
     276             :                 case UBIFS_DATA_KEY:
     277             :                 case UBIFS_DENT_KEY:
     278             :                 case UBIFS_XENT_KEY:
     279             :                         break;
     280           0 :                 default:
     281           0 :                         ubifs_err(c, "bad key type at slot %d: %d",
     282             :                                   i, key_type(c, &zbr->key));
     283             :                         err = 3;
     284             :                         goto out_dump;
     285             :                 }
     286             : 
     287  3059129431 :                 if (znode->level)
     288             :                         type = UBIFS_IDX_NODE;
     289             :                 else
     290  2491617872 :                         type = key_type(c, &zbr->key);
     291             : 
     292  3059129431 :                 if (c->ranges[type].max_len == 0) {
     293           0 :                         if (zbr->len != c->ranges[type].len) {
     294           0 :                                 ubifs_err(c, "bad target node (type %d) length (%d)",
     295             :                                           type, zbr->len);
     296           0 :                                 ubifs_err(c, "have to be %d", c->ranges[type].len);
     297             :                                 err = 4;
     298             :                                 goto out_dump;
     299             :                         }
     300  3059129431 :                 } else if (zbr->len < c->ranges[type].min_len ||
     301             :                            zbr->len > c->ranges[type].max_len) {
     302          38 :                         ubifs_err(c, "bad target node (type %d) length (%d)",
     303             :                                   type, zbr->len);
     304          38 :                         ubifs_err(c, "have to be in range of %d-%d",
     305             :                                   c->ranges[type].min_len,
     306             :                                   c->ranges[type].max_len);
     307             :                         err = 5;
     308             :                         goto out_dump;
     309             :                 }
     310             :         }
     311             : 
     312             :         /*
     313             :          * Ensure that the next key is greater or equivalent to the
     314             :          * previous one.
     315             :          */
     316  3059129239 :         for (i = 0; i < znode->child_cnt - 1; i++) {
     317             :                 const union ubifs_key *key1, *key2;
     318             : 
     319  2491633602 :                 key1 = &znode->zbranch[i].key;
     320  2491633602 :                 key2 = &znode->zbranch[i + 1].key;
     321             : 
     322  2491633602 :                 cmp = keys_cmp(c, key1, key2);
     323             :                 if (cmp > 0) {
     324          26 :                         ubifs_err(c, "bad key order (keys %d and %d)", i, i + 1);
     325             :                         err = 6;
     326             :                         goto out_dump;
     327  2491633576 :                 } else if (cmp == 0 && !is_hash_key(c, key1)) {
     328             :                         /* These can only be keys with colliding hash */
     329           0 :                         ubifs_err(c, "keys %d and %d are not hashed but equivalent",
     330             :                                   i, i + 1);
     331             :                         err = 7;
     332             :                         goto out_dump;
     333             :                 }
     334             :         }
     335             : 
     336   567495637 :         kfree(idx);
     337             :         return 0;
     338             : 
     339          82 : out_dump:
     340          82 :         set_failure_reason_callback(c, FR_TNC_CORRUPTED);
     341          82 :         ubifs_err(c, "bad indexing node at LEB %d:%d, error %d", lnum, offs, err);
     342          82 :         ubifs_dump_node(c, idx, c->max_idx_node_sz);
     343          82 :         kfree(idx);
     344             :         return -EINVAL;
     345             : }
     346             : 
     347             : /**
     348             :  * ubifs_load_znode - load znode to TNC cache.
     349             :  * @c: UBIFS file-system description object
     350             :  * @zbr: znode branch
     351             :  * @parent: znode's parent
     352             :  * @iip: index in parent
     353             :  *
     354             :  * This function loads znode pointed to by @zbr into the TNC cache and
     355             :  * returns pointer to it in case of success and a negative error code in case
     356             :  * of failure.
     357             :  */
     358   567496017 : struct ubifs_znode *ubifs_load_znode(struct ubifs_info *c,
     359             :                                      struct ubifs_zbranch *zbr,
     360             :                                      struct ubifs_znode *parent, int iip)
     361             : {
     362             :         int err;
     363             :         struct ubifs_znode *znode;
     364             : 
     365   567496017 :         ubifs_assert(c, !zbr->znode);
     366             :         /*
     367             :          * A slab cache is not presently used for znodes because the znode size
     368             :          * depends on the fanout which is stored in the superblock.
     369             :          */
     370  1134992034 :         znode = kzalloc(c->max_znode_sz, GFP_NOFS);
     371   567496017 :         if (!znode)
     372             :                 return ERR_PTR(-ENOMEM);
     373             : 
     374   567496017 :         err = read_znode(c, zbr, znode);
     375   567496017 :         if (err)
     376             :                 goto out;
     377             : 
     378  1134991274 :         atomic_long_inc(&c->clean_zn_cnt);
     379             : 
     380             :         /*
     381             :          * Increment the global clean znode counter as well. It is OK that
     382             :          * global and per-FS clean znode counters may be inconsistent for some
     383             :          * short time (because we might be preempted at this point), the global
     384             :          * one is only used in shrinker.
     385             :          */
     386   567495637 :         atomic_long_inc(&ubifs_clean_zn_cnt);
     387             : 
     388   567495637 :         zbr->znode = znode;
     389   567495637 :         znode->parent = parent;
     390   567495637 :         znode->time = ktime_get_seconds();
     391   567495637 :         znode->iip = iip;
     392             : 
     393   567495637 :         return znode;
     394             : 
     395         380 : out:
     396         380 :         kfree(znode);
     397         760 :         return ERR_PTR(err);
     398             : }
     399             : 
     400             : /**
     401             :  * ubifs_tnc_read_node - read a leaf node from the flash media.
     402             :  * @c: UBIFS file-system description object
     403             :  * @zbr: key and position of the node
     404             :  * @node: node is returned here
     405             :  *
     406             :  * This function reads a node defined by @zbr from the flash media. Returns
     407             :  * zero in case of success or a negative error code in case of failure.
     408             :  */
     409  2491640519 : int ubifs_tnc_read_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,
     410             :                         void *node)
     411             : {
     412  2491640519 :         union ubifs_key key1, *key = &zbr->key;
     413  4983281038 :         int err, type = key_type(c, key);
     414             :         struct ubifs_wbuf *wbuf;
     415             : 
     416             :         /*
     417             :          * 'zbr' has to point to on-flash node. The node may sit in a bud and
     418             :          * may even be in a write buffer, so we have to take care about this.
     419             :          */
     420  2491640519 :         wbuf = ubifs_get_wbuf(c, zbr->lnum);
     421  2491640519 :         if (wbuf)
     422     4310261 :                 err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len,
     423             :                                            zbr->lnum, zbr->offs);
     424             :         else
     425  2487330258 :                 err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum,
     426             :                                       zbr->offs);
     427             : 
     428  2491640517 :         if (err) {
     429      184992 :                 dbg_tnck(key, "key ");
     430      184992 :                 return err;
     431             :         }
     432             : 
     433             :         /* Make sure the key of the read node is correct */
     434  4982911050 :         key_read(c, node + UBIFS_KEY_OFFSET, &key1);
     435  2491455525 :         if (!keys_eq(c, key, &key1)) {
     436          18 :                 set_failure_reason_callback(c, FR_DATA_CORRUPTED);
     437          18 :                 ubifs_err(c, "bad key in node at LEB %d:%d",
     438             :                           zbr->lnum, zbr->offs);
     439          18 :                 dbg_tnck(key, "looked for key ");
     440          18 :                 dbg_tnck(&key1, "but found node's key ");
     441          18 :                 ubifs_dump_node(c, node, zbr->len);
     442          18 :                 return -EINVAL;
     443             :         }
     444             : 
     445             :         err = ubifs_node_check_hash(c, node, zbr->hash);
     446             :         if (err) {
     447             :                 ubifs_bad_hash(c, node, zbr->hash, zbr->lnum, zbr->offs);
     448             :                 return err;
     449             :         }
     450             : 
     451             :         return 0;
     452             : }

Generated by: LCOV version 1.13