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 | } |
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 | } |
371 | |