Commit | Line | Data |
---|---|---|
18a1e644 DW |
1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* | |
3 | * Copyright (c) 2022-2024 Oracle. All Rights Reserved. | |
4 | * Author: Darrick J. Wong <djwong@kernel.org> | |
5 | */ | |
6 | #include "xfs.h" | |
7 | #include "xfs_fs.h" | |
8 | #include "xfs_shared.h" | |
9 | #include "xfs_format.h" | |
10 | #include "xfs_trans_resv.h" | |
11 | #include "xfs_mount.h" | |
12 | #include "xfs_defer.h" | |
13 | #include "xfs_btree.h" | |
14 | #include "xfs_buf_mem.h" | |
15 | #include "xfs_btree_mem.h" | |
16 | #include "xfs_error.h" | |
17 | #include "scrub/rcbag_btree.h" | |
18 | #include "scrub/trace.h" | |
19 | ||
20 | static struct kmem_cache *rcbagbt_cur_cache; | |
21 | ||
22 | STATIC void | |
23 | rcbagbt_init_key_from_rec( | |
24 | union xfs_btree_key *key, | |
25 | const union xfs_btree_rec *rec) | |
26 | { | |
27 | struct rcbag_key *bag_key = (struct rcbag_key *)key; | |
28 | const struct rcbag_rec *bag_rec = (const struct rcbag_rec *)rec; | |
29 | ||
30 | BUILD_BUG_ON(sizeof(struct rcbag_key) > sizeof(union xfs_btree_key)); | |
31 | BUILD_BUG_ON(sizeof(struct rcbag_rec) > sizeof(union xfs_btree_rec)); | |
32 | ||
33 | bag_key->rbg_startblock = bag_rec->rbg_startblock; | |
34 | bag_key->rbg_blockcount = bag_rec->rbg_blockcount; | |
35 | } | |
36 | ||
37 | STATIC void | |
38 | rcbagbt_init_rec_from_cur( | |
39 | struct xfs_btree_cur *cur, | |
40 | union xfs_btree_rec *rec) | |
41 | { | |
42 | struct rcbag_rec *bag_rec = (struct rcbag_rec *)rec; | |
43 | struct rcbag_rec *bag_irec = (struct rcbag_rec *)&cur->bc_rec; | |
44 | ||
45 | bag_rec->rbg_startblock = bag_irec->rbg_startblock; | |
46 | bag_rec->rbg_blockcount = bag_irec->rbg_blockcount; | |
47 | bag_rec->rbg_refcount = bag_irec->rbg_refcount; | |
48 | } | |
49 | ||
50 | STATIC int64_t | |
51 | rcbagbt_key_diff( | |
52 | struct xfs_btree_cur *cur, | |
53 | const union xfs_btree_key *key) | |
54 | { | |
55 | struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec; | |
56 | const struct rcbag_key *kp = (const struct rcbag_key *)key; | |
57 | ||
58 | if (kp->rbg_startblock > rec->rbg_startblock) | |
59 | return 1; | |
60 | if (kp->rbg_startblock < rec->rbg_startblock) | |
61 | return -1; | |
62 | ||
63 | if (kp->rbg_blockcount > rec->rbg_blockcount) | |
64 | return 1; | |
65 | if (kp->rbg_blockcount < rec->rbg_blockcount) | |
66 | return -1; | |
67 | ||
68 | return 0; | |
69 | } | |
70 | ||
71 | STATIC int64_t | |
72 | rcbagbt_diff_two_keys( | |
73 | struct xfs_btree_cur *cur, | |
74 | const union xfs_btree_key *k1, | |
75 | const union xfs_btree_key *k2, | |
76 | const union xfs_btree_key *mask) | |
77 | { | |
78 | const struct rcbag_key *kp1 = (const struct rcbag_key *)k1; | |
79 | const struct rcbag_key *kp2 = (const struct rcbag_key *)k2; | |
80 | ||
81 | ASSERT(mask == NULL); | |
82 | ||
83 | if (kp1->rbg_startblock > kp2->rbg_startblock) | |
84 | return 1; | |
85 | if (kp1->rbg_startblock < kp2->rbg_startblock) | |
86 | return -1; | |
87 | ||
88 | if (kp1->rbg_blockcount > kp2->rbg_blockcount) | |
89 | return 1; | |
90 | if (kp1->rbg_blockcount < kp2->rbg_blockcount) | |
91 | return -1; | |
92 | ||
93 | return 0; | |
94 | } | |
95 | ||
96 | STATIC int | |
97 | rcbagbt_keys_inorder( | |
98 | struct xfs_btree_cur *cur, | |
99 | const union xfs_btree_key *k1, | |
100 | const union xfs_btree_key *k2) | |
101 | { | |
102 | const struct rcbag_key *kp1 = (const struct rcbag_key *)k1; | |
103 | const struct rcbag_key *kp2 = (const struct rcbag_key *)k2; | |
104 | ||
105 | if (kp1->rbg_startblock > kp2->rbg_startblock) | |
106 | return 0; | |
107 | if (kp1->rbg_startblock < kp2->rbg_startblock) | |
108 | return 1; | |
109 | ||
110 | if (kp1->rbg_blockcount > kp2->rbg_blockcount) | |
111 | return 0; | |
112 | if (kp1->rbg_blockcount < kp2->rbg_blockcount) | |
113 | return 1; | |
114 | ||
115 | return 0; | |
116 | } | |
117 | ||
118 | STATIC int | |
119 | rcbagbt_recs_inorder( | |
120 | struct xfs_btree_cur *cur, | |
121 | const union xfs_btree_rec *r1, | |
122 | const union xfs_btree_rec *r2) | |
123 | { | |
124 | const struct rcbag_rec *rp1 = (const struct rcbag_rec *)r1; | |
125 | const struct rcbag_rec *rp2 = (const struct rcbag_rec *)r2; | |
126 | ||
127 | if (rp1->rbg_startblock > rp2->rbg_startblock) | |
128 | return 0; | |
129 | if (rp1->rbg_startblock < rp2->rbg_startblock) | |
130 | return 1; | |
131 | ||
132 | if (rp1->rbg_blockcount > rp2->rbg_blockcount) | |
133 | return 0; | |
134 | if (rp1->rbg_blockcount < rp2->rbg_blockcount) | |
135 | return 1; | |
136 | ||
137 | return 0; | |
138 | } | |
139 | ||
140 | static xfs_failaddr_t | |
141 | rcbagbt_verify( | |
142 | struct xfs_buf *bp) | |
143 | { | |
144 | struct xfs_mount *mp = bp->b_mount; | |
145 | struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); | |
146 | xfs_failaddr_t fa; | |
147 | unsigned int level; | |
148 | unsigned int maxrecs; | |
149 | ||
150 | if (!xfs_verify_magic(bp, block->bb_magic)) | |
151 | return __this_address; | |
152 | ||
153 | fa = xfs_btree_fsblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN); | |
154 | if (fa) | |
155 | return fa; | |
156 | ||
157 | level = be16_to_cpu(block->bb_level); | |
158 | if (level >= rcbagbt_maxlevels_possible()) | |
159 | return __this_address; | |
160 | ||
161 | maxrecs = rcbagbt_maxrecs(mp, XFBNO_BLOCKSIZE, level == 0); | |
162 | return xfs_btree_memblock_verify(bp, maxrecs); | |
163 | } | |
164 | ||
165 | static void | |
166 | rcbagbt_rw_verify( | |
167 | struct xfs_buf *bp) | |
168 | { | |
169 | xfs_failaddr_t fa = rcbagbt_verify(bp); | |
170 | ||
171 | if (fa) | |
172 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); | |
173 | } | |
174 | ||
175 | /* skip crc checks on in-memory btrees to save time */ | |
176 | static const struct xfs_buf_ops rcbagbt_mem_buf_ops = { | |
177 | .name = "rcbagbt_mem", | |
178 | .magic = { 0, cpu_to_be32(RCBAG_MAGIC) }, | |
179 | .verify_read = rcbagbt_rw_verify, | |
180 | .verify_write = rcbagbt_rw_verify, | |
181 | .verify_struct = rcbagbt_verify, | |
182 | }; | |
183 | ||
184 | static const struct xfs_btree_ops rcbagbt_mem_ops = { | |
185 | .name = "rcbag", | |
186 | .type = XFS_BTREE_TYPE_MEM, | |
187 | ||
188 | .rec_len = sizeof(struct rcbag_rec), | |
189 | .key_len = sizeof(struct rcbag_key), | |
190 | .ptr_len = XFS_BTREE_LONG_PTR_LEN, | |
191 | ||
192 | .lru_refs = 1, | |
193 | .statoff = XFS_STATS_CALC_INDEX(xs_rcbag_2), | |
194 | ||
195 | .dup_cursor = xfbtree_dup_cursor, | |
196 | .set_root = xfbtree_set_root, | |
197 | .alloc_block = xfbtree_alloc_block, | |
198 | .free_block = xfbtree_free_block, | |
199 | .get_minrecs = xfbtree_get_minrecs, | |
200 | .get_maxrecs = xfbtree_get_maxrecs, | |
201 | .init_key_from_rec = rcbagbt_init_key_from_rec, | |
202 | .init_rec_from_cur = rcbagbt_init_rec_from_cur, | |
203 | .init_ptr_from_cur = xfbtree_init_ptr_from_cur, | |
204 | .key_diff = rcbagbt_key_diff, | |
205 | .buf_ops = &rcbagbt_mem_buf_ops, | |
206 | .diff_two_keys = rcbagbt_diff_two_keys, | |
207 | .keys_inorder = rcbagbt_keys_inorder, | |
208 | .recs_inorder = rcbagbt_recs_inorder, | |
209 | }; | |
210 | ||
211 | /* Create a cursor for an in-memory btree. */ | |
212 | struct xfs_btree_cur * | |
213 | rcbagbt_mem_cursor( | |
214 | struct xfs_mount *mp, | |
215 | struct xfs_trans *tp, | |
216 | struct xfbtree *xfbtree) | |
217 | { | |
218 | struct xfs_btree_cur *cur; | |
219 | ||
220 | cur = xfs_btree_alloc_cursor(mp, tp, &rcbagbt_mem_ops, | |
221 | rcbagbt_maxlevels_possible(), rcbagbt_cur_cache); | |
222 | ||
223 | cur->bc_mem.xfbtree = xfbtree; | |
224 | cur->bc_nlevels = xfbtree->nlevels; | |
225 | return cur; | |
226 | } | |
227 | ||
228 | /* Create an in-memory refcount bag btree. */ | |
229 | int | |
230 | rcbagbt_mem_init( | |
231 | struct xfs_mount *mp, | |
232 | struct xfbtree *xfbt, | |
233 | struct xfs_buftarg *btp) | |
234 | { | |
235 | xfbt->owner = 0; | |
236 | return xfbtree_init(mp, xfbt, btp, &rcbagbt_mem_ops); | |
237 | } | |
238 | ||
239 | /* Calculate number of records in a refcount bag btree block. */ | |
240 | static inline unsigned int | |
241 | rcbagbt_block_maxrecs( | |
242 | unsigned int blocklen, | |
243 | bool leaf) | |
244 | { | |
245 | if (leaf) | |
246 | return blocklen / sizeof(struct rcbag_rec); | |
247 | return blocklen / | |
248 | (sizeof(struct rcbag_key) + sizeof(rcbag_ptr_t)); | |
249 | } | |
250 | ||
251 | /* | |
252 | * Calculate number of records in an refcount bag btree block. | |
253 | */ | |
254 | unsigned int | |
255 | rcbagbt_maxrecs( | |
256 | struct xfs_mount *mp, | |
257 | unsigned int blocklen, | |
258 | bool leaf) | |
259 | { | |
260 | blocklen -= RCBAG_BLOCK_LEN; | |
261 | return rcbagbt_block_maxrecs(blocklen, leaf); | |
262 | } | |
263 | ||
264 | /* Compute the max possible height for refcount bag btrees. */ | |
265 | unsigned int | |
266 | rcbagbt_maxlevels_possible(void) | |
267 | { | |
268 | unsigned int minrecs[2]; | |
269 | unsigned int blocklen; | |
270 | ||
271 | blocklen = XFBNO_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN; | |
272 | ||
273 | minrecs[0] = rcbagbt_block_maxrecs(blocklen, true) / 2; | |
274 | minrecs[1] = rcbagbt_block_maxrecs(blocklen, false) / 2; | |
275 | ||
276 | return xfs_btree_space_to_height(minrecs, ULLONG_MAX); | |
277 | } | |
278 | ||
279 | /* Calculate the refcount bag btree size for some records. */ | |
280 | unsigned long long | |
281 | rcbagbt_calc_size( | |
282 | unsigned long long nr_records) | |
283 | { | |
284 | unsigned int minrecs[2]; | |
285 | unsigned int blocklen; | |
286 | ||
287 | blocklen = XFBNO_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN; | |
288 | ||
289 | minrecs[0] = rcbagbt_block_maxrecs(blocklen, true) / 2; | |
290 | minrecs[1] = rcbagbt_block_maxrecs(blocklen, false) / 2; | |
291 | ||
292 | return xfs_btree_calc_size(minrecs, nr_records); | |
293 | } | |
294 | ||
295 | int __init | |
296 | rcbagbt_init_cur_cache(void) | |
297 | { | |
298 | rcbagbt_cur_cache = kmem_cache_create("xfs_rcbagbt_cur", | |
299 | xfs_btree_cur_sizeof(rcbagbt_maxlevels_possible()), | |
300 | 0, 0, NULL); | |
301 | ||
302 | if (!rcbagbt_cur_cache) | |
303 | return -ENOMEM; | |
304 | return 0; | |
305 | } | |
306 | ||
307 | void | |
308 | rcbagbt_destroy_cur_cache(void) | |
309 | { | |
310 | kmem_cache_destroy(rcbagbt_cur_cache); | |
311 | rcbagbt_cur_cache = NULL; | |
312 | } | |
7a2192ac DW |
313 | |
314 | /* Look up the refcount bag record corresponding to this reverse mapping. */ | |
315 | int | |
316 | rcbagbt_lookup_eq( | |
317 | struct xfs_btree_cur *cur, | |
318 | const struct xfs_rmap_irec *rmap, | |
319 | int *success) | |
320 | { | |
321 | struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec; | |
322 | ||
323 | rec->rbg_startblock = rmap->rm_startblock; | |
324 | rec->rbg_blockcount = rmap->rm_blockcount; | |
325 | ||
326 | return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, success); | |
327 | } | |
328 | ||
329 | /* Get the data from the pointed-to record. */ | |
330 | int | |
331 | rcbagbt_get_rec( | |
332 | struct xfs_btree_cur *cur, | |
333 | struct rcbag_rec *rec, | |
334 | int *has) | |
335 | { | |
336 | union xfs_btree_rec *btrec; | |
337 | int error; | |
338 | ||
339 | error = xfs_btree_get_rec(cur, &btrec, has); | |
340 | if (error || !(*has)) | |
341 | return error; | |
342 | ||
343 | memcpy(rec, btrec, sizeof(struct rcbag_rec)); | |
344 | return 0; | |
345 | } | |
346 | ||
347 | /* Update the record referred to by cur to the value given. */ | |
348 | int | |
349 | rcbagbt_update( | |
350 | struct xfs_btree_cur *cur, | |
351 | const struct rcbag_rec *rec) | |
352 | { | |
353 | union xfs_btree_rec btrec; | |
354 | ||
355 | memcpy(&btrec, rec, sizeof(struct rcbag_rec)); | |
356 | return xfs_btree_update(cur, &btrec); | |
357 | } | |
358 | ||
359 | /* Update the record referred to by cur to the value given. */ | |
360 | int | |
361 | rcbagbt_insert( | |
362 | struct xfs_btree_cur *cur, | |
363 | const struct rcbag_rec *rec, | |
364 | int *success) | |
365 | { | |
366 | struct rcbag_rec *btrec = (struct rcbag_rec *)&cur->bc_rec; | |
367 | ||
368 | memcpy(btrec, rec, sizeof(struct rcbag_rec)); | |
369 | return xfs_btree_insert(cur, success); | |
370 | } |