1/*
   2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
   3 * All Rights Reserved.
   4 *
   5 * This program is free software; you can redistribute it and/or
   6 * modify it under the terms of the GNU General Public License as
   7 * published by the Free Software Foundation.
   8 *
   9 * This program is distributed in the hope that it would be useful,
  10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 * GNU General Public License for more details.
  13 *
  14 * You should have received a copy of the GNU General Public License
  15 * along with this program; if not, write the Free Software Foundation,
  16 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17 */
  18#include "xfs.h"
  19#include "xfs_fs.h"
  20#include "xfs_types.h"
 
 
 
  21#include "xfs_bit.h"
  22#include "xfs_log.h"
  23#include "xfs_trans.h"
  24#include "xfs_sb.h"
  25#include "xfs_ag.h"
  26#include "xfs_dir2.h"
  27#include "xfs_mount.h"
  28#include "xfs_bmap_btree.h"
  29#include "xfs_dinode.h"
  30#include "xfs_inode.h"
  31#include "xfs_alloc.h"
  32#include "xfs_bmap.h"
  33#include "xfs_rtalloc.h"
  34#include "xfs_fsops.h"
 
  35#include "xfs_error.h"
  36#include "xfs_inode_item.h"
  37#include "xfs_trans_space.h"
  38#include "xfs_utils.h"
  39#include "xfs_trace.h"
  40#include "xfs_buf.h"
 
 
 
  41
  42
  43/*
  44 * Prototypes for internal functions.
 
 
 
  45 */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  46
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  47
  48STATIC int xfs_rtallocate_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  49		xfs_extlen_t, xfs_buf_t **, xfs_fsblock_t *);
  50STATIC int xfs_rtany_summary(xfs_mount_t *, xfs_trans_t *, int, int,
  51		xfs_rtblock_t, xfs_buf_t **, xfs_fsblock_t *, int *);
  52STATIC int xfs_rtcheck_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  53		xfs_extlen_t, int, xfs_rtblock_t *, int *);
  54STATIC int xfs_rtfind_back(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  55		xfs_rtblock_t, xfs_rtblock_t *);
  56STATIC int xfs_rtfind_forw(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  57		xfs_rtblock_t, xfs_rtblock_t *);
  58STATIC int xfs_rtget_summary( xfs_mount_t *, xfs_trans_t *, int,
  59		xfs_rtblock_t, xfs_buf_t **, xfs_fsblock_t *, xfs_suminfo_t *);
  60STATIC int xfs_rtmodify_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
  61		xfs_extlen_t, int);
  62STATIC int xfs_rtmodify_summary(xfs_mount_t *, xfs_trans_t *, int,
  63		xfs_rtblock_t, int, xfs_buf_t **, xfs_fsblock_t *);
  64
  65/*
  66 * Internal functions.
  67 */
  68
  69/*
  70 * Allocate space to the bitmap or summary file, and zero it, for growfs.
 
  71 */
  72STATIC int				/* error */
  73xfs_growfs_rt_alloc(
  74	xfs_mount_t	*mp,		/* file system mount point */
  75	xfs_extlen_t	oblocks,	/* old count of blocks */
  76	xfs_extlen_t	nblocks,	/* new count of blocks */
  77	xfs_inode_t	*ip)		/* inode (bitmap/summary) */
 
 
 
 
  78{
  79	xfs_fileoff_t	bno;		/* block number in file */
  80	xfs_buf_t	*bp;		/* temporary buffer for zeroing */
  81	int		committed;	/* transaction committed flag */
  82	xfs_daddr_t	d;		/* disk block address */
  83	int		error;		/* error return value */
  84	xfs_fsblock_t	firstblock;	/* first block allocated in xaction */
  85	xfs_bmap_free_t	flist;		/* list of freed blocks */
  86	xfs_fsblock_t	fsbno;		/* filesystem block for bno */
  87	xfs_bmbt_irec_t	map;		/* block map output */
  88	int		nmap;		/* number of block maps */
  89	int		resblks;	/* space reservation */
  90
  91	/*
  92	 * Allocate space to the file, as necessary.
  93	 */
  94	while (oblocks < nblocks) {
  95		int		cancelflags = 0;
  96		xfs_trans_t	*tp;
  97
  98		tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_ALLOC);
  99		resblks = XFS_GROWFSRT_SPACE_RES(mp, nblocks - oblocks);
 100		/*
 101		 * Reserve space & log for one extent added to the file.
 102		 */
 103		if ((error = xfs_trans_reserve(tp, resblks,
 104				XFS_GROWRTALLOC_LOG_RES(mp), 0,
 105				XFS_TRANS_PERM_LOG_RES,
 106				XFS_DEFAULT_PERM_LOG_COUNT)))
 107			goto error_cancel;
 108		cancelflags = XFS_TRANS_RELEASE_LOG_RES;
 109		/*
 110		 * Lock the inode.
 111		 */
 112		xfs_ilock(ip, XFS_ILOCK_EXCL);
 113		xfs_trans_ijoin(tp, ip, XFS_ILOCK_EXCL);
 
 
 
 
 
 
 
 
 
 114
 115		xfs_bmap_init(&flist, &firstblock);
 116		/*
 117		 * Allocate blocks to the bitmap file.
 118		 */
 119		nmap = 1;
 120		cancelflags |= XFS_TRANS_ABORT;
 121		error = xfs_bmapi_write(tp, ip, oblocks, nblocks - oblocks,
 122					XFS_BMAPI_METADATA, &firstblock,
 123					resblks, &map, &nmap, &flist);
 124		if (!error && nmap < 1)
 125			error = XFS_ERROR(ENOSPC);
 126		if (error)
 127			goto error_cancel;
 128		/*
 129		 * Free any blocks freed up in the transaction, then commit.
 130		 */
 131		error = xfs_bmap_finish(&tp, &flist, &committed);
 132		if (error)
 133			goto error_cancel;
 134		error = xfs_trans_commit(tp, XFS_TRANS_RELEASE_LOG_RES);
 135		if (error)
 136			goto error;
 137		/*
 138		 * Now we need to clear the allocated blocks.
 139		 * Do this one block per transaction, to keep it simple.
 140		 */
 141		cancelflags = 0;
 142		for (bno = map.br_startoff, fsbno = map.br_startblock;
 143		     bno < map.br_startoff + map.br_blockcount;
 144		     bno++, fsbno++) {
 145			tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_ZERO);
 146			/*
 147			 * Reserve log for one block zeroing.
 148			 */
 149			if ((error = xfs_trans_reserve(tp, 0,
 150					XFS_GROWRTZERO_LOG_RES(mp), 0, 0, 0)))
 151				goto error_cancel;
 152			/*
 153			 * Lock the bitmap inode.
 154			 */
 155			xfs_ilock(ip, XFS_ILOCK_EXCL);
 156			xfs_trans_ijoin(tp, ip, XFS_ILOCK_EXCL);
 157			/*
 158			 * Get a buffer for the block.
 159			 */
 160			d = XFS_FSB_TO_DADDR(mp, fsbno);
 161			bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d,
 162				mp->m_bsize, 0);
 163			if (bp == NULL) {
 164				error = XFS_ERROR(EIO);
 165error_cancel:
 166				xfs_trans_cancel(tp, cancelflags);
 167				goto error;
 168			}
 169			memset(bp->b_addr, 0, mp->m_sb.sb_blocksize);
 170			xfs_trans_log_buf(tp, bp, 0, mp->m_sb.sb_blocksize - 1);
 171			/*
 172			 * Commit the transaction.
 173			 */
 174			error = xfs_trans_commit(tp, 0);
 175			if (error)
 176				goto error;
 
 
 
 
 
 
 
 
 
 
 
 177		}
 178		/*
 179		 * Go on to the next extent, if any.
 180		 */
 181		oblocks = map.br_startoff + map.br_blockcount;
 182	}
 183	return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 184
 185error:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 186	return error;
 187}
 188
 189/*
 190 * Attempt to allocate an extent minlen<=len<=maxlen starting from
 191 * bitmap block bbno.  If we don't get maxlen then use prod to trim
 192 * the length, if given.  Returns error; returns starting block in *rtblock.
 193 * The lengths are all in rtextents.
 194 */
 195STATIC int				/* error */
 196xfs_rtallocate_extent_block(
 197	xfs_mount_t	*mp,		/* file system mount point */
 198	xfs_trans_t	*tp,		/* transaction pointer */
 199	xfs_rtblock_t	bbno,		/* bitmap block number */
 200	xfs_extlen_t	minlen,		/* minimum length to allocate */
 201	xfs_extlen_t	maxlen,		/* maximum length to allocate */
 202	xfs_extlen_t	*len,		/* out: actual length allocated */
 203	xfs_rtblock_t	*nextp,		/* out: next block to try */
 204	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
 205	xfs_fsblock_t	*rsb,		/* in/out: summary block number */
 206	xfs_extlen_t	prod,		/* extent product factor */
 207	xfs_rtblock_t	*rtblock)	/* out: start block allocated */
 208{
 209	xfs_rtblock_t	besti;		/* best rtblock found so far */
 210	xfs_rtblock_t	bestlen;	/* best length found so far */
 211	xfs_rtblock_t	end;		/* last rtblock in chunk */
 212	int		error;		/* error value */
 213	xfs_rtblock_t	i;		/* current rtblock trying */
 214	xfs_rtblock_t	next;		/* next rtblock to try */
 215	int		stat;		/* status from internal calls */
 216
 217	/*
 218	 * Loop over all the extents starting in this bitmap block,
 219	 * looking for one that's long enough.
 220	 */
 221	for (i = XFS_BLOCKTOBIT(mp, bbno), besti = -1, bestlen = 0,
 222		end = XFS_BLOCKTOBIT(mp, bbno + 1) - 1;
 223	     i <= end;
 224	     i++) {
 225		/*
 226		 * See if there's a free extent of maxlen starting at i.
 227		 * If it's not so then next will contain the first non-free.
 228		 */
 229		error = xfs_rtcheck_range(mp, tp, i, maxlen, 1, &next, &stat);
 230		if (error) {
 231			return error;
 232		}
 233		if (stat) {
 234			/*
 235			 * i for maxlen is all free, allocate and return that.
 236			 */
 237			error = xfs_rtallocate_range(mp, tp, i, maxlen, rbpp,
 238				rsb);
 239			if (error) {
 240				return error;
 241			}
 242			*len = maxlen;
 243			*rtblock = i;
 244			return 0;
 245		}
 246		/*
 247		 * In the case where we have a variable-sized allocation
 248		 * request, figure out how big this free piece is,
 249		 * and if it's big enough for the minimum, and the best
 250		 * so far, remember it.
 251		 */
 252		if (minlen < maxlen) {
 253			xfs_rtblock_t	thislen;	/* this extent size */
 254
 255			thislen = next - i;
 256			if (thislen >= minlen && thislen > bestlen) {
 257				besti = i;
 258				bestlen = thislen;
 259			}
 260		}
 261		/*
 262		 * If not done yet, find the start of the next free space.
 263		 */
 264		if (next < end) {
 265			error = xfs_rtfind_forw(mp, tp, next, end, &i);
 266			if (error) {
 267				return error;
 268			}
 269		} else
 270			break;
 271	}
 272	/*
 273	 * Searched the whole thing & didn't find a maxlen free extent.
 274	 */
 275	if (minlen < maxlen && besti != -1) {
 276		xfs_extlen_t	p;	/* amount to trim length by */
 277
 278		/*
 279		 * If size should be a multiple of prod, make that so.
 280		 */
 281		if (prod > 1 && (p = do_mod(bestlen, prod)))
 282			bestlen -= p;
 283		/*
 284		 * Allocate besti for bestlen & return that.
 285		 */
 286		error = xfs_rtallocate_range(mp, tp, besti, bestlen, rbpp, rsb);
 287		if (error) {
 288			return error;
 289		}
 290		*len = bestlen;
 291		*rtblock = besti;
 292		return 0;
 293	}
 294	/*
 295	 * Allocation failed.  Set *nextp to the next block to try.
 296	 */
 297	*nextp = next;
 298	*rtblock = NULLRTBLOCK;
 299	return 0;
 300}
 301
 302/*
 303 * Allocate an extent of length minlen<=len<=maxlen, starting at block
 304 * bno.  If we don't get maxlen then use prod to trim the length, if given.
 305 * Returns error; returns starting block in *rtblock.
 306 * The lengths are all in rtextents.
 307 */
 308STATIC int				/* error */
 309xfs_rtallocate_extent_exact(
 310	xfs_mount_t	*mp,		/* file system mount point */
 311	xfs_trans_t	*tp,		/* transaction pointer */
 312	xfs_rtblock_t	bno,		/* starting block number to allocate */
 313	xfs_extlen_t	minlen,		/* minimum length to allocate */
 314	xfs_extlen_t	maxlen,		/* maximum length to allocate */
 315	xfs_extlen_t	*len,		/* out: actual length allocated */
 316	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
 317	xfs_fsblock_t	*rsb,		/* in/out: summary block number */
 318	xfs_extlen_t	prod,		/* extent product factor */
 319	xfs_rtblock_t	*rtblock)	/* out: start block allocated */
 320{
 321	int		error;		/* error value */
 322	xfs_extlen_t	i;		/* extent length trimmed due to prod */
 323	int		isfree;		/* extent is free */
 324	xfs_rtblock_t	next;		/* next block to try (dummy) */
 325
 326	ASSERT(minlen % prod == 0 && maxlen % prod == 0);
 327	/*
 328	 * Check if the range in question (for maxlen) is free.
 329	 */
 330	error = xfs_rtcheck_range(mp, tp, bno, maxlen, 1, &next, &isfree);
 331	if (error) {
 332		return error;
 333	}
 334	if (isfree) {
 335		/*
 336		 * If it is, allocate it and return success.
 337		 */
 338		error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb);
 339		if (error) {
 340			return error;
 341		}
 342		*len = maxlen;
 343		*rtblock = bno;
 344		return 0;
 345	}
 346	/*
 347	 * If not, allocate what there is, if it's at least minlen.
 348	 */
 349	maxlen = next - bno;
 350	if (maxlen < minlen) {
 351		/*
 352		 * Failed, return failure status.
 353		 */
 354		*rtblock = NULLRTBLOCK;
 355		return 0;
 356	}
 357	/*
 358	 * Trim off tail of extent, if prod is specified.
 359	 */
 360	if (prod > 1 && (i = maxlen % prod)) {
 361		maxlen -= i;
 362		if (maxlen < minlen) {
 363			/*
 364			 * Now we can't do it, return failure status.
 365			 */
 366			*rtblock = NULLRTBLOCK;
 367			return 0;
 368		}
 369	}
 370	/*
 371	 * Allocate what we can and return it.
 372	 */
 373	error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb);
 374	if (error) {
 375		return error;
 376	}
 377	*len = maxlen;
 378	*rtblock = bno;
 379	return 0;
 380}
 381
 382/*
 383 * Allocate an extent of length minlen<=len<=maxlen, starting as near
 384 * to bno as possible.  If we don't get maxlen then use prod to trim
 385 * the length, if given.  The lengths are all in rtextents.
 386 */
 387STATIC int				/* error */
 388xfs_rtallocate_extent_near(
 389	xfs_mount_t	*mp,		/* file system mount point */
 390	xfs_trans_t	*tp,		/* transaction pointer */
 391	xfs_rtblock_t	bno,		/* starting block number to allocate */
 392	xfs_extlen_t	minlen,		/* minimum length to allocate */
 393	xfs_extlen_t	maxlen,		/* maximum length to allocate */
 394	xfs_extlen_t	*len,		/* out: actual length allocated */
 395	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
 396	xfs_fsblock_t	*rsb,		/* in/out: summary block number */
 397	xfs_extlen_t	prod,		/* extent product factor */
 398	xfs_rtblock_t	*rtblock)	/* out: start block allocated */
 399{
 400	int		any;		/* any useful extents from summary */
 401	xfs_rtblock_t	bbno;		/* bitmap block number */
 402	int		error;		/* error value */
 403	int		i;		/* bitmap block offset (loop control) */
 404	int		j;		/* secondary loop control */
 405	int		log2len;	/* log2 of minlen */
 406	xfs_rtblock_t	n;		/* next block to try */
 407	xfs_rtblock_t	r;		/* result block */
 408
 409	ASSERT(minlen % prod == 0 && maxlen % prod == 0);
 410	/*
 411	 * If the block number given is off the end, silently set it to
 412	 * the last block.
 413	 */
 414	if (bno >= mp->m_sb.sb_rextents)
 415		bno = mp->m_sb.sb_rextents - 1;
 416	/*
 417	 * Try the exact allocation first.
 418	 */
 419	error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen, len,
 420		rbpp, rsb, prod, &r);
 421	if (error) {
 422		return error;
 423	}
 424	/*
 425	 * If the exact allocation worked, return that.
 426	 */
 427	if (r != NULLRTBLOCK) {
 428		*rtblock = r;
 429		return 0;
 430	}
 431	bbno = XFS_BITTOBLOCK(mp, bno);
 432	i = 0;
 433	ASSERT(minlen != 0);
 434	log2len = xfs_highbit32(minlen);
 435	/*
 436	 * Loop over all bitmap blocks (bbno + i is current block).
 437	 */
 438	for (;;) {
 439		/*
 440		 * Get summary information of extents of all useful levels
 441		 * starting in this bitmap block.
 442		 */
 443		error = xfs_rtany_summary(mp, tp, log2len, mp->m_rsumlevels - 1,
 444			bbno + i, rbpp, rsb, &any);
 445		if (error) {
 446			return error;
 447		}
 448		/*
 449		 * If there are any useful extents starting here, try
 450		 * allocating one.
 451		 */
 452		if (any) {
 453			/*
 454			 * On the positive side of the starting location.
 455			 */
 456			if (i >= 0) {
 457				/*
 458				 * Try to allocate an extent starting in
 459				 * this block.
 460				 */
 461				error = xfs_rtallocate_extent_block(mp, tp,
 462					bbno + i, minlen, maxlen, len, &n, rbpp,
 463					rsb, prod, &r);
 464				if (error) {
 465					return error;
 466				}
 467				/*
 468				 * If it worked, return it.
 469				 */
 470				if (r != NULLRTBLOCK) {
 471					*rtblock = r;
 472					return 0;
 473				}
 474			}
 475			/*
 476			 * On the negative side of the starting location.
 477			 */
 478			else {		/* i < 0 */
 479				/*
 480				 * Loop backwards through the bitmap blocks from
 481				 * the starting point-1 up to where we are now.
 482				 * There should be an extent which ends in this
 483				 * bitmap block and is long enough.
 484				 */
 485				for (j = -1; j > i; j--) {
 486					/*
 487					 * Grab the summary information for
 488					 * this bitmap block.
 489					 */
 490					error = xfs_rtany_summary(mp, tp,
 491						log2len, mp->m_rsumlevels - 1,
 492						bbno + j, rbpp, rsb, &any);
 493					if (error) {
 494						return error;
 495					}
 496					/*
 497					 * If there's no extent given in the
 498					 * summary that means the extent we
 499					 * found must carry over from an
 500					 * earlier block.  If there is an
 501					 * extent given, we've already tried
 502					 * that allocation, don't do it again.
 503					 */
 504					if (any)
 505						continue;
 506					error = xfs_rtallocate_extent_block(mp,
 507						tp, bbno + j, minlen, maxlen,
 508						len, &n, rbpp, rsb, prod, &r);
 509					if (error) {
 510						return error;
 511					}
 512					/*
 513					 * If it works, return the extent.
 514					 */
 515					if (r != NULLRTBLOCK) {
 516						*rtblock = r;
 517						return 0;
 518					}
 519				}
 520				/*
 521				 * There weren't intervening bitmap blocks
 522				 * with a long enough extent, or the
 523				 * allocation didn't work for some reason
 524				 * (i.e. it's a little * too short).
 525				 * Try to allocate from the summary block
 526				 * that we found.
 527				 */
 528				error = xfs_rtallocate_extent_block(mp, tp,
 529					bbno + i, minlen, maxlen, len, &n, rbpp,
 530					rsb, prod, &r);
 531				if (error) {
 532					return error;
 533				}
 534				/*
 535				 * If it works, return the extent.
 536				 */
 537				if (r != NULLRTBLOCK) {
 538					*rtblock = r;
 539					return 0;
 540				}
 541			}
 542		}
 543		/*
 544		 * Loop control.  If we were on the positive side, and there's
 545		 * still more blocks on the negative side, go there.
 546		 */
 547		if (i > 0 && (int)bbno - i >= 0)
 548			i = -i;
 549		/*
 550		 * If positive, and no more negative, but there are more
 551		 * positive, go there.
 552		 */
 553		else if (i > 0 && (int)bbno + i < mp->m_sb.sb_rbmblocks - 1)
 554			i++;
 555		/*
 556		 * If negative or 0 (just started), and there are positive
 557		 * blocks to go, go there.  The 0 case moves to block 1.
 558		 */
 559		else if (i <= 0 && (int)bbno - i < mp->m_sb.sb_rbmblocks - 1)
 560			i = 1 - i;
 561		/*
 562		 * If negative or 0 and there are more negative blocks,
 563		 * go there.
 564		 */
 565		else if (i <= 0 && (int)bbno + i > 0)
 566			i--;
 567		/*
 568		 * Must be done.  Return failure.
 569		 */
 570		else
 571			break;
 572	}
 573	*rtblock = NULLRTBLOCK;
 574	return 0;
 575}
 576
 577/*
 578 * Allocate an extent of length minlen<=len<=maxlen, with no position
 579 * specified.  If we don't get maxlen then use prod to trim
 580 * the length, if given.  The lengths are all in rtextents.
 581 */
 582STATIC int				/* error */
 583xfs_rtallocate_extent_size(
 584	xfs_mount_t	*mp,		/* file system mount point */
 585	xfs_trans_t	*tp,		/* transaction pointer */
 586	xfs_extlen_t	minlen,		/* minimum length to allocate */
 587	xfs_extlen_t	maxlen,		/* maximum length to allocate */
 588	xfs_extlen_t	*len,		/* out: actual length allocated */
 589	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
 590	xfs_fsblock_t	*rsb,		/* in/out: summary block number */
 591	xfs_extlen_t	prod,		/* extent product factor */
 592	xfs_rtblock_t	*rtblock)	/* out: start block allocated */
 593{
 594	int		error;		/* error value */
 595	int		i;		/* bitmap block number */
 596	int		l;		/* level number (loop control) */
 597	xfs_rtblock_t	n;		/* next block to be tried */
 598	xfs_rtblock_t	r;		/* result block number */
 599	xfs_suminfo_t	sum;		/* summary information for extents */
 600
 601	ASSERT(minlen % prod == 0 && maxlen % prod == 0);
 602	ASSERT(maxlen != 0);
 603
 604	/*
 605	 * Loop over all the levels starting with maxlen.
 606	 * At each level, look at all the bitmap blocks, to see if there
 607	 * are extents starting there that are long enough (>= maxlen).
 608	 * Note, only on the initial level can the allocation fail if
 609	 * the summary says there's an extent.
 610	 */
 611	for (l = xfs_highbit32(maxlen); l < mp->m_rsumlevels; l++) {
 612		/*
 613		 * Loop over all the bitmap blocks.
 614		 */
 615		for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
 616			/*
 617			 * Get the summary for this level/block.
 618			 */
 619			error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb,
 620				&sum);
 621			if (error) {
 622				return error;
 623			}
 624			/*
 625			 * Nothing there, on to the next block.
 626			 */
 627			if (!sum)
 628				continue;
 629			/*
 630			 * Try allocating the extent.
 631			 */
 632			error = xfs_rtallocate_extent_block(mp, tp, i, maxlen,
 633				maxlen, len, &n, rbpp, rsb, prod, &r);
 634			if (error) {
 635				return error;
 636			}
 637			/*
 638			 * If it worked, return that.
 639			 */
 640			if (r != NULLRTBLOCK) {
 641				*rtblock = r;
 642				return 0;
 643			}
 644			/*
 645			 * If the "next block to try" returned from the
 646			 * allocator is beyond the next bitmap block,
 647			 * skip to that bitmap block.
 648			 */
 649			if (XFS_BITTOBLOCK(mp, n) > i + 1)
 650				i = XFS_BITTOBLOCK(mp, n) - 1;
 651		}
 652	}
 653	/*
 654	 * Didn't find any maxlen blocks.  Try smaller ones, unless
 655	 * we're asking for a fixed size extent.
 656	 */
 657	if (minlen > --maxlen) {
 658		*rtblock = NULLRTBLOCK;
 659		return 0;
 660	}
 661	ASSERT(minlen != 0);
 662	ASSERT(maxlen != 0);
 663
 664	/*
 665	 * Loop over sizes, from maxlen down to minlen.
 666	 * This time, when we do the allocations, allow smaller ones
 667	 * to succeed.
 668	 */
 669	for (l = xfs_highbit32(maxlen); l >= xfs_highbit32(minlen); l--) {
 670		/*
 671		 * Loop over all the bitmap blocks, try an allocation
 672		 * starting in that block.
 673		 */
 674		for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
 675			/*
 676			 * Get the summary information for this level/block.
 677			 */
 678			error =	xfs_rtget_summary(mp, tp, l, i, rbpp, rsb,
 679						  &sum);
 680			if (error) {
 681				return error;
 682			}
 683			/*
 684			 * If nothing there, go on to next.
 685			 */
 686			if (!sum)
 687				continue;
 688			/*
 689			 * Try the allocation.  Make sure the specified
 690			 * minlen/maxlen are in the possible range for
 691			 * this summary level.
 692			 */
 693			error = xfs_rtallocate_extent_block(mp, tp, i,
 694					XFS_RTMAX(minlen, 1 << l),
 695					XFS_RTMIN(maxlen, (1 << (l + 1)) - 1),
 696					len, &n, rbpp, rsb, prod, &r);
 697			if (error) {
 698				return error;
 699			}
 700			/*
 701			 * If it worked, return that extent.
 702			 */
 703			if (r != NULLRTBLOCK) {
 704				*rtblock = r;
 705				return 0;
 706			}
 707			/*
 708			 * If the "next block to try" returned from the
 709			 * allocator is beyond the next bitmap block,
 710			 * skip to that bitmap block.
 711			 */
 712			if (XFS_BITTOBLOCK(mp, n) > i + 1)
 713				i = XFS_BITTOBLOCK(mp, n) - 1;
 714		}
 715	}
 716	/*
 717	 * Got nothing, return failure.
 718	 */
 719	*rtblock = NULLRTBLOCK;
 720	return 0;
 721}
 722
 723/*
 724 * Mark an extent specified by start and len allocated.
 725 * Updates all the summary information as well as the bitmap.
 726 */
 727STATIC int				/* error */
 728xfs_rtallocate_range(
 729	xfs_mount_t	*mp,		/* file system mount point */
 730	xfs_trans_t	*tp,		/* transaction pointer */
 731	xfs_rtblock_t	start,		/* start block to allocate */
 732	xfs_extlen_t	len,		/* length to allocate */
 733	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
 734	xfs_fsblock_t	*rsb)		/* in/out: summary block number */
 735{
 736	xfs_rtblock_t	end;		/* end of the allocated extent */
 737	int		error;		/* error value */
 738	xfs_rtblock_t	postblock;	/* first block allocated > end */
 739	xfs_rtblock_t	preblock;	/* first block allocated < start */
 
 
 
 
 
 
 
 740
 741	end = start + len - 1;
 742	/*
 743	 * Assume we're allocating out of the middle of a free extent.
 744	 * We need to find the beginning and end of the extent so we can
 745	 * properly update the summary.
 746	 */
 747	error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
 748	if (error) {
 749		return error;
 750	}
 751	/*
 752	 * Find the next allocated block (end of free extent).
 753	 */
 754	error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
 755		&postblock);
 756	if (error) {
 757		return error;
 758	}
 759	/*
 760	 * Decrement the summary information corresponding to the entire
 761	 * (old) free extent.
 762	 */
 763	error = xfs_rtmodify_summary(mp, tp,
 764		XFS_RTBLOCKLOG(postblock + 1 - preblock),
 765		XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
 766	if (error) {
 767		return error;
 768	}
 769	/*
 770	 * If there are blocks not being allocated at the front of the
 771	 * old extent, add summary data for them to be free.
 772	 */
 773	if (preblock < start) {
 774		error = xfs_rtmodify_summary(mp, tp,
 775			XFS_RTBLOCKLOG(start - preblock),
 776			XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
 777		if (error) {
 778			return error;
 779		}
 780	}
 781	/*
 782	 * If there are blocks not being allocated at the end of the
 783	 * old extent, add summary data for them to be free.
 784	 */
 785	if (postblock > end) {
 786		error = xfs_rtmodify_summary(mp, tp,
 787			XFS_RTBLOCKLOG(postblock - end),
 788			XFS_BITTOBLOCK(mp, end + 1), 1, rbpp, rsb);
 789		if (error) {
 790			return error;
 791		}
 792	}
 793	/*
 794	 * Modify the bitmap to mark this extent allocated.
 795	 */
 796	error = xfs_rtmodify_range(mp, tp, start, len, 0);
 797	return error;
 798}
 799
 800/*
 801 * Return whether there are any free extents in the size range given
 802 * by low and high, for the bitmap block bbno.
 803 */
 804STATIC int				/* error */
 805xfs_rtany_summary(
 806	xfs_mount_t	*mp,		/* file system mount structure */
 807	xfs_trans_t	*tp,		/* transaction pointer */
 808	int		low,		/* low log2 extent size */
 809	int		high,		/* high log2 extent size */
 810	xfs_rtblock_t	bbno,		/* bitmap block number */
 811	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
 812	xfs_fsblock_t	*rsb,		/* in/out: summary block number */
 813	int		*stat)		/* out: any good extents here? */
 814{
 815	int		error;		/* error value */
 816	int		log;		/* loop counter, log2 of ext. size */
 817	xfs_suminfo_t	sum;		/* summary data */
 818
 819	/*
 820	 * Loop over logs of extent sizes.  Order is irrelevant.
 821	 */
 822	for (log = low; log <= high; log++) {
 823		/*
 824		 * Get one summary datum.
 825		 */
 826		error = xfs_rtget_summary(mp, tp, log, bbno, rbpp, rsb, &sum);
 827		if (error) {
 828			return error;
 829		}
 
 830		/*
 831		 * If there are any, return success.
 832		 */
 833		if (sum) {
 834			*stat = 1;
 835			return 0;
 836		}
 837	}
 838	/*
 839	 * Found nothing, return failure.
 840	 */
 841	*stat = 0;
 842	return 0;
 843}
 844
 845/*
 846 * Get a buffer for the bitmap or summary file block specified.
 847 * The buffer is returned read and locked.
 848 */
 849STATIC int				/* error */
 850xfs_rtbuf_get(
 851	xfs_mount_t	*mp,		/* file system mount structure */
 852	xfs_trans_t	*tp,		/* transaction pointer */
 853	xfs_rtblock_t	block,		/* block number in bitmap or summary */
 854	int		issum,		/* is summary not bitmap */
 855	xfs_buf_t	**bpp)		/* output: buffer for the block */
 856{
 857	xfs_buf_t	*bp;		/* block buffer, result */
 858	xfs_inode_t	*ip;		/* bitmap or summary inode */
 859	xfs_bmbt_irec_t	map;
 860	int		nmap;
 861	int		error;		/* error value */
 862
 863	ip = issum ? mp->m_rsumip : mp->m_rbmip;
 864
 865	error = xfs_bmapi_read(ip, block, 1, &map, &nmap, XFS_DATA_FORK);
 866	if (error)
 867		return error;
 868
 869	ASSERT(map.br_startblock != NULLFSBLOCK);
 870	error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
 871				   XFS_FSB_TO_DADDR(mp, map.br_startblock),
 872				   mp->m_bsize, 0, &bp);
 873	if (error)
 874		return error;
 875	ASSERT(!xfs_buf_geterror(bp));
 876	*bpp = bp;
 877	return 0;
 878}
 879
 880#ifdef DEBUG
 881/*
 882 * Check that the given extent (block range) is allocated already.
 883 */
 884STATIC int				/* error */
 885xfs_rtcheck_alloc_range(
 886	xfs_mount_t	*mp,		/* file system mount point */
 887	xfs_trans_t	*tp,		/* transaction pointer */
 888	xfs_rtblock_t	bno,		/* starting block number of extent */
 889	xfs_extlen_t	len,		/* length of extent */
 890	int		*stat)		/* out: 1 for allocated, 0 for not */
 891{
 892	xfs_rtblock_t	new;		/* dummy for xfs_rtcheck_range */
 893
 894	return xfs_rtcheck_range(mp, tp, bno, len, 0, &new, stat);
 895}
 896#endif
 897
 898/*
 899 * Check that the given range is either all allocated (val = 0) or
 900 * all free (val = 1).
 901 */
 902STATIC int				/* error */
 903xfs_rtcheck_range(
 904	xfs_mount_t	*mp,		/* file system mount point */
 905	xfs_trans_t	*tp,		/* transaction pointer */
 906	xfs_rtblock_t	start,		/* starting block number of extent */
 907	xfs_extlen_t	len,		/* length of extent */
 908	int		val,		/* 1 for free, 0 for allocated */
 909	xfs_rtblock_t	*new,		/* out: first block not matching */
 910	int		*stat)		/* out: 1 for matches, 0 for not */
 911{
 912	xfs_rtword_t	*b;		/* current word in buffer */
 913	int		bit;		/* bit number in the word */
 914	xfs_rtblock_t	block;		/* bitmap block number */
 915	xfs_buf_t	*bp;		/* buf for the block */
 916	xfs_rtword_t	*bufp;		/* starting word in buffer */
 917	int		error;		/* error value */
 918	xfs_rtblock_t	i;		/* current bit number rel. to start */
 919	xfs_rtblock_t	lastbit;	/* last useful bit in word */
 920	xfs_rtword_t	mask;		/* mask of relevant bits for value */
 921	xfs_rtword_t	wdiff;		/* difference from wanted value */
 922	int		word;		/* word number in the buffer */
 923
 924	/*
 925	 * Compute starting bitmap block number
 926	 */
 927	block = XFS_BITTOBLOCK(mp, start);
 928	/*
 929	 * Read the bitmap block.
 930	 */
 931	error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
 932	if (error) {
 933		return error;
 934	}
 935	bufp = bp->b_addr;
 936	/*
 937	 * Compute the starting word's address, and starting bit.
 938	 */
 939	word = XFS_BITTOWORD(mp, start);
 940	b = &bufp[word];
 941	bit = (int)(start & (XFS_NBWORD - 1));
 942	/*
 943	 * 0 (allocated) => all zero's; 1 (free) => all one's.
 944	 */
 945	val = -val;
 946	/*
 947	 * If not starting on a word boundary, deal with the first
 948	 * (partial) word.
 949	 */
 950	if (bit) {
 951		/*
 952		 * Compute first bit not examined.
 953		 */
 954		lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
 955		/*
 956		 * Mask of relevant bits.
 957		 */
 958		mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
 959		/*
 960		 * Compute difference between actual and desired value.
 961		 */
 962		if ((wdiff = (*b ^ val) & mask)) {
 963			/*
 964			 * Different, compute first wrong bit and return.
 965			 */
 966			xfs_trans_brelse(tp, bp);
 967			i = XFS_RTLOBIT(wdiff) - bit;
 968			*new = start + i;
 969			*stat = 0;
 970			return 0;
 971		}
 972		i = lastbit - bit;
 973		/*
 974		 * Go on to next block if that's where the next word is
 975		 * and we need the next word.
 976		 */
 977		if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
 978			/*
 979			 * If done with this block, get the next one.
 980			 */
 981			xfs_trans_brelse(tp, bp);
 982			error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
 983			if (error) {
 984				return error;
 985			}
 986			b = bufp = bp->b_addr;
 987			word = 0;
 988		} else {
 989			/*
 990			 * Go on to the next word in the buffer.
 991			 */
 992			b++;
 993		}
 994	} else {
 995		/*
 996		 * Starting on a word boundary, no partial word.
 997		 */
 998		i = 0;
 999	}
1000	/*
1001	 * Loop over whole words in buffers.  When we use up one buffer
1002	 * we move on to the next one.
1003	 */
1004	while (len - i >= XFS_NBWORD) {
1005		/*
1006		 * Compute difference between actual and desired value.
1007		 */
1008		if ((wdiff = *b ^ val)) {
1009			/*
1010			 * Different, compute first wrong bit and return.
1011			 */
1012			xfs_trans_brelse(tp, bp);
1013			i += XFS_RTLOBIT(wdiff);
1014			*new = start + i;
1015			*stat = 0;
1016			return 0;
1017		}
1018		i += XFS_NBWORD;
1019		/*
1020		 * Go on to next block if that's where the next word is
1021		 * and we need the next word.
1022		 */
1023		if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1024			/*
1025			 * If done with this block, get the next one.
1026			 */
1027			xfs_trans_brelse(tp, bp);
1028			error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1029			if (error) {
1030				return error;
1031			}
1032			b = bufp = bp->b_addr;
1033			word = 0;
1034		} else {
1035			/*
1036			 * Go on to the next word in the buffer.
1037			 */
1038			b++;
1039		}
1040	}
1041	/*
1042	 * If not ending on a word boundary, deal with the last
1043	 * (partial) word.
1044	 */
1045	if ((lastbit = len - i)) {
1046		/*
1047		 * Mask of relevant bits.
1048		 */
1049		mask = ((xfs_rtword_t)1 << lastbit) - 1;
 
 
 
 
 
1050		/*
1051		 * Compute difference between actual and desired value.
 
1052		 */
1053		if ((wdiff = (*b ^ val) & mask)) {
 
 
 
 
1054			/*
1055			 * Different, compute first wrong bit and return.
1056			 */
1057			xfs_trans_brelse(tp, bp);
1058			i += XFS_RTLOBIT(wdiff);
1059			*new = start + i;
1060			*stat = 0;
1061			return 0;
1062		} else
1063			i = len;
1064	}
1065	/*
1066	 * Successful, return.
1067	 */
1068	xfs_trans_brelse(tp, bp);
1069	*new = start + i;
1070	*stat = 1;
1071	return 0;
1072}
1073
1074/*
1075 * Copy and transform the summary file, given the old and new
1076 * parameters in the mount structures.
1077 */
1078STATIC int				/* error */
1079xfs_rtcopy_summary(
1080	xfs_mount_t	*omp,		/* old file system mount point */
1081	xfs_mount_t	*nmp,		/* new file system mount point */
1082	xfs_trans_t	*tp)		/* transaction pointer */
1083{
1084	xfs_rtblock_t	bbno;		/* bitmap block number */
1085	xfs_buf_t	*bp;		/* summary buffer */
1086	int		error;		/* error return value */
1087	int		log;		/* summary level number (log length) */
1088	xfs_suminfo_t	sum;		/* summary data */
1089	xfs_fsblock_t	sumbno;		/* summary block number */
1090
1091	bp = NULL;
1092	for (log = omp->m_rsumlevels - 1; log >= 0; log--) {
1093		for (bbno = omp->m_sb.sb_rbmblocks - 1;
1094		     (xfs_srtblock_t)bbno >= 0;
1095		     bbno--) {
1096			error = xfs_rtget_summary(omp, tp, log, bbno, &bp,
1097				&sumbno, &sum);
1098			if (error)
1099				return error;
1100			if (sum == 0)
1101				continue;
1102			error = xfs_rtmodify_summary(omp, tp, log, bbno, -sum,
1103				&bp, &sumbno);
1104			if (error)
1105				return error;
1106			error = xfs_rtmodify_summary(nmp, tp, log, bbno, sum,
1107				&bp, &sumbno);
1108			if (error)
1109				return error;
1110			ASSERT(sum > 0);
1111		}
1112	}
1113	return 0;
1114}
1115
1116/*
1117 * Searching backward from start to limit, find the first block whose
1118 * allocated/free state is different from start's.
1119 */
1120STATIC int				/* error */
1121xfs_rtfind_back(
1122	xfs_mount_t	*mp,		/* file system mount point */
1123	xfs_trans_t	*tp,		/* transaction pointer */
1124	xfs_rtblock_t	start,		/* starting block to look at */
1125	xfs_rtblock_t	limit,		/* last block to look at */
1126	xfs_rtblock_t	*rtblock)	/* out: start block found */
1127{
1128	xfs_rtword_t	*b;		/* current word in buffer */
1129	int		bit;		/* bit number in the word */
1130	xfs_rtblock_t	block;		/* bitmap block number */
1131	xfs_buf_t	*bp;		/* buf for the block */
1132	xfs_rtword_t	*bufp;		/* starting word in buffer */
1133	int		error;		/* error value */
1134	xfs_rtblock_t	firstbit;	/* first useful bit in the word */
1135	xfs_rtblock_t	i;		/* current bit number rel. to start */
1136	xfs_rtblock_t	len;		/* length of inspected area */
1137	xfs_rtword_t	mask;		/* mask of relevant bits for value */
1138	xfs_rtword_t	want;		/* mask for "good" values */
1139	xfs_rtword_t	wdiff;		/* difference from wanted value */
1140	int		word;		/* word number in the buffer */
1141
1142	/*
1143	 * Compute and read in starting bitmap block for starting block.
1144	 */
1145	block = XFS_BITTOBLOCK(mp, start);
1146	error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1147	if (error) {
1148		return error;
1149	}
1150	bufp = bp->b_addr;
1151	/*
1152	 * Get the first word's index & point to it.
1153	 */
1154	word = XFS_BITTOWORD(mp, start);
1155	b = &bufp[word];
1156	bit = (int)(start & (XFS_NBWORD - 1));
1157	len = start - limit + 1;
1158	/*
1159	 * Compute match value, based on the bit at start: if 1 (free)
1160	 * then all-ones, else all-zeroes.
1161	 */
1162	want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
1163	/*
1164	 * If the starting position is not word-aligned, deal with the
1165	 * partial word.
1166	 */
1167	if (bit < XFS_NBWORD - 1) {
1168		/*
1169		 * Calculate first (leftmost) bit number to look at,
1170		 * and mask for all the relevant bits in this word.
1171		 */
1172		firstbit = XFS_RTMAX((xfs_srtblock_t)(bit - len + 1), 0);
1173		mask = (((xfs_rtword_t)1 << (bit - firstbit + 1)) - 1) <<
1174			firstbit;
1175		/*
1176		 * Calculate the difference between the value there
1177		 * and what we're looking for.
1178		 */
1179		if ((wdiff = (*b ^ want) & mask)) {
1180			/*
1181			 * Different.  Mark where we are and return.
1182			 */
1183			xfs_trans_brelse(tp, bp);
1184			i = bit - XFS_RTHIBIT(wdiff);
1185			*rtblock = start - i + 1;
1186			return 0;
1187		}
1188		i = bit - firstbit + 1;
1189		/*
1190		 * Go on to previous block if that's where the previous word is
1191		 * and we need the previous word.
1192		 */
1193		if (--word == -1 && i < len) {
1194			/*
1195			 * If done with this block, get the previous one.
1196			 */
1197			xfs_trans_brelse(tp, bp);
1198			error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
1199			if (error) {
1200				return error;
1201			}
1202			bufp = bp->b_addr;
1203			word = XFS_BLOCKWMASK(mp);
1204			b = &bufp[word];
1205		} else {
1206			/*
1207			 * Go on to the previous word in the buffer.
1208			 */
1209			b--;
1210		}
1211	} else {
1212		/*
1213		 * Starting on a word boundary, no partial word.
1214		 */
1215		i = 0;
1216	}
1217	/*
1218	 * Loop over whole words in buffers.  When we use up one buffer
1219	 * we move on to the previous one.
1220	 */
1221	while (len - i >= XFS_NBWORD) {
1222		/*
1223		 * Compute difference between actual and desired value.
1224		 */
1225		if ((wdiff = *b ^ want)) {
1226			/*
1227			 * Different, mark where we are and return.
1228			 */
1229			xfs_trans_brelse(tp, bp);
1230			i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
1231			*rtblock = start - i + 1;
1232			return 0;
1233		}
1234		i += XFS_NBWORD;
1235		/*
1236		 * Go on to previous block if that's where the previous word is
1237		 * and we need the previous word.
1238		 */
1239		if (--word == -1 && i < len) {
1240			/*
1241			 * If done with this block, get the previous one.
1242			 */
1243			xfs_trans_brelse(tp, bp);
1244			error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
1245			if (error) {
1246				return error;
1247			}
1248			bufp = bp->b_addr;
1249			word = XFS_BLOCKWMASK(mp);
1250			b = &bufp[word];
1251		} else {
1252			/*
1253			 * Go on to the previous word in the buffer.
1254			 */
1255			b--;
1256		}
1257	}
1258	/*
1259	 * If not ending on a word boundary, deal with the last
1260	 * (partial) word.
1261	 */
1262	if (len - i) {
1263		/*
1264		 * Calculate first (leftmost) bit number to look at,
1265		 * and mask for all the relevant bits in this word.
1266		 */
1267		firstbit = XFS_NBWORD - (len - i);
1268		mask = (((xfs_rtword_t)1 << (len - i)) - 1) << firstbit;
1269		/*
1270		 * Compute difference between actual and desired value.
1271		 */
1272		if ((wdiff = (*b ^ want) & mask)) {
1273			/*
1274			 * Different, mark where we are and return.
1275			 */
1276			xfs_trans_brelse(tp, bp);
1277			i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
1278			*rtblock = start - i + 1;
1279			return 0;
1280		} else
1281			i = len;
1282	}
1283	/*
1284	 * No match, return that we scanned the whole area.
1285	 */
1286	xfs_trans_brelse(tp, bp);
1287	*rtblock = start - i + 1;
1288	return 0;
1289}
1290
1291/*
1292 * Searching forward from start to limit, find the first block whose
1293 * allocated/free state is different from start's.
1294 */
1295STATIC int				/* error */
1296xfs_rtfind_forw(
1297	xfs_mount_t	*mp,		/* file system mount point */
1298	xfs_trans_t	*tp,		/* transaction pointer */
1299	xfs_rtblock_t	start,		/* starting block to look at */
1300	xfs_rtblock_t	limit,		/* last block to look at */
1301	xfs_rtblock_t	*rtblock)	/* out: start block found */
1302{
1303	xfs_rtword_t	*b;		/* current word in buffer */
1304	int		bit;		/* bit number in the word */
1305	xfs_rtblock_t	block;		/* bitmap block number */
1306	xfs_buf_t	*bp;		/* buf for the block */
1307	xfs_rtword_t	*bufp;		/* starting word in buffer */
1308	int		error;		/* error value */
1309	xfs_rtblock_t	i;		/* current bit number rel. to start */
1310	xfs_rtblock_t	lastbit;	/* last useful bit in the word */
1311	xfs_rtblock_t	len;		/* length of inspected area */
1312	xfs_rtword_t	mask;		/* mask of relevant bits for value */
1313	xfs_rtword_t	want;		/* mask for "good" values */
1314	xfs_rtword_t	wdiff;		/* difference from wanted value */
1315	int		word;		/* word number in the buffer */
1316
1317	/*
1318	 * Compute and read in starting bitmap block for starting block.
1319	 */
1320	block = XFS_BITTOBLOCK(mp, start);
1321	error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1322	if (error) {
1323		return error;
1324	}
1325	bufp = bp->b_addr;
1326	/*
1327	 * Get the first word's index & point to it.
1328	 */
1329	word = XFS_BITTOWORD(mp, start);
1330	b = &bufp[word];
1331	bit = (int)(start & (XFS_NBWORD - 1));
1332	len = limit - start + 1;
1333	/*
1334	 * Compute match value, based on the bit at start: if 1 (free)
1335	 * then all-ones, else all-zeroes.
1336	 */
1337	want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
1338	/*
1339	 * If the starting position is not word-aligned, deal with the
1340	 * partial word.
1341	 */
1342	if (bit) {
1343		/*
1344		 * Calculate last (rightmost) bit number to look at,
1345		 * and mask for all the relevant bits in this word.
1346		 */
1347		lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1348		mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1349		/*
1350		 * Calculate the difference between the value there
1351		 * and what we're looking for.
1352		 */
1353		if ((wdiff = (*b ^ want) & mask)) {
1354			/*
1355			 * Different.  Mark where we are and return.
1356			 */
1357			xfs_trans_brelse(tp, bp);
1358			i = XFS_RTLOBIT(wdiff) - bit;
1359			*rtblock = start + i - 1;
1360			return 0;
1361		}
1362		i = lastbit - bit;
1363		/*
1364		 * Go on to next block if that's where the next word is
1365		 * and we need the next word.
1366		 */
1367		if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1368			/*
1369			 * If done with this block, get the previous one.
1370			 */
1371			xfs_trans_brelse(tp, bp);
1372			error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1373			if (error) {
1374				return error;
1375			}
1376			b = bufp = bp->b_addr;
1377			word = 0;
1378		} else {
1379			/*
1380			 * Go on to the previous word in the buffer.
1381			 */
1382			b++;
1383		}
1384	} else {
1385		/*
1386		 * Starting on a word boundary, no partial word.
1387		 */
1388		i = 0;
1389	}
1390	/*
1391	 * Loop over whole words in buffers.  When we use up one buffer
1392	 * we move on to the next one.
1393	 */
1394	while (len - i >= XFS_NBWORD) {
1395		/*
1396		 * Compute difference between actual and desired value.
1397		 */
1398		if ((wdiff = *b ^ want)) {
1399			/*
1400			 * Different, mark where we are and return.
1401			 */
1402			xfs_trans_brelse(tp, bp);
1403			i += XFS_RTLOBIT(wdiff);
1404			*rtblock = start + i - 1;
1405			return 0;
1406		}
1407		i += XFS_NBWORD;
1408		/*
1409		 * Go on to next block if that's where the next word is
1410		 * and we need the next word.
1411		 */
1412		if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1413			/*
1414			 * If done with this block, get the next one.
1415			 */
1416			xfs_trans_brelse(tp, bp);
1417			error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1418			if (error) {
1419				return error;
 
 
 
 
1420			}
1421			b = bufp = bp->b_addr;
1422			word = 0;
1423		} else {
1424			/*
1425			 * Go on to the next word in the buffer.
1426			 */
1427			b++;
 
 
1428		}
1429	}
1430	/*
1431	 * If not ending on a word boundary, deal with the last
1432	 * (partial) word.
1433	 */
1434	if ((lastbit = len - i)) {
1435		/*
1436		 * Calculate mask for all the relevant bits in this word.
1437		 */
1438		mask = ((xfs_rtword_t)1 << lastbit) - 1;
1439		/*
1440		 * Compute difference between actual and desired value.
1441		 */
1442		if ((wdiff = (*b ^ want) & mask)) {
1443			/*
1444			 * Different, mark where we are and return.
1445			 */
1446			xfs_trans_brelse(tp, bp);
1447			i += XFS_RTLOBIT(wdiff);
1448			*rtblock = start + i - 1;
1449			return 0;
1450		} else
1451			i = len;
1452	}
1453	/*
1454	 * No match, return that we scanned the whole area.
1455	 */
1456	xfs_trans_brelse(tp, bp);
1457	*rtblock = start + i - 1;
1458	return 0;
1459}
1460
1461/*
1462 * Mark an extent specified by start and len freed.
1463 * Updates all the summary information as well as the bitmap.
1464 */
1465STATIC int				/* error */
1466xfs_rtfree_range(
1467	xfs_mount_t	*mp,		/* file system mount point */
1468	xfs_trans_t	*tp,		/* transaction pointer */
1469	xfs_rtblock_t	start,		/* starting block to free */
1470	xfs_extlen_t	len,		/* length to free */
1471	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
1472	xfs_fsblock_t	*rsb)		/* in/out: summary block number */
1473{
1474	xfs_rtblock_t	end;		/* end of the freed extent */
1475	int		error;		/* error value */
1476	xfs_rtblock_t	postblock;	/* first block freed > end */
1477	xfs_rtblock_t	preblock;	/* first block freed < start */
1478
1479	end = start + len - 1;
1480	/*
1481	 * Modify the bitmap to mark this extent freed.
1482	 */
1483	error = xfs_rtmodify_range(mp, tp, start, len, 1);
1484	if (error) {
1485		return error;
1486	}
1487	/*
1488	 * Assume we're freeing out of the middle of an allocated extent.
1489	 * We need to find the beginning and end of the extent so we can
1490	 * properly update the summary.
1491	 */
1492	error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
1493	if (error) {
1494		return error;
1495	}
1496	/*
1497	 * Find the next allocated block (end of allocated extent).
1498	 */
1499	error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
1500		&postblock);
1501	if (error)
1502		return error;
1503	/*
1504	 * If there are blocks not being freed at the front of the
1505	 * old extent, add summary data for them to be allocated.
1506	 */
1507	if (preblock < start) {
1508		error = xfs_rtmodify_summary(mp, tp,
1509			XFS_RTBLOCKLOG(start - preblock),
1510			XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
1511		if (error) {
1512			return error;
1513		}
1514	}
1515	/*
1516	 * If there are blocks not being freed at the end of the
1517	 * old extent, add summary data for them to be allocated.
1518	 */
1519	if (postblock > end) {
1520		error = xfs_rtmodify_summary(mp, tp,
1521			XFS_RTBLOCKLOG(postblock - end),
1522			XFS_BITTOBLOCK(mp, end + 1), -1, rbpp, rsb);
1523		if (error) {
1524			return error;
1525		}
1526	}
1527	/*
1528	 * Increment the summary information corresponding to the entire
1529	 * (new) free extent.
1530	 */
1531	error = xfs_rtmodify_summary(mp, tp,
1532		XFS_RTBLOCKLOG(postblock + 1 - preblock),
1533		XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
1534	return error;
1535}
1536
1537/*
1538 * Read and return the summary information for a given extent size,
1539 * bitmap block combination.
1540 * Keeps track of a current summary block, so we don't keep reading
1541 * it from the buffer cache.
1542 */
1543STATIC int				/* error */
1544xfs_rtget_summary(
1545	xfs_mount_t	*mp,		/* file system mount structure */
1546	xfs_trans_t	*tp,		/* transaction pointer */
1547	int		log,		/* log2 of extent size */
1548	xfs_rtblock_t	bbno,		/* bitmap block number */
1549	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
1550	xfs_fsblock_t	*rsb,		/* in/out: summary block number */
1551	xfs_suminfo_t	*sum)		/* out: summary info for this block */
1552{
1553	xfs_buf_t	*bp;		/* buffer for summary block */
1554	int		error;		/* error value */
1555	xfs_fsblock_t	sb;		/* summary fsblock */
1556	int		so;		/* index into the summary file */
1557	xfs_suminfo_t	*sp;		/* pointer to returned data */
1558
1559	/*
1560	 * Compute entry number in the summary file.
1561	 */
1562	so = XFS_SUMOFFS(mp, log, bbno);
1563	/*
1564	 * Compute the block number in the summary file.
1565	 */
1566	sb = XFS_SUMOFFSTOBLOCK(mp, so);
1567	/*
1568	 * If we have an old buffer, and the block number matches, use that.
1569	 */
1570	if (rbpp && *rbpp && *rsb == sb)
1571		bp = *rbpp;
1572	/*
1573	 * Otherwise we have to get the buffer.
1574	 */
1575	else {
1576		/*
1577		 * If there was an old one, get rid of it first.
1578		 */
1579		if (rbpp && *rbpp)
1580			xfs_trans_brelse(tp, *rbpp);
1581		error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
1582		if (error) {
1583			return error;
1584		}
1585		/*
1586		 * Remember this buffer and block for the next call.
1587		 */
1588		if (rbpp) {
1589			*rbpp = bp;
1590			*rsb = sb;
1591		}
1592	}
1593	/*
1594	 * Point to the summary information & copy it out.
1595	 */
1596	sp = XFS_SUMPTR(mp, bp, so);
1597	*sum = *sp;
1598	/*
1599	 * Drop the buffer if we're not asked to remember it.
1600	 */
1601	if (!rbpp)
1602		xfs_trans_brelse(tp, bp);
1603	return 0;
1604}
1605
1606/*
1607 * Set the given range of bitmap bits to the given value.
1608 * Do whatever I/O and logging is required.
1609 */
1610STATIC int				/* error */
1611xfs_rtmodify_range(
1612	xfs_mount_t	*mp,		/* file system mount point */
1613	xfs_trans_t	*tp,		/* transaction pointer */
1614	xfs_rtblock_t	start,		/* starting block to modify */
1615	xfs_extlen_t	len,		/* length of extent to modify */
1616	int		val)		/* 1 for free, 0 for allocated */
1617{
1618	xfs_rtword_t	*b;		/* current word in buffer */
1619	int		bit;		/* bit number in the word */
1620	xfs_rtblock_t	block;		/* bitmap block number */
1621	xfs_buf_t	*bp;		/* buf for the block */
1622	xfs_rtword_t	*bufp;		/* starting word in buffer */
1623	int		error;		/* error value */
1624	xfs_rtword_t	*first;		/* first used word in the buffer */
1625	int		i;		/* current bit number rel. to start */
1626	int		lastbit;	/* last useful bit in word */
1627	xfs_rtword_t	mask;		/* mask o frelevant bits for value */
1628	int		word;		/* word number in the buffer */
1629
1630	/*
1631	 * Compute starting bitmap block number.
1632	 */
1633	block = XFS_BITTOBLOCK(mp, start);
1634	/*
1635	 * Read the bitmap block, and point to its data.
1636	 */
1637	error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1638	if (error) {
1639		return error;
1640	}
1641	bufp = bp->b_addr;
1642	/*
1643	 * Compute the starting word's address, and starting bit.
1644	 */
1645	word = XFS_BITTOWORD(mp, start);
1646	first = b = &bufp[word];
1647	bit = (int)(start & (XFS_NBWORD - 1));
1648	/*
1649	 * 0 (allocated) => all zeroes; 1 (free) => all ones.
1650	 */
1651	val = -val;
1652	/*
1653	 * If not starting on a word boundary, deal with the first
1654	 * (partial) word.
1655	 */
1656	if (bit) {
1657		/*
1658		 * Compute first bit not changed and mask of relevant bits.
1659		 */
1660		lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1661		mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1662		/*
1663		 * Set/clear the active bits.
1664		 */
1665		if (val)
1666			*b |= mask;
1667		else
1668			*b &= ~mask;
1669		i = lastbit - bit;
1670		/*
1671		 * Go on to the next block if that's where the next word is
1672		 * and we need the next word.
1673		 */
1674		if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1675			/*
1676			 * Log the changed part of this block.
1677			 * Get the next one.
1678			 */
1679			xfs_trans_log_buf(tp, bp,
1680				(uint)((char *)first - (char *)bufp),
1681				(uint)((char *)b - (char *)bufp));
1682			error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1683			if (error) {
1684				return error;
1685			}
1686			first = b = bufp = bp->b_addr;
1687			word = 0;
1688		} else {
1689			/*
1690			 * Go on to the next word in the buffer
1691			 */
1692			b++;
1693		}
1694	} else {
1695		/*
1696		 * Starting on a word boundary, no partial word.
1697		 */
1698		i = 0;
1699	}
1700	/*
1701	 * Loop over whole words in buffers.  When we use up one buffer
1702	 * we move on to the next one.
1703	 */
1704	while (len - i >= XFS_NBWORD) {
1705		/*
1706		 * Set the word value correctly.
1707		 */
1708		*b = val;
1709		i += XFS_NBWORD;
1710		/*
1711		 * Go on to the next block if that's where the next word is
1712		 * and we need the next word.
1713		 */
1714		if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1715			/*
1716			 * Log the changed part of this block.
1717			 * Get the next one.
1718			 */
1719			xfs_trans_log_buf(tp, bp,
1720				(uint)((char *)first - (char *)bufp),
1721				(uint)((char *)b - (char *)bufp));
1722			error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1723			if (error) {
1724				return error;
1725			}
1726			first = b = bufp = bp->b_addr;
1727			word = 0;
1728		} else {
1729			/*
1730			 * Go on to the next word in the buffer
1731			 */
1732			b++;
1733		}
1734	}
1735	/*
1736	 * If not ending on a word boundary, deal with the last
1737	 * (partial) word.
1738	 */
1739	if ((lastbit = len - i)) {
1740		/*
1741		 * Compute a mask of relevant bits.
1742		 */
1743		bit = 0;
1744		mask = ((xfs_rtword_t)1 << lastbit) - 1;
1745		/*
1746		 * Set/clear the active bits.
1747		 */
1748		if (val)
1749			*b |= mask;
1750		else
1751			*b &= ~mask;
1752		b++;
1753	}
1754	/*
1755	 * Log any remaining changed bytes.
1756	 */
1757	if (b > first)
1758		xfs_trans_log_buf(tp, bp, (uint)((char *)first - (char *)bufp),
1759			(uint)((char *)b - (char *)bufp - 1));
1760	return 0;
1761}
1762
1763/*
1764 * Read and modify the summary information for a given extent size,
1765 * bitmap block combination.
1766 * Keeps track of a current summary block, so we don't keep reading
1767 * it from the buffer cache.
1768 */
1769STATIC int				/* error */
1770xfs_rtmodify_summary(
1771	xfs_mount_t	*mp,		/* file system mount point */
1772	xfs_trans_t	*tp,		/* transaction pointer */
1773	int		log,		/* log2 of extent size */
1774	xfs_rtblock_t	bbno,		/* bitmap block number */
1775	int		delta,		/* change to make to summary info */
1776	xfs_buf_t	**rbpp,		/* in/out: summary block buffer */
1777	xfs_fsblock_t	*rsb)		/* in/out: summary block number */
1778{
1779	xfs_buf_t	*bp;		/* buffer for the summary block */
1780	int		error;		/* error value */
1781	xfs_fsblock_t	sb;		/* summary fsblock */
1782	int		so;		/* index into the summary file */
1783	xfs_suminfo_t	*sp;		/* pointer to returned data */
1784
1785	/*
1786	 * Compute entry number in the summary file.
1787	 */
1788	so = XFS_SUMOFFS(mp, log, bbno);
1789	/*
1790	 * Compute the block number in the summary file.
1791	 */
1792	sb = XFS_SUMOFFSTOBLOCK(mp, so);
1793	/*
1794	 * If we have an old buffer, and the block number matches, use that.
1795	 */
1796	if (rbpp && *rbpp && *rsb == sb)
1797		bp = *rbpp;
1798	/*
1799	 * Otherwise we have to get the buffer.
1800	 */
1801	else {
1802		/*
1803		 * If there was an old one, get rid of it first.
1804		 */
1805		if (rbpp && *rbpp)
1806			xfs_trans_brelse(tp, *rbpp);
1807		error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
1808		if (error) {
1809			return error;
1810		}
1811		/*
1812		 * Remember this buffer and block for the next call.
1813		 */
1814		if (rbpp) {
1815			*rbpp = bp;
1816			*rsb = sb;
1817		}
1818	}
1819	/*
1820	 * Point to the summary information, modify and log it.
1821	 */
1822	sp = XFS_SUMPTR(mp, bp, so);
1823	*sp += delta;
1824	xfs_trans_log_buf(tp, bp, (uint)((char *)sp - (char *)bp->b_addr),
1825		(uint)((char *)sp - (char *)bp->b_addr + sizeof(*sp) - 1));
1826	return 0;
1827}
1828
1829/*
1830 * Visible (exported) functions.
1831 */
1832
1833/*
1834 * Grow the realtime area of the filesystem.
1835 */
1836int
1837xfs_growfs_rt(
1838	xfs_mount_t	*mp,		/* mount point for filesystem */
1839	xfs_growfs_rt_t	*in)		/* growfs rt input struct */
1840{
1841	xfs_rtblock_t	bmbno;		/* bitmap block number */
1842	xfs_buf_t	*bp;		/* temporary buffer */
1843	int		error;		/* error return value */
1844	xfs_mount_t	*nmp;		/* new (fake) mount structure */
1845	xfs_drfsbno_t	nrblocks;	/* new number of realtime blocks */
1846	xfs_extlen_t	nrbmblocks;	/* new number of rt bitmap blocks */
1847	xfs_drtbno_t	nrextents;	/* new number of realtime extents */
1848	uint8_t		nrextslog;	/* new log2 of sb_rextents */
1849	xfs_extlen_t	nrsumblocks;	/* new number of summary blocks */
1850	uint		nrsumlevels;	/* new rt summary levels */
1851	uint		nrsumsize;	/* new size of rt summary, bytes */
1852	xfs_sb_t	*nsbp;		/* new superblock */
1853	xfs_extlen_t	rbmblocks;	/* current number of rt bitmap blocks */
1854	xfs_extlen_t	rsumblocks;	/* current number of rt summary blks */
1855	xfs_sb_t	*sbp;		/* old superblock */
1856	xfs_fsblock_t	sumbno;		/* summary block number */
1857
1858	sbp = &mp->m_sb;
1859	/*
1860	 * Initial error checking.
1861	 */
1862	if (!capable(CAP_SYS_ADMIN))
1863		return XFS_ERROR(EPERM);
1864	if (mp->m_rtdev_targp == NULL || mp->m_rbmip == NULL ||
1865	    (nrblocks = in->newblocks) <= sbp->sb_rblocks ||
1866	    (sbp->sb_rblocks && (in->extsize != sbp->sb_rextsize)))
1867		return XFS_ERROR(EINVAL);
1868	if ((error = xfs_sb_validate_fsb_count(sbp, nrblocks)))
1869		return error;
1870	/*
1871	 * Read in the last block of the device, make sure it exists.
1872	 */
1873	bp = xfs_buf_read_uncached(mp->m_rtdev_targp,
1874				XFS_FSB_TO_BB(mp, nrblocks - 1),
1875				XFS_FSB_TO_BB(mp, 1), 0);
1876	if (!bp)
1877		return EIO;
 
 
 
 
 
1878	xfs_buf_relse(bp);
1879
1880	/*
1881	 * Calculate new parameters.  These are the final values to be reached.
1882	 */
1883	nrextents = nrblocks;
1884	do_div(nrextents, in->extsize);
1885	nrbmblocks = howmany_64(nrextents, NBBY * sbp->sb_blocksize);
1886	nrextslog = xfs_highbit32(nrextents);
1887	nrsumlevels = nrextslog + 1;
1888	nrsumsize = (uint)sizeof(xfs_suminfo_t) * nrsumlevels * nrbmblocks;
1889	nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
1890	nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
1891	/*
1892	 * New summary size can't be more than half the size of
1893	 * the log.  This prevents us from getting a log overflow,
1894	 * since we'll log basically the whole summary file at once.
1895	 */
1896	if (nrsumblocks > (mp->m_sb.sb_logblocks >> 1))
1897		return XFS_ERROR(EINVAL);
1898	/*
1899	 * Get the old block counts for bitmap and summary inodes.
1900	 * These can't change since other growfs callers are locked out.
1901	 */
1902	rbmblocks = XFS_B_TO_FSB(mp, mp->m_rbmip->i_d.di_size);
1903	rsumblocks = XFS_B_TO_FSB(mp, mp->m_rsumip->i_d.di_size);
1904	/*
1905	 * Allocate space to the bitmap and summary files, as necessary.
1906	 */
1907	error = xfs_growfs_rt_alloc(mp, rbmblocks, nrbmblocks, mp->m_rbmip);
1908	if (error)
1909		return error;
1910	error = xfs_growfs_rt_alloc(mp, rsumblocks, nrsumblocks, mp->m_rsumip);
1911	if (error)
1912		return error;
1913	/*
1914	 * Allocate a new (fake) mount/sb.
1915	 */
1916	nmp = kmem_alloc(sizeof(*nmp), KM_SLEEP);
1917	/*
1918	 * Loop over the bitmap blocks.
1919	 * We will do everything one bitmap block at a time.
1920	 * Skip the current block if it is exactly full.
1921	 * This also deals with the case where there were no rtextents before.
1922	 */
1923	for (bmbno = sbp->sb_rbmblocks -
1924		     ((sbp->sb_rextents & ((1 << mp->m_blkbit_log) - 1)) != 0);
1925	     bmbno < nrbmblocks;
1926	     bmbno++) {
1927		xfs_trans_t	*tp;
1928		int		cancelflags = 0;
1929
1930		*nmp = *mp;
1931		nsbp = &nmp->m_sb;
1932		/*
1933		 * Calculate new sb and mount fields for this round.
1934		 */
1935		nsbp->sb_rextsize = in->extsize;
1936		nsbp->sb_rbmblocks = bmbno + 1;
1937		nsbp->sb_rblocks =
1938			XFS_RTMIN(nrblocks,
1939				  nsbp->sb_rbmblocks * NBBY *
1940				  nsbp->sb_blocksize * nsbp->sb_rextsize);
1941		nsbp->sb_rextents = nsbp->sb_rblocks;
1942		do_div(nsbp->sb_rextents, nsbp->sb_rextsize);
1943		ASSERT(nsbp->sb_rextents != 0);
1944		nsbp->sb_rextslog = xfs_highbit32(nsbp->sb_rextents);
1945		nrsumlevels = nmp->m_rsumlevels = nsbp->sb_rextslog + 1;
1946		nrsumsize =
1947			(uint)sizeof(xfs_suminfo_t) * nrsumlevels *
1948			nsbp->sb_rbmblocks;
1949		nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
1950		nmp->m_rsumsize = nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
1951		/*
1952		 * Start a transaction, get the log reservation.
1953		 */
1954		tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_FREE);
1955		if ((error = xfs_trans_reserve(tp, 0,
1956				XFS_GROWRTFREE_LOG_RES(nmp), 0, 0, 0)))
 
1957			goto error_cancel;
1958		/*
1959		 * Lock out other callers by grabbing the bitmap inode lock.
1960		 */
1961		xfs_ilock(mp->m_rbmip, XFS_ILOCK_EXCL);
1962		xfs_trans_ijoin(tp, mp->m_rbmip, XFS_ILOCK_EXCL);
1963		/*
1964		 * Update the bitmap inode's size.
1965		 */
1966		mp->m_rbmip->i_d.di_size =
1967			nsbp->sb_rbmblocks * nsbp->sb_blocksize;
1968		xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
1969		cancelflags |= XFS_TRANS_ABORT;
1970		/*
1971		 * Get the summary inode into the transaction.
1972		 */
1973		xfs_ilock(mp->m_rsumip, XFS_ILOCK_EXCL);
1974		xfs_trans_ijoin(tp, mp->m_rsumip, XFS_ILOCK_EXCL);
1975		/*
1976		 * Update the summary inode's size.
1977		 */
1978		mp->m_rsumip->i_d.di_size = nmp->m_rsumsize;
1979		xfs_trans_log_inode(tp, mp->m_rsumip, XFS_ILOG_CORE);
1980		/*
1981		 * Copy summary data from old to new sizes.
1982		 * Do this when the real size (not block-aligned) changes.
1983		 */
1984		if (sbp->sb_rbmblocks != nsbp->sb_rbmblocks ||
1985		    mp->m_rsumlevels != nmp->m_rsumlevels) {
1986			error = xfs_rtcopy_summary(mp, nmp, tp);
1987			if (error)
1988				goto error_cancel;
1989		}
1990		/*
1991		 * Update superblock fields.
1992		 */
1993		if (nsbp->sb_rextsize != sbp->sb_rextsize)
1994			xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSIZE,
1995				nsbp->sb_rextsize - sbp->sb_rextsize);
1996		if (nsbp->sb_rbmblocks != sbp->sb_rbmblocks)
1997			xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBMBLOCKS,
1998				nsbp->sb_rbmblocks - sbp->sb_rbmblocks);
1999		if (nsbp->sb_rblocks != sbp->sb_rblocks)
2000			xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBLOCKS,
2001				nsbp->sb_rblocks - sbp->sb_rblocks);
2002		if (nsbp->sb_rextents != sbp->sb_rextents)
2003			xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTENTS,
2004				nsbp->sb_rextents - sbp->sb_rextents);
2005		if (nsbp->sb_rextslog != sbp->sb_rextslog)
2006			xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSLOG,
2007				nsbp->sb_rextslog - sbp->sb_rextslog);
2008		/*
2009		 * Free new extent.
2010		 */
2011		bp = NULL;
2012		error = xfs_rtfree_range(nmp, tp, sbp->sb_rextents,
2013			nsbp->sb_rextents - sbp->sb_rextents, &bp, &sumbno);
2014		if (error) {
2015error_cancel:
2016			xfs_trans_cancel(tp, cancelflags);
2017			break;
2018		}
2019		/*
2020		 * Mark more blocks free in the superblock.
2021		 */
2022		xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS,
2023			nsbp->sb_rextents - sbp->sb_rextents);
2024		/*
2025		 * Update mp values into the real mp structure.
2026		 */
2027		mp->m_rsumlevels = nrsumlevels;
2028		mp->m_rsumsize = nrsumsize;
2029
2030		error = xfs_trans_commit(tp, 0);
2031		if (error)
2032			break;
2033	}
2034
2035	/*
2036	 * Free the fake mp structure.
2037	 */
2038	kmem_free(nmp);
2039
2040	return error;
2041}
2042
2043/*
2044 * Allocate an extent in the realtime subvolume, with the usual allocation
2045 * parameters.  The length units are all in realtime extents, as is the
2046 * result block number.
2047 */
2048int					/* error */
2049xfs_rtallocate_extent(
2050	xfs_trans_t	*tp,		/* transaction pointer */
2051	xfs_rtblock_t	bno,		/* starting block number to allocate */
2052	xfs_extlen_t	minlen,		/* minimum length to allocate */
2053	xfs_extlen_t	maxlen,		/* maximum length to allocate */
2054	xfs_extlen_t	*len,		/* out: actual length allocated */
2055	xfs_alloctype_t	type,		/* allocation type XFS_ALLOCTYPE... */
2056	int		wasdel,		/* was a delayed allocation extent */
2057	xfs_extlen_t	prod,		/* extent product factor */
2058	xfs_rtblock_t	*rtblock)	/* out: start block allocated */
2059{
2060	xfs_mount_t	*mp = tp->t_mountp;
2061	int		error;		/* error value */
2062	xfs_rtblock_t	r;		/* result allocated block */
2063	xfs_fsblock_t	sb;		/* summary file block number */
2064	xfs_buf_t	*sumbp;		/* summary file block buffer */
2065
2066	ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL));
2067	ASSERT(minlen > 0 && minlen <= maxlen);
2068
2069	/*
2070	 * If prod is set then figure out what to do to minlen and maxlen.
2071	 */
2072	if (prod > 1) {
2073		xfs_extlen_t	i;
2074
2075		if ((i = maxlen % prod))
2076			maxlen -= i;
2077		if ((i = minlen % prod))
2078			minlen += prod - i;
2079		if (maxlen < minlen) {
2080			*rtblock = NULLRTBLOCK;
2081			return 0;
2082		}
2083	}
2084
2085	sumbp = NULL;
2086	/*
2087	 * Allocate by size, or near another block, or exactly at some block.
2088	 */
2089	switch (type) {
2090	case XFS_ALLOCTYPE_ANY_AG:
2091		error = xfs_rtallocate_extent_size(mp, tp, minlen, maxlen, len,
2092				&sumbp,	&sb, prod, &r);
2093		break;
2094	case XFS_ALLOCTYPE_NEAR_BNO:
2095		error = xfs_rtallocate_extent_near(mp, tp, bno, minlen, maxlen,
2096				len, &sumbp, &sb, prod, &r);
2097		break;
2098	case XFS_ALLOCTYPE_THIS_BNO:
2099		error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen,
2100				len, &sumbp, &sb, prod, &r);
2101		break;
2102	default:
2103		error = EIO;
2104		ASSERT(0);
2105	}
2106	if (error)
2107		return error;
2108
2109	/*
2110	 * If it worked, update the superblock.
2111	 */
2112	if (r != NULLRTBLOCK) {
2113		long	slen = (long)*len;
2114
2115		ASSERT(*len >= minlen && *len <= maxlen);
2116		if (wasdel)
2117			xfs_trans_mod_sb(tp, XFS_TRANS_SB_RES_FREXTENTS, -slen);
2118		else
2119			xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, -slen);
2120	}
2121	*rtblock = r;
2122	return 0;
2123}
2124
2125/*
2126 * Free an extent in the realtime subvolume.  Length is expressed in
2127 * realtime extents, as is the block number.
2128 */
2129int					/* error */
2130xfs_rtfree_extent(
2131	xfs_trans_t	*tp,		/* transaction pointer */
2132	xfs_rtblock_t	bno,		/* starting block number to free */
2133	xfs_extlen_t	len)		/* length of extent freed */
2134{
2135	int		error;		/* error value */
2136	xfs_mount_t	*mp;		/* file system mount structure */
2137	xfs_fsblock_t	sb;		/* summary file block number */
2138	xfs_buf_t	*sumbp;		/* summary file block buffer */
2139
2140	mp = tp->t_mountp;
2141
2142	ASSERT(mp->m_rbmip->i_itemp != NULL);
2143	ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL));
2144
2145#if defined(__KERNEL__) && defined(DEBUG)
2146	/*
2147	 * Check to see that this whole range is currently allocated.
2148	 */
2149	{
2150		int	stat;		/* result from checking range */
2151
2152		error = xfs_rtcheck_alloc_range(mp, tp, bno, len, &stat);
2153		if (error) {
2154			return error;
2155		}
2156		ASSERT(stat);
2157	}
2158#endif
2159	sumbp = NULL;
2160	/*
2161	 * Free the range of realtime blocks.
2162	 */
2163	error = xfs_rtfree_range(mp, tp, bno, len, &sumbp, &sb);
2164	if (error) {
2165		return error;
2166	}
2167	/*
2168	 * Mark more blocks free in the superblock.
2169	 */
2170	xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, (long)len);
2171	/*
2172	 * If we've now freed all the blocks, reset the file sequence
2173	 * number to 0.
2174	 */
2175	if (tp->t_frextents_delta + mp->m_sb.sb_frextents ==
2176	    mp->m_sb.sb_rextents) {
2177		if (!(mp->m_rbmip->i_d.di_flags & XFS_DIFLAG_NEWRTBM))
2178			mp->m_rbmip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
2179		*(__uint64_t *)&mp->m_rbmip->i_d.di_atime = 0;
2180		xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
2181	}
2182	return 0;
2183}
2184
2185/*
2186 * Initialize realtime fields in the mount structure.
2187 */
2188int				/* error */
2189xfs_rtmount_init(
2190	xfs_mount_t	*mp)	/* file system mount structure */
2191{
2192	xfs_buf_t	*bp;	/* buffer for last block of subvolume */
2193	xfs_daddr_t	d;	/* address of last block of subvolume */
2194	xfs_sb_t	*sbp;	/* filesystem superblock copy in mount */
2195
2196	sbp = &mp->m_sb;
2197	if (sbp->sb_rblocks == 0)
2198		return 0;
2199	if (mp->m_rtdev_targp == NULL) {
2200		xfs_warn(mp,
2201	"Filesystem has a realtime volume, use rtdev=device option");
2202		return XFS_ERROR(ENODEV);
2203	}
2204	mp->m_rsumlevels = sbp->sb_rextslog + 1;
2205	mp->m_rsumsize =
2206		(uint)sizeof(xfs_suminfo_t) * mp->m_rsumlevels *
2207		sbp->sb_rbmblocks;
2208	mp->m_rsumsize = roundup(mp->m_rsumsize, sbp->sb_blocksize);
2209	mp->m_rbmip = mp->m_rsumip = NULL;
2210	/*
2211	 * Check that the realtime section is an ok size.
2212	 */
2213	d = (xfs_daddr_t)XFS_FSB_TO_BB(mp, mp->m_sb.sb_rblocks);
2214	if (XFS_BB_TO_FSB(mp, d) != mp->m_sb.sb_rblocks) {
2215		xfs_warn(mp, "realtime mount -- %llu != %llu",
2216			(unsigned long long) XFS_BB_TO_FSB(mp, d),
2217			(unsigned long long) mp->m_sb.sb_rblocks);
2218		return XFS_ERROR(EFBIG);
2219	}
2220	bp = xfs_buf_read_uncached(mp->m_rtdev_targp,
2221					d - XFS_FSB_TO_BB(mp, 1),
2222					XFS_FSB_TO_BB(mp, 1), 0);
2223	if (!bp) {
2224		xfs_warn(mp, "realtime device size check failed");
 
 
2225		return EIO;
2226	}
2227	xfs_buf_relse(bp);
2228	return 0;
2229}
2230
2231/*
2232 * Get the bitmap and summary inodes into the mount structure
2233 * at mount time.
2234 */
2235int					/* error */
2236xfs_rtmount_inodes(
2237	xfs_mount_t	*mp)		/* file system mount structure */
2238{
2239	int		error;		/* error return value */
2240	xfs_sb_t	*sbp;
2241
2242	sbp = &mp->m_sb;
2243	if (sbp->sb_rbmino == NULLFSINO)
2244		return 0;
2245	error = xfs_iget(mp, NULL, sbp->sb_rbmino, 0, 0, &mp->m_rbmip);
2246	if (error)
2247		return error;
2248	ASSERT(mp->m_rbmip != NULL);
2249	ASSERT(sbp->sb_rsumino != NULLFSINO);
2250	error = xfs_iget(mp, NULL, sbp->sb_rsumino, 0, 0, &mp->m_rsumip);
2251	if (error) {
2252		IRELE(mp->m_rbmip);
2253		return error;
2254	}
2255	ASSERT(mp->m_rsumip != NULL);
2256	return 0;
2257}
2258
2259void
2260xfs_rtunmount_inodes(
2261	struct xfs_mount	*mp)
2262{
2263	if (mp->m_rbmip)
2264		IRELE(mp->m_rbmip);
2265	if (mp->m_rsumip)
2266		IRELE(mp->m_rsumip);
2267}
2268
2269/*
2270 * Pick an extent for allocation at the start of a new realtime file.
2271 * Use the sequence number stored in the atime field of the bitmap inode.
2272 * Translate this to a fraction of the rtextents, and return the product
2273 * of rtextents and the fraction.
2274 * The fraction sequence is 0, 1/2, 1/4, 3/4, 1/8, ..., 7/8, 1/16, ...
2275 */
2276int					/* error */
2277xfs_rtpick_extent(
2278	xfs_mount_t	*mp,		/* file system mount point */
2279	xfs_trans_t	*tp,		/* transaction pointer */
2280	xfs_extlen_t	len,		/* allocation length (rtextents) */
2281	xfs_rtblock_t	*pick)		/* result rt extent */
2282{
2283	xfs_rtblock_t	b;		/* result block */
2284	int		log2;		/* log of sequence number */
2285	__uint64_t	resid;		/* residual after log removed */
2286	__uint64_t	seq;		/* sequence number of file creation */
2287	__uint64_t	*seqp;		/* pointer to seqno in inode */
2288
2289	ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL));
2290
2291	seqp = (__uint64_t *)&mp->m_rbmip->i_d.di_atime;
2292	if (!(mp->m_rbmip->i_d.di_flags & XFS_DIFLAG_NEWRTBM)) {
2293		mp->m_rbmip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
2294		*seqp = 0;
2295	}
2296	seq = *seqp;
2297	if ((log2 = xfs_highbit64(seq)) == -1)
2298		b = 0;
2299	else {
2300		resid = seq - (1ULL << log2);
2301		b = (mp->m_sb.sb_rextents * ((resid << 1) + 1ULL)) >>
2302		    (log2 + 1);
2303		if (b >= mp->m_sb.sb_rextents)
2304			b = do_mod(b, mp->m_sb.sb_rextents);
2305		if (b + len > mp->m_sb.sb_rextents)
2306			b = mp->m_sb.sb_rextents - len;
2307	}
2308	*seqp = seq + 1;
2309	xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
2310	*pick = b;
2311	return 0;
2312}