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