]>
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 RW |
152 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
153 | ubifs_assert(c, !nm->hash && !nm->minor_hash); | |
1e51764a AB |
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 | { | |
6eb61d58 | 170 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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, | |
f4f61d2c RW |
183 | ino_t inum, |
184 | const struct fscrypt_name *nm) | |
1e51764a AB |
185 | { |
186 | union ubifs_key *key = k; | |
f4f61d2c | 187 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 188 | |
6eb61d58 | 189 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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, | |
f4f61d2c | 218 | const struct fscrypt_name *nm) |
1e51764a | 219 | { |
f4f61d2c | 220 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 221 | |
6eb61d58 | 222 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
223 | key->u32[0] = inum; |
224 | key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS); | |
225 | } | |
226 | ||
1e51764a AB |
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, | |
f4f61d2c | 235 | ino_t inum, const struct fscrypt_name *nm) |
1e51764a AB |
236 | { |
237 | union ubifs_key *key = k; | |
f4f61d2c | 238 | uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm)); |
1e51764a | 239 | |
6eb61d58 | 240 | ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK)); |
1e51764a AB |
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 | { | |
6eb61d58 | 271 | ubifs_assert(c, !(block & ~UBIFS_S_KEY_BLOCK_MASK)); |
1e51764a AB |
272 | key->u32[0] = inum; |
273 | key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS); | |
274 | } | |
275 | ||
e3c3efc2 AB |
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 | ||
1e51764a AB |
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 | ||
ba2f48f7 AB |
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 | ||
1e51764a AB |
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 | ||
0ecb9529 | 338 | return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS; |
1e51764a AB |
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 | */ | |
cb4f952d AB |
370 | static inline uint32_t key_hash(const struct ubifs_info *c, |
371 | const union ubifs_key *key) | |
1e51764a AB |
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 | */ | |
cb4f952d | 381 | static inline uint32_t key_hash_flash(const struct ubifs_info *c, const void *k) |
1e51764a AB |
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 | ||
0ecb9529 | 409 | return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK; |
1e51764a AB |
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 | |
4793e7c5 | 477 | * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2. |
1e51764a AB |
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 | ||
4793e7c5 AH |
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 | ||
1e51764a AB |
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 | } | |
e3c3efc2 | 543 | |
1e51764a | 544 | #endif /* !__UBIFS_KEY_H__ */ |