]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/ubifs/key.h
2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * SPDX-License-Identifier: GPL-2.0+
8 * Authors: Artem Bityutskiy (Битюцкий Артём)
13 * This header contains various key-related definitions and helper function.
14 * UBIFS allows several key schemes, so we access key fields only via these
15 * helpers. At the moment only one key scheme is supported.
20 * Keys are 64-bits long. First 32-bits are inode number (parent inode number
21 * in case of direntry key). Next 3 bits are node type. The last 29 bits are
22 * 4KiB offset in case of inode node, and direntry hash in case of a direntry
23 * node. We use "r5" hash borrowed from reiserfs.
26 #ifndef __UBIFS_KEY_H__
27 #define __UBIFS_KEY_H__
30 * key_mask_hash - mask a valid hash value.
31 * @val: value to be masked
33 * We use hash values as offset in directories, so values %0 and %1 are
34 * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This
35 * function makes sure the reserved values are not used.
37 static inline uint32_t key_mask_hash(uint32_t hash
)
39 hash
&= UBIFS_S_KEY_HASH_MASK
;
40 if (unlikely(hash
<= 2))
46 * key_r5_hash - R5 hash function (borrowed from reiserfs).
50 static inline uint32_t key_r5_hash(const char *s
, int len
)
53 const signed char *str
= (const signed char *)s
;
62 return key_mask_hash(a
);
66 * key_test_hash - testing hash function.
70 static inline uint32_t key_test_hash(const char *str
, int len
)
74 len
= min_t(uint32_t, len
, 4);
76 return key_mask_hash(a
);
80 * ino_key_init - initialize inode key.
81 * @c: UBIFS file-system description object
82 * @key: key to initialize
85 static inline void ino_key_init(const struct ubifs_info
*c
,
86 union ubifs_key
*key
, ino_t inum
)
89 key
->u32
[1] = UBIFS_INO_KEY
<< UBIFS_S_KEY_BLOCK_BITS
;
93 * ino_key_init_flash - initialize on-flash inode key.
94 * @c: UBIFS file-system description object
95 * @k: key to initialize
98 static inline void ino_key_init_flash(const struct ubifs_info
*c
, void *k
,
101 union ubifs_key
*key
= k
;
103 key
->j32
[0] = cpu_to_le32(inum
);
104 key
->j32
[1] = cpu_to_le32(UBIFS_INO_KEY
<< UBIFS_S_KEY_BLOCK_BITS
);
105 memset(k
+ 8, 0, UBIFS_MAX_KEY_LEN
- 8);
109 * lowest_ino_key - get the lowest possible inode key.
110 * @c: UBIFS file-system description object
111 * @key: key to initialize
112 * @inum: inode number
114 static inline void lowest_ino_key(const struct ubifs_info
*c
,
115 union ubifs_key
*key
, ino_t inum
)
122 * highest_ino_key - get the highest possible inode key.
123 * @c: UBIFS file-system description object
124 * @key: key to initialize
125 * @inum: inode number
127 static inline void highest_ino_key(const struct ubifs_info
*c
,
128 union ubifs_key
*key
, ino_t inum
)
131 key
->u32
[1] = 0xffffffff;
135 * dent_key_init - initialize directory entry key.
136 * @c: UBIFS file-system description object
137 * @key: key to initialize
138 * @inum: parent inode number
139 * @nm: direntry name and length
141 static inline void dent_key_init(const struct ubifs_info
*c
,
142 union ubifs_key
*key
, ino_t inum
,
143 const struct qstr
*nm
)
145 uint32_t hash
= c
->key_hash(nm
->name
, nm
->len
);
147 ubifs_assert(!(hash
& ~UBIFS_S_KEY_HASH_MASK
));
149 key
->u32
[1] = hash
| (UBIFS_DENT_KEY
<< UBIFS_S_KEY_HASH_BITS
);
153 * dent_key_init_hash - initialize directory entry key without re-calculating
155 * @c: UBIFS file-system description object
156 * @key: key to initialize
157 * @inum: parent inode number
158 * @hash: direntry name hash
160 static inline void dent_key_init_hash(const struct ubifs_info
*c
,
161 union ubifs_key
*key
, ino_t inum
,
164 ubifs_assert(!(hash
& ~UBIFS_S_KEY_HASH_MASK
));
166 key
->u32
[1] = hash
| (UBIFS_DENT_KEY
<< UBIFS_S_KEY_HASH_BITS
);
170 * dent_key_init_flash - initialize on-flash directory entry key.
171 * @c: UBIFS file-system description object
172 * @k: key to initialize
173 * @inum: parent inode number
174 * @nm: direntry name and length
176 static inline void dent_key_init_flash(const struct ubifs_info
*c
, void *k
,
177 ino_t inum
, const struct qstr
*nm
)
179 union ubifs_key
*key
= k
;
180 uint32_t hash
= c
->key_hash(nm
->name
, nm
->len
);
182 ubifs_assert(!(hash
& ~UBIFS_S_KEY_HASH_MASK
));
183 key
->j32
[0] = cpu_to_le32(inum
);
184 key
->j32
[1] = cpu_to_le32(hash
|
185 (UBIFS_DENT_KEY
<< UBIFS_S_KEY_HASH_BITS
));
186 memset(k
+ 8, 0, UBIFS_MAX_KEY_LEN
- 8);
190 * lowest_dent_key - get the lowest possible directory entry key.
191 * @c: UBIFS file-system description object
192 * @key: where to store the lowest key
193 * @inum: parent inode number
195 static inline void lowest_dent_key(const struct ubifs_info
*c
,
196 union ubifs_key
*key
, ino_t inum
)
199 key
->u32
[1] = UBIFS_DENT_KEY
<< UBIFS_S_KEY_HASH_BITS
;
203 * xent_key_init - initialize extended attribute entry key.
204 * @c: UBIFS file-system description object
205 * @key: key to initialize
206 * @inum: host inode number
207 * @nm: extended attribute entry name and length
209 static inline void xent_key_init(const struct ubifs_info
*c
,
210 union ubifs_key
*key
, ino_t inum
,
211 const struct qstr
*nm
)
213 uint32_t hash
= c
->key_hash(nm
->name
, nm
->len
);
215 ubifs_assert(!(hash
& ~UBIFS_S_KEY_HASH_MASK
));
217 key
->u32
[1] = hash
| (UBIFS_XENT_KEY
<< UBIFS_S_KEY_HASH_BITS
);
221 * xent_key_init_flash - initialize on-flash extended attribute entry key.
222 * @c: UBIFS file-system description object
223 * @k: key to initialize
224 * @inum: host inode number
225 * @nm: extended attribute entry name and length
227 static inline void xent_key_init_flash(const struct ubifs_info
*c
, void *k
,
228 ino_t inum
, const struct qstr
*nm
)
230 union ubifs_key
*key
= k
;
231 uint32_t hash
= c
->key_hash(nm
->name
, nm
->len
);
233 ubifs_assert(!(hash
& ~UBIFS_S_KEY_HASH_MASK
));
234 key
->j32
[0] = cpu_to_le32(inum
);
235 key
->j32
[1] = cpu_to_le32(hash
|
236 (UBIFS_XENT_KEY
<< UBIFS_S_KEY_HASH_BITS
));
237 memset(k
+ 8, 0, UBIFS_MAX_KEY_LEN
- 8);
241 * lowest_xent_key - get the lowest possible extended attribute entry key.
242 * @c: UBIFS file-system description object
243 * @key: where to store the lowest key
244 * @inum: host inode number
246 static inline void lowest_xent_key(const struct ubifs_info
*c
,
247 union ubifs_key
*key
, ino_t inum
)
250 key
->u32
[1] = UBIFS_XENT_KEY
<< UBIFS_S_KEY_HASH_BITS
;
254 * data_key_init - initialize data key.
255 * @c: UBIFS file-system description object
256 * @key: key to initialize
257 * @inum: inode number
258 * @block: block number
260 static inline void data_key_init(const struct ubifs_info
*c
,
261 union ubifs_key
*key
, ino_t inum
,
264 ubifs_assert(!(block
& ~UBIFS_S_KEY_BLOCK_MASK
));
266 key
->u32
[1] = block
| (UBIFS_DATA_KEY
<< UBIFS_S_KEY_BLOCK_BITS
);
270 * highest_data_key - get the highest possible data key for an inode.
271 * @c: UBIFS file-system description object
272 * @key: key to initialize
273 * @inum: inode number
275 static inline void highest_data_key(const struct ubifs_info
*c
,
276 union ubifs_key
*key
, ino_t inum
)
278 data_key_init(c
, key
, inum
, UBIFS_S_KEY_BLOCK_MASK
);
282 * trun_key_init - initialize truncation node key.
283 * @c: UBIFS file-system description object
284 * @key: key to initialize
285 * @inum: inode number
287 * Note, UBIFS does not have truncation keys on the media and this function is
288 * only used for purposes of replay.
290 static inline void trun_key_init(const struct ubifs_info
*c
,
291 union ubifs_key
*key
, ino_t inum
)
294 key
->u32
[1] = UBIFS_TRUN_KEY
<< UBIFS_S_KEY_BLOCK_BITS
;
298 * invalid_key_init - initialize invalid node key.
299 * @c: UBIFS file-system description object
300 * @key: key to initialize
302 * This is a helper function which marks a @key object as invalid.
304 static inline void invalid_key_init(const struct ubifs_info
*c
,
305 union ubifs_key
*key
)
307 key
->u32
[0] = 0xDEADBEAF;
308 key
->u32
[1] = UBIFS_INVALID_KEY
;
312 * key_type - get key type.
313 * @c: UBIFS file-system description object
314 * @key: key to get type of
316 static inline int key_type(const struct ubifs_info
*c
,
317 const union ubifs_key
*key
)
319 return key
->u32
[1] >> UBIFS_S_KEY_BLOCK_BITS
;
323 * key_type_flash - get type of a on-flash formatted key.
324 * @c: UBIFS file-system description object
325 * @k: key to get type of
327 static inline int key_type_flash(const struct ubifs_info
*c
, const void *k
)
329 const union ubifs_key
*key
= k
;
331 return le32_to_cpu(key
->j32
[1]) >> UBIFS_S_KEY_BLOCK_BITS
;
335 * key_inum - fetch inode number from key.
336 * @c: UBIFS file-system description object
337 * @k: key to fetch inode number from
339 static inline ino_t
key_inum(const struct ubifs_info
*c
, const void *k
)
341 const union ubifs_key
*key
= k
;
347 * key_inum_flash - fetch inode number from an on-flash formatted key.
348 * @c: UBIFS file-system description object
349 * @k: key to fetch inode number from
351 static inline ino_t
key_inum_flash(const struct ubifs_info
*c
, const void *k
)
353 const union ubifs_key
*key
= k
;
355 return le32_to_cpu(key
->j32
[0]);
359 * key_hash - get directory entry hash.
360 * @c: UBIFS file-system description object
361 * @key: the key to get hash from
363 static inline uint32_t key_hash(const struct ubifs_info
*c
,
364 const union ubifs_key
*key
)
366 return key
->u32
[1] & UBIFS_S_KEY_HASH_MASK
;
370 * key_hash_flash - get directory entry hash from an on-flash formatted key.
371 * @c: UBIFS file-system description object
372 * @k: the key to get hash from
374 static inline uint32_t key_hash_flash(const struct ubifs_info
*c
, const void *k
)
376 const union ubifs_key
*key
= k
;
378 return le32_to_cpu(key
->j32
[1]) & UBIFS_S_KEY_HASH_MASK
;
382 * key_block - get data block number.
383 * @c: UBIFS file-system description object
384 * @key: the key to get the block number from
386 static inline unsigned int key_block(const struct ubifs_info
*c
,
387 const union ubifs_key
*key
)
389 return key
->u32
[1] & UBIFS_S_KEY_BLOCK_MASK
;
393 * key_block_flash - get data block number from an on-flash formatted key.
394 * @c: UBIFS file-system description object
395 * @k: the key to get the block number from
397 static inline unsigned int key_block_flash(const struct ubifs_info
*c
,
400 const union ubifs_key
*key
= k
;
402 return le32_to_cpu(key
->j32
[1]) & UBIFS_S_KEY_BLOCK_MASK
;
406 * key_read - transform a key to in-memory format.
407 * @c: UBIFS file-system description object
408 * @from: the key to transform
409 * @to: the key to store the result
411 static inline void key_read(const struct ubifs_info
*c
, const void *from
,
414 const union ubifs_key
*f
= from
;
416 to
->u32
[0] = le32_to_cpu(f
->j32
[0]);
417 to
->u32
[1] = le32_to_cpu(f
->j32
[1]);
421 * key_write - transform a key from in-memory format.
422 * @c: UBIFS file-system description object
423 * @from: the key to transform
424 * @to: the key to store the result
426 static inline void key_write(const struct ubifs_info
*c
,
427 const union ubifs_key
*from
, void *to
)
429 union ubifs_key
*t
= to
;
431 t
->j32
[0] = cpu_to_le32(from
->u32
[0]);
432 t
->j32
[1] = cpu_to_le32(from
->u32
[1]);
433 memset(to
+ 8, 0, UBIFS_MAX_KEY_LEN
- 8);
437 * key_write_idx - transform a key from in-memory format for the index.
438 * @c: UBIFS file-system description object
439 * @from: the key to transform
440 * @to: the key to store the result
442 static inline void key_write_idx(const struct ubifs_info
*c
,
443 const union ubifs_key
*from
, void *to
)
445 union ubifs_key
*t
= to
;
447 t
->j32
[0] = cpu_to_le32(from
->u32
[0]);
448 t
->j32
[1] = cpu_to_le32(from
->u32
[1]);
452 * key_copy - copy a key.
453 * @c: UBIFS file-system description object
454 * @from: the key to copy from
455 * @to: the key to copy to
457 static inline void key_copy(const struct ubifs_info
*c
,
458 const union ubifs_key
*from
, union ubifs_key
*to
)
460 to
->u64
[0] = from
->u64
[0];
464 * keys_cmp - compare keys.
465 * @c: UBIFS file-system description object
466 * @key1: the first key to compare
467 * @key2: the second key to compare
469 * This function compares 2 keys and returns %-1 if @key1 is less than
470 * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
472 static inline int keys_cmp(const struct ubifs_info
*c
,
473 const union ubifs_key
*key1
,
474 const union ubifs_key
*key2
)
476 if (key1
->u32
[0] < key2
->u32
[0])
478 if (key1
->u32
[0] > key2
->u32
[0])
480 if (key1
->u32
[1] < key2
->u32
[1])
482 if (key1
->u32
[1] > key2
->u32
[1])
489 * keys_eq - determine if keys are equivalent.
490 * @c: UBIFS file-system description object
491 * @key1: the first key to compare
492 * @key2: the second key to compare
494 * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
497 static inline int keys_eq(const struct ubifs_info
*c
,
498 const union ubifs_key
*key1
,
499 const union ubifs_key
*key2
)
501 if (key1
->u32
[0] != key2
->u32
[0])
503 if (key1
->u32
[1] != key2
->u32
[1])
509 * is_hash_key - is a key vulnerable to hash collisions.
510 * @c: UBIFS file-system description object
513 * This function returns %1 if @key is a hashed key or %0 otherwise.
515 static inline int is_hash_key(const struct ubifs_info
*c
,
516 const union ubifs_key
*key
)
518 int type
= key_type(c
, key
);
520 return type
== UBIFS_DENT_KEY
|| type
== UBIFS_XENT_KEY
;
524 * key_max_inode_size - get maximum file size allowed by current key format.
525 * @c: UBIFS file-system description object
527 static inline unsigned long long key_max_inode_size(const struct ubifs_info
*c
)
529 switch (c
->key_fmt
) {
530 case UBIFS_SIMPLE_KEY_FMT
:
531 return (1ULL << UBIFS_S_KEY_BLOCK_BITS
) * UBIFS_BLOCK_SIZE
;
537 #endif /* !__UBIFS_KEY_H__ */