1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (c) 2014 Red Hat, Inc.
4 * All Rights Reserved.
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_bit.h"
13 #include "xfs_mount.h"
14 #include "xfs_sb.h"
15 #include "xfs_defer.h"
16 #include "xfs_btree.h"
17 #include "xfs_trans.h"
18 #include "xfs_alloc.h"
19 #include "xfs_rmap.h"
20 #include "xfs_rmap_btree.h"
21 #include "xfs_trace.h"
22 #include "xfs_errortag.h"
23 #include "xfs_error.h"
24 #include "xfs_inode.h"
25 #include "xfs_ag.h"
26 #include "xfs_health.h"
27 #include "xfs_rmap_item.h"
28
29 struct kmem_cache *xfs_rmap_intent_cache;
30
31 /*
32 * Lookup the first record less than or equal to [bno, len, owner, offset]
33 * in the btree given by cur.
34 */
35 int
36 xfs_rmap_lookup_le(
37 struct xfs_btree_cur *cur,
38 xfs_agblock_t bno,
39 uint64_t owner,
40 uint64_t offset,
41 unsigned int flags,
42 struct xfs_rmap_irec *irec,
43 int *stat)
44 {
45 int get_stat = 0;
46 int error;
47
48 cur->bc_rec.r.rm_startblock = bno;
49 cur->bc_rec.r.rm_blockcount = 0;
50 cur->bc_rec.r.rm_owner = owner;
51 cur->bc_rec.r.rm_offset = offset;
52 cur->bc_rec.r.rm_flags = flags;
53
54 error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
55 if (error || !(*stat) || !irec)
56 return error;
57
58 error = xfs_rmap_get_rec(cur, irec, &get_stat);
59 if (error)
60 return error;
61 if (!get_stat) {
62 xfs_btree_mark_sick(cur);
63 return -EFSCORRUPTED;
64 }
65
66 return 0;
67 }
68
69 /*
70 * Lookup the record exactly matching [bno, len, owner, offset]
71 * in the btree given by cur.
72 */
73 int
74 xfs_rmap_lookup_eq(
75 struct xfs_btree_cur *cur,
76 xfs_agblock_t bno,
77 xfs_extlen_t len,
78 uint64_t owner,
79 uint64_t offset,
80 unsigned int flags,
81 int *stat)
82 {
83 cur->bc_rec.r.rm_startblock = bno;
84 cur->bc_rec.r.rm_blockcount = len;
85 cur->bc_rec.r.rm_owner = owner;
86 cur->bc_rec.r.rm_offset = offset;
87 cur->bc_rec.r.rm_flags = flags;
88 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
89 }
90
91 /*
92 * Update the record referred to by cur to the value given
93 * by [bno, len, owner, offset].
94 * This either works (return 0) or gets an EFSCORRUPTED error.
95 */
96 STATIC int
97 xfs_rmap_update(
98 struct xfs_btree_cur *cur,
99 struct xfs_rmap_irec *irec)
100 {
101 union xfs_btree_rec rec;
102 int error;
103
104 trace_xfs_rmap_update(cur, irec->rm_startblock, irec->rm_blockcount,
105 irec->rm_owner, irec->rm_offset, irec->rm_flags);
106
107 rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock);
108 rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount);
109 rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner);
110 rec.rmap.rm_offset = cpu_to_be64(
111 xfs_rmap_irec_offset_pack(irec));
112 error = xfs_btree_update(cur, &rec);
113 if (error)
114 trace_xfs_rmap_update_error(cur, error, _RET_IP_);
115 return error;
116 }
117
118 int
119 xfs_rmap_insert(
120 struct xfs_btree_cur *rcur,
121 xfs_agblock_t agbno,
122 xfs_extlen_t len,
123 uint64_t owner,
124 uint64_t offset,
125 unsigned int flags)
126 {
127 int i;
128 int error;
129
130 trace_xfs_rmap_insert(rcur, agbno, len, owner, offset, flags);
131
132 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
133 if (error)
134 goto done;
135 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 0)) {
136 xfs_btree_mark_sick(rcur);
137 error = -EFSCORRUPTED;
138 goto done;
139 }
140
141 rcur->bc_rec.r.rm_startblock = agbno;
142 rcur->bc_rec.r.rm_blockcount = len;
143 rcur->bc_rec.r.rm_owner = owner;
144 rcur->bc_rec.r.rm_offset = offset;
145 rcur->bc_rec.r.rm_flags = flags;
146 error = xfs_btree_insert(rcur, &i);
147 if (error)
148 goto done;
149 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
150 xfs_btree_mark_sick(rcur);
151 error = -EFSCORRUPTED;
152 goto done;
153 }
154 done:
155 if (error)
156 trace_xfs_rmap_insert_error(rcur, error, _RET_IP_);
157 return error;
158 }
159
160 STATIC int
161 xfs_rmap_delete(
162 struct xfs_btree_cur *rcur,
163 xfs_agblock_t agbno,
164 xfs_extlen_t len,
165 uint64_t owner,
166 uint64_t offset,
167 unsigned int flags)
168 {
169 int i;
170 int error;
171
172 trace_xfs_rmap_delete(rcur, agbno, len, owner, offset, flags);
173
174 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
175 if (error)
176 goto done;
177 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
178 xfs_btree_mark_sick(rcur);
179 error = -EFSCORRUPTED;
180 goto done;
181 }
182
183 error = xfs_btree_delete(rcur, &i);
184 if (error)
185 goto done;
186 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
187 xfs_btree_mark_sick(rcur);
188 error = -EFSCORRUPTED;
189 goto done;
190 }
191 done:
192 if (error)
193 trace_xfs_rmap_delete_error(rcur, error, _RET_IP_);
194 return error;
195 }
196
197 /* Convert an internal btree record to an rmap record. */
198 xfs_failaddr_t
199 xfs_rmap_btrec_to_irec(
200 const union xfs_btree_rec *rec,
201 struct xfs_rmap_irec *irec)
202 {
203 irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock);
204 irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount);
205 irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner);
206 return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset),
207 irec);
208 }
209
210 /* Simple checks for rmap records. */
211 xfs_failaddr_t
212 xfs_rmap_check_irec(
213 struct xfs_perag *pag,
214 const struct xfs_rmap_irec *irec)
215 {
216 struct xfs_mount *mp = pag->pag_mount;
217 bool is_inode;
218 bool is_unwritten;
219 bool is_bmbt;
220 bool is_attr;
221
222 if (irec->rm_blockcount == 0)
223 return __this_address;
224 if (irec->rm_startblock <= XFS_AGFL_BLOCK(mp)) {
225 if (irec->rm_owner != XFS_RMAP_OWN_FS)
226 return __this_address;
227 if (irec->rm_blockcount != XFS_AGFL_BLOCK(mp) + 1)
228 return __this_address;
229 } else {
230 /* check for valid extent range, including overflow */
231 if (!xfs_verify_agbext(pag, irec->rm_startblock,
232 irec->rm_blockcount))
233 return __this_address;
234 }
235
236 if (!(xfs_verify_ino(mp, irec->rm_owner) ||
237 (irec->rm_owner <= XFS_RMAP_OWN_FS &&
238 irec->rm_owner >= XFS_RMAP_OWN_MIN)))
239 return __this_address;
240
241 /* Check flags. */
242 is_inode = !XFS_RMAP_NON_INODE_OWNER(irec->rm_owner);
243 is_bmbt = irec->rm_flags & XFS_RMAP_BMBT_BLOCK;
244 is_attr = irec->rm_flags & XFS_RMAP_ATTR_FORK;
245 is_unwritten = irec->rm_flags & XFS_RMAP_UNWRITTEN;
246
247 if (is_bmbt && irec->rm_offset != 0)
248 return __this_address;
249
250 if (!is_inode && irec->rm_offset != 0)
251 return __this_address;
252
253 if (is_unwritten && (is_bmbt || !is_inode || is_attr))
254 return __this_address;
255
256 if (!is_inode && (is_bmbt || is_unwritten || is_attr))
257 return __this_address;
258
259 /* Check for a valid fork offset, if applicable. */
260 if (is_inode && !is_bmbt &&
261 !xfs_verify_fileext(mp, irec->rm_offset, irec->rm_blockcount))
262 return __this_address;
263
264 return NULL;
265 }
266
267 static inline xfs_failaddr_t
268 xfs_rmap_check_btrec(
269 struct xfs_btree_cur *cur,
270 const struct xfs_rmap_irec *irec)
271 {
272 if (xfs_btree_is_mem_rmap(cur->bc_ops))
273 return xfs_rmap_check_irec(cur->bc_mem.pag, irec);
274 return xfs_rmap_check_irec(cur->bc_ag.pag, irec);
275 }
276
277 static inline int
278 xfs_rmap_complain_bad_rec(
279 struct xfs_btree_cur *cur,
280 xfs_failaddr_t fa,
281 const struct xfs_rmap_irec *irec)
282 {
283 struct xfs_mount *mp = cur->bc_mp;
284
285 if (xfs_btree_is_mem_rmap(cur->bc_ops))
286 xfs_warn(mp,
287 "In-Memory Reverse Mapping BTree record corruption detected at %pS!", fa);
288 else
289 xfs_warn(mp,
290 "Reverse Mapping BTree record corruption in AG %d detected at %pS!",
291 cur->bc_ag.pag->pag_agno, fa);
292 xfs_warn(mp,
293 "Owner 0x%llx, flags 0x%x, start block 0x%x block count 0x%x",
294 irec->rm_owner, irec->rm_flags, irec->rm_startblock,
295 irec->rm_blockcount);
296 xfs_btree_mark_sick(cur);
297 return -EFSCORRUPTED;
298 }
299
300 /*
301 * Get the data from the pointed-to record.
302 */
303 int
304 xfs_rmap_get_rec(
305 struct xfs_btree_cur *cur,
306 struct xfs_rmap_irec *irec,
307 int *stat)
308 {
309 union xfs_btree_rec *rec;
310 xfs_failaddr_t fa;
311 int error;
312
313 error = xfs_btree_get_rec(cur, &rec, stat);
314 if (error || !*stat)
315 return error;
316
317 fa = xfs_rmap_btrec_to_irec(rec, irec);
318 if (!fa)
319 fa = xfs_rmap_check_btrec(cur, irec);
320 if (fa)
321 return xfs_rmap_complain_bad_rec(cur, fa, irec);
322
323 return 0;
324 }
325
326 struct xfs_find_left_neighbor_info {
327 struct xfs_rmap_irec high;
328 struct xfs_rmap_irec *irec;
329 };
330
331 /* For each rmap given, figure out if it matches the key we want. */
332 STATIC int
333 xfs_rmap_find_left_neighbor_helper(
334 struct xfs_btree_cur *cur,
335 const struct xfs_rmap_irec *rec,
336 void *priv)
337 {
338 struct xfs_find_left_neighbor_info *info = priv;
339
340 trace_xfs_rmap_find_left_neighbor_candidate(cur, rec->rm_startblock,
341 rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
342 rec->rm_flags);
343
344 if (rec->rm_owner != info->high.rm_owner)
345 return 0;
346 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
347 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
348 rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset)
349 return 0;
350
351 *info->irec = *rec;
352 return -ECANCELED;
353 }
354
355 /*
356 * Find the record to the left of the given extent, being careful only to
357 * return a match with the same owner and adjacent physical and logical
358 * block ranges.
359 */
360 STATIC int
361 xfs_rmap_find_left_neighbor(
362 struct xfs_btree_cur *cur,
363 xfs_agblock_t bno,
364 uint64_t owner,
365 uint64_t offset,
366 unsigned int flags,
367 struct xfs_rmap_irec *irec,
368 int *stat)
369 {
370 struct xfs_find_left_neighbor_info info;
371 int found = 0;
372 int error;
373
374 *stat = 0;
375 if (bno == 0)
376 return 0;
377 info.high.rm_startblock = bno - 1;
378 info.high.rm_owner = owner;
379 if (!XFS_RMAP_NON_INODE_OWNER(owner) &&
380 !(flags & XFS_RMAP_BMBT_BLOCK)) {
381 if (offset == 0)
382 return 0;
383 info.high.rm_offset = offset - 1;
384 } else
385 info.high.rm_offset = 0;
386 info.high.rm_flags = flags;
387 info.high.rm_blockcount = 0;
388 info.irec = irec;
389
390 trace_xfs_rmap_find_left_neighbor_query(cur, bno, 0, owner, offset,
391 flags);
392
393 /*
394 * Historically, we always used the range query to walk every reverse
395 * mapping that could possibly overlap the key that the caller asked
396 * for, and filter out the ones that don't. That is very slow when
397 * there are a lot of records.
398 *
399 * However, there are two scenarios where the classic btree search can
400 * produce correct results -- if the index contains a record that is an
401 * exact match for the lookup key; and if there are no other records
402 * between the record we want and the key we supplied.
403 *
404 * As an optimization, try a non-overlapped lookup first. This makes
405 * extent conversion and remap operations run a bit faster if the
406 * physical extents aren't being shared. If we don't find what we
407 * want, we fall back to the overlapped query.
408 */
409 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec,
410 &found);
411 if (error)
412 return error;
413 if (found)
414 error = xfs_rmap_find_left_neighbor_helper(cur, irec, &info);
415 if (!error)
416 error = xfs_rmap_query_range(cur, &info.high, &info.high,
417 xfs_rmap_find_left_neighbor_helper, &info);
418 if (error != -ECANCELED)
419 return error;
420
421 *stat = 1;
422 trace_xfs_rmap_find_left_neighbor_result(cur, irec->rm_startblock,
423 irec->rm_blockcount, irec->rm_owner, irec->rm_offset,
424 irec->rm_flags);
425 return 0;
426 }
427
428 /* For each rmap given, figure out if it matches the key we want. */
429 STATIC int
430 xfs_rmap_lookup_le_range_helper(
431 struct xfs_btree_cur *cur,
432 const struct xfs_rmap_irec *rec,
433 void *priv)
434 {
435 struct xfs_find_left_neighbor_info *info = priv;
436
437 trace_xfs_rmap_lookup_le_range_candidate(cur, rec->rm_startblock,
438 rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
439 rec->rm_flags);
440
441 if (rec->rm_owner != info->high.rm_owner)
442 return 0;
443 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
444 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
445 (rec->rm_offset > info->high.rm_offset ||
446 rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset))
447 return 0;
448
449 *info->irec = *rec;
450 return -ECANCELED;
451 }
452
453 /*
454 * Find the record to the left of the given extent, being careful only to
455 * return a match with the same owner and overlapping physical and logical
456 * block ranges. This is the overlapping-interval version of
457 * xfs_rmap_lookup_le.
458 */
459 int
460 xfs_rmap_lookup_le_range(
461 struct xfs_btree_cur *cur,
462 xfs_agblock_t bno,
463 uint64_t owner,
464 uint64_t offset,
465 unsigned int flags,
466 struct xfs_rmap_irec *irec,
467 int *stat)
468 {
469 struct xfs_find_left_neighbor_info info;
470 int found = 0;
471 int error;
472
473 info.high.rm_startblock = bno;
474 info.high.rm_owner = owner;
475 if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK))
476 info.high.rm_offset = offset;
477 else
478 info.high.rm_offset = 0;
479 info.high.rm_flags = flags;
480 info.high.rm_blockcount = 0;
481 *stat = 0;
482 info.irec = irec;
483
484 trace_xfs_rmap_lookup_le_range(cur, bno, 0, owner, offset, flags);
485
486 /*
487 * Historically, we always used the range query to walk every reverse
488 * mapping that could possibly overlap the key that the caller asked
489 * for, and filter out the ones that don't. That is very slow when
490 * there are a lot of records.
491 *
492 * However, there are two scenarios where the classic btree search can
493 * produce correct results -- if the index contains a record that is an
494 * exact match for the lookup key; and if there are no other records
495 * between the record we want and the key we supplied.
496 *
497 * As an optimization, try a non-overlapped lookup first. This makes
498 * scrub run much faster on most filesystems because bmbt records are
499 * usually an exact match for rmap records. If we don't find what we
500 * want, we fall back to the overlapped query.
501 */
502 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec,
503 &found);
504 if (error)
505 return error;
506 if (found)
507 error = xfs_rmap_lookup_le_range_helper(cur, irec, &info);
508 if (!error)
509 error = xfs_rmap_query_range(cur, &info.high, &info.high,
510 xfs_rmap_lookup_le_range_helper, &info);
511 if (error != -ECANCELED)
512 return error;
513
514 *stat = 1;
515 trace_xfs_rmap_lookup_le_range_result(cur, irec->rm_startblock,
516 irec->rm_blockcount, irec->rm_owner, irec->rm_offset,
517 irec->rm_flags);
518 return 0;
519 }
520
521 /*
522 * Perform all the relevant owner checks for a removal op. If we're doing an
523 * unknown-owner removal then we have no owner information to check.
524 */
525 static int
526 xfs_rmap_free_check_owner(
527 struct xfs_btree_cur *cur,
528 uint64_t ltoff,
529 struct xfs_rmap_irec *rec,
530 xfs_filblks_t len,
531 uint64_t owner,
532 uint64_t offset,
533 unsigned int flags)
534 {
535 struct xfs_mount *mp = cur->bc_mp;
536 int error = 0;
537
538 if (owner == XFS_RMAP_OWN_UNKNOWN)
539 return 0;
540
541 /* Make sure the unwritten flag matches. */
542 if (XFS_IS_CORRUPT(mp,
543 (flags & XFS_RMAP_UNWRITTEN) !=
544 (rec->rm_flags & XFS_RMAP_UNWRITTEN))) {
545 xfs_btree_mark_sick(cur);
546 error = -EFSCORRUPTED;
547 goto out;
548 }
549
550 /* Make sure the owner matches what we expect to find in the tree. */
551 if (XFS_IS_CORRUPT(mp, owner != rec->rm_owner)) {
552 xfs_btree_mark_sick(cur);
553 error = -EFSCORRUPTED;
554 goto out;
555 }
556
557 /* Check the offset, if necessary. */
558 if (XFS_RMAP_NON_INODE_OWNER(owner))
559 goto out;
560
561 if (flags & XFS_RMAP_BMBT_BLOCK) {
562 if (XFS_IS_CORRUPT(mp,
563 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK))) {
564 xfs_btree_mark_sick(cur);
565 error = -EFSCORRUPTED;
566 goto out;
567 }
568 } else {
569 if (XFS_IS_CORRUPT(mp, rec->rm_offset > offset)) {
570 xfs_btree_mark_sick(cur);
571 error = -EFSCORRUPTED;
572 goto out;
573 }
574 if (XFS_IS_CORRUPT(mp,
575 offset + len > ltoff + rec->rm_blockcount)) {
576 xfs_btree_mark_sick(cur);
577 error = -EFSCORRUPTED;
578 goto out;
579 }
580 }
581
582 out:
583 return error;
584 }
585
586 /*
587 * Find the extent in the rmap btree and remove it.
588 *
589 * The record we find should always be an exact match for the extent that we're
590 * looking for, since we insert them into the btree without modification.
591 *
592 * Special Case #1: when growing the filesystem, we "free" an extent when
593 * growing the last AG. This extent is new space and so it is not tracked as
594 * used space in the btree. The growfs code will pass in an owner of
595 * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
596 * extent. We verify that - the extent lookup result in a record that does not
597 * overlap.
598 *
599 * Special Case #2: EFIs do not record the owner of the extent, so when
600 * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
601 * btree to ignore the owner (i.e. wildcard match) so we don't trigger
602 * corruption checks during log recovery.
603 */
604 STATIC int
605 xfs_rmap_unmap(
606 struct xfs_btree_cur *cur,
607 xfs_agblock_t bno,
608 xfs_extlen_t len,
609 bool unwritten,
610 const struct xfs_owner_info *oinfo)
611 {
612 struct xfs_mount *mp = cur->bc_mp;
613 struct xfs_rmap_irec ltrec;
614 uint64_t ltoff;
615 int error = 0;
616 int i;
617 uint64_t owner;
618 uint64_t offset;
619 unsigned int flags;
620 bool ignore_off;
621
622 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
623 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
624 (flags & XFS_RMAP_BMBT_BLOCK);
625 if (unwritten)
626 flags |= XFS_RMAP_UNWRITTEN;
627 trace_xfs_rmap_unmap(cur, bno, len, unwritten, oinfo);
628
629 /*
630 * We should always have a left record because there's a static record
631 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
632 * will not ever be removed from the tree.
633 */
634 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, <rec, &i);
635 if (error)
636 goto out_error;
637 if (XFS_IS_CORRUPT(mp, i != 1)) {
638 xfs_btree_mark_sick(cur);
639 error = -EFSCORRUPTED;
640 goto out_error;
641 }
642
643 trace_xfs_rmap_lookup_le_range_result(cur, ltrec.rm_startblock,
644 ltrec.rm_blockcount, ltrec.rm_owner, ltrec.rm_offset,
645 ltrec.rm_flags);
646 ltoff = ltrec.rm_offset;
647
648 /*
649 * For growfs, the incoming extent must be beyond the left record we
650 * just found as it is new space and won't be used by anyone. This is
651 * just a corruption check as we don't actually do anything with this
652 * extent. Note that we need to use >= instead of > because it might
653 * be the case that the "left" extent goes all the way to EOFS.
654 */
655 if (owner == XFS_RMAP_OWN_NULL) {
656 if (XFS_IS_CORRUPT(mp,
657 bno <
658 ltrec.rm_startblock + ltrec.rm_blockcount)) {
659 xfs_btree_mark_sick(cur);
660 error = -EFSCORRUPTED;
661 goto out_error;
662 }
663 goto out_done;
664 }
665
666 /*
667 * If we're doing an unknown-owner removal for EFI recovery, we expect
668 * to find the full range in the rmapbt or nothing at all. If we
669 * don't find any rmaps overlapping either end of the range, we're
670 * done. Hopefully this means that the EFI creator already queued
671 * (and finished) a RUI to remove the rmap.
672 */
673 if (owner == XFS_RMAP_OWN_UNKNOWN &&
674 ltrec.rm_startblock + ltrec.rm_blockcount <= bno) {
675 struct xfs_rmap_irec rtrec;
676
677 error = xfs_btree_increment(cur, 0, &i);
678 if (error)
679 goto out_error;
680 if (i == 0)
681 goto out_done;
682 error = xfs_rmap_get_rec(cur, &rtrec, &i);
683 if (error)
684 goto out_error;
685 if (XFS_IS_CORRUPT(mp, i != 1)) {
686 xfs_btree_mark_sick(cur);
687 error = -EFSCORRUPTED;
688 goto out_error;
689 }
690 if (rtrec.rm_startblock >= bno + len)
691 goto out_done;
692 }
693
694 /* Make sure the extent we found covers the entire freeing range. */
695 if (XFS_IS_CORRUPT(mp,
696 ltrec.rm_startblock > bno ||
697 ltrec.rm_startblock + ltrec.rm_blockcount <
698 bno + len)) {
699 xfs_btree_mark_sick(cur);
700 error = -EFSCORRUPTED;
701 goto out_error;
702 }
703
704 /* Check owner information. */
705 error = xfs_rmap_free_check_owner(cur, ltoff, <rec, len, owner,
706 offset, flags);
707 if (error)
708 goto out_error;
709
710 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
711 /* exact match, simply remove the record from rmap tree */
712 trace_xfs_rmap_delete(cur, ltrec.rm_startblock,
713 ltrec.rm_blockcount, ltrec.rm_owner,
714 ltrec.rm_offset, ltrec.rm_flags);
715 error = xfs_btree_delete(cur, &i);
716 if (error)
717 goto out_error;
718 if (XFS_IS_CORRUPT(mp, i != 1)) {
719 xfs_btree_mark_sick(cur);
720 error = -EFSCORRUPTED;
721 goto out_error;
722 }
723 } else if (ltrec.rm_startblock == bno) {
724 /*
725 * overlap left hand side of extent: move the start, trim the
726 * length and update the current record.
727 *
728 * ltbno ltlen
729 * Orig: |oooooooooooooooooooo|
730 * Freeing: |fffffffff|
731 * Result: |rrrrrrrrrr|
732 * bno len
733 */
734 ltrec.rm_startblock += len;
735 ltrec.rm_blockcount -= len;
736 if (!ignore_off)
737 ltrec.rm_offset += len;
738 error = xfs_rmap_update(cur, <rec);
739 if (error)
740 goto out_error;
741 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
742 /*
743 * overlap right hand side of extent: trim the length and update
744 * the current record.
745 *
746 * ltbno ltlen
747 * Orig: |oooooooooooooooooooo|
748 * Freeing: |fffffffff|
749 * Result: |rrrrrrrrrr|
750 * bno len
751 */
752 ltrec.rm_blockcount -= len;
753 error = xfs_rmap_update(cur, <rec);
754 if (error)
755 goto out_error;
756 } else {
757
758 /*
759 * overlap middle of extent: trim the length of the existing
760 * record to the length of the new left-extent size, increment
761 * the insertion position so we can insert a new record
762 * containing the remaining right-extent space.
763 *
764 * ltbno ltlen
765 * Orig: |oooooooooooooooooooo|
766 * Freeing: |fffffffff|
767 * Result: |rrrrr| |rrrr|
768 * bno len
769 */
770 xfs_extlen_t orig_len = ltrec.rm_blockcount;
771
772 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
773 error = xfs_rmap_update(cur, <rec);
774 if (error)
775 goto out_error;
776
777 error = xfs_btree_increment(cur, 0, &i);
778 if (error)
779 goto out_error;
780
781 cur->bc_rec.r.rm_startblock = bno + len;
782 cur->bc_rec.r.rm_blockcount = orig_len - len -
783 ltrec.rm_blockcount;
784 cur->bc_rec.r.rm_owner = ltrec.rm_owner;
785 if (ignore_off)
786 cur->bc_rec.r.rm_offset = 0;
787 else
788 cur->bc_rec.r.rm_offset = offset + len;
789 cur->bc_rec.r.rm_flags = flags;
790 trace_xfs_rmap_insert(cur, cur->bc_rec.r.rm_startblock,
791 cur->bc_rec.r.rm_blockcount,
792 cur->bc_rec.r.rm_owner,
793 cur->bc_rec.r.rm_offset,
794 cur->bc_rec.r.rm_flags);
795 error = xfs_btree_insert(cur, &i);
796 if (error)
797 goto out_error;
798 }
799
800 out_done:
801 trace_xfs_rmap_unmap_done(cur, bno, len, unwritten, oinfo);
802 out_error:
803 if (error)
804 trace_xfs_rmap_unmap_error(cur, error, _RET_IP_);
805 return error;
806 }
807
808 #ifdef CONFIG_XFS_LIVE_HOOKS
809 /*
810 * Use a static key here to reduce the overhead of rmapbt live updates. If
811 * the compiler supports jump labels, the static branch will be replaced by a
812 * nop sled when there are no hook users. Online fsck is currently the only
813 * caller, so this is a reasonable tradeoff.
814 *
815 * Note: Patching the kernel code requires taking the cpu hotplug lock. Other
816 * parts of the kernel allocate memory with that lock held, which means that
817 * XFS callers cannot hold any locks that might be used by memory reclaim or
818 * writeback when calling the static_branch_{inc,dec} functions.
819 */
820 DEFINE_STATIC_XFS_HOOK_SWITCH(xfs_rmap_hooks_switch);
821
822 void
823 xfs_rmap_hook_disable(void)
824 {
825 xfs_hooks_switch_off(&xfs_rmap_hooks_switch);
826 }
827
828 void
829 xfs_rmap_hook_enable(void)
830 {
831 xfs_hooks_switch_on(&xfs_rmap_hooks_switch);
832 }
833
834 /* Call downstream hooks for a reverse mapping update. */
835 static inline void
836 xfs_rmap_update_hook(
837 struct xfs_trans *tp,
838 struct xfs_perag *pag,
839 enum xfs_rmap_intent_type op,
840 xfs_agblock_t startblock,
841 xfs_extlen_t blockcount,
842 bool unwritten,
843 const struct xfs_owner_info *oinfo)
844 {
845 if (xfs_hooks_switched_on(&xfs_rmap_hooks_switch)) {
846 struct xfs_rmap_update_params p = {
847 .startblock = startblock,
848 .blockcount = blockcount,
849 .unwritten = unwritten,
850 .oinfo = *oinfo, /* struct copy */
851 };
852
853 if (pag)
854 xfs_hooks_call(&pag->pag_rmap_update_hooks, op, &p);
855 }
856 }
857
858 /* Call the specified function during a reverse mapping update. */
859 int
860 xfs_rmap_hook_add(
861 struct xfs_perag *pag,
862 struct xfs_rmap_hook *hook)
863 {
864 return xfs_hooks_add(&pag->pag_rmap_update_hooks, &hook->rmap_hook);
865 }
866
867 /* Stop calling the specified function during a reverse mapping update. */
868 void
869 xfs_rmap_hook_del(
870 struct xfs_perag *pag,
871 struct xfs_rmap_hook *hook)
872 {
873 xfs_hooks_del(&pag->pag_rmap_update_hooks, &hook->rmap_hook);
874 }
875
876 /* Configure rmap update hook functions. */
877 void
878 xfs_rmap_hook_setup(
879 struct xfs_rmap_hook *hook,
880 notifier_fn_t mod_fn)
881 {
882 xfs_hook_setup(&hook->rmap_hook, mod_fn);
883 }
884 #else
885 # define xfs_rmap_update_hook(t, p, o, s, b, u, oi) do { } while (0)
886 #endif /* CONFIG_XFS_LIVE_HOOKS */
887
888 /*
889 * Remove a reference to an extent in the rmap btree.
890 */
891 int
892 xfs_rmap_free(
893 struct xfs_trans *tp,
894 struct xfs_buf *agbp,
895 struct xfs_perag *pag,
896 xfs_agblock_t bno,
897 xfs_extlen_t len,
898 const struct xfs_owner_info *oinfo)
899 {
900 struct xfs_mount *mp = tp->t_mountp;
901 struct xfs_btree_cur *cur;
902 int error;
903
904 if (!xfs_has_rmapbt(mp))
905 return 0;
906
907 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
908 xfs_rmap_update_hook(tp, pag, XFS_RMAP_UNMAP, bno, len, false, oinfo);
909 error = xfs_rmap_unmap(cur, bno, len, false, oinfo);
910
911 xfs_btree_del_cursor(cur, error);
912 return error;
913 }
914
915 /*
916 * A mergeable rmap must have the same owner and the same values for
917 * the unwritten, attr_fork, and bmbt flags. The startblock and
918 * offset are checked separately.
919 */
920 static bool
921 xfs_rmap_is_mergeable(
922 struct xfs_rmap_irec *irec,
923 uint64_t owner,
924 unsigned int flags)
925 {
926 if (irec->rm_owner == XFS_RMAP_OWN_NULL)
927 return false;
928 if (irec->rm_owner != owner)
929 return false;
930 if ((flags & XFS_RMAP_UNWRITTEN) ^
931 (irec->rm_flags & XFS_RMAP_UNWRITTEN))
932 return false;
933 if ((flags & XFS_RMAP_ATTR_FORK) ^
934 (irec->rm_flags & XFS_RMAP_ATTR_FORK))
935 return false;
936 if ((flags & XFS_RMAP_BMBT_BLOCK) ^
937 (irec->rm_flags & XFS_RMAP_BMBT_BLOCK))
938 return false;
939 return true;
940 }
941
942 /*
943 * When we allocate a new block, the first thing we do is add a reference to
944 * the extent in the rmap btree. This takes the form of a [agbno, length,
945 * owner, offset] record. Flags are encoded in the high bits of the offset
946 * field.
947 */
948 STATIC int
949 xfs_rmap_map(
950 struct xfs_btree_cur *cur,
951 xfs_agblock_t bno,
952 xfs_extlen_t len,
953 bool unwritten,
954 const struct xfs_owner_info *oinfo)
955 {
956 struct xfs_mount *mp = cur->bc_mp;
957 struct xfs_rmap_irec ltrec;
958 struct xfs_rmap_irec gtrec;
959 int have_gt;
960 int have_lt;
961 int error = 0;
962 int i;
963 uint64_t owner;
964 uint64_t offset;
965 unsigned int flags = 0;
966 bool ignore_off;
967
968 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
969 ASSERT(owner != 0);
970 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
971 (flags & XFS_RMAP_BMBT_BLOCK);
972 if (unwritten)
973 flags |= XFS_RMAP_UNWRITTEN;
974 trace_xfs_rmap_map(cur, bno, len, unwritten, oinfo);
975 ASSERT(!xfs_rmap_should_skip_owner_update(oinfo));
976
977 /*
978 * For the initial lookup, look for an exact match or the left-adjacent
979 * record for our insertion point. This will also give us the record for
980 * start block contiguity tests.
981 */
982 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, <rec,
983 &have_lt);
984 if (error)
985 goto out_error;
986 if (have_lt) {
987 trace_xfs_rmap_lookup_le_range_result(cur, ltrec.rm_startblock,
988 ltrec.rm_blockcount, ltrec.rm_owner,
989 ltrec.rm_offset, ltrec.rm_flags);
990
991 if (!xfs_rmap_is_mergeable(<rec, owner, flags))
992 have_lt = 0;
993 }
994
995 if (XFS_IS_CORRUPT(mp,
996 have_lt != 0 &&
997 ltrec.rm_startblock + ltrec.rm_blockcount > bno)) {
998 xfs_btree_mark_sick(cur);
999 error = -EFSCORRUPTED;
1000 goto out_error;
1001 }
1002
1003 /*
1004 * Increment the cursor to see if we have a right-adjacent record to our
1005 * insertion point. This will give us the record for end block
1006 * contiguity tests.
1007 */
1008 error = xfs_btree_increment(cur, 0, &have_gt);
1009 if (error)
1010 goto out_error;
1011 if (have_gt) {
1012 error = xfs_rmap_get_rec(cur, >rec, &have_gt);
1013 if (error)
1014 goto out_error;
1015 if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
1016 xfs_btree_mark_sick(cur);
1017 error = -EFSCORRUPTED;
1018 goto out_error;
1019 }
1020 if (XFS_IS_CORRUPT(mp, bno + len > gtrec.rm_startblock)) {
1021 xfs_btree_mark_sick(cur);
1022 error = -EFSCORRUPTED;
1023 goto out_error;
1024 }
1025 trace_xfs_rmap_find_right_neighbor_result(cur,
1026 gtrec.rm_startblock, gtrec.rm_blockcount,
1027 gtrec.rm_owner, gtrec.rm_offset,
1028 gtrec.rm_flags);
1029 if (!xfs_rmap_is_mergeable(>rec, owner, flags))
1030 have_gt = 0;
1031 }
1032
1033 /*
1034 * Note: cursor currently points one record to the right of ltrec, even
1035 * if there is no record in the tree to the right.
1036 */
1037 if (have_lt &&
1038 ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
1039 (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) {
1040 /*
1041 * left edge contiguous, merge into left record.
1042 *
1043 * ltbno ltlen
1044 * orig: |ooooooooo|
1045 * adding: |aaaaaaaaa|
1046 * result: |rrrrrrrrrrrrrrrrrrr|
1047 * bno len
1048 */
1049 ltrec.rm_blockcount += len;
1050 if (have_gt &&
1051 bno + len == gtrec.rm_startblock &&
1052 (ignore_off || offset + len == gtrec.rm_offset) &&
1053 (unsigned long)ltrec.rm_blockcount + len +
1054 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) {
1055 /*
1056 * right edge also contiguous, delete right record
1057 * and merge into left record.
1058 *
1059 * ltbno ltlen gtbno gtlen
1060 * orig: |ooooooooo| |ooooooooo|
1061 * adding: |aaaaaaaaa|
1062 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
1063 */
1064 ltrec.rm_blockcount += gtrec.rm_blockcount;
1065 trace_xfs_rmap_delete(cur, gtrec.rm_startblock,
1066 gtrec.rm_blockcount, gtrec.rm_owner,
1067 gtrec.rm_offset, gtrec.rm_flags);
1068 error = xfs_btree_delete(cur, &i);
1069 if (error)
1070 goto out_error;
1071 if (XFS_IS_CORRUPT(mp, i != 1)) {
1072 xfs_btree_mark_sick(cur);
1073 error = -EFSCORRUPTED;
1074 goto out_error;
1075 }
1076 }
1077
1078 /* point the cursor back to the left record and update */
1079 error = xfs_btree_decrement(cur, 0, &have_gt);
1080 if (error)
1081 goto out_error;
1082 error = xfs_rmap_update(cur, <rec);
1083 if (error)
1084 goto out_error;
1085 } else if (have_gt &&
1086 bno + len == gtrec.rm_startblock &&
1087 (ignore_off || offset + len == gtrec.rm_offset)) {
1088 /*
1089 * right edge contiguous, merge into right record.
1090 *
1091 * gtbno gtlen
1092 * Orig: |ooooooooo|
1093 * adding: |aaaaaaaaa|
1094 * Result: |rrrrrrrrrrrrrrrrrrr|
1095 * bno len
1096 */
1097 gtrec.rm_startblock = bno;
1098 gtrec.rm_blockcount += len;
1099 if (!ignore_off)
1100 gtrec.rm_offset = offset;
1101 error = xfs_rmap_update(cur, >rec);
1102 if (error)
1103 goto out_error;
1104 } else {
1105 /*
1106 * no contiguous edge with identical owner, insert
1107 * new record at current cursor position.
1108 */
1109 cur->bc_rec.r.rm_startblock = bno;
1110 cur->bc_rec.r.rm_blockcount = len;
1111 cur->bc_rec.r.rm_owner = owner;
1112 cur->bc_rec.r.rm_offset = offset;
1113 cur->bc_rec.r.rm_flags = flags;
1114 trace_xfs_rmap_insert(cur, bno, len, owner, offset, flags);
1115 error = xfs_btree_insert(cur, &i);
1116 if (error)
1117 goto out_error;
1118 if (XFS_IS_CORRUPT(mp, i != 1)) {
1119 xfs_btree_mark_sick(cur);
1120 error = -EFSCORRUPTED;
1121 goto out_error;
1122 }
1123 }
1124
1125 trace_xfs_rmap_map_done(cur, bno, len, unwritten, oinfo);
1126 out_error:
1127 if (error)
1128 trace_xfs_rmap_map_error(cur, error, _RET_IP_);
1129 return error;
1130 }
1131
1132 /*
1133 * Add a reference to an extent in the rmap btree.
1134 */
1135 int
1136 xfs_rmap_alloc(
1137 struct xfs_trans *tp,
1138 struct xfs_buf *agbp,
1139 struct xfs_perag *pag,
1140 xfs_agblock_t bno,
1141 xfs_extlen_t len,
1142 const struct xfs_owner_info *oinfo)
1143 {
1144 struct xfs_mount *mp = tp->t_mountp;
1145 struct xfs_btree_cur *cur;
1146 int error;
1147
1148 if (!xfs_has_rmapbt(mp))
1149 return 0;
1150
1151 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
1152 xfs_rmap_update_hook(tp, pag, XFS_RMAP_MAP, bno, len, false, oinfo);
1153 error = xfs_rmap_map(cur, bno, len, false, oinfo);
1154
1155 xfs_btree_del_cursor(cur, error);
1156 return error;
1157 }
1158
1159 #define RMAP_LEFT_CONTIG (1 << 0)
1160 #define RMAP_RIGHT_CONTIG (1 << 1)
1161 #define RMAP_LEFT_FILLING (1 << 2)
1162 #define RMAP_RIGHT_FILLING (1 << 3)
1163 #define RMAP_LEFT_VALID (1 << 6)
1164 #define RMAP_RIGHT_VALID (1 << 7)
1165
1166 #define LEFT r[0]
1167 #define RIGHT r[1]
1168 #define PREV r[2]
1169 #define NEW r[3]
1170
1171 /*
1172 * Convert an unwritten extent to a real extent or vice versa.
1173 * Does not handle overlapping extents.
1174 */
1175 STATIC int
1176 xfs_rmap_convert(
1177 struct xfs_btree_cur *cur,
1178 xfs_agblock_t bno,
1179 xfs_extlen_t len,
1180 bool unwritten,
1181 const struct xfs_owner_info *oinfo)
1182 {
1183 struct xfs_mount *mp = cur->bc_mp;
1184 struct xfs_rmap_irec r[4]; /* neighbor extent entries */
1185 /* left is 0, right is 1, */
1186 /* prev is 2, new is 3 */
1187 uint64_t owner;
1188 uint64_t offset;
1189 uint64_t new_endoff;
1190 unsigned int oldext;
1191 unsigned int newext;
1192 unsigned int flags = 0;
1193 int i;
1194 int state = 0;
1195 int error;
1196
1197 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1198 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1199 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1200 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1201 new_endoff = offset + len;
1202 trace_xfs_rmap_convert(cur, bno, len, unwritten, oinfo);
1203
1204 /*
1205 * For the initial lookup, look for an exact match or the left-adjacent
1206 * record for our insertion point. This will also give us the record for
1207 * start block contiguity tests.
1208 */
1209 error = xfs_rmap_lookup_le(cur, bno, owner, offset, oldext, &PREV, &i);
1210 if (error)
1211 goto done;
1212 if (XFS_IS_CORRUPT(mp, i != 1)) {
1213 xfs_btree_mark_sick(cur);
1214 error = -EFSCORRUPTED;
1215 goto done;
1216 }
1217
1218 trace_xfs_rmap_lookup_le_range_result(cur, PREV.rm_startblock,
1219 PREV.rm_blockcount, PREV.rm_owner, PREV.rm_offset,
1220 PREV.rm_flags);
1221
1222 ASSERT(PREV.rm_offset <= offset);
1223 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1224 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1225 newext = ~oldext & XFS_RMAP_UNWRITTEN;
1226
1227 /*
1228 * Set flags determining what part of the previous oldext allocation
1229 * extent is being replaced by a newext allocation.
1230 */
1231 if (PREV.rm_offset == offset)
1232 state |= RMAP_LEFT_FILLING;
1233 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1234 state |= RMAP_RIGHT_FILLING;
1235
1236 /*
1237 * Decrement the cursor to see if we have a left-adjacent record to our
1238 * insertion point. This will give us the record for end block
1239 * contiguity tests.
1240 */
1241 error = xfs_btree_decrement(cur, 0, &i);
1242 if (error)
1243 goto done;
1244 if (i) {
1245 state |= RMAP_LEFT_VALID;
1246 error = xfs_rmap_get_rec(cur, &LEFT, &i);
1247 if (error)
1248 goto done;
1249 if (XFS_IS_CORRUPT(mp, i != 1)) {
1250 xfs_btree_mark_sick(cur);
1251 error = -EFSCORRUPTED;
1252 goto done;
1253 }
1254 if (XFS_IS_CORRUPT(mp,
1255 LEFT.rm_startblock + LEFT.rm_blockcount >
1256 bno)) {
1257 xfs_btree_mark_sick(cur);
1258 error = -EFSCORRUPTED;
1259 goto done;
1260 }
1261 trace_xfs_rmap_find_left_neighbor_result(cur,
1262 LEFT.rm_startblock, LEFT.rm_blockcount,
1263 LEFT.rm_owner, LEFT.rm_offset, LEFT.rm_flags);
1264 if (LEFT.rm_startblock + LEFT.rm_blockcount == bno &&
1265 LEFT.rm_offset + LEFT.rm_blockcount == offset &&
1266 xfs_rmap_is_mergeable(&LEFT, owner, newext))
1267 state |= RMAP_LEFT_CONTIG;
1268 }
1269
1270 /*
1271 * Increment the cursor to see if we have a right-adjacent record to our
1272 * insertion point. This will give us the record for end block
1273 * contiguity tests.
1274 */
1275 error = xfs_btree_increment(cur, 0, &i);
1276 if (error)
1277 goto done;
1278 if (XFS_IS_CORRUPT(mp, i != 1)) {
1279 xfs_btree_mark_sick(cur);
1280 error = -EFSCORRUPTED;
1281 goto done;
1282 }
1283 error = xfs_btree_increment(cur, 0, &i);
1284 if (error)
1285 goto done;
1286 if (i) {
1287 state |= RMAP_RIGHT_VALID;
1288 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1289 if (error)
1290 goto done;
1291 if (XFS_IS_CORRUPT(mp, i != 1)) {
1292 xfs_btree_mark_sick(cur);
1293 error = -EFSCORRUPTED;
1294 goto done;
1295 }
1296 if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) {
1297 xfs_btree_mark_sick(cur);
1298 error = -EFSCORRUPTED;
1299 goto done;
1300 }
1301 trace_xfs_rmap_find_right_neighbor_result(cur,
1302 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1303 RIGHT.rm_owner, RIGHT.rm_offset,
1304 RIGHT.rm_flags);
1305 if (bno + len == RIGHT.rm_startblock &&
1306 offset + len == RIGHT.rm_offset &&
1307 xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1308 state |= RMAP_RIGHT_CONTIG;
1309 }
1310
1311 /* check that left + prev + right is not too long */
1312 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1313 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1314 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1315 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1316 (unsigned long)LEFT.rm_blockcount + len +
1317 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1318 state &= ~RMAP_RIGHT_CONTIG;
1319
1320 trace_xfs_rmap_convert_state(cur, state, _RET_IP_);
1321
1322 /* reset the cursor back to PREV */
1323 error = xfs_rmap_lookup_le(cur, bno, owner, offset, oldext, NULL, &i);
1324 if (error)
1325 goto done;
1326 if (XFS_IS_CORRUPT(mp, i != 1)) {
1327 xfs_btree_mark_sick(cur);
1328 error = -EFSCORRUPTED;
1329 goto done;
1330 }
1331
1332 /*
1333 * Switch out based on the FILLING and CONTIG state bits.
1334 */
1335 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1336 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1337 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1338 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1339 /*
1340 * Setting all of a previous oldext extent to newext.
1341 * The left and right neighbors are both contiguous with new.
1342 */
1343 error = xfs_btree_increment(cur, 0, &i);
1344 if (error)
1345 goto done;
1346 if (XFS_IS_CORRUPT(mp, i != 1)) {
1347 xfs_btree_mark_sick(cur);
1348 error = -EFSCORRUPTED;
1349 goto done;
1350 }
1351 trace_xfs_rmap_delete(cur, RIGHT.rm_startblock,
1352 RIGHT.rm_blockcount, RIGHT.rm_owner,
1353 RIGHT.rm_offset, RIGHT.rm_flags);
1354 error = xfs_btree_delete(cur, &i);
1355 if (error)
1356 goto done;
1357 if (XFS_IS_CORRUPT(mp, i != 1)) {
1358 xfs_btree_mark_sick(cur);
1359 error = -EFSCORRUPTED;
1360 goto done;
1361 }
1362 error = xfs_btree_decrement(cur, 0, &i);
1363 if (error)
1364 goto done;
1365 if (XFS_IS_CORRUPT(mp, i != 1)) {
1366 xfs_btree_mark_sick(cur);
1367 error = -EFSCORRUPTED;
1368 goto done;
1369 }
1370 trace_xfs_rmap_delete(cur, PREV.rm_startblock,
1371 PREV.rm_blockcount, PREV.rm_owner,
1372 PREV.rm_offset, PREV.rm_flags);
1373 error = xfs_btree_delete(cur, &i);
1374 if (error)
1375 goto done;
1376 if (XFS_IS_CORRUPT(mp, i != 1)) {
1377 xfs_btree_mark_sick(cur);
1378 error = -EFSCORRUPTED;
1379 goto done;
1380 }
1381 error = xfs_btree_decrement(cur, 0, &i);
1382 if (error)
1383 goto done;
1384 if (XFS_IS_CORRUPT(mp, i != 1)) {
1385 xfs_btree_mark_sick(cur);
1386 error = -EFSCORRUPTED;
1387 goto done;
1388 }
1389 NEW = LEFT;
1390 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1391 error = xfs_rmap_update(cur, &NEW);
1392 if (error)
1393 goto done;
1394 break;
1395
1396 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1397 /*
1398 * Setting all of a previous oldext extent to newext.
1399 * The left neighbor is contiguous, the right is not.
1400 */
1401 trace_xfs_rmap_delete(cur, PREV.rm_startblock,
1402 PREV.rm_blockcount, PREV.rm_owner,
1403 PREV.rm_offset, PREV.rm_flags);
1404 error = xfs_btree_delete(cur, &i);
1405 if (error)
1406 goto done;
1407 if (XFS_IS_CORRUPT(mp, i != 1)) {
1408 xfs_btree_mark_sick(cur);
1409 error = -EFSCORRUPTED;
1410 goto done;
1411 }
1412 error = xfs_btree_decrement(cur, 0, &i);
1413 if (error)
1414 goto done;
1415 if (XFS_IS_CORRUPT(mp, i != 1)) {
1416 xfs_btree_mark_sick(cur);
1417 error = -EFSCORRUPTED;
1418 goto done;
1419 }
1420 NEW = LEFT;
1421 NEW.rm_blockcount += PREV.rm_blockcount;
1422 error = xfs_rmap_update(cur, &NEW);
1423 if (error)
1424 goto done;
1425 break;
1426
1427 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1428 /*
1429 * Setting all of a previous oldext extent to newext.
1430 * The right neighbor is contiguous, the left is not.
1431 */
1432 error = xfs_btree_increment(cur, 0, &i);
1433 if (error)
1434 goto done;
1435 if (XFS_IS_CORRUPT(mp, i != 1)) {
1436 xfs_btree_mark_sick(cur);
1437 error = -EFSCORRUPTED;
1438 goto done;
1439 }
1440 trace_xfs_rmap_delete(cur, RIGHT.rm_startblock,
1441 RIGHT.rm_blockcount, RIGHT.rm_owner,
1442 RIGHT.rm_offset, RIGHT.rm_flags);
1443 error = xfs_btree_delete(cur, &i);
1444 if (error)
1445 goto done;
1446 if (XFS_IS_CORRUPT(mp, i != 1)) {
1447 xfs_btree_mark_sick(cur);
1448 error = -EFSCORRUPTED;
1449 goto done;
1450 }
1451 error = xfs_btree_decrement(cur, 0, &i);
1452 if (error)
1453 goto done;
1454 if (XFS_IS_CORRUPT(mp, i != 1)) {
1455 xfs_btree_mark_sick(cur);
1456 error = -EFSCORRUPTED;
1457 goto done;
1458 }
1459 NEW = PREV;
1460 NEW.rm_blockcount = len + RIGHT.rm_blockcount;
1461 NEW.rm_flags = newext;
1462 error = xfs_rmap_update(cur, &NEW);
1463 if (error)
1464 goto done;
1465 break;
1466
1467 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1468 /*
1469 * Setting all of a previous oldext extent to newext.
1470 * Neither the left nor right neighbors are contiguous with
1471 * the new one.
1472 */
1473 NEW = PREV;
1474 NEW.rm_flags = newext;
1475 error = xfs_rmap_update(cur, &NEW);
1476 if (error)
1477 goto done;
1478 break;
1479
1480 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1481 /*
1482 * Setting the first part of a previous oldext extent to newext.
1483 * The left neighbor is contiguous.
1484 */
1485 NEW = PREV;
1486 NEW.rm_offset += len;
1487 NEW.rm_startblock += len;
1488 NEW.rm_blockcount -= len;
1489 error = xfs_rmap_update(cur, &NEW);
1490 if (error)
1491 goto done;
1492 error = xfs_btree_decrement(cur, 0, &i);
1493 if (error)
1494 goto done;
1495 NEW = LEFT;
1496 NEW.rm_blockcount += len;
1497 error = xfs_rmap_update(cur, &NEW);
1498 if (error)
1499 goto done;
1500 break;
1501
1502 case RMAP_LEFT_FILLING:
1503 /*
1504 * Setting the first part of a previous oldext extent to newext.
1505 * The left neighbor is not contiguous.
1506 */
1507 NEW = PREV;
1508 NEW.rm_startblock += len;
1509 NEW.rm_offset += len;
1510 NEW.rm_blockcount -= len;
1511 error = xfs_rmap_update(cur, &NEW);
1512 if (error)
1513 goto done;
1514 NEW.rm_startblock = bno;
1515 NEW.rm_owner = owner;
1516 NEW.rm_offset = offset;
1517 NEW.rm_blockcount = len;
1518 NEW.rm_flags = newext;
1519 cur->bc_rec.r = NEW;
1520 trace_xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1521 error = xfs_btree_insert(cur, &i);
1522 if (error)
1523 goto done;
1524 if (XFS_IS_CORRUPT(mp, i != 1)) {
1525 xfs_btree_mark_sick(cur);
1526 error = -EFSCORRUPTED;
1527 goto done;
1528 }
1529 break;
1530
1531 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1532 /*
1533 * Setting the last part of a previous oldext extent to newext.
1534 * The right neighbor is contiguous with the new allocation.
1535 */
1536 NEW = PREV;
1537 NEW.rm_blockcount -= len;
1538 error = xfs_rmap_update(cur, &NEW);
1539 if (error)
1540 goto done;
1541 error = xfs_btree_increment(cur, 0, &i);
1542 if (error)
1543 goto done;
1544 NEW = RIGHT;
1545 NEW.rm_offset = offset;
1546 NEW.rm_startblock = bno;
1547 NEW.rm_blockcount += len;
1548 error = xfs_rmap_update(cur, &NEW);
1549 if (error)
1550 goto done;
1551 break;
1552
1553 case RMAP_RIGHT_FILLING:
1554 /*
1555 * Setting the last part of a previous oldext extent to newext.
1556 * The right neighbor is not contiguous.
1557 */
1558 NEW = PREV;
1559 NEW.rm_blockcount -= len;
1560 error = xfs_rmap_update(cur, &NEW);
1561 if (error)
1562 goto done;
1563 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1564 oldext, &i);
1565 if (error)
1566 goto done;
1567 if (XFS_IS_CORRUPT(mp, i != 0)) {
1568 xfs_btree_mark_sick(cur);
1569 error = -EFSCORRUPTED;
1570 goto done;
1571 }
1572 NEW.rm_startblock = bno;
1573 NEW.rm_owner = owner;
1574 NEW.rm_offset = offset;
1575 NEW.rm_blockcount = len;
1576 NEW.rm_flags = newext;
1577 cur->bc_rec.r = NEW;
1578 trace_xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1579 error = xfs_btree_insert(cur, &i);
1580 if (error)
1581 goto done;
1582 if (XFS_IS_CORRUPT(mp, i != 1)) {
1583 xfs_btree_mark_sick(cur);
1584 error = -EFSCORRUPTED;
1585 goto done;
1586 }
1587 break;
1588
1589 case 0:
1590 /*
1591 * Setting the middle part of a previous oldext extent to
1592 * newext. Contiguity is impossible here.
1593 * One extent becomes three extents.
1594 */
1595 /* new right extent - oldext */
1596 NEW.rm_startblock = bno + len;
1597 NEW.rm_owner = owner;
1598 NEW.rm_offset = new_endoff;
1599 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1600 new_endoff;
1601 NEW.rm_flags = PREV.rm_flags;
1602 error = xfs_rmap_update(cur, &NEW);
1603 if (error)
1604 goto done;
1605 /* new left extent - oldext */
1606 NEW = PREV;
1607 NEW.rm_blockcount = offset - PREV.rm_offset;
1608 cur->bc_rec.r = NEW;
1609 trace_xfs_rmap_insert(cur, NEW.rm_startblock,
1610 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1611 NEW.rm_flags);
1612 error = xfs_btree_insert(cur, &i);
1613 if (error)
1614 goto done;
1615 if (XFS_IS_CORRUPT(mp, i != 1)) {
1616 xfs_btree_mark_sick(cur);
1617 error = -EFSCORRUPTED;
1618 goto done;
1619 }
1620 /*
1621 * Reset the cursor to the position of the new extent
1622 * we are about to insert as we can't trust it after
1623 * the previous insert.
1624 */
1625 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1626 oldext, &i);
1627 if (error)
1628 goto done;
1629 if (XFS_IS_CORRUPT(mp, i != 0)) {
1630 xfs_btree_mark_sick(cur);
1631 error = -EFSCORRUPTED;
1632 goto done;
1633 }
1634 /* new middle extent - newext */
1635 cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN;
1636 cur->bc_rec.r.rm_flags |= newext;
1637 trace_xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1638 error = xfs_btree_insert(cur, &i);
1639 if (error)
1640 goto done;
1641 if (XFS_IS_CORRUPT(mp, i != 1)) {
1642 xfs_btree_mark_sick(cur);
1643 error = -EFSCORRUPTED;
1644 goto done;
1645 }
1646 break;
1647
1648 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1649 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1650 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1651 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1652 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1653 case RMAP_LEFT_CONTIG:
1654 case RMAP_RIGHT_CONTIG:
1655 /*
1656 * These cases are all impossible.
1657 */
1658 ASSERT(0);
1659 }
1660
1661 trace_xfs_rmap_convert_done(cur, bno, len, unwritten, oinfo);
1662 done:
1663 if (error)
1664 trace_xfs_rmap_convert_error(cur, error, _RET_IP_);
1665 return error;
1666 }
1667
1668 /*
1669 * Convert an unwritten extent to a real extent or vice versa. If there is no
1670 * possibility of overlapping extents, delegate to the simpler convert
1671 * function.
1672 */
1673 STATIC int
1674 xfs_rmap_convert_shared(
1675 struct xfs_btree_cur *cur,
1676 xfs_agblock_t bno,
1677 xfs_extlen_t len,
1678 bool unwritten,
1679 const struct xfs_owner_info *oinfo)
1680 {
1681 struct xfs_mount *mp = cur->bc_mp;
1682 struct xfs_rmap_irec r[4]; /* neighbor extent entries */
1683 /* left is 0, right is 1, */
1684 /* prev is 2, new is 3 */
1685 uint64_t owner;
1686 uint64_t offset;
1687 uint64_t new_endoff;
1688 unsigned int oldext;
1689 unsigned int newext;
1690 unsigned int flags = 0;
1691 int i;
1692 int state = 0;
1693 int error;
1694
1695 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1696 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1697 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1698 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1699 new_endoff = offset + len;
1700 trace_xfs_rmap_convert(cur, bno, len, unwritten, oinfo);
1701
1702 /*
1703 * For the initial lookup, look for and exact match or the left-adjacent
1704 * record for our insertion point. This will also give us the record for
1705 * start block contiguity tests.
1706 */
1707 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, oldext,
1708 &PREV, &i);
1709 if (error)
1710 goto done;
1711 if (XFS_IS_CORRUPT(mp, i != 1)) {
1712 xfs_btree_mark_sick(cur);
1713 error = -EFSCORRUPTED;
1714 goto done;
1715 }
1716
1717 ASSERT(PREV.rm_offset <= offset);
1718 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1719 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1720 newext = ~oldext & XFS_RMAP_UNWRITTEN;
1721
1722 /*
1723 * Set flags determining what part of the previous oldext allocation
1724 * extent is being replaced by a newext allocation.
1725 */
1726 if (PREV.rm_offset == offset)
1727 state |= RMAP_LEFT_FILLING;
1728 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1729 state |= RMAP_RIGHT_FILLING;
1730
1731 /* Is there a left record that abuts our range? */
1732 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext,
1733 &LEFT, &i);
1734 if (error)
1735 goto done;
1736 if (i) {
1737 state |= RMAP_LEFT_VALID;
1738 if (XFS_IS_CORRUPT(mp,
1739 LEFT.rm_startblock + LEFT.rm_blockcount >
1740 bno)) {
1741 xfs_btree_mark_sick(cur);
1742 error = -EFSCORRUPTED;
1743 goto done;
1744 }
1745 if (xfs_rmap_is_mergeable(&LEFT, owner, newext))
1746 state |= RMAP_LEFT_CONTIG;
1747 }
1748
1749 /* Is there a right record that abuts our range? */
1750 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1751 newext, &i);
1752 if (error)
1753 goto done;
1754 if (i) {
1755 state |= RMAP_RIGHT_VALID;
1756 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1757 if (error)
1758 goto done;
1759 if (XFS_IS_CORRUPT(mp, i != 1)) {
1760 xfs_btree_mark_sick(cur);
1761 error = -EFSCORRUPTED;
1762 goto done;
1763 }
1764 if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) {
1765 xfs_btree_mark_sick(cur);
1766 error = -EFSCORRUPTED;
1767 goto done;
1768 }
1769 trace_xfs_rmap_find_right_neighbor_result(cur,
1770 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1771 RIGHT.rm_owner, RIGHT.rm_offset,
1772 RIGHT.rm_flags);
1773 if (xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1774 state |= RMAP_RIGHT_CONTIG;
1775 }
1776
1777 /* check that left + prev + right is not too long */
1778 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1779 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1780 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1781 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1782 (unsigned long)LEFT.rm_blockcount + len +
1783 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1784 state &= ~RMAP_RIGHT_CONTIG;
1785
1786 trace_xfs_rmap_convert_state(cur, state, _RET_IP_);
1787 /*
1788 * Switch out based on the FILLING and CONTIG state bits.
1789 */
1790 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1791 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1792 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1793 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1794 /*
1795 * Setting all of a previous oldext extent to newext.
1796 * The left and right neighbors are both contiguous with new.
1797 */
1798 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1799 RIGHT.rm_blockcount, RIGHT.rm_owner,
1800 RIGHT.rm_offset, RIGHT.rm_flags);
1801 if (error)
1802 goto done;
1803 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1804 PREV.rm_blockcount, PREV.rm_owner,
1805 PREV.rm_offset, PREV.rm_flags);
1806 if (error)
1807 goto done;
1808 NEW = LEFT;
1809 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1810 NEW.rm_blockcount, NEW.rm_owner,
1811 NEW.rm_offset, NEW.rm_flags, &i);
1812 if (error)
1813 goto done;
1814 if (XFS_IS_CORRUPT(mp, i != 1)) {
1815 xfs_btree_mark_sick(cur);
1816 error = -EFSCORRUPTED;
1817 goto done;
1818 }
1819 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1820 error = xfs_rmap_update(cur, &NEW);
1821 if (error)
1822 goto done;
1823 break;
1824
1825 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1826 /*
1827 * Setting all of a previous oldext extent to newext.
1828 * The left neighbor is contiguous, the right is not.
1829 */
1830 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1831 PREV.rm_blockcount, PREV.rm_owner,
1832 PREV.rm_offset, PREV.rm_flags);
1833 if (error)
1834 goto done;
1835 NEW = LEFT;
1836 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1837 NEW.rm_blockcount, NEW.rm_owner,
1838 NEW.rm_offset, NEW.rm_flags, &i);
1839 if (error)
1840 goto done;
1841 if (XFS_IS_CORRUPT(mp, i != 1)) {
1842 xfs_btree_mark_sick(cur);
1843 error = -EFSCORRUPTED;
1844 goto done;
1845 }
1846 NEW.rm_blockcount += PREV.rm_blockcount;
1847 error = xfs_rmap_update(cur, &NEW);
1848 if (error)
1849 goto done;
1850 break;
1851
1852 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1853 /*
1854 * Setting all of a previous oldext extent to newext.
1855 * The right neighbor is contiguous, the left is not.
1856 */
1857 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1858 RIGHT.rm_blockcount, RIGHT.rm_owner,
1859 RIGHT.rm_offset, RIGHT.rm_flags);
1860 if (error)
1861 goto done;
1862 NEW = PREV;
1863 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1864 NEW.rm_blockcount, NEW.rm_owner,
1865 NEW.rm_offset, NEW.rm_flags, &i);
1866 if (error)
1867 goto done;
1868 if (XFS_IS_CORRUPT(mp, i != 1)) {
1869 xfs_btree_mark_sick(cur);
1870 error = -EFSCORRUPTED;
1871 goto done;
1872 }
1873 NEW.rm_blockcount += RIGHT.rm_blockcount;
1874 NEW.rm_flags = RIGHT.rm_flags;
1875 error = xfs_rmap_update(cur, &NEW);
1876 if (error)
1877 goto done;
1878 break;
1879
1880 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1881 /*
1882 * Setting all of a previous oldext extent to newext.
1883 * Neither the left nor right neighbors are contiguous with
1884 * the new one.
1885 */
1886 NEW = PREV;
1887 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1888 NEW.rm_blockcount, NEW.rm_owner,
1889 NEW.rm_offset, NEW.rm_flags, &i);
1890 if (error)
1891 goto done;
1892 if (XFS_IS_CORRUPT(mp, i != 1)) {
1893 xfs_btree_mark_sick(cur);
1894 error = -EFSCORRUPTED;
1895 goto done;
1896 }
1897 NEW.rm_flags = newext;
1898 error = xfs_rmap_update(cur, &NEW);
1899 if (error)
1900 goto done;
1901 break;
1902
1903 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1904 /*
1905 * Setting the first part of a previous oldext extent to newext.
1906 * The left neighbor is contiguous.
1907 */
1908 NEW = PREV;
1909 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1910 NEW.rm_blockcount, NEW.rm_owner,
1911 NEW.rm_offset, NEW.rm_flags);
1912 if (error)
1913 goto done;
1914 NEW.rm_offset += len;
1915 NEW.rm_startblock += len;
1916 NEW.rm_blockcount -= len;
1917 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1918 NEW.rm_blockcount, NEW.rm_owner,
1919 NEW.rm_offset, NEW.rm_flags);
1920 if (error)
1921 goto done;
1922 NEW = LEFT;
1923 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1924 NEW.rm_blockcount, NEW.rm_owner,
1925 NEW.rm_offset, NEW.rm_flags, &i);
1926 if (error)
1927 goto done;
1928 if (XFS_IS_CORRUPT(mp, i != 1)) {
1929 xfs_btree_mark_sick(cur);
1930 error = -EFSCORRUPTED;
1931 goto done;
1932 }
1933 NEW.rm_blockcount += len;
1934 error = xfs_rmap_update(cur, &NEW);
1935 if (error)
1936 goto done;
1937 break;
1938
1939 case RMAP_LEFT_FILLING:
1940 /*
1941 * Setting the first part of a previous oldext extent to newext.
1942 * The left neighbor is not contiguous.
1943 */
1944 NEW = PREV;
1945 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1946 NEW.rm_blockcount, NEW.rm_owner,
1947 NEW.rm_offset, NEW.rm_flags);
1948 if (error)
1949 goto done;
1950 NEW.rm_offset += len;
1951 NEW.rm_startblock += len;
1952 NEW.rm_blockcount -= len;
1953 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1954 NEW.rm_blockcount, NEW.rm_owner,
1955 NEW.rm_offset, NEW.rm_flags);
1956 if (error)
1957 goto done;
1958 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1959 if (error)
1960 goto done;
1961 break;
1962
1963 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1964 /*
1965 * Setting the last part of a previous oldext extent to newext.
1966 * The right neighbor is contiguous with the new allocation.
1967 */
1968 NEW = PREV;
1969 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1970 NEW.rm_blockcount, NEW.rm_owner,
1971 NEW.rm_offset, NEW.rm_flags, &i);
1972 if (error)
1973 goto done;
1974 if (XFS_IS_CORRUPT(mp, i != 1)) {
1975 xfs_btree_mark_sick(cur);
1976 error = -EFSCORRUPTED;
1977 goto done;
1978 }
1979 NEW.rm_blockcount = offset - NEW.rm_offset;
1980 error = xfs_rmap_update(cur, &NEW);
1981 if (error)
1982 goto done;
1983 NEW = RIGHT;
1984 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1985 NEW.rm_blockcount, NEW.rm_owner,
1986 NEW.rm_offset, NEW.rm_flags);
1987 if (error)
1988 goto done;
1989 NEW.rm_offset = offset;
1990 NEW.rm_startblock = bno;
1991 NEW.rm_blockcount += len;
1992 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1993 NEW.rm_blockcount, NEW.rm_owner,
1994 NEW.rm_offset, NEW.rm_flags);
1995 if (error)
1996 goto done;
1997 break;
1998
1999 case RMAP_RIGHT_FILLING:
2000 /*
2001 * Setting the last part of a previous oldext extent to newext.
2002 * The right neighbor is not contiguous.
2003 */
2004 NEW = PREV;
2005 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
2006 NEW.rm_blockcount, NEW.rm_owner,
2007 NEW.rm_offset, NEW.rm_flags, &i);
2008 if (error)
2009 goto done;
2010 if (XFS_IS_CORRUPT(mp, i != 1)) {
2011 xfs_btree_mark_sick(cur);
2012 error = -EFSCORRUPTED;
2013 goto done;
2014 }
2015 NEW.rm_blockcount -= len;
2016 error = xfs_rmap_update(cur, &NEW);
2017 if (error)
2018 goto done;
2019 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
2020 if (error)
2021 goto done;
2022 break;
2023
2024 case 0:
2025 /*
2026 * Setting the middle part of a previous oldext extent to
2027 * newext. Contiguity is impossible here.
2028 * One extent becomes three extents.
2029 */
2030 /* new right extent - oldext */
2031 NEW.rm_startblock = bno + len;
2032 NEW.rm_owner = owner;
2033 NEW.rm_offset = new_endoff;
2034 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
2035 new_endoff;
2036 NEW.rm_flags = PREV.rm_flags;
2037 error = xfs_rmap_insert(cur, NEW.rm_startblock,
2038 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
2039 NEW.rm_flags);
2040 if (error)
2041 goto done;
2042 /* new left extent - oldext */
2043 NEW = PREV;
2044 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
2045 NEW.rm_blockcount, NEW.rm_owner,
2046 NEW.rm_offset, NEW.rm_flags, &i);
2047 if (error)
2048 goto done;
2049 if (XFS_IS_CORRUPT(mp, i != 1)) {
2050 xfs_btree_mark_sick(cur);
2051 error = -EFSCORRUPTED;
2052 goto done;
2053 }
2054 NEW.rm_blockcount = offset - NEW.rm_offset;
2055 error = xfs_rmap_update(cur, &NEW);
2056 if (error)
2057 goto done;
2058 /* new middle extent - newext */
2059 NEW.rm_startblock = bno;
2060 NEW.rm_blockcount = len;
2061 NEW.rm_owner = owner;
2062 NEW.rm_offset = offset;
2063 NEW.rm_flags = newext;
2064 error = xfs_rmap_insert(cur, NEW.rm_startblock,
2065 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
2066 NEW.rm_flags);
2067 if (error)
2068 goto done;
2069 break;
2070
2071 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
2072 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
2073 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
2074 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
2075 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
2076 case RMAP_LEFT_CONTIG:
2077 case RMAP_RIGHT_CONTIG:
2078 /*
2079 * These cases are all impossible.
2080 */
2081 ASSERT(0);
2082 }
2083
2084 trace_xfs_rmap_convert_done(cur, bno, len, unwritten, oinfo);
2085 done:
2086 if (error)
2087 trace_xfs_rmap_convert_error(cur, error, _RET_IP_);
2088 return error;
2089 }
2090
2091 #undef NEW
2092 #undef LEFT
2093 #undef RIGHT
2094 #undef PREV
2095
2096 /*
2097 * Find an extent in the rmap btree and unmap it. For rmap extent types that
2098 * can overlap (data fork rmaps on reflink filesystems) we must be careful
2099 * that the prev/next records in the btree might belong to another owner.
2100 * Therefore we must use delete+insert to alter any of the key fields.
2101 *
2102 * For every other situation there can only be one owner for a given extent,
2103 * so we can call the regular _free function.
2104 */
2105 STATIC int
2106 xfs_rmap_unmap_shared(
2107 struct xfs_btree_cur *cur,
2108 xfs_agblock_t bno,
2109 xfs_extlen_t len,
2110 bool unwritten,
2111 const struct xfs_owner_info *oinfo)
2112 {
2113 struct xfs_mount *mp = cur->bc_mp;
2114 struct xfs_rmap_irec ltrec;
2115 uint64_t ltoff;
2116 int error = 0;
2117 int i;
2118 uint64_t owner;
2119 uint64_t offset;
2120 unsigned int flags;
2121
2122 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2123 if (unwritten)
2124 flags |= XFS_RMAP_UNWRITTEN;
2125 trace_xfs_rmap_unmap(cur, bno, len, unwritten, oinfo);
2126
2127 /*
2128 * We should always have a left record because there's a static record
2129 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
2130 * will not ever be removed from the tree.
2131 */
2132 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
2133 <rec, &i);
2134 if (error)
2135 goto out_error;
2136 if (XFS_IS_CORRUPT(mp, i != 1)) {
2137 xfs_btree_mark_sick(cur);
2138 error = -EFSCORRUPTED;
2139 goto out_error;
2140 }
2141 ltoff = ltrec.rm_offset;
2142
2143 /* Make sure the extent we found covers the entire freeing range. */
2144 if (XFS_IS_CORRUPT(mp,
2145 ltrec.rm_startblock > bno ||
2146 ltrec.rm_startblock + ltrec.rm_blockcount <
2147 bno + len)) {
2148 xfs_btree_mark_sick(cur);
2149 error = -EFSCORRUPTED;
2150 goto out_error;
2151 }
2152
2153 /* Make sure the owner matches what we expect to find in the tree. */
2154 if (XFS_IS_CORRUPT(mp, owner != ltrec.rm_owner)) {
2155 xfs_btree_mark_sick(cur);
2156 error = -EFSCORRUPTED;
2157 goto out_error;
2158 }
2159
2160 /* Make sure the unwritten flag matches. */
2161 if (XFS_IS_CORRUPT(mp,
2162 (flags & XFS_RMAP_UNWRITTEN) !=
2163 (ltrec.rm_flags & XFS_RMAP_UNWRITTEN))) {
2164 xfs_btree_mark_sick(cur);
2165 error = -EFSCORRUPTED;
2166 goto out_error;
2167 }
2168
2169 /* Check the offset. */
2170 if (XFS_IS_CORRUPT(mp, ltrec.rm_offset > offset)) {
2171 xfs_btree_mark_sick(cur);
2172 error = -EFSCORRUPTED;
2173 goto out_error;
2174 }
2175 if (XFS_IS_CORRUPT(mp, offset > ltoff + ltrec.rm_blockcount)) {
2176 xfs_btree_mark_sick(cur);
2177 error = -EFSCORRUPTED;
2178 goto out_error;
2179 }
2180
2181 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
2182 /* Exact match, simply remove the record from rmap tree. */
2183 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
2184 ltrec.rm_blockcount, ltrec.rm_owner,
2185 ltrec.rm_offset, ltrec.rm_flags);
2186 if (error)
2187 goto out_error;
2188 } else if (ltrec.rm_startblock == bno) {
2189 /*
2190 * Overlap left hand side of extent: move the start, trim the
2191 * length and update the current record.
2192 *
2193 * ltbno ltlen
2194 * Orig: |oooooooooooooooooooo|
2195 * Freeing: |fffffffff|
2196 * Result: |rrrrrrrrrr|
2197 * bno len
2198 */
2199
2200 /* Delete prev rmap. */
2201 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
2202 ltrec.rm_blockcount, ltrec.rm_owner,
2203 ltrec.rm_offset, ltrec.rm_flags);
2204 if (error)
2205 goto out_error;
2206
2207 /* Add an rmap at the new offset. */
2208 ltrec.rm_startblock += len;
2209 ltrec.rm_blockcount -= len;
2210 ltrec.rm_offset += len;
2211 error = xfs_rmap_insert(cur, ltrec.rm_startblock,
2212 ltrec.rm_blockcount, ltrec.rm_owner,
2213 ltrec.rm_offset, ltrec.rm_flags);
2214 if (error)
2215 goto out_error;
2216 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
2217 /*
2218 * Overlap right hand side of extent: trim the length and
2219 * update the current record.
2220 *
2221 * ltbno ltlen
2222 * Orig: |oooooooooooooooooooo|
2223 * Freeing: |fffffffff|
2224 * Result: |rrrrrrrrrr|
2225 * bno len
2226 */
2227 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2228 ltrec.rm_blockcount, ltrec.rm_owner,
2229 ltrec.rm_offset, ltrec.rm_flags, &i);
2230 if (error)
2231 goto out_error;
2232 if (XFS_IS_CORRUPT(mp, i != 1)) {
2233 xfs_btree_mark_sick(cur);
2234 error = -EFSCORRUPTED;
2235 goto out_error;
2236 }
2237 ltrec.rm_blockcount -= len;
2238 error = xfs_rmap_update(cur, <rec);
2239 if (error)
2240 goto out_error;
2241 } else {
2242 /*
2243 * Overlap middle of extent: trim the length of the existing
2244 * record to the length of the new left-extent size, increment
2245 * the insertion position so we can insert a new record
2246 * containing the remaining right-extent space.
2247 *
2248 * ltbno ltlen
2249 * Orig: |oooooooooooooooooooo|
2250 * Freeing: |fffffffff|
2251 * Result: |rrrrr| |rrrr|
2252 * bno len
2253 */
2254 xfs_extlen_t orig_len = ltrec.rm_blockcount;
2255
2256 /* Shrink the left side of the rmap */
2257 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2258 ltrec.rm_blockcount, ltrec.rm_owner,
2259 ltrec.rm_offset, ltrec.rm_flags, &i);
2260 if (error)
2261 goto out_error;
2262 if (XFS_IS_CORRUPT(mp, i != 1)) {
2263 xfs_btree_mark_sick(cur);
2264 error = -EFSCORRUPTED;
2265 goto out_error;
2266 }
2267 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
2268 error = xfs_rmap_update(cur, <rec);
2269 if (error)
2270 goto out_error;
2271
2272 /* Add an rmap at the new offset */
2273 error = xfs_rmap_insert(cur, bno + len,
2274 orig_len - len - ltrec.rm_blockcount,
2275 ltrec.rm_owner, offset + len,
2276 ltrec.rm_flags);
2277 if (error)
2278 goto out_error;
2279 }
2280
2281 trace_xfs_rmap_unmap_done(cur, bno, len, unwritten, oinfo);
2282 out_error:
2283 if (error)
2284 trace_xfs_rmap_unmap_error(cur, error, _RET_IP_);
2285 return error;
2286 }
2287
2288 /*
2289 * Find an extent in the rmap btree and map it. For rmap extent types that
2290 * can overlap (data fork rmaps on reflink filesystems) we must be careful
2291 * that the prev/next records in the btree might belong to another owner.
2292 * Therefore we must use delete+insert to alter any of the key fields.
2293 *
2294 * For every other situation there can only be one owner for a given extent,
2295 * so we can call the regular _alloc function.
2296 */
2297 STATIC int
2298 xfs_rmap_map_shared(
2299 struct xfs_btree_cur *cur,
2300 xfs_agblock_t bno,
2301 xfs_extlen_t len,
2302 bool unwritten,
2303 const struct xfs_owner_info *oinfo)
2304 {
2305 struct xfs_mount *mp = cur->bc_mp;
2306 struct xfs_rmap_irec ltrec;
2307 struct xfs_rmap_irec gtrec;
2308 int have_gt;
2309 int have_lt;
2310 int error = 0;
2311 int i;
2312 uint64_t owner;
2313 uint64_t offset;
2314 unsigned int flags = 0;
2315
2316 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2317 if (unwritten)
2318 flags |= XFS_RMAP_UNWRITTEN;
2319 trace_xfs_rmap_map(cur, bno, len, unwritten, oinfo);
2320
2321 /* Is there a left record that abuts our range? */
2322 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags,
2323 <rec, &have_lt);
2324 if (error)
2325 goto out_error;
2326 if (have_lt &&
2327 !xfs_rmap_is_mergeable(<rec, owner, flags))
2328 have_lt = 0;
2329
2330 /* Is there a right record that abuts our range? */
2331 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
2332 flags, &have_gt);
2333 if (error)
2334 goto out_error;
2335 if (have_gt) {
2336 error = xfs_rmap_get_rec(cur, >rec, &have_gt);
2337 if (error)
2338 goto out_error;
2339 if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
2340 xfs_btree_mark_sick(cur);
2341 error = -EFSCORRUPTED;
2342 goto out_error;
2343 }
2344 trace_xfs_rmap_find_right_neighbor_result(cur,
2345 gtrec.rm_startblock, gtrec.rm_blockcount,
2346 gtrec.rm_owner, gtrec.rm_offset,
2347 gtrec.rm_flags);
2348
2349 if (!xfs_rmap_is_mergeable(>rec, owner, flags))
2350 have_gt = 0;
2351 }
2352
2353 if (have_lt &&
2354 ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
2355 ltrec.rm_offset + ltrec.rm_blockcount == offset) {
2356 /*
2357 * Left edge contiguous, merge into left record.
2358 *
2359 * ltbno ltlen
2360 * orig: |ooooooooo|
2361 * adding: |aaaaaaaaa|
2362 * result: |rrrrrrrrrrrrrrrrrrr|
2363 * bno len
2364 */
2365 ltrec.rm_blockcount += len;
2366 if (have_gt &&
2367 bno + len == gtrec.rm_startblock &&
2368 offset + len == gtrec.rm_offset) {
2369 /*
2370 * Right edge also contiguous, delete right record
2371 * and merge into left record.
2372 *
2373 * ltbno ltlen gtbno gtlen
2374 * orig: |ooooooooo| |ooooooooo|
2375 * adding: |aaaaaaaaa|
2376 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
2377 */
2378 ltrec.rm_blockcount += gtrec.rm_blockcount;
2379 error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2380 gtrec.rm_blockcount, gtrec.rm_owner,
2381 gtrec.rm_offset, gtrec.rm_flags);
2382 if (error)
2383 goto out_error;
2384 }
2385
2386 /* Point the cursor back to the left record and update. */
2387 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2388 ltrec.rm_blockcount, ltrec.rm_owner,
2389 ltrec.rm_offset, ltrec.rm_flags, &i);
2390 if (error)
2391 goto out_error;
2392 if (XFS_IS_CORRUPT(mp, i != 1)) {
2393 xfs_btree_mark_sick(cur);
2394 error = -EFSCORRUPTED;
2395 goto out_error;
2396 }
2397
2398 error = xfs_rmap_update(cur, <rec);
2399 if (error)
2400 goto out_error;
2401 } else if (have_gt &&
2402 bno + len == gtrec.rm_startblock &&
2403 offset + len == gtrec.rm_offset) {
2404 /*
2405 * Right edge contiguous, merge into right record.
2406 *
2407 * gtbno gtlen
2408 * Orig: |ooooooooo|
2409 * adding: |aaaaaaaaa|
2410 * Result: |rrrrrrrrrrrrrrrrrrr|
2411 * bno len
2412 */
2413 /* Delete the old record. */
2414 error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2415 gtrec.rm_blockcount, gtrec.rm_owner,
2416 gtrec.rm_offset, gtrec.rm_flags);
2417 if (error)
2418 goto out_error;
2419
2420 /* Move the start and re-add it. */
2421 gtrec.rm_startblock = bno;
2422 gtrec.rm_blockcount += len;
2423 gtrec.rm_offset = offset;
2424 error = xfs_rmap_insert(cur, gtrec.rm_startblock,
2425 gtrec.rm_blockcount, gtrec.rm_owner,
2426 gtrec.rm_offset, gtrec.rm_flags);
2427 if (error)
2428 goto out_error;
2429 } else {
2430 /*
2431 * No contiguous edge with identical owner, insert
2432 * new record at current cursor position.
2433 */
2434 error = xfs_rmap_insert(cur, bno, len, owner, offset, flags);
2435 if (error)
2436 goto out_error;
2437 }
2438
2439 trace_xfs_rmap_map_done(cur, bno, len, unwritten, oinfo);
2440 out_error:
2441 if (error)
2442 trace_xfs_rmap_map_error(cur, error, _RET_IP_);
2443 return error;
2444 }
2445
2446 /* Insert a raw rmap into the rmapbt. */
2447 int
2448 xfs_rmap_map_raw(
2449 struct xfs_btree_cur *cur,
2450 struct xfs_rmap_irec *rmap)
2451 {
2452 struct xfs_owner_info oinfo;
2453
2454 xfs_owner_info_pack(&oinfo, rmap->rm_owner, rmap->rm_offset,
2455 rmap->rm_flags);
2456
2457 if ((rmap->rm_flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK |
2458 XFS_RMAP_UNWRITTEN)) ||
2459 XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner))
2460 return xfs_rmap_map(cur, rmap->rm_startblock,
2461 rmap->rm_blockcount,
2462 rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2463 &oinfo);
2464
2465 return xfs_rmap_map_shared(cur, rmap->rm_startblock,
2466 rmap->rm_blockcount,
2467 rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2468 &oinfo);
2469 }
2470
2471 struct xfs_rmap_query_range_info {
2472 xfs_rmap_query_range_fn fn;
2473 void *priv;
2474 };
2475
2476 /* Format btree record and pass to our callback. */
2477 STATIC int
2478 xfs_rmap_query_range_helper(
2479 struct xfs_btree_cur *cur,
2480 const union xfs_btree_rec *rec,
2481 void *priv)
2482 {
2483 struct xfs_rmap_query_range_info *query = priv;
2484 struct xfs_rmap_irec irec;
2485 xfs_failaddr_t fa;
2486
2487 fa = xfs_rmap_btrec_to_irec(rec, &irec);
2488 if (!fa)
2489 fa = xfs_rmap_check_btrec(cur, &irec);
2490 if (fa)
2491 return xfs_rmap_complain_bad_rec(cur, fa, &irec);
2492
2493 return query->fn(cur, &irec, query->priv);
2494 }
2495
2496 /* Find all rmaps between two keys. */
2497 int
2498 xfs_rmap_query_range(
2499 struct xfs_btree_cur *cur,
2500 const struct xfs_rmap_irec *low_rec,
2501 const struct xfs_rmap_irec *high_rec,
2502 xfs_rmap_query_range_fn fn,
2503 void *priv)
2504 {
2505 union xfs_btree_irec low_brec = { .r = *low_rec };
2506 union xfs_btree_irec high_brec = { .r = *high_rec };
2507 struct xfs_rmap_query_range_info query = { .priv = priv, .fn = fn };
2508
2509 return xfs_btree_query_range(cur, &low_brec, &high_brec,
2510 xfs_rmap_query_range_helper, &query);
2511 }
2512
2513 /* Find all rmaps. */
2514 int
2515 xfs_rmap_query_all(
2516 struct xfs_btree_cur *cur,
2517 xfs_rmap_query_range_fn fn,
2518 void *priv)
2519 {
2520 struct xfs_rmap_query_range_info query;
2521
2522 query.priv = priv;
2523 query.fn = fn;
2524 return xfs_btree_query_all(cur, xfs_rmap_query_range_helper, &query);
2525 }
2526
2527 /* Commit an rmap operation into the ondisk tree. */
2528 int
2529 __xfs_rmap_finish_intent(
2530 struct xfs_btree_cur *rcur,
2531 enum xfs_rmap_intent_type op,
2532 xfs_agblock_t bno,
2533 xfs_extlen_t len,
2534 const struct xfs_owner_info *oinfo,
2535 bool unwritten)
2536 {
2537 switch (op) {
2538 case XFS_RMAP_ALLOC:
2539 case XFS_RMAP_MAP:
2540 return xfs_rmap_map(rcur, bno, len, unwritten, oinfo);
2541 case XFS_RMAP_MAP_SHARED:
2542 return xfs_rmap_map_shared(rcur, bno, len, unwritten, oinfo);
2543 case XFS_RMAP_FREE:
2544 case XFS_RMAP_UNMAP:
2545 return xfs_rmap_unmap(rcur, bno, len, unwritten, oinfo);
2546 case XFS_RMAP_UNMAP_SHARED:
2547 return xfs_rmap_unmap_shared(rcur, bno, len, unwritten, oinfo);
2548 case XFS_RMAP_CONVERT:
2549 return xfs_rmap_convert(rcur, bno, len, !unwritten, oinfo);
2550 case XFS_RMAP_CONVERT_SHARED:
2551 return xfs_rmap_convert_shared(rcur, bno, len, !unwritten,
2552 oinfo);
2553 default:
2554 ASSERT(0);
2555 return -EFSCORRUPTED;
2556 }
2557 }
2558
2559 /*
2560 * Process one of the deferred rmap operations. We pass back the
2561 * btree cursor to maintain our lock on the rmapbt between calls.
2562 * This saves time and eliminates a buffer deadlock between the
2563 * superblock and the AGF because we'll always grab them in the same
2564 * order.
2565 */
2566 int
2567 xfs_rmap_finish_one(
2568 struct xfs_trans *tp,
2569 struct xfs_rmap_intent *ri,
2570 struct xfs_btree_cur **pcur)
2571 {
2572 struct xfs_owner_info oinfo;
2573 struct xfs_mount *mp = tp->t_mountp;
2574 struct xfs_btree_cur *rcur = *pcur;
2575 struct xfs_buf *agbp = NULL;
2576 xfs_agblock_t bno;
2577 bool unwritten;
2578 int error = 0;
2579
2580 trace_xfs_rmap_deferred(mp, ri);
2581
2582 if (XFS_TEST_ERROR(false, mp, XFS_ERRTAG_RMAP_FINISH_ONE))
2583 return -EIO;
2584
2585 /*
2586 * If we haven't gotten a cursor or the cursor AG doesn't match
2587 * the startblock, get one now.
2588 */
2589 if (rcur != NULL && rcur->bc_ag.pag != ri->ri_pag) {
2590 xfs_btree_del_cursor(rcur, 0);
2591 rcur = NULL;
2592 *pcur = NULL;
2593 }
2594 if (rcur == NULL) {
2595 /*
2596 * Refresh the freelist before we start changing the
2597 * rmapbt, because a shape change could cause us to
2598 * allocate blocks.
2599 */
2600 error = xfs_free_extent_fix_freelist(tp, ri->ri_pag, &agbp);
2601 if (error) {
2602 xfs_ag_mark_sick(ri->ri_pag, XFS_SICK_AG_AGFL);
2603 return error;
2604 }
2605 if (XFS_IS_CORRUPT(tp->t_mountp, !agbp)) {
2606 xfs_ag_mark_sick(ri->ri_pag, XFS_SICK_AG_AGFL);
2607 return -EFSCORRUPTED;
2608 }
2609
2610 *pcur = rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, ri->ri_pag);
2611 }
2612
2613 xfs_rmap_ino_owner(&oinfo, ri->ri_owner, ri->ri_whichfork,
2614 ri->ri_bmap.br_startoff);
2615 unwritten = ri->ri_bmap.br_state == XFS_EXT_UNWRITTEN;
2616 bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, ri->ri_bmap.br_startblock);
2617
2618 error = __xfs_rmap_finish_intent(rcur, ri->ri_type, bno,
2619 ri->ri_bmap.br_blockcount, &oinfo, unwritten);
2620 if (error)
2621 return error;
2622
2623 xfs_rmap_update_hook(tp, ri->ri_pag, ri->ri_type, bno,
2624 ri->ri_bmap.br_blockcount, unwritten, &oinfo);
2625 return 0;
2626 }
2627
2628 /*
2629 * Don't defer an rmap if we aren't an rmap filesystem.
2630 */
2631 static bool
2632 xfs_rmap_update_is_needed(
2633 struct xfs_mount *mp,
2634 int whichfork)
2635 {
2636 return xfs_has_rmapbt(mp) && whichfork != XFS_COW_FORK;
2637 }
2638
2639 /*
2640 * Record a rmap intent; the list is kept sorted first by AG and then by
2641 * increasing age.
2642 */
2643 static void
2644 __xfs_rmap_add(
2645 struct xfs_trans *tp,
2646 enum xfs_rmap_intent_type type,
2647 uint64_t owner,
2648 int whichfork,
2649 struct xfs_bmbt_irec *bmap)
2650 {
2651 struct xfs_rmap_intent *ri;
2652
2653 ri = kmem_cache_alloc(xfs_rmap_intent_cache, GFP_KERNEL | __GFP_NOFAIL);
2654 INIT_LIST_HEAD(&ri->ri_list);
2655 ri->ri_type = type;
2656 ri->ri_owner = owner;
2657 ri->ri_whichfork = whichfork;
2658 ri->ri_bmap = *bmap;
2659
2660 xfs_rmap_defer_add(tp, ri);
2661 }
2662
2663 /* Map an extent into a file. */
2664 void
2665 xfs_rmap_map_extent(
2666 struct xfs_trans *tp,
2667 struct xfs_inode *ip,
2668 int whichfork,
2669 struct xfs_bmbt_irec *PREV)
2670 {
2671 enum xfs_rmap_intent_type type = XFS_RMAP_MAP;
2672
2673 if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2674 return;
2675
2676 if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2677 type = XFS_RMAP_MAP_SHARED;
2678
2679 __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2680 }
2681
2682 /* Unmap an extent out of a file. */
2683 void
2684 xfs_rmap_unmap_extent(
2685 struct xfs_trans *tp,
2686 struct xfs_inode *ip,
2687 int whichfork,
2688 struct xfs_bmbt_irec *PREV)
2689 {
2690 enum xfs_rmap_intent_type type = XFS_RMAP_UNMAP;
2691
2692 if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2693 return;
2694
2695 if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2696 type = XFS_RMAP_UNMAP_SHARED;
2697
2698 __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2699 }
2700
2701 /*
2702 * Convert a data fork extent from unwritten to real or vice versa.
2703 *
2704 * Note that tp can be NULL here as no transaction is used for COW fork
2705 * unwritten conversion.
2706 */
2707 void
2708 xfs_rmap_convert_extent(
2709 struct xfs_mount *mp,
2710 struct xfs_trans *tp,
2711 struct xfs_inode *ip,
2712 int whichfork,
2713 struct xfs_bmbt_irec *PREV)
2714 {
2715 enum xfs_rmap_intent_type type = XFS_RMAP_CONVERT;
2716
2717 if (!xfs_rmap_update_is_needed(mp, whichfork))
2718 return;
2719
2720 if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2721 type = XFS_RMAP_CONVERT_SHARED;
2722
2723 __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2724 }
2725
2726 /* Schedule the creation of an rmap for non-file data. */
2727 void
2728 xfs_rmap_alloc_extent(
2729 struct xfs_trans *tp,
2730 xfs_agnumber_t agno,
2731 xfs_agblock_t bno,
2732 xfs_extlen_t len,
2733 uint64_t owner)
2734 {
2735 struct xfs_bmbt_irec bmap;
2736
2737 if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2738 return;
2739
2740 bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2741 bmap.br_blockcount = len;
2742 bmap.br_startoff = 0;
2743 bmap.br_state = XFS_EXT_NORM;
2744
2745 __xfs_rmap_add(tp, XFS_RMAP_ALLOC, owner, XFS_DATA_FORK, &bmap);
2746 }
2747
2748 /* Schedule the deletion of an rmap for non-file data. */
2749 void
2750 xfs_rmap_free_extent(
2751 struct xfs_trans *tp,
2752 xfs_agnumber_t agno,
2753 xfs_agblock_t bno,
2754 xfs_extlen_t len,
2755 uint64_t owner)
2756 {
2757 struct xfs_bmbt_irec bmap;
2758
2759 if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2760 return;
2761
2762 bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2763 bmap.br_blockcount = len;
2764 bmap.br_startoff = 0;
2765 bmap.br_state = XFS_EXT_NORM;
2766
2767 __xfs_rmap_add(tp, XFS_RMAP_FREE, owner, XFS_DATA_FORK, &bmap);
2768 }
2769
2770 /* Compare rmap records. Returns -1 if a < b, 1 if a > b, and 0 if equal. */
2771 int
2772 xfs_rmap_compare(
2773 const struct xfs_rmap_irec *a,
2774 const struct xfs_rmap_irec *b)
2775 {
2776 __u64 oa;
2777 __u64 ob;
2778
2779 oa = xfs_rmap_irec_offset_pack(a);
2780 ob = xfs_rmap_irec_offset_pack(b);
2781
2782 if (a->rm_startblock < b->rm_startblock)
2783 return -1;
2784 else if (a->rm_startblock > b->rm_startblock)
2785 return 1;
2786 else if (a->rm_owner < b->rm_owner)
2787 return -1;
2788 else if (a->rm_owner > b->rm_owner)
2789 return 1;
2790 else if (oa < ob)
2791 return -1;
2792 else if (oa > ob)
2793 return 1;
2794 else
2795 return 0;
2796 }
2797
2798 /*
2799 * Scan the physical storage part of the keyspace of the reverse mapping index
2800 * and tell us if the area has no records, is fully mapped by records, or is
2801 * partially filled.
2802 */
2803 int
2804 xfs_rmap_has_records(
2805 struct xfs_btree_cur *cur,
2806 xfs_agblock_t bno,
2807 xfs_extlen_t len,
2808 enum xbtree_recpacking *outcome)
2809 {
2810 union xfs_btree_key mask = {
2811 .rmap.rm_startblock = cpu_to_be32(-1U),
2812 };
2813 union xfs_btree_irec low;
2814 union xfs_btree_irec high;
2815
2816 memset(&low, 0, sizeof(low));
2817 low.r.rm_startblock = bno;
2818 memset(&high, 0xFF, sizeof(high));
2819 high.r.rm_startblock = bno + len - 1;
2820
2821 return xfs_btree_has_records(cur, &low, &high, &mask, outcome);
2822 }
2823
2824 struct xfs_rmap_ownercount {
2825 /* Owner that we're looking for. */
2826 struct xfs_rmap_irec good;
2827
2828 /* rmap search keys */
2829 struct xfs_rmap_irec low;
2830 struct xfs_rmap_irec high;
2831
2832 struct xfs_rmap_matches *results;
2833
2834 /* Stop early if we find a nonmatch? */
2835 bool stop_on_nonmatch;
2836 };
2837
2838 /* Does this rmap represent space that can have multiple owners? */
2839 static inline bool
2840 xfs_rmap_shareable(
2841 struct xfs_mount *mp,
2842 const struct xfs_rmap_irec *rmap)
2843 {
2844 if (!xfs_has_reflink(mp))
2845 return false;
2846 if (XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner))
2847 return false;
2848 if (rmap->rm_flags & (XFS_RMAP_ATTR_FORK |
2849 XFS_RMAP_BMBT_BLOCK))
2850 return false;
2851 return true;
2852 }
2853
2854 static inline void
2855 xfs_rmap_ownercount_init(
2856 struct xfs_rmap_ownercount *roc,
2857 xfs_agblock_t bno,
2858 xfs_extlen_t len,
2859 const struct xfs_owner_info *oinfo,
2860 struct xfs_rmap_matches *results)
2861 {
2862 memset(roc, 0, sizeof(*roc));
2863 roc->results = results;
2864
2865 roc->low.rm_startblock = bno;
2866 memset(&roc->high, 0xFF, sizeof(roc->high));
2867 roc->high.rm_startblock = bno + len - 1;
2868
2869 memset(results, 0, sizeof(*results));
2870 roc->good.rm_startblock = bno;
2871 roc->good.rm_blockcount = len;
2872 roc->good.rm_owner = oinfo->oi_owner;
2873 roc->good.rm_offset = oinfo->oi_offset;
2874 if (oinfo->oi_flags & XFS_OWNER_INFO_ATTR_FORK)
2875 roc->good.rm_flags |= XFS_RMAP_ATTR_FORK;
2876 if (oinfo->oi_flags & XFS_OWNER_INFO_BMBT_BLOCK)
2877 roc->good.rm_flags |= XFS_RMAP_BMBT_BLOCK;
2878 }
2879
2880 /* Figure out if this is a match for the owner. */
2881 STATIC int
2882 xfs_rmap_count_owners_helper(
2883 struct xfs_btree_cur *cur,
2884 const struct xfs_rmap_irec *rec,
2885 void *priv)
2886 {
2887 struct xfs_rmap_ownercount *roc = priv;
2888 struct xfs_rmap_irec check = *rec;
2889 unsigned int keyflags;
2890 bool filedata;
2891 int64_t delta;
2892
2893 filedata = !XFS_RMAP_NON_INODE_OWNER(check.rm_owner) &&
2894 !(check.rm_flags & XFS_RMAP_BMBT_BLOCK);
2895
2896 /* Trim the part of check that comes before the comparison range. */
2897 delta = (int64_t)roc->good.rm_startblock - check.rm_startblock;
2898 if (delta > 0) {
2899 check.rm_startblock += delta;
2900 check.rm_blockcount -= delta;
2901 if (filedata)
2902 check.rm_offset += delta;
2903 }
2904
2905 /* Trim the part of check that comes after the comparison range. */
2906 delta = (check.rm_startblock + check.rm_blockcount) -
2907 (roc->good.rm_startblock + roc->good.rm_blockcount);
2908 if (delta > 0)
2909 check.rm_blockcount -= delta;
2910
2911 /* Don't care about unwritten status for establishing ownership. */
2912 keyflags = check.rm_flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK);
2913
2914 if (check.rm_startblock == roc->good.rm_startblock &&
2915 check.rm_blockcount == roc->good.rm_blockcount &&
2916 check.rm_owner == roc->good.rm_owner &&
2917 check.rm_offset == roc->good.rm_offset &&
2918 keyflags == roc->good.rm_flags) {
2919 roc->results->matches++;
2920 } else {
2921 roc->results->non_owner_matches++;
2922 if (xfs_rmap_shareable(cur->bc_mp, &roc->good) ^
2923 xfs_rmap_shareable(cur->bc_mp, &check))
2924 roc->results->bad_non_owner_matches++;
2925 }
2926
2927 if (roc->results->non_owner_matches && roc->stop_on_nonmatch)
2928 return -ECANCELED;
2929
2930 return 0;
2931 }
2932
2933 /* Count the number of owners and non-owners of this range of blocks. */
2934 int
2935 xfs_rmap_count_owners(
2936 struct xfs_btree_cur *cur,
2937 xfs_agblock_t bno,
2938 xfs_extlen_t len,
2939 const struct xfs_owner_info *oinfo,
2940 struct xfs_rmap_matches *results)
2941 {
2942 struct xfs_rmap_ownercount roc;
2943 int error;
2944
2945 xfs_rmap_ownercount_init(&roc, bno, len, oinfo, results);
2946 error = xfs_rmap_query_range(cur, &roc.low, &roc.high,
2947 xfs_rmap_count_owners_helper, &roc);
2948 if (error)
2949 return error;
2950
2951 /*
2952 * There can't be any non-owner rmaps that conflict with the given
2953 * owner if we didn't find any rmaps matching the owner.
2954 */
2955 if (!results->matches)
2956 results->bad_non_owner_matches = 0;
2957
2958 return 0;
2959 }
2960
2961 /*
2962 * Given an extent and some owner info, can we find records overlapping
2963 * the extent whose owner info does not match the given owner?
2964 */
2965 int
2966 xfs_rmap_has_other_keys(
2967 struct xfs_btree_cur *cur,
2968 xfs_agblock_t bno,
2969 xfs_extlen_t len,
2970 const struct xfs_owner_info *oinfo,
2971 bool *has_other)
2972 {
2973 struct xfs_rmap_matches res;
2974 struct xfs_rmap_ownercount roc;
2975 int error;
2976
2977 xfs_rmap_ownercount_init(&roc, bno, len, oinfo, &res);
2978 roc.stop_on_nonmatch = true;
2979
2980 error = xfs_rmap_query_range(cur, &roc.low, &roc.high,
2981 xfs_rmap_count_owners_helper, &roc);
2982 if (error == -ECANCELED) {
2983 *has_other = true;
2984 return 0;
2985 }
2986 if (error)
2987 return error;
2988
2989 *has_other = false;
2990 return 0;
2991 }
2992
2993 const struct xfs_owner_info XFS_RMAP_OINFO_SKIP_UPDATE = {
2994 .oi_owner = XFS_RMAP_OWN_NULL,
2995 };
2996 const struct xfs_owner_info XFS_RMAP_OINFO_ANY_OWNER = {
2997 .oi_owner = XFS_RMAP_OWN_UNKNOWN,
2998 };
2999 const struct xfs_owner_info XFS_RMAP_OINFO_FS = {
3000 .oi_owner = XFS_RMAP_OWN_FS,
3001 };
3002 const struct xfs_owner_info XFS_RMAP_OINFO_LOG = {
3003 .oi_owner = XFS_RMAP_OWN_LOG,
3004 };
3005 const struct xfs_owner_info XFS_RMAP_OINFO_AG = {
3006 .oi_owner = XFS_RMAP_OWN_AG,
3007 };
3008 const struct xfs_owner_info XFS_RMAP_OINFO_INOBT = {
3009 .oi_owner = XFS_RMAP_OWN_INOBT,
3010 };
3011 const struct xfs_owner_info XFS_RMAP_OINFO_INODES = {
3012 .oi_owner = XFS_RMAP_OWN_INODES,
3013 };
3014 const struct xfs_owner_info XFS_RMAP_OINFO_REFC = {
3015 .oi_owner = XFS_RMAP_OWN_REFC,
3016 };
3017 const struct xfs_owner_info XFS_RMAP_OINFO_COW = {
3018 .oi_owner = XFS_RMAP_OWN_COW,
3019 };
3020
3021 int __init
3022 xfs_rmap_intent_init_cache(void)
3023 {
3024 xfs_rmap_intent_cache = kmem_cache_create("xfs_rmap_intent",
3025 sizeof(struct xfs_rmap_intent),
3026 0, 0, NULL);
3027
3028 return xfs_rmap_intent_cache != NULL ? 0 : -ENOMEM;
3029 }
3030
3031 void
3032 xfs_rmap_intent_destroy_cache(void)
3033 {
3034 kmem_cache_destroy(xfs_rmap_intent_cache);
3035 xfs_rmap_intent_cache = NULL;
3036 }
3037
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.