]> CyberLeo.Net >> Repos - FreeBSD/stable/10.git/blob - sys/ufs/ffs/ffs_balloc.c
MFC r304229:
[FreeBSD/stable/10.git] / sys / ufs / ffs / ffs_balloc.c
1 /*-
2  * Copyright (c) 2002 Networks Associates Technology, Inc.
3  * All rights reserved.
4  *
5  * This software was developed for the FreeBSD Project by Marshall
6  * Kirk McKusick and Network Associates Laboratories, the Security
7  * Research Division of Network Associates, Inc. under DARPA/SPAWAR
8  * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS
9  * research program
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in the
18  *    documentation and/or other materials provided with the distribution.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  *
32  * Copyright (c) 1982, 1986, 1989, 1993
33  *      The Regents of the University of California.  All rights reserved.
34  *
35  * Redistribution and use in source and binary forms, with or without
36  * modification, are permitted provided that the following conditions
37  * are met:
38  * 1. Redistributions of source code must retain the above copyright
39  *    notice, this list of conditions and the following disclaimer.
40  * 2. Redistributions in binary form must reproduce the above copyright
41  *    notice, this list of conditions and the following disclaimer in the
42  *    documentation and/or other materials provided with the distribution.
43  * 4. Neither the name of the University nor the names of its contributors
44  *    may be used to endorse or promote products derived from this software
45  *    without specific prior written permission.
46  *
47  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
48  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
49  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
50  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
51  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
52  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
53  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
54  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
55  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
57  * SUCH DAMAGE.
58  *
59  *      @(#)ffs_balloc.c        8.8 (Berkeley) 6/16/95
60  */
61
62 #include <sys/cdefs.h>
63 __FBSDID("$FreeBSD$");
64
65 #include <sys/param.h>
66 #include <sys/systm.h>
67 #include <sys/bio.h>
68 #include <sys/buf.h>
69 #include <sys/lock.h>
70 #include <sys/mount.h>
71 #include <sys/vnode.h>
72
73 #include <ufs/ufs/quota.h>
74 #include <ufs/ufs/inode.h>
75 #include <ufs/ufs/ufs_extern.h>
76 #include <ufs/ufs/extattr.h>
77 #include <ufs/ufs/ufsmount.h>
78
79 #include <ufs/ffs/fs.h>
80 #include <ufs/ffs/ffs_extern.h>
81
82 /*
83  * Balloc defines the structure of filesystem storage
84  * by allocating the physical blocks on a device given
85  * the inode and the logical block number in a file.
86  * This is the allocation strategy for UFS1. Below is
87  * the allocation strategy for UFS2.
88  */
89 int
90 ffs_balloc_ufs1(struct vnode *vp, off_t startoffset, int size,
91     struct ucred *cred, int flags, struct buf **bpp)
92 {
93         struct inode *ip;
94         struct ufs1_dinode *dp;
95         ufs_lbn_t lbn, lastlbn;
96         struct fs *fs;
97         ufs1_daddr_t nb;
98         struct buf *bp, *nbp;
99         struct ufsmount *ump;
100         struct indir indirs[NIADDR + 2];
101         int deallocated, osize, nsize, num, i, error;
102         ufs2_daddr_t newb;
103         ufs1_daddr_t *bap, pref;
104         ufs1_daddr_t *allocib, *blkp, *allocblk, allociblk[NIADDR + 1];
105         ufs2_daddr_t *lbns_remfree, lbns[NIADDR + 1];
106         int unwindidx = -1;
107         int saved_inbdflush;
108         static struct timeval lastfail;
109         static int curfail;
110         int gbflags, reclaimed;
111
112         ip = VTOI(vp);
113         dp = ip->i_din1;
114         fs = ip->i_fs;
115         ump = ip->i_ump;
116         lbn = lblkno(fs, startoffset);
117         size = blkoff(fs, startoffset) + size;
118         reclaimed = 0;
119         if (size > fs->fs_bsize)
120                 panic("ffs_balloc_ufs1: blk too big");
121         *bpp = NULL;
122         if (flags & IO_EXT)
123                 return (EOPNOTSUPP);
124         if (lbn < 0)
125                 return (EFBIG);
126         gbflags = (flags & BA_UNMAPPED) != 0 ? GB_UNMAPPED : 0;
127
128         if (DOINGSOFTDEP(vp))
129                 softdep_prealloc(vp, MNT_WAIT);
130         /*
131          * If the next write will extend the file into a new block,
132          * and the file is currently composed of a fragment
133          * this fragment has to be extended to be a full block.
134          */
135         lastlbn = lblkno(fs, ip->i_size);
136         if (lastlbn < NDADDR && lastlbn < lbn) {
137                 nb = lastlbn;
138                 osize = blksize(fs, ip, nb);
139                 if (osize < fs->fs_bsize && osize > 0) {
140                         UFS_LOCK(ump);
141                         error = ffs_realloccg(ip, nb, dp->di_db[nb],
142                            ffs_blkpref_ufs1(ip, lastlbn, (int)nb,
143                            &dp->di_db[0]), osize, (int)fs->fs_bsize, flags,
144                            cred, &bp);
145                         if (error)
146                                 return (error);
147                         if (DOINGSOFTDEP(vp))
148                                 softdep_setup_allocdirect(ip, nb,
149                                     dbtofsb(fs, bp->b_blkno), dp->di_db[nb],
150                                     fs->fs_bsize, osize, bp);
151                         ip->i_size = smalllblktosize(fs, nb + 1);
152                         dp->di_size = ip->i_size;
153                         dp->di_db[nb] = dbtofsb(fs, bp->b_blkno);
154                         ip->i_flag |= IN_CHANGE | IN_UPDATE;
155                         if (flags & IO_SYNC)
156                                 bwrite(bp);
157                         else
158                                 bawrite(bp);
159                 }
160         }
161         /*
162          * The first NDADDR blocks are direct blocks
163          */
164         if (lbn < NDADDR) {
165                 if (flags & BA_METAONLY)
166                         panic("ffs_balloc_ufs1: BA_METAONLY for direct block");
167                 nb = dp->di_db[lbn];
168                 if (nb != 0 && ip->i_size >= smalllblktosize(fs, lbn + 1)) {
169                         error = bread(vp, lbn, fs->fs_bsize, NOCRED, &bp);
170                         if (error) {
171                                 brelse(bp);
172                                 return (error);
173                         }
174                         bp->b_blkno = fsbtodb(fs, nb);
175                         *bpp = bp;
176                         return (0);
177                 }
178                 if (nb != 0) {
179                         /*
180                          * Consider need to reallocate a fragment.
181                          */
182                         osize = fragroundup(fs, blkoff(fs, ip->i_size));
183                         nsize = fragroundup(fs, size);
184                         if (nsize <= osize) {
185                                 error = bread(vp, lbn, osize, NOCRED, &bp);
186                                 if (error) {
187                                         brelse(bp);
188                                         return (error);
189                                 }
190                                 bp->b_blkno = fsbtodb(fs, nb);
191                         } else {
192                                 UFS_LOCK(ump);
193                                 error = ffs_realloccg(ip, lbn, dp->di_db[lbn],
194                                     ffs_blkpref_ufs1(ip, lbn, (int)lbn,
195                                     &dp->di_db[0]), osize, nsize, flags,
196                                     cred, &bp);
197                                 if (error)
198                                         return (error);
199                                 if (DOINGSOFTDEP(vp))
200                                         softdep_setup_allocdirect(ip, lbn,
201                                             dbtofsb(fs, bp->b_blkno), nb,
202                                             nsize, osize, bp);
203                         }
204                 } else {
205                         if (ip->i_size < smalllblktosize(fs, lbn + 1))
206                                 nsize = fragroundup(fs, size);
207                         else
208                                 nsize = fs->fs_bsize;
209                         UFS_LOCK(ump);
210                         error = ffs_alloc(ip, lbn,
211                             ffs_blkpref_ufs1(ip, lbn, (int)lbn, &dp->di_db[0]),
212                             nsize, flags, cred, &newb);
213                         if (error)
214                                 return (error);
215                         bp = getblk(vp, lbn, nsize, 0, 0, gbflags);
216                         bp->b_blkno = fsbtodb(fs, newb);
217                         if (flags & BA_CLRBUF)
218                                 vfs_bio_clrbuf(bp);
219                         if (DOINGSOFTDEP(vp))
220                                 softdep_setup_allocdirect(ip, lbn, newb, 0,
221                                     nsize, 0, bp);
222                 }
223                 dp->di_db[lbn] = dbtofsb(fs, bp->b_blkno);
224                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
225                 *bpp = bp;
226                 return (0);
227         }
228         /*
229          * Determine the number of levels of indirection.
230          */
231         pref = 0;
232         if ((error = ufs_getlbns(vp, lbn, indirs, &num)) != 0)
233                 return(error);
234 #ifdef INVARIANTS
235         if (num < 1)
236                 panic ("ffs_balloc_ufs1: ufs_getlbns returned indirect block");
237 #endif
238         saved_inbdflush = curthread_pflags_set(TDP_INBDFLUSH);
239         /*
240          * Fetch the first indirect block allocating if necessary.
241          */
242         --num;
243         nb = dp->di_ib[indirs[0].in_off];
244         allocib = NULL;
245         allocblk = allociblk;
246         lbns_remfree = lbns;
247         if (nb == 0) {
248                 UFS_LOCK(ump);
249                 pref = ffs_blkpref_ufs1(ip, lbn, -indirs[0].in_off - 1,
250                     (ufs1_daddr_t *)0);
251                 if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
252                     flags, cred, &newb)) != 0) {
253                         curthread_pflags_restore(saved_inbdflush);
254                         return (error);
255                 }
256                 pref = newb + fs->fs_frag;
257                 nb = newb;
258                 MPASS(allocblk < allociblk + nitems(allociblk));
259                 MPASS(lbns_remfree < lbns + nitems(lbns));
260                 *allocblk++ = nb;
261                 *lbns_remfree++ = indirs[1].in_lbn;
262                 bp = getblk(vp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, gbflags);
263                 bp->b_blkno = fsbtodb(fs, nb);
264                 vfs_bio_clrbuf(bp);
265                 if (DOINGSOFTDEP(vp)) {
266                         softdep_setup_allocdirect(ip, NDADDR + indirs[0].in_off,
267                             newb, 0, fs->fs_bsize, 0, bp);
268                         bdwrite(bp);
269                 } else {
270                         /*
271                          * Write synchronously so that indirect blocks
272                          * never point at garbage.
273                          */
274                         if (DOINGASYNC(vp))
275                                 bdwrite(bp);
276                         else if ((error = bwrite(bp)) != 0)
277                                 goto fail;
278                 }
279                 allocib = &dp->di_ib[indirs[0].in_off];
280                 *allocib = nb;
281                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
282         }
283         /*
284          * Fetch through the indirect blocks, allocating as necessary.
285          */
286 retry:
287         for (i = 1;;) {
288                 error = bread(vp,
289                     indirs[i].in_lbn, (int)fs->fs_bsize, NOCRED, &bp);
290                 if (error) {
291                         brelse(bp);
292                         goto fail;
293                 }
294                 bap = (ufs1_daddr_t *)bp->b_data;
295                 nb = bap[indirs[i].in_off];
296                 if (i == num)
297                         break;
298                 i += 1;
299                 if (nb != 0) {
300                         bqrelse(bp);
301                         continue;
302                 }
303                 UFS_LOCK(ump);
304                 /*
305                  * If parent indirect has just been allocated, try to cluster
306                  * immediately following it.
307                  */
308                 if (pref == 0)
309                         pref = ffs_blkpref_ufs1(ip, lbn, i - num - 1,
310                             (ufs1_daddr_t *)0);
311                 if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
312                     flags | IO_BUFLOCKED, cred, &newb)) != 0) {
313                         brelse(bp);
314                         if (DOINGSOFTDEP(vp) && ++reclaimed == 1) {
315                                 UFS_LOCK(ump);
316                                 softdep_request_cleanup(fs, vp, cred,
317                                     FLUSH_BLOCKS_WAIT);
318                                 UFS_UNLOCK(ump);
319                                 goto retry;
320                         }
321                         if (ppsratecheck(&lastfail, &curfail, 1)) {
322                                 ffs_fserr(fs, ip->i_number, "filesystem full");
323                                 uprintf("\n%s: write failed, filesystem "
324                                     "is full\n", fs->fs_fsmnt);
325                         }
326                         goto fail;
327                 }
328                 pref = newb + fs->fs_frag;
329                 nb = newb;
330                 MPASS(allocblk < allociblk + nitems(allociblk));
331                 MPASS(lbns_remfree < lbns + nitems(lbns));
332                 *allocblk++ = nb;
333                 *lbns_remfree++ = indirs[i].in_lbn;
334                 nbp = getblk(vp, indirs[i].in_lbn, fs->fs_bsize, 0, 0, 0);
335                 nbp->b_blkno = fsbtodb(fs, nb);
336                 vfs_bio_clrbuf(nbp);
337                 if (DOINGSOFTDEP(vp)) {
338                         softdep_setup_allocindir_meta(nbp, ip, bp,
339                             indirs[i - 1].in_off, nb);
340                         bdwrite(nbp);
341                 } else {
342                         /*
343                          * Write synchronously so that indirect blocks
344                          * never point at garbage.
345                          */
346                         if ((error = bwrite(nbp)) != 0) {
347                                 brelse(bp);
348                                 goto fail;
349                         }
350                 }
351                 bap[indirs[i - 1].in_off] = nb;
352                 if (allocib == NULL && unwindidx < 0)
353                         unwindidx = i - 1;
354                 /*
355                  * If required, write synchronously, otherwise use
356                  * delayed write.
357                  */
358                 if (flags & IO_SYNC) {
359                         bwrite(bp);
360                 } else {
361                         if (bp->b_bufsize == fs->fs_bsize)
362                                 bp->b_flags |= B_CLUSTEROK;
363                         bdwrite(bp);
364                 }
365         }
366         /*
367          * If asked only for the indirect block, then return it.
368          */
369         if (flags & BA_METAONLY) {
370                 curthread_pflags_restore(saved_inbdflush);
371                 *bpp = bp;
372                 return (0);
373         }
374         /*
375          * Get the data block, allocating if necessary.
376          */
377         if (nb == 0) {
378                 UFS_LOCK(ump);
379                 /*
380                  * If allocating metadata at the front of the cylinder
381                  * group and parent indirect block has just been allocated,
382                  * then cluster next to it if it is the first indirect in
383                  * the file. Otherwise it has been allocated in the metadata
384                  * area, so we want to find our own place out in the data area.
385                  */
386                 if (pref == 0 || (lbn > NDADDR && fs->fs_metaspace != 0))
387                         pref = ffs_blkpref_ufs1(ip, lbn, indirs[i].in_off,
388                             &bap[0]);
389                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
390                     flags | IO_BUFLOCKED, cred, &newb);
391                 if (error) {
392                         brelse(bp);
393                         if (DOINGSOFTDEP(vp) && ++reclaimed == 1) {
394                                 UFS_LOCK(ump);
395                                 softdep_request_cleanup(fs, vp, cred,
396                                     FLUSH_BLOCKS_WAIT);
397                                 UFS_UNLOCK(ump);
398                                 goto retry;
399                         }
400                         if (ppsratecheck(&lastfail, &curfail, 1)) {
401                                 ffs_fserr(fs, ip->i_number, "filesystem full");
402                                 uprintf("\n%s: write failed, filesystem "
403                                     "is full\n", fs->fs_fsmnt);
404                         }
405                         goto fail;
406                 }
407                 nb = newb;
408                 MPASS(allocblk < allociblk + nitems(allociblk));
409                 MPASS(lbns_remfree < lbns + nitems(lbns));
410                 *allocblk++ = nb;
411                 *lbns_remfree++ = lbn;
412                 nbp = getblk(vp, lbn, fs->fs_bsize, 0, 0, gbflags);
413                 nbp->b_blkno = fsbtodb(fs, nb);
414                 if (flags & BA_CLRBUF)
415                         vfs_bio_clrbuf(nbp);
416                 if (DOINGSOFTDEP(vp))
417                         softdep_setup_allocindir_page(ip, lbn, bp,
418                             indirs[i].in_off, nb, 0, nbp);
419                 bap[indirs[i].in_off] = nb;
420                 /*
421                  * If required, write synchronously, otherwise use
422                  * delayed write.
423                  */
424                 if (flags & IO_SYNC) {
425                         bwrite(bp);
426                 } else {
427                         if (bp->b_bufsize == fs->fs_bsize)
428                                 bp->b_flags |= B_CLUSTEROK;
429                         bdwrite(bp);
430                 }
431                 curthread_pflags_restore(saved_inbdflush);
432                 *bpp = nbp;
433                 return (0);
434         }
435         brelse(bp);
436         if (flags & BA_CLRBUF) {
437                 int seqcount = (flags & BA_SEQMASK) >> BA_SEQSHIFT;
438                 if (seqcount != 0 &&
439                     (vp->v_mount->mnt_flag & MNT_NOCLUSTERR) == 0 &&
440                     !(vm_page_count_severe() || buf_dirty_count_severe())) {
441                         error = cluster_read(vp, ip->i_size, lbn,
442                             (int)fs->fs_bsize, NOCRED,
443                             MAXBSIZE, seqcount, gbflags, &nbp);
444                 } else {
445                         error = bread_gb(vp, lbn, (int)fs->fs_bsize, NOCRED,
446                             gbflags, &nbp);
447                 }
448                 if (error) {
449                         brelse(nbp);
450                         goto fail;
451                 }
452         } else {
453                 nbp = getblk(vp, lbn, fs->fs_bsize, 0, 0, gbflags);
454                 nbp->b_blkno = fsbtodb(fs, nb);
455         }
456         curthread_pflags_restore(saved_inbdflush);
457         *bpp = nbp;
458         return (0);
459 fail:
460         curthread_pflags_restore(saved_inbdflush);
461         /*
462          * If we have failed to allocate any blocks, simply return the error.
463          * This is the usual case and avoids the need to fsync the file.
464          */
465         if (allocblk == allociblk && allocib == NULL && unwindidx == -1)
466                 return (error);
467         /*
468          * If we have failed part way through block allocation, we
469          * have to deallocate any indirect blocks that we have allocated.
470          * We have to fsync the file before we start to get rid of all
471          * of its dependencies so that we do not leave them dangling.
472          * We have to sync it at the end so that the soft updates code
473          * does not find any untracked changes. Although this is really
474          * slow, running out of disk space is not expected to be a common
475          * occurrence. The error return from fsync is ignored as we already
476          * have an error to return to the user.
477          *
478          * XXX Still have to journal the free below
479          */
480         (void) ffs_syncvnode(vp, MNT_WAIT, 0);
481         for (deallocated = 0, blkp = allociblk, lbns_remfree = lbns;
482              blkp < allocblk; blkp++, lbns_remfree++) {
483                 /*
484                  * We shall not leave the freed blocks on the vnode
485                  * buffer object lists.
486                  */
487                 bp = getblk(vp, *lbns_remfree, fs->fs_bsize, 0, 0,
488                     GB_NOCREAT | GB_UNMAPPED);
489                 if (bp != NULL) {
490                         bp->b_flags |= (B_INVAL | B_RELBUF);
491                         bp->b_flags &= ~B_ASYNC;
492                         brelse(bp);
493                 }
494                 deallocated += fs->fs_bsize;
495         }
496         if (allocib != NULL) {
497                 *allocib = 0;
498         } else if (unwindidx >= 0) {
499                 int r;
500
501                 r = bread(vp, indirs[unwindidx].in_lbn, 
502                     (int)fs->fs_bsize, NOCRED, &bp);
503                 if (r) {
504                         panic("Could not unwind indirect block, error %d", r);
505                         brelse(bp);
506                 } else {
507                         bap = (ufs1_daddr_t *)bp->b_data;
508                         bap[indirs[unwindidx].in_off] = 0;
509                         if (flags & IO_SYNC) {
510                                 bwrite(bp);
511                         } else {
512                                 if (bp->b_bufsize == fs->fs_bsize)
513                                         bp->b_flags |= B_CLUSTEROK;
514                                 bdwrite(bp);
515                         }
516                 }
517         }
518         if (deallocated) {
519 #ifdef QUOTA
520                 /*
521                  * Restore user's disk quota because allocation failed.
522                  */
523                 (void) chkdq(ip, -btodb(deallocated), cred, FORCE);
524 #endif
525                 dp->di_blocks -= btodb(deallocated);
526                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
527         }
528         (void) ffs_syncvnode(vp, MNT_WAIT, 0);
529         /*
530          * After the buffers are invalidated and on-disk pointers are
531          * cleared, free the blocks.
532          */
533         for (blkp = allociblk; blkp < allocblk; blkp++) {
534                 ffs_blkfree(ump, fs, ip->i_devvp, *blkp, fs->fs_bsize,
535                     ip->i_number, vp->v_type, NULL);
536         }
537         return (error);
538 }
539
540 /*
541  * Balloc defines the structure of file system storage
542  * by allocating the physical blocks on a device given
543  * the inode and the logical block number in a file.
544  * This is the allocation strategy for UFS2. Above is
545  * the allocation strategy for UFS1.
546  */
547 int
548 ffs_balloc_ufs2(struct vnode *vp, off_t startoffset, int size,
549     struct ucred *cred, int flags, struct buf **bpp)
550 {
551         struct inode *ip;
552         struct ufs2_dinode *dp;
553         ufs_lbn_t lbn, lastlbn;
554         struct fs *fs;
555         struct buf *bp, *nbp;
556         struct ufsmount *ump;
557         struct indir indirs[NIADDR + 2];
558         ufs2_daddr_t nb, newb, *bap, pref;
559         ufs2_daddr_t *allocib, *blkp, *allocblk, allociblk[NIADDR + 1];
560         ufs2_daddr_t *lbns_remfree, lbns[NIADDR + 1];
561         int deallocated, osize, nsize, num, i, error;
562         int unwindidx = -1;
563         int saved_inbdflush;
564         static struct timeval lastfail;
565         static int curfail;
566         int gbflags, reclaimed;
567
568         ip = VTOI(vp);
569         dp = ip->i_din2;
570         fs = ip->i_fs;
571         ump = ip->i_ump;
572         lbn = lblkno(fs, startoffset);
573         size = blkoff(fs, startoffset) + size;
574         reclaimed = 0;
575         if (size > fs->fs_bsize)
576                 panic("ffs_balloc_ufs2: blk too big");
577         *bpp = NULL;
578         if (lbn < 0)
579                 return (EFBIG);
580         gbflags = (flags & BA_UNMAPPED) != 0 ? GB_UNMAPPED : 0;
581
582         if (DOINGSOFTDEP(vp))
583                 softdep_prealloc(vp, MNT_WAIT);
584         
585         /*
586          * Check for allocating external data.
587          */
588         if (flags & IO_EXT) {
589                 if (lbn >= NXADDR)
590                         return (EFBIG);
591                 /*
592                  * If the next write will extend the data into a new block,
593                  * and the data is currently composed of a fragment
594                  * this fragment has to be extended to be a full block.
595                  */
596                 lastlbn = lblkno(fs, dp->di_extsize);
597                 if (lastlbn < lbn) {
598                         nb = lastlbn;
599                         osize = sblksize(fs, dp->di_extsize, nb);
600                         if (osize < fs->fs_bsize && osize > 0) {
601                                 UFS_LOCK(ump);
602                                 error = ffs_realloccg(ip, -1 - nb,
603                                     dp->di_extb[nb],
604                                     ffs_blkpref_ufs2(ip, lastlbn, (int)nb,
605                                     &dp->di_extb[0]), osize,
606                                     (int)fs->fs_bsize, flags, cred, &bp);
607                                 if (error)
608                                         return (error);
609                                 if (DOINGSOFTDEP(vp))
610                                         softdep_setup_allocext(ip, nb,
611                                             dbtofsb(fs, bp->b_blkno),
612                                             dp->di_extb[nb],
613                                             fs->fs_bsize, osize, bp);
614                                 dp->di_extsize = smalllblktosize(fs, nb + 1);
615                                 dp->di_extb[nb] = dbtofsb(fs, bp->b_blkno);
616                                 bp->b_xflags |= BX_ALTDATA;
617                                 ip->i_flag |= IN_CHANGE;
618                                 if (flags & IO_SYNC)
619                                         bwrite(bp);
620                                 else
621                                         bawrite(bp);
622                         }
623                 }
624                 /*
625                  * All blocks are direct blocks
626                  */
627                 if (flags & BA_METAONLY)
628                         panic("ffs_balloc_ufs2: BA_METAONLY for ext block");
629                 nb = dp->di_extb[lbn];
630                 if (nb != 0 && dp->di_extsize >= smalllblktosize(fs, lbn + 1)) {
631                         error = bread_gb(vp, -1 - lbn, fs->fs_bsize, NOCRED,
632                             gbflags, &bp);
633                         if (error) {
634                                 brelse(bp);
635                                 return (error);
636                         }
637                         bp->b_blkno = fsbtodb(fs, nb);
638                         bp->b_xflags |= BX_ALTDATA;
639                         *bpp = bp;
640                         return (0);
641                 }
642                 if (nb != 0) {
643                         /*
644                          * Consider need to reallocate a fragment.
645                          */
646                         osize = fragroundup(fs, blkoff(fs, dp->di_extsize));
647                         nsize = fragroundup(fs, size);
648                         if (nsize <= osize) {
649                                 error = bread_gb(vp, -1 - lbn, osize, NOCRED,
650                                     gbflags, &bp);
651                                 if (error) {
652                                         brelse(bp);
653                                         return (error);
654                                 }
655                                 bp->b_blkno = fsbtodb(fs, nb);
656                                 bp->b_xflags |= BX_ALTDATA;
657                         } else {
658                                 UFS_LOCK(ump);
659                                 error = ffs_realloccg(ip, -1 - lbn,
660                                     dp->di_extb[lbn],
661                                     ffs_blkpref_ufs2(ip, lbn, (int)lbn,
662                                     &dp->di_extb[0]), osize, nsize, flags,
663                                     cred, &bp);
664                                 if (error)
665                                         return (error);
666                                 bp->b_xflags |= BX_ALTDATA;
667                                 if (DOINGSOFTDEP(vp))
668                                         softdep_setup_allocext(ip, lbn,
669                                             dbtofsb(fs, bp->b_blkno), nb,
670                                             nsize, osize, bp);
671                         }
672                 } else {
673                         if (dp->di_extsize < smalllblktosize(fs, lbn + 1))
674                                 nsize = fragroundup(fs, size);
675                         else
676                                 nsize = fs->fs_bsize;
677                         UFS_LOCK(ump);
678                         error = ffs_alloc(ip, lbn,
679                            ffs_blkpref_ufs2(ip, lbn, (int)lbn, &dp->di_extb[0]),
680                            nsize, flags, cred, &newb);
681                         if (error)
682                                 return (error);
683                         bp = getblk(vp, -1 - lbn, nsize, 0, 0, gbflags);
684                         bp->b_blkno = fsbtodb(fs, newb);
685                         bp->b_xflags |= BX_ALTDATA;
686                         if (flags & BA_CLRBUF)
687                                 vfs_bio_clrbuf(bp);
688                         if (DOINGSOFTDEP(vp))
689                                 softdep_setup_allocext(ip, lbn, newb, 0,
690                                     nsize, 0, bp);
691                 }
692                 dp->di_extb[lbn] = dbtofsb(fs, bp->b_blkno);
693                 ip->i_flag |= IN_CHANGE;
694                 *bpp = bp;
695                 return (0);
696         }
697         /*
698          * If the next write will extend the file into a new block,
699          * and the file is currently composed of a fragment
700          * this fragment has to be extended to be a full block.
701          */
702         lastlbn = lblkno(fs, ip->i_size);
703         if (lastlbn < NDADDR && lastlbn < lbn) {
704                 nb = lastlbn;
705                 osize = blksize(fs, ip, nb);
706                 if (osize < fs->fs_bsize && osize > 0) {
707                         UFS_LOCK(ump);
708                         error = ffs_realloccg(ip, nb, dp->di_db[nb],
709                             ffs_blkpref_ufs2(ip, lastlbn, (int)nb,
710                             &dp->di_db[0]), osize, (int)fs->fs_bsize,
711                             flags, cred, &bp);
712                         if (error)
713                                 return (error);
714                         if (DOINGSOFTDEP(vp))
715                                 softdep_setup_allocdirect(ip, nb,
716                                     dbtofsb(fs, bp->b_blkno),
717                                     dp->di_db[nb],
718                                     fs->fs_bsize, osize, bp);
719                         ip->i_size = smalllblktosize(fs, nb + 1);
720                         dp->di_size = ip->i_size;
721                         dp->di_db[nb] = dbtofsb(fs, bp->b_blkno);
722                         ip->i_flag |= IN_CHANGE | IN_UPDATE;
723                         if (flags & IO_SYNC)
724                                 bwrite(bp);
725                         else
726                                 bawrite(bp);
727                 }
728         }
729         /*
730          * The first NDADDR blocks are direct blocks
731          */
732         if (lbn < NDADDR) {
733                 if (flags & BA_METAONLY)
734                         panic("ffs_balloc_ufs2: BA_METAONLY for direct block");
735                 nb = dp->di_db[lbn];
736                 if (nb != 0 && ip->i_size >= smalllblktosize(fs, lbn + 1)) {
737                         error = bread_gb(vp, lbn, fs->fs_bsize, NOCRED,
738                             gbflags, &bp);
739                         if (error) {
740                                 brelse(bp);
741                                 return (error);
742                         }
743                         bp->b_blkno = fsbtodb(fs, nb);
744                         *bpp = bp;
745                         return (0);
746                 }
747                 if (nb != 0) {
748                         /*
749                          * Consider need to reallocate a fragment.
750                          */
751                         osize = fragroundup(fs, blkoff(fs, ip->i_size));
752                         nsize = fragroundup(fs, size);
753                         if (nsize <= osize) {
754                                 error = bread_gb(vp, lbn, osize, NOCRED,
755                                     gbflags, &bp);
756                                 if (error) {
757                                         brelse(bp);
758                                         return (error);
759                                 }
760                                 bp->b_blkno = fsbtodb(fs, nb);
761                         } else {
762                                 UFS_LOCK(ump);
763                                 error = ffs_realloccg(ip, lbn, dp->di_db[lbn],
764                                     ffs_blkpref_ufs2(ip, lbn, (int)lbn,
765                                     &dp->di_db[0]), osize, nsize, flags,
766                                     cred, &bp);
767                                 if (error)
768                                         return (error);
769                                 if (DOINGSOFTDEP(vp))
770                                         softdep_setup_allocdirect(ip, lbn,
771                                             dbtofsb(fs, bp->b_blkno), nb,
772                                             nsize, osize, bp);
773                         }
774                 } else {
775                         if (ip->i_size < smalllblktosize(fs, lbn + 1))
776                                 nsize = fragroundup(fs, size);
777                         else
778                                 nsize = fs->fs_bsize;
779                         UFS_LOCK(ump);
780                         error = ffs_alloc(ip, lbn,
781                             ffs_blkpref_ufs2(ip, lbn, (int)lbn,
782                                 &dp->di_db[0]), nsize, flags, cred, &newb);
783                         if (error)
784                                 return (error);
785                         bp = getblk(vp, lbn, nsize, 0, 0, gbflags);
786                         bp->b_blkno = fsbtodb(fs, newb);
787                         if (flags & BA_CLRBUF)
788                                 vfs_bio_clrbuf(bp);
789                         if (DOINGSOFTDEP(vp))
790                                 softdep_setup_allocdirect(ip, lbn, newb, 0,
791                                     nsize, 0, bp);
792                 }
793                 dp->di_db[lbn] = dbtofsb(fs, bp->b_blkno);
794                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
795                 *bpp = bp;
796                 return (0);
797         }
798         /*
799          * Determine the number of levels of indirection.
800          */
801         pref = 0;
802         if ((error = ufs_getlbns(vp, lbn, indirs, &num)) != 0)
803                 return(error);
804 #ifdef INVARIANTS
805         if (num < 1)
806                 panic ("ffs_balloc_ufs2: ufs_getlbns returned indirect block");
807 #endif
808         saved_inbdflush = curthread_pflags_set(TDP_INBDFLUSH);
809         /*
810          * Fetch the first indirect block allocating if necessary.
811          */
812         --num;
813         nb = dp->di_ib[indirs[0].in_off];
814         allocib = NULL;
815         allocblk = allociblk;
816         lbns_remfree = lbns;
817         if (nb == 0) {
818                 UFS_LOCK(ump);
819                 pref = ffs_blkpref_ufs2(ip, lbn, -indirs[0].in_off - 1,
820                     (ufs2_daddr_t *)0);
821                 if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
822                     flags, cred, &newb)) != 0) {
823                         curthread_pflags_restore(saved_inbdflush);
824                         return (error);
825                 }
826                 pref = newb + fs->fs_frag;
827                 nb = newb;
828                 MPASS(allocblk < allociblk + nitems(allociblk));
829                 MPASS(lbns_remfree < lbns + nitems(lbns));
830                 *allocblk++ = nb;
831                 *lbns_remfree++ = indirs[1].in_lbn;
832                 bp = getblk(vp, indirs[1].in_lbn, fs->fs_bsize, 0, 0,
833                     GB_UNMAPPED);
834                 bp->b_blkno = fsbtodb(fs, nb);
835                 vfs_bio_clrbuf(bp);
836                 if (DOINGSOFTDEP(vp)) {
837                         softdep_setup_allocdirect(ip, NDADDR + indirs[0].in_off,
838                             newb, 0, fs->fs_bsize, 0, bp);
839                         bdwrite(bp);
840                 } else {
841                         /*
842                          * Write synchronously so that indirect blocks
843                          * never point at garbage.
844                          */
845                         if (DOINGASYNC(vp))
846                                 bdwrite(bp);
847                         else if ((error = bwrite(bp)) != 0)
848                                 goto fail;
849                 }
850                 allocib = &dp->di_ib[indirs[0].in_off];
851                 *allocib = nb;
852                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
853         }
854         /*
855          * Fetch through the indirect blocks, allocating as necessary.
856          */
857 retry:
858         for (i = 1;;) {
859                 error = bread(vp,
860                     indirs[i].in_lbn, (int)fs->fs_bsize, NOCRED, &bp);
861                 if (error) {
862                         brelse(bp);
863                         goto fail;
864                 }
865                 bap = (ufs2_daddr_t *)bp->b_data;
866                 nb = bap[indirs[i].in_off];
867                 if (i == num)
868                         break;
869                 i += 1;
870                 if (nb != 0) {
871                         bqrelse(bp);
872                         continue;
873                 }
874                 UFS_LOCK(ump);
875                 /*
876                  * If parent indirect has just been allocated, try to cluster
877                  * immediately following it.
878                  */
879                 if (pref == 0)
880                         pref = ffs_blkpref_ufs2(ip, lbn, i - num - 1,
881                             (ufs2_daddr_t *)0);
882                 if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
883                     flags | IO_BUFLOCKED, cred, &newb)) != 0) {
884                         brelse(bp);
885                         if (DOINGSOFTDEP(vp) && ++reclaimed == 1) {
886                                 UFS_LOCK(ump);
887                                 softdep_request_cleanup(fs, vp, cred,
888                                     FLUSH_BLOCKS_WAIT);
889                                 UFS_UNLOCK(ump);
890                                 goto retry;
891                         }
892                         if (ppsratecheck(&lastfail, &curfail, 1)) {
893                                 ffs_fserr(fs, ip->i_number, "filesystem full");
894                                 uprintf("\n%s: write failed, filesystem "
895                                     "is full\n", fs->fs_fsmnt);
896                         }
897                         goto fail;
898                 }
899                 pref = newb + fs->fs_frag;
900                 nb = newb;
901                 MPASS(allocblk < allociblk + nitems(allociblk));
902                 MPASS(lbns_remfree < lbns + nitems(lbns));
903                 *allocblk++ = nb;
904                 *lbns_remfree++ = indirs[i].in_lbn;
905                 nbp = getblk(vp, indirs[i].in_lbn, fs->fs_bsize, 0, 0,
906                     GB_UNMAPPED);
907                 nbp->b_blkno = fsbtodb(fs, nb);
908                 vfs_bio_clrbuf(nbp);
909                 if (DOINGSOFTDEP(vp)) {
910                         softdep_setup_allocindir_meta(nbp, ip, bp,
911                             indirs[i - 1].in_off, nb);
912                         bdwrite(nbp);
913                 } else {
914                         /*
915                          * Write synchronously so that indirect blocks
916                          * never point at garbage.
917                          */
918                         if ((error = bwrite(nbp)) != 0) {
919                                 brelse(bp);
920                                 goto fail;
921                         }
922                 }
923                 bap[indirs[i - 1].in_off] = nb;
924                 if (allocib == NULL && unwindidx < 0)
925                         unwindidx = i - 1;
926                 /*
927                  * If required, write synchronously, otherwise use
928                  * delayed write.
929                  */
930                 if (flags & IO_SYNC) {
931                         bwrite(bp);
932                 } else {
933                         if (bp->b_bufsize == fs->fs_bsize)
934                                 bp->b_flags |= B_CLUSTEROK;
935                         bdwrite(bp);
936                 }
937         }
938         /*
939          * If asked only for the indirect block, then return it.
940          */
941         if (flags & BA_METAONLY) {
942                 curthread_pflags_restore(saved_inbdflush);
943                 *bpp = bp;
944                 return (0);
945         }
946         /*
947          * Get the data block, allocating if necessary.
948          */
949         if (nb == 0) {
950                 UFS_LOCK(ump);
951                 /*
952                  * If allocating metadata at the front of the cylinder
953                  * group and parent indirect block has just been allocated,
954                  * then cluster next to it if it is the first indirect in
955                  * the file. Otherwise it has been allocated in the metadata
956                  * area, so we want to find our own place out in the data area.
957                  */
958                 if (pref == 0 || (lbn > NDADDR && fs->fs_metaspace != 0))
959                         pref = ffs_blkpref_ufs2(ip, lbn, indirs[i].in_off,
960                             &bap[0]);
961                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
962                     flags | IO_BUFLOCKED, cred, &newb);
963                 if (error) {
964                         brelse(bp);
965                         if (DOINGSOFTDEP(vp) && ++reclaimed == 1) {
966                                 UFS_LOCK(ump);
967                                 softdep_request_cleanup(fs, vp, cred,
968                                     FLUSH_BLOCKS_WAIT);
969                                 UFS_UNLOCK(ump);
970                                 goto retry;
971                         }
972                         if (ppsratecheck(&lastfail, &curfail, 1)) {
973                                 ffs_fserr(fs, ip->i_number, "filesystem full");
974                                 uprintf("\n%s: write failed, filesystem "
975                                     "is full\n", fs->fs_fsmnt);
976                         }
977                         goto fail;
978                 }
979                 nb = newb;
980                 MPASS(allocblk < allociblk + nitems(allociblk));
981                 MPASS(lbns_remfree < lbns + nitems(lbns));
982                 *allocblk++ = nb;
983                 *lbns_remfree++ = lbn;
984                 nbp = getblk(vp, lbn, fs->fs_bsize, 0, 0, gbflags);
985                 nbp->b_blkno = fsbtodb(fs, nb);
986                 if (flags & BA_CLRBUF)
987                         vfs_bio_clrbuf(nbp);
988                 if (DOINGSOFTDEP(vp))
989                         softdep_setup_allocindir_page(ip, lbn, bp,
990                             indirs[i].in_off, nb, 0, nbp);
991                 bap[indirs[i].in_off] = nb;
992                 /*
993                  * If required, write synchronously, otherwise use
994                  * delayed write.
995                  */
996                 if (flags & IO_SYNC) {
997                         bwrite(bp);
998                 } else {
999                         if (bp->b_bufsize == fs->fs_bsize)
1000                                 bp->b_flags |= B_CLUSTEROK;
1001                         bdwrite(bp);
1002                 }
1003                 curthread_pflags_restore(saved_inbdflush);
1004                 *bpp = nbp;
1005                 return (0);
1006         }
1007         brelse(bp);
1008         /*
1009          * If requested clear invalid portions of the buffer.  If we
1010          * have to do a read-before-write (typical if BA_CLRBUF is set),
1011          * try to do some read-ahead in the sequential case to reduce
1012          * the number of I/O transactions.
1013          */
1014         if (flags & BA_CLRBUF) {
1015                 int seqcount = (flags & BA_SEQMASK) >> BA_SEQSHIFT;
1016                 if (seqcount != 0 &&
1017                     (vp->v_mount->mnt_flag & MNT_NOCLUSTERR) == 0 &&
1018                     !(vm_page_count_severe() || buf_dirty_count_severe())) {
1019                         error = cluster_read(vp, ip->i_size, lbn,
1020                             (int)fs->fs_bsize, NOCRED,
1021                             MAXBSIZE, seqcount, gbflags, &nbp);
1022                 } else {
1023                         error = bread_gb(vp, lbn, (int)fs->fs_bsize,
1024                             NOCRED, gbflags, &nbp);
1025                 }
1026                 if (error) {
1027                         brelse(nbp);
1028                         goto fail;
1029                 }
1030         } else {
1031                 nbp = getblk(vp, lbn, fs->fs_bsize, 0, 0, gbflags);
1032                 nbp->b_blkno = fsbtodb(fs, nb);
1033         }
1034         curthread_pflags_restore(saved_inbdflush);
1035         *bpp = nbp;
1036         return (0);
1037 fail:
1038         curthread_pflags_restore(saved_inbdflush);
1039         /*
1040          * If we have failed to allocate any blocks, simply return the error.
1041          * This is the usual case and avoids the need to fsync the file.
1042          */
1043         if (allocblk == allociblk && allocib == NULL && unwindidx == -1)
1044                 return (error);
1045         /*
1046          * If we have failed part way through block allocation, we
1047          * have to deallocate any indirect blocks that we have allocated.
1048          * We have to fsync the file before we start to get rid of all
1049          * of its dependencies so that we do not leave them dangling.
1050          * We have to sync it at the end so that the soft updates code
1051          * does not find any untracked changes. Although this is really
1052          * slow, running out of disk space is not expected to be a common
1053          * occurrence. The error return from fsync is ignored as we already
1054          * have an error to return to the user.
1055          *
1056          * XXX Still have to journal the free below
1057          */
1058         (void) ffs_syncvnode(vp, MNT_WAIT, 0);
1059         for (deallocated = 0, blkp = allociblk, lbns_remfree = lbns;
1060              blkp < allocblk; blkp++, lbns_remfree++) {
1061                 /*
1062                  * We shall not leave the freed blocks on the vnode
1063                  * buffer object lists.
1064                  */
1065                 bp = getblk(vp, *lbns_remfree, fs->fs_bsize, 0, 0,
1066                     GB_NOCREAT | GB_UNMAPPED);
1067                 if (bp != NULL) {
1068                         bp->b_flags |= (B_INVAL | B_RELBUF);
1069                         bp->b_flags &= ~B_ASYNC;
1070                         brelse(bp);
1071                 }
1072                 deallocated += fs->fs_bsize;
1073         }
1074         if (allocib != NULL) {
1075                 *allocib = 0;
1076         } else if (unwindidx >= 0) {
1077                 int r;
1078
1079                 r = bread(vp, indirs[unwindidx].in_lbn, 
1080                     (int)fs->fs_bsize, NOCRED, &bp);
1081                 if (r) {
1082                         panic("Could not unwind indirect block, error %d", r);
1083                         brelse(bp);
1084                 } else {
1085                         bap = (ufs2_daddr_t *)bp->b_data;
1086                         bap[indirs[unwindidx].in_off] = 0;
1087                         if (flags & IO_SYNC) {
1088                                 bwrite(bp);
1089                         } else {
1090                                 if (bp->b_bufsize == fs->fs_bsize)
1091                                         bp->b_flags |= B_CLUSTEROK;
1092                                 bdwrite(bp);
1093                         }
1094                 }
1095         }
1096         if (deallocated) {
1097 #ifdef QUOTA
1098                 /*
1099                  * Restore user's disk quota because allocation failed.
1100                  */
1101                 (void) chkdq(ip, -btodb(deallocated), cred, FORCE);
1102 #endif
1103                 dp->di_blocks -= btodb(deallocated);
1104                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
1105         }
1106         (void) ffs_syncvnode(vp, MNT_WAIT, 0);
1107         /*
1108          * After the buffers are invalidated and on-disk pointers are
1109          * cleared, free the blocks.
1110          */
1111         for (blkp = allociblk; blkp < allocblk; blkp++) {
1112                 ffs_blkfree(ump, fs, ip->i_devvp, *blkp, fs->fs_bsize,
1113                     ip->i_number, vp->v_type, NULL);
1114         }
1115         return (error);
1116 }