← Back to branch summary

~pmdj/ubuntu/trusty/qemu/2.9+applesmc+fadtv3

« back to all changes in this revision

Viewing changes to roms/u-boot/fs/ubifs/key.h

  • Committer: Phil Dennis-Jordan
  • Date: 2017-07-21 08:03:43 UTC
  • mfrom: (1.1.1)
  • Revision ID: phil@philjordan.eu-20170721080343-2yr2vdj7713czahv
New upstream release 2.9.0.

Show diffs side-by-side

added added

removed removed

Lines of Context:
roms/u-boot/fs/ubifs/key.h
 
1
/*
 
2
 * This file is part of UBIFS.
 
3
 *
 
4
 * Copyright (C) 2006-2008 Nokia Corporation.
 
5
 *
 
6
 * This program is free software; you can redistribute it and/or modify it
 
7
 * under the terms of the GNU General Public License version 2 as published by
 
8
 * the Free Software Foundation.
 
9
 *
 
10
 * This program is distributed in the hope that it will be useful, but WITHOUT
 
11
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 
12
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 
13
 * more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License along with
 
16
 * this program; if not, write to the Free Software Foundation, Inc., 51
 
17
 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 
18
 *
 
19
 * Authors: Artem Bityutskiy (Битюцкий Артём)
 
20
 *          Adrian Hunter
 
21
 */
 
22
 
 
23
/*
 
24
 * This header contains various key-related definitions and helper function.
 
25
 * UBIFS allows several key schemes, so we access key fields only via these
 
26
 * helpers. At the moment only one key scheme is supported.
 
27
 *
 
28
 * Simple key scheme
 
29
 * ~~~~~~~~~~~~~~~~~
 
30
 *
 
31
 * Keys are 64-bits long. First 32-bits are inode number (parent inode number
 
32
 * in case of direntry key). Next 3 bits are node type. The last 29 bits are
 
33
 * 4KiB offset in case of inode node, and direntry hash in case of a direntry
 
34
 * node. We use "r5" hash borrowed from reiserfs.
 
35
 */
 
36
 
 
37
#ifndef __UBIFS_KEY_H__
 
38
#define __UBIFS_KEY_H__
 
39
 
 
40
/**
 
41
 * key_mask_hash - mask a valid hash value.
 
42
 * @val: value to be masked
 
43
 *
 
44
 * We use hash values as offset in directories, so values %0 and %1 are
 
45
 * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This
 
46
 * function makes sure the reserved values are not used.
 
47
 */
 
48
static inline uint32_t key_mask_hash(uint32_t hash)
 
49
{
 
50
        hash &= UBIFS_S_KEY_HASH_MASK;
 
51
        if (unlikely(hash <= 2))
 
52
                hash += 3;
 
53
        return hash;
 
54
}
 
55
 
 
56
/**
 
57
 * key_r5_hash - R5 hash function (borrowed from reiserfs).
 
58
 * @s: direntry name
 
59
 * @len: name length
 
60
 */
 
61
static inline uint32_t key_r5_hash(const char *s, int len)
 
62
{
 
63
        uint32_t a = 0;
 
64
        const signed char *str = (const signed char *)s;
 
65
 
 
66
        while (*str) {
 
67
                a += *str << 4;
 
68
                a += *str >> 4;
 
69
                a *= 11;
 
70
                str++;
 
71
        }
 
72
 
 
73
        return key_mask_hash(a);
 
74
}
 
75
 
 
76
/**
 
77
 * key_test_hash - testing hash function.
 
78
 * @str: direntry name
 
79
 * @len: name length
 
80
 */
 
81
static inline uint32_t key_test_hash(const char *str, int len)
 
82
{
 
83
        uint32_t a = 0;
 
84
 
 
85
        len = min_t(uint32_t, len, 4);
 
86
        memcpy(&a, str, len);
 
87
        return key_mask_hash(a);
 
88
}
 
89
 
 
90
/**
 
91
 * ino_key_init - initialize inode key.
 
92
 * @c: UBIFS file-system description object
 
93
 * @key: key to initialize
 
94
 * @inum: inode number
 
95
 */
 
96
static inline void ino_key_init(const struct ubifs_info *c,
 
97
                                union ubifs_key *key, ino_t inum)
 
98
{
 
99
        key->u32[0] = inum;
 
100
        key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS;
 
101
}
 
102
 
 
103
/**
 
104
 * ino_key_init_flash - initialize on-flash inode key.
 
105
 * @c: UBIFS file-system description object
 
106
 * @k: key to initialize
 
107
 * @inum: inode number
 
108
 */
 
109
static inline void ino_key_init_flash(const struct ubifs_info *c, void *k,
 
110
                                      ino_t inum)
 
111
{
 
112
        union ubifs_key *key = k;
 
113
 
 
114
        key->j32[0] = cpu_to_le32(inum);
 
115
        key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
 
116
        memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 
117
}
 
118
 
 
119
/**
 
120
 * lowest_ino_key - get the lowest possible inode key.
 
121
 * @c: UBIFS file-system description object
 
122
 * @key: key to initialize
 
123
 * @inum: inode number
 
124
 */
 
125
static inline void lowest_ino_key(const struct ubifs_info *c,
 
126
                                union ubifs_key *key, ino_t inum)
 
127
{
 
128
        key->u32[0] = inum;
 
129
        key->u32[1] = 0;
 
130
}
 
131
 
 
132
/**
 
133
 * highest_ino_key - get the highest possible inode key.
 
134
 * @c: UBIFS file-system description object
 
135
 * @key: key to initialize
 
136
 * @inum: inode number
 
137
 */
 
138
static inline void highest_ino_key(const struct ubifs_info *c,
 
139
                                union ubifs_key *key, ino_t inum)
 
140
{
 
141
        key->u32[0] = inum;
 
142
        key->u32[1] = 0xffffffff;
 
143
}
 
144
 
 
145
/**
 
146
 * dent_key_init - initialize directory entry key.
 
147
 * @c: UBIFS file-system description object
 
148
 * @key: key to initialize
 
149
 * @inum: parent inode number
 
150
 * @nm: direntry name and length
 
151
 */
 
152
static inline void dent_key_init(const struct ubifs_info *c,
 
153
                                 union ubifs_key *key, ino_t inum,
 
154
                                 const struct qstr *nm)
 
155
{
 
156
        uint32_t hash = c->key_hash(nm->name, nm->len);
 
157
 
 
158
        ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
 
159
        key->u32[0] = inum;
 
160
        key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
 
161
}
 
162
 
 
163
/**
 
164
 * dent_key_init_hash - initialize directory entry key without re-calculating
 
165
 *                      hash function.
 
166
 * @c: UBIFS file-system description object
 
167
 * @key: key to initialize
 
168
 * @inum: parent inode number
 
169
 * @hash: direntry name hash
 
170
 */
 
171
static inline void dent_key_init_hash(const struct ubifs_info *c,
 
172
                                      union ubifs_key *key, ino_t inum,
 
173
                                      uint32_t hash)
 
174
{
 
175
        ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
 
176
        key->u32[0] = inum;
 
177
        key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
 
178
}
 
179
 
 
180
/**
 
181
 * dent_key_init_flash - initialize on-flash directory entry key.
 
182
 * @c: UBIFS file-system description object
 
183
 * @k: key to initialize
 
184
 * @inum: parent inode number
 
185
 * @nm: direntry name and length
 
186
 */
 
187
static inline void dent_key_init_flash(const struct ubifs_info *c, void *k,
 
188
                                       ino_t inum, const struct qstr *nm)
 
189
{
 
190
        union ubifs_key *key = k;
 
191
        uint32_t hash = c->key_hash(nm->name, nm->len);
 
192
 
 
193
        ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
 
194
        key->j32[0] = cpu_to_le32(inum);
 
195
        key->j32[1] = cpu_to_le32(hash |
 
196
                                  (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS));
 
197
        memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 
198
}
 
199
 
 
200
/**
 
201
 * lowest_dent_key - get the lowest possible directory entry key.
 
202
 * @c: UBIFS file-system description object
 
203
 * @key: where to store the lowest key
 
204
 * @inum: parent inode number
 
205
 */
 
206
static inline void lowest_dent_key(const struct ubifs_info *c,
 
207
                                   union ubifs_key *key, ino_t inum)
 
208
{
 
209
        key->u32[0] = inum;
 
210
        key->u32[1] = UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS;
 
211
}
 
212
 
 
213
/**
 
214
 * xent_key_init - initialize extended attribute entry key.
 
215
 * @c: UBIFS file-system description object
 
216
 * @key: key to initialize
 
217
 * @inum: host inode number
 
218
 * @nm: extended attribute entry name and length
 
219
 */
 
220
static inline void xent_key_init(const struct ubifs_info *c,
 
221
                                 union ubifs_key *key, ino_t inum,
 
222
                                 const struct qstr *nm)
 
223
{
 
224
        uint32_t hash = c->key_hash(nm->name, nm->len);
 
225
 
 
226
        ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
 
227
        key->u32[0] = inum;
 
228
        key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
 
229
}
 
230
 
 
231
/**
 
232
 * xent_key_init_hash - initialize extended attribute entry key without
 
233
 *                      re-calculating hash function.
 
234
 * @c: UBIFS file-system description object
 
235
 * @key: key to initialize
 
236
 * @inum: host inode number
 
237
 * @hash: extended attribute entry name hash
 
238
 */
 
239
static inline void xent_key_init_hash(const struct ubifs_info *c,
 
240
                                      union ubifs_key *key, ino_t inum,
 
241
                                      uint32_t hash)
 
242
{
 
243
        ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
 
244
        key->u32[0] = inum;
 
245
        key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
 
246
}
 
247
 
 
248
/**
 
249
 * xent_key_init_flash - initialize on-flash extended attribute entry key.
 
250
 * @c: UBIFS file-system description object
 
251
 * @k: key to initialize
 
252
 * @inum: host inode number
 
253
 * @nm: extended attribute entry name and length
 
254
 */
 
255
static inline void xent_key_init_flash(const struct ubifs_info *c, void *k,
 
256
                                       ino_t inum, const struct qstr *nm)
 
257
{
 
258
        union ubifs_key *key = k;
 
259
        uint32_t hash = c->key_hash(nm->name, nm->len);
 
260
 
 
261
        ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
 
262
        key->j32[0] = cpu_to_le32(inum);
 
263
        key->j32[1] = cpu_to_le32(hash |
 
264
                                  (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS));
 
265
        memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 
266
}
 
267
 
 
268
/**
 
269
 * lowest_xent_key - get the lowest possible extended attribute entry key.
 
270
 * @c: UBIFS file-system description object
 
271
 * @key: where to store the lowest key
 
272
 * @inum: host inode number
 
273
 */
 
274
static inline void lowest_xent_key(const struct ubifs_info *c,
 
275
                                   union ubifs_key *key, ino_t inum)
 
276
{
 
277
        key->u32[0] = inum;
 
278
        key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
 
279
}
 
280
 
 
281
/**
 
282
 * data_key_init - initialize data key.
 
283
 * @c: UBIFS file-system description object
 
284
 * @key: key to initialize
 
285
 * @inum: inode number
 
286
 * @block: block number
 
287
 */
 
288
static inline void data_key_init(const struct ubifs_info *c,
 
289
                                 union ubifs_key *key, ino_t inum,
 
290
                                 unsigned int block)
 
291
{
 
292
        ubifs_assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK));
 
293
        key->u32[0] = inum;
 
294
        key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
 
295
}
 
296
 
 
297
/**
 
298
 * data_key_init_flash - initialize on-flash data key.
 
299
 * @c: UBIFS file-system description object
 
300
 * @k: key to initialize
 
301
 * @inum: inode number
 
302
 * @block: block number
 
303
 */
 
304
static inline void data_key_init_flash(const struct ubifs_info *c, void *k,
 
305
                                       ino_t inum, unsigned int block)
 
306
{
 
307
        union ubifs_key *key = k;
 
308
 
 
309
        ubifs_assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK));
 
310
        key->j32[0] = cpu_to_le32(inum);
 
311
        key->j32[1] = cpu_to_le32(block |
 
312
                                  (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS));
 
313
        memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 
314
}
 
315
 
 
316
/**
 
317
 * trun_key_init - initialize truncation node key.
 
318
 * @c: UBIFS file-system description object
 
319
 * @key: key to initialize
 
320
 * @inum: inode number
 
321
 *
 
322
 * Note, UBIFS does not have truncation keys on the media and this function is
 
323
 * only used for purposes of replay.
 
324
 */
 
325
static inline void trun_key_init(const struct ubifs_info *c,
 
326
                                 union ubifs_key *key, ino_t inum)
 
327
{
 
328
        key->u32[0] = inum;
 
329
        key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
 
330
}
 
331
 
 
332
/**
 
333
 * key_type - get key type.
 
334
 * @c: UBIFS file-system description object
 
335
 * @key: key to get type of
 
336
 */
 
337
static inline int key_type(const struct ubifs_info *c,
 
338
                           const union ubifs_key *key)
 
339
{
 
340
        return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
 
341
}
 
342
 
 
343
/**
 
344
 * key_type_flash - get type of a on-flash formatted key.
 
345
 * @c: UBIFS file-system description object
 
346
 * @k: key to get type of
 
347
 */
 
348
static inline int key_type_flash(const struct ubifs_info *c, const void *k)
 
349
{
 
350
        const union ubifs_key *key = k;
 
351
 
 
352
        return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
 
353
}
 
354
 
 
355
/**
 
356
 * key_inum - fetch inode number from key.
 
357
 * @c: UBIFS file-system description object
 
358
 * @k: key to fetch inode number from
 
359
 */
 
360
static inline ino_t key_inum(const struct ubifs_info *c, const void *k)
 
361
{
 
362
        const union ubifs_key *key = k;
 
363
 
 
364
        return key->u32[0];
 
365
}
 
366
 
 
367
/**
 
368
 * key_inum_flash - fetch inode number from an on-flash formatted key.
 
369
 * @c: UBIFS file-system description object
 
370
 * @k: key to fetch inode number from
 
371
 */
 
372
static inline ino_t key_inum_flash(const struct ubifs_info *c, const void *k)
 
373
{
 
374
        const union ubifs_key *key = k;
 
375
 
 
376
        return le32_to_cpu(key->j32[0]);
 
377
}
 
378
 
 
379
/**
 
380
 * key_hash - get directory entry hash.
 
381
 * @c: UBIFS file-system description object
 
382
 * @key: the key to get hash from
 
383
 */
 
384
static inline int key_hash(const struct ubifs_info *c,
 
385
                           const union ubifs_key *key)
 
386
{
 
387
        return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
 
388
}
 
389
 
 
390
/**
 
391
 * key_hash_flash - get directory entry hash from an on-flash formatted key.
 
392
 * @c: UBIFS file-system description object
 
393
 * @k: the key to get hash from
 
394
 */
 
395
static inline int key_hash_flash(const struct ubifs_info *c, const void *k)
 
396
{
 
397
        const union ubifs_key *key = k;
 
398
 
 
399
        return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
 
400
}
 
401
 
 
402
/**
 
403
 * key_block - get data block number.
 
404
 * @c: UBIFS file-system description object
 
405
 * @key: the key to get the block number from
 
406
 */
 
407
static inline unsigned int key_block(const struct ubifs_info *c,
 
408
                                     const union ubifs_key *key)
 
409
{
 
410
        return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
 
411
}
 
412
 
 
413
/**
 
414
 * key_block_flash - get data block number from an on-flash formatted key.
 
415
 * @c: UBIFS file-system description object
 
416
 * @k: the key to get the block number from
 
417
 */
 
418
static inline unsigned int key_block_flash(const struct ubifs_info *c,
 
419
                                           const void *k)
 
420
{
 
421
        const union ubifs_key *key = k;
 
422
 
 
423
        return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK;
 
424
}
 
425
 
 
426
/**
 
427
 * key_read - transform a key to 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_read(const struct ubifs_info *c, const void *from,
 
433
                            union ubifs_key *to)
 
434
{
 
435
        const union ubifs_key *f = from;
 
436
 
 
437
        to->u32[0] = le32_to_cpu(f->j32[0]);
 
438
        to->u32[1] = le32_to_cpu(f->j32[1]);
 
439
}
 
440
 
 
441
/**
 
442
 * key_write - transform a key from in-memory format.
 
443
 * @c: UBIFS file-system description object
 
444
 * @from: the key to transform
 
445
 * @to: the key to store the result
 
446
 */
 
447
static inline void key_write(const struct ubifs_info *c,
 
448
                             const union ubifs_key *from, void *to)
 
449
{
 
450
        union ubifs_key *t = to;
 
451
 
 
452
        t->j32[0] = cpu_to_le32(from->u32[0]);
 
453
        t->j32[1] = cpu_to_le32(from->u32[1]);
 
454
        memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
 
455
}
 
456
 
 
457
/**
 
458
 * key_write_idx - transform a key from in-memory format for the index.
 
459
 * @c: UBIFS file-system description object
 
460
 * @from: the key to transform
 
461
 * @to: the key to store the result
 
462
 */
 
463
static inline void key_write_idx(const struct ubifs_info *c,
 
464
                                 const union ubifs_key *from, void *to)
 
465
{
 
466
        union ubifs_key *t = to;
 
467
 
 
468
        t->j32[0] = cpu_to_le32(from->u32[0]);
 
469
        t->j32[1] = cpu_to_le32(from->u32[1]);
 
470
}
 
471
 
 
472
/**
 
473
 * key_copy - copy a key.
 
474
 * @c: UBIFS file-system description object
 
475
 * @from: the key to copy from
 
476
 * @to: the key to copy to
 
477
 */
 
478
static inline void key_copy(const struct ubifs_info *c,
 
479
                            const union ubifs_key *from, union ubifs_key *to)
 
480
{
 
481
        to->u64[0] = from->u64[0];
 
482
}
 
483
 
 
484
/**
 
485
 * keys_cmp - compare keys.
 
486
 * @c: UBIFS file-system description object
 
487
 * @key1: the first key to compare
 
488
 * @key2: the second key to compare
 
489
 *
 
490
 * This function compares 2 keys and returns %-1 if @key1 is less than
 
491
 * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
 
492
 */
 
493
static inline int keys_cmp(const struct ubifs_info *c,
 
494
                           const union ubifs_key *key1,
 
495
                           const union ubifs_key *key2)
 
496
{
 
497
        if (key1->u32[0] < key2->u32[0])
 
498
                return -1;
 
499
        if (key1->u32[0] > key2->u32[0])
 
500
                return 1;
 
501
        if (key1->u32[1] < key2->u32[1])
 
502
                return -1;
 
503
        if (key1->u32[1] > key2->u32[1])
 
504
                return 1;
 
505
 
 
506
        return 0;
 
507
}
 
508
 
 
509
/**
 
510
 * keys_eq - determine if keys are equivalent.
 
511
 * @c: UBIFS file-system description object
 
512
 * @key1: the first key to compare
 
513
 * @key2: the second key to compare
 
514
 *
 
515
 * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
 
516
 * %0 if not.
 
517
 */
 
518
static inline int keys_eq(const struct ubifs_info *c,
 
519
                          const union ubifs_key *key1,
 
520
                          const union ubifs_key *key2)
 
521
{
 
522
        if (key1->u32[0] != key2->u32[0])
 
523
                return 0;
 
524
        if (key1->u32[1] != key2->u32[1])
 
525
                return 0;
 
526
        return 1;
 
527
}
 
528
 
 
529
/**
 
530
 * is_hash_key - is a key vulnerable to hash collisions.
 
531
 * @c: UBIFS file-system description object
 
532
 * @key: key
 
533
 *
 
534
 * This function returns %1 if @key is a hashed key or %0 otherwise.
 
535
 */
 
536
static inline int is_hash_key(const struct ubifs_info *c,
 
537
                              const union ubifs_key *key)
 
538
{
 
539
        int type = key_type(c, key);
 
540
 
 
541
        return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
 
542
}
 
543
 
 
544
/**
 
545
 * key_max_inode_size - get maximum file size allowed by current key format.
 
546
 * @c: UBIFS file-system description object
 
547
 */
 
548
static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
 
549
{
 
550
        switch (c->key_fmt) {
 
551
        case UBIFS_SIMPLE_KEY_FMT:
 
552
                return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
 
553
        default:
 
554
                return 0;
 
555
        }
 
556
}
 
557
#endif /* !__UBIFS_KEY_H__ */