Loading...
Note: File does not exist in v3.15.
1// SPDX-License-Identifier: GPL-2.0+
2/*
3 * Copyright (C) 2016 Oracle. All Rights Reserved.
4 * Author: Darrick J. Wong <darrick.wong@oracle.com>
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_mount.h"
13#include "xfs_defer.h"
14#include "xfs_btree.h"
15#include "xfs_bmap.h"
16#include "xfs_refcount_btree.h"
17#include "xfs_alloc.h"
18#include "xfs_errortag.h"
19#include "xfs_error.h"
20#include "xfs_trace.h"
21#include "xfs_trans.h"
22#include "xfs_bit.h"
23#include "xfs_refcount.h"
24#include "xfs_rmap.h"
25
26/* Allowable refcount adjustment amounts. */
27enum xfs_refc_adjust_op {
28 XFS_REFCOUNT_ADJUST_INCREASE = 1,
29 XFS_REFCOUNT_ADJUST_DECREASE = -1,
30 XFS_REFCOUNT_ADJUST_COW_ALLOC = 0,
31 XFS_REFCOUNT_ADJUST_COW_FREE = -1,
32};
33
34STATIC int __xfs_refcount_cow_alloc(struct xfs_btree_cur *rcur,
35 xfs_agblock_t agbno, xfs_extlen_t aglen);
36STATIC int __xfs_refcount_cow_free(struct xfs_btree_cur *rcur,
37 xfs_agblock_t agbno, xfs_extlen_t aglen);
38
39/*
40 * Look up the first record less than or equal to [bno, len] in the btree
41 * given by cur.
42 */
43int
44xfs_refcount_lookup_le(
45 struct xfs_btree_cur *cur,
46 xfs_agblock_t bno,
47 int *stat)
48{
49 trace_xfs_refcount_lookup(cur->bc_mp, cur->bc_private.a.agno, bno,
50 XFS_LOOKUP_LE);
51 cur->bc_rec.rc.rc_startblock = bno;
52 cur->bc_rec.rc.rc_blockcount = 0;
53 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
54}
55
56/*
57 * Look up the first record greater than or equal to [bno, len] in the btree
58 * given by cur.
59 */
60int
61xfs_refcount_lookup_ge(
62 struct xfs_btree_cur *cur,
63 xfs_agblock_t bno,
64 int *stat)
65{
66 trace_xfs_refcount_lookup(cur->bc_mp, cur->bc_private.a.agno, bno,
67 XFS_LOOKUP_GE);
68 cur->bc_rec.rc.rc_startblock = bno;
69 cur->bc_rec.rc.rc_blockcount = 0;
70 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
71}
72
73/*
74 * Look up the first record equal to [bno, len] in the btree
75 * given by cur.
76 */
77int
78xfs_refcount_lookup_eq(
79 struct xfs_btree_cur *cur,
80 xfs_agblock_t bno,
81 int *stat)
82{
83 trace_xfs_refcount_lookup(cur->bc_mp, cur->bc_private.a.agno, bno,
84 XFS_LOOKUP_LE);
85 cur->bc_rec.rc.rc_startblock = bno;
86 cur->bc_rec.rc.rc_blockcount = 0;
87 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
88}
89
90/* Convert on-disk record to in-core format. */
91void
92xfs_refcount_btrec_to_irec(
93 union xfs_btree_rec *rec,
94 struct xfs_refcount_irec *irec)
95{
96 irec->rc_startblock = be32_to_cpu(rec->refc.rc_startblock);
97 irec->rc_blockcount = be32_to_cpu(rec->refc.rc_blockcount);
98 irec->rc_refcount = be32_to_cpu(rec->refc.rc_refcount);
99}
100
101/*
102 * Get the data from the pointed-to record.
103 */
104int
105xfs_refcount_get_rec(
106 struct xfs_btree_cur *cur,
107 struct xfs_refcount_irec *irec,
108 int *stat)
109{
110 struct xfs_mount *mp = cur->bc_mp;
111 xfs_agnumber_t agno = cur->bc_private.a.agno;
112 union xfs_btree_rec *rec;
113 int error;
114 xfs_agblock_t realstart;
115
116 error = xfs_btree_get_rec(cur, &rec, stat);
117 if (error || !*stat)
118 return error;
119
120 xfs_refcount_btrec_to_irec(rec, irec);
121
122 agno = cur->bc_private.a.agno;
123 if (irec->rc_blockcount == 0 || irec->rc_blockcount > MAXREFCEXTLEN)
124 goto out_bad_rec;
125
126 /* handle special COW-staging state */
127 realstart = irec->rc_startblock;
128 if (realstart & XFS_REFC_COW_START) {
129 if (irec->rc_refcount != 1)
130 goto out_bad_rec;
131 realstart &= ~XFS_REFC_COW_START;
132 } else if (irec->rc_refcount < 2) {
133 goto out_bad_rec;
134 }
135
136 /* check for valid extent range, including overflow */
137 if (!xfs_verify_agbno(mp, agno, realstart))
138 goto out_bad_rec;
139 if (realstart > realstart + irec->rc_blockcount)
140 goto out_bad_rec;
141 if (!xfs_verify_agbno(mp, agno, realstart + irec->rc_blockcount - 1))
142 goto out_bad_rec;
143
144 if (irec->rc_refcount == 0 || irec->rc_refcount > MAXREFCOUNT)
145 goto out_bad_rec;
146
147 trace_xfs_refcount_get(cur->bc_mp, cur->bc_private.a.agno, irec);
148 return 0;
149
150out_bad_rec:
151 xfs_warn(mp,
152 "Refcount BTree record corruption in AG %d detected!", agno);
153 xfs_warn(mp,
154 "Start block 0x%x, block count 0x%x, references 0x%x",
155 irec->rc_startblock, irec->rc_blockcount, irec->rc_refcount);
156 return -EFSCORRUPTED;
157}
158
159/*
160 * Update the record referred to by cur to the value given
161 * by [bno, len, refcount].
162 * This either works (return 0) or gets an EFSCORRUPTED error.
163 */
164STATIC int
165xfs_refcount_update(
166 struct xfs_btree_cur *cur,
167 struct xfs_refcount_irec *irec)
168{
169 union xfs_btree_rec rec;
170 int error;
171
172 trace_xfs_refcount_update(cur->bc_mp, cur->bc_private.a.agno, irec);
173 rec.refc.rc_startblock = cpu_to_be32(irec->rc_startblock);
174 rec.refc.rc_blockcount = cpu_to_be32(irec->rc_blockcount);
175 rec.refc.rc_refcount = cpu_to_be32(irec->rc_refcount);
176 error = xfs_btree_update(cur, &rec);
177 if (error)
178 trace_xfs_refcount_update_error(cur->bc_mp,
179 cur->bc_private.a.agno, error, _RET_IP_);
180 return error;
181}
182
183/*
184 * Insert the record referred to by cur to the value given
185 * by [bno, len, refcount].
186 * This either works (return 0) or gets an EFSCORRUPTED error.
187 */
188int
189xfs_refcount_insert(
190 struct xfs_btree_cur *cur,
191 struct xfs_refcount_irec *irec,
192 int *i)
193{
194 int error;
195
196 trace_xfs_refcount_insert(cur->bc_mp, cur->bc_private.a.agno, irec);
197 cur->bc_rec.rc.rc_startblock = irec->rc_startblock;
198 cur->bc_rec.rc.rc_blockcount = irec->rc_blockcount;
199 cur->bc_rec.rc.rc_refcount = irec->rc_refcount;
200 error = xfs_btree_insert(cur, i);
201 if (error)
202 goto out_error;
203 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, *i == 1, out_error);
204
205out_error:
206 if (error)
207 trace_xfs_refcount_insert_error(cur->bc_mp,
208 cur->bc_private.a.agno, error, _RET_IP_);
209 return error;
210}
211
212/*
213 * Remove the record referred to by cur, then set the pointer to the spot
214 * where the record could be re-inserted, in case we want to increment or
215 * decrement the cursor.
216 * This either works (return 0) or gets an EFSCORRUPTED error.
217 */
218STATIC int
219xfs_refcount_delete(
220 struct xfs_btree_cur *cur,
221 int *i)
222{
223 struct xfs_refcount_irec irec;
224 int found_rec;
225 int error;
226
227 error = xfs_refcount_get_rec(cur, &irec, &found_rec);
228 if (error)
229 goto out_error;
230 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
231 trace_xfs_refcount_delete(cur->bc_mp, cur->bc_private.a.agno, &irec);
232 error = xfs_btree_delete(cur, i);
233 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, *i == 1, out_error);
234 if (error)
235 goto out_error;
236 error = xfs_refcount_lookup_ge(cur, irec.rc_startblock, &found_rec);
237out_error:
238 if (error)
239 trace_xfs_refcount_delete_error(cur->bc_mp,
240 cur->bc_private.a.agno, error, _RET_IP_);
241 return error;
242}
243
244/*
245 * Adjusting the Reference Count
246 *
247 * As stated elsewhere, the reference count btree (refcbt) stores
248 * >1 reference counts for extents of physical blocks. In this
249 * operation, we're either raising or lowering the reference count of
250 * some subrange stored in the tree:
251 *
252 * <------ adjustment range ------>
253 * ----+ +---+-----+ +--+--------+---------
254 * 2 | | 3 | 4 | |17| 55 | 10
255 * ----+ +---+-----+ +--+--------+---------
256 * X axis is physical blocks number;
257 * reference counts are the numbers inside the rectangles
258 *
259 * The first thing we need to do is to ensure that there are no
260 * refcount extents crossing either boundary of the range to be
261 * adjusted. For any extent that does cross a boundary, split it into
262 * two extents so that we can increment the refcount of one of the
263 * pieces later:
264 *
265 * <------ adjustment range ------>
266 * ----+ +---+-----+ +--+--------+----+----
267 * 2 | | 3 | 2 | |17| 55 | 10 | 10
268 * ----+ +---+-----+ +--+--------+----+----
269 *
270 * For this next step, let's assume that all the physical blocks in
271 * the adjustment range are mapped to a file and are therefore in use
272 * at least once. Therefore, we can infer that any gap in the
273 * refcount tree within the adjustment range represents a physical
274 * extent with refcount == 1:
275 *
276 * <------ adjustment range ------>
277 * ----+---+---+-----+-+--+--------+----+----
278 * 2 |"1"| 3 | 2 |1|17| 55 | 10 | 10
279 * ----+---+---+-----+-+--+--------+----+----
280 * ^
281 *
282 * For each extent that falls within the interval range, figure out
283 * which extent is to the left or the right of that extent. Now we
284 * have a left, current, and right extent. If the new reference count
285 * of the center extent enables us to merge left, center, and right
286 * into one record covering all three, do so. If the center extent is
287 * at the left end of the range, abuts the left extent, and its new
288 * reference count matches the left extent's record, then merge them.
289 * If the center extent is at the right end of the range, abuts the
290 * right extent, and the reference counts match, merge those. In the
291 * example, we can left merge (assuming an increment operation):
292 *
293 * <------ adjustment range ------>
294 * --------+---+-----+-+--+--------+----+----
295 * 2 | 3 | 2 |1|17| 55 | 10 | 10
296 * --------+---+-----+-+--+--------+----+----
297 * ^
298 *
299 * For all other extents within the range, adjust the reference count
300 * or delete it if the refcount falls below 2. If we were
301 * incrementing, the end result looks like this:
302 *
303 * <------ adjustment range ------>
304 * --------+---+-----+-+--+--------+----+----
305 * 2 | 4 | 3 |2|18| 56 | 11 | 10
306 * --------+---+-----+-+--+--------+----+----
307 *
308 * The result of a decrement operation looks as such:
309 *
310 * <------ adjustment range ------>
311 * ----+ +---+ +--+--------+----+----
312 * 2 | | 2 | |16| 54 | 9 | 10
313 * ----+ +---+ +--+--------+----+----
314 * DDDD 111111DD
315 *
316 * The blocks marked "D" are freed; the blocks marked "1" are only
317 * referenced once and therefore the record is removed from the
318 * refcount btree.
319 */
320
321/* Next block after this extent. */
322static inline xfs_agblock_t
323xfs_refc_next(
324 struct xfs_refcount_irec *rc)
325{
326 return rc->rc_startblock + rc->rc_blockcount;
327}
328
329/*
330 * Split a refcount extent that crosses agbno.
331 */
332STATIC int
333xfs_refcount_split_extent(
334 struct xfs_btree_cur *cur,
335 xfs_agblock_t agbno,
336 bool *shape_changed)
337{
338 struct xfs_refcount_irec rcext, tmp;
339 int found_rec;
340 int error;
341
342 *shape_changed = false;
343 error = xfs_refcount_lookup_le(cur, agbno, &found_rec);
344 if (error)
345 goto out_error;
346 if (!found_rec)
347 return 0;
348
349 error = xfs_refcount_get_rec(cur, &rcext, &found_rec);
350 if (error)
351 goto out_error;
352 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
353 if (rcext.rc_startblock == agbno || xfs_refc_next(&rcext) <= agbno)
354 return 0;
355
356 *shape_changed = true;
357 trace_xfs_refcount_split_extent(cur->bc_mp, cur->bc_private.a.agno,
358 &rcext, agbno);
359
360 /* Establish the right extent. */
361 tmp = rcext;
362 tmp.rc_startblock = agbno;
363 tmp.rc_blockcount -= (agbno - rcext.rc_startblock);
364 error = xfs_refcount_update(cur, &tmp);
365 if (error)
366 goto out_error;
367
368 /* Insert the left extent. */
369 tmp = rcext;
370 tmp.rc_blockcount = agbno - rcext.rc_startblock;
371 error = xfs_refcount_insert(cur, &tmp, &found_rec);
372 if (error)
373 goto out_error;
374 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
375 return error;
376
377out_error:
378 trace_xfs_refcount_split_extent_error(cur->bc_mp,
379 cur->bc_private.a.agno, error, _RET_IP_);
380 return error;
381}
382
383/*
384 * Merge the left, center, and right extents.
385 */
386STATIC int
387xfs_refcount_merge_center_extents(
388 struct xfs_btree_cur *cur,
389 struct xfs_refcount_irec *left,
390 struct xfs_refcount_irec *center,
391 struct xfs_refcount_irec *right,
392 unsigned long long extlen,
393 xfs_extlen_t *aglen)
394{
395 int error;
396 int found_rec;
397
398 trace_xfs_refcount_merge_center_extents(cur->bc_mp,
399 cur->bc_private.a.agno, left, center, right);
400
401 /*
402 * Make sure the center and right extents are not in the btree.
403 * If the center extent was synthesized, the first delete call
404 * removes the right extent and we skip the second deletion.
405 * If center and right were in the btree, then the first delete
406 * call removes the center and the second one removes the right
407 * extent.
408 */
409 error = xfs_refcount_lookup_ge(cur, center->rc_startblock,
410 &found_rec);
411 if (error)
412 goto out_error;
413 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
414
415 error = xfs_refcount_delete(cur, &found_rec);
416 if (error)
417 goto out_error;
418 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
419
420 if (center->rc_refcount > 1) {
421 error = xfs_refcount_delete(cur, &found_rec);
422 if (error)
423 goto out_error;
424 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
425 out_error);
426 }
427
428 /* Enlarge the left extent. */
429 error = xfs_refcount_lookup_le(cur, left->rc_startblock,
430 &found_rec);
431 if (error)
432 goto out_error;
433 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
434
435 left->rc_blockcount = extlen;
436 error = xfs_refcount_update(cur, left);
437 if (error)
438 goto out_error;
439
440 *aglen = 0;
441 return error;
442
443out_error:
444 trace_xfs_refcount_merge_center_extents_error(cur->bc_mp,
445 cur->bc_private.a.agno, error, _RET_IP_);
446 return error;
447}
448
449/*
450 * Merge with the left extent.
451 */
452STATIC int
453xfs_refcount_merge_left_extent(
454 struct xfs_btree_cur *cur,
455 struct xfs_refcount_irec *left,
456 struct xfs_refcount_irec *cleft,
457 xfs_agblock_t *agbno,
458 xfs_extlen_t *aglen)
459{
460 int error;
461 int found_rec;
462
463 trace_xfs_refcount_merge_left_extent(cur->bc_mp,
464 cur->bc_private.a.agno, left, cleft);
465
466 /* If the extent at agbno (cleft) wasn't synthesized, remove it. */
467 if (cleft->rc_refcount > 1) {
468 error = xfs_refcount_lookup_le(cur, cleft->rc_startblock,
469 &found_rec);
470 if (error)
471 goto out_error;
472 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
473 out_error);
474
475 error = xfs_refcount_delete(cur, &found_rec);
476 if (error)
477 goto out_error;
478 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
479 out_error);
480 }
481
482 /* Enlarge the left extent. */
483 error = xfs_refcount_lookup_le(cur, left->rc_startblock,
484 &found_rec);
485 if (error)
486 goto out_error;
487 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
488
489 left->rc_blockcount += cleft->rc_blockcount;
490 error = xfs_refcount_update(cur, left);
491 if (error)
492 goto out_error;
493
494 *agbno += cleft->rc_blockcount;
495 *aglen -= cleft->rc_blockcount;
496 return error;
497
498out_error:
499 trace_xfs_refcount_merge_left_extent_error(cur->bc_mp,
500 cur->bc_private.a.agno, error, _RET_IP_);
501 return error;
502}
503
504/*
505 * Merge with the right extent.
506 */
507STATIC int
508xfs_refcount_merge_right_extent(
509 struct xfs_btree_cur *cur,
510 struct xfs_refcount_irec *right,
511 struct xfs_refcount_irec *cright,
512 xfs_extlen_t *aglen)
513{
514 int error;
515 int found_rec;
516
517 trace_xfs_refcount_merge_right_extent(cur->bc_mp,
518 cur->bc_private.a.agno, cright, right);
519
520 /*
521 * If the extent ending at agbno+aglen (cright) wasn't synthesized,
522 * remove it.
523 */
524 if (cright->rc_refcount > 1) {
525 error = xfs_refcount_lookup_le(cur, cright->rc_startblock,
526 &found_rec);
527 if (error)
528 goto out_error;
529 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
530 out_error);
531
532 error = xfs_refcount_delete(cur, &found_rec);
533 if (error)
534 goto out_error;
535 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
536 out_error);
537 }
538
539 /* Enlarge the right extent. */
540 error = xfs_refcount_lookup_le(cur, right->rc_startblock,
541 &found_rec);
542 if (error)
543 goto out_error;
544 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
545
546 right->rc_startblock -= cright->rc_blockcount;
547 right->rc_blockcount += cright->rc_blockcount;
548 error = xfs_refcount_update(cur, right);
549 if (error)
550 goto out_error;
551
552 *aglen -= cright->rc_blockcount;
553 return error;
554
555out_error:
556 trace_xfs_refcount_merge_right_extent_error(cur->bc_mp,
557 cur->bc_private.a.agno, error, _RET_IP_);
558 return error;
559}
560
561#define XFS_FIND_RCEXT_SHARED 1
562#define XFS_FIND_RCEXT_COW 2
563/*
564 * Find the left extent and the one after it (cleft). This function assumes
565 * that we've already split any extent crossing agbno.
566 */
567STATIC int
568xfs_refcount_find_left_extents(
569 struct xfs_btree_cur *cur,
570 struct xfs_refcount_irec *left,
571 struct xfs_refcount_irec *cleft,
572 xfs_agblock_t agbno,
573 xfs_extlen_t aglen,
574 int flags)
575{
576 struct xfs_refcount_irec tmp;
577 int error;
578 int found_rec;
579
580 left->rc_startblock = cleft->rc_startblock = NULLAGBLOCK;
581 error = xfs_refcount_lookup_le(cur, agbno - 1, &found_rec);
582 if (error)
583 goto out_error;
584 if (!found_rec)
585 return 0;
586
587 error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
588 if (error)
589 goto out_error;
590 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
591
592 if (xfs_refc_next(&tmp) != agbno)
593 return 0;
594 if ((flags & XFS_FIND_RCEXT_SHARED) && tmp.rc_refcount < 2)
595 return 0;
596 if ((flags & XFS_FIND_RCEXT_COW) && tmp.rc_refcount > 1)
597 return 0;
598 /* We have a left extent; retrieve (or invent) the next right one */
599 *left = tmp;
600
601 error = xfs_btree_increment(cur, 0, &found_rec);
602 if (error)
603 goto out_error;
604 if (found_rec) {
605 error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
606 if (error)
607 goto out_error;
608 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
609 out_error);
610
611 /* if tmp starts at the end of our range, just use that */
612 if (tmp.rc_startblock == agbno)
613 *cleft = tmp;
614 else {
615 /*
616 * There's a gap in the refcntbt at the start of the
617 * range we're interested in (refcount == 1) so
618 * synthesize the implied extent and pass it back.
619 * We assume here that the agbno/aglen range was
620 * passed in from a data fork extent mapping and
621 * therefore is allocated to exactly one owner.
622 */
623 cleft->rc_startblock = agbno;
624 cleft->rc_blockcount = min(aglen,
625 tmp.rc_startblock - agbno);
626 cleft->rc_refcount = 1;
627 }
628 } else {
629 /*
630 * No extents, so pretend that there's one covering the whole
631 * range.
632 */
633 cleft->rc_startblock = agbno;
634 cleft->rc_blockcount = aglen;
635 cleft->rc_refcount = 1;
636 }
637 trace_xfs_refcount_find_left_extent(cur->bc_mp, cur->bc_private.a.agno,
638 left, cleft, agbno);
639 return error;
640
641out_error:
642 trace_xfs_refcount_find_left_extent_error(cur->bc_mp,
643 cur->bc_private.a.agno, error, _RET_IP_);
644 return error;
645}
646
647/*
648 * Find the right extent and the one before it (cright). This function
649 * assumes that we've already split any extents crossing agbno + aglen.
650 */
651STATIC int
652xfs_refcount_find_right_extents(
653 struct xfs_btree_cur *cur,
654 struct xfs_refcount_irec *right,
655 struct xfs_refcount_irec *cright,
656 xfs_agblock_t agbno,
657 xfs_extlen_t aglen,
658 int flags)
659{
660 struct xfs_refcount_irec tmp;
661 int error;
662 int found_rec;
663
664 right->rc_startblock = cright->rc_startblock = NULLAGBLOCK;
665 error = xfs_refcount_lookup_ge(cur, agbno + aglen, &found_rec);
666 if (error)
667 goto out_error;
668 if (!found_rec)
669 return 0;
670
671 error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
672 if (error)
673 goto out_error;
674 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1, out_error);
675
676 if (tmp.rc_startblock != agbno + aglen)
677 return 0;
678 if ((flags & XFS_FIND_RCEXT_SHARED) && tmp.rc_refcount < 2)
679 return 0;
680 if ((flags & XFS_FIND_RCEXT_COW) && tmp.rc_refcount > 1)
681 return 0;
682 /* We have a right extent; retrieve (or invent) the next left one */
683 *right = tmp;
684
685 error = xfs_btree_decrement(cur, 0, &found_rec);
686 if (error)
687 goto out_error;
688 if (found_rec) {
689 error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
690 if (error)
691 goto out_error;
692 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, found_rec == 1,
693 out_error);
694
695 /* if tmp ends at the end of our range, just use that */
696 if (xfs_refc_next(&tmp) == agbno + aglen)
697 *cright = tmp;
698 else {
699 /*
700 * There's a gap in the refcntbt at the end of the
701 * range we're interested in (refcount == 1) so
702 * create the implied extent and pass it back.
703 * We assume here that the agbno/aglen range was
704 * passed in from a data fork extent mapping and
705 * therefore is allocated to exactly one owner.
706 */
707 cright->rc_startblock = max(agbno, xfs_refc_next(&tmp));
708 cright->rc_blockcount = right->rc_startblock -
709 cright->rc_startblock;
710 cright->rc_refcount = 1;
711 }
712 } else {
713 /*
714 * No extents, so pretend that there's one covering the whole
715 * range.
716 */
717 cright->rc_startblock = agbno;
718 cright->rc_blockcount = aglen;
719 cright->rc_refcount = 1;
720 }
721 trace_xfs_refcount_find_right_extent(cur->bc_mp, cur->bc_private.a.agno,
722 cright, right, agbno + aglen);
723 return error;
724
725out_error:
726 trace_xfs_refcount_find_right_extent_error(cur->bc_mp,
727 cur->bc_private.a.agno, error, _RET_IP_);
728 return error;
729}
730
731/* Is this extent valid? */
732static inline bool
733xfs_refc_valid(
734 struct xfs_refcount_irec *rc)
735{
736 return rc->rc_startblock != NULLAGBLOCK;
737}
738
739/*
740 * Try to merge with any extents on the boundaries of the adjustment range.
741 */
742STATIC int
743xfs_refcount_merge_extents(
744 struct xfs_btree_cur *cur,
745 xfs_agblock_t *agbno,
746 xfs_extlen_t *aglen,
747 enum xfs_refc_adjust_op adjust,
748 int flags,
749 bool *shape_changed)
750{
751 struct xfs_refcount_irec left = {0}, cleft = {0};
752 struct xfs_refcount_irec cright = {0}, right = {0};
753 int error;
754 unsigned long long ulen;
755 bool cequal;
756
757 *shape_changed = false;
758 /*
759 * Find the extent just below agbno [left], just above agbno [cleft],
760 * just below (agbno + aglen) [cright], and just above (agbno + aglen)
761 * [right].
762 */
763 error = xfs_refcount_find_left_extents(cur, &left, &cleft, *agbno,
764 *aglen, flags);
765 if (error)
766 return error;
767 error = xfs_refcount_find_right_extents(cur, &right, &cright, *agbno,
768 *aglen, flags);
769 if (error)
770 return error;
771
772 /* No left or right extent to merge; exit. */
773 if (!xfs_refc_valid(&left) && !xfs_refc_valid(&right))
774 return 0;
775
776 cequal = (cleft.rc_startblock == cright.rc_startblock) &&
777 (cleft.rc_blockcount == cright.rc_blockcount);
778
779 /* Try to merge left, cleft, and right. cleft must == cright. */
780 ulen = (unsigned long long)left.rc_blockcount + cleft.rc_blockcount +
781 right.rc_blockcount;
782 if (xfs_refc_valid(&left) && xfs_refc_valid(&right) &&
783 xfs_refc_valid(&cleft) && xfs_refc_valid(&cright) && cequal &&
784 left.rc_refcount == cleft.rc_refcount + adjust &&
785 right.rc_refcount == cleft.rc_refcount + adjust &&
786 ulen < MAXREFCEXTLEN) {
787 *shape_changed = true;
788 return xfs_refcount_merge_center_extents(cur, &left, &cleft,
789 &right, ulen, aglen);
790 }
791
792 /* Try to merge left and cleft. */
793 ulen = (unsigned long long)left.rc_blockcount + cleft.rc_blockcount;
794 if (xfs_refc_valid(&left) && xfs_refc_valid(&cleft) &&
795 left.rc_refcount == cleft.rc_refcount + adjust &&
796 ulen < MAXREFCEXTLEN) {
797 *shape_changed = true;
798 error = xfs_refcount_merge_left_extent(cur, &left, &cleft,
799 agbno, aglen);
800 if (error)
801 return error;
802
803 /*
804 * If we just merged left + cleft and cleft == cright,
805 * we no longer have a cright to merge with right. We're done.
806 */
807 if (cequal)
808 return 0;
809 }
810
811 /* Try to merge cright and right. */
812 ulen = (unsigned long long)right.rc_blockcount + cright.rc_blockcount;
813 if (xfs_refc_valid(&right) && xfs_refc_valid(&cright) &&
814 right.rc_refcount == cright.rc_refcount + adjust &&
815 ulen < MAXREFCEXTLEN) {
816 *shape_changed = true;
817 return xfs_refcount_merge_right_extent(cur, &right, &cright,
818 aglen);
819 }
820
821 return error;
822}
823
824/*
825 * XXX: This is a pretty hand-wavy estimate. The penalty for guessing
826 * true incorrectly is a shutdown FS; the penalty for guessing false
827 * incorrectly is more transaction rolls than might be necessary.
828 * Be conservative here.
829 */
830static bool
831xfs_refcount_still_have_space(
832 struct xfs_btree_cur *cur)
833{
834 unsigned long overhead;
835
836 overhead = cur->bc_private.a.priv.refc.shape_changes *
837 xfs_allocfree_log_count(cur->bc_mp, 1);
838 overhead *= cur->bc_mp->m_sb.sb_blocksize;
839
840 /*
841 * Only allow 2 refcount extent updates per transaction if the
842 * refcount continue update "error" has been injected.
843 */
844 if (cur->bc_private.a.priv.refc.nr_ops > 2 &&
845 XFS_TEST_ERROR(false, cur->bc_mp,
846 XFS_ERRTAG_REFCOUNT_CONTINUE_UPDATE))
847 return false;
848
849 if (cur->bc_private.a.priv.refc.nr_ops == 0)
850 return true;
851 else if (overhead > cur->bc_tp->t_log_res)
852 return false;
853 return cur->bc_tp->t_log_res - overhead >
854 cur->bc_private.a.priv.refc.nr_ops * XFS_REFCOUNT_ITEM_OVERHEAD;
855}
856
857/*
858 * Adjust the refcounts of middle extents. At this point we should have
859 * split extents that crossed the adjustment range; merged with adjacent
860 * extents; and updated agbno/aglen to reflect the merges. Therefore,
861 * all we have to do is update the extents inside [agbno, agbno + aglen].
862 */
863STATIC int
864xfs_refcount_adjust_extents(
865 struct xfs_btree_cur *cur,
866 xfs_agblock_t *agbno,
867 xfs_extlen_t *aglen,
868 enum xfs_refc_adjust_op adj,
869 struct xfs_owner_info *oinfo)
870{
871 struct xfs_refcount_irec ext, tmp;
872 int error;
873 int found_rec, found_tmp;
874 xfs_fsblock_t fsbno;
875
876 /* Merging did all the work already. */
877 if (*aglen == 0)
878 return 0;
879
880 error = xfs_refcount_lookup_ge(cur, *agbno, &found_rec);
881 if (error)
882 goto out_error;
883
884 while (*aglen > 0 && xfs_refcount_still_have_space(cur)) {
885 error = xfs_refcount_get_rec(cur, &ext, &found_rec);
886 if (error)
887 goto out_error;
888 if (!found_rec) {
889 ext.rc_startblock = cur->bc_mp->m_sb.sb_agblocks;
890 ext.rc_blockcount = 0;
891 ext.rc_refcount = 0;
892 }
893
894 /*
895 * Deal with a hole in the refcount tree; if a file maps to
896 * these blocks and there's no refcountbt record, pretend that
897 * there is one with refcount == 1.
898 */
899 if (ext.rc_startblock != *agbno) {
900 tmp.rc_startblock = *agbno;
901 tmp.rc_blockcount = min(*aglen,
902 ext.rc_startblock - *agbno);
903 tmp.rc_refcount = 1 + adj;
904 trace_xfs_refcount_modify_extent(cur->bc_mp,
905 cur->bc_private.a.agno, &tmp);
906
907 /*
908 * Either cover the hole (increment) or
909 * delete the range (decrement).
910 */
911 if (tmp.rc_refcount) {
912 error = xfs_refcount_insert(cur, &tmp,
913 &found_tmp);
914 if (error)
915 goto out_error;
916 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
917 found_tmp == 1, out_error);
918 cur->bc_private.a.priv.refc.nr_ops++;
919 } else {
920 fsbno = XFS_AGB_TO_FSB(cur->bc_mp,
921 cur->bc_private.a.agno,
922 tmp.rc_startblock);
923 xfs_bmap_add_free(cur->bc_tp, fsbno,
924 tmp.rc_blockcount, oinfo);
925 }
926
927 (*agbno) += tmp.rc_blockcount;
928 (*aglen) -= tmp.rc_blockcount;
929
930 error = xfs_refcount_lookup_ge(cur, *agbno,
931 &found_rec);
932 if (error)
933 goto out_error;
934 }
935
936 /* Stop if there's nothing left to modify */
937 if (*aglen == 0 || !xfs_refcount_still_have_space(cur))
938 break;
939
940 /*
941 * Adjust the reference count and either update the tree
942 * (incr) or free the blocks (decr).
943 */
944 if (ext.rc_refcount == MAXREFCOUNT)
945 goto skip;
946 ext.rc_refcount += adj;
947 trace_xfs_refcount_modify_extent(cur->bc_mp,
948 cur->bc_private.a.agno, &ext);
949 if (ext.rc_refcount > 1) {
950 error = xfs_refcount_update(cur, &ext);
951 if (error)
952 goto out_error;
953 cur->bc_private.a.priv.refc.nr_ops++;
954 } else if (ext.rc_refcount == 1) {
955 error = xfs_refcount_delete(cur, &found_rec);
956 if (error)
957 goto out_error;
958 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
959 found_rec == 1, out_error);
960 cur->bc_private.a.priv.refc.nr_ops++;
961 goto advloop;
962 } else {
963 fsbno = XFS_AGB_TO_FSB(cur->bc_mp,
964 cur->bc_private.a.agno,
965 ext.rc_startblock);
966 xfs_bmap_add_free(cur->bc_tp, fsbno, ext.rc_blockcount,
967 oinfo);
968 }
969
970skip:
971 error = xfs_btree_increment(cur, 0, &found_rec);
972 if (error)
973 goto out_error;
974
975advloop:
976 (*agbno) += ext.rc_blockcount;
977 (*aglen) -= ext.rc_blockcount;
978 }
979
980 return error;
981out_error:
982 trace_xfs_refcount_modify_extent_error(cur->bc_mp,
983 cur->bc_private.a.agno, error, _RET_IP_);
984 return error;
985}
986
987/* Adjust the reference count of a range of AG blocks. */
988STATIC int
989xfs_refcount_adjust(
990 struct xfs_btree_cur *cur,
991 xfs_agblock_t agbno,
992 xfs_extlen_t aglen,
993 xfs_agblock_t *new_agbno,
994 xfs_extlen_t *new_aglen,
995 enum xfs_refc_adjust_op adj,
996 struct xfs_owner_info *oinfo)
997{
998 bool shape_changed;
999 int shape_changes = 0;
1000 int error;
1001
1002 *new_agbno = agbno;
1003 *new_aglen = aglen;
1004 if (adj == XFS_REFCOUNT_ADJUST_INCREASE)
1005 trace_xfs_refcount_increase(cur->bc_mp, cur->bc_private.a.agno,
1006 agbno, aglen);
1007 else
1008 trace_xfs_refcount_decrease(cur->bc_mp, cur->bc_private.a.agno,
1009 agbno, aglen);
1010
1011 /*
1012 * Ensure that no rcextents cross the boundary of the adjustment range.
1013 */
1014 error = xfs_refcount_split_extent(cur, agbno, &shape_changed);
1015 if (error)
1016 goto out_error;
1017 if (shape_changed)
1018 shape_changes++;
1019
1020 error = xfs_refcount_split_extent(cur, agbno + aglen, &shape_changed);
1021 if (error)
1022 goto out_error;
1023 if (shape_changed)
1024 shape_changes++;
1025
1026 /*
1027 * Try to merge with the left or right extents of the range.
1028 */
1029 error = xfs_refcount_merge_extents(cur, new_agbno, new_aglen, adj,
1030 XFS_FIND_RCEXT_SHARED, &shape_changed);
1031 if (error)
1032 goto out_error;
1033 if (shape_changed)
1034 shape_changes++;
1035 if (shape_changes)
1036 cur->bc_private.a.priv.refc.shape_changes++;
1037
1038 /* Now that we've taken care of the ends, adjust the middle extents */
1039 error = xfs_refcount_adjust_extents(cur, new_agbno, new_aglen,
1040 adj, oinfo);
1041 if (error)
1042 goto out_error;
1043
1044 return 0;
1045
1046out_error:
1047 trace_xfs_refcount_adjust_error(cur->bc_mp, cur->bc_private.a.agno,
1048 error, _RET_IP_);
1049 return error;
1050}
1051
1052/* Clean up after calling xfs_refcount_finish_one. */
1053void
1054xfs_refcount_finish_one_cleanup(
1055 struct xfs_trans *tp,
1056 struct xfs_btree_cur *rcur,
1057 int error)
1058{
1059 struct xfs_buf *agbp;
1060
1061 if (rcur == NULL)
1062 return;
1063 agbp = rcur->bc_private.a.agbp;
1064 xfs_btree_del_cursor(rcur, error);
1065 if (error)
1066 xfs_trans_brelse(tp, agbp);
1067}
1068
1069/*
1070 * Process one of the deferred refcount operations. We pass back the
1071 * btree cursor to maintain our lock on the btree between calls.
1072 * This saves time and eliminates a buffer deadlock between the
1073 * superblock and the AGF because we'll always grab them in the same
1074 * order.
1075 */
1076int
1077xfs_refcount_finish_one(
1078 struct xfs_trans *tp,
1079 enum xfs_refcount_intent_type type,
1080 xfs_fsblock_t startblock,
1081 xfs_extlen_t blockcount,
1082 xfs_fsblock_t *new_fsb,
1083 xfs_extlen_t *new_len,
1084 struct xfs_btree_cur **pcur)
1085{
1086 struct xfs_mount *mp = tp->t_mountp;
1087 struct xfs_btree_cur *rcur;
1088 struct xfs_buf *agbp = NULL;
1089 int error = 0;
1090 xfs_agnumber_t agno;
1091 xfs_agblock_t bno;
1092 xfs_agblock_t new_agbno;
1093 unsigned long nr_ops = 0;
1094 int shape_changes = 0;
1095
1096 agno = XFS_FSB_TO_AGNO(mp, startblock);
1097 ASSERT(agno != NULLAGNUMBER);
1098 bno = XFS_FSB_TO_AGBNO(mp, startblock);
1099
1100 trace_xfs_refcount_deferred(mp, XFS_FSB_TO_AGNO(mp, startblock),
1101 type, XFS_FSB_TO_AGBNO(mp, startblock),
1102 blockcount);
1103
1104 if (XFS_TEST_ERROR(false, mp,
1105 XFS_ERRTAG_REFCOUNT_FINISH_ONE))
1106 return -EIO;
1107
1108 /*
1109 * If we haven't gotten a cursor or the cursor AG doesn't match
1110 * the startblock, get one now.
1111 */
1112 rcur = *pcur;
1113 if (rcur != NULL && rcur->bc_private.a.agno != agno) {
1114 nr_ops = rcur->bc_private.a.priv.refc.nr_ops;
1115 shape_changes = rcur->bc_private.a.priv.refc.shape_changes;
1116 xfs_refcount_finish_one_cleanup(tp, rcur, 0);
1117 rcur = NULL;
1118 *pcur = NULL;
1119 }
1120 if (rcur == NULL) {
1121 error = xfs_alloc_read_agf(tp->t_mountp, tp, agno,
1122 XFS_ALLOC_FLAG_FREEING, &agbp);
1123 if (error)
1124 return error;
1125 if (!agbp)
1126 return -EFSCORRUPTED;
1127
1128 rcur = xfs_refcountbt_init_cursor(mp, tp, agbp, agno);
1129 if (!rcur) {
1130 error = -ENOMEM;
1131 goto out_cur;
1132 }
1133 rcur->bc_private.a.priv.refc.nr_ops = nr_ops;
1134 rcur->bc_private.a.priv.refc.shape_changes = shape_changes;
1135 }
1136 *pcur = rcur;
1137
1138 switch (type) {
1139 case XFS_REFCOUNT_INCREASE:
1140 error = xfs_refcount_adjust(rcur, bno, blockcount, &new_agbno,
1141 new_len, XFS_REFCOUNT_ADJUST_INCREASE, NULL);
1142 *new_fsb = XFS_AGB_TO_FSB(mp, agno, new_agbno);
1143 break;
1144 case XFS_REFCOUNT_DECREASE:
1145 error = xfs_refcount_adjust(rcur, bno, blockcount, &new_agbno,
1146 new_len, XFS_REFCOUNT_ADJUST_DECREASE, NULL);
1147 *new_fsb = XFS_AGB_TO_FSB(mp, agno, new_agbno);
1148 break;
1149 case XFS_REFCOUNT_ALLOC_COW:
1150 *new_fsb = startblock + blockcount;
1151 *new_len = 0;
1152 error = __xfs_refcount_cow_alloc(rcur, bno, blockcount);
1153 break;
1154 case XFS_REFCOUNT_FREE_COW:
1155 *new_fsb = startblock + blockcount;
1156 *new_len = 0;
1157 error = __xfs_refcount_cow_free(rcur, bno, blockcount);
1158 break;
1159 default:
1160 ASSERT(0);
1161 error = -EFSCORRUPTED;
1162 }
1163 if (!error && *new_len > 0)
1164 trace_xfs_refcount_finish_one_leftover(mp, agno, type,
1165 bno, blockcount, new_agbno, *new_len);
1166 return error;
1167
1168out_cur:
1169 xfs_trans_brelse(tp, agbp);
1170
1171 return error;
1172}
1173
1174/*
1175 * Record a refcount intent for later processing.
1176 */
1177static void
1178__xfs_refcount_add(
1179 struct xfs_trans *tp,
1180 enum xfs_refcount_intent_type type,
1181 xfs_fsblock_t startblock,
1182 xfs_extlen_t blockcount)
1183{
1184 struct xfs_refcount_intent *ri;
1185
1186 trace_xfs_refcount_defer(tp->t_mountp,
1187 XFS_FSB_TO_AGNO(tp->t_mountp, startblock),
1188 type, XFS_FSB_TO_AGBNO(tp->t_mountp, startblock),
1189 blockcount);
1190
1191 ri = kmem_alloc(sizeof(struct xfs_refcount_intent),
1192 KM_NOFS);
1193 INIT_LIST_HEAD(&ri->ri_list);
1194 ri->ri_type = type;
1195 ri->ri_startblock = startblock;
1196 ri->ri_blockcount = blockcount;
1197
1198 xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_REFCOUNT, &ri->ri_list);
1199}
1200
1201/*
1202 * Increase the reference count of the blocks backing a file's extent.
1203 */
1204void
1205xfs_refcount_increase_extent(
1206 struct xfs_trans *tp,
1207 struct xfs_bmbt_irec *PREV)
1208{
1209 if (!xfs_sb_version_hasreflink(&tp->t_mountp->m_sb))
1210 return;
1211
1212 __xfs_refcount_add(tp, XFS_REFCOUNT_INCREASE, PREV->br_startblock,
1213 PREV->br_blockcount);
1214}
1215
1216/*
1217 * Decrease the reference count of the blocks backing a file's extent.
1218 */
1219void
1220xfs_refcount_decrease_extent(
1221 struct xfs_trans *tp,
1222 struct xfs_bmbt_irec *PREV)
1223{
1224 if (!xfs_sb_version_hasreflink(&tp->t_mountp->m_sb))
1225 return;
1226
1227 __xfs_refcount_add(tp, XFS_REFCOUNT_DECREASE, PREV->br_startblock,
1228 PREV->br_blockcount);
1229}
1230
1231/*
1232 * Given an AG extent, find the lowest-numbered run of shared blocks
1233 * within that range and return the range in fbno/flen. If
1234 * find_end_of_shared is set, return the longest contiguous extent of
1235 * shared blocks; if not, just return the first extent we find. If no
1236 * shared blocks are found, fbno and flen will be set to NULLAGBLOCK
1237 * and 0, respectively.
1238 */
1239int
1240xfs_refcount_find_shared(
1241 struct xfs_btree_cur *cur,
1242 xfs_agblock_t agbno,
1243 xfs_extlen_t aglen,
1244 xfs_agblock_t *fbno,
1245 xfs_extlen_t *flen,
1246 bool find_end_of_shared)
1247{
1248 struct xfs_refcount_irec tmp;
1249 int i;
1250 int have;
1251 int error;
1252
1253 trace_xfs_refcount_find_shared(cur->bc_mp, cur->bc_private.a.agno,
1254 agbno, aglen);
1255
1256 /* By default, skip the whole range */
1257 *fbno = NULLAGBLOCK;
1258 *flen = 0;
1259
1260 /* Try to find a refcount extent that crosses the start */
1261 error = xfs_refcount_lookup_le(cur, agbno, &have);
1262 if (error)
1263 goto out_error;
1264 if (!have) {
1265 /* No left extent, look at the next one */
1266 error = xfs_btree_increment(cur, 0, &have);
1267 if (error)
1268 goto out_error;
1269 if (!have)
1270 goto done;
1271 }
1272 error = xfs_refcount_get_rec(cur, &tmp, &i);
1273 if (error)
1274 goto out_error;
1275 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, out_error);
1276
1277 /* If the extent ends before the start, look at the next one */
1278 if (tmp.rc_startblock + tmp.rc_blockcount <= agbno) {
1279 error = xfs_btree_increment(cur, 0, &have);
1280 if (error)
1281 goto out_error;
1282 if (!have)
1283 goto done;
1284 error = xfs_refcount_get_rec(cur, &tmp, &i);
1285 if (error)
1286 goto out_error;
1287 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, out_error);
1288 }
1289
1290 /* If the extent starts after the range we want, bail out */
1291 if (tmp.rc_startblock >= agbno + aglen)
1292 goto done;
1293
1294 /* We found the start of a shared extent! */
1295 if (tmp.rc_startblock < agbno) {
1296 tmp.rc_blockcount -= (agbno - tmp.rc_startblock);
1297 tmp.rc_startblock = agbno;
1298 }
1299
1300 *fbno = tmp.rc_startblock;
1301 *flen = min(tmp.rc_blockcount, agbno + aglen - *fbno);
1302 if (!find_end_of_shared)
1303 goto done;
1304
1305 /* Otherwise, find the end of this shared extent */
1306 while (*fbno + *flen < agbno + aglen) {
1307 error = xfs_btree_increment(cur, 0, &have);
1308 if (error)
1309 goto out_error;
1310 if (!have)
1311 break;
1312 error = xfs_refcount_get_rec(cur, &tmp, &i);
1313 if (error)
1314 goto out_error;
1315 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp, i == 1, out_error);
1316 if (tmp.rc_startblock >= agbno + aglen ||
1317 tmp.rc_startblock != *fbno + *flen)
1318 break;
1319 *flen = min(*flen + tmp.rc_blockcount, agbno + aglen - *fbno);
1320 }
1321
1322done:
1323 trace_xfs_refcount_find_shared_result(cur->bc_mp,
1324 cur->bc_private.a.agno, *fbno, *flen);
1325
1326out_error:
1327 if (error)
1328 trace_xfs_refcount_find_shared_error(cur->bc_mp,
1329 cur->bc_private.a.agno, error, _RET_IP_);
1330 return error;
1331}
1332
1333/*
1334 * Recovering CoW Blocks After a Crash
1335 *
1336 * Due to the way that the copy on write mechanism works, there's a window of
1337 * opportunity in which we can lose track of allocated blocks during a crash.
1338 * Because CoW uses delayed allocation in the in-core CoW fork, writeback
1339 * causes blocks to be allocated and stored in the CoW fork. The blocks are
1340 * no longer in the free space btree but are not otherwise recorded anywhere
1341 * until the write completes and the blocks are mapped into the file. A crash
1342 * in between allocation and remapping results in the replacement blocks being
1343 * lost. This situation is exacerbated by the CoW extent size hint because
1344 * allocations can hang around for long time.
1345 *
1346 * However, there is a place where we can record these allocations before they
1347 * become mappings -- the reference count btree. The btree does not record
1348 * extents with refcount == 1, so we can record allocations with a refcount of
1349 * 1. Blocks being used for CoW writeout cannot be shared, so there should be
1350 * no conflict with shared block records. These mappings should be created
1351 * when we allocate blocks to the CoW fork and deleted when they're removed
1352 * from the CoW fork.
1353 *
1354 * Minor nit: records for in-progress CoW allocations and records for shared
1355 * extents must never be merged, to preserve the property that (except for CoW
1356 * allocations) there are no refcount btree entries with refcount == 1. The
1357 * only time this could potentially happen is when unsharing a block that's
1358 * adjacent to CoW allocations, so we must be careful to avoid this.
1359 *
1360 * At mount time we recover lost CoW allocations by searching the refcount
1361 * btree for these refcount == 1 mappings. These represent CoW allocations
1362 * that were in progress at the time the filesystem went down, so we can free
1363 * them to get the space back.
1364 *
1365 * This mechanism is superior to creating EFIs for unmapped CoW extents for
1366 * several reasons -- first, EFIs pin the tail of the log and would have to be
1367 * periodically relogged to avoid filling up the log. Second, CoW completions
1368 * will have to file an EFD and create new EFIs for whatever remains in the
1369 * CoW fork; this partially takes care of (1) but extent-size reservations
1370 * will have to periodically relog even if there's no writeout in progress.
1371 * This can happen if the CoW extent size hint is set, which you really want.
1372 * Third, EFIs cannot currently be automatically relogged into newer
1373 * transactions to advance the log tail. Fourth, stuffing the log full of
1374 * EFIs places an upper bound on the number of CoW allocations that can be
1375 * held filesystem-wide at any given time. Recording them in the refcount
1376 * btree doesn't require us to maintain any state in memory and doesn't pin
1377 * the log.
1378 */
1379/*
1380 * Adjust the refcounts of CoW allocations. These allocations are "magic"
1381 * in that they're not referenced anywhere else in the filesystem, so we
1382 * stash them in the refcount btree with a refcount of 1 until either file
1383 * remapping (or CoW cancellation) happens.
1384 */
1385STATIC int
1386xfs_refcount_adjust_cow_extents(
1387 struct xfs_btree_cur *cur,
1388 xfs_agblock_t agbno,
1389 xfs_extlen_t aglen,
1390 enum xfs_refc_adjust_op adj)
1391{
1392 struct xfs_refcount_irec ext, tmp;
1393 int error;
1394 int found_rec, found_tmp;
1395
1396 if (aglen == 0)
1397 return 0;
1398
1399 /* Find any overlapping refcount records */
1400 error = xfs_refcount_lookup_ge(cur, agbno, &found_rec);
1401 if (error)
1402 goto out_error;
1403 error = xfs_refcount_get_rec(cur, &ext, &found_rec);
1404 if (error)
1405 goto out_error;
1406 if (!found_rec) {
1407 ext.rc_startblock = cur->bc_mp->m_sb.sb_agblocks +
1408 XFS_REFC_COW_START;
1409 ext.rc_blockcount = 0;
1410 ext.rc_refcount = 0;
1411 }
1412
1413 switch (adj) {
1414 case XFS_REFCOUNT_ADJUST_COW_ALLOC:
1415 /* Adding a CoW reservation, there should be nothing here. */
1416 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
1417 ext.rc_startblock >= agbno + aglen, out_error);
1418
1419 tmp.rc_startblock = agbno;
1420 tmp.rc_blockcount = aglen;
1421 tmp.rc_refcount = 1;
1422 trace_xfs_refcount_modify_extent(cur->bc_mp,
1423 cur->bc_private.a.agno, &tmp);
1424
1425 error = xfs_refcount_insert(cur, &tmp,
1426 &found_tmp);
1427 if (error)
1428 goto out_error;
1429 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
1430 found_tmp == 1, out_error);
1431 break;
1432 case XFS_REFCOUNT_ADJUST_COW_FREE:
1433 /* Removing a CoW reservation, there should be one extent. */
1434 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
1435 ext.rc_startblock == agbno, out_error);
1436 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
1437 ext.rc_blockcount == aglen, out_error);
1438 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
1439 ext.rc_refcount == 1, out_error);
1440
1441 ext.rc_refcount = 0;
1442 trace_xfs_refcount_modify_extent(cur->bc_mp,
1443 cur->bc_private.a.agno, &ext);
1444 error = xfs_refcount_delete(cur, &found_rec);
1445 if (error)
1446 goto out_error;
1447 XFS_WANT_CORRUPTED_GOTO(cur->bc_mp,
1448 found_rec == 1, out_error);
1449 break;
1450 default:
1451 ASSERT(0);
1452 }
1453
1454 return error;
1455out_error:
1456 trace_xfs_refcount_modify_extent_error(cur->bc_mp,
1457 cur->bc_private.a.agno, error, _RET_IP_);
1458 return error;
1459}
1460
1461/*
1462 * Add or remove refcount btree entries for CoW reservations.
1463 */
1464STATIC int
1465xfs_refcount_adjust_cow(
1466 struct xfs_btree_cur *cur,
1467 xfs_agblock_t agbno,
1468 xfs_extlen_t aglen,
1469 enum xfs_refc_adjust_op adj)
1470{
1471 bool shape_changed;
1472 int error;
1473
1474 agbno += XFS_REFC_COW_START;
1475
1476 /*
1477 * Ensure that no rcextents cross the boundary of the adjustment range.
1478 */
1479 error = xfs_refcount_split_extent(cur, agbno, &shape_changed);
1480 if (error)
1481 goto out_error;
1482
1483 error = xfs_refcount_split_extent(cur, agbno + aglen, &shape_changed);
1484 if (error)
1485 goto out_error;
1486
1487 /*
1488 * Try to merge with the left or right extents of the range.
1489 */
1490 error = xfs_refcount_merge_extents(cur, &agbno, &aglen, adj,
1491 XFS_FIND_RCEXT_COW, &shape_changed);
1492 if (error)
1493 goto out_error;
1494
1495 /* Now that we've taken care of the ends, adjust the middle extents */
1496 error = xfs_refcount_adjust_cow_extents(cur, agbno, aglen, adj);
1497 if (error)
1498 goto out_error;
1499
1500 return 0;
1501
1502out_error:
1503 trace_xfs_refcount_adjust_cow_error(cur->bc_mp, cur->bc_private.a.agno,
1504 error, _RET_IP_);
1505 return error;
1506}
1507
1508/*
1509 * Record a CoW allocation in the refcount btree.
1510 */
1511STATIC int
1512__xfs_refcount_cow_alloc(
1513 struct xfs_btree_cur *rcur,
1514 xfs_agblock_t agbno,
1515 xfs_extlen_t aglen)
1516{
1517 trace_xfs_refcount_cow_increase(rcur->bc_mp, rcur->bc_private.a.agno,
1518 agbno, aglen);
1519
1520 /* Add refcount btree reservation */
1521 return xfs_refcount_adjust_cow(rcur, agbno, aglen,
1522 XFS_REFCOUNT_ADJUST_COW_ALLOC);
1523}
1524
1525/*
1526 * Remove a CoW allocation from the refcount btree.
1527 */
1528STATIC int
1529__xfs_refcount_cow_free(
1530 struct xfs_btree_cur *rcur,
1531 xfs_agblock_t agbno,
1532 xfs_extlen_t aglen)
1533{
1534 trace_xfs_refcount_cow_decrease(rcur->bc_mp, rcur->bc_private.a.agno,
1535 agbno, aglen);
1536
1537 /* Remove refcount btree reservation */
1538 return xfs_refcount_adjust_cow(rcur, agbno, aglen,
1539 XFS_REFCOUNT_ADJUST_COW_FREE);
1540}
1541
1542/* Record a CoW staging extent in the refcount btree. */
1543void
1544xfs_refcount_alloc_cow_extent(
1545 struct xfs_trans *tp,
1546 xfs_fsblock_t fsb,
1547 xfs_extlen_t len)
1548{
1549 struct xfs_mount *mp = tp->t_mountp;
1550
1551 if (!xfs_sb_version_hasreflink(&mp->m_sb))
1552 return;
1553
1554 __xfs_refcount_add(tp, XFS_REFCOUNT_ALLOC_COW, fsb, len);
1555
1556 /* Add rmap entry */
1557 xfs_rmap_alloc_extent(tp, XFS_FSB_TO_AGNO(mp, fsb),
1558 XFS_FSB_TO_AGBNO(mp, fsb), len, XFS_RMAP_OWN_COW);
1559}
1560
1561/* Forget a CoW staging event in the refcount btree. */
1562void
1563xfs_refcount_free_cow_extent(
1564 struct xfs_trans *tp,
1565 xfs_fsblock_t fsb,
1566 xfs_extlen_t len)
1567{
1568 struct xfs_mount *mp = tp->t_mountp;
1569
1570 if (!xfs_sb_version_hasreflink(&mp->m_sb))
1571 return;
1572
1573 /* Remove rmap entry */
1574 xfs_rmap_free_extent(tp, XFS_FSB_TO_AGNO(mp, fsb),
1575 XFS_FSB_TO_AGBNO(mp, fsb), len, XFS_RMAP_OWN_COW);
1576 __xfs_refcount_add(tp, XFS_REFCOUNT_FREE_COW, fsb, len);
1577}
1578
1579struct xfs_refcount_recovery {
1580 struct list_head rr_list;
1581 struct xfs_refcount_irec rr_rrec;
1582};
1583
1584/* Stuff an extent on the recovery list. */
1585STATIC int
1586xfs_refcount_recover_extent(
1587 struct xfs_btree_cur *cur,
1588 union xfs_btree_rec *rec,
1589 void *priv)
1590{
1591 struct list_head *debris = priv;
1592 struct xfs_refcount_recovery *rr;
1593
1594 if (be32_to_cpu(rec->refc.rc_refcount) != 1)
1595 return -EFSCORRUPTED;
1596
1597 rr = kmem_alloc(sizeof(struct xfs_refcount_recovery), 0);
1598 xfs_refcount_btrec_to_irec(rec, &rr->rr_rrec);
1599 list_add_tail(&rr->rr_list, debris);
1600
1601 return 0;
1602}
1603
1604/* Find and remove leftover CoW reservations. */
1605int
1606xfs_refcount_recover_cow_leftovers(
1607 struct xfs_mount *mp,
1608 xfs_agnumber_t agno)
1609{
1610 struct xfs_trans *tp;
1611 struct xfs_btree_cur *cur;
1612 struct xfs_buf *agbp;
1613 struct xfs_refcount_recovery *rr, *n;
1614 struct list_head debris;
1615 union xfs_btree_irec low;
1616 union xfs_btree_irec high;
1617 xfs_fsblock_t fsb;
1618 xfs_agblock_t agbno;
1619 int error;
1620
1621 if (mp->m_sb.sb_agblocks >= XFS_REFC_COW_START)
1622 return -EOPNOTSUPP;
1623
1624 INIT_LIST_HEAD(&debris);
1625
1626 /*
1627 * In this first part, we use an empty transaction to gather up
1628 * all the leftover CoW extents so that we can subsequently
1629 * delete them. The empty transaction is used to avoid
1630 * a buffer lock deadlock if there happens to be a loop in the
1631 * refcountbt because we're allowed to re-grab a buffer that is
1632 * already attached to our transaction. When we're done
1633 * recording the CoW debris we cancel the (empty) transaction
1634 * and everything goes away cleanly.
1635 */
1636 error = xfs_trans_alloc_empty(mp, &tp);
1637 if (error)
1638 return error;
1639
1640 error = xfs_alloc_read_agf(mp, tp, agno, 0, &agbp);
1641 if (error)
1642 goto out_trans;
1643 if (!agbp) {
1644 error = -ENOMEM;
1645 goto out_trans;
1646 }
1647 cur = xfs_refcountbt_init_cursor(mp, tp, agbp, agno);
1648
1649 /* Find all the leftover CoW staging extents. */
1650 memset(&low, 0, sizeof(low));
1651 memset(&high, 0, sizeof(high));
1652 low.rc.rc_startblock = XFS_REFC_COW_START;
1653 high.rc.rc_startblock = -1U;
1654 error = xfs_btree_query_range(cur, &low, &high,
1655 xfs_refcount_recover_extent, &debris);
1656 xfs_btree_del_cursor(cur, error);
1657 xfs_trans_brelse(tp, agbp);
1658 xfs_trans_cancel(tp);
1659 if (error)
1660 goto out_free;
1661
1662 /* Now iterate the list to free the leftovers */
1663 list_for_each_entry_safe(rr, n, &debris, rr_list) {
1664 /* Set up transaction. */
1665 error = xfs_trans_alloc(mp, &M_RES(mp)->tr_write, 0, 0, 0, &tp);
1666 if (error)
1667 goto out_free;
1668
1669 trace_xfs_refcount_recover_extent(mp, agno, &rr->rr_rrec);
1670
1671 /* Free the orphan record */
1672 agbno = rr->rr_rrec.rc_startblock - XFS_REFC_COW_START;
1673 fsb = XFS_AGB_TO_FSB(mp, agno, agbno);
1674 xfs_refcount_free_cow_extent(tp, fsb,
1675 rr->rr_rrec.rc_blockcount);
1676
1677 /* Free the block. */
1678 xfs_bmap_add_free(tp, fsb, rr->rr_rrec.rc_blockcount, NULL);
1679
1680 error = xfs_trans_commit(tp);
1681 if (error)
1682 goto out_free;
1683
1684 list_del(&rr->rr_list);
1685 kmem_free(rr);
1686 }
1687
1688 return error;
1689out_trans:
1690 xfs_trans_cancel(tp);
1691out_free:
1692 /* Free the leftover list */
1693 list_for_each_entry_safe(rr, n, &debris, rr_list) {
1694 list_del(&rr->rr_list);
1695 kmem_free(rr);
1696 }
1697 return error;
1698}
1699
1700/* Is there a record covering a given extent? */
1701int
1702xfs_refcount_has_record(
1703 struct xfs_btree_cur *cur,
1704 xfs_agblock_t bno,
1705 xfs_extlen_t len,
1706 bool *exists)
1707{
1708 union xfs_btree_irec low;
1709 union xfs_btree_irec high;
1710
1711 memset(&low, 0, sizeof(low));
1712 low.rc.rc_startblock = bno;
1713 memset(&high, 0xFF, sizeof(high));
1714 high.rc.rc_startblock = bno + len - 1;
1715
1716 return xfs_btree_has_record(cur, &low, &high, exists);
1717}