Commit | Line | Data |
---|---|---|
2b27bdcc | 1 | /* SPDX-License-Identifier: GPL-2.0-only */ |
1e51764a AB |
2 | /* |
3 | * This file is part of UBIFS. | |
4 | * | |
5 | * Copyright (C) 2006-2008 Nokia Corporation. | |
6 | * | |
1e51764a AB |
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 | ||
170eb55f DY |
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 | ||
1e51764a AB |
31 | #ifndef __UBIFS_KEY_H__ |
32 | #define __UBIFS_KEY_H__ | |
33 | ||
5dd7cbc0 KM |
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 | ||
1e51764a AB |
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 | ||
b9bc8c7b | 60 | while (len--) { |
1e51764a AB |
61 | a += *str << 4; |
62 | a += *str >> 4; | |
63 | a *= 11; | |
64 | str++; | |
65 | } | |
66 | ||
5dd7cbc0 | 67 | return key_mask_hash(a); |
1e51764a AB |
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); | |
5dd7cbc0 | 81 | return key_mask_hash(a); |
1e51764a AB |
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 | |
f4f61d2c | 144 | * @nm: direntry name and length. Not a string when encrypted! |
1e51764a AB |
145 | */ |
146 | static inline void dent_key_init(const struct ubifs_info *c, | |
147 | union ubifs_key *key, ino_t inum, | |
f4f61d2c | 148 | const struct fscrypt_name *nm) |
1e51764a | 149 | { |
f4f61d2c | 150 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 151 | |
6eb61d58 | 152 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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 | { | |
6eb61d58 | 169 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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, | |
f4f61d2c RW |
182 | ino_t inum, |
183 | const struct fscrypt_name *nm) | |
1e51764a AB |
184 | { |
185 | union ubifs_key *key = k; | |
f4f61d2c | 186 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 187 | |
6eb61d58 | 188 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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, | |
f4f61d2c | 217 | const struct fscrypt_name *nm) |
1e51764a | 218 | { |
f4f61d2c | 219 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 220 | |
6eb61d58 | 221 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
222 | key->u32[0] = inum; |
223 | key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS); | |
224 | } | |
225 | ||
1e51764a AB |
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, | |
f4f61d2c | 234 | ino_t inum, const struct fscrypt_name *nm) |
1e51764a AB |
235 | { |
236 | union ubifs_key *key = k; | |
f4f61d2c | 237 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 238 | |
6eb61d58 | 239 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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 | { | |
6eb61d58 | 270 | ubifs_assert(c, !(block & ~UBIFS_S_KEY_BLOCK_MASK)); |
1e51764a AB |
271 | key->u32[0] = inum; |
272 | key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS); | |
273 | } | |
274 | ||
e3c3efc2 AB |
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 | ||
1e51764a AB |
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 | ||
ba2f48f7 AB |
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 | ||
1e51764a AB |
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 | ||
0ecb9529 | 337 | return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS; |
1e51764a AB |
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 | */ | |
cb4f952d AB |
369 | static inline uint32_t key_hash(const struct ubifs_info *c, |
370 | const union ubifs_key *key) | |
1e51764a AB |
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 | */ | |
cb4f952d | 380 | static inline uint32_t key_hash_flash(const struct ubifs_info *c, const void *k) |
1e51764a AB |
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 | ||
0ecb9529 | 408 | return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK; |
1e51764a AB |
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 | |
4793e7c5 | 476 | * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2. |
1e51764a AB |
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 | ||
4793e7c5 AH |
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 | ||
1e51764a AB |
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 | } | |
e3c3efc2 | 542 | |
1e51764a | 543 | #endif /* !__UBIFS_KEY_H__ */ |