fs/ubifs/key.h

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