]> git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - fs/xfs/libxfs/xfs_rmap.c
projects / mirror_ubuntu-artful-kernel.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xfs: create a function to query all records in a btree
[mirror_ubuntu-artful-kernel.git] / fs / xfs / libxfs / xfs_rmap.c
1 /*
2 * Copyright (c) 2014 Red Hat, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_shared.h"
21 #include "xfs_format.h"
22 #include "xfs_log_format.h"
23 #include "xfs_trans_resv.h"
24 #include "xfs_bit.h"
25 #include "xfs_sb.h"
26 #include "xfs_mount.h"
27 #include "xfs_defer.h"
28 #include "xfs_da_format.h"
29 #include "xfs_da_btree.h"
30 #include "xfs_btree.h"
31 #include "xfs_trans.h"
32 #include "xfs_alloc.h"
33 #include "xfs_rmap.h"
34 #include "xfs_rmap_btree.h"
35 #include "xfs_trans_space.h"
36 #include "xfs_trace.h"
37 #include "xfs_error.h"
38 #include "xfs_extent_busy.h"
39 #include "xfs_bmap.h"
40 #include "xfs_inode.h"
41
42 /*
43 * Lookup the first record less than or equal to [bno, len, owner, offset]
44 * in the btree given by cur.
45 */
46 int
47 xfs_rmap_lookup_le(
48 struct xfs_btree_cur *cur,
49 xfs_agblock_t bno,
50 xfs_extlen_t len,
51 uint64_t owner,
52 uint64_t offset,
53 unsigned int flags,
54 int *stat)
55 {
56 cur->bc_rec.r.rm_startblock = bno;
57 cur->bc_rec.r.rm_blockcount = len;
58 cur->bc_rec.r.rm_owner = owner;
59 cur->bc_rec.r.rm_offset = offset;
60 cur->bc_rec.r.rm_flags = flags;
61 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
62 }
63
64 /*
65 * Lookup the record exactly matching [bno, len, owner, offset]
66 * in the btree given by cur.
67 */
68 int
69 xfs_rmap_lookup_eq(
70 struct xfs_btree_cur *cur,
71 xfs_agblock_t bno,
72 xfs_extlen_t len,
73 uint64_t owner,
74 uint64_t offset,
75 unsigned int flags,
76 int *stat)
77 {
78 cur->bc_rec.r.rm_startblock = bno;
79 cur->bc_rec.r.rm_blockcount = len;
80 cur->bc_rec.r.rm_owner = owner;
81 cur->bc_rec.r.rm_offset = offset;
82 cur->bc_rec.r.rm_flags = flags;
83 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
84 }
85
86 /*
87 * Update the record referred to by cur to the value given
88 * by [bno, len, owner, offset].
89 * This either works (return 0) or gets an EFSCORRUPTED error.
90 */
91 STATIC int
92 xfs_rmap_update(
93 struct xfs_btree_cur *cur,
94 struct xfs_rmap_irec *irec)
95 {
96 union xfs_btree_rec rec;
97 int error;
98
99 trace_xfs_rmap_update(cur->bc_mp, cur->bc_private.a.agno,
100 irec->rm_startblock, irec->rm_blockcount,
101 irec->rm_owner, irec->rm_offset, irec->rm_flags);
102
103 rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock);
104 rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount);
105 rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner);
106 rec.rmap.rm_offset = cpu_to_be64(
107 xfs_rmap_irec_offset_pack(irec));
108 error = xfs_btree_update(cur, &rec);
109 if (error)
110 trace_xfs_rmap_update_error(cur->bc_mp,
111 cur->bc_private.a.agno, error, _RET_IP_);
112 return error;
113 }
114
115 int
116 xfs_rmap_insert(
117 struct xfs_btree_cur *rcur,
118 xfs_agblock_t agbno,
119 xfs_extlen_t len,
120 uint64_t owner,
121 uint64_t offset,
122 unsigned int flags)
123 {
124 int i;
125 int error;
126
127 trace_xfs_rmap_insert(rcur->bc_mp, rcur->bc_private.a.agno, agbno,
128 len, owner, offset, flags);
129
130 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
131 if (error)
132 goto done;
133 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 0, done);
134
135 rcur->bc_rec.r.rm_startblock = agbno;
136 rcur->bc_rec.r.rm_blockcount = len;
137 rcur->bc_rec.r.rm_owner = owner;
138 rcur->bc_rec.r.rm_offset = offset;
139 rcur->bc_rec.r.rm_flags = flags;
140 error = xfs_btree_insert(rcur, &i);
141 if (error)
142 goto done;
143 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 1, done);
144 done:
145 if (error)
146 trace_xfs_rmap_insert_error(rcur->bc_mp,
147 rcur->bc_private.a.agno, error, _RET_IP_);
148 return error;
149 }
150
151 STATIC int
152 xfs_rmap_delete(
153 struct xfs_btree_cur *rcur,
154 xfs_agblock_t agbno,
155 xfs_extlen_t len,
156 uint64_t owner,
157 uint64_t offset,
158 unsigned int flags)
159 {
160 int i;
161 int error;
162
163 trace_xfs_rmap_delete(rcur->bc_mp, rcur->bc_private.a.agno, agbno,
164 len, owner, offset, flags);
165
166 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
167 if (error)
168 goto done;
169 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 1, done);
170
171 error = xfs_btree_delete(rcur, &i);
172 if (error)
173 goto done;
174 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 1, done);
175 done:
176 if (error)
177 trace_xfs_rmap_delete_error(rcur->bc_mp,
178 rcur->bc_private.a.agno, error, _RET_IP_);
179 return error;
180 }
181
182 static int
183 xfs_rmap_btrec_to_irec(
184 union xfs_btree_rec *rec,
185 struct xfs_rmap_irec *irec)
186 {
187 irec->rm_flags = 0;
188 irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock);
189 irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount);
190 irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner);
191 return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset),
192 irec);
193 }
194
195 /*
196 * Get the data from the pointed-to record.
197 */
198 int
199 xfs_rmap_get_rec(
200 struct xfs_btree_cur *cur,
201 struct xfs_rmap_irec *irec,
202 int *stat)
203 {
204 union xfs_btree_rec *rec;
205 int error;
206
207 error = xfs_btree_get_rec(cur, &rec, stat);
208 if (error || !*stat)
209 return error;
210
211 return xfs_rmap_btrec_to_irec(rec, irec);
212 }
213
214 struct xfs_find_left_neighbor_info {
215 struct xfs_rmap_irec high;
216 struct xfs_rmap_irec *irec;
217 int *stat;
218 };
219
220 /* For each rmap given, figure out if it matches the key we want. */
221 STATIC int
222 xfs_rmap_find_left_neighbor_helper(
223 struct xfs_btree_cur *cur,
224 struct xfs_rmap_irec *rec,
225 void *priv)
226 {
227 struct xfs_find_left_neighbor_info *info = priv;
228
229 trace_xfs_rmap_find_left_neighbor_candidate(cur->bc_mp,
230 cur->bc_private.a.agno, rec->rm_startblock,
231 rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
232 rec->rm_flags);
233
234 if (rec->rm_owner != info->high.rm_owner)
235 return XFS_BTREE_QUERY_RANGE_CONTINUE;
236 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
237 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
238 rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset)
239 return XFS_BTREE_QUERY_RANGE_CONTINUE;
240
241 *info->irec = *rec;
242 *info->stat = 1;
243 return XFS_BTREE_QUERY_RANGE_ABORT;
244 }
245
246 /*
247 * Find the record to the left of the given extent, being careful only to
248 * return a match with the same owner and adjacent physical and logical
249 * block ranges.
250 */
251 int
252 xfs_rmap_find_left_neighbor(
253 struct xfs_btree_cur *cur,
254 xfs_agblock_t bno,
255 uint64_t owner,
256 uint64_t offset,
257 unsigned int flags,
258 struct xfs_rmap_irec *irec,
259 int *stat)
260 {
261 struct xfs_find_left_neighbor_info info;
262 int error;
263
264 *stat = 0;
265 if (bno == 0)
266 return 0;
267 info.high.rm_startblock = bno - 1;
268 info.high.rm_owner = owner;
269 if (!XFS_RMAP_NON_INODE_OWNER(owner) &&
270 !(flags & XFS_RMAP_BMBT_BLOCK)) {
271 if (offset == 0)
272 return 0;
273 info.high.rm_offset = offset - 1;
274 } else
275 info.high.rm_offset = 0;
276 info.high.rm_flags = flags;
277 info.high.rm_blockcount = 0;
278 info.irec = irec;
279 info.stat = stat;
280
281 trace_xfs_rmap_find_left_neighbor_query(cur->bc_mp,
282 cur->bc_private.a.agno, bno, 0, owner, offset, flags);
283
284 error = xfs_rmap_query_range(cur, &info.high, &info.high,
285 xfs_rmap_find_left_neighbor_helper, &info);
286 if (error == XFS_BTREE_QUERY_RANGE_ABORT)
287 error = 0;
288 if (*stat)
289 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
290 cur->bc_private.a.agno, irec->rm_startblock,
291 irec->rm_blockcount, irec->rm_owner,
292 irec->rm_offset, irec->rm_flags);
293 return error;
294 }
295
296 /* For each rmap given, figure out if it matches the key we want. */
297 STATIC int
298 xfs_rmap_lookup_le_range_helper(
299 struct xfs_btree_cur *cur,
300 struct xfs_rmap_irec *rec,
301 void *priv)
302 {
303 struct xfs_find_left_neighbor_info *info = priv;
304
305 trace_xfs_rmap_lookup_le_range_candidate(cur->bc_mp,
306 cur->bc_private.a.agno, rec->rm_startblock,
307 rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
308 rec->rm_flags);
309
310 if (rec->rm_owner != info->high.rm_owner)
311 return XFS_BTREE_QUERY_RANGE_CONTINUE;
312 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
313 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
314 (rec->rm_offset > info->high.rm_offset ||
315 rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset))
316 return XFS_BTREE_QUERY_RANGE_CONTINUE;
317
318 *info->irec = *rec;
319 *info->stat = 1;
320 return XFS_BTREE_QUERY_RANGE_ABORT;
321 }
322
323 /*
324 * Find the record to the left of the given extent, being careful only to
325 * return a match with the same owner and overlapping physical and logical
326 * block ranges. This is the overlapping-interval version of
327 * xfs_rmap_lookup_le.
328 */
329 int
330 xfs_rmap_lookup_le_range(
331 struct xfs_btree_cur *cur,
332 xfs_agblock_t bno,
333 uint64_t owner,
334 uint64_t offset,
335 unsigned int flags,
336 struct xfs_rmap_irec *irec,
337 int *stat)
338 {
339 struct xfs_find_left_neighbor_info info;
340 int error;
341
342 info.high.rm_startblock = bno;
343 info.high.rm_owner = owner;
344 if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK))
345 info.high.rm_offset = offset;
346 else
347 info.high.rm_offset = 0;
348 info.high.rm_flags = flags;
349 info.high.rm_blockcount = 0;
350 *stat = 0;
351 info.irec = irec;
352 info.stat = stat;
353
354 trace_xfs_rmap_lookup_le_range(cur->bc_mp,
355 cur->bc_private.a.agno, bno, 0, owner, offset, flags);
356 error = xfs_rmap_query_range(cur, &info.high, &info.high,
357 xfs_rmap_lookup_le_range_helper, &info);
358 if (error == XFS_BTREE_QUERY_RANGE_ABORT)
359 error = 0;
360 if (*stat)
361 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
362 cur->bc_private.a.agno, irec->rm_startblock,
363 irec->rm_blockcount, irec->rm_owner,
364 irec->rm_offset, irec->rm_flags);
365 return error;
366 }
367
368 /*
369 * Find the extent in the rmap btree and remove it.
370 *
371 * The record we find should always be an exact match for the extent that we're
372 * looking for, since we insert them into the btree without modification.
373 *
374 * Special Case #1: when growing the filesystem, we "free" an extent when
375 * growing the last AG. This extent is new space and so it is not tracked as
376 * used space in the btree. The growfs code will pass in an owner of
377 * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
378 * extent. We verify that - the extent lookup result in a record that does not
379 * overlap.
380 *
381 * Special Case #2: EFIs do not record the owner of the extent, so when
382 * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
383 * btree to ignore the owner (i.e. wildcard match) so we don't trigger
384 * corruption checks during log recovery.
385 */
386 STATIC int
387 xfs_rmap_unmap(
388 struct xfs_btree_cur *cur,
389 xfs_agblock_t bno,
390 xfs_extlen_t len,
391 bool unwritten,
392 struct xfs_owner_info *oinfo)
393 {
394 struct xfs_mount *mp = cur->bc_mp;
395 struct xfs_rmap_irec ltrec;
396 uint64_t ltoff;
397 int error = 0;
398 int i;
399 uint64_t owner;
400 uint64_t offset;
401 unsigned int flags;
402 bool ignore_off;
403
404 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
405 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
406 (flags & XFS_RMAP_BMBT_BLOCK);
407 if (unwritten)
408 flags |= XFS_RMAP_UNWRITTEN;
409 trace_xfs_rmap_unmap(mp, cur->bc_private.a.agno, bno, len,
410 unwritten, oinfo);
411
412 /*
413 * We should always have a left record because there's a static record
414 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
415 * will not ever be removed from the tree.
416 */
417 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags, &i);
418 if (error)
419 goto out_error;
420 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
421
422 error = xfs_rmap_get_rec(cur, &ltrec, &i);
423 if (error)
424 goto out_error;
425 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
426 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
427 cur->bc_private.a.agno, ltrec.rm_startblock,
428 ltrec.rm_blockcount, ltrec.rm_owner,
429 ltrec.rm_offset, ltrec.rm_flags);
430 ltoff = ltrec.rm_offset;
431
432 /*
433 * For growfs, the incoming extent must be beyond the left record we
434 * just found as it is new space and won't be used by anyone. This is
435 * just a corruption check as we don't actually do anything with this
436 * extent. Note that we need to use >= instead of > because it might
437 * be the case that the "left" extent goes all the way to EOFS.
438 */
439 if (owner == XFS_RMAP_OWN_NULL) {
440 XFS_WANT_CORRUPTED_GOTO(mp, bno >= ltrec.rm_startblock +
441 ltrec.rm_blockcount, out_error);
442 goto out_done;
443 }
444
445 /* Make sure the unwritten flag matches. */
446 XFS_WANT_CORRUPTED_GOTO(mp, (flags & XFS_RMAP_UNWRITTEN) ==
447 (ltrec.rm_flags & XFS_RMAP_UNWRITTEN), out_error);
448
449 /* Make sure the extent we found covers the entire freeing range. */
450 XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_startblock <= bno &&
451 ltrec.rm_startblock + ltrec.rm_blockcount >=
452 bno + len, out_error);
453
454 /* Make sure the owner matches what we expect to find in the tree. */
455 XFS_WANT_CORRUPTED_GOTO(mp, owner == ltrec.rm_owner ||
456 XFS_RMAP_NON_INODE_OWNER(owner), out_error);
457
458 /* Check the offset, if necessary. */
459 if (!XFS_RMAP_NON_INODE_OWNER(owner)) {
460 if (flags & XFS_RMAP_BMBT_BLOCK) {
461 XFS_WANT_CORRUPTED_GOTO(mp,
462 ltrec.rm_flags & XFS_RMAP_BMBT_BLOCK,
463 out_error);
464 } else {
465 XFS_WANT_CORRUPTED_GOTO(mp,
466 ltrec.rm_offset <= offset, out_error);
467 XFS_WANT_CORRUPTED_GOTO(mp,
468 ltoff + ltrec.rm_blockcount >= offset + len,
469 out_error);
470 }
471 }
472
473 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
474 /* exact match, simply remove the record from rmap tree */
475 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
476 ltrec.rm_startblock, ltrec.rm_blockcount,
477 ltrec.rm_owner, ltrec.rm_offset,
478 ltrec.rm_flags);
479 error = xfs_btree_delete(cur, &i);
480 if (error)
481 goto out_error;
482 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
483 } else if (ltrec.rm_startblock == bno) {
484 /*
485 * overlap left hand side of extent: move the start, trim the
486 * length and update the current record.
487 *
488 * ltbno ltlen
489 * Orig: |oooooooooooooooooooo|
490 * Freeing: |fffffffff|
491 * Result: |rrrrrrrrrr|
492 * bno len
493 */
494 ltrec.rm_startblock += len;
495 ltrec.rm_blockcount -= len;
496 if (!ignore_off)
497 ltrec.rm_offset += len;
498 error = xfs_rmap_update(cur, &ltrec);
499 if (error)
500 goto out_error;
501 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
502 /*
503 * overlap right hand side of extent: trim the length and update
504 * the current record.
505 *
506 * ltbno ltlen
507 * Orig: |oooooooooooooooooooo|
508 * Freeing: |fffffffff|
509 * Result: |rrrrrrrrrr|
510 * bno len
511 */
512 ltrec.rm_blockcount -= len;
513 error = xfs_rmap_update(cur, &ltrec);
514 if (error)
515 goto out_error;
516 } else {
517
518 /*
519 * overlap middle of extent: trim the length of the existing
520 * record to the length of the new left-extent size, increment
521 * the insertion position so we can insert a new record
522 * containing the remaining right-extent space.
523 *
524 * ltbno ltlen
525 * Orig: |oooooooooooooooooooo|
526 * Freeing: |fffffffff|
527 * Result: |rrrrr| |rrrr|
528 * bno len
529 */
530 xfs_extlen_t orig_len = ltrec.rm_blockcount;
531
532 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
533 error = xfs_rmap_update(cur, &ltrec);
534 if (error)
535 goto out_error;
536
537 error = xfs_btree_increment(cur, 0, &i);
538 if (error)
539 goto out_error;
540
541 cur->bc_rec.r.rm_startblock = bno + len;
542 cur->bc_rec.r.rm_blockcount = orig_len - len -
543 ltrec.rm_blockcount;
544 cur->bc_rec.r.rm_owner = ltrec.rm_owner;
545 if (ignore_off)
546 cur->bc_rec.r.rm_offset = 0;
547 else
548 cur->bc_rec.r.rm_offset = offset + len;
549 cur->bc_rec.r.rm_flags = flags;
550 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno,
551 cur->bc_rec.r.rm_startblock,
552 cur->bc_rec.r.rm_blockcount,
553 cur->bc_rec.r.rm_owner,
554 cur->bc_rec.r.rm_offset,
555 cur->bc_rec.r.rm_flags);
556 error = xfs_btree_insert(cur, &i);
557 if (error)
558 goto out_error;
559 }
560
561 out_done:
562 trace_xfs_rmap_unmap_done(mp, cur->bc_private.a.agno, bno, len,
563 unwritten, oinfo);
564 out_error:
565 if (error)
566 trace_xfs_rmap_unmap_error(mp, cur->bc_private.a.agno,
567 error, _RET_IP_);
568 return error;
569 }
570
571 /*
572 * Remove a reference to an extent in the rmap btree.
573 */
574 int
575 xfs_rmap_free(
576 struct xfs_trans *tp,
577 struct xfs_buf *agbp,
578 xfs_agnumber_t agno,
579 xfs_agblock_t bno,
580 xfs_extlen_t len,
581 struct xfs_owner_info *oinfo)
582 {
583 struct xfs_mount *mp = tp->t_mountp;
584 struct xfs_btree_cur *cur;
585 int error;
586
587 if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
588 return 0;
589
590 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno);
591
592 error = xfs_rmap_unmap(cur, bno, len, false, oinfo);
593 if (error)
594 goto out_error;
595
596 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
597 return 0;
598
599 out_error:
600 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
601 return error;
602 }
603
604 /*
605 * A mergeable rmap must have the same owner and the same values for
606 * the unwritten, attr_fork, and bmbt flags. The startblock and
607 * offset are checked separately.
608 */
609 static bool
610 xfs_rmap_is_mergeable(
611 struct xfs_rmap_irec *irec,
612 uint64_t owner,
613 unsigned int flags)
614 {
615 if (irec->rm_owner == XFS_RMAP_OWN_NULL)
616 return false;
617 if (irec->rm_owner != owner)
618 return false;
619 if ((flags & XFS_RMAP_UNWRITTEN) ^
620 (irec->rm_flags & XFS_RMAP_UNWRITTEN))
621 return false;
622 if ((flags & XFS_RMAP_ATTR_FORK) ^
623 (irec->rm_flags & XFS_RMAP_ATTR_FORK))
624 return false;
625 if ((flags & XFS_RMAP_BMBT_BLOCK) ^
626 (irec->rm_flags & XFS_RMAP_BMBT_BLOCK))
627 return false;
628 return true;
629 }
630
631 /*
632 * When we allocate a new block, the first thing we do is add a reference to
633 * the extent in the rmap btree. This takes the form of a [agbno, length,
634 * owner, offset] record. Flags are encoded in the high bits of the offset
635 * field.
636 */
637 STATIC int
638 xfs_rmap_map(
639 struct xfs_btree_cur *cur,
640 xfs_agblock_t bno,
641 xfs_extlen_t len,
642 bool unwritten,
643 struct xfs_owner_info *oinfo)
644 {
645 struct xfs_mount *mp = cur->bc_mp;
646 struct xfs_rmap_irec ltrec;
647 struct xfs_rmap_irec gtrec;
648 int have_gt;
649 int have_lt;
650 int error = 0;
651 int i;
652 uint64_t owner;
653 uint64_t offset;
654 unsigned int flags = 0;
655 bool ignore_off;
656
657 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
658 ASSERT(owner != 0);
659 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
660 (flags & XFS_RMAP_BMBT_BLOCK);
661 if (unwritten)
662 flags |= XFS_RMAP_UNWRITTEN;
663 trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len,
664 unwritten, oinfo);
665
666 /*
667 * For the initial lookup, look for an exact match or the left-adjacent
668 * record for our insertion point. This will also give us the record for
669 * start block contiguity tests.
670 */
671 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags,
672 &have_lt);
673 if (error)
674 goto out_error;
675 XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error);
676
677 error = xfs_rmap_get_rec(cur, &ltrec, &have_lt);
678 if (error)
679 goto out_error;
680 XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error);
681 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
682 cur->bc_private.a.agno, ltrec.rm_startblock,
683 ltrec.rm_blockcount, ltrec.rm_owner,
684 ltrec.rm_offset, ltrec.rm_flags);
685
686 if (!xfs_rmap_is_mergeable(&ltrec, owner, flags))
687 have_lt = 0;
688
689 XFS_WANT_CORRUPTED_GOTO(mp,
690 have_lt == 0 ||
691 ltrec.rm_startblock + ltrec.rm_blockcount <= bno, out_error);
692
693 /*
694 * Increment the cursor to see if we have a right-adjacent record to our
695 * insertion point. This will give us the record for end block
696 * contiguity tests.
697 */
698 error = xfs_btree_increment(cur, 0, &have_gt);
699 if (error)
700 goto out_error;
701 if (have_gt) {
702 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
703 if (error)
704 goto out_error;
705 XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error);
706 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= gtrec.rm_startblock,
707 out_error);
708 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
709 cur->bc_private.a.agno, gtrec.rm_startblock,
710 gtrec.rm_blockcount, gtrec.rm_owner,
711 gtrec.rm_offset, gtrec.rm_flags);
712 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
713 have_gt = 0;
714 }
715
716 /*
717 * Note: cursor currently points one record to the right of ltrec, even
718 * if there is no record in the tree to the right.
719 */
720 if (have_lt &&
721 ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
722 (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) {
723 /*
724 * left edge contiguous, merge into left record.
725 *
726 * ltbno ltlen
727 * orig: |ooooooooo|
728 * adding: |aaaaaaaaa|
729 * result: |rrrrrrrrrrrrrrrrrrr|
730 * bno len
731 */
732 ltrec.rm_blockcount += len;
733 if (have_gt &&
734 bno + len == gtrec.rm_startblock &&
735 (ignore_off || offset + len == gtrec.rm_offset) &&
736 (unsigned long)ltrec.rm_blockcount + len +
737 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) {
738 /*
739 * right edge also contiguous, delete right record
740 * and merge into left record.
741 *
742 * ltbno ltlen gtbno gtlen
743 * orig: |ooooooooo| |ooooooooo|
744 * adding: |aaaaaaaaa|
745 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
746 */
747 ltrec.rm_blockcount += gtrec.rm_blockcount;
748 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
749 gtrec.rm_startblock,
750 gtrec.rm_blockcount,
751 gtrec.rm_owner,
752 gtrec.rm_offset,
753 gtrec.rm_flags);
754 error = xfs_btree_delete(cur, &i);
755 if (error)
756 goto out_error;
757 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
758 }
759
760 /* point the cursor back to the left record and update */
761 error = xfs_btree_decrement(cur, 0, &have_gt);
762 if (error)
763 goto out_error;
764 error = xfs_rmap_update(cur, &ltrec);
765 if (error)
766 goto out_error;
767 } else if (have_gt &&
768 bno + len == gtrec.rm_startblock &&
769 (ignore_off || offset + len == gtrec.rm_offset)) {
770 /*
771 * right edge contiguous, merge into right record.
772 *
773 * gtbno gtlen
774 * Orig: |ooooooooo|
775 * adding: |aaaaaaaaa|
776 * Result: |rrrrrrrrrrrrrrrrrrr|
777 * bno len
778 */
779 gtrec.rm_startblock = bno;
780 gtrec.rm_blockcount += len;
781 if (!ignore_off)
782 gtrec.rm_offset = offset;
783 error = xfs_rmap_update(cur, &gtrec);
784 if (error)
785 goto out_error;
786 } else {
787 /*
788 * no contiguous edge with identical owner, insert
789 * new record at current cursor position.
790 */
791 cur->bc_rec.r.rm_startblock = bno;
792 cur->bc_rec.r.rm_blockcount = len;
793 cur->bc_rec.r.rm_owner = owner;
794 cur->bc_rec.r.rm_offset = offset;
795 cur->bc_rec.r.rm_flags = flags;
796 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len,
797 owner, offset, flags);
798 error = xfs_btree_insert(cur, &i);
799 if (error)
800 goto out_error;
801 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
802 }
803
804 trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len,
805 unwritten, oinfo);
806 out_error:
807 if (error)
808 trace_xfs_rmap_map_error(mp, cur->bc_private.a.agno,
809 error, _RET_IP_);
810 return error;
811 }
812
813 /*
814 * Add a reference to an extent in the rmap btree.
815 */
816 int
817 xfs_rmap_alloc(
818 struct xfs_trans *tp,
819 struct xfs_buf *agbp,
820 xfs_agnumber_t agno,
821 xfs_agblock_t bno,
822 xfs_extlen_t len,
823 struct xfs_owner_info *oinfo)
824 {
825 struct xfs_mount *mp = tp->t_mountp;
826 struct xfs_btree_cur *cur;
827 int error;
828
829 if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
830 return 0;
831
832 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno);
833 error = xfs_rmap_map(cur, bno, len, false, oinfo);
834 if (error)
835 goto out_error;
836
837 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
838 return 0;
839
840 out_error:
841 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
842 return error;
843 }
844
845 #define RMAP_LEFT_CONTIG (1 << 0)
846 #define RMAP_RIGHT_CONTIG (1 << 1)
847 #define RMAP_LEFT_FILLING (1 << 2)
848 #define RMAP_RIGHT_FILLING (1 << 3)
849 #define RMAP_LEFT_VALID (1 << 6)
850 #define RMAP_RIGHT_VALID (1 << 7)
851
852 #define LEFT r[0]
853 #define RIGHT r[1]
854 #define PREV r[2]
855 #define NEW r[3]
856
857 /*
858 * Convert an unwritten extent to a real extent or vice versa.
859 * Does not handle overlapping extents.
860 */
861 STATIC int
862 xfs_rmap_convert(
863 struct xfs_btree_cur *cur,
864 xfs_agblock_t bno,
865 xfs_extlen_t len,
866 bool unwritten,
867 struct xfs_owner_info *oinfo)
868 {
869 struct xfs_mount *mp = cur->bc_mp;
870 struct xfs_rmap_irec r[4]; /* neighbor extent entries */
871 /* left is 0, right is 1, prev is 2 */
872 /* new is 3 */
873 uint64_t owner;
874 uint64_t offset;
875 uint64_t new_endoff;
876 unsigned int oldext;
877 unsigned int newext;
878 unsigned int flags = 0;
879 int i;
880 int state = 0;
881 int error;
882
883 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
884 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
885 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
886 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
887 new_endoff = offset + len;
888 trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len,
889 unwritten, oinfo);
890
891 /*
892 * For the initial lookup, look for an exact match or the left-adjacent
893 * record for our insertion point. This will also give us the record for
894 * start block contiguity tests.
895 */
896 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i);
897 if (error)
898 goto done;
899 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
900
901 error = xfs_rmap_get_rec(cur, &PREV, &i);
902 if (error)
903 goto done;
904 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
905 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
906 cur->bc_private.a.agno, PREV.rm_startblock,
907 PREV.rm_blockcount, PREV.rm_owner,
908 PREV.rm_offset, PREV.rm_flags);
909
910 ASSERT(PREV.rm_offset <= offset);
911 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
912 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
913 newext = ~oldext & XFS_RMAP_UNWRITTEN;
914
915 /*
916 * Set flags determining what part of the previous oldext allocation
917 * extent is being replaced by a newext allocation.
918 */
919 if (PREV.rm_offset == offset)
920 state |= RMAP_LEFT_FILLING;
921 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
922 state |= RMAP_RIGHT_FILLING;
923
924 /*
925 * Decrement the cursor to see if we have a left-adjacent record to our
926 * insertion point. This will give us the record for end block
927 * contiguity tests.
928 */
929 error = xfs_btree_decrement(cur, 0, &i);
930 if (error)
931 goto done;
932 if (i) {
933 state |= RMAP_LEFT_VALID;
934 error = xfs_rmap_get_rec(cur, &LEFT, &i);
935 if (error)
936 goto done;
937 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
938 XFS_WANT_CORRUPTED_GOTO(mp,
939 LEFT.rm_startblock + LEFT.rm_blockcount <= bno,
940 done);
941 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
942 cur->bc_private.a.agno, LEFT.rm_startblock,
943 LEFT.rm_blockcount, LEFT.rm_owner,
944 LEFT.rm_offset, LEFT.rm_flags);
945 if (LEFT.rm_startblock + LEFT.rm_blockcount == bno &&
946 LEFT.rm_offset + LEFT.rm_blockcount == offset &&
947 xfs_rmap_is_mergeable(&LEFT, owner, newext))
948 state |= RMAP_LEFT_CONTIG;
949 }
950
951 /*
952 * Increment the cursor to see if we have a right-adjacent record to our
953 * insertion point. This will give us the record for end block
954 * contiguity tests.
955 */
956 error = xfs_btree_increment(cur, 0, &i);
957 if (error)
958 goto done;
959 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
960 error = xfs_btree_increment(cur, 0, &i);
961 if (error)
962 goto done;
963 if (i) {
964 state |= RMAP_RIGHT_VALID;
965 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
966 if (error)
967 goto done;
968 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
969 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock,
970 done);
971 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
972 cur->bc_private.a.agno, RIGHT.rm_startblock,
973 RIGHT.rm_blockcount, RIGHT.rm_owner,
974 RIGHT.rm_offset, RIGHT.rm_flags);
975 if (bno + len == RIGHT.rm_startblock &&
976 offset + len == RIGHT.rm_offset &&
977 xfs_rmap_is_mergeable(&RIGHT, owner, newext))
978 state |= RMAP_RIGHT_CONTIG;
979 }
980
981 /* check that left + prev + right is not too long */
982 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
983 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
984 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
985 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
986 (unsigned long)LEFT.rm_blockcount + len +
987 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
988 state &= ~RMAP_RIGHT_CONTIG;
989
990 trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state,
991 _RET_IP_);
992
993 /* reset the cursor back to PREV */
994 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i);
995 if (error)
996 goto done;
997 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
998
999 /*
1000 * Switch out based on the FILLING and CONTIG state bits.
1001 */
1002 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1003 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1004 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1005 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1006 /*
1007 * Setting all of a previous oldext extent to newext.
1008 * The left and right neighbors are both contiguous with new.
1009 */
1010 error = xfs_btree_increment(cur, 0, &i);
1011 if (error)
1012 goto done;
1013 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1014 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1015 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1016 RIGHT.rm_owner, RIGHT.rm_offset,
1017 RIGHT.rm_flags);
1018 error = xfs_btree_delete(cur, &i);
1019 if (error)
1020 goto done;
1021 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1022 error = xfs_btree_decrement(cur, 0, &i);
1023 if (error)
1024 goto done;
1025 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1026 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1027 PREV.rm_startblock, PREV.rm_blockcount,
1028 PREV.rm_owner, PREV.rm_offset,
1029 PREV.rm_flags);
1030 error = xfs_btree_delete(cur, &i);
1031 if (error)
1032 goto done;
1033 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1034 error = xfs_btree_decrement(cur, 0, &i);
1035 if (error)
1036 goto done;
1037 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1038 NEW = LEFT;
1039 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1040 error = xfs_rmap_update(cur, &NEW);
1041 if (error)
1042 goto done;
1043 break;
1044
1045 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1046 /*
1047 * Setting all of a previous oldext extent to newext.
1048 * The left neighbor is contiguous, the right is not.
1049 */
1050 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1051 PREV.rm_startblock, PREV.rm_blockcount,
1052 PREV.rm_owner, PREV.rm_offset,
1053 PREV.rm_flags);
1054 error = xfs_btree_delete(cur, &i);
1055 if (error)
1056 goto done;
1057 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1058 error = xfs_btree_decrement(cur, 0, &i);
1059 if (error)
1060 goto done;
1061 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1062 NEW = LEFT;
1063 NEW.rm_blockcount += PREV.rm_blockcount;
1064 error = xfs_rmap_update(cur, &NEW);
1065 if (error)
1066 goto done;
1067 break;
1068
1069 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1070 /*
1071 * Setting all of a previous oldext extent to newext.
1072 * The right neighbor is contiguous, the left is not.
1073 */
1074 error = xfs_btree_increment(cur, 0, &i);
1075 if (error)
1076 goto done;
1077 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1078 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1079 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1080 RIGHT.rm_owner, RIGHT.rm_offset,
1081 RIGHT.rm_flags);
1082 error = xfs_btree_delete(cur, &i);
1083 if (error)
1084 goto done;
1085 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1086 error = xfs_btree_decrement(cur, 0, &i);
1087 if (error)
1088 goto done;
1089 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1090 NEW = PREV;
1091 NEW.rm_blockcount = len + RIGHT.rm_blockcount;
1092 NEW.rm_flags = newext;
1093 error = xfs_rmap_update(cur, &NEW);
1094 if (error)
1095 goto done;
1096 break;
1097
1098 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1099 /*
1100 * Setting all of a previous oldext extent to newext.
1101 * Neither the left nor right neighbors are contiguous with
1102 * the new one.
1103 */
1104 NEW = PREV;
1105 NEW.rm_flags = newext;
1106 error = xfs_rmap_update(cur, &NEW);
1107 if (error)
1108 goto done;
1109 break;
1110
1111 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1112 /*
1113 * Setting the first part of a previous oldext extent to newext.
1114 * The left neighbor is contiguous.
1115 */
1116 NEW = PREV;
1117 NEW.rm_offset += len;
1118 NEW.rm_startblock += len;
1119 NEW.rm_blockcount -= len;
1120 error = xfs_rmap_update(cur, &NEW);
1121 if (error)
1122 goto done;
1123 error = xfs_btree_decrement(cur, 0, &i);
1124 if (error)
1125 goto done;
1126 NEW = LEFT;
1127 NEW.rm_blockcount += len;
1128 error = xfs_rmap_update(cur, &NEW);
1129 if (error)
1130 goto done;
1131 break;
1132
1133 case RMAP_LEFT_FILLING:
1134 /*
1135 * Setting the first part of a previous oldext extent to newext.
1136 * The left neighbor is not contiguous.
1137 */
1138 NEW = PREV;
1139 NEW.rm_startblock += len;
1140 NEW.rm_offset += len;
1141 NEW.rm_blockcount -= len;
1142 error = xfs_rmap_update(cur, &NEW);
1143 if (error)
1144 goto done;
1145 NEW.rm_startblock = bno;
1146 NEW.rm_owner = owner;
1147 NEW.rm_offset = offset;
1148 NEW.rm_blockcount = len;
1149 NEW.rm_flags = newext;
1150 cur->bc_rec.r = NEW;
1151 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno,
1152 len, owner, offset, newext);
1153 error = xfs_btree_insert(cur, &i);
1154 if (error)
1155 goto done;
1156 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1157 break;
1158
1159 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1160 /*
1161 * Setting the last part of a previous oldext extent to newext.
1162 * The right neighbor is contiguous with the new allocation.
1163 */
1164 NEW = PREV;
1165 NEW.rm_blockcount -= len;
1166 error = xfs_rmap_update(cur, &NEW);
1167 if (error)
1168 goto done;
1169 error = xfs_btree_increment(cur, 0, &i);
1170 if (error)
1171 goto done;
1172 NEW = RIGHT;
1173 NEW.rm_offset = offset;
1174 NEW.rm_startblock = bno;
1175 NEW.rm_blockcount += len;
1176 error = xfs_rmap_update(cur, &NEW);
1177 if (error)
1178 goto done;
1179 break;
1180
1181 case RMAP_RIGHT_FILLING:
1182 /*
1183 * Setting the last part of a previous oldext extent to newext.
1184 * The right neighbor is not contiguous.
1185 */
1186 NEW = PREV;
1187 NEW.rm_blockcount -= len;
1188 error = xfs_rmap_update(cur, &NEW);
1189 if (error)
1190 goto done;
1191 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1192 oldext, &i);
1193 if (error)
1194 goto done;
1195 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done);
1196 NEW.rm_startblock = bno;
1197 NEW.rm_owner = owner;
1198 NEW.rm_offset = offset;
1199 NEW.rm_blockcount = len;
1200 NEW.rm_flags = newext;
1201 cur->bc_rec.r = NEW;
1202 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno,
1203 len, owner, offset, newext);
1204 error = xfs_btree_insert(cur, &i);
1205 if (error)
1206 goto done;
1207 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1208 break;
1209
1210 case 0:
1211 /*
1212 * Setting the middle part of a previous oldext extent to
1213 * newext. Contiguity is impossible here.
1214 * One extent becomes three extents.
1215 */
1216 /* new right extent - oldext */
1217 NEW.rm_startblock = bno + len;
1218 NEW.rm_owner = owner;
1219 NEW.rm_offset = new_endoff;
1220 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1221 new_endoff;
1222 NEW.rm_flags = PREV.rm_flags;
1223 error = xfs_rmap_update(cur, &NEW);
1224 if (error)
1225 goto done;
1226 /* new left extent - oldext */
1227 NEW = PREV;
1228 NEW.rm_blockcount = offset - PREV.rm_offset;
1229 cur->bc_rec.r = NEW;
1230 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno,
1231 NEW.rm_startblock, NEW.rm_blockcount,
1232 NEW.rm_owner, NEW.rm_offset,
1233 NEW.rm_flags);
1234 error = xfs_btree_insert(cur, &i);
1235 if (error)
1236 goto done;
1237 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1238 /*
1239 * Reset the cursor to the position of the new extent
1240 * we are about to insert as we can't trust it after
1241 * the previous insert.
1242 */
1243 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1244 oldext, &i);
1245 if (error)
1246 goto done;
1247 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done);
1248 /* new middle extent - newext */
1249 cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN;
1250 cur->bc_rec.r.rm_flags |= newext;
1251 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len,
1252 owner, offset, newext);
1253 error = xfs_btree_insert(cur, &i);
1254 if (error)
1255 goto done;
1256 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1257 break;
1258
1259 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1260 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1261 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1262 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1263 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1264 case RMAP_LEFT_CONTIG:
1265 case RMAP_RIGHT_CONTIG:
1266 /*
1267 * These cases are all impossible.
1268 */
1269 ASSERT(0);
1270 }
1271
1272 trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len,
1273 unwritten, oinfo);
1274 done:
1275 if (error)
1276 trace_xfs_rmap_convert_error(cur->bc_mp,
1277 cur->bc_private.a.agno, error, _RET_IP_);
1278 return error;
1279 }
1280
1281 /*
1282 * Convert an unwritten extent to a real extent or vice versa. If there is no
1283 * possibility of overlapping extents, delegate to the simpler convert
1284 * function.
1285 */
1286 STATIC int
1287 xfs_rmap_convert_shared(
1288 struct xfs_btree_cur *cur,
1289 xfs_agblock_t bno,
1290 xfs_extlen_t len,
1291 bool unwritten,
1292 struct xfs_owner_info *oinfo)
1293 {
1294 struct xfs_mount *mp = cur->bc_mp;
1295 struct xfs_rmap_irec r[4]; /* neighbor extent entries */
1296 /* left is 0, right is 1, prev is 2 */
1297 /* new is 3 */
1298 uint64_t owner;
1299 uint64_t offset;
1300 uint64_t new_endoff;
1301 unsigned int oldext;
1302 unsigned int newext;
1303 unsigned int flags = 0;
1304 int i;
1305 int state = 0;
1306 int error;
1307
1308 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1309 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1310 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1311 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1312 new_endoff = offset + len;
1313 trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len,
1314 unwritten, oinfo);
1315
1316 /*
1317 * For the initial lookup, look for and exact match or the left-adjacent
1318 * record for our insertion point. This will also give us the record for
1319 * start block contiguity tests.
1320 */
1321 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
1322 &PREV, &i);
1323 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1324
1325 ASSERT(PREV.rm_offset <= offset);
1326 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1327 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1328 newext = ~oldext & XFS_RMAP_UNWRITTEN;
1329
1330 /*
1331 * Set flags determining what part of the previous oldext allocation
1332 * extent is being replaced by a newext allocation.
1333 */
1334 if (PREV.rm_offset == offset)
1335 state |= RMAP_LEFT_FILLING;
1336 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1337 state |= RMAP_RIGHT_FILLING;
1338
1339 /* Is there a left record that abuts our range? */
1340 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext,
1341 &LEFT, &i);
1342 if (error)
1343 goto done;
1344 if (i) {
1345 state |= RMAP_LEFT_VALID;
1346 XFS_WANT_CORRUPTED_GOTO(mp,
1347 LEFT.rm_startblock + LEFT.rm_blockcount <= bno,
1348 done);
1349 if (xfs_rmap_is_mergeable(&LEFT, owner, newext))
1350 state |= RMAP_LEFT_CONTIG;
1351 }
1352
1353 /* Is there a right record that abuts our range? */
1354 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1355 newext, &i);
1356 if (error)
1357 goto done;
1358 if (i) {
1359 state |= RMAP_RIGHT_VALID;
1360 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1361 if (error)
1362 goto done;
1363 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1364 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock,
1365 done);
1366 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1367 cur->bc_private.a.agno, RIGHT.rm_startblock,
1368 RIGHT.rm_blockcount, RIGHT.rm_owner,
1369 RIGHT.rm_offset, RIGHT.rm_flags);
1370 if (xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1371 state |= RMAP_RIGHT_CONTIG;
1372 }
1373
1374 /* check that left + prev + right is not too long */
1375 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1376 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1377 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1378 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1379 (unsigned long)LEFT.rm_blockcount + len +
1380 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1381 state &= ~RMAP_RIGHT_CONTIG;
1382
1383 trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state,
1384 _RET_IP_);
1385 /*
1386 * Switch out based on the FILLING and CONTIG state bits.
1387 */
1388 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1389 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1390 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1391 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1392 /*
1393 * Setting all of a previous oldext extent to newext.
1394 * The left and right neighbors are both contiguous with new.
1395 */
1396 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1397 RIGHT.rm_blockcount, RIGHT.rm_owner,
1398 RIGHT.rm_offset, RIGHT.rm_flags);
1399 if (error)
1400 goto done;
1401 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1402 PREV.rm_blockcount, PREV.rm_owner,
1403 PREV.rm_offset, PREV.rm_flags);
1404 if (error)
1405 goto done;
1406 NEW = LEFT;
1407 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1408 NEW.rm_blockcount, NEW.rm_owner,
1409 NEW.rm_offset, NEW.rm_flags, &i);
1410 if (error)
1411 goto done;
1412 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1413 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1414 error = xfs_rmap_update(cur, &NEW);
1415 if (error)
1416 goto done;
1417 break;
1418
1419 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1420 /*
1421 * Setting all of a previous oldext extent to newext.
1422 * The left neighbor is contiguous, the right is not.
1423 */
1424 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1425 PREV.rm_blockcount, PREV.rm_owner,
1426 PREV.rm_offset, PREV.rm_flags);
1427 if (error)
1428 goto done;
1429 NEW = LEFT;
1430 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1431 NEW.rm_blockcount, NEW.rm_owner,
1432 NEW.rm_offset, NEW.rm_flags, &i);
1433 if (error)
1434 goto done;
1435 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1436 NEW.rm_blockcount += PREV.rm_blockcount;
1437 error = xfs_rmap_update(cur, &NEW);
1438 if (error)
1439 goto done;
1440 break;
1441
1442 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1443 /*
1444 * Setting all of a previous oldext extent to newext.
1445 * The right neighbor is contiguous, the left is not.
1446 */
1447 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1448 RIGHT.rm_blockcount, RIGHT.rm_owner,
1449 RIGHT.rm_offset, RIGHT.rm_flags);
1450 if (error)
1451 goto done;
1452 NEW = PREV;
1453 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1454 NEW.rm_blockcount, NEW.rm_owner,
1455 NEW.rm_offset, NEW.rm_flags, &i);
1456 if (error)
1457 goto done;
1458 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1459 NEW.rm_blockcount += RIGHT.rm_blockcount;
1460 NEW.rm_flags = RIGHT.rm_flags;
1461 error = xfs_rmap_update(cur, &NEW);
1462 if (error)
1463 goto done;
1464 break;
1465
1466 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1467 /*
1468 * Setting all of a previous oldext extent to newext.
1469 * Neither the left nor right neighbors are contiguous with
1470 * the new one.
1471 */
1472 NEW = PREV;
1473 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1474 NEW.rm_blockcount, NEW.rm_owner,
1475 NEW.rm_offset, NEW.rm_flags, &i);
1476 if (error)
1477 goto done;
1478 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1479 NEW.rm_flags = newext;
1480 error = xfs_rmap_update(cur, &NEW);
1481 if (error)
1482 goto done;
1483 break;
1484
1485 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1486 /*
1487 * Setting the first part of a previous oldext extent to newext.
1488 * The left neighbor is contiguous.
1489 */
1490 NEW = PREV;
1491 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1492 NEW.rm_blockcount, NEW.rm_owner,
1493 NEW.rm_offset, NEW.rm_flags);
1494 if (error)
1495 goto done;
1496 NEW.rm_offset += len;
1497 NEW.rm_startblock += len;
1498 NEW.rm_blockcount -= len;
1499 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1500 NEW.rm_blockcount, NEW.rm_owner,
1501 NEW.rm_offset, NEW.rm_flags);
1502 if (error)
1503 goto done;
1504 NEW = LEFT;
1505 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1506 NEW.rm_blockcount, NEW.rm_owner,
1507 NEW.rm_offset, NEW.rm_flags, &i);
1508 if (error)
1509 goto done;
1510 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1511 NEW.rm_blockcount += len;
1512 error = xfs_rmap_update(cur, &NEW);
1513 if (error)
1514 goto done;
1515 break;
1516
1517 case RMAP_LEFT_FILLING:
1518 /*
1519 * Setting the first part of a previous oldext extent to newext.
1520 * The left neighbor is not contiguous.
1521 */
1522 NEW = PREV;
1523 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1524 NEW.rm_blockcount, NEW.rm_owner,
1525 NEW.rm_offset, NEW.rm_flags);
1526 if (error)
1527 goto done;
1528 NEW.rm_offset += len;
1529 NEW.rm_startblock += len;
1530 NEW.rm_blockcount -= len;
1531 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1532 NEW.rm_blockcount, NEW.rm_owner,
1533 NEW.rm_offset, NEW.rm_flags);
1534 if (error)
1535 goto done;
1536 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1537 if (error)
1538 goto done;
1539 break;
1540
1541 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1542 /*
1543 * Setting the last part of a previous oldext extent to newext.
1544 * The right neighbor is contiguous with the new allocation.
1545 */
1546 NEW = PREV;
1547 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1548 NEW.rm_blockcount, NEW.rm_owner,
1549 NEW.rm_offset, NEW.rm_flags, &i);
1550 if (error)
1551 goto done;
1552 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1553 NEW.rm_blockcount = offset - NEW.rm_offset;
1554 error = xfs_rmap_update(cur, &NEW);
1555 if (error)
1556 goto done;
1557 NEW = RIGHT;
1558 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1559 NEW.rm_blockcount, NEW.rm_owner,
1560 NEW.rm_offset, NEW.rm_flags);
1561 if (error)
1562 goto done;
1563 NEW.rm_offset = offset;
1564 NEW.rm_startblock = bno;
1565 NEW.rm_blockcount += len;
1566 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1567 NEW.rm_blockcount, NEW.rm_owner,
1568 NEW.rm_offset, NEW.rm_flags);
1569 if (error)
1570 goto done;
1571 break;
1572
1573 case RMAP_RIGHT_FILLING:
1574 /*
1575 * Setting the last part of a previous oldext extent to newext.
1576 * The right neighbor is not contiguous.
1577 */
1578 NEW = PREV;
1579 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1580 NEW.rm_blockcount, NEW.rm_owner,
1581 NEW.rm_offset, NEW.rm_flags, &i);
1582 if (error)
1583 goto done;
1584 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1585 NEW.rm_blockcount -= len;
1586 error = xfs_rmap_update(cur, &NEW);
1587 if (error)
1588 goto done;
1589 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1590 if (error)
1591 goto done;
1592 break;
1593
1594 case 0:
1595 /*
1596 * Setting the middle part of a previous oldext extent to
1597 * newext. Contiguity is impossible here.
1598 * One extent becomes three extents.
1599 */
1600 /* new right extent - oldext */
1601 NEW.rm_startblock = bno + len;
1602 NEW.rm_owner = owner;
1603 NEW.rm_offset = new_endoff;
1604 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1605 new_endoff;
1606 NEW.rm_flags = PREV.rm_flags;
1607 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1608 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1609 NEW.rm_flags);
1610 if (error)
1611 goto done;
1612 /* new left extent - oldext */
1613 NEW = PREV;
1614 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1615 NEW.rm_blockcount, NEW.rm_owner,
1616 NEW.rm_offset, NEW.rm_flags, &i);
1617 if (error)
1618 goto done;
1619 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1620 NEW.rm_blockcount = offset - NEW.rm_offset;
1621 error = xfs_rmap_update(cur, &NEW);
1622 if (error)
1623 goto done;
1624 /* new middle extent - newext */
1625 NEW.rm_startblock = bno;
1626 NEW.rm_blockcount = len;
1627 NEW.rm_owner = owner;
1628 NEW.rm_offset = offset;
1629 NEW.rm_flags = newext;
1630 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1631 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1632 NEW.rm_flags);
1633 if (error)
1634 goto done;
1635 break;
1636
1637 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1638 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1639 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1640 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1641 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1642 case RMAP_LEFT_CONTIG:
1643 case RMAP_RIGHT_CONTIG:
1644 /*
1645 * These cases are all impossible.
1646 */
1647 ASSERT(0);
1648 }
1649
1650 trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len,
1651 unwritten, oinfo);
1652 done:
1653 if (error)
1654 trace_xfs_rmap_convert_error(cur->bc_mp,
1655 cur->bc_private.a.agno, error, _RET_IP_);
1656 return error;
1657 }
1658
1659 #undef NEW
1660 #undef LEFT
1661 #undef RIGHT
1662 #undef PREV
1663
1664 /*
1665 * Find an extent in the rmap btree and unmap it. For rmap extent types that
1666 * can overlap (data fork rmaps on reflink filesystems) we must be careful
1667 * that the prev/next records in the btree might belong to another owner.
1668 * Therefore we must use delete+insert to alter any of the key fields.
1669 *
1670 * For every other situation there can only be one owner for a given extent,
1671 * so we can call the regular _free function.
1672 */
1673 STATIC int
1674 xfs_rmap_unmap_shared(
1675 struct xfs_btree_cur *cur,
1676 xfs_agblock_t bno,
1677 xfs_extlen_t len,
1678 bool unwritten,
1679 struct xfs_owner_info *oinfo)
1680 {
1681 struct xfs_mount *mp = cur->bc_mp;
1682 struct xfs_rmap_irec ltrec;
1683 uint64_t ltoff;
1684 int error = 0;
1685 int i;
1686 uint64_t owner;
1687 uint64_t offset;
1688 unsigned int flags;
1689
1690 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1691 if (unwritten)
1692 flags |= XFS_RMAP_UNWRITTEN;
1693 trace_xfs_rmap_unmap(mp, cur->bc_private.a.agno, bno, len,
1694 unwritten, oinfo);
1695
1696 /*
1697 * We should always have a left record because there's a static record
1698 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
1699 * will not ever be removed from the tree.
1700 */
1701 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
1702 &ltrec, &i);
1703 if (error)
1704 goto out_error;
1705 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1706 ltoff = ltrec.rm_offset;
1707
1708 /* Make sure the extent we found covers the entire freeing range. */
1709 XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_startblock <= bno &&
1710 ltrec.rm_startblock + ltrec.rm_blockcount >=
1711 bno + len, out_error);
1712
1713 /* Make sure the owner matches what we expect to find in the tree. */
1714 XFS_WANT_CORRUPTED_GOTO(mp, owner == ltrec.rm_owner, out_error);
1715
1716 /* Make sure the unwritten flag matches. */
1717 XFS_WANT_CORRUPTED_GOTO(mp, (flags & XFS_RMAP_UNWRITTEN) ==
1718 (ltrec.rm_flags & XFS_RMAP_UNWRITTEN), out_error);
1719
1720 /* Check the offset. */
1721 XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_offset <= offset, out_error);
1722 XFS_WANT_CORRUPTED_GOTO(mp, offset <= ltoff + ltrec.rm_blockcount,
1723 out_error);
1724
1725 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
1726 /* Exact match, simply remove the record from rmap tree. */
1727 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
1728 ltrec.rm_blockcount, ltrec.rm_owner,
1729 ltrec.rm_offset, ltrec.rm_flags);
1730 if (error)
1731 goto out_error;
1732 } else if (ltrec.rm_startblock == bno) {
1733 /*
1734 * Overlap left hand side of extent: move the start, trim the
1735 * length and update the current record.
1736 *
1737 * ltbno ltlen
1738 * Orig: |oooooooooooooooooooo|
1739 * Freeing: |fffffffff|
1740 * Result: |rrrrrrrrrr|
1741 * bno len
1742 */
1743
1744 /* Delete prev rmap. */
1745 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
1746 ltrec.rm_blockcount, ltrec.rm_owner,
1747 ltrec.rm_offset, ltrec.rm_flags);
1748 if (error)
1749 goto out_error;
1750
1751 /* Add an rmap at the new offset. */
1752 ltrec.rm_startblock += len;
1753 ltrec.rm_blockcount -= len;
1754 ltrec.rm_offset += len;
1755 error = xfs_rmap_insert(cur, ltrec.rm_startblock,
1756 ltrec.rm_blockcount, ltrec.rm_owner,
1757 ltrec.rm_offset, ltrec.rm_flags);
1758 if (error)
1759 goto out_error;
1760 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
1761 /*
1762 * Overlap right hand side of extent: trim the length and
1763 * update the current record.
1764 *
1765 * ltbno ltlen
1766 * Orig: |oooooooooooooooooooo|
1767 * Freeing: |fffffffff|
1768 * Result: |rrrrrrrrrr|
1769 * bno len
1770 */
1771 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
1772 ltrec.rm_blockcount, ltrec.rm_owner,
1773 ltrec.rm_offset, ltrec.rm_flags, &i);
1774 if (error)
1775 goto out_error;
1776 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1777 ltrec.rm_blockcount -= len;
1778 error = xfs_rmap_update(cur, &ltrec);
1779 if (error)
1780 goto out_error;
1781 } else {
1782 /*
1783 * Overlap middle of extent: trim the length of the existing
1784 * record to the length of the new left-extent size, increment
1785 * the insertion position so we can insert a new record
1786 * containing the remaining right-extent space.
1787 *
1788 * ltbno ltlen
1789 * Orig: |oooooooooooooooooooo|
1790 * Freeing: |fffffffff|
1791 * Result: |rrrrr| |rrrr|
1792 * bno len
1793 */
1794 xfs_extlen_t orig_len = ltrec.rm_blockcount;
1795
1796 /* Shrink the left side of the rmap */
1797 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
1798 ltrec.rm_blockcount, ltrec.rm_owner,
1799 ltrec.rm_offset, ltrec.rm_flags, &i);
1800 if (error)
1801 goto out_error;
1802 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1803 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
1804 error = xfs_rmap_update(cur, &ltrec);
1805 if (error)
1806 goto out_error;
1807
1808 /* Add an rmap at the new offset */
1809 error = xfs_rmap_insert(cur, bno + len,
1810 orig_len - len - ltrec.rm_blockcount,
1811 ltrec.rm_owner, offset + len,
1812 ltrec.rm_flags);
1813 if (error)
1814 goto out_error;
1815 }
1816
1817 trace_xfs_rmap_unmap_done(mp, cur->bc_private.a.agno, bno, len,
1818 unwritten, oinfo);
1819 out_error:
1820 if (error)
1821 trace_xfs_rmap_unmap_error(cur->bc_mp,
1822 cur->bc_private.a.agno, error, _RET_IP_);
1823 return error;
1824 }
1825
1826 /*
1827 * Find an extent in the rmap btree and map it. For rmap extent types that
1828 * can overlap (data fork rmaps on reflink filesystems) we must be careful
1829 * that the prev/next records in the btree might belong to another owner.
1830 * Therefore we must use delete+insert to alter any of the key fields.
1831 *
1832 * For every other situation there can only be one owner for a given extent,
1833 * so we can call the regular _alloc function.
1834 */
1835 STATIC int
1836 xfs_rmap_map_shared(
1837 struct xfs_btree_cur *cur,
1838 xfs_agblock_t bno,
1839 xfs_extlen_t len,
1840 bool unwritten,
1841 struct xfs_owner_info *oinfo)
1842 {
1843 struct xfs_mount *mp = cur->bc_mp;
1844 struct xfs_rmap_irec ltrec;
1845 struct xfs_rmap_irec gtrec;
1846 int have_gt;
1847 int have_lt;
1848 int error = 0;
1849 int i;
1850 uint64_t owner;
1851 uint64_t offset;
1852 unsigned int flags = 0;
1853
1854 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1855 if (unwritten)
1856 flags |= XFS_RMAP_UNWRITTEN;
1857 trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len,
1858 unwritten, oinfo);
1859
1860 /* Is there a left record that abuts our range? */
1861 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags,
1862 &ltrec, &have_lt);
1863 if (error)
1864 goto out_error;
1865 if (have_lt &&
1866 !xfs_rmap_is_mergeable(&ltrec, owner, flags))
1867 have_lt = 0;
1868
1869 /* Is there a right record that abuts our range? */
1870 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1871 flags, &have_gt);
1872 if (error)
1873 goto out_error;
1874 if (have_gt) {
1875 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
1876 if (error)
1877 goto out_error;
1878 XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error);
1879 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1880 cur->bc_private.a.agno, gtrec.rm_startblock,
1881 gtrec.rm_blockcount, gtrec.rm_owner,
1882 gtrec.rm_offset, gtrec.rm_flags);
1883
1884 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
1885 have_gt = 0;
1886 }
1887
1888 if (have_lt &&
1889 ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
1890 ltrec.rm_offset + ltrec.rm_blockcount == offset) {
1891 /*
1892 * Left edge contiguous, merge into left record.
1893 *
1894 * ltbno ltlen
1895 * orig: |ooooooooo|
1896 * adding: |aaaaaaaaa|
1897 * result: |rrrrrrrrrrrrrrrrrrr|
1898 * bno len
1899 */
1900 ltrec.rm_blockcount += len;
1901 if (have_gt &&
1902 bno + len == gtrec.rm_startblock &&
1903 offset + len == gtrec.rm_offset) {
1904 /*
1905 * Right edge also contiguous, delete right record
1906 * and merge into left record.
1907 *
1908 * ltbno ltlen gtbno gtlen
1909 * orig: |ooooooooo| |ooooooooo|
1910 * adding: |aaaaaaaaa|
1911 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
1912 */
1913 ltrec.rm_blockcount += gtrec.rm_blockcount;
1914 error = xfs_rmap_delete(cur, gtrec.rm_startblock,
1915 gtrec.rm_blockcount, gtrec.rm_owner,
1916 gtrec.rm_offset, gtrec.rm_flags);
1917 if (error)
1918 goto out_error;
1919 }
1920
1921 /* Point the cursor back to the left record and update. */
1922 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
1923 ltrec.rm_blockcount, ltrec.rm_owner,
1924 ltrec.rm_offset, ltrec.rm_flags, &i);
1925 if (error)
1926 goto out_error;
1927 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1928
1929 error = xfs_rmap_update(cur, &ltrec);
1930 if (error)
1931 goto out_error;
1932 } else if (have_gt &&
1933 bno + len == gtrec.rm_startblock &&
1934 offset + len == gtrec.rm_offset) {
1935 /*
1936 * Right edge contiguous, merge into right record.
1937 *
1938 * gtbno gtlen
1939 * Orig: |ooooooooo|
1940 * adding: |aaaaaaaaa|
1941 * Result: |rrrrrrrrrrrrrrrrrrr|
1942 * bno len
1943 */
1944 /* Delete the old record. */
1945 error = xfs_rmap_delete(cur, gtrec.rm_startblock,
1946 gtrec.rm_blockcount, gtrec.rm_owner,
1947 gtrec.rm_offset, gtrec.rm_flags);
1948 if (error)
1949 goto out_error;
1950
1951 /* Move the start and re-add it. */
1952 gtrec.rm_startblock = bno;
1953 gtrec.rm_blockcount += len;
1954 gtrec.rm_offset = offset;
1955 error = xfs_rmap_insert(cur, gtrec.rm_startblock,
1956 gtrec.rm_blockcount, gtrec.rm_owner,
1957 gtrec.rm_offset, gtrec.rm_flags);
1958 if (error)
1959 goto out_error;
1960 } else {
1961 /*
1962 * No contiguous edge with identical owner, insert
1963 * new record at current cursor position.
1964 */
1965 error = xfs_rmap_insert(cur, bno, len, owner, offset, flags);
1966 if (error)
1967 goto out_error;
1968 }
1969
1970 trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len,
1971 unwritten, oinfo);
1972 out_error:
1973 if (error)
1974 trace_xfs_rmap_map_error(cur->bc_mp,
1975 cur->bc_private.a.agno, error, _RET_IP_);
1976 return error;
1977 }
1978
1979 struct xfs_rmap_query_range_info {
1980 xfs_rmap_query_range_fn fn;
1981 void *priv;
1982 };
1983
1984 /* Format btree record and pass to our callback. */
1985 STATIC int
1986 xfs_rmap_query_range_helper(
1987 struct xfs_btree_cur *cur,
1988 union xfs_btree_rec *rec,
1989 void *priv)
1990 {
1991 struct xfs_rmap_query_range_info *query = priv;
1992 struct xfs_rmap_irec irec;
1993 int error;
1994
1995 error = xfs_rmap_btrec_to_irec(rec, &irec);
1996 if (error)
1997 return error;
1998 return query->fn(cur, &irec, query->priv);
1999 }
2000
2001 /* Find all rmaps between two keys. */
2002 int
2003 xfs_rmap_query_range(
2004 struct xfs_btree_cur *cur,
2005 struct xfs_rmap_irec *low_rec,
2006 struct xfs_rmap_irec *high_rec,
2007 xfs_rmap_query_range_fn fn,
2008 void *priv)
2009 {
2010 union xfs_btree_irec low_brec;
2011 union xfs_btree_irec high_brec;
2012 struct xfs_rmap_query_range_info query;
2013
2014 low_brec.r = *low_rec;
2015 high_brec.r = *high_rec;
2016 query.priv = priv;
2017 query.fn = fn;
2018 return xfs_btree_query_range(cur, &low_brec, &high_brec,
2019 xfs_rmap_query_range_helper, &query);
2020 }
2021
2022 /* Find all rmaps. */
2023 int
2024 xfs_rmap_query_all(
2025 struct xfs_btree_cur *cur,
2026 xfs_rmap_query_range_fn fn,
2027 void *priv)
2028 {
2029 struct xfs_rmap_query_range_info query;
2030
2031 query.priv = priv;
2032 query.fn = fn;
2033 return xfs_btree_query_all(cur, xfs_rmap_query_range_helper, &query);
2034 }
2035
2036 /* Clean up after calling xfs_rmap_finish_one. */
2037 void
2038 xfs_rmap_finish_one_cleanup(
2039 struct xfs_trans *tp,
2040 struct xfs_btree_cur *rcur,
2041 int error)
2042 {
2043 struct xfs_buf *agbp;
2044
2045 if (rcur == NULL)
2046 return;
2047 agbp = rcur->bc_private.a.agbp;
2048 xfs_btree_del_cursor(rcur, error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR);
2049 if (error)
2050 xfs_trans_brelse(tp, agbp);
2051 }
2052
2053 /*
2054 * Process one of the deferred rmap operations. We pass back the
2055 * btree cursor to maintain our lock on the rmapbt between calls.
2056 * This saves time and eliminates a buffer deadlock between the
2057 * superblock and the AGF because we'll always grab them in the same
2058 * order.
2059 */
2060 int
2061 xfs_rmap_finish_one(
2062 struct xfs_trans *tp,
2063 enum xfs_rmap_intent_type type,
2064 __uint64_t owner,
2065 int whichfork,
2066 xfs_fileoff_t startoff,
2067 xfs_fsblock_t startblock,
2068 xfs_filblks_t blockcount,
2069 xfs_exntst_t state,
2070 struct xfs_btree_cur **pcur)
2071 {
2072 struct xfs_mount *mp = tp->t_mountp;
2073 struct xfs_btree_cur *rcur;
2074 struct xfs_buf *agbp = NULL;
2075 int error = 0;
2076 xfs_agnumber_t agno;
2077 struct xfs_owner_info oinfo;
2078 xfs_agblock_t bno;
2079 bool unwritten;
2080
2081 agno = XFS_FSB_TO_AGNO(mp, startblock);
2082 ASSERT(agno != NULLAGNUMBER);
2083 bno = XFS_FSB_TO_AGBNO(mp, startblock);
2084
2085 trace_xfs_rmap_deferred(mp, agno, type, bno, owner, whichfork,
2086 startoff, blockcount, state);
2087
2088 if (XFS_TEST_ERROR(false, mp,
2089 XFS_ERRTAG_RMAP_FINISH_ONE,
2090 XFS_RANDOM_RMAP_FINISH_ONE))
2091 return -EIO;
2092
2093 /*
2094 * If we haven't gotten a cursor or the cursor AG doesn't match
2095 * the startblock, get one now.
2096 */
2097 rcur = *pcur;
2098 if (rcur != NULL && rcur->bc_private.a.agno != agno) {
2099 xfs_rmap_finish_one_cleanup(tp, rcur, 0);
2100 rcur = NULL;
2101 *pcur = NULL;
2102 }
2103 if (rcur == NULL) {
2104 /*
2105 * Refresh the freelist before we start changing the
2106 * rmapbt, because a shape change could cause us to
2107 * allocate blocks.
2108 */
2109 error = xfs_free_extent_fix_freelist(tp, agno, &agbp);
2110 if (error)
2111 return error;
2112 if (!agbp)
2113 return -EFSCORRUPTED;
2114
2115 rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno);
2116 if (!rcur) {
2117 error = -ENOMEM;
2118 goto out_cur;
2119 }
2120 }
2121 *pcur = rcur;
2122
2123 xfs_rmap_ino_owner(&oinfo, owner, whichfork, startoff);
2124 unwritten = state == XFS_EXT_UNWRITTEN;
2125 bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, startblock);
2126
2127 switch (type) {
2128 case XFS_RMAP_ALLOC:
2129 case XFS_RMAP_MAP:
2130 error = xfs_rmap_map(rcur, bno, blockcount, unwritten, &oinfo);
2131 break;
2132 case XFS_RMAP_MAP_SHARED:
2133 error = xfs_rmap_map_shared(rcur, bno, blockcount, unwritten,
2134 &oinfo);
2135 break;
2136 case XFS_RMAP_FREE:
2137 case XFS_RMAP_UNMAP:
2138 error = xfs_rmap_unmap(rcur, bno, blockcount, unwritten,
2139 &oinfo);
2140 break;
2141 case XFS_RMAP_UNMAP_SHARED:
2142 error = xfs_rmap_unmap_shared(rcur, bno, blockcount, unwritten,
2143 &oinfo);
2144 break;
2145 case XFS_RMAP_CONVERT:
2146 error = xfs_rmap_convert(rcur, bno, blockcount, !unwritten,
2147 &oinfo);
2148 break;
2149 case XFS_RMAP_CONVERT_SHARED:
2150 error = xfs_rmap_convert_shared(rcur, bno, blockcount,
2151 !unwritten, &oinfo);
2152 break;
2153 default:
2154 ASSERT(0);
2155 error = -EFSCORRUPTED;
2156 }
2157 return error;
2158
2159 out_cur:
2160 xfs_trans_brelse(tp, agbp);
2161
2162 return error;
2163 }
2164
2165 /*
2166 * Don't defer an rmap if we aren't an rmap filesystem.
2167 */
2168 static bool
2169 xfs_rmap_update_is_needed(
2170 struct xfs_mount *mp,
2171 int whichfork)
2172 {
2173 return xfs_sb_version_hasrmapbt(&mp->m_sb) && whichfork != XFS_COW_FORK;
2174 }
2175
2176 /*
2177 * Record a rmap intent; the list is kept sorted first by AG and then by
2178 * increasing age.
2179 */
2180 static int
2181 __xfs_rmap_add(
2182 struct xfs_mount *mp,
2183 struct xfs_defer_ops *dfops,
2184 enum xfs_rmap_intent_type type,
2185 __uint64_t owner,
2186 int whichfork,
2187 struct xfs_bmbt_irec *bmap)
2188 {
2189 struct xfs_rmap_intent *ri;
2190
2191 trace_xfs_rmap_defer(mp, XFS_FSB_TO_AGNO(mp, bmap->br_startblock),
2192 type,
2193 XFS_FSB_TO_AGBNO(mp, bmap->br_startblock),
2194 owner, whichfork,
2195 bmap->br_startoff,
2196 bmap->br_blockcount,
2197 bmap->br_state);
2198
2199 ri = kmem_alloc(sizeof(struct xfs_rmap_intent), KM_SLEEP | KM_NOFS);
2200 INIT_LIST_HEAD(&ri->ri_list);
2201 ri->ri_type = type;
2202 ri->ri_owner = owner;
2203 ri->ri_whichfork = whichfork;
2204 ri->ri_bmap = *bmap;
2205
2206 xfs_defer_add(dfops, XFS_DEFER_OPS_TYPE_RMAP, &ri->ri_list);
2207 return 0;
2208 }
2209
2210 /* Map an extent into a file. */
2211 int
2212 xfs_rmap_map_extent(
2213 struct xfs_mount *mp,
2214 struct xfs_defer_ops *dfops,
2215 struct xfs_inode *ip,
2216 int whichfork,
2217 struct xfs_bmbt_irec *PREV)
2218 {
2219 if (!xfs_rmap_update_is_needed(mp, whichfork))
2220 return 0;
2221
2222 return __xfs_rmap_add(mp, dfops, xfs_is_reflink_inode(ip) ?
2223 XFS_RMAP_MAP_SHARED : XFS_RMAP_MAP, ip->i_ino,
2224 whichfork, PREV);
2225 }
2226
2227 /* Unmap an extent out of a file. */
2228 int
2229 xfs_rmap_unmap_extent(
2230 struct xfs_mount *mp,
2231 struct xfs_defer_ops *dfops,
2232 struct xfs_inode *ip,
2233 int whichfork,
2234 struct xfs_bmbt_irec *PREV)
2235 {
2236 if (!xfs_rmap_update_is_needed(mp, whichfork))
2237 return 0;
2238
2239 return __xfs_rmap_add(mp, dfops, xfs_is_reflink_inode(ip) ?
2240 XFS_RMAP_UNMAP_SHARED : XFS_RMAP_UNMAP, ip->i_ino,
2241 whichfork, PREV);
2242 }
2243
2244 /* Convert a data fork extent from unwritten to real or vice versa. */
2245 int
2246 xfs_rmap_convert_extent(
2247 struct xfs_mount *mp,
2248 struct xfs_defer_ops *dfops,
2249 struct xfs_inode *ip,
2250 int whichfork,
2251 struct xfs_bmbt_irec *PREV)
2252 {
2253 if (!xfs_rmap_update_is_needed(mp, whichfork))
2254 return 0;
2255
2256 return __xfs_rmap_add(mp, dfops, xfs_is_reflink_inode(ip) ?
2257 XFS_RMAP_CONVERT_SHARED : XFS_RMAP_CONVERT, ip->i_ino,
2258 whichfork, PREV);
2259 }
2260
2261 /* Schedule the creation of an rmap for non-file data. */
2262 int
2263 xfs_rmap_alloc_extent(
2264 struct xfs_mount *mp,
2265 struct xfs_defer_ops *dfops,
2266 xfs_agnumber_t agno,
2267 xfs_agblock_t bno,
2268 xfs_extlen_t len,
2269 __uint64_t owner)
2270 {
2271 struct xfs_bmbt_irec bmap;
2272
2273 if (!xfs_rmap_update_is_needed(mp, XFS_DATA_FORK))
2274 return 0;
2275
2276 bmap.br_startblock = XFS_AGB_TO_FSB(mp, agno, bno);
2277 bmap.br_blockcount = len;
2278 bmap.br_startoff = 0;
2279 bmap.br_state = XFS_EXT_NORM;
2280
2281 return __xfs_rmap_add(mp, dfops, XFS_RMAP_ALLOC, owner,
2282 XFS_DATA_FORK, &bmap);
2283 }
2284
2285 /* Schedule the deletion of an rmap for non-file data. */
2286 int
2287 xfs_rmap_free_extent(
2288 struct xfs_mount *mp,
2289 struct xfs_defer_ops *dfops,
2290 xfs_agnumber_t agno,
2291 xfs_agblock_t bno,
2292 xfs_extlen_t len,
2293 __uint64_t owner)
2294 {
2295 struct xfs_bmbt_irec bmap;
2296
2297 if (!xfs_rmap_update_is_needed(mp, XFS_DATA_FORK))
2298 return 0;
2299
2300 bmap.br_startblock = XFS_AGB_TO_FSB(mp, agno, bno);
2301 bmap.br_blockcount = len;
2302 bmap.br_startoff = 0;
2303 bmap.br_state = XFS_EXT_NORM;
2304
2305 return __xfs_rmap_add(mp, dfops, XFS_RMAP_FREE, owner,
2306 XFS_DATA_FORK, &bmap);
2307 }
Ubuntu Artful kernel mirror