blob: 232450ce61a8d9778d3f58df6cb639ed3e75aafa [file] [log] [blame]
Darrick J. Wong035e00a2016-08-03 11:36:07 +10001/*
2 * Copyright (c) 2014 Red Hat, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18#include "xfs.h"
19#include "xfs_fs.h"
20#include "xfs_shared.h"
21#include "xfs_format.h"
22#include "xfs_log_format.h"
23#include "xfs_trans_resv.h"
24#include "xfs_bit.h"
25#include "xfs_sb.h"
26#include "xfs_mount.h"
27#include "xfs_defer.h"
28#include "xfs_inode.h"
29#include "xfs_trans.h"
30#include "xfs_alloc.h"
31#include "xfs_btree.h"
Darrick J. Wong4b8ed672016-08-03 11:39:05 +100032#include "xfs_rmap.h"
Darrick J. Wong035e00a2016-08-03 11:36:07 +100033#include "xfs_rmap_btree.h"
34#include "xfs_trace.h"
35#include "xfs_cksum.h"
36#include "xfs_error.h"
37#include "xfs_extent_busy.h"
38
Darrick J. Wong4b8ed672016-08-03 11:39:05 +100039/*
40 * Reverse map btree.
41 *
42 * This is a per-ag tree used to track the owner(s) of a given extent. With
43 * reflink it is possible for there to be multiple owners, which is a departure
44 * from classic XFS. Owner records for data extents are inserted when the
45 * extent is mapped and removed when an extent is unmapped. Owner records for
46 * all other block types (i.e. metadata) are inserted when an extent is
47 * allocated and removed when an extent is freed. There can only be one owner
48 * of a metadata extent, usually an inode or some other metadata structure like
49 * an AG btree.
50 *
51 * The rmap btree is part of the free space management, so blocks for the tree
52 * are sourced from the agfl. Hence we need transaction reservation support for
53 * this tree so that the freelist is always large enough. This also impacts on
54 * the minimum space we need to leave free in the AG.
55 *
56 * The tree is ordered by [ag block, owner, offset]. This is a large key size,
57 * but it is the only way to enforce unique keys when a block can be owned by
58 * multiple files at any offset. There's no need to order/search by extent
59 * size for online updating/management of the tree. It is intended that most
60 * reverse lookups will be to find the owner(s) of a particular block, or to
61 * try to recover tree and file data from corrupt primary metadata.
62 */
63
Darrick J. Wong035e00a2016-08-03 11:36:07 +100064static struct xfs_btree_cur *
65xfs_rmapbt_dup_cursor(
66 struct xfs_btree_cur *cur)
67{
68 return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp,
69 cur->bc_private.a.agbp, cur->bc_private.a.agno);
70}
71
Darrick J. Wong4b8ed672016-08-03 11:39:05 +100072STATIC void
73xfs_rmapbt_set_root(
74 struct xfs_btree_cur *cur,
75 union xfs_btree_ptr *ptr,
76 int inc)
77{
78 struct xfs_buf *agbp = cur->bc_private.a.agbp;
79 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
80 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno);
81 int btnum = cur->bc_btnum;
82 struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno);
83
84 ASSERT(ptr->s != 0);
85
86 agf->agf_roots[btnum] = ptr->s;
87 be32_add_cpu(&agf->agf_levels[btnum], inc);
88 pag->pagf_levels[btnum] += inc;
89 xfs_perag_put(pag);
90
91 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
92}
93
94STATIC int
95xfs_rmapbt_alloc_block(
96 struct xfs_btree_cur *cur,
97 union xfs_btree_ptr *start,
98 union xfs_btree_ptr *new,
99 int *stat)
100{
101 int error;
102 xfs_agblock_t bno;
103
104 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
105
106 /* Allocate the new block from the freelist. If we can't, give up. */
107 error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
108 &bno, 1);
109 if (error) {
110 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
111 return error;
112 }
113
114 trace_xfs_rmapbt_alloc_block(cur->bc_mp, cur->bc_private.a.agno,
115 bno, 1);
116 if (bno == NULLAGBLOCK) {
117 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
118 *stat = 0;
119 return 0;
120 }
121
122 xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1,
123 false);
124
125 xfs_trans_agbtree_delta(cur->bc_tp, 1);
126 new->s = cpu_to_be32(bno);
127
128 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
129 *stat = 1;
130 return 0;
131}
132
133STATIC int
134xfs_rmapbt_free_block(
135 struct xfs_btree_cur *cur,
136 struct xfs_buf *bp)
137{
138 struct xfs_buf *agbp = cur->bc_private.a.agbp;
139 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
140 xfs_agblock_t bno;
141 int error;
142
143 bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp));
144 trace_xfs_rmapbt_free_block(cur->bc_mp, cur->bc_private.a.agno,
145 bno, 1);
146 error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1);
147 if (error)
148 return error;
149
150 xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1,
151 XFS_EXTENT_BUSY_SKIP_DISCARD);
152 xfs_trans_agbtree_delta(cur->bc_tp, -1);
153
154 return 0;
155}
156
157STATIC int
158xfs_rmapbt_get_minrecs(
159 struct xfs_btree_cur *cur,
160 int level)
161{
162 return cur->bc_mp->m_rmap_mnr[level != 0];
163}
164
165STATIC int
166xfs_rmapbt_get_maxrecs(
167 struct xfs_btree_cur *cur,
168 int level)
169{
170 return cur->bc_mp->m_rmap_mxr[level != 0];
171}
172
173STATIC void
174xfs_rmapbt_init_key_from_rec(
175 union xfs_btree_key *key,
176 union xfs_btree_rec *rec)
177{
178 key->rmap.rm_startblock = rec->rmap.rm_startblock;
179 key->rmap.rm_owner = rec->rmap.rm_owner;
180 key->rmap.rm_offset = rec->rmap.rm_offset;
181}
182
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000183/*
184 * The high key for a reverse mapping record can be computed by shifting
185 * the startblock and offset to the highest value that would still map
186 * to that record. In practice this means that we add blockcount-1 to
187 * the startblock for all records, and if the record is for a data/attr
188 * fork mapping, we add blockcount-1 to the offset too.
189 */
190STATIC void
191xfs_rmapbt_init_high_key_from_rec(
192 union xfs_btree_key *key,
193 union xfs_btree_rec *rec)
194{
195 __uint64_t off;
196 int adj;
197
198 adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1;
199
200 key->rmap.rm_startblock = rec->rmap.rm_startblock;
201 be32_add_cpu(&key->rmap.rm_startblock, adj);
202 key->rmap.rm_owner = rec->rmap.rm_owner;
203 key->rmap.rm_offset = rec->rmap.rm_offset;
204 if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) ||
205 XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset)))
206 return;
207 off = be64_to_cpu(key->rmap.rm_offset);
208 off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK);
209 key->rmap.rm_offset = cpu_to_be64(off);
210}
211
Darrick J. Wong4b8ed672016-08-03 11:39:05 +1000212STATIC void
213xfs_rmapbt_init_rec_from_cur(
214 struct xfs_btree_cur *cur,
215 union xfs_btree_rec *rec)
216{
217 rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock);
218 rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount);
219 rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner);
220 rec->rmap.rm_offset = cpu_to_be64(
221 xfs_rmap_irec_offset_pack(&cur->bc_rec.r));
222}
223
224STATIC void
225xfs_rmapbt_init_ptr_from_cur(
226 struct xfs_btree_cur *cur,
227 union xfs_btree_ptr *ptr)
228{
229 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
230
231 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
232 ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
233
234 ptr->s = agf->agf_roots[cur->bc_btnum];
235}
236
237STATIC __int64_t
238xfs_rmapbt_key_diff(
239 struct xfs_btree_cur *cur,
240 union xfs_btree_key *key)
241{
242 struct xfs_rmap_irec *rec = &cur->bc_rec.r;
243 struct xfs_rmap_key *kp = &key->rmap;
244 __u64 x, y;
245 __int64_t d;
246
247 d = (__int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock;
248 if (d)
249 return d;
250
251 x = be64_to_cpu(kp->rm_owner);
252 y = rec->rm_owner;
253 if (x > y)
254 return 1;
255 else if (y > x)
256 return -1;
257
258 x = XFS_RMAP_OFF(be64_to_cpu(kp->rm_offset));
259 y = rec->rm_offset;
260 if (x > y)
261 return 1;
262 else if (y > x)
263 return -1;
264 return 0;
265}
266
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000267STATIC __int64_t
268xfs_rmapbt_diff_two_keys(
269 struct xfs_btree_cur *cur,
270 union xfs_btree_key *k1,
271 union xfs_btree_key *k2)
272{
273 struct xfs_rmap_key *kp1 = &k1->rmap;
274 struct xfs_rmap_key *kp2 = &k2->rmap;
275 __int64_t d;
276 __u64 x, y;
277
278 d = (__int64_t)be32_to_cpu(kp1->rm_startblock) -
279 be32_to_cpu(kp2->rm_startblock);
280 if (d)
281 return d;
282
283 x = be64_to_cpu(kp1->rm_owner);
284 y = be64_to_cpu(kp2->rm_owner);
285 if (x > y)
286 return 1;
287 else if (y > x)
288 return -1;
289
290 x = XFS_RMAP_OFF(be64_to_cpu(kp1->rm_offset));
291 y = XFS_RMAP_OFF(be64_to_cpu(kp2->rm_offset));
292 if (x > y)
293 return 1;
294 else if (y > x)
295 return -1;
296 return 0;
297}
298
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000299static bool
300xfs_rmapbt_verify(
301 struct xfs_buf *bp)
302{
303 struct xfs_mount *mp = bp->b_target->bt_mount;
304 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
305 struct xfs_perag *pag = bp->b_pag;
306 unsigned int level;
307
308 /*
309 * magic number and level verification
310 *
311 * During growfs operations, we can't verify the exact level or owner as
312 * the perag is not fully initialised and hence not attached to the
313 * buffer. In this case, check against the maximum tree depth.
314 *
315 * Similarly, during log recovery we will have a perag structure
316 * attached, but the agf information will not yet have been initialised
317 * from the on disk AGF. Again, we can only check against maximum limits
318 * in this case.
319 */
320 if (block->bb_magic != cpu_to_be32(XFS_RMAP_CRC_MAGIC))
321 return false;
322
323 if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
324 return false;
325 if (!xfs_btree_sblock_v5hdr_verify(bp))
326 return false;
327
328 level = be16_to_cpu(block->bb_level);
329 if (pag && pag->pagf_init) {
330 if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi])
331 return false;
332 } else if (level >= mp->m_rmap_maxlevels)
333 return false;
334
335 return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]);
336}
337
338static void
339xfs_rmapbt_read_verify(
340 struct xfs_buf *bp)
341{
342 if (!xfs_btree_sblock_verify_crc(bp))
343 xfs_buf_ioerror(bp, -EFSBADCRC);
344 else if (!xfs_rmapbt_verify(bp))
345 xfs_buf_ioerror(bp, -EFSCORRUPTED);
346
347 if (bp->b_error) {
348 trace_xfs_btree_corrupt(bp, _RET_IP_);
349 xfs_verifier_error(bp);
350 }
351}
352
353static void
354xfs_rmapbt_write_verify(
355 struct xfs_buf *bp)
356{
357 if (!xfs_rmapbt_verify(bp)) {
358 trace_xfs_btree_corrupt(bp, _RET_IP_);
359 xfs_buf_ioerror(bp, -EFSCORRUPTED);
360 xfs_verifier_error(bp);
361 return;
362 }
363 xfs_btree_sblock_calc_crc(bp);
364
365}
366
367const struct xfs_buf_ops xfs_rmapbt_buf_ops = {
368 .name = "xfs_rmapbt",
369 .verify_read = xfs_rmapbt_read_verify,
370 .verify_write = xfs_rmapbt_write_verify,
371};
372
Darrick J. Wong4b8ed672016-08-03 11:39:05 +1000373#if defined(DEBUG) || defined(XFS_WARN)
374STATIC int
375xfs_rmapbt_keys_inorder(
376 struct xfs_btree_cur *cur,
377 union xfs_btree_key *k1,
378 union xfs_btree_key *k2)
379{
380 __uint32_t x;
381 __uint32_t y;
382 __uint64_t a;
383 __uint64_t b;
384
385 x = be32_to_cpu(k1->rmap.rm_startblock);
386 y = be32_to_cpu(k2->rmap.rm_startblock);
387 if (x < y)
388 return 1;
389 else if (x > y)
390 return 0;
391 a = be64_to_cpu(k1->rmap.rm_owner);
392 b = be64_to_cpu(k2->rmap.rm_owner);
393 if (a < b)
394 return 1;
395 else if (a > b)
396 return 0;
397 a = XFS_RMAP_OFF(be64_to_cpu(k1->rmap.rm_offset));
398 b = XFS_RMAP_OFF(be64_to_cpu(k2->rmap.rm_offset));
399 if (a <= b)
400 return 1;
401 return 0;
402}
403
404STATIC int
405xfs_rmapbt_recs_inorder(
406 struct xfs_btree_cur *cur,
407 union xfs_btree_rec *r1,
408 union xfs_btree_rec *r2)
409{
410 __uint32_t x;
411 __uint32_t y;
412 __uint64_t a;
413 __uint64_t b;
414
415 x = be32_to_cpu(r1->rmap.rm_startblock);
416 y = be32_to_cpu(r2->rmap.rm_startblock);
417 if (x < y)
418 return 1;
419 else if (x > y)
420 return 0;
421 a = be64_to_cpu(r1->rmap.rm_owner);
422 b = be64_to_cpu(r2->rmap.rm_owner);
423 if (a < b)
424 return 1;
425 else if (a > b)
426 return 0;
427 a = XFS_RMAP_OFF(be64_to_cpu(r1->rmap.rm_offset));
428 b = XFS_RMAP_OFF(be64_to_cpu(r2->rmap.rm_offset));
429 if (a <= b)
430 return 1;
431 return 0;
432}
433#endif /* DEBUG */
434
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000435static const struct xfs_btree_ops xfs_rmapbt_ops = {
436 .rec_len = sizeof(struct xfs_rmap_rec),
437 .key_len = 2 * sizeof(struct xfs_rmap_key),
438
439 .dup_cursor = xfs_rmapbt_dup_cursor,
Darrick J. Wong4b8ed672016-08-03 11:39:05 +1000440 .set_root = xfs_rmapbt_set_root,
441 .alloc_block = xfs_rmapbt_alloc_block,
442 .free_block = xfs_rmapbt_free_block,
443 .get_minrecs = xfs_rmapbt_get_minrecs,
444 .get_maxrecs = xfs_rmapbt_get_maxrecs,
445 .init_key_from_rec = xfs_rmapbt_init_key_from_rec,
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000446 .init_high_key_from_rec = xfs_rmapbt_init_high_key_from_rec,
Darrick J. Wong4b8ed672016-08-03 11:39:05 +1000447 .init_rec_from_cur = xfs_rmapbt_init_rec_from_cur,
448 .init_ptr_from_cur = xfs_rmapbt_init_ptr_from_cur,
449 .key_diff = xfs_rmapbt_key_diff,
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000450 .buf_ops = &xfs_rmapbt_buf_ops,
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000451 .diff_two_keys = xfs_rmapbt_diff_two_keys,
Darrick J. Wong4b8ed672016-08-03 11:39:05 +1000452#if defined(DEBUG) || defined(XFS_WARN)
453 .keys_inorder = xfs_rmapbt_keys_inorder,
454 .recs_inorder = xfs_rmapbt_recs_inorder,
455#endif
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000456
457 .get_leaf_keys = xfs_btree_get_leaf_keys_overlapped,
458 .get_node_keys = xfs_btree_get_node_keys_overlapped,
459 .update_keys = xfs_btree_update_keys_overlapped,
460};
461
462/*
463 * Allocate a new allocation btree cursor.
464 */
465struct xfs_btree_cur *
466xfs_rmapbt_init_cursor(
467 struct xfs_mount *mp,
468 struct xfs_trans *tp,
469 struct xfs_buf *agbp,
470 xfs_agnumber_t agno)
471{
472 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
473 struct xfs_btree_cur *cur;
474
475 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
476 cur->bc_tp = tp;
477 cur->bc_mp = mp;
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000478 /* Overlapping btree; 2 keys per pointer. */
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000479 cur->bc_btnum = XFS_BTNUM_RMAP;
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000480 cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING;
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000481 cur->bc_blocklog = mp->m_sb.sb_blocklog;
482 cur->bc_ops = &xfs_rmapbt_ops;
483 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]);
484
485 cur->bc_private.a.agbp = agbp;
486 cur->bc_private.a.agno = agno;
487
488 return cur;
489}
490
491/*
492 * Calculate number of records in an rmap btree block.
493 */
494int
495xfs_rmapbt_maxrecs(
496 struct xfs_mount *mp,
497 int blocklen,
498 int leaf)
499{
500 blocklen -= XFS_RMAP_BLOCK_LEN;
501
502 if (leaf)
503 return blocklen / sizeof(struct xfs_rmap_rec);
504 return blocklen /
Darrick J. Wongcfed56a2016-08-03 11:40:56 +1000505 (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t));
Darrick J. Wong035e00a2016-08-03 11:36:07 +1000506}
507
508/* Compute the maximum height of an rmap btree. */
509void
510xfs_rmapbt_compute_maxlevels(
511 struct xfs_mount *mp)
512{
513 mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(mp,
514 mp->m_rmap_mnr, mp->m_sb.sb_agblocks);
515}