LCOV - code coverage report
Current view: top level - libubifs - key.h (source / functions) Hit Total Coverage
Test: a simple test Lines: 69 76 90.8 %
Date: 2024-06-05 20:10:43 Functions: 3 4 75.0 %
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: Artem Bityutskiy (Битюцкий Артём)
       8             :  *          Adrian Hunter
       9             :  */
      10             : 
      11             : /*
      12             :  * This header contains various key-related definitions and helper function.
      13             :  * UBIFS allows several key schemes, so we access key fields only via these
      14             :  * helpers. At the moment only one key scheme is supported.
      15             :  *
      16             :  * Simple key scheme
      17             :  * ~~~~~~~~~~~~~~~~~
      18             :  *
      19             :  * Keys are 64-bits long. First 32-bits are inode number (parent inode number
      20             :  * in case of direntry key). Next 3 bits are node type. The last 29 bits are
      21             :  * 4KiB offset in case of inode node, and direntry hash in case of a direntry
      22             :  * node. We use "r5" hash borrowed from reiserfs.
      23             :  */
      24             : 
      25             : /*
      26             :  * Lot's of the key helpers require a struct ubifs_info *c as the first parameter.
      27             :  * But we are not using it at all currently. That's designed for future extensions of
      28             :  * different c->key_format. But right now, there is only one key type, UBIFS_SIMPLE_KEY_FMT.
      29             :  */
      30             : 
      31             : #ifndef __UBIFS_KEY_H__
      32             : #define __UBIFS_KEY_H__
      33             : 
      34             : /**
      35             :  * key_mask_hash - mask a valid hash value.
      36             :  * @val: value to be masked
      37             :  *
      38             :  * We use hash values as offset in directories, so values %0 and %1 are
      39             :  * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This
      40             :  * function makes sure the reserved values are not used.
      41             :  */
      42             : static inline uint32_t key_mask_hash(uint32_t hash)
      43             : {
      44      125623 :         hash &= UBIFS_S_KEY_HASH_MASK;
      45      125623 :         if (unlikely(hash <= 2))
      46           0 :                 hash += 3;
      47             :         return hash;
      48             : }
      49             : 
      50             : /**
      51             :  * key_r5_hash - R5 hash function (borrowed from reiserfs).
      52             :  * @s: direntry name
      53             :  * @len: name length
      54             :  */
      55      125623 : static inline uint32_t key_r5_hash(const char *s, int len)
      56             : {
      57      125623 :         uint32_t a = 0;
      58      125623 :         const signed char *str = (const signed char *)s;
      59             : 
      60     1221462 :         while (len--) {
      61      970216 :                 a += *str << 4;
      62      970216 :                 a += *str >> 4;
      63      970216 :                 a *= 11;
      64      970216 :                 str++;
      65             :         }
      66             : 
      67      125623 :         return key_mask_hash(a);
      68             : }
      69             : 
      70             : /**
      71             :  * key_test_hash - testing hash function.
      72             :  * @str: direntry name
      73             :  * @len: name length
      74             :  */
      75           0 : static inline uint32_t key_test_hash(const char *str, int len)
      76             : {
      77           0 :         uint32_t a = 0;
      78             : 
      79           0 :         len = min_t(uint32_t, len, 4);
      80           0 :         memcpy(&a, str, len);
      81           0 :         return key_mask_hash(a);
      82             : }
      83             : 
      84             : /**
      85             :  * ino_key_init - initialize inode key.
      86             :  * @c: UBIFS file-system description object
      87             :  * @key: key to initialize
      88             :  * @inum: inode number
      89             :  */
      90             : static inline void ino_key_init(__unused const struct ubifs_info *c,
      91             :                                 union ubifs_key *key, ino_t inum)
      92             : {
      93      201606 :         key->u32[0] = inum;
      94      201606 :         key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS;
      95             : }
      96             : 
      97             : /**
      98             :  * ino_key_init_flash - initialize on-flash inode key.
      99             :  * @c: UBIFS file-system description object
     100             :  * @k: key to initialize
     101             :  * @inum: inode number
     102             :  */
     103             : static inline void ino_key_init_flash(__unused const struct ubifs_info *c,
     104             :                                       void *k, ino_t inum)
     105             : {
     106         470 :         union ubifs_key *key = k;
     107             : 
     108         470 :         key->j32[0] = cpu_to_le32(inum);
     109         470 :         key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
     110         470 :         memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
     111             : }
     112             : 
     113             : /**
     114             :  * lowest_ino_key - get the lowest possible inode key.
     115             :  * @c: UBIFS file-system description object
     116             :  * @key: key to initialize
     117             :  * @inum: inode number
     118             :  */
     119             : static inline void lowest_ino_key(__unused const struct ubifs_info *c,
     120             :                                   union ubifs_key *key, ino_t inum)
     121             : {
     122        5488 :         key->u32[0] = inum;
     123        5488 :         key->u32[1] = 0;
     124             : }
     125             : 
     126             : /**
     127             :  * highest_ino_key - get the highest possible inode key.
     128             :  * @c: UBIFS file-system description object
     129             :  * @key: key to initialize
     130             :  * @inum: inode number
     131             :  */
     132             : static inline void highest_ino_key(__unused const struct ubifs_info *c,
     133             :                                    union ubifs_key *key, ino_t inum)
     134             : {
     135        5488 :         key->u32[0] = inum;
     136        5488 :         key->u32[1] = 0xffffffff;
     137             : }
     138             : 
     139             : /**
     140             :  * dent_key_init - initialize directory entry key.
     141             :  * @c: UBIFS file-system description object
     142             :  * @key: key to initialize
     143             :  * @inum: parent inode number
     144             :  * @nm: direntry name and length. Not a string when encrypted!
     145             :  */
     146       92663 : static inline void dent_key_init(const struct ubifs_info *c,
     147             :                                  union ubifs_key *key, ino_t inum,
     148             :                                  const struct fscrypt_name *nm)
     149             : {
     150       92663 :         uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
     151             : 
     152       92663 :         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
     153       92663 :         key->u32[0] = inum;
     154       92663 :         key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
     155       92663 : }
     156             : 
     157             : /**
     158             :  * dent_key_init_hash - initialize directory entry key without re-calculating
     159             :  *                      hash function.
     160             :  * @c: UBIFS file-system description object
     161             :  * @key: key to initialize
     162             :  * @inum: parent inode number
     163             :  * @hash: direntry name hash
     164             :  */
     165             : static inline void dent_key_init_hash(const struct ubifs_info *c,
     166             :                                       union ubifs_key *key, ino_t inum,
     167             :                                       uint32_t hash)
     168             : {
     169             :         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
     170             :         key->u32[0] = inum;
     171             :         key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
     172             : }
     173             : 
     174             : /**
     175             :  * xent_key_init - initialize extended attribute entry key.
     176             :  * @c: UBIFS file-system description object
     177             :  * @key: key to initialize
     178             :  * @inum: host inode number
     179             :  * @nm: extended attribute entry name and length
     180             :  */
     181       32960 : static inline void xent_key_init(const struct ubifs_info *c,
     182             :                                  union ubifs_key *key, ino_t inum,
     183             :                                  const struct fscrypt_name *nm)
     184             : {
     185       32960 :         uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
     186             : 
     187       32960 :         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
     188       32960 :         key->u32[0] = inum;
     189       32960 :         key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
     190       32960 : }
     191             : 
     192             : /**
     193             :  * lowest_xent_key - get the lowest possible extended attribute entry key.
     194             :  * @c: UBIFS file-system description object
     195             :  * @key: where to store the lowest key
     196             :  * @inum: host inode number
     197             :  */
     198             : static inline void lowest_xent_key(__unused const struct ubifs_info *c,
     199             :                                    union ubifs_key *key, ino_t inum)
     200             : {
     201        4747 :         key->u32[0] = inum;
     202        4747 :         key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
     203             : }
     204             : 
     205             : /**
     206             :  * data_key_init - initialize data key.
     207             :  * @c: UBIFS file-system description object
     208             :  * @key: key to initialize
     209             :  * @inum: inode number
     210             :  * @block: block number
     211             :  */
     212             : static inline void data_key_init(const struct ubifs_info *c,
     213             :                                  union ubifs_key *key, ino_t inum,
     214             :                                  unsigned int block)
     215             : {
     216     1192518 :         ubifs_assert(c, !(block & ~UBIFS_S_KEY_BLOCK_MASK));
     217     1192518 :         key->u32[0] = inum;
     218     1192518 :         key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
     219             : }
     220             : 
     221             : /**
     222             :  * highest_data_key - get the highest possible data key for an inode.
     223             :  * @c: UBIFS file-system description object
     224             :  * @key: key to initialize
     225             :  * @inum: inode number
     226             :  */
     227             : static inline void highest_data_key(const struct ubifs_info *c,
     228             :                                     union ubifs_key *key, ino_t inum)
     229             : {
     230             :         data_key_init(c, key, inum, UBIFS_S_KEY_BLOCK_MASK);
     231             : }
     232             : 
     233             : /**
     234             :  * trun_key_init - initialize truncation node key.
     235             :  * @c: UBIFS file-system description object
     236             :  * @key: key to initialize
     237             :  * @inum: inode number
     238             :  *
     239             :  * Note, UBIFS does not have truncation keys on the media and this function is
     240             :  * only used for purposes of replay.
     241             :  */
     242             : static inline void trun_key_init(__unused const struct ubifs_info *c,
     243             :                                  union ubifs_key *key, ino_t inum)
     244             : {
     245      331282 :         key->u32[0] = inum;
     246      331282 :         key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
     247             : }
     248             : 
     249             : /**
     250             :  * invalid_key_init - initialize invalid node key.
     251             :  * @c: UBIFS file-system description object
     252             :  * @key: key to initialize
     253             :  *
     254             :  * This is a helper function which marks a @key object as invalid.
     255             :  */
     256             : static inline void invalid_key_init(__unused const struct ubifs_info *c,
     257             :                                     union ubifs_key *key)
     258             : {
     259  5049082841 :         key->u32[0] = 0xDEADBEAF;
     260  5049082841 :         key->u32[1] = UBIFS_INVALID_KEY;
     261             : }
     262             : 
     263             : /**
     264             :  * key_type - get key type.
     265             :  * @c: UBIFS file-system description object
     266             :  * @key: key to get type of
     267             :  */
     268             : static inline int key_type(__unused const struct ubifs_info *c,
     269             :                            const union ubifs_key *key)
     270             : {
     271 26324366815 :         return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
     272             : }
     273             : 
     274             : /**
     275             :  * key_type_flash - get type of a on-flash formatted key.
     276             :  * @c: UBIFS file-system description object
     277             :  * @k: key to get type of
     278             :  */
     279             : static inline int key_type_flash(__unused const struct ubifs_info *c,
     280             :                                  const void *k)
     281             : {
     282   240132460 :         const union ubifs_key *key = k;
     283             : 
     284   240132460 :         return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
     285             : }
     286             : 
     287             : /**
     288             :  * key_inum - fetch inode number from key.
     289             :  * @c: UBIFS file-system description object
     290             :  * @k: key to fetch inode number from
     291             :  */
     292             : static inline ino_t key_inum(__unused const struct ubifs_info *c, const void *k)
     293             : {
     294  5523452996 :         const union ubifs_key *key = k;
     295             : 
     296  5523422856 :         return key->u32[0];
     297             : }
     298             : 
     299             : /**
     300             :  * key_inum_flash - fetch inode number from an on-flash formatted key.
     301             :  * @c: UBIFS file-system description object
     302             :  * @k: key to fetch inode number from
     303             :  */
     304             : static inline ino_t key_inum_flash(__unused const struct ubifs_info *c,
     305             :                                    const void *k)
     306             : {
     307             :         const union ubifs_key *key = k;
     308             : 
     309             :         return le32_to_cpu(key->j32[0]);
     310             : }
     311             : 
     312             : /**
     313             :  * key_hash - get directory entry hash.
     314             :  * @c: UBIFS file-system description object
     315             :  * @key: the key to get hash from
     316             :  */
     317             : static inline uint32_t key_hash(__unused const struct ubifs_info *c,
     318             :                                 const union ubifs_key *key)
     319             : {
     320      155254 :         return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
     321             : }
     322             : 
     323             : /**
     324             :  * key_hash_flash - get directory entry hash from an on-flash formatted key.
     325             :  * @c: UBIFS file-system description object
     326             :  * @k: the key to get hash from
     327             :  */
     328             : static inline uint32_t key_hash_flash(__unused const struct ubifs_info *c,
     329             :                                       const void *k)
     330             : {
     331             :         const union ubifs_key *key = k;
     332             : 
     333             :         return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
     334             : }
     335             : 
     336             : /**
     337             :  * key_block - get data block number.
     338             :  * @c: UBIFS file-system description object
     339             :  * @key: the key to get the block number from
     340             :  */
     341             : static inline unsigned int key_block(__unused const struct ubifs_info *c,
     342             :                                      const union ubifs_key *key)
     343             : {
     344  2209251763 :         return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
     345             : }
     346             : 
     347             : /**
     348             :  * key_block_flash - get data block number from an on-flash formatted key.
     349             :  * @c: UBIFS file-system description object
     350             :  * @k: the key to get the block number from
     351             :  */
     352             : static inline unsigned int key_block_flash(__unused const struct ubifs_info *c,
     353             :                                            const void *k)
     354             : {
     355             :         const union ubifs_key *key = k;
     356             : 
     357             :         return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK;
     358             : }
     359             : 
     360             : /**
     361             :  * key_read - transform a key to in-memory format.
     362             :  * @c: UBIFS file-system description object
     363             :  * @from: the key to transform
     364             :  * @to: the key to store the result
     365             :  */
     366             : static inline void key_read(__unused const struct ubifs_info *c,
     367             :                             const void *from, union ubifs_key *to)
     368             : {
     369 16116874498 :         const union ubifs_key *f = from;
     370             : 
     371 16116874498 :         to->u32[0] = le32_to_cpu(f->j32[0]);
     372 16116874498 :         to->u32[1] = le32_to_cpu(f->j32[1]);
     373             : }
     374             : 
     375             : /**
     376             :  * key_write - transform a key from in-memory format.
     377             :  * @c: UBIFS file-system description object
     378             :  * @from: the key to transform
     379             :  * @to: the key to store the result
     380             :  */
     381             : static inline void key_write(__unused const struct ubifs_info *c,
     382             :                              const union ubifs_key *from, void *to)
     383             : {
     384     1429352 :         union ubifs_key *t = to;
     385             : 
     386     1429352 :         t->j32[0] = cpu_to_le32(from->u32[0]);
     387     1429352 :         t->j32[1] = cpu_to_le32(from->u32[1]);
     388     1429352 :         memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
     389             : }
     390             : 
     391             : /**
     392             :  * key_write_idx - transform a key from in-memory format for the index.
     393             :  * @c: UBIFS file-system description object
     394             :  * @from: the key to transform
     395             :  * @to: the key to store the result
     396             :  */
     397             : static inline void key_write_idx(__unused const struct ubifs_info *c,
     398             :                                  const union ubifs_key *from, void *to)
     399             : {
     400   123090022 :         union ubifs_key *t = to;
     401             : 
     402   123090022 :         t->j32[0] = cpu_to_le32(from->u32[0]);
     403   123090022 :         t->j32[1] = cpu_to_le32(from->u32[1]);
     404             : }
     405             : 
     406             : /**
     407             :  * key_copy - copy a key.
     408             :  * @c: UBIFS file-system description object
     409             :  * @from: the key to copy from
     410             :  * @to: the key to copy to
     411             :  */
     412             : static inline void key_copy(__unused const struct ubifs_info *c,
     413             :                             const union ubifs_key *from, union ubifs_key *to)
     414             : {
     415  2902982423 :         to->u64[0] = from->u64[0];
     416             : }
     417             : 
     418             : /**
     419             :  * keys_cmp - compare keys.
     420             :  * @c: UBIFS file-system description object
     421             :  * @key1: the first key to compare
     422             :  * @key2: the second key to compare
     423             :  *
     424             :  * This function compares 2 keys and returns %-1 if @key1 is less than
     425             :  * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
     426             :  */
     427             : static inline int keys_cmp(__unused const struct ubifs_info *c,
     428             :                            const union ubifs_key *key1,
     429             :                            const union ubifs_key *key2)
     430             : {
     431 >25215*10^7 :         if (key1->u32[0] < key2->u32[0])
     432             :                 return -1;
     433 >16736*10^7 :         if (key1->u32[0] > key2->u32[0])
     434             :                 return 1;
     435 61156780271 :         if (key1->u32[1] < key2->u32[1])
     436             :                 return -1;
     437 41037522593 :         if (key1->u32[1] > key2->u32[1])
     438             :                 return 1;
     439             : 
     440             :         return 0;
     441             : }
     442             : 
     443             : /**
     444             :  * keys_eq - determine if keys are equivalent.
     445             :  * @c: UBIFS file-system description object
     446             :  * @key1: the first key to compare
     447             :  * @key2: the second key to compare
     448             :  *
     449             :  * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
     450             :  * %0 if not.
     451             :  */
     452             : static inline int keys_eq(__unused const struct ubifs_info *c,
     453             :                           const union ubifs_key *key1,
     454             :                           const union ubifs_key *key2)
     455             : {
     456  2491455525 :         if (key1->u32[0] != key2->u32[0])
     457             :                 return 0;
     458  2491455525 :         if (key1->u32[1] != key2->u32[1])
     459             :                 return 0;
     460             :         return 1;
     461             : }
     462             : 
     463             : /**
     464             :  * is_hash_key - is a key vulnerable to hash collisions.
     465             :  * @c: UBIFS file-system description object
     466             :  * @key: key
     467             :  *
     468             :  * This function returns %1 if @key is a hashed key or %0 otherwise.
     469             :  */
     470             : static inline int is_hash_key(const struct ubifs_info *c,
     471             :                               const union ubifs_key *key)
     472             : {
     473 13010150648 :         int type = key_type(c, key);
     474             : 
     475  6505075324 :         return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
     476             : }
     477             : 
     478             : /**
     479             :  * key_max_inode_size - get maximum file size allowed by current key format.
     480             :  * @c: UBIFS file-system description object
     481             :  */
     482             : static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
     483             : {
     484        2340 :         switch (c->key_fmt) {
     485             :         case UBIFS_SIMPLE_KEY_FMT:
     486             :                 return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
     487           0 :         default:
     488             :                 return 0;
     489             :         }
     490             : }
     491             : 
     492             : #endif /* !__UBIFS_KEY_H__ */

Generated by: LCOV version 1.13