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(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(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 | |