fs/ubifs/key.h

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