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