]>
Commit | Line | Data |
---|---|---|
37b3b4d6 | 1 | // SPDX-License-Identifier: GPL-2.0 |
2bd0ea18 | 2 | /* |
da23017d NS |
3 | * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. |
4 | * All Rights Reserved. | |
2bd0ea18 | 5 | */ |
9c799827 | 6 | #include "libxfs_priv.h" |
b626fb59 DC |
7 | #include "xfs_fs.h" |
8 | #include "xfs_shared.h" | |
9 | #include "xfs_format.h" | |
2cf10e4c | 10 | #include "xfs_log_format.h" |
b626fb59 | 11 | #include "xfs_trans_resv.h" |
b626fb59 DC |
12 | #include "xfs_mount.h" |
13 | #include "xfs_btree.h" | |
7bc27889 | 14 | #include "xfs_btree_staging.h" |
b626fb59 DC |
15 | #include "xfs_alloc_btree.h" |
16 | #include "xfs_alloc.h" | |
17 | #include "xfs_trace.h" | |
2cf10e4c | 18 | #include "xfs_trans.h" |
f93d2173 | 19 | #include "xfs_ag.h" |
b626fb59 | 20 | |
5c35b317 | 21 | static struct kmem_cache *xfs_allocbt_cur_cache; |
2bd0ea18 | 22 | |
b194c7d8 BN |
23 | STATIC struct xfs_btree_cur * |
24 | xfs_allocbt_dup_cursor( | |
25 | struct xfs_btree_cur *cur) | |
2bd0ea18 | 26 | { |
b194c7d8 | 27 | return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp, |
ecb44e84 | 28 | cur->bc_ag.agbp, cur->bc_ag.pag, cur->bc_btnum); |
2bd0ea18 NS |
29 | } |
30 | ||
2bd0ea18 | 31 | STATIC void |
b194c7d8 | 32 | xfs_allocbt_set_root( |
67e6075e DW |
33 | struct xfs_btree_cur *cur, |
34 | const union xfs_btree_ptr *ptr, | |
35 | int inc) | |
2bd0ea18 | 36 | { |
aa6fa37f | 37 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
0bc284c2 | 38 | struct xfs_agf *agf = agbp->b_addr; |
b194c7d8 | 39 | int btnum = cur->bc_btnum; |
2bd0ea18 | 40 | |
b194c7d8 | 41 | ASSERT(ptr->s != 0); |
2bd0ea18 | 42 | |
b194c7d8 BN |
43 | agf->agf_roots[btnum] = ptr->s; |
44 | be32_add_cpu(&agf->agf_levels[btnum], inc); | |
ecb44e84 | 45 | cur->bc_ag.pag->pagf_levels[btnum] += inc; |
2bd0ea18 | 46 | |
b194c7d8 | 47 | xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); |
2bd0ea18 NS |
48 | } |
49 | ||
b194c7d8 BN |
50 | STATIC int |
51 | xfs_allocbt_alloc_block( | |
43cbf380 DW |
52 | struct xfs_btree_cur *cur, |
53 | const union xfs_btree_ptr *start, | |
54 | union xfs_btree_ptr *new, | |
55 | int *stat) | |
2bd0ea18 | 56 | { |
b194c7d8 BN |
57 | int error; |
58 | xfs_agblock_t bno; | |
2bd0ea18 | 59 | |
b194c7d8 | 60 | /* Allocate the new block from the freelist. If we can't, give up. */ |
1d202c10 DC |
61 | error = xfs_alloc_get_freelist(cur->bc_ag.pag, cur->bc_tp, |
62 | cur->bc_ag.agbp, &bno, 1); | |
97b3ffd0 | 63 | if (error) |
2bd0ea18 | 64 | return error; |
b194c7d8 BN |
65 | |
66 | if (bno == NULLAGBLOCK) { | |
2bd0ea18 NS |
67 | *stat = 0; |
68 | return 0; | |
69 | } | |
2bd0ea18 | 70 | |
92c76be5 | 71 | atomic64_inc(&cur->bc_mp->m_allocbt_blks); |
1d202c10 | 72 | xfs_extent_busy_reuse(cur->bc_mp, cur->bc_ag.pag, bno, 1, false); |
a2ceac1f | 73 | |
b194c7d8 | 74 | new->s = cpu_to_be32(bno); |
2bd0ea18 | 75 | |
2bd0ea18 NS |
76 | *stat = 1; |
77 | return 0; | |
2bd0ea18 NS |
78 | } |
79 | ||
b194c7d8 BN |
80 | STATIC int |
81 | xfs_allocbt_free_block( | |
82 | struct xfs_btree_cur *cur, | |
83 | struct xfs_buf *bp) | |
2bd0ea18 | 84 | { |
aa6fa37f | 85 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
b194c7d8 BN |
86 | xfs_agblock_t bno; |
87 | int error; | |
2bd0ea18 | 88 | |
d4aaa66b | 89 | bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp)); |
9a73333d DC |
90 | error = xfs_alloc_put_freelist(cur->bc_ag.pag, cur->bc_tp, agbp, NULL, |
91 | bno, 1); | |
5e656dbb | 92 | if (error) |
2bd0ea18 | 93 | return error; |
2bd0ea18 | 94 | |
92c76be5 | 95 | atomic64_dec(&cur->bc_mp->m_allocbt_blks); |
7635c486 | 96 | xfs_extent_busy_insert(cur->bc_tp, agbp->b_pag, bno, 1, |
a2ceac1f | 97 | XFS_EXTENT_BUSY_SKIP_DISCARD); |
2bd0ea18 NS |
98 | return 0; |
99 | } | |
100 | ||
101 | /* | |
b194c7d8 | 102 | * Update the longest extent in the AGF |
2bd0ea18 | 103 | */ |
b194c7d8 BN |
104 | STATIC void |
105 | xfs_allocbt_update_lastrec( | |
99c5a767 DW |
106 | struct xfs_btree_cur *cur, |
107 | const struct xfs_btree_block *block, | |
108 | const union xfs_btree_rec *rec, | |
109 | int ptr, | |
110 | int reason) | |
2bd0ea18 | 111 | { |
aa6fa37f | 112 | struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; |
56b2de80 | 113 | struct xfs_perag *pag; |
b194c7d8 BN |
114 | __be32 len; |
115 | int numrecs; | |
2bd0ea18 | 116 | |
b194c7d8 BN |
117 | ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); |
118 | ||
119 | switch (reason) { | |
120 | case LASTREC_UPDATE: | |
121 | /* | |
122 | * If this is the last leaf block and it's the last record, | |
123 | * then update the size of the longest extent in the AG. | |
124 | */ | |
125 | if (ptr != xfs_btree_get_numrecs(block)) | |
126 | return; | |
127 | len = rec->alloc.ar_blockcount; | |
128 | break; | |
129 | case LASTREC_INSREC: | |
130 | if (be32_to_cpu(rec->alloc.ar_blockcount) <= | |
131 | be32_to_cpu(agf->agf_longest)) | |
132 | return; | |
133 | len = rec->alloc.ar_blockcount; | |
134 | break; | |
135 | case LASTREC_DELREC: | |
136 | numrecs = xfs_btree_get_numrecs(block); | |
137 | if (ptr <= numrecs) | |
138 | return; | |
139 | ASSERT(ptr == numrecs + 1); | |
2bd0ea18 | 140 | |
b194c7d8 BN |
141 | if (numrecs) { |
142 | xfs_alloc_rec_t *rrp; | |
143 | ||
b3563c19 | 144 | rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs); |
b194c7d8 BN |
145 | len = rrp->ar_blockcount; |
146 | } else { | |
147 | len = 0; | |
148 | } | |
149 | ||
150 | break; | |
151 | default: | |
152 | ASSERT(0); | |
153 | return; | |
2bd0ea18 | 154 | } |
b194c7d8 BN |
155 | |
156 | agf->agf_longest = len; | |
10c0a390 | 157 | pag = cur->bc_ag.agbp->b_pag; |
56b2de80 | 158 | pag->pagf_longest = be32_to_cpu(len); |
aa6fa37f | 159 | xfs_alloc_log_agf(cur->bc_tp, cur->bc_ag.agbp, XFS_AGF_LONGEST); |
2bd0ea18 NS |
160 | } |
161 | ||
b194c7d8 BN |
162 | STATIC int |
163 | xfs_allocbt_get_minrecs( | |
164 | struct xfs_btree_cur *cur, | |
165 | int level) | |
166 | { | |
167 | return cur->bc_mp->m_alloc_mnr[level != 0]; | |
168 | } | |
2bd0ea18 | 169 | |
b194c7d8 BN |
170 | STATIC int |
171 | xfs_allocbt_get_maxrecs( | |
172 | struct xfs_btree_cur *cur, | |
173 | int level) | |
2bd0ea18 | 174 | { |
b194c7d8 BN |
175 | return cur->bc_mp->m_alloc_mxr[level != 0]; |
176 | } | |
2bd0ea18 | 177 | |
b194c7d8 BN |
178 | STATIC void |
179 | xfs_allocbt_init_key_from_rec( | |
c65978b6 DW |
180 | union xfs_btree_key *key, |
181 | const union xfs_btree_rec *rec) | |
b194c7d8 | 182 | { |
b194c7d8 BN |
183 | key->alloc.ar_startblock = rec->alloc.ar_startblock; |
184 | key->alloc.ar_blockcount = rec->alloc.ar_blockcount; | |
2bd0ea18 NS |
185 | } |
186 | ||
46a1586d DW |
187 | STATIC void |
188 | xfs_bnobt_init_high_key_from_rec( | |
c65978b6 DW |
189 | union xfs_btree_key *key, |
190 | const union xfs_btree_rec *rec) | |
46a1586d | 191 | { |
c65978b6 | 192 | __u32 x; |
46a1586d DW |
193 | |
194 | x = be32_to_cpu(rec->alloc.ar_startblock); | |
195 | x += be32_to_cpu(rec->alloc.ar_blockcount) - 1; | |
196 | key->alloc.ar_startblock = cpu_to_be32(x); | |
197 | key->alloc.ar_blockcount = 0; | |
198 | } | |
199 | ||
200 | STATIC void | |
201 | xfs_cntbt_init_high_key_from_rec( | |
c65978b6 DW |
202 | union xfs_btree_key *key, |
203 | const union xfs_btree_rec *rec) | |
46a1586d DW |
204 | { |
205 | key->alloc.ar_blockcount = rec->alloc.ar_blockcount; | |
206 | key->alloc.ar_startblock = 0; | |
207 | } | |
208 | ||
b194c7d8 BN |
209 | STATIC void |
210 | xfs_allocbt_init_rec_from_cur( | |
211 | struct xfs_btree_cur *cur, | |
212 | union xfs_btree_rec *rec) | |
2bd0ea18 | 213 | { |
b194c7d8 BN |
214 | rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock); |
215 | rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount); | |
216 | } | |
217 | ||
218 | STATIC void | |
219 | xfs_allocbt_init_ptr_from_cur( | |
220 | struct xfs_btree_cur *cur, | |
221 | union xfs_btree_ptr *ptr) | |
222 | { | |
aa6fa37f | 223 | struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; |
2bd0ea18 | 224 | |
ecb44e84 | 225 | ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno)); |
b194c7d8 BN |
226 | |
227 | ptr->s = agf->agf_roots[cur->bc_btnum]; | |
228 | } | |
229 | ||
4a492e72 | 230 | STATIC int64_t |
46a1586d | 231 | xfs_bnobt_key_diff( |
901acb0e DW |
232 | struct xfs_btree_cur *cur, |
233 | const union xfs_btree_key *key) | |
b194c7d8 | 234 | { |
901acb0e DW |
235 | struct xfs_alloc_rec_incore *rec = &cur->bc_rec.a; |
236 | const struct xfs_alloc_rec *kp = &key->alloc; | |
b194c7d8 | 237 | |
4a492e72 | 238 | return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; |
46a1586d DW |
239 | } |
240 | ||
4a492e72 | 241 | STATIC int64_t |
46a1586d | 242 | xfs_cntbt_key_diff( |
901acb0e DW |
243 | struct xfs_btree_cur *cur, |
244 | const union xfs_btree_key *key) | |
46a1586d | 245 | { |
901acb0e DW |
246 | struct xfs_alloc_rec_incore *rec = &cur->bc_rec.a; |
247 | const struct xfs_alloc_rec *kp = &key->alloc; | |
248 | int64_t diff; | |
b194c7d8 | 249 | |
4a492e72 | 250 | diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount; |
b194c7d8 BN |
251 | if (diff) |
252 | return diff; | |
253 | ||
4a492e72 | 254 | return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; |
2bd0ea18 NS |
255 | } |
256 | ||
4a492e72 | 257 | STATIC int64_t |
46a1586d | 258 | xfs_bnobt_diff_two_keys( |
901acb0e DW |
259 | struct xfs_btree_cur *cur, |
260 | const union xfs_btree_key *k1, | |
d99b8900 DW |
261 | const union xfs_btree_key *k2, |
262 | const union xfs_btree_key *mask) | |
46a1586d | 263 | { |
d99b8900 DW |
264 | ASSERT(!mask || mask->alloc.ar_startblock); |
265 | ||
4a492e72 | 266 | return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) - |
d99b8900 | 267 | be32_to_cpu(k2->alloc.ar_startblock); |
46a1586d DW |
268 | } |
269 | ||
4a492e72 | 270 | STATIC int64_t |
46a1586d | 271 | xfs_cntbt_diff_two_keys( |
901acb0e DW |
272 | struct xfs_btree_cur *cur, |
273 | const union xfs_btree_key *k1, | |
d99b8900 DW |
274 | const union xfs_btree_key *k2, |
275 | const union xfs_btree_key *mask) | |
46a1586d | 276 | { |
901acb0e | 277 | int64_t diff; |
46a1586d | 278 | |
d99b8900 DW |
279 | ASSERT(!mask || (mask->alloc.ar_blockcount && |
280 | mask->alloc.ar_startblock)); | |
281 | ||
46a1586d DW |
282 | diff = be32_to_cpu(k1->alloc.ar_blockcount) - |
283 | be32_to_cpu(k2->alloc.ar_blockcount); | |
284 | if (diff) | |
285 | return diff; | |
286 | ||
287 | return be32_to_cpu(k1->alloc.ar_startblock) - | |
288 | be32_to_cpu(k2->alloc.ar_startblock); | |
289 | } | |
290 | ||
bc01119d | 291 | static xfs_failaddr_t |
a2ceac1f DC |
292 | xfs_allocbt_verify( |
293 | struct xfs_buf *bp) | |
294 | { | |
7861ef77 | 295 | struct xfs_mount *mp = bp->b_mount; |
a2ceac1f DC |
296 | struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); |
297 | struct xfs_perag *pag = bp->b_pag; | |
bc01119d | 298 | xfs_failaddr_t fa; |
a2ceac1f | 299 | unsigned int level; |
1d8220ba BF |
300 | xfs_btnum_t btnum = XFS_BTNUM_BNOi; |
301 | ||
302 | if (!xfs_verify_magic(bp, block->bb_magic)) | |
303 | return __this_address; | |
304 | ||
94541a16 | 305 | if (xfs_has_crc(mp)) { |
1d8220ba BF |
306 | fa = xfs_btree_sblock_v5hdr_verify(bp); |
307 | if (fa) | |
308 | return fa; | |
309 | } | |
a2ceac1f DC |
310 | |
311 | /* | |
1d8220ba BF |
312 | * The perag may not be attached during grow operations or fully |
313 | * initialized from the AGF during log recovery. Therefore we can only | |
314 | * check against maximum tree depth from those contexts. | |
c0adfb03 | 315 | * |
1d8220ba BF |
316 | * Otherwise check against the per-tree limit. Peek at one of the |
317 | * verifier magic values to determine the type of tree we're verifying | |
318 | * against. | |
a2ceac1f DC |
319 | */ |
320 | level = be16_to_cpu(block->bb_level); | |
1d8220ba BF |
321 | if (bp->b_ops->magic[0] == cpu_to_be32(XFS_ABTC_MAGIC)) |
322 | btnum = XFS_BTNUM_CNTi; | |
03dc2ef2 | 323 | if (pag && xfs_perag_initialised_agf(pag)) { |
1d8220ba | 324 | if (level >= pag->pagf_levels[btnum]) |
bc01119d | 325 | return __this_address; |
4aa2259d | 326 | } else if (level >= mp->m_alloc_maxlevels) |
bc01119d | 327 | return __this_address; |
a2ceac1f | 328 | |
dbca0167 | 329 | return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); |
a2ceac1f DC |
330 | } |
331 | ||
332 | static void | |
333 | xfs_allocbt_read_verify( | |
334 | struct xfs_buf *bp) | |
335 | { | |
1e697959 DW |
336 | xfs_failaddr_t fa; |
337 | ||
45922933 | 338 | if (!xfs_btree_sblock_verify_crc(bp)) |
1e697959 DW |
339 | xfs_verifier_error(bp, -EFSBADCRC, __this_address); |
340 | else { | |
341 | fa = xfs_allocbt_verify(bp); | |
342 | if (fa) | |
343 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); | |
344 | } | |
45922933 | 345 | |
7e6c95f1 | 346 | if (bp->b_error) |
45922933 | 347 | trace_xfs_btree_corrupt(bp, _RET_IP_); |
a2ceac1f DC |
348 | } |
349 | ||
350 | static void | |
351 | xfs_allocbt_write_verify( | |
352 | struct xfs_buf *bp) | |
353 | { | |
1e697959 DW |
354 | xfs_failaddr_t fa; |
355 | ||
356 | fa = xfs_allocbt_verify(bp); | |
357 | if (fa) { | |
5dfa5cd2 | 358 | trace_xfs_btree_corrupt(bp, _RET_IP_); |
1e697959 | 359 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); |
dbf564d1 | 360 | return; |
5dfa5cd2 DC |
361 | } |
362 | xfs_btree_sblock_calc_crc(bp); | |
363 | ||
a2ceac1f DC |
364 | } |
365 | ||
fce74e98 BF |
366 | const struct xfs_buf_ops xfs_bnobt_buf_ops = { |
367 | .name = "xfs_bnobt", | |
1d8220ba BF |
368 | .magic = { cpu_to_be32(XFS_ABTB_MAGIC), |
369 | cpu_to_be32(XFS_ABTB_CRC_MAGIC) }, | |
a2ceac1f DC |
370 | .verify_read = xfs_allocbt_read_verify, |
371 | .verify_write = xfs_allocbt_write_verify, | |
95d9582b | 372 | .verify_struct = xfs_allocbt_verify, |
a2ceac1f DC |
373 | }; |
374 | ||
fce74e98 BF |
375 | const struct xfs_buf_ops xfs_cntbt_buf_ops = { |
376 | .name = "xfs_cntbt", | |
1d8220ba BF |
377 | .magic = { cpu_to_be32(XFS_ABTC_MAGIC), |
378 | cpu_to_be32(XFS_ABTC_CRC_MAGIC) }, | |
fce74e98 BF |
379 | .verify_read = xfs_allocbt_read_verify, |
380 | .verify_write = xfs_allocbt_write_verify, | |
381 | .verify_struct = xfs_allocbt_verify, | |
382 | }; | |
a2ceac1f | 383 | |
b194c7d8 | 384 | STATIC int |
46a1586d | 385 | xfs_bnobt_keys_inorder( |
141bbc5c DW |
386 | struct xfs_btree_cur *cur, |
387 | const union xfs_btree_key *k1, | |
388 | const union xfs_btree_key *k2) | |
b194c7d8 | 389 | { |
46a1586d DW |
390 | return be32_to_cpu(k1->alloc.ar_startblock) < |
391 | be32_to_cpu(k2->alloc.ar_startblock); | |
b194c7d8 | 392 | } |
2bd0ea18 | 393 | |
b194c7d8 | 394 | STATIC int |
46a1586d | 395 | xfs_bnobt_recs_inorder( |
141bbc5c DW |
396 | struct xfs_btree_cur *cur, |
397 | const union xfs_btree_rec *r1, | |
398 | const union xfs_btree_rec *r2) | |
b194c7d8 | 399 | { |
46a1586d DW |
400 | return be32_to_cpu(r1->alloc.ar_startblock) + |
401 | be32_to_cpu(r1->alloc.ar_blockcount) <= | |
402 | be32_to_cpu(r2->alloc.ar_startblock); | |
403 | } | |
404 | ||
405 | STATIC int | |
406 | xfs_cntbt_keys_inorder( | |
141bbc5c DW |
407 | struct xfs_btree_cur *cur, |
408 | const union xfs_btree_key *k1, | |
409 | const union xfs_btree_key *k2) | |
46a1586d DW |
410 | { |
411 | return be32_to_cpu(k1->alloc.ar_blockcount) < | |
412 | be32_to_cpu(k2->alloc.ar_blockcount) || | |
413 | (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && | |
414 | be32_to_cpu(k1->alloc.ar_startblock) < | |
415 | be32_to_cpu(k2->alloc.ar_startblock)); | |
2bd0ea18 NS |
416 | } |
417 | ||
46a1586d DW |
418 | STATIC int |
419 | xfs_cntbt_recs_inorder( | |
141bbc5c DW |
420 | struct xfs_btree_cur *cur, |
421 | const union xfs_btree_rec *r1, | |
422 | const union xfs_btree_rec *r2) | |
46a1586d DW |
423 | { |
424 | return be32_to_cpu(r1->alloc.ar_blockcount) < | |
425 | be32_to_cpu(r2->alloc.ar_blockcount) || | |
426 | (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && | |
427 | be32_to_cpu(r1->alloc.ar_startblock) < | |
428 | be32_to_cpu(r2->alloc.ar_startblock)); | |
429 | } | |
46a1586d | 430 | |
9ba4dc82 DW |
431 | STATIC enum xbtree_key_contig |
432 | xfs_allocbt_keys_contiguous( | |
433 | struct xfs_btree_cur *cur, | |
434 | const union xfs_btree_key *key1, | |
d99b8900 DW |
435 | const union xfs_btree_key *key2, |
436 | const union xfs_btree_key *mask) | |
9ba4dc82 | 437 | { |
d99b8900 DW |
438 | ASSERT(!mask || mask->alloc.ar_startblock); |
439 | ||
9ba4dc82 DW |
440 | return xbtree_key_contig(be32_to_cpu(key1->alloc.ar_startblock), |
441 | be32_to_cpu(key2->alloc.ar_startblock)); | |
442 | } | |
443 | ||
46a1586d | 444 | static const struct xfs_btree_ops xfs_bnobt_ops = { |
b194c7d8 BN |
445 | .rec_len = sizeof(xfs_alloc_rec_t), |
446 | .key_len = sizeof(xfs_alloc_key_t), | |
447 | ||
448 | .dup_cursor = xfs_allocbt_dup_cursor, | |
449 | .set_root = xfs_allocbt_set_root, | |
b194c7d8 BN |
450 | .alloc_block = xfs_allocbt_alloc_block, |
451 | .free_block = xfs_allocbt_free_block, | |
452 | .update_lastrec = xfs_allocbt_update_lastrec, | |
453 | .get_minrecs = xfs_allocbt_get_minrecs, | |
454 | .get_maxrecs = xfs_allocbt_get_maxrecs, | |
455 | .init_key_from_rec = xfs_allocbt_init_key_from_rec, | |
46a1586d | 456 | .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec, |
b194c7d8 BN |
457 | .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, |
458 | .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, | |
46a1586d | 459 | .key_diff = xfs_bnobt_key_diff, |
fce74e98 | 460 | .buf_ops = &xfs_bnobt_buf_ops, |
46a1586d | 461 | .diff_two_keys = xfs_bnobt_diff_two_keys, |
46a1586d DW |
462 | .keys_inorder = xfs_bnobt_keys_inorder, |
463 | .recs_inorder = xfs_bnobt_recs_inorder, | |
9ba4dc82 | 464 | .keys_contiguous = xfs_allocbt_keys_contiguous, |
46a1586d DW |
465 | }; |
466 | ||
467 | static const struct xfs_btree_ops xfs_cntbt_ops = { | |
468 | .rec_len = sizeof(xfs_alloc_rec_t), | |
469 | .key_len = sizeof(xfs_alloc_key_t), | |
470 | ||
471 | .dup_cursor = xfs_allocbt_dup_cursor, | |
472 | .set_root = xfs_allocbt_set_root, | |
473 | .alloc_block = xfs_allocbt_alloc_block, | |
474 | .free_block = xfs_allocbt_free_block, | |
475 | .update_lastrec = xfs_allocbt_update_lastrec, | |
476 | .get_minrecs = xfs_allocbt_get_minrecs, | |
477 | .get_maxrecs = xfs_allocbt_get_maxrecs, | |
478 | .init_key_from_rec = xfs_allocbt_init_key_from_rec, | |
479 | .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec, | |
480 | .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, | |
481 | .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, | |
482 | .key_diff = xfs_cntbt_key_diff, | |
fce74e98 | 483 | .buf_ops = &xfs_cntbt_buf_ops, |
46a1586d | 484 | .diff_two_keys = xfs_cntbt_diff_two_keys, |
46a1586d DW |
485 | .keys_inorder = xfs_cntbt_keys_inorder, |
486 | .recs_inorder = xfs_cntbt_recs_inorder, | |
9ba4dc82 | 487 | .keys_contiguous = NULL, /* not needed right now */ |
b194c7d8 | 488 | }; |
2bd0ea18 | 489 | |
7bc27889 DW |
490 | /* Allocate most of a new allocation btree cursor. */ |
491 | STATIC struct xfs_btree_cur * | |
492 | xfs_allocbt_init_common( | |
493 | struct xfs_mount *mp, | |
494 | struct xfs_trans *tp, | |
ca7d293d | 495 | struct xfs_perag *pag, |
7bc27889 | 496 | xfs_btnum_t btnum) |
2bd0ea18 | 497 | { |
b194c7d8 | 498 | struct xfs_btree_cur *cur; |
2bd0ea18 | 499 | |
b194c7d8 | 500 | ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); |
2bd0ea18 | 501 | |
7d10d094 DW |
502 | cur = xfs_btree_alloc_cursor(mp, tp, btnum, mp->m_alloc_maxlevels, |
503 | xfs_allocbt_cur_cache); | |
ecb44e84 | 504 | cur->bc_ag.abt.active = false; |
a2ceac1f DC |
505 | |
506 | if (btnum == XFS_BTNUM_CNT) { | |
46a1586d | 507 | cur->bc_ops = &xfs_cntbt_ops; |
7bc27889 | 508 | cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2); |
b194c7d8 | 509 | cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; |
a2ceac1f | 510 | } else { |
46a1586d | 511 | cur->bc_ops = &xfs_bnobt_ops; |
7bc27889 | 512 | cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2); |
a2ceac1f | 513 | } |
b194c7d8 | 514 | |
11e716f4 | 515 | cur->bc_ag.pag = xfs_perag_hold(pag); |
b194c7d8 | 516 | |
b16a427a | 517 | if (xfs_has_crc(mp)) |
5dfa5cd2 DC |
518 | cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; |
519 | ||
b194c7d8 | 520 | return cur; |
2bd0ea18 | 521 | } |
b3563c19 | 522 | |
7bc27889 DW |
523 | /* |
524 | * Allocate a new allocation btree cursor. | |
525 | */ | |
526 | struct xfs_btree_cur * /* new alloc btree cursor */ | |
527 | xfs_allocbt_init_cursor( | |
528 | struct xfs_mount *mp, /* file system mount point */ | |
529 | struct xfs_trans *tp, /* transaction pointer */ | |
530 | struct xfs_buf *agbp, /* buffer for agf structure */ | |
ca7d293d | 531 | struct xfs_perag *pag, |
7bc27889 DW |
532 | xfs_btnum_t btnum) /* btree identifier */ |
533 | { | |
534 | struct xfs_agf *agf = agbp->b_addr; | |
535 | struct xfs_btree_cur *cur; | |
536 | ||
ecb44e84 | 537 | cur = xfs_allocbt_init_common(mp, tp, pag, btnum); |
7bc27889 DW |
538 | if (btnum == XFS_BTNUM_CNT) |
539 | cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); | |
540 | else | |
541 | cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); | |
542 | ||
543 | cur->bc_ag.agbp = agbp; | |
544 | ||
545 | return cur; | |
546 | } | |
547 | ||
548 | /* Create a free space btree cursor with a fake root for staging. */ | |
549 | struct xfs_btree_cur * | |
550 | xfs_allocbt_stage_cursor( | |
551 | struct xfs_mount *mp, | |
552 | struct xbtree_afakeroot *afake, | |
ecb44e84 | 553 | struct xfs_perag *pag, |
7bc27889 DW |
554 | xfs_btnum_t btnum) |
555 | { | |
556 | struct xfs_btree_cur *cur; | |
557 | ||
ecb44e84 | 558 | cur = xfs_allocbt_init_common(mp, NULL, pag, btnum); |
7bc27889 DW |
559 | xfs_btree_stage_afakeroot(cur, afake); |
560 | return cur; | |
561 | } | |
562 | ||
563 | /* | |
564 | * Install a new free space btree root. Caller is responsible for invalidating | |
565 | * and freeing the old btree blocks. | |
566 | */ | |
567 | void | |
568 | xfs_allocbt_commit_staged_btree( | |
569 | struct xfs_btree_cur *cur, | |
570 | struct xfs_trans *tp, | |
571 | struct xfs_buf *agbp) | |
572 | { | |
573 | struct xfs_agf *agf = agbp->b_addr; | |
574 | struct xbtree_afakeroot *afake = cur->bc_ag.afake; | |
575 | ||
576 | ASSERT(cur->bc_flags & XFS_BTREE_STAGING); | |
577 | ||
578 | agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root); | |
579 | agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels); | |
580 | xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); | |
581 | ||
582 | if (cur->bc_btnum == XFS_BTNUM_BNO) { | |
583 | xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_bnobt_ops); | |
584 | } else { | |
585 | cur->bc_flags |= XFS_BTREE_LASTREC_UPDATE; | |
586 | xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_cntbt_ops); | |
587 | } | |
588 | } | |
589 | ||
441815c7 DW |
590 | /* Calculate number of records in an alloc btree block. */ |
591 | static inline unsigned int | |
592 | xfs_allocbt_block_maxrecs( | |
593 | unsigned int blocklen, | |
594 | bool leaf) | |
595 | { | |
596 | if (leaf) | |
597 | return blocklen / sizeof(xfs_alloc_rec_t); | |
598 | return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); | |
599 | } | |
600 | ||
b3563c19 BN |
601 | /* |
602 | * Calculate number of records in an alloc btree block. | |
603 | */ | |
604 | int | |
605 | xfs_allocbt_maxrecs( | |
606 | struct xfs_mount *mp, | |
607 | int blocklen, | |
608 | int leaf) | |
609 | { | |
610 | blocklen -= XFS_ALLOC_BLOCK_LEN(mp); | |
441815c7 DW |
611 | return xfs_allocbt_block_maxrecs(blocklen, leaf); |
612 | } | |
b3563c19 | 613 | |
441815c7 DW |
614 | /* Free space btrees are at their largest when every other block is free. */ |
615 | #define XFS_MAX_FREESP_RECORDS ((XFS_MAX_AG_BLOCKS + 1) / 2) | |
616 | ||
617 | /* Compute the max possible height for free space btrees. */ | |
618 | unsigned int | |
619 | xfs_allocbt_maxlevels_ondisk(void) | |
620 | { | |
621 | unsigned int minrecs[2]; | |
622 | unsigned int blocklen; | |
623 | ||
624 | blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, | |
625 | XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN); | |
626 | ||
627 | minrecs[0] = xfs_allocbt_block_maxrecs(blocklen, true) / 2; | |
628 | minrecs[1] = xfs_allocbt_block_maxrecs(blocklen, false) / 2; | |
629 | ||
630 | return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_FREESP_RECORDS); | |
b3563c19 | 631 | } |
5f728383 DW |
632 | |
633 | /* Calculate the freespace btree size for some records. */ | |
634 | xfs_extlen_t | |
635 | xfs_allocbt_calc_size( | |
636 | struct xfs_mount *mp, | |
637 | unsigned long long len) | |
638 | { | |
639 | return xfs_btree_calc_size(mp->m_alloc_mnr, len); | |
640 | } | |
7d10d094 DW |
641 | |
642 | int __init | |
643 | xfs_allocbt_init_cur_cache(void) | |
644 | { | |
645 | xfs_allocbt_cur_cache = kmem_cache_create("xfs_bnobt_cur", | |
646 | xfs_btree_cur_sizeof(xfs_allocbt_maxlevels_ondisk()), | |
647 | 0, 0, NULL); | |
648 | ||
649 | if (!xfs_allocbt_cur_cache) | |
650 | return -ENOMEM; | |
651 | return 0; | |
652 | } | |
653 | ||
654 | void | |
655 | xfs_allocbt_destroy_cur_cache(void) | |
656 | { | |
657 | kmem_cache_destroy(xfs_allocbt_cur_cache); | |
658 | xfs_allocbt_cur_cache = NULL; | |
659 | } |