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