fs/ubifs/key.h

   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         hash &= UBIFS_S_KEY_HASH_MASK;
  45         if (unlikely(hash <= 2))
  46                 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 static inline uint32_t key_r5_hash(const char *s, int len)
  56 {
  57         uint32_t a = 0;
  58         const signed char *str = (const signed char *)s;
  59
  60         while (len--) {
  61                 a += *str << 4;
  62                 a += *str >> 4;
  63                 a *= 11;
  64                 str++;
  65         }
  66
  67         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 static inline uint32_t key_test_hash(const char *str, int len)
  76 {
  77         uint32_t a = 0;
  78
  79         len = min_t(uint32_t, len, 4);
  80         memcpy(&a, str, len);
  81         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(const struct ubifs_info *c,
  91                                 union ubifs_key *key, ino_t inum)
  92 {
  93         key->u32[0] = inum;
  94         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(const struct ubifs_info *c, void *k,
 104                                       ino_t inum)
 105 {
 106         union ubifs_key *key = k;
 107
 108         key->j32[0] = cpu_to_le32(inum);
 109         key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
 110         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(const struct ubifs_info *c,
 120                                 union ubifs_key *key, ino_t inum)
 121 {
 122         key->u32[0] = inum;
 123         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(const struct ubifs_info *c,
 133                                 union ubifs_key *key, ino_t inum)
 134 {
 135         key->u32[0] = inum;
 136         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 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         uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
 151
 152         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
 153         ubifs_assert(c, !nm->hash && !nm->minor_hash);
 154         key->u32[0] = inum;
 155         key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
 156 }
 157
 158 /**
 159  * dent_key_init_hash - initialize directory entry key without re-calculating
 160  *                      hash function.
 161  * @c: UBIFS file-system description object
 162  * @key: key to initialize
 163  * @inum: parent inode number
 164  * @hash: direntry name hash
 165  */
 166 static inline void dent_key_init_hash(const struct ubifs_info *c,
 167                                       union ubifs_key *key, ino_t inum,
 168                                       uint32_t hash)
 169 {
 170         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
 171         key->u32[0] = inum;
 172         key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
 173 }
 174
 175 /**
 176  * dent_key_init_flash - initialize on-flash directory entry key.
 177  * @c: UBIFS file-system description object
 178  * @k: key to initialize
 179  * @inum: parent inode number
 180  * @nm: direntry name and length
 181  */
 182 static inline void dent_key_init_flash(const struct ubifs_info *c, void *k,
 183                                        ino_t inum,
 184                                        const struct fscrypt_name *nm)
 185 {
 186         union ubifs_key *key = k;
 187         uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
 188
 189         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
 190         key->j32[0] = cpu_to_le32(inum);
 191         key->j32[1] = cpu_to_le32(hash |
 192                                   (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS));
 193         memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 194 }
 195
 196 /**
 197  * lowest_dent_key - get the lowest possible directory entry key.
 198  * @c: UBIFS file-system description object
 199  * @key: where to store the lowest key
 200  * @inum: parent inode number
 201  */
 202 static inline void lowest_dent_key(const struct ubifs_info *c,
 203                                    union ubifs_key *key, ino_t inum)
 204 {
 205         key->u32[0] = inum;
 206         key->u32[1] = UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS;
 207 }
 208
 209 /**
 210  * xent_key_init - initialize extended attribute entry key.
 211  * @c: UBIFS file-system description object
 212  * @key: key to initialize
 213  * @inum: host inode number
 214  * @nm: extended attribute entry name and length
 215  */
 216 static inline void xent_key_init(const struct ubifs_info *c,
 217                                  union ubifs_key *key, ino_t inum,
 218                                  const struct fscrypt_name *nm)
 219 {
 220         uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
 221
 222         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
 223         key->u32[0] = inum;
 224         key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
 225 }
 226
 227 /**
 228  * xent_key_init_flash - initialize on-flash extended attribute entry key.
 229  * @c: UBIFS file-system description object
 230  * @k: key to initialize
 231  * @inum: host inode number
 232  * @nm: extended attribute entry name and length
 233  */
 234 static inline void xent_key_init_flash(const struct ubifs_info *c, void *k,
 235                                        ino_t inum, const struct fscrypt_name *nm)
 236 {
 237         union ubifs_key *key = k;
 238         uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
 239
 240         ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
 241         key->j32[0] = cpu_to_le32(inum);
 242         key->j32[1] = cpu_to_le32(hash |
 243                                   (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS));
 244         memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 245 }
 246
 247 /**
 248  * lowest_xent_key - get the lowest possible extended attribute entry key.
 249  * @c: UBIFS file-system description object
 250  * @key: where to store the lowest key
 251  * @inum: host inode number
 252  */
 253 static inline void lowest_xent_key(const struct ubifs_info *c,
 254                                    union ubifs_key *key, ino_t inum)
 255 {
 256         key->u32[0] = inum;
 257         key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
 258 }
 259
 260 /**
 261  * data_key_init - initialize data key.
 262  * @c: UBIFS file-system description object
 263  * @key: key to initialize
 264  * @inum: inode number
 265  * @block: block number
 266  */
 267 static inline void data_key_init(const struct ubifs_info *c,
 268                                  union ubifs_key *key, ino_t inum,
 269                                  unsigned int block)
 270 {
 271         ubifs_assert(c, !(block & ~UBIFS_S_KEY_BLOCK_MASK));
 272         key->u32[0] = inum;
 273         key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
 274 }
 275
 276 /**
 277  * highest_data_key - get the highest possible data key for an inode.
 278  * @c: UBIFS file-system description object
 279  * @key: key to initialize
 280  * @inum: inode number
 281  */
 282 static inline void highest_data_key(const struct ubifs_info *c,
 283                                    union ubifs_key *key, ino_t inum)
 284 {
 285         data_key_init(c, key, inum, UBIFS_S_KEY_BLOCK_MASK);
 286 }
 287
 288 /**
 289  * trun_key_init - initialize truncation node key.
 290  * @c: UBIFS file-system description object
 291  * @key: key to initialize
 292  * @inum: inode number
 293  *
 294  * Note, UBIFS does not have truncation keys on the media and this function is
 295  * only used for purposes of replay.
 296  */
 297 static inline void trun_key_init(const struct ubifs_info *c,
 298                                  union ubifs_key *key, ino_t inum)
 299 {
 300         key->u32[0] = inum;
 301         key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
 302 }
 303
 304 /**
 305  * invalid_key_init - initialize invalid node key.
 306  * @c: UBIFS file-system description object
 307  * @key: key to initialize
 308  *
 309  * This is a helper function which marks a @key object as invalid.
 310  */
 311 static inline void invalid_key_init(const struct ubifs_info *c,
 312                                     union ubifs_key *key)
 313 {
 314         key->u32[0] = 0xDEADBEAF;
 315         key->u32[1] = UBIFS_INVALID_KEY;
 316 }
 317
 318 /**
 319  * key_type - get key type.
 320  * @c: UBIFS file-system description object
 321  * @key: key to get type of
 322  */
 323 static inline int key_type(const struct ubifs_info *c,
 324                            const union ubifs_key *key)
 325 {
 326         return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
 327 }
 328
 329 /**
 330  * key_type_flash - get type of a on-flash formatted key.
 331  * @c: UBIFS file-system description object
 332  * @k: key to get type of
 333  */
 334 static inline int key_type_flash(const struct ubifs_info *c, const void *k)
 335 {
 336         const union ubifs_key *key = k;
 337
 338         return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
 339 }
 340
 341 /**
 342  * key_inum - fetch inode number from key.
 343  * @c: UBIFS file-system description object
 344  * @k: key to fetch inode number from
 345  */
 346 static inline ino_t key_inum(const struct ubifs_info *c, const void *k)
 347 {
 348         const union ubifs_key *key = k;
 349
 350         return key->u32[0];
 351 }
 352
 353 /**
 354  * key_inum_flash - fetch inode number from an on-flash formatted key.
 355  * @c: UBIFS file-system description object
 356  * @k: key to fetch inode number from
 357  */
 358 static inline ino_t key_inum_flash(const struct ubifs_info *c, const void *k)
 359 {
 360         const union ubifs_key *key = k;
 361
 362         return le32_to_cpu(key->j32[0]);
 363 }
 364
 365 /**
 366  * key_hash - get directory entry hash.
 367  * @c: UBIFS file-system description object
 368  * @key: the key to get hash from
 369  */
 370 static inline uint32_t key_hash(const struct ubifs_info *c,
 371                                 const union ubifs_key *key)
 372 {
 373         return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
 374 }
 375
 376 /**
 377  * key_hash_flash - get directory entry hash from an on-flash formatted key.
 378  * @c: UBIFS file-system description object
 379  * @k: the key to get hash from
 380  */
 381 static inline uint32_t key_hash_flash(const struct ubifs_info *c, const void *k)
 382 {
 383         const union ubifs_key *key = k;
 384
 385         return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
 386 }
 387
 388 /**
 389  * key_block - get data block number.
 390  * @c: UBIFS file-system description object
 391  * @key: the key to get the block number from
 392  */
 393 static inline unsigned int key_block(const struct ubifs_info *c,
 394                                      const union ubifs_key *key)
 395 {
 396         return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
 397 }
 398
 399 /**
 400  * key_block_flash - get data block number from an on-flash formatted key.
 401  * @c: UBIFS file-system description object
 402  * @k: the key to get the block number from
 403  */
 404 static inline unsigned int key_block_flash(const struct ubifs_info *c,
 405                                            const void *k)
 406 {
 407         const union ubifs_key *key = k;
 408
 409         return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK;
 410 }
 411
 412 /**
 413  * key_read - transform a key to in-memory format.
 414  * @c: UBIFS file-system description object
 415  * @from: the key to transform
 416  * @to: the key to store the result
 417  */
 418 static inline void key_read(const struct ubifs_info *c, const void *from,
 419                             union ubifs_key *to)
 420 {
 421         const union ubifs_key *f = from;
 422
 423         to->u32[0] = le32_to_cpu(f->j32[0]);
 424         to->u32[1] = le32_to_cpu(f->j32[1]);
 425 }
 426
 427 /**
 428  * key_write - transform a key from in-memory format.
 429  * @c: UBIFS file-system description object
 430  * @from: the key to transform
 431  * @to: the key to store the result
 432  */
 433 static inline void key_write(const struct ubifs_info *c,
 434                              const union ubifs_key *from, void *to)
 435 {
 436         union ubifs_key *t = to;
 437
 438         t->j32[0] = cpu_to_le32(from->u32[0]);
 439         t->j32[1] = cpu_to_le32(from->u32[1]);
 440         memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 441 }
 442
 443 /**
 444  * key_write_idx - transform a key from in-memory format for the index.
 445  * @c: UBIFS file-system description object
 446  * @from: the key to transform
 447  * @to: the key to store the result
 448  */
 449 static inline void key_write_idx(const struct ubifs_info *c,
 450                                  const union ubifs_key *from, void *to)
 451 {
 452         union ubifs_key *t = to;
 453
 454         t->j32[0] = cpu_to_le32(from->u32[0]);
 455         t->j32[1] = cpu_to_le32(from->u32[1]);
 456 }
 457
 458 /**
 459  * key_copy - copy a key.
 460  * @c: UBIFS file-system description object
 461  * @from: the key to copy from
 462  * @to: the key to copy to
 463  */
 464 static inline void key_copy(const struct ubifs_info *c,
 465                             const union ubifs_key *from, union ubifs_key *to)
 466 {
 467         to->u64[0] = from->u64[0];
 468 }
 469
 470 /**
 471  * keys_cmp - compare keys.
 472  * @c: UBIFS file-system description object
 473  * @key1: the first key to compare
 474  * @key2: the second key to compare
 475  *
 476  * This function compares 2 keys and returns %-1 if @key1 is less than
 477  * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
 478  */
 479 static inline int keys_cmp(const struct ubifs_info *c,
 480                            const union ubifs_key *key1,
 481                            const union ubifs_key *key2)
 482 {
 483         if (key1->u32[0] < key2->u32[0])
 484                 return -1;
 485         if (key1->u32[0] > key2->u32[0])
 486                 return 1;
 487         if (key1->u32[1] < key2->u32[1])
 488                 return -1;
 489         if (key1->u32[1] > key2->u32[1])
 490                 return 1;
 491
 492         return 0;
 493 }
 494
 495 /**
 496  * keys_eq - determine if keys are equivalent.
 497  * @c: UBIFS file-system description object
 498  * @key1: the first key to compare
 499  * @key2: the second key to compare
 500  *
 501  * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
 502  * %0 if not.
 503  */
 504 static inline int keys_eq(const struct ubifs_info *c,
 505                           const union ubifs_key *key1,
 506                           const union ubifs_key *key2)
 507 {
 508         if (key1->u32[0] != key2->u32[0])
 509                 return 0;
 510         if (key1->u32[1] != key2->u32[1])
 511                 return 0;
 512         return 1;
 513 }
 514
 515 /**
 516  * is_hash_key - is a key vulnerable to hash collisions.
 517  * @c: UBIFS file-system description object
 518  * @key: key
 519  *
 520  * This function returns %1 if @key is a hashed key or %0 otherwise.
 521  */
 522 static inline int is_hash_key(const struct ubifs_info *c,
 523                               const union ubifs_key *key)
 524 {
 525         int type = key_type(c, key);
 526
 527         return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
 528 }
 529
 530 /**
 531  * key_max_inode_size - get maximum file size allowed by current key format.
 532  * @c: UBIFS file-system description object
 533  */
 534 static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
 535 {
 536         switch (c->key_fmt) {
 537         case UBIFS_SIMPLE_KEY_FMT:
 538                 return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
 539         default:
 540                 return 0;
 541         }
 542 }
 543
 544 #endif /* !__UBIFS_KEY_H__ */