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__ */ 545