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