1/* SPDX-License-Identifier: GPL-2.0 */
2/*
3 * fs/f2fs/node.h
4 *
5 * Copyright (c) 2012 Samsung Electronics Co., Ltd.
6 * http://www.samsung.com/
7 */
8/* start node id of a node block dedicated to the given node id */
9#define START_NID(nid) (((nid) / NAT_ENTRY_PER_BLOCK) * NAT_ENTRY_PER_BLOCK)
10
11/* node block offset on the NAT area dedicated to the given start node id */
12#define NAT_BLOCK_OFFSET(start_nid) ((start_nid) / NAT_ENTRY_PER_BLOCK)
13
14/* # of pages to perform synchronous readahead before building free nids */
15#define FREE_NID_PAGES 8
16#define MAX_FREE_NIDS (NAT_ENTRY_PER_BLOCK * FREE_NID_PAGES)
17
18/* size of free nid batch when shrinking */
19#define SHRINK_NID_BATCH_SIZE 8
20
21#define DEF_RA_NID_PAGES 0 /* # of nid pages to be readaheaded */
22
23/* maximum readahead size for node during getting data blocks */
24#define MAX_RA_NODE 128
25
26/* control the memory footprint threshold (10MB per 1GB ram) */
27#define DEF_RAM_THRESHOLD 1
28
29/* control dirty nats ratio threshold (default: 10% over max nid count) */
30#define DEF_DIRTY_NAT_RATIO_THRESHOLD 10
31/* control total # of nats */
32#define DEF_NAT_CACHE_THRESHOLD 100000
33
34/* control total # of node writes used for roll-fowrad recovery */
35#define DEF_RF_NODE_BLOCKS 0
36
37/* vector size for gang look-up from nat cache that consists of radix tree */
38#define NAT_VEC_SIZE 32
39
40/* return value for read_node_page */
41#define LOCKED_PAGE 1
42
43/* check pinned file's alignment status of physical blocks */
44#define FILE_NOT_ALIGNED 1
45
46/* For flag in struct node_info */
47enum {
48 IS_CHECKPOINTED, /* is it checkpointed before? */
49 HAS_FSYNCED_INODE, /* is the inode fsynced before? */
50 HAS_LAST_FSYNC, /* has the latest node fsync mark? */
51 IS_DIRTY, /* this nat entry is dirty? */
52 IS_PREALLOC, /* nat entry is preallocated */
53};
54
55/* For node type in __get_node_folio() */
56enum node_type {
57 NODE_TYPE_REGULAR,
58 NODE_TYPE_INODE,
59 NODE_TYPE_XATTR,
60};
61
62/*
63 * For node information
64 */
65struct node_info {
66 nid_t nid; /* node id */
67 nid_t ino; /* inode number of the node's owner */
68 block_t blk_addr; /* block address of the node */
69 unsigned char version; /* version of the node */
70 unsigned char flag; /* for node information bits */
71};
72
73struct nat_entry {
74 struct list_head list; /* for clean or dirty nat list */
75 struct node_info ni; /* in-memory node information */
76};
77
78#define nat_get_nid(nat) ((nat)->ni.nid)
79#define nat_set_nid(nat, n) ((nat)->ni.nid = (n))
80#define nat_get_blkaddr(nat) ((nat)->ni.blk_addr)
81#define nat_set_blkaddr(nat, b) ((nat)->ni.blk_addr = (b))
82#define nat_get_ino(nat) ((nat)->ni.ino)
83#define nat_set_ino(nat, i) ((nat)->ni.ino = (i))
84#define nat_get_version(nat) ((nat)->ni.version)
85#define nat_set_version(nat, v) ((nat)->ni.version = (v))
86
87#define inc_node_version(version) (++(version))
88
89static inline void copy_node_info(struct node_info *dst,
90 struct node_info *src)
91{
92 dst->nid = src->nid;
93 dst->ino = src->ino;
94 dst->blk_addr = src->blk_addr;
95 dst->version = src->version;
96 /* should not copy flag here */
97}
98
99static inline void set_nat_flag(struct nat_entry *ne,
100 unsigned int type, bool set)
101{
102 if (set)
103 ne->ni.flag |= BIT(type);
104 else
105 ne->ni.flag &= ~BIT(type);
106}
107
108static inline bool get_nat_flag(struct nat_entry *ne, unsigned int type)
109{
110 return ne->ni.flag & BIT(type);
111}
112
113static inline void nat_reset_flag(struct nat_entry *ne)
114{
115 /* these states can be set only after checkpoint was done */
116 set_nat_flag(ne, type: IS_CHECKPOINTED, set: true);
117 set_nat_flag(ne, type: HAS_FSYNCED_INODE, set: false);
118 set_nat_flag(ne, type: HAS_LAST_FSYNC, set: true);
119}
120
121static inline void node_info_from_raw_nat(struct node_info *ni,
122 struct f2fs_nat_entry *raw_ne)
123{
124 ni->ino = le32_to_cpu(raw_ne->ino);
125 ni->blk_addr = le32_to_cpu(raw_ne->block_addr);
126 ni->version = raw_ne->version;
127}
128
129static inline void raw_nat_from_node_info(struct f2fs_nat_entry *raw_ne,
130 struct node_info *ni)
131{
132 raw_ne->ino = cpu_to_le32(ni->ino);
133 raw_ne->block_addr = cpu_to_le32(ni->blk_addr);
134 raw_ne->version = ni->version;
135}
136
137static inline bool excess_dirty_nats(struct f2fs_sb_info *sbi)
138{
139 return NM_I(sbi)->nat_cnt[DIRTY_NAT] >= NM_I(sbi)->max_nid *
140 NM_I(sbi)->dirty_nats_ratio / 100;
141}
142
143static inline bool excess_cached_nats(struct f2fs_sb_info *sbi)
144{
145 return NM_I(sbi)->nat_cnt[TOTAL_NAT] >= DEF_NAT_CACHE_THRESHOLD;
146}
147
148enum mem_type {
149 FREE_NIDS, /* indicates the free nid list */
150 NAT_ENTRIES, /* indicates the cached nat entry */
151 DIRTY_DENTS, /* indicates dirty dentry pages */
152 INO_ENTRIES, /* indicates inode entries */
153 READ_EXTENT_CACHE, /* indicates read extent cache */
154 AGE_EXTENT_CACHE, /* indicates age extent cache */
155 DISCARD_CACHE, /* indicates memory of cached discard cmds */
156 COMPRESS_PAGE, /* indicates memory of cached compressed pages */
157 BASE_CHECK, /* check kernel status */
158};
159
160struct nat_entry_set {
161 struct list_head set_list; /* link with other nat sets */
162 struct list_head entry_list; /* link with dirty nat entries */
163 nid_t set; /* set number*/
164 unsigned int entry_cnt; /* the # of nat entries in set */
165};
166
167struct free_nid {
168 struct list_head list; /* for free node id list */
169 nid_t nid; /* node id */
170 int state; /* in use or not: FREE_NID or PREALLOC_NID */
171};
172
173static inline void next_free_nid(struct f2fs_sb_info *sbi, nid_t *nid)
174{
175 struct f2fs_nm_info *nm_i = NM_I(sbi);
176 struct free_nid *fnid;
177
178 spin_lock(lock: &nm_i->nid_list_lock);
179 if (nm_i->nid_cnt[FREE_NID] <= 0) {
180 spin_unlock(lock: &nm_i->nid_list_lock);
181 return;
182 }
183 fnid = list_first_entry(&nm_i->free_nid_list, struct free_nid, list);
184 *nid = fnid->nid;
185 spin_unlock(lock: &nm_i->nid_list_lock);
186}
187
188/*
189 * inline functions
190 */
191static inline void get_nat_bitmap(struct f2fs_sb_info *sbi, void *addr)
192{
193 struct f2fs_nm_info *nm_i = NM_I(sbi);
194
195#ifdef CONFIG_F2FS_CHECK_FS
196 if (memcmp(p: nm_i->nat_bitmap, q: nm_i->nat_bitmap_mir,
197 size: nm_i->bitmap_size))
198 f2fs_bug_on(sbi, 1);
199#endif
200 memcpy(addr, nm_i->nat_bitmap, nm_i->bitmap_size);
201}
202
203static inline pgoff_t current_nat_addr(struct f2fs_sb_info *sbi, nid_t start)
204{
205 struct f2fs_nm_info *nm_i = NM_I(sbi);
206 pgoff_t block_off;
207 pgoff_t block_addr;
208
209 /*
210 * block_off = segment_off * 512 + off_in_segment
211 * OLD = (segment_off * 512) * 2 + off_in_segment
212 * NEW = 2 * (segment_off * 512 + off_in_segment) - off_in_segment
213 */
214 block_off = NAT_BLOCK_OFFSET(start);
215
216 block_addr = (pgoff_t)(nm_i->nat_blkaddr +
217 (block_off << 1) -
218 (block_off & (BLKS_PER_SEG(sbi) - 1)));
219
220 if (f2fs_test_bit(nr: block_off, addr: nm_i->nat_bitmap))
221 block_addr += BLKS_PER_SEG(sbi);
222
223 return block_addr;
224}
225
226static inline pgoff_t next_nat_addr(struct f2fs_sb_info *sbi,
227 pgoff_t block_addr)
228{
229 struct f2fs_nm_info *nm_i = NM_I(sbi);
230
231 block_addr -= nm_i->nat_blkaddr;
232 block_addr ^= BIT(sbi->log_blocks_per_seg);
233 return block_addr + nm_i->nat_blkaddr;
234}
235
236static inline void set_to_next_nat(struct f2fs_nm_info *nm_i, nid_t start_nid)
237{
238 unsigned int block_off = NAT_BLOCK_OFFSET(start_nid);
239
240 f2fs_change_bit(nr: block_off, addr: nm_i->nat_bitmap);
241#ifdef CONFIG_F2FS_CHECK_FS
242 f2fs_change_bit(nr: block_off, addr: nm_i->nat_bitmap_mir);
243#endif
244}
245
246static inline nid_t ino_of_node(struct page *node_page)
247{
248 struct f2fs_node *rn = F2FS_NODE(page: node_page);
249 return le32_to_cpu(rn->footer.ino);
250}
251
252static inline nid_t nid_of_node(struct page *node_page)
253{
254 struct f2fs_node *rn = F2FS_NODE(page: node_page);
255 return le32_to_cpu(rn->footer.nid);
256}
257
258static inline unsigned int ofs_of_node(const struct page *node_page)
259{
260 struct f2fs_node *rn = F2FS_NODE(page: node_page);
261 unsigned flag = le32_to_cpu(rn->footer.flag);
262 return flag >> OFFSET_BIT_SHIFT;
263}
264
265static inline __u64 cpver_of_node(struct page *node_page)
266{
267 struct f2fs_node *rn = F2FS_NODE(page: node_page);
268 return le64_to_cpu(rn->footer.cp_ver);
269}
270
271static inline block_t next_blkaddr_of_node(struct folio *node_folio)
272{
273 struct f2fs_node *rn = F2FS_NODE(page: &node_folio->page);
274 return le32_to_cpu(rn->footer.next_blkaddr);
275}
276
277static inline void fill_node_footer(struct page *page, nid_t nid,
278 nid_t ino, unsigned int ofs, bool reset)
279{
280 struct f2fs_node *rn = F2FS_NODE(page);
281 unsigned int old_flag = 0;
282
283 if (reset)
284 memset(rn, 0, sizeof(*rn));
285 else
286 old_flag = le32_to_cpu(rn->footer.flag);
287
288 rn->footer.nid = cpu_to_le32(nid);
289 rn->footer.ino = cpu_to_le32(ino);
290
291 /* should remain old flag bits such as COLD_BIT_SHIFT */
292 rn->footer.flag = cpu_to_le32((ofs << OFFSET_BIT_SHIFT) |
293 (old_flag & OFFSET_BIT_MASK));
294}
295
296static inline void copy_node_footer(struct page *dst, struct page *src)
297{
298 struct f2fs_node *src_rn = F2FS_NODE(page: src);
299 struct f2fs_node *dst_rn = F2FS_NODE(page: dst);
300 memcpy(&dst_rn->footer, &src_rn->footer, sizeof(struct node_footer));
301}
302
303static inline void fill_node_footer_blkaddr(struct page *page, block_t blkaddr)
304{
305 struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi: F2FS_P_SB(page));
306 struct f2fs_node *rn = F2FS_NODE(page);
307 __u64 cp_ver = cur_cp_version(cp: ckpt);
308
309 if (__is_set_ckpt_flags(cp: ckpt, CP_CRC_RECOVERY_FLAG))
310 cp_ver |= (cur_cp_crc(cp: ckpt) << 32);
311
312 rn->footer.cp_ver = cpu_to_le64(cp_ver);
313 rn->footer.next_blkaddr = cpu_to_le32(blkaddr);
314}
315
316static inline bool is_recoverable_dnode(struct page *page)
317{
318 struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi: F2FS_P_SB(page));
319 __u64 cp_ver = cur_cp_version(cp: ckpt);
320
321 /* Don't care crc part, if fsck.f2fs sets it. */
322 if (__is_set_ckpt_flags(cp: ckpt, CP_NOCRC_RECOVERY_FLAG))
323 return (cp_ver << 32) == (cpver_of_node(node_page: page) << 32);
324
325 if (__is_set_ckpt_flags(cp: ckpt, CP_CRC_RECOVERY_FLAG))
326 cp_ver |= (cur_cp_crc(cp: ckpt) << 32);
327
328 return cp_ver == cpver_of_node(node_page: page);
329}
330
331/*
332 * f2fs assigns the following node offsets described as (num).
333 * N = NIDS_PER_BLOCK
334 *
335 * Inode block (0)
336 * |- direct node (1)
337 * |- direct node (2)
338 * |- indirect node (3)
339 * | `- direct node (4 => 4 + N - 1)
340 * |- indirect node (4 + N)
341 * | `- direct node (5 + N => 5 + 2N - 1)
342 * `- double indirect node (5 + 2N)
343 * `- indirect node (6 + 2N)
344 * `- direct node
345 * ......
346 * `- indirect node ((6 + 2N) + x(N + 1))
347 * `- direct node
348 * ......
349 * `- indirect node ((6 + 2N) + (N - 1)(N + 1))
350 * `- direct node
351 */
352static inline bool IS_DNODE(const struct page *node_page)
353{
354 unsigned int ofs = ofs_of_node(node_page);
355
356 if (f2fs_has_xattr_block(ofs))
357 return true;
358
359 if (ofs == 3 || ofs == 4 + NIDS_PER_BLOCK ||
360 ofs == 5 + 2 * NIDS_PER_BLOCK)
361 return false;
362 if (ofs >= 6 + 2 * NIDS_PER_BLOCK) {
363 ofs -= 6 + 2 * NIDS_PER_BLOCK;
364 if (!((long int)ofs % (NIDS_PER_BLOCK + 1)))
365 return false;
366 }
367 return true;
368}
369
370static inline int set_nid(struct folio *folio, int off, nid_t nid, bool i)
371{
372 struct f2fs_node *rn = F2FS_NODE(page: &folio->page);
373
374 f2fs_folio_wait_writeback(folio, type: NODE, ordered: true, locked: true);
375
376 if (i)
377 rn->i.i_nid[off - NODE_DIR1_BLOCK] = cpu_to_le32(nid);
378 else
379 rn->in.nid[off] = cpu_to_le32(nid);
380 return folio_mark_dirty(folio);
381}
382
383static inline nid_t get_nid(struct page *p, int off, bool i)
384{
385 struct f2fs_node *rn = F2FS_NODE(page: p);
386
387 if (i)
388 return le32_to_cpu(rn->i.i_nid[off - NODE_DIR1_BLOCK]);
389 return le32_to_cpu(rn->in.nid[off]);
390}
391
392/*
393 * Coldness identification:
394 * - Mark cold files in f2fs_inode_info
395 * - Mark cold node blocks in their node footer
396 * - Mark cold data pages in page cache
397 */
398
399static inline int is_node(const struct page *page, int type)
400{
401 struct f2fs_node *rn = F2FS_NODE(page);
402 return le32_to_cpu(rn->footer.flag) & BIT(type);
403}
404
405#define is_cold_node(page) is_node(page, COLD_BIT_SHIFT)
406#define is_fsync_dnode(page) is_node(page, FSYNC_BIT_SHIFT)
407#define is_dent_dnode(page) is_node(page, DENT_BIT_SHIFT)
408
409static inline void set_cold_node(struct page *page, bool is_dir)
410{
411 struct f2fs_node *rn = F2FS_NODE(page);
412 unsigned int flag = le32_to_cpu(rn->footer.flag);
413
414 if (is_dir)
415 flag &= ~BIT(COLD_BIT_SHIFT);
416 else
417 flag |= BIT(COLD_BIT_SHIFT);
418 rn->footer.flag = cpu_to_le32(flag);
419}
420
421static inline void set_mark(struct page *page, int mark, int type)
422{
423 struct f2fs_node *rn = F2FS_NODE(page);
424 unsigned int flag = le32_to_cpu(rn->footer.flag);
425 if (mark)
426 flag |= BIT(type);
427 else
428 flag &= ~BIT(type);
429 rn->footer.flag = cpu_to_le32(flag);
430
431#ifdef CONFIG_F2FS_CHECK_FS
432 f2fs_inode_chksum_set(sbi: F2FS_P_SB(page), page);
433#endif
434}
435#define set_dentry_mark(page, mark) set_mark(page, mark, DENT_BIT_SHIFT)
436#define set_fsync_mark(page, mark) set_mark(page, mark, FSYNC_BIT_SHIFT)
437

source code of linux/fs/f2fs/node.h