Back to home page

OSCL-LXR
 
 

     

0001 /* SPDX-License-Identifier: GPL-2.0-only */
0002 /*
0003  * This file is part of UBIFS.
0004  *
0005  * Copyright (C) 2006-2008 Nokia Corporation.
0006  *
0007  * Authors: Artem Bityutskiy (Битюцкий Артём)
0008  *          Adrian Hunter
0009  */
0010 
0011 /*
0012  * This header contains various key-related definitions and helper function.
0013  * UBIFS allows several key schemes, so we access key fields only via these
0014  * helpers. At the moment only one key scheme is supported.
0015  *
0016  * Simple key scheme
0017  * ~~~~~~~~~~~~~~~~~
0018  *
0019  * Keys are 64-bits long. First 32-bits are inode number (parent inode number
0020  * in case of direntry key). Next 3 bits are node type. The last 29 bits are
0021  * 4KiB offset in case of inode node, and direntry hash in case of a direntry
0022  * node. We use "r5" hash borrowed from reiserfs.
0023  */
0024 
0025 /*
0026  * Lot's of the key helpers require a struct ubifs_info *c as the first parameter.
0027  * But we are not using it at all currently. That's designed for future extensions of
0028  * different c->key_format. But right now, there is only one key type, UBIFS_SIMPLE_KEY_FMT.
0029  */
0030 
0031 #ifndef __UBIFS_KEY_H__
0032 #define __UBIFS_KEY_H__
0033 
0034 /**
0035  * key_mask_hash - mask a valid hash value.
0036  * @val: value to be masked
0037  *
0038  * We use hash values as offset in directories, so values %0 and %1 are
0039  * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This
0040  * function makes sure the reserved values are not used.
0041  */
0042 static inline uint32_t key_mask_hash(uint32_t hash)
0043 {
0044     hash &= UBIFS_S_KEY_HASH_MASK;
0045     if (unlikely(hash <= 2))
0046         hash += 3;
0047     return hash;
0048 }
0049 
0050 /**
0051  * key_r5_hash - R5 hash function (borrowed from reiserfs).
0052  * @s: direntry name
0053  * @len: name length
0054  */
0055 static inline uint32_t key_r5_hash(const char *s, int len)
0056 {
0057     uint32_t a = 0;
0058     const signed char *str = (const signed char *)s;
0059 
0060     while (len--) {
0061         a += *str << 4;
0062         a += *str >> 4;
0063         a *= 11;
0064         str++;
0065     }
0066 
0067     return key_mask_hash(a);
0068 }
0069 
0070 /**
0071  * key_test_hash - testing hash function.
0072  * @str: direntry name
0073  * @len: name length
0074  */
0075 static inline uint32_t key_test_hash(const char *str, int len)
0076 {
0077     uint32_t a = 0;
0078 
0079     len = min_t(uint32_t, len, 4);
0080     memcpy(&a, str, len);
0081     return key_mask_hash(a);
0082 }
0083 
0084 /**
0085  * ino_key_init - initialize inode key.
0086  * @c: UBIFS file-system description object
0087  * @key: key to initialize
0088  * @inum: inode number
0089  */
0090 static inline void ino_key_init(const struct ubifs_info *c,
0091                 union ubifs_key *key, ino_t inum)
0092 {
0093     key->u32[0] = inum;
0094     key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS;
0095 }
0096 
0097 /**
0098  * ino_key_init_flash - initialize on-flash inode key.
0099  * @c: UBIFS file-system description object
0100  * @k: key to initialize
0101  * @inum: inode number
0102  */
0103 static inline void ino_key_init_flash(const struct ubifs_info *c, void *k,
0104                       ino_t inum)
0105 {
0106     union ubifs_key *key = k;
0107 
0108     key->j32[0] = cpu_to_le32(inum);
0109     key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
0110     memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
0111 }
0112 
0113 /**
0114  * lowest_ino_key - get the lowest possible inode key.
0115  * @c: UBIFS file-system description object
0116  * @key: key to initialize
0117  * @inum: inode number
0118  */
0119 static inline void lowest_ino_key(const struct ubifs_info *c,
0120                 union ubifs_key *key, ino_t inum)
0121 {
0122     key->u32[0] = inum;
0123     key->u32[1] = 0;
0124 }
0125 
0126 /**
0127  * highest_ino_key - get the highest possible inode key.
0128  * @c: UBIFS file-system description object
0129  * @key: key to initialize
0130  * @inum: inode number
0131  */
0132 static inline void highest_ino_key(const struct ubifs_info *c,
0133                 union ubifs_key *key, ino_t inum)
0134 {
0135     key->u32[0] = inum;
0136     key->u32[1] = 0xffffffff;
0137 }
0138 
0139 /**
0140  * dent_key_init - initialize directory entry key.
0141  * @c: UBIFS file-system description object
0142  * @key: key to initialize
0143  * @inum: parent inode number
0144  * @nm: direntry name and length. Not a string when encrypted!
0145  */
0146 static inline void dent_key_init(const struct ubifs_info *c,
0147                  union ubifs_key *key, ino_t inum,
0148                  const struct fscrypt_name *nm)
0149 {
0150     uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
0151 
0152     ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
0153     key->u32[0] = inum;
0154     key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
0155 }
0156 
0157 /**
0158  * dent_key_init_hash - initialize directory entry key without re-calculating
0159  *                      hash function.
0160  * @c: UBIFS file-system description object
0161  * @key: key to initialize
0162  * @inum: parent inode number
0163  * @hash: direntry name hash
0164  */
0165 static inline void dent_key_init_hash(const struct ubifs_info *c,
0166                       union ubifs_key *key, ino_t inum,
0167                       uint32_t hash)
0168 {
0169     ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
0170     key->u32[0] = inum;
0171     key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
0172 }
0173 
0174 /**
0175  * dent_key_init_flash - initialize on-flash directory entry key.
0176  * @c: UBIFS file-system description object
0177  * @k: key to initialize
0178  * @inum: parent inode number
0179  * @nm: direntry name and length
0180  */
0181 static inline void dent_key_init_flash(const struct ubifs_info *c, void *k,
0182                        ino_t inum,
0183                        const struct fscrypt_name *nm)
0184 {
0185     union ubifs_key *key = k;
0186     uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
0187 
0188     ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
0189     key->j32[0] = cpu_to_le32(inum);
0190     key->j32[1] = cpu_to_le32(hash |
0191                   (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS));
0192     memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
0193 }
0194 
0195 /**
0196  * lowest_dent_key - get the lowest possible directory entry key.
0197  * @c: UBIFS file-system description object
0198  * @key: where to store the lowest key
0199  * @inum: parent inode number
0200  */
0201 static inline void lowest_dent_key(const struct ubifs_info *c,
0202                    union ubifs_key *key, ino_t inum)
0203 {
0204     key->u32[0] = inum;
0205     key->u32[1] = UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS;
0206 }
0207 
0208 /**
0209  * xent_key_init - initialize extended attribute entry key.
0210  * @c: UBIFS file-system description object
0211  * @key: key to initialize
0212  * @inum: host inode number
0213  * @nm: extended attribute entry name and length
0214  */
0215 static inline void xent_key_init(const struct ubifs_info *c,
0216                  union ubifs_key *key, ino_t inum,
0217                  const struct fscrypt_name *nm)
0218 {
0219     uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
0220 
0221     ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
0222     key->u32[0] = inum;
0223     key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
0224 }
0225 
0226 /**
0227  * xent_key_init_flash - initialize on-flash extended attribute entry key.
0228  * @c: UBIFS file-system description object
0229  * @k: key to initialize
0230  * @inum: host inode number
0231  * @nm: extended attribute entry name and length
0232  */
0233 static inline void xent_key_init_flash(const struct ubifs_info *c, void *k,
0234                        ino_t inum, const struct fscrypt_name *nm)
0235 {
0236     union ubifs_key *key = k;
0237     uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
0238 
0239     ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
0240     key->j32[0] = cpu_to_le32(inum);
0241     key->j32[1] = cpu_to_le32(hash |
0242                   (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS));
0243     memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
0244 }
0245 
0246 /**
0247  * lowest_xent_key - get the lowest possible extended attribute entry key.
0248  * @c: UBIFS file-system description object
0249  * @key: where to store the lowest key
0250  * @inum: host inode number
0251  */
0252 static inline void lowest_xent_key(const struct ubifs_info *c,
0253                    union ubifs_key *key, ino_t inum)
0254 {
0255     key->u32[0] = inum;
0256     key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
0257 }
0258 
0259 /**
0260  * data_key_init - initialize data key.
0261  * @c: UBIFS file-system description object
0262  * @key: key to initialize
0263  * @inum: inode number
0264  * @block: block number
0265  */
0266 static inline void data_key_init(const struct ubifs_info *c,
0267                  union ubifs_key *key, ino_t inum,
0268                  unsigned int block)
0269 {
0270     ubifs_assert(c, !(block & ~UBIFS_S_KEY_BLOCK_MASK));
0271     key->u32[0] = inum;
0272     key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
0273 }
0274 
0275 /**
0276  * highest_data_key - get the highest possible data key for an inode.
0277  * @c: UBIFS file-system description object
0278  * @key: key to initialize
0279  * @inum: inode number
0280  */
0281 static inline void highest_data_key(const struct ubifs_info *c,
0282                    union ubifs_key *key, ino_t inum)
0283 {
0284     data_key_init(c, key, inum, UBIFS_S_KEY_BLOCK_MASK);
0285 }
0286 
0287 /**
0288  * trun_key_init - initialize truncation node key.
0289  * @c: UBIFS file-system description object
0290  * @key: key to initialize
0291  * @inum: inode number
0292  *
0293  * Note, UBIFS does not have truncation keys on the media and this function is
0294  * only used for purposes of replay.
0295  */
0296 static inline void trun_key_init(const struct ubifs_info *c,
0297                  union ubifs_key *key, ino_t inum)
0298 {
0299     key->u32[0] = inum;
0300     key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
0301 }
0302 
0303 /**
0304  * invalid_key_init - initialize invalid node key.
0305  * @c: UBIFS file-system description object
0306  * @key: key to initialize
0307  *
0308  * This is a helper function which marks a @key object as invalid.
0309  */
0310 static inline void invalid_key_init(const struct ubifs_info *c,
0311                     union ubifs_key *key)
0312 {
0313     key->u32[0] = 0xDEADBEAF;
0314     key->u32[1] = UBIFS_INVALID_KEY;
0315 }
0316 
0317 /**
0318  * key_type - get key type.
0319  * @c: UBIFS file-system description object
0320  * @key: key to get type of
0321  */
0322 static inline int key_type(const struct ubifs_info *c,
0323                const union ubifs_key *key)
0324 {
0325     return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
0326 }
0327 
0328 /**
0329  * key_type_flash - get type of a on-flash formatted key.
0330  * @c: UBIFS file-system description object
0331  * @k: key to get type of
0332  */
0333 static inline int key_type_flash(const struct ubifs_info *c, const void *k)
0334 {
0335     const union ubifs_key *key = k;
0336 
0337     return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
0338 }
0339 
0340 /**
0341  * key_inum - fetch inode number from key.
0342  * @c: UBIFS file-system description object
0343  * @k: key to fetch inode number from
0344  */
0345 static inline ino_t key_inum(const struct ubifs_info *c, const void *k)
0346 {
0347     const union ubifs_key *key = k;
0348 
0349     return key->u32[0];
0350 }
0351 
0352 /**
0353  * key_inum_flash - fetch inode number from an on-flash formatted key.
0354  * @c: UBIFS file-system description object
0355  * @k: key to fetch inode number from
0356  */
0357 static inline ino_t key_inum_flash(const struct ubifs_info *c, const void *k)
0358 {
0359     const union ubifs_key *key = k;
0360 
0361     return le32_to_cpu(key->j32[0]);
0362 }
0363 
0364 /**
0365  * key_hash - get directory entry hash.
0366  * @c: UBIFS file-system description object
0367  * @key: the key to get hash from
0368  */
0369 static inline uint32_t key_hash(const struct ubifs_info *c,
0370                 const union ubifs_key *key)
0371 {
0372     return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
0373 }
0374 
0375 /**
0376  * key_hash_flash - get directory entry hash from an on-flash formatted key.
0377  * @c: UBIFS file-system description object
0378  * @k: the key to get hash from
0379  */
0380 static inline uint32_t key_hash_flash(const struct ubifs_info *c, const void *k)
0381 {
0382     const union ubifs_key *key = k;
0383 
0384     return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
0385 }
0386 
0387 /**
0388  * key_block - get data block number.
0389  * @c: UBIFS file-system description object
0390  * @key: the key to get the block number from
0391  */
0392 static inline unsigned int key_block(const struct ubifs_info *c,
0393                      const union ubifs_key *key)
0394 {
0395     return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
0396 }
0397 
0398 /**
0399  * key_block_flash - get data block number from an on-flash formatted key.
0400  * @c: UBIFS file-system description object
0401  * @k: the key to get the block number from
0402  */
0403 static inline unsigned int key_block_flash(const struct ubifs_info *c,
0404                        const void *k)
0405 {
0406     const union ubifs_key *key = k;
0407 
0408     return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK;
0409 }
0410 
0411 /**
0412  * key_read - transform a key to in-memory format.
0413  * @c: UBIFS file-system description object
0414  * @from: the key to transform
0415  * @to: the key to store the result
0416  */
0417 static inline void key_read(const struct ubifs_info *c, const void *from,
0418                 union ubifs_key *to)
0419 {
0420     const union ubifs_key *f = from;
0421 
0422     to->u32[0] = le32_to_cpu(f->j32[0]);
0423     to->u32[1] = le32_to_cpu(f->j32[1]);
0424 }
0425 
0426 /**
0427  * key_write - transform a key from in-memory format.
0428  * @c: UBIFS file-system description object
0429  * @from: the key to transform
0430  * @to: the key to store the result
0431  */
0432 static inline void key_write(const struct ubifs_info *c,
0433                  const union ubifs_key *from, void *to)
0434 {
0435     union ubifs_key *t = to;
0436 
0437     t->j32[0] = cpu_to_le32(from->u32[0]);
0438     t->j32[1] = cpu_to_le32(from->u32[1]);
0439     memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
0440 }
0441 
0442 /**
0443  * key_write_idx - transform a key from in-memory format for the index.
0444  * @c: UBIFS file-system description object
0445  * @from: the key to transform
0446  * @to: the key to store the result
0447  */
0448 static inline void key_write_idx(const struct ubifs_info *c,
0449                  const union ubifs_key *from, void *to)
0450 {
0451     union ubifs_key *t = to;
0452 
0453     t->j32[0] = cpu_to_le32(from->u32[0]);
0454     t->j32[1] = cpu_to_le32(from->u32[1]);
0455 }
0456 
0457 /**
0458  * key_copy - copy a key.
0459  * @c: UBIFS file-system description object
0460  * @from: the key to copy from
0461  * @to: the key to copy to
0462  */
0463 static inline void key_copy(const struct ubifs_info *c,
0464                 const union ubifs_key *from, union ubifs_key *to)
0465 {
0466     to->u64[0] = from->u64[0];
0467 }
0468 
0469 /**
0470  * keys_cmp - compare keys.
0471  * @c: UBIFS file-system description object
0472  * @key1: the first key to compare
0473  * @key2: the second key to compare
0474  *
0475  * This function compares 2 keys and returns %-1 if @key1 is less than
0476  * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
0477  */
0478 static inline int keys_cmp(const struct ubifs_info *c,
0479                const union ubifs_key *key1,
0480                const union ubifs_key *key2)
0481 {
0482     if (key1->u32[0] < key2->u32[0])
0483         return -1;
0484     if (key1->u32[0] > key2->u32[0])
0485         return 1;
0486     if (key1->u32[1] < key2->u32[1])
0487         return -1;
0488     if (key1->u32[1] > key2->u32[1])
0489         return 1;
0490 
0491     return 0;
0492 }
0493 
0494 /**
0495  * keys_eq - determine if keys are equivalent.
0496  * @c: UBIFS file-system description object
0497  * @key1: the first key to compare
0498  * @key2: the second key to compare
0499  *
0500  * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
0501  * %0 if not.
0502  */
0503 static inline int keys_eq(const struct ubifs_info *c,
0504               const union ubifs_key *key1,
0505               const union ubifs_key *key2)
0506 {
0507     if (key1->u32[0] != key2->u32[0])
0508         return 0;
0509     if (key1->u32[1] != key2->u32[1])
0510         return 0;
0511     return 1;
0512 }
0513 
0514 /**
0515  * is_hash_key - is a key vulnerable to hash collisions.
0516  * @c: UBIFS file-system description object
0517  * @key: key
0518  *
0519  * This function returns %1 if @key is a hashed key or %0 otherwise.
0520  */
0521 static inline int is_hash_key(const struct ubifs_info *c,
0522                   const union ubifs_key *key)
0523 {
0524     int type = key_type(c, key);
0525 
0526     return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
0527 }
0528 
0529 /**
0530  * key_max_inode_size - get maximum file size allowed by current key format.
0531  * @c: UBIFS file-system description object
0532  */
0533 static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
0534 {
0535     switch (c->key_fmt) {
0536     case UBIFS_SIMPLE_KEY_FMT:
0537         return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
0538     default:
0539         return 0;
0540     }
0541 }
0542 
0543 #endif /* !__UBIFS_KEY_H__ */
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!