forked from torvalds/linux
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ubifs.h
1859 lines (1728 loc) · 63.2 KB
/
ubifs.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* This file is part of UBIFS.
*
* Copyright (C) 2006-2008 Nokia Corporation
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as published by
* the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program; if not, write to the Free Software Foundation, Inc., 51
* Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*
* Authors: Artem Bityutskiy (Битюцкий Артём)
* Adrian Hunter
*/
#ifndef __UBIFS_H__
#define __UBIFS_H__
#include <asm/div64.h>
#include <linux/statfs.h>
#include <linux/fs.h>
#include <linux/err.h>
#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/spinlock.h>
#include <linux/mutex.h>
#include <linux/rwsem.h>
#include <linux/mtd/ubi.h>
#include <linux/pagemap.h>
#include <linux/backing-dev.h>
#include <linux/security.h>
#include <linux/xattr.h>
#include <linux/random.h>
#define __FS_HAS_ENCRYPTION IS_ENABLED(CONFIG_UBIFS_FS_ENCRYPTION)
#include <linux/fscrypt.h>
#include "ubifs-media.h"
/* Version of this UBIFS implementation */
#define UBIFS_VERSION 1
/* UBIFS file system VFS magic number */
#define UBIFS_SUPER_MAGIC 0x24051905
/* Number of UBIFS blocks per VFS page */
#define UBIFS_BLOCKS_PER_PAGE (PAGE_SIZE / UBIFS_BLOCK_SIZE)
#define UBIFS_BLOCKS_PER_PAGE_SHIFT (PAGE_SHIFT - UBIFS_BLOCK_SHIFT)
/* "File system end of life" sequence number watermark */
#define SQNUM_WARN_WATERMARK 0xFFFFFFFF00000000ULL
#define SQNUM_WATERMARK 0xFFFFFFFFFF000000ULL
/*
* Minimum amount of LEBs reserved for the index. At present the index needs at
* least 2 LEBs: one for the index head and one for in-the-gaps method (which
* currently does not cater for the index head and so excludes it from
* consideration).
*/
#define MIN_INDEX_LEBS 2
/* Minimum amount of data UBIFS writes to the flash */
#define MIN_WRITE_SZ (UBIFS_DATA_NODE_SZ + 8)
/*
* Currently we do not support inode number overlapping and re-using, so this
* watermark defines dangerous inode number level. This should be fixed later,
* although it is difficult to exceed current limit. Another option is to use
* 64-bit inode numbers, but this means more overhead.
*/
#define INUM_WARN_WATERMARK 0xFFF00000
#define INUM_WATERMARK 0xFFFFFF00
/* Maximum number of entries in each LPT (LEB category) heap */
#define LPT_HEAP_SZ 256
/*
* Background thread name pattern. The numbers are UBI device and volume
* numbers.
*/
#define BGT_NAME_PATTERN "ubifs_bgt%d_%d"
/* Maximum possible inode number (only 32-bit inodes are supported now) */
#define MAX_INUM 0xFFFFFFFF
/* Number of non-data journal heads */
#define NONDATA_JHEADS_CNT 2
/* Shorter names for journal head numbers for internal usage */
#define GCHD UBIFS_GC_HEAD
#define BASEHD UBIFS_BASE_HEAD
#define DATAHD UBIFS_DATA_HEAD
/* 'No change' value for 'ubifs_change_lp()' */
#define LPROPS_NC 0x80000001
/*
* There is no notion of truncation key because truncation nodes do not exist
* in TNC. However, when replaying, it is handy to introduce fake "truncation"
* keys for truncation nodes because the code becomes simpler. So we define
* %UBIFS_TRUN_KEY type.
*
* But otherwise, out of the journal reply scope, the truncation keys are
* invalid.
*/
#define UBIFS_TRUN_KEY UBIFS_KEY_TYPES_CNT
#define UBIFS_INVALID_KEY UBIFS_KEY_TYPES_CNT
/*
* How much a directory entry/extended attribute entry adds to the parent/host
* inode.
*/
#define CALC_DENT_SIZE(name_len) ALIGN(UBIFS_DENT_NODE_SZ + (name_len) + 1, 8)
/* How much an extended attribute adds to the host inode */
#define CALC_XATTR_BYTES(data_len) ALIGN(UBIFS_INO_NODE_SZ + (data_len) + 1, 8)
/*
* Znodes which were not touched for 'OLD_ZNODE_AGE' seconds are considered
* "old", and znode which were touched last 'YOUNG_ZNODE_AGE' seconds ago are
* considered "young". This is used by shrinker when selecting znode to trim
* off.
*/
#define OLD_ZNODE_AGE 20
#define YOUNG_ZNODE_AGE 5
/*
* Some compressors, like LZO, may end up with more data then the input buffer.
* So UBIFS always allocates larger output buffer, to be sure the compressor
* will not corrupt memory in case of worst case compression.
*/
#define WORST_COMPR_FACTOR 2
#ifdef CONFIG_UBIFS_FS_ENCRYPTION
#define UBIFS_CIPHER_BLOCK_SIZE FS_CRYPTO_BLOCK_SIZE
#else
#define UBIFS_CIPHER_BLOCK_SIZE 0
#endif
/*
* How much memory is needed for a buffer where we compress a data node.
*/
#define COMPRESSED_DATA_NODE_BUF_SZ \
(UBIFS_DATA_NODE_SZ + UBIFS_BLOCK_SIZE * WORST_COMPR_FACTOR)
/* Maximum expected tree height for use by bottom_up_buf */
#define BOTTOM_UP_HEIGHT 64
/* Maximum number of data nodes to bulk-read */
#define UBIFS_MAX_BULK_READ 32
/*
* Lockdep classes for UBIFS inode @ui_mutex.
*/
enum {
WB_MUTEX_1 = 0,
WB_MUTEX_2 = 1,
WB_MUTEX_3 = 2,
WB_MUTEX_4 = 3,
};
/*
* Znode flags (actually, bit numbers which store the flags).
*
* DIRTY_ZNODE: znode is dirty
* COW_ZNODE: znode is being committed and a new instance of this znode has to
* be created before changing this znode
* OBSOLETE_ZNODE: znode is obsolete, which means it was deleted, but it is
* still in the commit list and the ongoing commit operation
* will commit it, and delete this znode after it is done
*/
enum {
DIRTY_ZNODE = 0,
COW_ZNODE = 1,
OBSOLETE_ZNODE = 2,
};
/*
* Commit states.
*
* COMMIT_RESTING: commit is not wanted
* COMMIT_BACKGROUND: background commit has been requested
* COMMIT_REQUIRED: commit is required
* COMMIT_RUNNING_BACKGROUND: background commit is running
* COMMIT_RUNNING_REQUIRED: commit is running and it is required
* COMMIT_BROKEN: commit failed
*/
enum {
COMMIT_RESTING = 0,
COMMIT_BACKGROUND,
COMMIT_REQUIRED,
COMMIT_RUNNING_BACKGROUND,
COMMIT_RUNNING_REQUIRED,
COMMIT_BROKEN,
};
/*
* 'ubifs_scan_a_node()' return values.
*
* SCANNED_GARBAGE: scanned garbage
* SCANNED_EMPTY_SPACE: scanned empty space
* SCANNED_A_NODE: scanned a valid node
* SCANNED_A_CORRUPT_NODE: scanned a corrupted node
* SCANNED_A_BAD_PAD_NODE: scanned a padding node with invalid pad length
*
* Greater than zero means: 'scanned that number of padding bytes'
*/
enum {
SCANNED_GARBAGE = 0,
SCANNED_EMPTY_SPACE = -1,
SCANNED_A_NODE = -2,
SCANNED_A_CORRUPT_NODE = -3,
SCANNED_A_BAD_PAD_NODE = -4,
};
/*
* LPT cnode flag bits.
*
* DIRTY_CNODE: cnode is dirty
* OBSOLETE_CNODE: cnode is being committed and has been copied (or deleted),
* so it can (and must) be freed when the commit is finished
* COW_CNODE: cnode is being committed and must be copied before writing
*/
enum {
DIRTY_CNODE = 0,
OBSOLETE_CNODE = 1,
COW_CNODE = 2,
};
/*
* Dirty flag bits (lpt_drty_flgs) for LPT special nodes.
*
* LTAB_DIRTY: ltab node is dirty
* LSAVE_DIRTY: lsave node is dirty
*/
enum {
LTAB_DIRTY = 1,
LSAVE_DIRTY = 2,
};
/*
* Return codes used by the garbage collector.
* @LEB_FREED: the logical eraseblock was freed and is ready to use
* @LEB_FREED_IDX: indexing LEB was freed and can be used only after the commit
* @LEB_RETAINED: the logical eraseblock was freed and retained for GC purposes
*/
enum {
LEB_FREED,
LEB_FREED_IDX,
LEB_RETAINED,
};
/**
* struct ubifs_old_idx - index node obsoleted since last commit start.
* @rb: rb-tree node
* @lnum: LEB number of obsoleted index node
* @offs: offset of obsoleted index node
*/
struct ubifs_old_idx {
struct rb_node rb;
int lnum;
int offs;
};
/* The below union makes it easier to deal with keys */
union ubifs_key {
uint8_t u8[UBIFS_SK_LEN];
uint32_t u32[UBIFS_SK_LEN/4];
uint64_t u64[UBIFS_SK_LEN/8];
__le32 j32[UBIFS_SK_LEN/4];
};
/**
* struct ubifs_scan_node - UBIFS scanned node information.
* @list: list of scanned nodes
* @key: key of node scanned (if it has one)
* @sqnum: sequence number
* @type: type of node scanned
* @offs: offset with LEB of node scanned
* @len: length of node scanned
* @node: raw node
*/
struct ubifs_scan_node {
struct list_head list;
union ubifs_key key;
unsigned long long sqnum;
int type;
int offs;
int len;
void *node;
};
/**
* struct ubifs_scan_leb - UBIFS scanned LEB information.
* @lnum: logical eraseblock number
* @nodes_cnt: number of nodes scanned
* @nodes: list of struct ubifs_scan_node
* @endpt: end point (and therefore the start of empty space)
* @buf: buffer containing entire LEB scanned
*/
struct ubifs_scan_leb {
int lnum;
int nodes_cnt;
struct list_head nodes;
int endpt;
void *buf;
};
/**
* struct ubifs_gced_idx_leb - garbage-collected indexing LEB.
* @list: list
* @lnum: LEB number
* @unmap: OK to unmap this LEB
*
* This data structure is used to temporary store garbage-collected indexing
* LEBs - they are not released immediately, but only after the next commit.
* This is needed to guarantee recoverability.
*/
struct ubifs_gced_idx_leb {
struct list_head list;
int lnum;
int unmap;
};
/**
* struct ubifs_inode - UBIFS in-memory inode description.
* @vfs_inode: VFS inode description object
* @creat_sqnum: sequence number at time of creation
* @del_cmtno: commit number corresponding to the time the inode was deleted,
* protected by @c->commit_sem;
* @xattr_size: summarized size of all extended attributes in bytes
* @xattr_cnt: count of extended attributes this inode has
* @xattr_names: sum of lengths of all extended attribute names belonging to
* this inode
* @dirty: non-zero if the inode is dirty
* @xattr: non-zero if this is an extended attribute inode
* @bulk_read: non-zero if bulk-read should be used
* @ui_mutex: serializes inode write-back with the rest of VFS operations,
* serializes "clean <-> dirty" state changes, serializes bulk-read,
* protects @dirty, @bulk_read, @ui_size, and @xattr_size
* @ui_lock: protects @synced_i_size
* @synced_i_size: synchronized size of inode, i.e. the value of inode size
* currently stored on the flash; used only for regular file
* inodes
* @ui_size: inode size used by UBIFS when writing to flash
* @flags: inode flags (@UBIFS_COMPR_FL, etc)
* @compr_type: default compression type used for this inode
* @last_page_read: page number of last page read (for bulk read)
* @read_in_a_row: number of consecutive pages read in a row (for bulk read)
* @data_len: length of the data attached to the inode
* @data: inode's data
*
* @ui_mutex exists for two main reasons. At first it prevents inodes from
* being written back while UBIFS changing them, being in the middle of an VFS
* operation. This way UBIFS makes sure the inode fields are consistent. For
* example, in 'ubifs_rename()' we change 3 inodes simultaneously, and
* write-back must not write any of them before we have finished.
*
* The second reason is budgeting - UBIFS has to budget all operations. If an
* operation is going to mark an inode dirty, it has to allocate budget for
* this. It cannot just mark it dirty because there is no guarantee there will
* be enough flash space to write the inode back later. This means UBIFS has
* to have full control over inode "clean <-> dirty" transitions (and pages
* actually). But unfortunately, VFS marks inodes dirty in many places, and it
* does not ask the file-system if it is allowed to do so (there is a notifier,
* but it is not enough), i.e., there is no mechanism to synchronize with this.
* So UBIFS has its own inode dirty flag and its own mutex to serialize
* "clean <-> dirty" transitions.
*
* The @synced_i_size field is used to make sure we never write pages which are
* beyond last synchronized inode size. See 'ubifs_writepage()' for more
* information.
*
* The @ui_size is a "shadow" variable for @inode->i_size and UBIFS uses
* @ui_size instead of @inode->i_size. The reason for this is that UBIFS cannot
* make sure @inode->i_size is always changed under @ui_mutex, because it
* cannot call 'truncate_setsize()' with @ui_mutex locked, because it would
* deadlock with 'ubifs_writepage()' (see file.c). All the other inode fields
* are changed under @ui_mutex, so they do not need "shadow" fields. Note, one
* could consider to rework locking and base it on "shadow" fields.
*/
struct ubifs_inode {
struct inode vfs_inode;
unsigned long long creat_sqnum;
unsigned long long del_cmtno;
unsigned int xattr_size;
unsigned int xattr_cnt;
unsigned int xattr_names;
unsigned int dirty:1;
unsigned int xattr:1;
unsigned int bulk_read:1;
unsigned int compr_type:2;
struct mutex ui_mutex;
spinlock_t ui_lock;
loff_t synced_i_size;
loff_t ui_size;
int flags;
pgoff_t last_page_read;
pgoff_t read_in_a_row;
int data_len;
void *data;
};
/**
* struct ubifs_unclean_leb - records a LEB recovered under read-only mode.
* @list: list
* @lnum: LEB number of recovered LEB
* @endpt: offset where recovery ended
*
* This structure records a LEB identified during recovery that needs to be
* cleaned but was not because UBIFS was mounted read-only. The information
* is used to clean the LEB when remounting to read-write mode.
*/
struct ubifs_unclean_leb {
struct list_head list;
int lnum;
int endpt;
};
/*
* LEB properties flags.
*
* LPROPS_UNCAT: not categorized
* LPROPS_DIRTY: dirty > free, dirty >= @c->dead_wm, not index
* LPROPS_DIRTY_IDX: dirty + free > @c->min_idx_node_sze and index
* LPROPS_FREE: free > 0, dirty < @c->dead_wm, not empty, not index
* LPROPS_HEAP_CNT: number of heaps used for storing categorized LEBs
* LPROPS_EMPTY: LEB is empty, not taken
* LPROPS_FREEABLE: free + dirty == leb_size, not index, not taken
* LPROPS_FRDI_IDX: free + dirty == leb_size and index, may be taken
* LPROPS_CAT_MASK: mask for the LEB categories above
* LPROPS_TAKEN: LEB was taken (this flag is not saved on the media)
* LPROPS_INDEX: LEB contains indexing nodes (this flag also exists on flash)
*/
enum {
LPROPS_UNCAT = 0,
LPROPS_DIRTY = 1,
LPROPS_DIRTY_IDX = 2,
LPROPS_FREE = 3,
LPROPS_HEAP_CNT = 3,
LPROPS_EMPTY = 4,
LPROPS_FREEABLE = 5,
LPROPS_FRDI_IDX = 6,
LPROPS_CAT_MASK = 15,
LPROPS_TAKEN = 16,
LPROPS_INDEX = 32,
};
/**
* struct ubifs_lprops - logical eraseblock properties.
* @free: amount of free space in bytes
* @dirty: amount of dirty space in bytes
* @flags: LEB properties flags (see above)
* @lnum: LEB number
* @list: list of same-category lprops (for LPROPS_EMPTY and LPROPS_FREEABLE)
* @hpos: heap position in heap of same-category lprops (other categories)
*/
struct ubifs_lprops {
int free;
int dirty;
int flags;
int lnum;
union {
struct list_head list;
int hpos;
};
};
/**
* struct ubifs_lpt_lprops - LPT logical eraseblock properties.
* @free: amount of free space in bytes
* @dirty: amount of dirty space in bytes
* @tgc: trivial GC flag (1 => unmap after commit end)
* @cmt: commit flag (1 => reserved for commit)
*/
struct ubifs_lpt_lprops {
int free;
int dirty;
unsigned tgc:1;
unsigned cmt:1;
};
/**
* struct ubifs_lp_stats - statistics of eraseblocks in the main area.
* @empty_lebs: number of empty LEBs
* @taken_empty_lebs: number of taken LEBs
* @idx_lebs: number of indexing LEBs
* @total_free: total free space in bytes (includes all LEBs)
* @total_dirty: total dirty space in bytes (includes all LEBs)
* @total_used: total used space in bytes (does not include index LEBs)
* @total_dead: total dead space in bytes (does not include index LEBs)
* @total_dark: total dark space in bytes (does not include index LEBs)
*
* The @taken_empty_lebs field counts the LEBs that are in the transient state
* of having been "taken" for use but not yet written to. @taken_empty_lebs is
* needed to account correctly for @gc_lnum, otherwise @empty_lebs could be
* used by itself (in which case 'unused_lebs' would be a better name). In the
* case of @gc_lnum, it is "taken" at mount time or whenever a LEB is retained
* by GC, but unlike other empty LEBs that are "taken", it may not be written
* straight away (i.e. before the next commit start or unmount), so either
* @gc_lnum must be specially accounted for, or the current approach followed
* i.e. count it under @taken_empty_lebs.
*
* @empty_lebs includes @taken_empty_lebs.
*
* @total_used, @total_dead and @total_dark fields do not account indexing
* LEBs.
*/
struct ubifs_lp_stats {
int empty_lebs;
int taken_empty_lebs;
int idx_lebs;
long long total_free;
long long total_dirty;
long long total_used;
long long total_dead;
long long total_dark;
};
struct ubifs_nnode;
/**
* struct ubifs_cnode - LEB Properties Tree common node.
* @parent: parent nnode
* @cnext: next cnode to commit
* @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE)
* @iip: index in parent
* @level: level in the tree (zero for pnodes, greater than zero for nnodes)
* @num: node number
*/
struct ubifs_cnode {
struct ubifs_nnode *parent;
struct ubifs_cnode *cnext;
unsigned long flags;
int iip;
int level;
int num;
};
/**
* struct ubifs_pnode - LEB Properties Tree leaf node.
* @parent: parent nnode
* @cnext: next cnode to commit
* @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE)
* @iip: index in parent
* @level: level in the tree (always zero for pnodes)
* @num: node number
* @lprops: LEB properties array
*/
struct ubifs_pnode {
struct ubifs_nnode *parent;
struct ubifs_cnode *cnext;
unsigned long flags;
int iip;
int level;
int num;
struct ubifs_lprops lprops[UBIFS_LPT_FANOUT];
};
/**
* struct ubifs_nbranch - LEB Properties Tree internal node branch.
* @lnum: LEB number of child
* @offs: offset of child
* @nnode: nnode child
* @pnode: pnode child
* @cnode: cnode child
*/
struct ubifs_nbranch {
int lnum;
int offs;
union {
struct ubifs_nnode *nnode;
struct ubifs_pnode *pnode;
struct ubifs_cnode *cnode;
};
};
/**
* struct ubifs_nnode - LEB Properties Tree internal node.
* @parent: parent nnode
* @cnext: next cnode to commit
* @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE)
* @iip: index in parent
* @level: level in the tree (always greater than zero for nnodes)
* @num: node number
* @nbranch: branches to child nodes
*/
struct ubifs_nnode {
struct ubifs_nnode *parent;
struct ubifs_cnode *cnext;
unsigned long flags;
int iip;
int level;
int num;
struct ubifs_nbranch nbranch[UBIFS_LPT_FANOUT];
};
/**
* struct ubifs_lpt_heap - heap of categorized lprops.
* @arr: heap array
* @cnt: number in heap
* @max_cnt: maximum number allowed in heap
*
* There are %LPROPS_HEAP_CNT heaps.
*/
struct ubifs_lpt_heap {
struct ubifs_lprops **arr;
int cnt;
int max_cnt;
};
/*
* Return codes for LPT scan callback function.
*
* LPT_SCAN_CONTINUE: continue scanning
* LPT_SCAN_ADD: add the LEB properties scanned to the tree in memory
* LPT_SCAN_STOP: stop scanning
*/
enum {
LPT_SCAN_CONTINUE = 0,
LPT_SCAN_ADD = 1,
LPT_SCAN_STOP = 2,
};
struct ubifs_info;
/* Callback used by the 'ubifs_lpt_scan_nolock()' function */
typedef int (*ubifs_lpt_scan_callback)(struct ubifs_info *c,
const struct ubifs_lprops *lprops,
int in_tree, void *data);
/**
* struct ubifs_wbuf - UBIFS write-buffer.
* @c: UBIFS file-system description object
* @buf: write-buffer (of min. flash I/O unit size)
* @lnum: logical eraseblock number the write-buffer points to
* @offs: write-buffer offset in this logical eraseblock
* @avail: number of bytes available in the write-buffer
* @used: number of used bytes in the write-buffer
* @size: write-buffer size (in [@c->min_io_size, @c->max_write_size] range)
* @jhead: journal head the mutex belongs to (note, needed only to shut lockdep
* up by 'mutex_lock_nested()).
* @sync_callback: write-buffer synchronization callback
* @io_mutex: serializes write-buffer I/O
* @lock: serializes @buf, @lnum, @offs, @avail, @used, @next_ino and @inodes
* fields
* @timer: write-buffer timer
* @no_timer: non-zero if this write-buffer does not have a timer
* @need_sync: non-zero if the timer expired and the wbuf needs sync'ing
* @next_ino: points to the next position of the following inode number
* @inodes: stores the inode numbers of the nodes which are in wbuf
*
* The write-buffer synchronization callback is called when the write-buffer is
* synchronized in order to notify how much space was wasted due to
* write-buffer padding and how much free space is left in the LEB.
*
* Note: the fields @buf, @lnum, @offs, @avail and @used can be read under
* spin-lock or mutex because they are written under both mutex and spin-lock.
* @buf is appended to under mutex but overwritten under both mutex and
* spin-lock. Thus the data between @buf and @buf + @used can be read under
* spinlock.
*/
struct ubifs_wbuf {
struct ubifs_info *c;
void *buf;
int lnum;
int offs;
int avail;
int used;
int size;
int jhead;
int (*sync_callback)(struct ubifs_info *c, int lnum, int free, int pad);
struct mutex io_mutex;
spinlock_t lock;
struct hrtimer timer;
unsigned int no_timer:1;
unsigned int need_sync:1;
int next_ino;
ino_t *inodes;
};
/**
* struct ubifs_bud - bud logical eraseblock.
* @lnum: logical eraseblock number
* @start: where the (uncommitted) bud data starts
* @jhead: journal head number this bud belongs to
* @list: link in the list buds belonging to the same journal head
* @rb: link in the tree of all buds
*/
struct ubifs_bud {
int lnum;
int start;
int jhead;
struct list_head list;
struct rb_node rb;
};
/**
* struct ubifs_jhead - journal head.
* @wbuf: head's write-buffer
* @buds_list: list of bud LEBs belonging to this journal head
* @grouped: non-zero if UBIFS groups nodes when writing to this journal head
*
* Note, the @buds list is protected by the @c->buds_lock.
*/
struct ubifs_jhead {
struct ubifs_wbuf wbuf;
struct list_head buds_list;
unsigned int grouped:1;
};
/**
* struct ubifs_zbranch - key/coordinate/length branch stored in znodes.
* @key: key
* @znode: znode address in memory
* @lnum: LEB number of the target node (indexing node or data node)
* @offs: target node offset within @lnum
* @len: target node length
*/
struct ubifs_zbranch {
union ubifs_key key;
union {
struct ubifs_znode *znode;
void *leaf;
};
int lnum;
int offs;
int len;
};
/**
* struct ubifs_znode - in-memory representation of an indexing node.
* @parent: parent znode or NULL if it is the root
* @cnext: next znode to commit
* @flags: znode flags (%DIRTY_ZNODE, %COW_ZNODE or %OBSOLETE_ZNODE)
* @time: last access time (seconds)
* @level: level of the entry in the TNC tree
* @child_cnt: count of child znodes
* @iip: index in parent's zbranch array
* @alt: lower bound of key range has altered i.e. child inserted at slot 0
* @lnum: LEB number of the corresponding indexing node
* @offs: offset of the corresponding indexing node
* @len: length of the corresponding indexing node
* @zbranch: array of znode branches (@c->fanout elements)
*
* Note! The @lnum, @offs, and @len fields are not really needed - we have them
* only for internal consistency check. They could be removed to save some RAM.
*/
struct ubifs_znode {
struct ubifs_znode *parent;
struct ubifs_znode *cnext;
unsigned long flags;
unsigned long time;
int level;
int child_cnt;
int iip;
int alt;
int lnum;
int offs;
int len;
struct ubifs_zbranch zbranch[];
};
/**
* struct bu_info - bulk-read information.
* @key: first data node key
* @zbranch: zbranches of data nodes to bulk read
* @buf: buffer to read into
* @buf_len: buffer length
* @gc_seq: GC sequence number to detect races with GC
* @cnt: number of data nodes for bulk read
* @blk_cnt: number of data blocks including holes
* @oef: end of file reached
*/
struct bu_info {
union ubifs_key key;
struct ubifs_zbranch zbranch[UBIFS_MAX_BULK_READ];
void *buf;
int buf_len;
int gc_seq;
int cnt;
int blk_cnt;
int eof;
};
/**
* struct ubifs_node_range - node length range description data structure.
* @len: fixed node length
* @min_len: minimum possible node length
* @max_len: maximum possible node length
*
* If @max_len is %0, the node has fixed length @len.
*/
struct ubifs_node_range {
union {
int len;
int min_len;
};
int max_len;
};
/**
* struct ubifs_compressor - UBIFS compressor description structure.
* @compr_type: compressor type (%UBIFS_COMPR_LZO, etc)
* @cc: cryptoapi compressor handle
* @comp_mutex: mutex used during compression
* @decomp_mutex: mutex used during decompression
* @name: compressor name
* @capi_name: cryptoapi compressor name
*/
struct ubifs_compressor {
int compr_type;
struct crypto_comp *cc;
struct mutex *comp_mutex;
struct mutex *decomp_mutex;
const char *name;
const char *capi_name;
};
/**
* struct ubifs_budget_req - budget requirements of an operation.
*
* @fast: non-zero if the budgeting should try to acquire budget quickly and
* should not try to call write-back
* @recalculate: non-zero if @idx_growth, @data_growth, and @dd_growth fields
* have to be re-calculated
* @new_page: non-zero if the operation adds a new page
* @dirtied_page: non-zero if the operation makes a page dirty
* @new_dent: non-zero if the operation adds a new directory entry
* @mod_dent: non-zero if the operation removes or modifies an existing
* directory entry
* @new_ino: non-zero if the operation adds a new inode
* @new_ino_d: how much data newly created inode contains
* @dirtied_ino: how many inodes the operation makes dirty
* @dirtied_ino_d: how much data dirtied inode contains
* @idx_growth: how much the index will supposedly grow
* @data_growth: how much new data the operation will supposedly add
* @dd_growth: how much data that makes other data dirty the operation will
* supposedly add
*
* @idx_growth, @data_growth and @dd_growth are not used in budget request. The
* budgeting subsystem caches index and data growth values there to avoid
* re-calculating them when the budget is released. However, if @idx_growth is
* %-1, it is calculated by the release function using other fields.
*
* An inode may contain 4KiB of data at max., thus the widths of @new_ino_d
* is 13 bits, and @dirtied_ino_d - 15, because up to 4 inodes may be made
* dirty by the re-name operation.
*
* Note, UBIFS aligns node lengths to 8-bytes boundary, so the requester has to
* make sure the amount of inode data which contribute to @new_ino_d and
* @dirtied_ino_d fields are aligned.
*/
struct ubifs_budget_req {
unsigned int fast:1;
unsigned int recalculate:1;
#ifndef UBIFS_DEBUG
unsigned int new_page:1;
unsigned int dirtied_page:1;
unsigned int new_dent:1;
unsigned int mod_dent:1;
unsigned int new_ino:1;
unsigned int new_ino_d:13;
unsigned int dirtied_ino:4;
unsigned int dirtied_ino_d:15;
#else
/* Not bit-fields to check for overflows */
unsigned int new_page;
unsigned int dirtied_page;
unsigned int new_dent;
unsigned int mod_dent;
unsigned int new_ino;
unsigned int new_ino_d;
unsigned int dirtied_ino;
unsigned int dirtied_ino_d;
#endif
int idx_growth;
int data_growth;
int dd_growth;
};
/**
* struct ubifs_orphan - stores the inode number of an orphan.
* @rb: rb-tree node of rb-tree of orphans sorted by inode number
* @list: list head of list of orphans in order added
* @new_list: list head of list of orphans added since the last commit
* @cnext: next orphan to commit
* @dnext: next orphan to delete
* @inum: inode number
* @new: %1 => added since the last commit, otherwise %0
* @cmt: %1 => commit pending, otherwise %0
* @del: %1 => delete pending, otherwise %0
*/
struct ubifs_orphan {
struct rb_node rb;
struct list_head list;
struct list_head new_list;
struct ubifs_orphan *cnext;
struct ubifs_orphan *dnext;
ino_t inum;
unsigned new:1;
unsigned cmt:1;
unsigned del:1;
};
/**
* struct ubifs_mount_opts - UBIFS-specific mount options information.
* @unmount_mode: selected unmount mode (%0 default, %1 normal, %2 fast)
* @bulk_read: enable/disable bulk-reads (%0 default, %1 disable, %2 enable)
* @chk_data_crc: enable/disable CRC data checking when reading data nodes
* (%0 default, %1 disable, %2 enable)
* @override_compr: override default compressor (%0 - do not override and use
* superblock compressor, %1 - override and use compressor
* specified in @compr_type)
* @compr_type: compressor type to override the superblock compressor with
* (%UBIFS_COMPR_NONE, etc)
*/
struct ubifs_mount_opts {
unsigned int unmount_mode:2;
unsigned int bulk_read:2;
unsigned int chk_data_crc:2;
unsigned int override_compr:1;
unsigned int compr_type:2;
};
/**
* struct ubifs_budg_info - UBIFS budgeting information.
* @idx_growth: amount of bytes budgeted for index growth
* @data_growth: amount of bytes budgeted for cached data
* @dd_growth: amount of bytes budgeted for cached data that will make
* other data dirty
* @uncommitted_idx: amount of bytes were budgeted for growth of the index, but
* which still have to be taken into account because the index
* has not been committed so far
* @old_idx_sz: size of index on flash
* @min_idx_lebs: minimum number of LEBs required for the index
* @nospace: non-zero if the file-system does not have flash space (used as
* optimization)
* @nospace_rp: the same as @nospace, but additionally means that even reserved
* pool is full
* @page_budget: budget for a page (constant, never changed after mount)
* @inode_budget: budget for an inode (constant, never changed after mount)
* @dent_budget: budget for a directory entry (constant, never changed after
* mount)
*/
struct ubifs_budg_info {
long long idx_growth;
long long data_growth;
long long dd_growth;
long long uncommitted_idx;
unsigned long long old_idx_sz;
int min_idx_lebs;
unsigned int nospace:1;
unsigned int nospace_rp:1;
int page_budget;
int inode_budget;
int dent_budget;
};
struct ubifs_debug_info;
/**
* struct ubifs_info - UBIFS file-system description data structure
* (per-superblock).
* @vfs_sb: VFS @struct super_block object
*
* @highest_inum: highest used inode number
* @max_sqnum: current global sequence number
* @cmt_no: commit number of the last successfully completed commit, protected
* by @commit_sem
* @cnt_lock: protects @highest_inum and @max_sqnum counters
* @fmt_version: UBIFS on-flash format version
* @ro_compat_version: R/O compatibility version
* @uuid: UUID from super block
*
* @lhead_lnum: log head logical eraseblock number
* @lhead_offs: log head offset
* @ltail_lnum: log tail logical eraseblock number (offset is always 0)
* @log_mutex: protects the log, @lhead_lnum, @lhead_offs, @ltail_lnum, and
* @bud_bytes
* @min_log_bytes: minimum required number of bytes in the log
* @cmt_bud_bytes: used during commit to temporarily amount of bytes in
* committed buds
*
* @buds: tree of all buds indexed by bud LEB number
* @bud_bytes: how many bytes of flash is used by buds
* @buds_lock: protects the @buds tree, @bud_bytes, and per-journal head bud
* lists
* @jhead_cnt: count of journal heads
* @jheads: journal heads (head zero is base head)
* @max_bud_bytes: maximum number of bytes allowed in buds
* @bg_bud_bytes: number of bud bytes when background commit is initiated