1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. |
4 | * All Rights Reserved. |
5 | */ |
6 | #include "xfs.h" |
7 | #include "xfs_fs.h" |
8 | #include "xfs_shared.h" |
9 | #include "xfs_format.h" |
10 | #include "xfs_log_format.h" |
11 | #include "xfs_trans_resv.h" |
12 | #include "xfs_bit.h" |
13 | #include "xfs_mount.h" |
14 | #include "xfs_btree.h" |
15 | #include "xfs_btree_staging.h" |
16 | #include "xfs_ialloc.h" |
17 | #include "xfs_ialloc_btree.h" |
18 | #include "xfs_alloc.h" |
19 | #include "xfs_error.h" |
20 | #include "xfs_health.h" |
21 | #include "xfs_trace.h" |
22 | #include "xfs_trans.h" |
23 | #include "xfs_rmap.h" |
24 | #include "xfs_ag.h" |
25 | |
26 | static struct kmem_cache *xfs_inobt_cur_cache; |
27 | |
28 | STATIC int |
29 | xfs_inobt_get_minrecs( |
30 | struct xfs_btree_cur *cur, |
31 | int level) |
32 | { |
33 | return M_IGEO(cur->bc_mp)->inobt_mnr[level != 0]; |
34 | } |
35 | |
36 | STATIC struct xfs_btree_cur * |
37 | xfs_inobt_dup_cursor( |
38 | struct xfs_btree_cur *cur) |
39 | { |
40 | return xfs_inobt_init_cursor(pag: cur->bc_ag.pag, tp: cur->bc_tp, |
41 | agbp: cur->bc_ag.agbp); |
42 | } |
43 | |
44 | STATIC struct xfs_btree_cur * |
45 | xfs_finobt_dup_cursor( |
46 | struct xfs_btree_cur *cur) |
47 | { |
48 | return xfs_finobt_init_cursor(pag: cur->bc_ag.pag, tp: cur->bc_tp, |
49 | agbp: cur->bc_ag.agbp); |
50 | } |
51 | |
52 | STATIC void |
53 | xfs_inobt_set_root( |
54 | struct xfs_btree_cur *cur, |
55 | const union xfs_btree_ptr *nptr, |
56 | int inc) /* level change */ |
57 | { |
58 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
59 | struct xfs_agi *agi = agbp->b_addr; |
60 | |
61 | agi->agi_root = nptr->s; |
62 | be32_add_cpu(&agi->agi_level, inc); |
63 | xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL); |
64 | } |
65 | |
66 | STATIC void |
67 | xfs_finobt_set_root( |
68 | struct xfs_btree_cur *cur, |
69 | const union xfs_btree_ptr *nptr, |
70 | int inc) /* level change */ |
71 | { |
72 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
73 | struct xfs_agi *agi = agbp->b_addr; |
74 | |
75 | agi->agi_free_root = nptr->s; |
76 | be32_add_cpu(&agi->agi_free_level, inc); |
77 | xfs_ialloc_log_agi(cur->bc_tp, agbp, |
78 | XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL); |
79 | } |
80 | |
81 | /* Update the inode btree block counter for this btree. */ |
82 | static inline void |
83 | xfs_inobt_mod_blockcount( |
84 | struct xfs_btree_cur *cur, |
85 | int howmuch) |
86 | { |
87 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
88 | struct xfs_agi *agi = agbp->b_addr; |
89 | |
90 | if (!xfs_has_inobtcounts(cur->bc_mp)) |
91 | return; |
92 | |
93 | if (xfs_btree_is_fino(cur->bc_ops)) |
94 | be32_add_cpu(&agi->agi_fblocks, howmuch); |
95 | else |
96 | be32_add_cpu(&agi->agi_iblocks, howmuch); |
97 | xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_IBLOCKS); |
98 | } |
99 | |
100 | STATIC int |
101 | __xfs_inobt_alloc_block( |
102 | struct xfs_btree_cur *cur, |
103 | const union xfs_btree_ptr *start, |
104 | union xfs_btree_ptr *new, |
105 | int *stat, |
106 | enum xfs_ag_resv_type resv) |
107 | { |
108 | xfs_alloc_arg_t args; /* block allocation args */ |
109 | int error; /* error return value */ |
110 | xfs_agblock_t sbno = be32_to_cpu(start->s); |
111 | |
112 | memset(&args, 0, sizeof(args)); |
113 | args.tp = cur->bc_tp; |
114 | args.mp = cur->bc_mp; |
115 | args.pag = cur->bc_ag.pag; |
116 | args.oinfo = XFS_RMAP_OINFO_INOBT; |
117 | args.minlen = 1; |
118 | args.maxlen = 1; |
119 | args.prod = 1; |
120 | args.resv = resv; |
121 | |
122 | error = xfs_alloc_vextent_near_bno(&args, |
123 | XFS_AGB_TO_FSB(args.mp, args.pag->pag_agno, sbno)); |
124 | if (error) |
125 | return error; |
126 | |
127 | if (args.fsbno == NULLFSBLOCK) { |
128 | *stat = 0; |
129 | return 0; |
130 | } |
131 | ASSERT(args.len == 1); |
132 | |
133 | new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno)); |
134 | *stat = 1; |
135 | xfs_inobt_mod_blockcount(cur, howmuch: 1); |
136 | return 0; |
137 | } |
138 | |
139 | STATIC int |
140 | xfs_inobt_alloc_block( |
141 | struct xfs_btree_cur *cur, |
142 | const union xfs_btree_ptr *start, |
143 | union xfs_btree_ptr *new, |
144 | int *stat) |
145 | { |
146 | return __xfs_inobt_alloc_block(cur, start, new, stat, XFS_AG_RESV_NONE); |
147 | } |
148 | |
149 | STATIC int |
150 | xfs_finobt_alloc_block( |
151 | struct xfs_btree_cur *cur, |
152 | const union xfs_btree_ptr *start, |
153 | union xfs_btree_ptr *new, |
154 | int *stat) |
155 | { |
156 | if (cur->bc_mp->m_finobt_nores) |
157 | return xfs_inobt_alloc_block(cur, start, new, stat); |
158 | return __xfs_inobt_alloc_block(cur, start, new, stat, |
159 | XFS_AG_RESV_METADATA); |
160 | } |
161 | |
162 | STATIC int |
163 | __xfs_inobt_free_block( |
164 | struct xfs_btree_cur *cur, |
165 | struct xfs_buf *bp, |
166 | enum xfs_ag_resv_type resv) |
167 | { |
168 | xfs_fsblock_t fsbno; |
169 | |
170 | xfs_inobt_mod_blockcount(cur, howmuch: -1); |
171 | fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp)); |
172 | return xfs_free_extent_later(cur->bc_tp, fsbno, 1, |
173 | &XFS_RMAP_OINFO_INOBT, resv, false); |
174 | } |
175 | |
176 | STATIC int |
177 | xfs_inobt_free_block( |
178 | struct xfs_btree_cur *cur, |
179 | struct xfs_buf *bp) |
180 | { |
181 | return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_NONE); |
182 | } |
183 | |
184 | STATIC int |
185 | xfs_finobt_free_block( |
186 | struct xfs_btree_cur *cur, |
187 | struct xfs_buf *bp) |
188 | { |
189 | if (cur->bc_mp->m_finobt_nores) |
190 | return xfs_inobt_free_block(cur, bp); |
191 | return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_METADATA); |
192 | } |
193 | |
194 | STATIC int |
195 | xfs_inobt_get_maxrecs( |
196 | struct xfs_btree_cur *cur, |
197 | int level) |
198 | { |
199 | return M_IGEO(cur->bc_mp)->inobt_mxr[level != 0]; |
200 | } |
201 | |
202 | STATIC void |
203 | xfs_inobt_init_key_from_rec( |
204 | union xfs_btree_key *key, |
205 | const union xfs_btree_rec *rec) |
206 | { |
207 | key->inobt.ir_startino = rec->inobt.ir_startino; |
208 | } |
209 | |
210 | STATIC void |
211 | xfs_inobt_init_high_key_from_rec( |
212 | union xfs_btree_key *key, |
213 | const union xfs_btree_rec *rec) |
214 | { |
215 | __u32 x; |
216 | |
217 | x = be32_to_cpu(rec->inobt.ir_startino); |
218 | x += XFS_INODES_PER_CHUNK - 1; |
219 | key->inobt.ir_startino = cpu_to_be32(x); |
220 | } |
221 | |
222 | STATIC void |
223 | xfs_inobt_init_rec_from_cur( |
224 | struct xfs_btree_cur *cur, |
225 | union xfs_btree_rec *rec) |
226 | { |
227 | rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino); |
228 | if (xfs_has_sparseinodes(cur->bc_mp)) { |
229 | rec->inobt.ir_u.sp.ir_holemask = |
230 | cpu_to_be16(cur->bc_rec.i.ir_holemask); |
231 | rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count; |
232 | rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount; |
233 | } else { |
234 | /* ir_holemask/ir_count not supported on-disk */ |
235 | rec->inobt.ir_u.f.ir_freecount = |
236 | cpu_to_be32(cur->bc_rec.i.ir_freecount); |
237 | } |
238 | rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free); |
239 | } |
240 | |
241 | /* |
242 | * initial value of ptr for lookup |
243 | */ |
244 | STATIC void |
245 | xfs_inobt_init_ptr_from_cur( |
246 | struct xfs_btree_cur *cur, |
247 | union xfs_btree_ptr *ptr) |
248 | { |
249 | struct xfs_agi *agi = cur->bc_ag.agbp->b_addr; |
250 | |
251 | ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agi->agi_seqno)); |
252 | |
253 | ptr->s = agi->agi_root; |
254 | } |
255 | |
256 | STATIC void |
257 | xfs_finobt_init_ptr_from_cur( |
258 | struct xfs_btree_cur *cur, |
259 | union xfs_btree_ptr *ptr) |
260 | { |
261 | struct xfs_agi *agi = cur->bc_ag.agbp->b_addr; |
262 | |
263 | ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agi->agi_seqno)); |
264 | ptr->s = agi->agi_free_root; |
265 | } |
266 | |
267 | STATIC int64_t |
268 | xfs_inobt_key_diff( |
269 | struct xfs_btree_cur *cur, |
270 | const union xfs_btree_key *key) |
271 | { |
272 | return (int64_t)be32_to_cpu(key->inobt.ir_startino) - |
273 | cur->bc_rec.i.ir_startino; |
274 | } |
275 | |
276 | STATIC int64_t |
277 | xfs_inobt_diff_two_keys( |
278 | struct xfs_btree_cur *cur, |
279 | const union xfs_btree_key *k1, |
280 | const union xfs_btree_key *k2, |
281 | const union xfs_btree_key *mask) |
282 | { |
283 | ASSERT(!mask || mask->inobt.ir_startino); |
284 | |
285 | return (int64_t)be32_to_cpu(k1->inobt.ir_startino) - |
286 | be32_to_cpu(k2->inobt.ir_startino); |
287 | } |
288 | |
289 | static xfs_failaddr_t |
290 | xfs_inobt_verify( |
291 | struct xfs_buf *bp) |
292 | { |
293 | struct xfs_mount *mp = bp->b_mount; |
294 | struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); |
295 | xfs_failaddr_t fa; |
296 | unsigned int level; |
297 | |
298 | if (!xfs_verify_magic(bp, block->bb_magic)) |
299 | return __this_address; |
300 | |
301 | /* |
302 | * During growfs operations, we can't verify the exact owner as the |
303 | * perag is not fully initialised and hence not attached to the buffer. |
304 | * |
305 | * Similarly, during log recovery we will have a perag structure |
306 | * attached, but the agi information will not yet have been initialised |
307 | * from the on disk AGI. We don't currently use any of this information, |
308 | * but beware of the landmine (i.e. need to check |
309 | * xfs_perag_initialised_agi(pag)) if we ever do. |
310 | */ |
311 | if (xfs_has_crc(mp)) { |
312 | fa = xfs_btree_agblock_v5hdr_verify(bp); |
313 | if (fa) |
314 | return fa; |
315 | } |
316 | |
317 | /* level verification */ |
318 | level = be16_to_cpu(block->bb_level); |
319 | if (level >= M_IGEO(mp)->inobt_maxlevels) |
320 | return __this_address; |
321 | |
322 | return xfs_btree_agblock_verify(bp, |
323 | M_IGEO(mp)->inobt_mxr[level != 0]); |
324 | } |
325 | |
326 | static void |
327 | xfs_inobt_read_verify( |
328 | struct xfs_buf *bp) |
329 | { |
330 | xfs_failaddr_t fa; |
331 | |
332 | if (!xfs_btree_agblock_verify_crc(bp)) |
333 | xfs_verifier_error(bp, -EFSBADCRC, __this_address); |
334 | else { |
335 | fa = xfs_inobt_verify(bp); |
336 | if (fa) |
337 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); |
338 | } |
339 | |
340 | if (bp->b_error) |
341 | trace_xfs_btree_corrupt(bp, _RET_IP_); |
342 | } |
343 | |
344 | static void |
345 | xfs_inobt_write_verify( |
346 | struct xfs_buf *bp) |
347 | { |
348 | xfs_failaddr_t fa; |
349 | |
350 | fa = xfs_inobt_verify(bp); |
351 | if (fa) { |
352 | trace_xfs_btree_corrupt(bp, _RET_IP_); |
353 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); |
354 | return; |
355 | } |
356 | xfs_btree_agblock_calc_crc(bp); |
357 | |
358 | } |
359 | |
360 | const struct xfs_buf_ops xfs_inobt_buf_ops = { |
361 | .name = "xfs_inobt" , |
362 | .magic = { cpu_to_be32(XFS_IBT_MAGIC), cpu_to_be32(XFS_IBT_CRC_MAGIC) }, |
363 | .verify_read = xfs_inobt_read_verify, |
364 | .verify_write = xfs_inobt_write_verify, |
365 | .verify_struct = xfs_inobt_verify, |
366 | }; |
367 | |
368 | const struct xfs_buf_ops xfs_finobt_buf_ops = { |
369 | .name = "xfs_finobt" , |
370 | .magic = { cpu_to_be32(XFS_FIBT_MAGIC), |
371 | cpu_to_be32(XFS_FIBT_CRC_MAGIC) }, |
372 | .verify_read = xfs_inobt_read_verify, |
373 | .verify_write = xfs_inobt_write_verify, |
374 | .verify_struct = xfs_inobt_verify, |
375 | }; |
376 | |
377 | STATIC int |
378 | xfs_inobt_keys_inorder( |
379 | struct xfs_btree_cur *cur, |
380 | const union xfs_btree_key *k1, |
381 | const union xfs_btree_key *k2) |
382 | { |
383 | return be32_to_cpu(k1->inobt.ir_startino) < |
384 | be32_to_cpu(k2->inobt.ir_startino); |
385 | } |
386 | |
387 | STATIC int |
388 | xfs_inobt_recs_inorder( |
389 | struct xfs_btree_cur *cur, |
390 | const union xfs_btree_rec *r1, |
391 | const union xfs_btree_rec *r2) |
392 | { |
393 | return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <= |
394 | be32_to_cpu(r2->inobt.ir_startino); |
395 | } |
396 | |
397 | STATIC enum xbtree_key_contig |
398 | xfs_inobt_keys_contiguous( |
399 | struct xfs_btree_cur *cur, |
400 | const union xfs_btree_key *key1, |
401 | const union xfs_btree_key *key2, |
402 | const union xfs_btree_key *mask) |
403 | { |
404 | ASSERT(!mask || mask->inobt.ir_startino); |
405 | |
406 | return xbtree_key_contig(be32_to_cpu(key1->inobt.ir_startino), |
407 | be32_to_cpu(key2->inobt.ir_startino)); |
408 | } |
409 | |
410 | const struct xfs_btree_ops xfs_inobt_ops = { |
411 | .name = "ino" , |
412 | .type = XFS_BTREE_TYPE_AG, |
413 | |
414 | .rec_len = sizeof(xfs_inobt_rec_t), |
415 | .key_len = sizeof(xfs_inobt_key_t), |
416 | .ptr_len = XFS_BTREE_SHORT_PTR_LEN, |
417 | |
418 | .lru_refs = XFS_INO_BTREE_REF, |
419 | .statoff = XFS_STATS_CALC_INDEX(xs_ibt_2), |
420 | .sick_mask = XFS_SICK_AG_INOBT, |
421 | |
422 | .dup_cursor = xfs_inobt_dup_cursor, |
423 | .set_root = xfs_inobt_set_root, |
424 | .alloc_block = xfs_inobt_alloc_block, |
425 | .free_block = xfs_inobt_free_block, |
426 | .get_minrecs = xfs_inobt_get_minrecs, |
427 | .get_maxrecs = xfs_inobt_get_maxrecs, |
428 | .init_key_from_rec = xfs_inobt_init_key_from_rec, |
429 | .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec, |
430 | .init_rec_from_cur = xfs_inobt_init_rec_from_cur, |
431 | .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, |
432 | .key_diff = xfs_inobt_key_diff, |
433 | .buf_ops = &xfs_inobt_buf_ops, |
434 | .diff_two_keys = xfs_inobt_diff_two_keys, |
435 | .keys_inorder = xfs_inobt_keys_inorder, |
436 | .recs_inorder = xfs_inobt_recs_inorder, |
437 | .keys_contiguous = xfs_inobt_keys_contiguous, |
438 | }; |
439 | |
440 | const struct xfs_btree_ops xfs_finobt_ops = { |
441 | .name = "fino" , |
442 | .type = XFS_BTREE_TYPE_AG, |
443 | |
444 | .rec_len = sizeof(xfs_inobt_rec_t), |
445 | .key_len = sizeof(xfs_inobt_key_t), |
446 | .ptr_len = XFS_BTREE_SHORT_PTR_LEN, |
447 | |
448 | .lru_refs = XFS_INO_BTREE_REF, |
449 | .statoff = XFS_STATS_CALC_INDEX(xs_fibt_2), |
450 | .sick_mask = XFS_SICK_AG_FINOBT, |
451 | |
452 | .dup_cursor = xfs_finobt_dup_cursor, |
453 | .set_root = xfs_finobt_set_root, |
454 | .alloc_block = xfs_finobt_alloc_block, |
455 | .free_block = xfs_finobt_free_block, |
456 | .get_minrecs = xfs_inobt_get_minrecs, |
457 | .get_maxrecs = xfs_inobt_get_maxrecs, |
458 | .init_key_from_rec = xfs_inobt_init_key_from_rec, |
459 | .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec, |
460 | .init_rec_from_cur = xfs_inobt_init_rec_from_cur, |
461 | .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur, |
462 | .key_diff = xfs_inobt_key_diff, |
463 | .buf_ops = &xfs_finobt_buf_ops, |
464 | .diff_two_keys = xfs_inobt_diff_two_keys, |
465 | .keys_inorder = xfs_inobt_keys_inorder, |
466 | .recs_inorder = xfs_inobt_recs_inorder, |
467 | .keys_contiguous = xfs_inobt_keys_contiguous, |
468 | }; |
469 | |
470 | /* |
471 | * Create an inode btree cursor. |
472 | * |
473 | * For staging cursors tp and agbp are NULL. |
474 | */ |
475 | struct xfs_btree_cur * |
476 | xfs_inobt_init_cursor( |
477 | struct xfs_perag *pag, |
478 | struct xfs_trans *tp, |
479 | struct xfs_buf *agbp) |
480 | { |
481 | struct xfs_mount *mp = pag->pag_mount; |
482 | struct xfs_btree_cur *cur; |
483 | |
484 | cur = xfs_btree_alloc_cursor(mp, tp, &xfs_inobt_ops, |
485 | M_IGEO(mp)->inobt_maxlevels, xfs_inobt_cur_cache); |
486 | cur->bc_ag.pag = xfs_perag_hold(pag); |
487 | cur->bc_ag.agbp = agbp; |
488 | if (agbp) { |
489 | struct xfs_agi *agi = agbp->b_addr; |
490 | |
491 | cur->bc_nlevels = be32_to_cpu(agi->agi_level); |
492 | } |
493 | return cur; |
494 | } |
495 | |
496 | /* |
497 | * Create a free inode btree cursor. |
498 | * |
499 | * For staging cursors tp and agbp are NULL. |
500 | */ |
501 | struct xfs_btree_cur * |
502 | xfs_finobt_init_cursor( |
503 | struct xfs_perag *pag, |
504 | struct xfs_trans *tp, |
505 | struct xfs_buf *agbp) |
506 | { |
507 | struct xfs_mount *mp = pag->pag_mount; |
508 | struct xfs_btree_cur *cur; |
509 | |
510 | cur = xfs_btree_alloc_cursor(mp, tp, &xfs_finobt_ops, |
511 | M_IGEO(mp)->inobt_maxlevels, xfs_inobt_cur_cache); |
512 | cur->bc_ag.pag = xfs_perag_hold(pag); |
513 | cur->bc_ag.agbp = agbp; |
514 | if (agbp) { |
515 | struct xfs_agi *agi = agbp->b_addr; |
516 | |
517 | cur->bc_nlevels = be32_to_cpu(agi->agi_free_level); |
518 | } |
519 | return cur; |
520 | } |
521 | |
522 | /* |
523 | * Install a new inobt btree root. Caller is responsible for invalidating |
524 | * and freeing the old btree blocks. |
525 | */ |
526 | void |
527 | xfs_inobt_commit_staged_btree( |
528 | struct xfs_btree_cur *cur, |
529 | struct xfs_trans *tp, |
530 | struct xfs_buf *agbp) |
531 | { |
532 | struct xfs_agi *agi = agbp->b_addr; |
533 | struct xbtree_afakeroot *afake = cur->bc_ag.afake; |
534 | int fields; |
535 | |
536 | ASSERT(cur->bc_flags & XFS_BTREE_STAGING); |
537 | |
538 | if (xfs_btree_is_ino(cur->bc_ops)) { |
539 | fields = XFS_AGI_ROOT | XFS_AGI_LEVEL; |
540 | agi->agi_root = cpu_to_be32(afake->af_root); |
541 | agi->agi_level = cpu_to_be32(afake->af_levels); |
542 | if (xfs_has_inobtcounts(cur->bc_mp)) { |
543 | agi->agi_iblocks = cpu_to_be32(afake->af_blocks); |
544 | fields |= XFS_AGI_IBLOCKS; |
545 | } |
546 | xfs_ialloc_log_agi(tp, agbp, fields); |
547 | xfs_btree_commit_afakeroot(cur, tp, agbp); |
548 | } else { |
549 | fields = XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL; |
550 | agi->agi_free_root = cpu_to_be32(afake->af_root); |
551 | agi->agi_free_level = cpu_to_be32(afake->af_levels); |
552 | if (xfs_has_inobtcounts(cur->bc_mp)) { |
553 | agi->agi_fblocks = cpu_to_be32(afake->af_blocks); |
554 | fields |= XFS_AGI_IBLOCKS; |
555 | } |
556 | xfs_ialloc_log_agi(tp, agbp, fields); |
557 | xfs_btree_commit_afakeroot(cur, tp, agbp); |
558 | } |
559 | } |
560 | |
561 | /* Calculate number of records in an inode btree block. */ |
562 | static inline unsigned int |
563 | xfs_inobt_block_maxrecs( |
564 | unsigned int blocklen, |
565 | bool leaf) |
566 | { |
567 | if (leaf) |
568 | return blocklen / sizeof(xfs_inobt_rec_t); |
569 | return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); |
570 | } |
571 | |
572 | /* |
573 | * Calculate number of records in an inobt btree block. |
574 | */ |
575 | int |
576 | xfs_inobt_maxrecs( |
577 | struct xfs_mount *mp, |
578 | int blocklen, |
579 | int leaf) |
580 | { |
581 | blocklen -= XFS_INOBT_BLOCK_LEN(mp); |
582 | return xfs_inobt_block_maxrecs(blocklen, leaf); |
583 | } |
584 | |
585 | /* |
586 | * Maximum number of inode btree records per AG. Pretend that we can fill an |
587 | * entire AG completely full of inodes except for the AG headers. |
588 | */ |
589 | #define XFS_MAX_INODE_RECORDS \ |
590 | ((XFS_MAX_AG_BYTES - (4 * BBSIZE)) / XFS_DINODE_MIN_SIZE) / \ |
591 | XFS_INODES_PER_CHUNK |
592 | |
593 | /* Compute the max possible height for the inode btree. */ |
594 | static inline unsigned int |
595 | xfs_inobt_maxlevels_ondisk(void) |
596 | { |
597 | unsigned int minrecs[2]; |
598 | unsigned int blocklen; |
599 | |
600 | blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, |
601 | XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN); |
602 | |
603 | minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2; |
604 | minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2; |
605 | |
606 | return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS); |
607 | } |
608 | |
609 | /* Compute the max possible height for the free inode btree. */ |
610 | static inline unsigned int |
611 | xfs_finobt_maxlevels_ondisk(void) |
612 | { |
613 | unsigned int minrecs[2]; |
614 | unsigned int blocklen; |
615 | |
616 | blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN; |
617 | |
618 | minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2; |
619 | minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2; |
620 | |
621 | return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS); |
622 | } |
623 | |
624 | /* Compute the max possible height for either inode btree. */ |
625 | unsigned int |
626 | xfs_iallocbt_maxlevels_ondisk(void) |
627 | { |
628 | return max(xfs_inobt_maxlevels_ondisk(), |
629 | xfs_finobt_maxlevels_ondisk()); |
630 | } |
631 | |
632 | /* |
633 | * Convert the inode record holemask to an inode allocation bitmap. The inode |
634 | * allocation bitmap is inode granularity and specifies whether an inode is |
635 | * physically allocated on disk (not whether the inode is considered allocated |
636 | * or free by the fs). |
637 | * |
638 | * A bit value of 1 means the inode is allocated, a value of 0 means it is free. |
639 | */ |
640 | uint64_t |
641 | xfs_inobt_irec_to_allocmask( |
642 | const struct xfs_inobt_rec_incore *rec) |
643 | { |
644 | uint64_t bitmap = 0; |
645 | uint64_t inodespbit; |
646 | int nextbit; |
647 | uint allocbitmap; |
648 | |
649 | /* |
650 | * The holemask has 16-bits for a 64 inode record. Therefore each |
651 | * holemask bit represents multiple inodes. Create a mask of bits to set |
652 | * in the allocmask for each holemask bit. |
653 | */ |
654 | inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1; |
655 | |
656 | /* |
657 | * Allocated inodes are represented by 0 bits in holemask. Invert the 0 |
658 | * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask |
659 | * anything beyond the 16 holemask bits since this casts to a larger |
660 | * type. |
661 | */ |
662 | allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1); |
663 | |
664 | /* |
665 | * allocbitmap is the inverted holemask so every set bit represents |
666 | * allocated inodes. To expand from 16-bit holemask granularity to |
667 | * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target |
668 | * bitmap for every holemask bit. |
669 | */ |
670 | nextbit = xfs_next_bit(&allocbitmap, 1, 0); |
671 | while (nextbit != -1) { |
672 | ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY)); |
673 | |
674 | bitmap |= (inodespbit << |
675 | (nextbit * XFS_INODES_PER_HOLEMASK_BIT)); |
676 | |
677 | nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1); |
678 | } |
679 | |
680 | return bitmap; |
681 | } |
682 | |
683 | #if defined(DEBUG) || defined(XFS_WARN) |
684 | /* |
685 | * Verify that an in-core inode record has a valid inode count. |
686 | */ |
687 | int |
688 | xfs_inobt_rec_check_count( |
689 | struct xfs_mount *mp, |
690 | struct xfs_inobt_rec_incore *rec) |
691 | { |
692 | int inocount = 0; |
693 | int nextbit = 0; |
694 | uint64_t allocbmap; |
695 | int wordsz; |
696 | |
697 | wordsz = sizeof(allocbmap) / sizeof(unsigned int); |
698 | allocbmap = xfs_inobt_irec_to_allocmask(rec); |
699 | |
700 | nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit); |
701 | while (nextbit != -1) { |
702 | inocount++; |
703 | nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, |
704 | nextbit + 1); |
705 | } |
706 | |
707 | if (inocount != rec->ir_count) |
708 | return -EFSCORRUPTED; |
709 | |
710 | return 0; |
711 | } |
712 | #endif /* DEBUG */ |
713 | |
714 | static xfs_extlen_t |
715 | xfs_inobt_max_size( |
716 | struct xfs_perag *pag) |
717 | { |
718 | struct xfs_mount *mp = pag->pag_mount; |
719 | xfs_agblock_t agblocks = pag->block_count; |
720 | |
721 | /* Bail out if we're uninitialized, which can happen in mkfs. */ |
722 | if (M_IGEO(mp)->inobt_mxr[0] == 0) |
723 | return 0; |
724 | |
725 | /* |
726 | * The log is permanently allocated, so the space it occupies will |
727 | * never be available for the kinds of things that would require btree |
728 | * expansion. We therefore can pretend the space isn't there. |
729 | */ |
730 | if (xfs_ag_contains_log(mp, pag->pag_agno)) |
731 | agblocks -= mp->m_sb.sb_logblocks; |
732 | |
733 | return xfs_btree_calc_size(M_IGEO(mp)->inobt_mnr, |
734 | (uint64_t)agblocks * mp->m_sb.sb_inopblock / |
735 | XFS_INODES_PER_CHUNK); |
736 | } |
737 | |
738 | static int |
739 | xfs_finobt_count_blocks( |
740 | struct xfs_perag *pag, |
741 | struct xfs_trans *tp, |
742 | xfs_extlen_t *tree_blocks) |
743 | { |
744 | struct xfs_buf *agbp = NULL; |
745 | struct xfs_btree_cur *cur; |
746 | int error; |
747 | |
748 | error = xfs_ialloc_read_agi(pag, tp, agibpp: &agbp); |
749 | if (error) |
750 | return error; |
751 | |
752 | cur = xfs_inobt_init_cursor(pag, tp, agbp); |
753 | error = xfs_btree_count_blocks(cur, tree_blocks); |
754 | xfs_btree_del_cursor(cur, error); |
755 | xfs_trans_brelse(tp, agbp); |
756 | |
757 | return error; |
758 | } |
759 | |
760 | /* Read finobt block count from AGI header. */ |
761 | static int |
762 | xfs_finobt_read_blocks( |
763 | struct xfs_perag *pag, |
764 | struct xfs_trans *tp, |
765 | xfs_extlen_t *tree_blocks) |
766 | { |
767 | struct xfs_buf *agbp; |
768 | struct xfs_agi *agi; |
769 | int error; |
770 | |
771 | error = xfs_ialloc_read_agi(pag, tp, agibpp: &agbp); |
772 | if (error) |
773 | return error; |
774 | |
775 | agi = agbp->b_addr; |
776 | *tree_blocks = be32_to_cpu(agi->agi_fblocks); |
777 | xfs_trans_brelse(tp, agbp); |
778 | return 0; |
779 | } |
780 | |
781 | /* |
782 | * Figure out how many blocks to reserve and how many are used by this btree. |
783 | */ |
784 | int |
785 | xfs_finobt_calc_reserves( |
786 | struct xfs_perag *pag, |
787 | struct xfs_trans *tp, |
788 | xfs_extlen_t *ask, |
789 | xfs_extlen_t *used) |
790 | { |
791 | xfs_extlen_t tree_len = 0; |
792 | int error; |
793 | |
794 | if (!xfs_has_finobt(pag->pag_mount)) |
795 | return 0; |
796 | |
797 | if (xfs_has_inobtcounts(pag->pag_mount)) |
798 | error = xfs_finobt_read_blocks(pag, tp, &tree_len); |
799 | else |
800 | error = xfs_finobt_count_blocks(pag, tp, &tree_len); |
801 | if (error) |
802 | return error; |
803 | |
804 | *ask += xfs_inobt_max_size(pag); |
805 | *used += tree_len; |
806 | return 0; |
807 | } |
808 | |
809 | /* Calculate the inobt btree size for some records. */ |
810 | xfs_extlen_t |
811 | xfs_iallocbt_calc_size( |
812 | struct xfs_mount *mp, |
813 | unsigned long long len) |
814 | { |
815 | return xfs_btree_calc_size(limits: M_IGEO(mp)->inobt_mnr, records: len); |
816 | } |
817 | |
818 | int __init |
819 | xfs_inobt_init_cur_cache(void) |
820 | { |
821 | xfs_inobt_cur_cache = kmem_cache_create("xfs_inobt_cur" , |
822 | xfs_btree_cur_sizeof(xfs_inobt_maxlevels_ondisk()), |
823 | 0, 0, NULL); |
824 | |
825 | if (!xfs_inobt_cur_cache) |
826 | return -ENOMEM; |
827 | return 0; |
828 | } |
829 | |
830 | void |
831 | xfs_inobt_destroy_cur_cache(void) |
832 | { |
833 | kmem_cache_destroy(xfs_inobt_cur_cache); |
834 | xfs_inobt_cur_cache = NULL; |
835 | } |
836 | |