Line data Source code
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 125623 : hash &= UBIFS_S_KEY_HASH_MASK;
45 125623 : if (unlikely(hash <= 2))
46 0 : 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 125623 : static inline uint32_t key_r5_hash(const char *s, int len)
56 : {
57 125623 : uint32_t a = 0;
58 125623 : const signed char *str = (const signed char *)s;
59 :
60 1221462 : while (len--) {
61 970216 : a += *str << 4;
62 970216 : a += *str >> 4;
63 970216 : a *= 11;
64 970216 : str++;
65 : }
66 :
67 125623 : 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 0 : static inline uint32_t key_test_hash(const char *str, int len)
76 : {
77 0 : uint32_t a = 0;
78 :
79 0 : len = min_t(uint32_t, len, 4);
80 0 : memcpy(&a, str, len);
81 0 : 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(__unused const struct ubifs_info *c,
91 : union ubifs_key *key, ino_t inum)
92 : {
93 201606 : key->u32[0] = inum;
94 201606 : 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(__unused const struct ubifs_info *c,
104 : void *k, ino_t inum)
105 : {
106 470 : union ubifs_key *key = k;
107 :
108 470 : key->j32[0] = cpu_to_le32(inum);
109 470 : key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
110 470 : 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(__unused const struct ubifs_info *c,
120 : union ubifs_key *key, ino_t inum)
121 : {
122 5488 : key->u32[0] = inum;
123 5488 : 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(__unused const struct ubifs_info *c,
133 : union ubifs_key *key, ino_t inum)
134 : {
135 5488 : key->u32[0] = inum;
136 5488 : 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 92663 : 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 92663 : uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
151 :
152 92663 : ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
153 92663 : key->u32[0] = inum;
154 92663 : key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
155 92663 : }
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 : * xent_key_init - initialize extended attribute entry key.
176 : * @c: UBIFS file-system description object
177 : * @key: key to initialize
178 : * @inum: host inode number
179 : * @nm: extended attribute entry name and length
180 : */
181 32960 : static inline void xent_key_init(const struct ubifs_info *c,
182 : union ubifs_key *key, ino_t inum,
183 : const struct fscrypt_name *nm)
184 : {
185 32960 : uint32_t hash = c->key_hash(fname_name(nm), fname_len(nm));
186 :
187 32960 : ubifs_assert(c, !(hash & ~UBIFS_S_KEY_HASH_MASK));
188 32960 : key->u32[0] = inum;
189 32960 : key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
190 32960 : }
191 :
192 : /**
193 : * lowest_xent_key - get the lowest possible extended attribute entry key.
194 : * @c: UBIFS file-system description object
195 : * @key: where to store the lowest key
196 : * @inum: host inode number
197 : */
198 : static inline void lowest_xent_key(__unused const struct ubifs_info *c,
199 : union ubifs_key *key, ino_t inum)
200 : {
201 4747 : key->u32[0] = inum;
202 4747 : key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
203 : }
204 :
205 : /**
206 : * data_key_init - initialize data key.
207 : * @c: UBIFS file-system description object
208 : * @key: key to initialize
209 : * @inum: inode number
210 : * @block: block number
211 : */
212 : static inline void data_key_init(const struct ubifs_info *c,
213 : union ubifs_key *key, ino_t inum,
214 : unsigned int block)
215 : {
216 1192518 : ubifs_assert(c, !(block & ~UBIFS_S_KEY_BLOCK_MASK));
217 1192518 : key->u32[0] = inum;
218 1192518 : key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
219 : }
220 :
221 : /**
222 : * highest_data_key - get the highest possible data key for an inode.
223 : * @c: UBIFS file-system description object
224 : * @key: key to initialize
225 : * @inum: inode number
226 : */
227 : static inline void highest_data_key(const struct ubifs_info *c,
228 : union ubifs_key *key, ino_t inum)
229 : {
230 : data_key_init(c, key, inum, UBIFS_S_KEY_BLOCK_MASK);
231 : }
232 :
233 : /**
234 : * trun_key_init - initialize truncation node key.
235 : * @c: UBIFS file-system description object
236 : * @key: key to initialize
237 : * @inum: inode number
238 : *
239 : * Note, UBIFS does not have truncation keys on the media and this function is
240 : * only used for purposes of replay.
241 : */
242 : static inline void trun_key_init(__unused const struct ubifs_info *c,
243 : union ubifs_key *key, ino_t inum)
244 : {
245 331282 : key->u32[0] = inum;
246 331282 : key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
247 : }
248 :
249 : /**
250 : * invalid_key_init - initialize invalid node key.
251 : * @c: UBIFS file-system description object
252 : * @key: key to initialize
253 : *
254 : * This is a helper function which marks a @key object as invalid.
255 : */
256 : static inline void invalid_key_init(__unused const struct ubifs_info *c,
257 : union ubifs_key *key)
258 : {
259 5049082841 : key->u32[0] = 0xDEADBEAF;
260 5049082841 : key->u32[1] = UBIFS_INVALID_KEY;
261 : }
262 :
263 : /**
264 : * key_type - get key type.
265 : * @c: UBIFS file-system description object
266 : * @key: key to get type of
267 : */
268 : static inline int key_type(__unused const struct ubifs_info *c,
269 : const union ubifs_key *key)
270 : {
271 26324366815 : return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
272 : }
273 :
274 : /**
275 : * key_type_flash - get type of a on-flash formatted key.
276 : * @c: UBIFS file-system description object
277 : * @k: key to get type of
278 : */
279 : static inline int key_type_flash(__unused const struct ubifs_info *c,
280 : const void *k)
281 : {
282 240132460 : const union ubifs_key *key = k;
283 :
284 240132460 : return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
285 : }
286 :
287 : /**
288 : * key_inum - fetch inode number from key.
289 : * @c: UBIFS file-system description object
290 : * @k: key to fetch inode number from
291 : */
292 : static inline ino_t key_inum(__unused const struct ubifs_info *c, const void *k)
293 : {
294 5523452996 : const union ubifs_key *key = k;
295 :
296 5523422856 : return key->u32[0];
297 : }
298 :
299 : /**
300 : * key_inum_flash - fetch inode number from an on-flash formatted key.
301 : * @c: UBIFS file-system description object
302 : * @k: key to fetch inode number from
303 : */
304 : static inline ino_t key_inum_flash(__unused const struct ubifs_info *c,
305 : const void *k)
306 : {
307 : const union ubifs_key *key = k;
308 :
309 : return le32_to_cpu(key->j32[0]);
310 : }
311 :
312 : /**
313 : * key_hash - get directory entry hash.
314 : * @c: UBIFS file-system description object
315 : * @key: the key to get hash from
316 : */
317 : static inline uint32_t key_hash(__unused const struct ubifs_info *c,
318 : const union ubifs_key *key)
319 : {
320 155254 : return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
321 : }
322 :
323 : /**
324 : * key_hash_flash - get directory entry hash from an on-flash formatted key.
325 : * @c: UBIFS file-system description object
326 : * @k: the key to get hash from
327 : */
328 : static inline uint32_t key_hash_flash(__unused const struct ubifs_info *c,
329 : const void *k)
330 : {
331 : const union ubifs_key *key = k;
332 :
333 : return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
334 : }
335 :
336 : /**
337 : * key_block - get data block number.
338 : * @c: UBIFS file-system description object
339 : * @key: the key to get the block number from
340 : */
341 : static inline unsigned int key_block(__unused const struct ubifs_info *c,
342 : const union ubifs_key *key)
343 : {
344 2209251763 : return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
345 : }
346 :
347 : /**
348 : * key_block_flash - get data block number from an on-flash formatted key.
349 : * @c: UBIFS file-system description object
350 : * @k: the key to get the block number from
351 : */
352 : static inline unsigned int key_block_flash(__unused const struct ubifs_info *c,
353 : const void *k)
354 : {
355 : const union ubifs_key *key = k;
356 :
357 : return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK;
358 : }
359 :
360 : /**
361 : * key_read - transform a key to in-memory format.
362 : * @c: UBIFS file-system description object
363 : * @from: the key to transform
364 : * @to: the key to store the result
365 : */
366 : static inline void key_read(__unused const struct ubifs_info *c,
367 : const void *from, union ubifs_key *to)
368 : {
369 16116874498 : const union ubifs_key *f = from;
370 :
371 16116874498 : to->u32[0] = le32_to_cpu(f->j32[0]);
372 16116874498 : to->u32[1] = le32_to_cpu(f->j32[1]);
373 : }
374 :
375 : /**
376 : * key_write - transform a key from in-memory format.
377 : * @c: UBIFS file-system description object
378 : * @from: the key to transform
379 : * @to: the key to store the result
380 : */
381 : static inline void key_write(__unused const struct ubifs_info *c,
382 : const union ubifs_key *from, void *to)
383 : {
384 1429352 : union ubifs_key *t = to;
385 :
386 1429352 : t->j32[0] = cpu_to_le32(from->u32[0]);
387 1429352 : t->j32[1] = cpu_to_le32(from->u32[1]);
388 1429352 : memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
389 : }
390 :
391 : /**
392 : * key_write_idx - transform a key from in-memory format for the index.
393 : * @c: UBIFS file-system description object
394 : * @from: the key to transform
395 : * @to: the key to store the result
396 : */
397 : static inline void key_write_idx(__unused const struct ubifs_info *c,
398 : const union ubifs_key *from, void *to)
399 : {
400 123090022 : union ubifs_key *t = to;
401 :
402 123090022 : t->j32[0] = cpu_to_le32(from->u32[0]);
403 123090022 : t->j32[1] = cpu_to_le32(from->u32[1]);
404 : }
405 :
406 : /**
407 : * key_copy - copy a key.
408 : * @c: UBIFS file-system description object
409 : * @from: the key to copy from
410 : * @to: the key to copy to
411 : */
412 : static inline void key_copy(__unused const struct ubifs_info *c,
413 : const union ubifs_key *from, union ubifs_key *to)
414 : {
415 2902982423 : to->u64[0] = from->u64[0];
416 : }
417 :
418 : /**
419 : * keys_cmp - compare keys.
420 : * @c: UBIFS file-system description object
421 : * @key1: the first key to compare
422 : * @key2: the second key to compare
423 : *
424 : * This function compares 2 keys and returns %-1 if @key1 is less than
425 : * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
426 : */
427 : static inline int keys_cmp(__unused const struct ubifs_info *c,
428 : const union ubifs_key *key1,
429 : const union ubifs_key *key2)
430 : {
431 >25215*10^7 : if (key1->u32[0] < key2->u32[0])
432 : return -1;
433 >16736*10^7 : if (key1->u32[0] > key2->u32[0])
434 : return 1;
435 61156780271 : if (key1->u32[1] < key2->u32[1])
436 : return -1;
437 41037522593 : if (key1->u32[1] > key2->u32[1])
438 : return 1;
439 :
440 : return 0;
441 : }
442 :
443 : /**
444 : * keys_eq - determine if keys are equivalent.
445 : * @c: UBIFS file-system description object
446 : * @key1: the first key to compare
447 : * @key2: the second key to compare
448 : *
449 : * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
450 : * %0 if not.
451 : */
452 : static inline int keys_eq(__unused const struct ubifs_info *c,
453 : const union ubifs_key *key1,
454 : const union ubifs_key *key2)
455 : {
456 2491455525 : if (key1->u32[0] != key2->u32[0])
457 : return 0;
458 2491455525 : if (key1->u32[1] != key2->u32[1])
459 : return 0;
460 : return 1;
461 : }
462 :
463 : /**
464 : * is_hash_key - is a key vulnerable to hash collisions.
465 : * @c: UBIFS file-system description object
466 : * @key: key
467 : *
468 : * This function returns %1 if @key is a hashed key or %0 otherwise.
469 : */
470 : static inline int is_hash_key(const struct ubifs_info *c,
471 : const union ubifs_key *key)
472 : {
473 13010150648 : int type = key_type(c, key);
474 :
475 6505075324 : return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
476 : }
477 :
478 : /**
479 : * key_max_inode_size - get maximum file size allowed by current key format.
480 : * @c: UBIFS file-system description object
481 : */
482 : static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
483 : {
484 2340 : switch (c->key_fmt) {
485 : case UBIFS_SIMPLE_KEY_FMT:
486 : return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
487 0 : default:
488 : return 0;
489 : }
490 : }
491 :
492 : #endif /* !__UBIFS_KEY_H__ */
|