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