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