2 * Copyright (c) 2000-2004 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
34 #include "xfs_types.h"
38 #include "xfs_trans.h"
43 #include "xfs_dmapi.h"
44 #include "xfs_mount.h"
45 #include "xfs_bmap_btree.h"
46 #include "xfs_alloc_btree.h"
47 #include "xfs_ialloc_btree.h"
48 #include "xfs_dir_sf.h"
49 #include "xfs_dir2_sf.h"
50 #include "xfs_attr_sf.h"
51 #include "xfs_dinode.h"
52 #include "xfs_inode.h"
53 #include "xfs_btree.h"
54 #include "xfs_ialloc.h"
55 #include "xfs_alloc.h"
57 #include "xfs_rtalloc.h"
58 #include "xfs_fsops.h"
59 #include "xfs_error.h"
61 #include "xfs_inode_item.h"
62 #include "xfs_trans_space.h"
66 * Prototypes for internal functions.
70 STATIC int xfs_rtallocate_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
71 xfs_extlen_t, xfs_buf_t **, xfs_fsblock_t *);
72 STATIC int xfs_rtany_summary(xfs_mount_t *, xfs_trans_t *, int, int,
73 xfs_rtblock_t, xfs_buf_t **, xfs_fsblock_t *, int *);
74 STATIC int xfs_rtcheck_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
75 xfs_extlen_t, int, xfs_rtblock_t *, int *);
76 STATIC int xfs_rtfind_back(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
77 xfs_rtblock_t, xfs_rtblock_t *);
78 STATIC int xfs_rtfind_forw(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
79 xfs_rtblock_t, xfs_rtblock_t *);
80 STATIC int xfs_rtget_summary( xfs_mount_t *, xfs_trans_t *, int,
81 xfs_rtblock_t, xfs_buf_t **, xfs_fsblock_t *, xfs_suminfo_t *);
82 STATIC int xfs_rtmodify_range(xfs_mount_t *, xfs_trans_t *, xfs_rtblock_t,
84 STATIC int xfs_rtmodify_summary(xfs_mount_t *, xfs_trans_t *, int,
85 xfs_rtblock_t, int, xfs_buf_t **, xfs_fsblock_t *);
92 * xfs_lowbit32: get low bit set out of 32-bit argument, -1 if none set.
104 * Allocate space to the bitmap or summary file, and zero it, for growfs.
106 STATIC int /* error */
108 xfs_mount_t *mp, /* file system mount point */
109 xfs_extlen_t oblocks, /* old count of blocks */
110 xfs_extlen_t nblocks, /* new count of blocks */
111 xfs_ino_t ino) /* inode number (bitmap/summary) */
113 xfs_fileoff_t bno; /* block number in file */
114 xfs_buf_t *bp; /* temporary buffer for zeroing */
115 int cancelflags; /* flags for xfs_trans_cancel */
116 int committed; /* transaction committed flag */
117 xfs_daddr_t d; /* disk block address */
118 int error; /* error return value */
119 xfs_fsblock_t firstblock; /* first block allocated in xaction */
120 xfs_bmap_free_t flist; /* list of freed blocks */
121 xfs_fsblock_t fsbno; /* filesystem block for bno */
122 xfs_inode_t *ip; /* pointer to incore inode */
123 xfs_bmbt_irec_t map; /* block map output */
124 int nmap; /* number of block maps */
125 int resblks; /* space reservation */
126 xfs_trans_t *tp; /* transaction pointer */
129 * Allocate space to the file, as necessary.
131 while (oblocks < nblocks) {
132 tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_ALLOC);
133 resblks = XFS_GROWFSRT_SPACE_RES(mp, nblocks - oblocks);
136 * Reserve space & log for one extent added to the file.
138 if ((error = xfs_trans_reserve(tp, resblks,
139 XFS_GROWRTALLOC_LOG_RES(mp), 0,
140 XFS_TRANS_PERM_LOG_RES,
141 XFS_DEFAULT_PERM_LOG_COUNT)))
143 cancelflags = XFS_TRANS_RELEASE_LOG_RES;
147 if ((error = xfs_trans_iget(mp, tp, ino, 0, XFS_ILOCK_EXCL, &ip)))
149 XFS_BMAP_INIT(&flist, &firstblock);
151 * Allocate blocks to the bitmap file.
154 cancelflags |= XFS_TRANS_ABORT;
155 error = xfs_bmapi(tp, ip, oblocks, nblocks - oblocks,
156 XFS_BMAPI_WRITE | XFS_BMAPI_METADATA, &firstblock,
157 resblks, &map, &nmap, &flist);
158 if (!error && nmap < 1)
159 error = XFS_ERROR(ENOSPC);
163 * Free any blocks freed up in the transaction, then commit.
165 error = xfs_bmap_finish(&tp, &flist, firstblock, &committed);
168 xfs_trans_commit(tp, XFS_TRANS_RELEASE_LOG_RES, NULL);
170 * Now we need to clear the allocated blocks.
171 * Do this one block per transaction, to keep it simple.
174 for (bno = map.br_startoff, fsbno = map.br_startblock;
175 bno < map.br_startoff + map.br_blockcount;
177 tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_ZERO);
179 * Reserve log for one block zeroing.
181 if ((error = xfs_trans_reserve(tp, 0,
182 XFS_GROWRTZERO_LOG_RES(mp), 0, 0, 0)))
185 * Lock the bitmap inode.
187 if ((error = xfs_trans_iget(mp, tp, ino, 0, XFS_ILOCK_EXCL,
191 * Get a buffer for the block.
193 d = XFS_FSB_TO_DADDR(mp, fsbno);
194 bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d,
197 error = XFS_ERROR(EIO);
200 memset(XFS_BUF_PTR(bp), 0, mp->m_sb.sb_blocksize);
201 xfs_trans_log_buf(tp, bp, 0, mp->m_sb.sb_blocksize - 1);
203 * Commit the transaction.
205 xfs_trans_commit(tp, 0, NULL);
208 * Go on to the next extent, if any.
210 oblocks = map.br_startoff + map.br_blockcount;
214 xfs_trans_cancel(tp, cancelflags);
219 * Attempt to allocate an extent minlen<=len<=maxlen starting from
220 * bitmap block bbno. If we don't get maxlen then use prod to trim
221 * the length, if given. Returns error; returns starting block in *rtblock.
222 * The lengths are all in rtextents.
224 STATIC int /* error */
225 xfs_rtallocate_extent_block(
226 xfs_mount_t *mp, /* file system mount point */
227 xfs_trans_t *tp, /* transaction pointer */
228 xfs_rtblock_t bbno, /* bitmap block number */
229 xfs_extlen_t minlen, /* minimum length to allocate */
230 xfs_extlen_t maxlen, /* maximum length to allocate */
231 xfs_extlen_t *len, /* out: actual length allocated */
232 xfs_rtblock_t *nextp, /* out: next block to try */
233 xfs_buf_t **rbpp, /* in/out: summary block buffer */
234 xfs_fsblock_t *rsb, /* in/out: summary block number */
235 xfs_extlen_t prod, /* extent product factor */
236 xfs_rtblock_t *rtblock) /* out: start block allocated */
238 xfs_rtblock_t besti; /* best rtblock found so far */
239 xfs_rtblock_t bestlen; /* best length found so far */
240 xfs_rtblock_t end; /* last rtblock in chunk */
241 int error; /* error value */
242 xfs_rtblock_t i; /* current rtblock trying */
243 xfs_rtblock_t next; /* next rtblock to try */
244 int stat; /* status from internal calls */
247 * Loop over all the extents starting in this bitmap block,
248 * looking for one that's long enough.
250 for (i = XFS_BLOCKTOBIT(mp, bbno), besti = -1, bestlen = 0,
251 end = XFS_BLOCKTOBIT(mp, bbno + 1) - 1;
255 * See if there's a free extent of maxlen starting at i.
256 * If it's not so then next will contain the first non-free.
258 error = xfs_rtcheck_range(mp, tp, i, maxlen, 1, &next, &stat);
264 * i for maxlen is all free, allocate and return that.
266 error = xfs_rtallocate_range(mp, tp, i, maxlen, rbpp,
276 * In the case where we have a variable-sized allocation
277 * request, figure out how big this free piece is,
278 * and if it's big enough for the minimum, and the best
279 * so far, remember it.
281 if (minlen < maxlen) {
282 xfs_rtblock_t thislen; /* this extent size */
285 if (thislen >= minlen && thislen > bestlen) {
291 * If not done yet, find the start of the next free space.
294 error = xfs_rtfind_forw(mp, tp, next, end, &i);
302 * Searched the whole thing & didn't find a maxlen free extent.
304 if (minlen < maxlen && besti != -1) {
305 xfs_extlen_t p; /* amount to trim length by */
308 * If size should be a multiple of prod, make that so.
310 if (prod > 1 && (p = do_mod(bestlen, prod)))
313 * Allocate besti for bestlen & return that.
315 error = xfs_rtallocate_range(mp, tp, besti, bestlen, rbpp, rsb);
324 * Allocation failed. Set *nextp to the next block to try.
327 *rtblock = NULLRTBLOCK;
332 * Allocate an extent of length minlen<=len<=maxlen, starting at block
333 * bno. If we don't get maxlen then use prod to trim the length, if given.
334 * Returns error; returns starting block in *rtblock.
335 * The lengths are all in rtextents.
337 STATIC int /* error */
338 xfs_rtallocate_extent_exact(
339 xfs_mount_t *mp, /* file system mount point */
340 xfs_trans_t *tp, /* transaction pointer */
341 xfs_rtblock_t bno, /* starting block number to allocate */
342 xfs_extlen_t minlen, /* minimum length to allocate */
343 xfs_extlen_t maxlen, /* maximum length to allocate */
344 xfs_extlen_t *len, /* out: actual length allocated */
345 xfs_buf_t **rbpp, /* in/out: summary block buffer */
346 xfs_fsblock_t *rsb, /* in/out: summary block number */
347 xfs_extlen_t prod, /* extent product factor */
348 xfs_rtblock_t *rtblock) /* out: start block allocated */
350 int error; /* error value */
351 xfs_extlen_t i; /* extent length trimmed due to prod */
352 int isfree; /* extent is free */
353 xfs_rtblock_t next; /* next block to try (dummy) */
355 ASSERT(minlen % prod == 0 && maxlen % prod == 0);
357 * Check if the range in question (for maxlen) is free.
359 error = xfs_rtcheck_range(mp, tp, bno, maxlen, 1, &next, &isfree);
365 * If it is, allocate it and return success.
367 error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb);
376 * If not, allocate what there is, if it's at least minlen.
379 if (maxlen < minlen) {
381 * Failed, return failure status.
383 *rtblock = NULLRTBLOCK;
387 * Trim off tail of extent, if prod is specified.
389 if (prod > 1 && (i = maxlen % prod)) {
391 if (maxlen < minlen) {
393 * Now we can't do it, return failure status.
395 *rtblock = NULLRTBLOCK;
400 * Allocate what we can and return it.
402 error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb);
412 * Allocate an extent of length minlen<=len<=maxlen, starting as near
413 * to bno as possible. If we don't get maxlen then use prod to trim
414 * the length, if given. The lengths are all in rtextents.
416 STATIC int /* error */
417 xfs_rtallocate_extent_near(
418 xfs_mount_t *mp, /* file system mount point */
419 xfs_trans_t *tp, /* transaction pointer */
420 xfs_rtblock_t bno, /* starting block number to allocate */
421 xfs_extlen_t minlen, /* minimum length to allocate */
422 xfs_extlen_t maxlen, /* maximum length to allocate */
423 xfs_extlen_t *len, /* out: actual length allocated */
424 xfs_buf_t **rbpp, /* in/out: summary block buffer */
425 xfs_fsblock_t *rsb, /* in/out: summary block number */
426 xfs_extlen_t prod, /* extent product factor */
427 xfs_rtblock_t *rtblock) /* out: start block allocated */
429 int any; /* any useful extents from summary */
430 xfs_rtblock_t bbno; /* bitmap block number */
431 int error; /* error value */
432 int i; /* bitmap block offset (loop control) */
433 int j; /* secondary loop control */
434 int log2len; /* log2 of minlen */
435 xfs_rtblock_t n; /* next block to try */
436 xfs_rtblock_t r; /* result block */
438 ASSERT(minlen % prod == 0 && maxlen % prod == 0);
440 * If the block number given is off the end, silently set it to
443 if (bno >= mp->m_sb.sb_rextents)
444 bno = mp->m_sb.sb_rextents - 1;
446 * Try the exact allocation first.
448 error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen, len,
449 rbpp, rsb, prod, &r);
454 * If the exact allocation worked, return that.
456 if (r != NULLRTBLOCK) {
460 bbno = XFS_BITTOBLOCK(mp, bno);
462 log2len = xfs_highbit32(minlen);
464 * Loop over all bitmap blocks (bbno + i is current block).
468 * Get summary information of extents of all useful levels
469 * starting in this bitmap block.
471 error = xfs_rtany_summary(mp, tp, log2len, mp->m_rsumlevels - 1,
472 bbno + i, rbpp, rsb, &any);
477 * If there are any useful extents starting here, try
482 * On the positive side of the starting location.
486 * Try to allocate an extent starting in
489 error = xfs_rtallocate_extent_block(mp, tp,
490 bbno + i, minlen, maxlen, len, &n, rbpp,
496 * If it worked, return it.
498 if (r != NULLRTBLOCK) {
504 * On the negative side of the starting location.
508 * Loop backwards through the bitmap blocks from
509 * the starting point-1 up to where we are now.
510 * There should be an extent which ends in this
511 * bitmap block and is long enough.
513 for (j = -1; j > i; j--) {
515 * Grab the summary information for
518 error = xfs_rtany_summary(mp, tp,
519 log2len, mp->m_rsumlevels - 1,
520 bbno + j, rbpp, rsb, &any);
525 * If there's no extent given in the
526 * summary that means the extent we
527 * found must carry over from an
528 * earlier block. If there is an
529 * extent given, we've already tried
530 * that allocation, don't do it again.
534 error = xfs_rtallocate_extent_block(mp,
535 tp, bbno + j, minlen, maxlen,
536 len, &n, rbpp, rsb, prod, &r);
541 * If it works, return the extent.
543 if (r != NULLRTBLOCK) {
549 * There weren't intervening bitmap blocks
550 * with a long enough extent, or the
551 * allocation didn't work for some reason
552 * (i.e. it's a little * too short).
553 * Try to allocate from the summary block
556 error = xfs_rtallocate_extent_block(mp, tp,
557 bbno + i, minlen, maxlen, len, &n, rbpp,
563 * If it works, return the extent.
565 if (r != NULLRTBLOCK) {
572 * Loop control. If we were on the positive side, and there's
573 * still more blocks on the negative side, go there.
575 if (i > 0 && (int)bbno - i >= 0)
578 * If positive, and no more negative, but there are more
579 * positive, go there.
581 else if (i > 0 && (int)bbno + i < mp->m_sb.sb_rbmblocks - 1)
584 * If negative or 0 (just started), and there are positive
585 * blocks to go, go there. The 0 case moves to block 1.
587 else if (i <= 0 && (int)bbno - i < mp->m_sb.sb_rbmblocks - 1)
590 * If negative or 0 and there are more negative blocks,
593 else if (i <= 0 && (int)bbno + i > 0)
596 * Must be done. Return failure.
601 *rtblock = NULLRTBLOCK;
606 * Allocate an extent of length minlen<=len<=maxlen, with no position
607 * specified. If we don't get maxlen then use prod to trim
608 * the length, if given. The lengths are all in rtextents.
610 STATIC int /* error */
611 xfs_rtallocate_extent_size(
612 xfs_mount_t *mp, /* file system mount point */
613 xfs_trans_t *tp, /* transaction pointer */
614 xfs_extlen_t minlen, /* minimum length to allocate */
615 xfs_extlen_t maxlen, /* maximum length to allocate */
616 xfs_extlen_t *len, /* out: actual length allocated */
617 xfs_buf_t **rbpp, /* in/out: summary block buffer */
618 xfs_fsblock_t *rsb, /* in/out: summary block number */
619 xfs_extlen_t prod, /* extent product factor */
620 xfs_rtblock_t *rtblock) /* out: start block allocated */
622 int error; /* error value */
623 int i; /* bitmap block number */
624 int l; /* level number (loop control) */
625 xfs_rtblock_t n; /* next block to be tried */
626 xfs_rtblock_t r; /* result block number */
627 xfs_suminfo_t sum; /* summary information for extents */
629 ASSERT(minlen % prod == 0 && maxlen % prod == 0);
631 * Loop over all the levels starting with maxlen.
632 * At each level, look at all the bitmap blocks, to see if there
633 * are extents starting there that are long enough (>= maxlen).
634 * Note, only on the initial level can the allocation fail if
635 * the summary says there's an extent.
637 for (l = xfs_highbit32(maxlen); l < mp->m_rsumlevels; l++) {
639 * Loop over all the bitmap blocks.
641 for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
643 * Get the summary for this level/block.
645 error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb,
651 * Nothing there, on to the next block.
656 * Try allocating the extent.
658 error = xfs_rtallocate_extent_block(mp, tp, i, maxlen,
659 maxlen, len, &n, rbpp, rsb, prod, &r);
664 * If it worked, return that.
666 if (r != NULLRTBLOCK) {
671 * If the "next block to try" returned from the
672 * allocator is beyond the next bitmap block,
673 * skip to that bitmap block.
675 if (XFS_BITTOBLOCK(mp, n) > i + 1)
676 i = XFS_BITTOBLOCK(mp, n) - 1;
680 * Didn't find any maxlen blocks. Try smaller ones, unless
681 * we're asking for a fixed size extent.
683 if (minlen > --maxlen) {
684 *rtblock = NULLRTBLOCK;
688 * Loop over sizes, from maxlen down to minlen.
689 * This time, when we do the allocations, allow smaller ones
692 for (l = xfs_highbit32(maxlen); l >= xfs_highbit32(minlen); l--) {
694 * Loop over all the bitmap blocks, try an allocation
695 * starting in that block.
697 for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
699 * Get the summary information for this level/block.
701 error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb,
707 * If nothing there, go on to next.
712 * Try the allocation. Make sure the specified
713 * minlen/maxlen are in the possible range for
714 * this summary level.
716 error = xfs_rtallocate_extent_block(mp, tp, i,
717 XFS_RTMAX(minlen, 1 << l),
718 XFS_RTMIN(maxlen, (1 << (l + 1)) - 1),
719 len, &n, rbpp, rsb, prod, &r);
724 * If it worked, return that extent.
726 if (r != NULLRTBLOCK) {
731 * If the "next block to try" returned from the
732 * allocator is beyond the next bitmap block,
733 * skip to that bitmap block.
735 if (XFS_BITTOBLOCK(mp, n) > i + 1)
736 i = XFS_BITTOBLOCK(mp, n) - 1;
740 * Got nothing, return failure.
742 *rtblock = NULLRTBLOCK;
747 * Mark an extent specified by start and len allocated.
748 * Updates all the summary information as well as the bitmap.
750 STATIC int /* error */
751 xfs_rtallocate_range(
752 xfs_mount_t *mp, /* file system mount point */
753 xfs_trans_t *tp, /* transaction pointer */
754 xfs_rtblock_t start, /* start block to allocate */
755 xfs_extlen_t len, /* length to allocate */
756 xfs_buf_t **rbpp, /* in/out: summary block buffer */
757 xfs_fsblock_t *rsb) /* in/out: summary block number */
759 xfs_rtblock_t end; /* end of the allocated extent */
760 int error; /* error value */
761 xfs_rtblock_t postblock; /* first block allocated > end */
762 xfs_rtblock_t preblock; /* first block allocated < start */
764 end = start + len - 1;
766 * Assume we're allocating out of the middle of a free extent.
767 * We need to find the beginning and end of the extent so we can
768 * properly update the summary.
770 error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
775 * Find the next allocated block (end of free extent).
777 error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
783 * Decrement the summary information corresponding to the entire
786 error = xfs_rtmodify_summary(mp, tp,
787 XFS_RTBLOCKLOG(postblock + 1 - preblock),
788 XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
793 * If there are blocks not being allocated at the front of the
794 * old extent, add summary data for them to be free.
796 if (preblock < start) {
797 error = xfs_rtmodify_summary(mp, tp,
798 XFS_RTBLOCKLOG(start - preblock),
799 XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
805 * If there are blocks not being allocated at the end of the
806 * old extent, add summary data for them to be free.
808 if (postblock > end) {
809 error = xfs_rtmodify_summary(mp, tp,
810 XFS_RTBLOCKLOG(postblock - end),
811 XFS_BITTOBLOCK(mp, end + 1), 1, rbpp, rsb);
817 * Modify the bitmap to mark this extent allocated.
819 error = xfs_rtmodify_range(mp, tp, start, len, 0);
824 * Return whether there are any free extents in the size range given
825 * by low and high, for the bitmap block bbno.
827 STATIC int /* error */
829 xfs_mount_t *mp, /* file system mount structure */
830 xfs_trans_t *tp, /* transaction pointer */
831 int low, /* low log2 extent size */
832 int high, /* high log2 extent size */
833 xfs_rtblock_t bbno, /* bitmap block number */
834 xfs_buf_t **rbpp, /* in/out: summary block buffer */
835 xfs_fsblock_t *rsb, /* in/out: summary block number */
836 int *stat) /* out: any good extents here? */
838 int error; /* error value */
839 int log; /* loop counter, log2 of ext. size */
840 xfs_suminfo_t sum; /* summary data */
843 * Loop over logs of extent sizes. Order is irrelevant.
845 for (log = low; log <= high; log++) {
847 * Get one summary datum.
849 error = xfs_rtget_summary(mp, tp, log, bbno, rbpp, rsb, &sum);
854 * If there are any, return success.
862 * Found nothing, return failure.
869 * Get a buffer for the bitmap or summary file block specified.
870 * The buffer is returned read and locked.
872 STATIC int /* error */
874 xfs_mount_t *mp, /* file system mount structure */
875 xfs_trans_t *tp, /* transaction pointer */
876 xfs_rtblock_t block, /* block number in bitmap or summary */
877 int issum, /* is summary not bitmap */
878 xfs_buf_t **bpp) /* output: buffer for the block */
880 xfs_buf_t *bp; /* block buffer, result */
881 xfs_daddr_t d; /* disk addr of block */
882 int error; /* error value */
883 xfs_fsblock_t fsb; /* fs block number for block */
884 xfs_inode_t *ip; /* bitmap or summary inode */
886 ip = issum ? mp->m_rsumip : mp->m_rbmip;
888 * Map from the file offset (block) and inode number to the
891 error = xfs_bmapi_single(tp, ip, XFS_DATA_FORK, &fsb, block);
895 ASSERT(fsb != NULLFSBLOCK);
897 * Convert to disk address for buffer cache.
899 d = XFS_FSB_TO_DADDR(mp, fsb);
903 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
904 mp->m_bsize, 0, &bp);
908 ASSERT(bp && !XFS_BUF_GETERROR(bp));
915 * Check that the given extent (block range) is allocated already.
917 STATIC int /* error */
918 xfs_rtcheck_alloc_range(
919 xfs_mount_t *mp, /* file system mount point */
920 xfs_trans_t *tp, /* transaction pointer */
921 xfs_rtblock_t bno, /* starting block number of extent */
922 xfs_extlen_t len, /* length of extent */
923 int *stat) /* out: 1 for allocated, 0 for not */
925 xfs_rtblock_t new; /* dummy for xfs_rtcheck_range */
927 return xfs_rtcheck_range(mp, tp, bno, len, 0, &new, stat);
933 * Check whether the given block in the bitmap has the given value.
935 STATIC int /* 1 for matches, 0 for not */
937 xfs_mount_t *mp, /* file system mount structure */
938 xfs_trans_t *tp, /* transaction pointer */
939 xfs_rtblock_t start, /* bit (block) to check */
940 int val) /* 1 for free, 0 for allocated */
942 int bit; /* bit number in the word */
943 xfs_rtblock_t block; /* bitmap block number */
944 xfs_buf_t *bp; /* buf for the block */
945 xfs_rtword_t *bufp; /* pointer into the buffer */
947 int error; /* error value */
948 xfs_rtword_t wdiff; /* difference between bit & expected */
949 int word; /* word number in the buffer */
950 xfs_rtword_t wval; /* word value from buffer */
952 block = XFS_BITTOBLOCK(mp, start);
953 error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
954 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
955 word = XFS_BITTOWORD(mp, start);
956 bit = (int)(start & (XFS_NBWORD - 1));
958 xfs_trans_brelse(tp, bp);
959 wdiff = (wval ^ -val) & ((xfs_rtword_t)1 << bit);
966 * Check that the given extent (block range) is free already.
968 STATIC int /* error */
969 xfs_rtcheck_free_range(
970 xfs_mount_t *mp, /* file system mount point */
971 xfs_trans_t *tp, /* transaction pointer */
972 xfs_rtblock_t bno, /* starting block number of extent */
973 xfs_extlen_t len, /* length of extent */
974 int *stat) /* out: 1 for free, 0 for not */
976 xfs_rtblock_t new; /* dummy for xfs_rtcheck_range */
978 return xfs_rtcheck_range(mp, tp, bno, len, 1, &new, stat);
983 * Check that the given range is either all allocated (val = 0) or
984 * all free (val = 1).
986 STATIC int /* error */
988 xfs_mount_t *mp, /* file system mount point */
989 xfs_trans_t *tp, /* transaction pointer */
990 xfs_rtblock_t start, /* starting block number of extent */
991 xfs_extlen_t len, /* length of extent */
992 int val, /* 1 for free, 0 for allocated */
993 xfs_rtblock_t *new, /* out: first block not matching */
994 int *stat) /* out: 1 for matches, 0 for not */
996 xfs_rtword_t *b; /* current word in buffer */
997 int bit; /* bit number in the word */
998 xfs_rtblock_t block; /* bitmap block number */
999 xfs_buf_t *bp; /* buf for the block */
1000 xfs_rtword_t *bufp; /* starting word in buffer */
1001 int error; /* error value */
1002 xfs_rtblock_t i; /* current bit number rel. to start */
1003 xfs_rtblock_t lastbit; /* last useful bit in word */
1004 xfs_rtword_t mask; /* mask of relevant bits for value */
1005 xfs_rtword_t wdiff; /* difference from wanted value */
1006 int word; /* word number in the buffer */
1009 * Compute starting bitmap block number
1011 block = XFS_BITTOBLOCK(mp, start);
1013 * Read the bitmap block.
1015 error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1019 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1021 * Compute the starting word's address, and starting bit.
1023 word = XFS_BITTOWORD(mp, start);
1025 bit = (int)(start & (XFS_NBWORD - 1));
1027 * 0 (allocated) => all zero's; 1 (free) => all one's.
1031 * If not starting on a word boundary, deal with the first
1036 * Compute first bit not examined.
1038 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1040 * Mask of relevant bits.
1042 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1044 * Compute difference between actual and desired value.
1046 if ((wdiff = (*b ^ val) & mask)) {
1048 * Different, compute first wrong bit and return.
1050 xfs_trans_brelse(tp, bp);
1051 i = XFS_RTLOBIT(wdiff) - bit;
1058 * Go on to next block if that's where the next word is
1059 * and we need the next word.
1061 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1063 * If done with this block, get the next one.
1065 xfs_trans_brelse(tp, bp);
1066 error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1070 b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1074 * Go on to the next word in the buffer.
1080 * Starting on a word boundary, no partial word.
1085 * Loop over whole words in buffers. When we use up one buffer
1086 * we move on to the next one.
1088 while (len - i >= XFS_NBWORD) {
1090 * Compute difference between actual and desired value.
1092 if ((wdiff = *b ^ val)) {
1094 * Different, compute first wrong bit and return.
1096 xfs_trans_brelse(tp, bp);
1097 i += XFS_RTLOBIT(wdiff);
1104 * Go on to next block if that's where the next word is
1105 * and we need the next word.
1107 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1109 * If done with this block, get the next one.
1111 xfs_trans_brelse(tp, bp);
1112 error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1116 b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1120 * Go on to the next word in the buffer.
1126 * If not ending on a word boundary, deal with the last
1129 if ((lastbit = len - i)) {
1131 * Mask of relevant bits.
1133 mask = ((xfs_rtword_t)1 << lastbit) - 1;
1135 * Compute difference between actual and desired value.
1137 if ((wdiff = (*b ^ val) & mask)) {
1139 * Different, compute first wrong bit and return.
1141 xfs_trans_brelse(tp, bp);
1142 i += XFS_RTLOBIT(wdiff);
1150 * Successful, return.
1152 xfs_trans_brelse(tp, bp);
1159 * Copy and transform the summary file, given the old and new
1160 * parameters in the mount structures.
1162 STATIC int /* error */
1164 xfs_mount_t *omp, /* old file system mount point */
1165 xfs_mount_t *nmp, /* new file system mount point */
1166 xfs_trans_t *tp) /* transaction pointer */
1168 xfs_rtblock_t bbno; /* bitmap block number */
1169 xfs_buf_t *bp; /* summary buffer */
1170 int error; /* error return value */
1171 int log; /* summary level number (log length) */
1172 xfs_suminfo_t sum; /* summary data */
1173 xfs_fsblock_t sumbno; /* summary block number */
1176 for (log = omp->m_rsumlevels - 1; log >= 0; log--) {
1177 for (bbno = omp->m_sb.sb_rbmblocks - 1;
1178 (xfs_srtblock_t)bbno >= 0;
1180 error = xfs_rtget_summary(omp, tp, log, bbno, &bp,
1186 error = xfs_rtmodify_summary(omp, tp, log, bbno, -sum,
1190 error = xfs_rtmodify_summary(nmp, tp, log, bbno, sum,
1201 * Searching backward from start to limit, find the first block whose
1202 * allocated/free state is different from start's.
1204 STATIC int /* error */
1206 xfs_mount_t *mp, /* file system mount point */
1207 xfs_trans_t *tp, /* transaction pointer */
1208 xfs_rtblock_t start, /* starting block to look at */
1209 xfs_rtblock_t limit, /* last block to look at */
1210 xfs_rtblock_t *rtblock) /* out: start block found */
1212 xfs_rtword_t *b; /* current word in buffer */
1213 int bit; /* bit number in the word */
1214 xfs_rtblock_t block; /* bitmap block number */
1215 xfs_buf_t *bp; /* buf for the block */
1216 xfs_rtword_t *bufp; /* starting word in buffer */
1217 int error; /* error value */
1218 xfs_rtblock_t firstbit; /* first useful bit in the word */
1219 xfs_rtblock_t i; /* current bit number rel. to start */
1220 xfs_rtblock_t len; /* length of inspected area */
1221 xfs_rtword_t mask; /* mask of relevant bits for value */
1222 xfs_rtword_t want; /* mask for "good" values */
1223 xfs_rtword_t wdiff; /* difference from wanted value */
1224 int word; /* word number in the buffer */
1227 * Compute and read in starting bitmap block for starting block.
1229 block = XFS_BITTOBLOCK(mp, start);
1230 error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1234 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1236 * Get the first word's index & point to it.
1238 word = XFS_BITTOWORD(mp, start);
1240 bit = (int)(start & (XFS_NBWORD - 1));
1241 len = start - limit + 1;
1243 * Compute match value, based on the bit at start: if 1 (free)
1244 * then all-ones, else all-zeroes.
1246 want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
1248 * If the starting position is not word-aligned, deal with the
1251 if (bit < XFS_NBWORD - 1) {
1253 * Calculate first (leftmost) bit number to look at,
1254 * and mask for all the relevant bits in this word.
1256 firstbit = XFS_RTMAX((xfs_srtblock_t)(bit - len + 1), 0);
1257 mask = (((xfs_rtword_t)1 << (bit - firstbit + 1)) - 1) <<
1260 * Calculate the difference between the value there
1261 * and what we're looking for.
1263 if ((wdiff = (*b ^ want) & mask)) {
1265 * Different. Mark where we are and return.
1267 xfs_trans_brelse(tp, bp);
1268 i = bit - XFS_RTHIBIT(wdiff);
1269 *rtblock = start - i + 1;
1272 i = bit - firstbit + 1;
1274 * Go on to previous block if that's where the previous word is
1275 * and we need the previous word.
1277 if (--word == -1 && i < len) {
1279 * If done with this block, get the previous one.
1281 xfs_trans_brelse(tp, bp);
1282 error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
1286 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1287 word = XFS_BLOCKWMASK(mp);
1291 * Go on to the previous word in the buffer.
1297 * Starting on a word boundary, no partial word.
1302 * Loop over whole words in buffers. When we use up one buffer
1303 * we move on to the previous one.
1305 while (len - i >= XFS_NBWORD) {
1307 * Compute difference between actual and desired value.
1309 if ((wdiff = *b ^ want)) {
1311 * Different, mark where we are and return.
1313 xfs_trans_brelse(tp, bp);
1314 i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
1315 *rtblock = start - i + 1;
1320 * Go on to previous block if that's where the previous word is
1321 * and we need the previous word.
1323 if (--word == -1 && i < len) {
1325 * If done with this block, get the previous one.
1327 xfs_trans_brelse(tp, bp);
1328 error = xfs_rtbuf_get(mp, tp, --block, 0, &bp);
1332 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1333 word = XFS_BLOCKWMASK(mp);
1337 * Go on to the previous word in the buffer.
1343 * If not ending on a word boundary, deal with the last
1348 * Calculate first (leftmost) bit number to look at,
1349 * and mask for all the relevant bits in this word.
1351 firstbit = XFS_NBWORD - (len - i);
1352 mask = (((xfs_rtword_t)1 << (len - i)) - 1) << firstbit;
1354 * Compute difference between actual and desired value.
1356 if ((wdiff = (*b ^ want) & mask)) {
1358 * Different, mark where we are and return.
1360 xfs_trans_brelse(tp, bp);
1361 i += XFS_NBWORD - 1 - XFS_RTHIBIT(wdiff);
1362 *rtblock = start - i + 1;
1368 * No match, return that we scanned the whole area.
1370 xfs_trans_brelse(tp, bp);
1371 *rtblock = start - i + 1;
1376 * Searching forward from start to limit, find the first block whose
1377 * allocated/free state is different from start's.
1379 STATIC int /* error */
1381 xfs_mount_t *mp, /* file system mount point */
1382 xfs_trans_t *tp, /* transaction pointer */
1383 xfs_rtblock_t start, /* starting block to look at */
1384 xfs_rtblock_t limit, /* last block to look at */
1385 xfs_rtblock_t *rtblock) /* out: start block found */
1387 xfs_rtword_t *b; /* current word in buffer */
1388 int bit; /* bit number in the word */
1389 xfs_rtblock_t block; /* bitmap block number */
1390 xfs_buf_t *bp; /* buf for the block */
1391 xfs_rtword_t *bufp; /* starting word in buffer */
1392 int error; /* error value */
1393 xfs_rtblock_t i; /* current bit number rel. to start */
1394 xfs_rtblock_t lastbit; /* last useful bit in the word */
1395 xfs_rtblock_t len; /* length of inspected area */
1396 xfs_rtword_t mask; /* mask of relevant bits for value */
1397 xfs_rtword_t want; /* mask for "good" values */
1398 xfs_rtword_t wdiff; /* difference from wanted value */
1399 int word; /* word number in the buffer */
1402 * Compute and read in starting bitmap block for starting block.
1404 block = XFS_BITTOBLOCK(mp, start);
1405 error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1409 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1411 * Get the first word's index & point to it.
1413 word = XFS_BITTOWORD(mp, start);
1415 bit = (int)(start & (XFS_NBWORD - 1));
1416 len = limit - start + 1;
1418 * Compute match value, based on the bit at start: if 1 (free)
1419 * then all-ones, else all-zeroes.
1421 want = (*b & ((xfs_rtword_t)1 << bit)) ? -1 : 0;
1423 * If the starting position is not word-aligned, deal with the
1428 * Calculate last (rightmost) bit number to look at,
1429 * and mask for all the relevant bits in this word.
1431 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1432 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1434 * Calculate the difference between the value there
1435 * and what we're looking for.
1437 if ((wdiff = (*b ^ want) & mask)) {
1439 * Different. Mark where we are and return.
1441 xfs_trans_brelse(tp, bp);
1442 i = XFS_RTLOBIT(wdiff) - bit;
1443 *rtblock = start + i - 1;
1448 * Go on to next block if that's where the next word is
1449 * and we need the next word.
1451 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1453 * If done with this block, get the previous one.
1455 xfs_trans_brelse(tp, bp);
1456 error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1460 b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1464 * Go on to the previous word in the buffer.
1470 * Starting on a word boundary, no partial word.
1475 * Loop over whole words in buffers. When we use up one buffer
1476 * we move on to the next one.
1478 while (len - i >= XFS_NBWORD) {
1480 * Compute difference between actual and desired value.
1482 if ((wdiff = *b ^ want)) {
1484 * Different, mark where we are and return.
1486 xfs_trans_brelse(tp, bp);
1487 i += XFS_RTLOBIT(wdiff);
1488 *rtblock = start + i - 1;
1493 * Go on to next block if that's where the next word is
1494 * and we need the next word.
1496 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1498 * If done with this block, get the next one.
1500 xfs_trans_brelse(tp, bp);
1501 error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1505 b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1509 * Go on to the next word in the buffer.
1515 * If not ending on a word boundary, deal with the last
1518 if ((lastbit = len - i)) {
1520 * Calculate mask for all the relevant bits in this word.
1522 mask = ((xfs_rtword_t)1 << lastbit) - 1;
1524 * Compute difference between actual and desired value.
1526 if ((wdiff = (*b ^ want) & mask)) {
1528 * Different, mark where we are and return.
1530 xfs_trans_brelse(tp, bp);
1531 i += XFS_RTLOBIT(wdiff);
1532 *rtblock = start + i - 1;
1538 * No match, return that we scanned the whole area.
1540 xfs_trans_brelse(tp, bp);
1541 *rtblock = start + i - 1;
1546 * Mark an extent specified by start and len freed.
1547 * Updates all the summary information as well as the bitmap.
1549 STATIC int /* error */
1551 xfs_mount_t *mp, /* file system mount point */
1552 xfs_trans_t *tp, /* transaction pointer */
1553 xfs_rtblock_t start, /* starting block to free */
1554 xfs_extlen_t len, /* length to free */
1555 xfs_buf_t **rbpp, /* in/out: summary block buffer */
1556 xfs_fsblock_t *rsb) /* in/out: summary block number */
1558 xfs_rtblock_t end; /* end of the freed extent */
1559 int error; /* error value */
1560 xfs_rtblock_t postblock; /* first block freed > end */
1561 xfs_rtblock_t preblock; /* first block freed < start */
1563 end = start + len - 1;
1565 * Modify the bitmap to mark this extent freed.
1567 error = xfs_rtmodify_range(mp, tp, start, len, 1);
1572 * Assume we're freeing out of the middle of an allocated extent.
1573 * We need to find the beginning and end of the extent so we can
1574 * properly update the summary.
1576 error = xfs_rtfind_back(mp, tp, start, 0, &preblock);
1581 * Find the next allocated block (end of allocated extent).
1583 error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1,
1586 * If there are blocks not being freed at the front of the
1587 * old extent, add summary data for them to be allocated.
1589 if (preblock < start) {
1590 error = xfs_rtmodify_summary(mp, tp,
1591 XFS_RTBLOCKLOG(start - preblock),
1592 XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb);
1598 * If there are blocks not being freed at the end of the
1599 * old extent, add summary data for them to be allocated.
1601 if (postblock > end) {
1602 error = xfs_rtmodify_summary(mp, tp,
1603 XFS_RTBLOCKLOG(postblock - end),
1604 XFS_BITTOBLOCK(mp, end + 1), -1, rbpp, rsb);
1610 * Increment the summary information corresponding to the entire
1611 * (new) free extent.
1613 error = xfs_rtmodify_summary(mp, tp,
1614 XFS_RTBLOCKLOG(postblock + 1 - preblock),
1615 XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb);
1620 * Read and return the summary information for a given extent size,
1621 * bitmap block combination.
1622 * Keeps track of a current summary block, so we don't keep reading
1623 * it from the buffer cache.
1625 STATIC int /* error */
1627 xfs_mount_t *mp, /* file system mount structure */
1628 xfs_trans_t *tp, /* transaction pointer */
1629 int log, /* log2 of extent size */
1630 xfs_rtblock_t bbno, /* bitmap block number */
1631 xfs_buf_t **rbpp, /* in/out: summary block buffer */
1632 xfs_fsblock_t *rsb, /* in/out: summary block number */
1633 xfs_suminfo_t *sum) /* out: summary info for this block */
1635 xfs_buf_t *bp; /* buffer for summary block */
1636 int error; /* error value */
1637 xfs_fsblock_t sb; /* summary fsblock */
1638 int so; /* index into the summary file */
1639 xfs_suminfo_t *sp; /* pointer to returned data */
1642 * Compute entry number in the summary file.
1644 so = XFS_SUMOFFS(mp, log, bbno);
1646 * Compute the block number in the summary file.
1648 sb = XFS_SUMOFFSTOBLOCK(mp, so);
1650 * If we have an old buffer, and the block number matches, use that.
1652 if (rbpp && *rbpp && *rsb == sb)
1655 * Otherwise we have to get the buffer.
1659 * If there was an old one, get rid of it first.
1662 xfs_trans_brelse(tp, *rbpp);
1663 error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
1668 * Remember this buffer and block for the next call.
1676 * Point to the summary information & copy it out.
1678 sp = XFS_SUMPTR(mp, bp, so);
1681 * Drop the buffer if we're not asked to remember it.
1684 xfs_trans_brelse(tp, bp);
1689 * Set the given range of bitmap bits to the given value.
1690 * Do whatever I/O and logging is required.
1692 STATIC int /* error */
1694 xfs_mount_t *mp, /* file system mount point */
1695 xfs_trans_t *tp, /* transaction pointer */
1696 xfs_rtblock_t start, /* starting block to modify */
1697 xfs_extlen_t len, /* length of extent to modify */
1698 int val) /* 1 for free, 0 for allocated */
1700 xfs_rtword_t *b; /* current word in buffer */
1701 int bit; /* bit number in the word */
1702 xfs_rtblock_t block; /* bitmap block number */
1703 xfs_buf_t *bp; /* buf for the block */
1704 xfs_rtword_t *bufp; /* starting word in buffer */
1705 int error; /* error value */
1706 xfs_rtword_t *first; /* first used word in the buffer */
1707 int i; /* current bit number rel. to start */
1708 int lastbit; /* last useful bit in word */
1709 xfs_rtword_t mask; /* mask o frelevant bits for value */
1710 int word; /* word number in the buffer */
1713 * Compute starting bitmap block number.
1715 block = XFS_BITTOBLOCK(mp, start);
1717 * Read the bitmap block, and point to its data.
1719 error = xfs_rtbuf_get(mp, tp, block, 0, &bp);
1723 bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1725 * Compute the starting word's address, and starting bit.
1727 word = XFS_BITTOWORD(mp, start);
1728 first = b = &bufp[word];
1729 bit = (int)(start & (XFS_NBWORD - 1));
1731 * 0 (allocated) => all zeroes; 1 (free) => all ones.
1735 * If not starting on a word boundary, deal with the first
1740 * Compute first bit not changed and mask of relevant bits.
1742 lastbit = XFS_RTMIN(bit + len, XFS_NBWORD);
1743 mask = (((xfs_rtword_t)1 << (lastbit - bit)) - 1) << bit;
1745 * Set/clear the active bits.
1753 * Go on to the next block if that's where the next word is
1754 * and we need the next word.
1756 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1758 * Log the changed part of this block.
1761 xfs_trans_log_buf(tp, bp,
1762 (uint)((char *)first - (char *)bufp),
1763 (uint)((char *)b - (char *)bufp));
1764 error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1768 first = b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1772 * Go on to the next word in the buffer
1778 * Starting on a word boundary, no partial word.
1783 * Loop over whole words in buffers. When we use up one buffer
1784 * we move on to the next one.
1786 while (len - i >= XFS_NBWORD) {
1788 * Set the word value correctly.
1793 * Go on to the next block if that's where the next word is
1794 * and we need the next word.
1796 if (++word == XFS_BLOCKWSIZE(mp) && i < len) {
1798 * Log the changed part of this block.
1801 xfs_trans_log_buf(tp, bp,
1802 (uint)((char *)first - (char *)bufp),
1803 (uint)((char *)b - (char *)bufp));
1804 error = xfs_rtbuf_get(mp, tp, ++block, 0, &bp);
1808 first = b = bufp = (xfs_rtword_t *)XFS_BUF_PTR(bp);
1812 * Go on to the next word in the buffer
1818 * If not ending on a word boundary, deal with the last
1821 if ((lastbit = len - i)) {
1823 * Compute a mask of relevant bits.
1826 mask = ((xfs_rtword_t)1 << lastbit) - 1;
1828 * Set/clear the active bits.
1837 * Log any remaining changed bytes.
1840 xfs_trans_log_buf(tp, bp, (uint)((char *)first - (char *)bufp),
1841 (uint)((char *)b - (char *)bufp - 1));
1846 * Read and modify the summary information for a given extent size,
1847 * bitmap block combination.
1848 * Keeps track of a current summary block, so we don't keep reading
1849 * it from the buffer cache.
1851 STATIC int /* error */
1852 xfs_rtmodify_summary(
1853 xfs_mount_t *mp, /* file system mount point */
1854 xfs_trans_t *tp, /* transaction pointer */
1855 int log, /* log2 of extent size */
1856 xfs_rtblock_t bbno, /* bitmap block number */
1857 int delta, /* change to make to summary info */
1858 xfs_buf_t **rbpp, /* in/out: summary block buffer */
1859 xfs_fsblock_t *rsb) /* in/out: summary block number */
1861 xfs_buf_t *bp; /* buffer for the summary block */
1862 int error; /* error value */
1863 xfs_fsblock_t sb; /* summary fsblock */
1864 int so; /* index into the summary file */
1865 xfs_suminfo_t *sp; /* pointer to returned data */
1868 * Compute entry number in the summary file.
1870 so = XFS_SUMOFFS(mp, log, bbno);
1872 * Compute the block number in the summary file.
1874 sb = XFS_SUMOFFSTOBLOCK(mp, so);
1876 * If we have an old buffer, and the block number matches, use that.
1878 if (rbpp && *rbpp && *rsb == sb)
1881 * Otherwise we have to get the buffer.
1885 * If there was an old one, get rid of it first.
1888 xfs_trans_brelse(tp, *rbpp);
1889 error = xfs_rtbuf_get(mp, tp, sb, 1, &bp);
1894 * Remember this buffer and block for the next call.
1902 * Point to the summary information, modify and log it.
1904 sp = XFS_SUMPTR(mp, bp, so);
1906 xfs_trans_log_buf(tp, bp, (uint)((char *)sp - (char *)XFS_BUF_PTR(bp)),
1907 (uint)((char *)sp - (char *)XFS_BUF_PTR(bp) + sizeof(*sp) - 1));
1912 * Visible (exported) functions.
1916 * Grow the realtime area of the filesystem.
1920 xfs_mount_t *mp, /* mount point for filesystem */
1921 xfs_growfs_rt_t *in) /* growfs rt input struct */
1923 xfs_rtblock_t bmbno; /* bitmap block number */
1924 xfs_buf_t *bp; /* temporary buffer */
1925 int cancelflags; /* flags for xfs_trans_cancel */
1926 int error; /* error return value */
1927 xfs_inode_t *ip; /* bitmap inode, used as lock */
1928 xfs_mount_t *nmp; /* new (fake) mount structure */
1929 xfs_drfsbno_t nrblocks; /* new number of realtime blocks */
1930 xfs_extlen_t nrbmblocks; /* new number of rt bitmap blocks */
1931 xfs_drtbno_t nrextents; /* new number of realtime extents */
1932 uint8_t nrextslog; /* new log2 of sb_rextents */
1933 xfs_extlen_t nrsumblocks; /* new number of summary blocks */
1934 uint nrsumlevels; /* new rt summary levels */
1935 uint nrsumsize; /* new size of rt summary, bytes */
1936 xfs_sb_t *nsbp; /* new superblock */
1937 xfs_extlen_t rbmblocks; /* current number of rt bitmap blocks */
1938 xfs_extlen_t rsumblocks; /* current number of rt summary blks */
1939 xfs_sb_t *sbp; /* old superblock */
1940 xfs_fsblock_t sumbno; /* summary block number */
1941 xfs_trans_t *tp; /* transaction pointer */
1945 * Initial error checking.
1947 if (mp->m_rtdev_targp || mp->m_rbmip == NULL ||
1948 (nrblocks = in->newblocks) <= sbp->sb_rblocks ||
1949 (sbp->sb_rblocks && (in->extsize != sbp->sb_rextsize)))
1950 return XFS_ERROR(EINVAL);
1952 * Read in the last block of the device, make sure it exists.
1954 error = xfs_read_buf(mp, mp->m_rtdev_targp,
1955 XFS_FSB_TO_BB(mp, in->newblocks - 1),
1956 XFS_FSB_TO_BB(mp, 1), 0, &bp);
1962 * Calculate new parameters. These are the final values to be reached.
1964 nrextents = nrblocks;
1965 do_div(nrextents, in->extsize);
1966 nrbmblocks = roundup_64(nrextents, NBBY * sbp->sb_blocksize);
1967 nrextslog = xfs_highbit32(nrextents);
1968 nrsumlevels = nrextslog + 1;
1969 nrsumsize = (uint)sizeof(xfs_suminfo_t) * nrsumlevels * nrbmblocks;
1970 nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
1971 nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
1973 * New summary size can't be more than half the size of
1974 * the log. This prevents us from getting a log overflow,
1975 * since we'll log basically the whole summary file at once.
1977 if (nrsumblocks > (mp->m_sb.sb_logblocks >> 1))
1978 return XFS_ERROR(EINVAL);
1980 * Get the old block counts for bitmap and summary inodes.
1981 * These can't change since other growfs callers are locked out.
1983 rbmblocks = XFS_B_TO_FSB(mp, mp->m_rbmip->i_d.di_size);
1984 rsumblocks = XFS_B_TO_FSB(mp, mp->m_rsumip->i_d.di_size);
1986 * Allocate space to the bitmap and summary files, as necessary.
1988 if ((error = xfs_growfs_rt_alloc(mp, rbmblocks, nrbmblocks,
1989 mp->m_sb.sb_rbmino)))
1991 if ((error = xfs_growfs_rt_alloc(mp, rsumblocks, nrsumblocks,
1992 mp->m_sb.sb_rsumino)))
1996 * Loop over the bitmap blocks.
1997 * We will do everything one bitmap block at a time.
1998 * Skip the current block if it is exactly full.
1999 * This also deals with the case where there were no rtextents before.
2001 for (bmbno = sbp->sb_rbmblocks -
2002 ((sbp->sb_rextents & ((1 << mp->m_blkbit_log) - 1)) != 0);
2006 * Allocate a new (fake) mount/sb.
2008 nmp = kmem_alloc(sizeof(*nmp), KM_SLEEP);
2012 * Calculate new sb and mount fields for this round.
2014 nsbp->sb_rextsize = in->extsize;
2015 nsbp->sb_rbmblocks = bmbno + 1;
2018 nsbp->sb_rbmblocks * NBBY *
2019 nsbp->sb_blocksize * nsbp->sb_rextsize);
2020 nsbp->sb_rextents = nsbp->sb_rblocks;
2021 do_div(nsbp->sb_rextents, nsbp->sb_rextsize);
2022 nsbp->sb_rextslog = xfs_highbit32(nsbp->sb_rextents);
2023 nrsumlevels = nmp->m_rsumlevels = nsbp->sb_rextslog + 1;
2025 (uint)sizeof(xfs_suminfo_t) * nrsumlevels *
2027 nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
2028 nmp->m_rsumsize = nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
2030 * Start a transaction, get the log reservation.
2032 tp = xfs_trans_alloc(mp, XFS_TRANS_GROWFSRT_FREE);
2034 if ((error = xfs_trans_reserve(tp, 0,
2035 XFS_GROWRTFREE_LOG_RES(nmp), 0, 0, 0)))
2038 * Lock out other callers by grabbing the bitmap inode lock.
2040 if ((error = xfs_trans_iget(mp, tp, 0, mp->m_sb.sb_rbmino,
2041 XFS_ILOCK_EXCL, &ip)))
2043 ASSERT(ip == mp->m_rbmip);
2045 * Update the bitmap inode's size.
2047 mp->m_rbmip->i_d.di_size =
2048 nsbp->sb_rbmblocks * nsbp->sb_blocksize;
2049 xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE);
2050 cancelflags |= XFS_TRANS_ABORT;
2052 * Get the summary inode into the transaction.
2054 if ((error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rsumino,
2055 0, XFS_ILOCK_EXCL, &ip)))
2057 ASSERT(ip == mp->m_rsumip);
2059 * Update the summary inode's size.
2061 mp->m_rsumip->i_d.di_size = nmp->m_rsumsize;
2062 xfs_trans_log_inode(tp, mp->m_rsumip, XFS_ILOG_CORE);
2064 * Copy summary data from old to new sizes.
2065 * Do this when the real size (not block-aligned) changes.
2067 if (sbp->sb_rbmblocks != nsbp->sb_rbmblocks ||
2068 mp->m_rsumlevels != nmp->m_rsumlevels) {
2069 error = xfs_rtcopy_summary(mp, nmp, tp);
2074 * Update superblock fields.
2076 if (nsbp->sb_rextsize != sbp->sb_rextsize)
2077 xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSIZE,
2078 nsbp->sb_rextsize - sbp->sb_rextsize);
2079 if (nsbp->sb_rbmblocks != sbp->sb_rbmblocks)
2080 xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBMBLOCKS,
2081 nsbp->sb_rbmblocks - sbp->sb_rbmblocks);
2082 if (nsbp->sb_rblocks != sbp->sb_rblocks)
2083 xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBLOCKS,
2084 nsbp->sb_rblocks - sbp->sb_rblocks);
2085 if (nsbp->sb_rextents != sbp->sb_rextents)
2086 xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTENTS,
2087 nsbp->sb_rextents - sbp->sb_rextents);
2088 if (nsbp->sb_rextslog != sbp->sb_rextslog)
2089 xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSLOG,
2090 nsbp->sb_rextslog - sbp->sb_rextslog);
2095 error = xfs_rtfree_range(nmp, tp, sbp->sb_rextents,
2096 nsbp->sb_rextents - sbp->sb_rextents, &bp, &sumbno);
2100 * Mark more blocks free in the superblock.
2102 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS,
2103 nsbp->sb_rextents - sbp->sb_rextents);
2105 * Free the fake mp structure.
2107 kmem_free(nmp, sizeof(*nmp));
2110 * Update mp values into the real mp structure.
2112 mp->m_rsumlevels = nrsumlevels;
2113 mp->m_rsumsize = nrsumsize;
2115 * Commit the transaction.
2117 xfs_trans_commit(tp, 0, NULL);
2122 * Error paths come here.
2126 kmem_free(nmp, sizeof(*nmp));
2127 xfs_trans_cancel(tp, cancelflags);
2132 * Allocate an extent in the realtime subvolume, with the usual allocation
2133 * parameters. The length units are all in realtime extents, as is the
2134 * result block number.
2137 xfs_rtallocate_extent(
2138 xfs_trans_t *tp, /* transaction pointer */
2139 xfs_rtblock_t bno, /* starting block number to allocate */
2140 xfs_extlen_t minlen, /* minimum length to allocate */
2141 xfs_extlen_t maxlen, /* maximum length to allocate */
2142 xfs_extlen_t *len, /* out: actual length allocated */
2143 xfs_alloctype_t type, /* allocation type XFS_ALLOCTYPE... */
2144 int wasdel, /* was a delayed allocation extent */
2145 xfs_extlen_t prod, /* extent product factor */
2146 xfs_rtblock_t *rtblock) /* out: start block allocated */
2148 int error; /* error value */
2149 xfs_inode_t *ip; /* inode for bitmap file */
2150 xfs_mount_t *mp; /* file system mount structure */
2151 xfs_rtblock_t r; /* result allocated block */
2152 xfs_fsblock_t sb; /* summary file block number */
2153 xfs_buf_t *sumbp; /* summary file block buffer */
2155 ASSERT(minlen > 0 && minlen <= maxlen);
2158 * If prod is set then figure out what to do to minlen and maxlen.
2163 if ((i = maxlen % prod))
2165 if ((i = minlen % prod))
2167 if (maxlen < minlen) {
2168 *rtblock = NULLRTBLOCK;
2173 * Lock out other callers by grabbing the bitmap inode lock.
2175 error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rbmino, 0, XFS_ILOCK_EXCL, &ip);
2181 * Allocate by size, or near another block, or exactly at some block.
2184 case XFS_ALLOCTYPE_ANY_AG:
2185 error = xfs_rtallocate_extent_size(mp, tp, minlen, maxlen, len,
2186 &sumbp, &sb, prod, &r);
2188 case XFS_ALLOCTYPE_NEAR_BNO:
2189 error = xfs_rtallocate_extent_near(mp, tp, bno, minlen, maxlen,
2190 len, &sumbp, &sb, prod, &r);
2192 case XFS_ALLOCTYPE_THIS_BNO:
2193 error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen,
2194 len, &sumbp, &sb, prod, &r);
2203 * If it worked, update the superblock.
2205 if (r != NULLRTBLOCK) {
2206 long slen = (long)*len;
2208 ASSERT(*len >= minlen && *len <= maxlen);
2210 xfs_trans_mod_sb(tp, XFS_TRANS_SB_RES_FREXTENTS, -slen);
2212 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, -slen);
2219 * Free an extent in the realtime subvolume. Length is expressed in
2220 * realtime extents, as is the block number.
2224 xfs_trans_t *tp, /* transaction pointer */
2225 xfs_rtblock_t bno, /* starting block number to free */
2226 xfs_extlen_t len) /* length of extent freed */
2228 int error; /* error value */
2229 xfs_inode_t *ip; /* bitmap file inode */
2230 xfs_mount_t *mp; /* file system mount structure */
2231 xfs_fsblock_t sb; /* summary file block number */
2232 xfs_buf_t *sumbp; /* summary file block buffer */
2236 * Synchronize by locking the bitmap inode.
2238 error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rbmino, 0, XFS_ILOCK_EXCL, &ip);
2242 #if defined(__KERNEL__) && defined(DEBUG)
2244 * Check to see that this whole range is currently allocated.
2247 int stat; /* result from checking range */
2249 error = xfs_rtcheck_alloc_range(mp, tp, bno, len, &stat);
2258 * Free the range of realtime blocks.
2260 error = xfs_rtfree_range(mp, tp, bno, len, &sumbp, &sb);
2265 * Mark more blocks free in the superblock.
2267 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, (long)len);
2269 * If we've now freed all the blocks, reset the file sequence
2272 if (tp->t_frextents_delta + mp->m_sb.sb_frextents ==
2273 mp->m_sb.sb_rextents) {
2274 if (!(ip->i_d.di_flags & XFS_DIFLAG_NEWRTBM))
2275 ip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
2276 *(__uint64_t *)&ip->i_d.di_atime = 0;
2277 xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
2283 * Initialize realtime fields in the mount structure.
2287 xfs_mount_t *mp) /* file system mount structure */
2289 xfs_buf_t *bp; /* buffer for last block of subvolume */
2290 xfs_daddr_t d; /* address of last block of subvolume */
2291 int error; /* error return value */
2292 xfs_sb_t *sbp; /* filesystem superblock copy in mount */
2295 if (sbp->sb_rblocks == 0)
2297 if (mp->m_rtdev_targp == NULL) {
2299 "XFS: This filesystem has a realtime volume, use rtdev=device option");
2300 return XFS_ERROR(ENODEV);
2302 mp->m_rsumlevels = sbp->sb_rextslog + 1;
2304 (uint)sizeof(xfs_suminfo_t) * mp->m_rsumlevels *
2306 mp->m_rsumsize = roundup(mp->m_rsumsize, sbp->sb_blocksize);
2307 mp->m_rbmip = mp->m_rsumip = NULL;
2309 * Check that the realtime section is an ok size.
2311 d = (xfs_daddr_t)XFS_FSB_TO_BB(mp, mp->m_sb.sb_rblocks);
2312 if (XFS_BB_TO_FSB(mp, d) != mp->m_sb.sb_rblocks) {
2313 cmn_err(CE_WARN, "XFS: realtime mount -- %llu != %llu",
2314 (unsigned long long) XFS_BB_TO_FSB(mp, d),
2315 (unsigned long long) mp->m_sb.sb_rblocks);
2316 return XFS_ERROR(E2BIG);
2318 error = xfs_read_buf(mp, mp->m_rtdev_targp,
2319 d - XFS_FSB_TO_BB(mp, 1),
2320 XFS_FSB_TO_BB(mp, 1), 0, &bp);
2323 "XFS: realtime mount -- xfs_read_buf failed, returned %d", error);
2324 if (error == ENOSPC)
2325 return XFS_ERROR(E2BIG);
2333 * Get the bitmap and summary inodes into the mount structure
2338 xfs_mount_t *mp) /* file system mount structure */
2340 int error; /* error return value */
2344 if (sbp->sb_rbmino == NULLFSINO)
2346 error = xfs_iget(mp, NULL, sbp->sb_rbmino, 0, 0, &mp->m_rbmip, 0);
2349 ASSERT(mp->m_rbmip != NULL);
2350 ASSERT(sbp->sb_rsumino != NULLFSINO);
2351 error = xfs_iget(mp, NULL, sbp->sb_rsumino, 0, 0, &mp->m_rsumip, 0);
2353 VN_RELE(XFS_ITOV(mp->m_rbmip));
2356 ASSERT(mp->m_rsumip != NULL);
2361 * Pick an extent for allocation at the start of a new realtime file.
2362 * Use the sequence number stored in the atime field of the bitmap inode.
2363 * Translate this to a fraction of the rtextents, and return the product
2364 * of rtextents and the fraction.
2365 * The fraction sequence is 0, 1/2, 1/4, 3/4, 1/8, ..., 7/8, 1/16, ...
2369 xfs_mount_t *mp, /* file system mount point */
2370 xfs_trans_t *tp, /* transaction pointer */
2371 xfs_extlen_t len, /* allocation length (rtextents) */
2372 xfs_rtblock_t *pick) /* result rt extent */
2374 xfs_rtblock_t b; /* result block */
2375 int error; /* error return value */
2376 xfs_inode_t *ip; /* bitmap incore inode */
2377 int log2; /* log of sequence number */
2378 __uint64_t resid; /* residual after log removed */
2379 __uint64_t seq; /* sequence number of file creation */
2380 __uint64_t *seqp; /* pointer to seqno in inode */
2382 error = xfs_trans_iget(mp, tp, mp->m_sb.sb_rbmino, 0, XFS_ILOCK_EXCL, &ip);
2385 ASSERT(ip == mp->m_rbmip);
2386 seqp = (__uint64_t *)&ip->i_d.di_atime;
2387 if (!(ip->i_d.di_flags & XFS_DIFLAG_NEWRTBM)) {
2388 ip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM;
2392 if ((log2 = xfs_highbit64(seq)) == -1)
2395 resid = seq - (1ULL << log2);
2396 b = (mp->m_sb.sb_rextents * ((resid << 1) + 1ULL)) >>
2398 if (b >= mp->m_sb.sb_rextents)
2399 b = do_mod(b, mp->m_sb.sb_rextents);
2400 if (b + len > mp->m_sb.sb_rextents)
2401 b = mp->m_sb.sb_rextents - len;
2404 xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
2411 * Debug code: print out the value of a range in the bitmap.
2415 xfs_mount_t *mp, /* file system mount structure */
2416 xfs_trans_t *tp, /* transaction pointer */
2417 xfs_rtblock_t start, /* starting block to print */
2418 xfs_extlen_t len) /* length to print */
2420 xfs_extlen_t i; /* block number in the extent */
2422 printk("%Ld: ", (long long)start);
2423 for (i = 0; i < len; i++)
2424 printk("%d", xfs_rtcheck_bit(mp, tp, start + i, 1));
2429 * Debug code: print the summary file.
2432 xfs_rtprint_summary(
2433 xfs_mount_t *mp, /* file system mount structure */
2434 xfs_trans_t *tp) /* transaction pointer */
2436 xfs_suminfo_t c; /* summary data */
2437 xfs_rtblock_t i; /* bitmap block number */
2438 int l; /* summary information level */
2439 int p; /* flag for printed anything */
2440 xfs_fsblock_t sb; /* summary block number */
2441 xfs_buf_t *sumbp; /* summary block buffer */
2444 for (l = 0; l < mp->m_rsumlevels; l++) {
2445 for (p = 0, i = 0; i < mp->m_sb.sb_rbmblocks; i++) {
2446 (void)xfs_rtget_summary(mp, tp, l, i, &sumbp, &sb, &c);
2449 printk("%Ld-%Ld:", 1LL << l,
2450 XFS_RTMIN((1LL << l) +
2452 mp->m_sb.sb_rextents));
2455 printk(" %Ld:%d", (long long)i, c);
2462 xfs_trans_brelse(tp, sumbp);