Change the kernel dev_t, representing a pointer to a specinfo structure,
[dragonfly.git] / sys / vfs / ufs / ffs_alloc.c
CommitLineData
984263bc
MD
1/*
2 * Copyright (c) 1982, 1986, 1989, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 *
33 * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95
34 * $FreeBSD: src/sys/ufs/ffs/ffs_alloc.c,v 1.64.2.2 2001/09/21 19:15:21 dillon Exp $
cddfb7bb 35 * $DragonFly: src/sys/vfs/ufs/ffs_alloc.c,v 1.24 2006/09/03 18:52:30 dillon Exp $
984263bc
MD
36 */
37
38#include "opt_quota.h"
39
40#include <sys/param.h>
41#include <sys/systm.h>
42#include <sys/buf.h>
43#include <sys/conf.h>
44#include <sys/proc.h>
45#include <sys/vnode.h>
46#include <sys/mount.h>
47#include <sys/kernel.h>
48#include <sys/sysctl.h>
49#include <sys/syslog.h>
50
f91a71dd
JS
51#include <machine/inttypes.h>
52
1f2de5d4
MD
53#include "quota.h"
54#include "inode.h"
55#include "ufs_extern.h"
56#include "ufsmount.h"
984263bc 57
1f2de5d4
MD
58#include "fs.h"
59#include "ffs_extern.h"
984263bc 60
a6ee311a
RG
61typedef ufs_daddr_t allocfcn_t (struct inode *ip, int cg, ufs_daddr_t bpref,
62 int size);
984263bc 63
a6ee311a 64static ufs_daddr_t ffs_alloccg (struct inode *, int, ufs_daddr_t, int);
984263bc 65static ufs_daddr_t
a6ee311a 66 ffs_alloccgblk (struct inode *, struct buf *, ufs_daddr_t);
984263bc 67#ifdef DIAGNOSTIC
a6ee311a 68static int ffs_checkblk (struct inode *, ufs_daddr_t, long);
984263bc 69#endif
a6ee311a
RG
70static void ffs_clusteracct (struct fs *, struct cg *, ufs_daddr_t,
71 int);
72static ufs_daddr_t ffs_clusteralloc (struct inode *, int, ufs_daddr_t,
73 int);
74static ino_t ffs_dirpref (struct inode *);
75static ufs_daddr_t ffs_fragextend (struct inode *, int, long, int, int);
f719c866 76static void ffs_fserr (struct fs *, uint, char *);
984263bc 77static u_long ffs_hashalloc
a6ee311a
RG
78 (struct inode *, int, long, int, allocfcn_t *);
79static ino_t ffs_nodealloccg (struct inode *, int, ufs_daddr_t, int);
80static ufs_daddr_t ffs_mapsearch (struct fs *, struct cg *, ufs_daddr_t,
81 int);
984263bc
MD
82
83/*
f719c866 84 * Allocate a block in the filesystem.
984263bc
MD
85 *
86 * The size of the requested block is given, which must be some
87 * multiple of fs_fsize and <= fs_bsize.
88 * A preference may be optionally specified. If a preference is given
89 * the following hierarchy is used to allocate a block:
90 * 1) allocate the requested block.
91 * 2) allocate a rotationally optimal block in the same cylinder.
92 * 3) allocate a block in the same cylinder group.
93 * 4) quadradically rehash into other cylinder groups, until an
94 * available block is located.
95 * If no block preference is given the following heirarchy is used
96 * to allocate a block:
97 * 1) allocate a block in the cylinder group that contains the
98 * inode for the file.
99 * 2) quadradically rehash into other cylinder groups, until an
100 * available block is located.
101 */
102int
0973c589
CP
103ffs_alloc(struct inode *ip, ufs_daddr_t lbn, ufs_daddr_t bpref, int size,
104 struct ucred *cred, ufs_daddr_t *bnp)
984263bc 105{
3ff2135f 106 struct fs *fs;
984263bc
MD
107 ufs_daddr_t bno;
108 int cg;
109#ifdef QUOTA
110 int error;
111#endif
112
113 *bnp = 0;
114 fs = ip->i_fs;
115#ifdef DIAGNOSTIC
f719c866 116 if ((uint)size > fs->fs_bsize || fragoff(fs, size) != 0) {
984263bc
MD
117 printf("dev = %s, bsize = %ld, size = %d, fs = %s\n",
118 devtoname(ip->i_dev), (long)fs->fs_bsize, size,
119 fs->fs_fsmnt);
120 panic("ffs_alloc: bad size");
121 }
122 if (cred == NOCRED)
123 panic("ffs_alloc: missing credential");
124#endif /* DIAGNOSTIC */
125 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
126 goto nospace;
127 if (cred->cr_uid != 0 &&
128 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0)
129 goto nospace;
130#ifdef QUOTA
50e58362 131 error = ufs_chkdq(ip, (long)btodb(size), cred, 0);
984263bc
MD
132 if (error)
133 return (error);
134#endif
135 if (bpref >= fs->fs_size)
136 bpref = 0;
137 if (bpref == 0)
138 cg = ino_to_cg(fs, ip->i_number);
139 else
140 cg = dtog(fs, bpref);
141 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size,
142 ffs_alloccg);
143 if (bno > 0) {
144 ip->i_blocks += btodb(size);
145 ip->i_flag |= IN_CHANGE | IN_UPDATE;
146 *bnp = bno;
147 return (0);
148 }
149#ifdef QUOTA
150 /*
151 * Restore user's disk quota because allocation failed.
152 */
50e58362 153 (void) ufs_chkdq(ip, (long)-btodb(size), cred, FORCE);
984263bc
MD
154#endif
155nospace:
f719c866
DR
156 ffs_fserr(fs, cred->cr_uid, "filesystem full");
157 uprintf("\n%s: write failed, filesystem is full\n", fs->fs_fsmnt);
984263bc
MD
158 return (ENOSPC);
159}
160
161/*
162 * Reallocate a fragment to a bigger size
163 *
164 * The number and size of the old block is given, and a preference
165 * and new size is also specified. The allocator attempts to extend
166 * the original block. Failing that, the regular block allocator is
167 * invoked to get an appropriate block.
168 */
169int
0973c589
CP
170ffs_realloccg(struct inode *ip, ufs_daddr_t lbprev, ufs_daddr_t bpref,
171 int osize, int nsize, struct ucred *cred, struct buf **bpp)
984263bc 172{
3ff2135f 173 struct fs *fs;
984263bc
MD
174 struct buf *bp;
175 int cg, request, error;
176 ufs_daddr_t bprev, bno;
177
178 *bpp = 0;
179 fs = ip->i_fs;
180#ifdef DIAGNOSTIC
f719c866
DR
181 if ((uint)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
182 (uint)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
984263bc
MD
183 printf(
184 "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n",
185 devtoname(ip->i_dev), (long)fs->fs_bsize, osize,
186 nsize, fs->fs_fsmnt);
187 panic("ffs_realloccg: bad size");
188 }
189 if (cred == NOCRED)
190 panic("ffs_realloccg: missing credential");
191#endif /* DIAGNOSTIC */
192 if (cred->cr_uid != 0 &&
193 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0)
194 goto nospace;
195 if ((bprev = ip->i_db[lbprev]) == 0) {
196 printf("dev = %s, bsize = %ld, bprev = %ld, fs = %s\n",
197 devtoname(ip->i_dev), (long)fs->fs_bsize, (long)bprev,
198 fs->fs_fsmnt);
199 panic("ffs_realloccg: bad bprev");
200 }
201 /*
202 * Allocate the extra space in the buffer.
203 */
54078292 204 error = bread(ITOV(ip), lblktodoff(fs, lbprev), osize, &bp);
984263bc
MD
205 if (error) {
206 brelse(bp);
207 return (error);
208 }
209
54078292 210 if(bp->b_bio2.bio_offset == NOOFFSET) {
984263bc
MD
211 if( lbprev >= NDADDR)
212 panic("ffs_realloccg: lbprev out of range");
54078292 213 bp->b_bio2.bio_offset = fsbtodoff(fs, bprev);
984263bc
MD
214 }
215
216#ifdef QUOTA
50e58362 217 error = ufs_chkdq(ip, (long)btodb(nsize - osize), cred, 0);
984263bc
MD
218 if (error) {
219 brelse(bp);
220 return (error);
221 }
222#endif
223 /*
224 * Check for extension in the existing location.
225 */
226 cg = dtog(fs, bprev);
227 bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize);
228 if (bno) {
54078292 229 if (bp->b_bio2.bio_offset != fsbtodoff(fs, bno))
984263bc
MD
230 panic("ffs_realloccg: bad blockno");
231 ip->i_blocks += btodb(nsize - osize);
232 ip->i_flag |= IN_CHANGE | IN_UPDATE;
233 allocbuf(bp, nsize);
f719c866 234 bzero((char *)bp->b_data + osize, (uint)nsize - osize);
984263bc
MD
235 *bpp = bp;
236 return (0);
237 }
238 /*
239 * Allocate a new disk location.
240 */
241 if (bpref >= fs->fs_size)
242 bpref = 0;
243 switch ((int)fs->fs_optim) {
244 case FS_OPTSPACE:
245 /*
246 * Allocate an exact sized fragment. Although this makes
247 * best use of space, we will waste time relocating it if
248 * the file continues to grow. If the fragmentation is
249 * less than half of the minimum free reserve, we choose
250 * to begin optimizing for time.
251 */
252 request = nsize;
253 if (fs->fs_minfree <= 5 ||
254 fs->fs_cstotal.cs_nffree >
255 (off_t)fs->fs_dsize * fs->fs_minfree / (2 * 100))
256 break;
257 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n",
258 fs->fs_fsmnt);
259 fs->fs_optim = FS_OPTTIME;
260 break;
261 case FS_OPTTIME:
262 /*
263 * At this point we have discovered a file that is trying to
264 * grow a small fragment to a larger fragment. To save time,
265 * we allocate a full sized block, then free the unused portion.
266 * If the file continues to grow, the `ffs_fragextend' call
267 * above will be able to grow it in place without further
268 * copying. If aberrant programs cause disk fragmentation to
269 * grow within 2% of the free reserve, we choose to begin
270 * optimizing for space.
271 */
272 request = fs->fs_bsize;
273 if (fs->fs_cstotal.cs_nffree <
274 (off_t)fs->fs_dsize * (fs->fs_minfree - 2) / 100)
275 break;
276 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n",
277 fs->fs_fsmnt);
278 fs->fs_optim = FS_OPTSPACE;
279 break;
280 default:
281 printf("dev = %s, optim = %ld, fs = %s\n",
282 devtoname(ip->i_dev), (long)fs->fs_optim, fs->fs_fsmnt);
283 panic("ffs_realloccg: bad optim");
284 /* NOTREACHED */
285 }
286 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request,
287 ffs_alloccg);
288 if (bno > 0) {
54078292 289 bp->b_bio2.bio_offset = fsbtodoff(fs, bno);
984263bc
MD
290 if (!DOINGSOFTDEP(ITOV(ip)))
291 ffs_blkfree(ip, bprev, (long)osize);
292 if (nsize < request)
293 ffs_blkfree(ip, bno + numfrags(fs, nsize),
294 (long)(request - nsize));
295 ip->i_blocks += btodb(nsize - osize);
296 ip->i_flag |= IN_CHANGE | IN_UPDATE;
297 allocbuf(bp, nsize);
f719c866 298 bzero((char *)bp->b_data + osize, (uint)nsize - osize);
984263bc
MD
299 *bpp = bp;
300 return (0);
301 }
302#ifdef QUOTA
303 /*
304 * Restore user's disk quota because allocation failed.
305 */
50e58362 306 (void) ufs_chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE);
984263bc
MD
307#endif
308 brelse(bp);
309nospace:
310 /*
311 * no space available
312 */
f719c866
DR
313 ffs_fserr(fs, cred->cr_uid, "filesystem full");
314 uprintf("\n%s: write failed, filesystem is full\n", fs->fs_fsmnt);
984263bc
MD
315 return (ENOSPC);
316}
317
318SYSCTL_NODE(_vfs, OID_AUTO, ffs, CTLFLAG_RW, 0, "FFS filesystem");
319
320/*
321 * Reallocate a sequence of blocks into a contiguous sequence of blocks.
322 *
323 * The vnode and an array of buffer pointers for a range of sequential
324 * logical blocks to be made contiguous is given. The allocator attempts
325 * to find a range of sequential blocks starting as close as possible to
326 * an fs_rotdelay offset from the end of the allocation for the logical
327 * block immediately preceeding the current range. If successful, the
328 * physical block numbers in the buffer pointers and in the inode are
329 * changed to reflect the new allocation. If unsuccessful, the allocation
330 * is left unchanged. The success in doing the reallocation is returned.
331 * Note that the error return is not reflected back to the user. Rather
332 * the previous block allocation will be used.
333 */
334static int doasyncfree = 1;
335SYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, "");
336
337static int doreallocblks = 1;
338SYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, "");
339
340#ifdef DEBUG
341static volatile int prtrealloc = 0;
342#endif
343
0973c589
CP
344/*
345 * ffs_reallocblks(struct vnode *a_vp, struct cluster_save *a_buflist)
346 */
984263bc 347int
0973c589 348ffs_reallocblks(struct vop_reallocblks_args *ap)
984263bc
MD
349{
350 struct fs *fs;
351 struct inode *ip;
352 struct vnode *vp;
353 struct buf *sbp, *ebp;
354 ufs_daddr_t *bap, *sbap, *ebap = 0;
355 struct cluster_save *buflist;
356 ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno;
54078292
MD
357#ifdef DIAGNOSTIC
358 off_t boffset;
359#endif
984263bc 360 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
d490cb23 361 int i, len, slen, start_lvl, end_lvl, pref, ssize;
984263bc
MD
362
363 if (doreallocblks == 0)
364 return (ENOSPC);
365 vp = ap->a_vp;
366 ip = VTOI(vp);
367 fs = ip->i_fs;
368 if (fs->fs_contigsumsize <= 0)
369 return (ENOSPC);
370 buflist = ap->a_buflist;
371 len = buflist->bs_nchildren;
54078292 372 start_lbn = lblkno(fs, buflist->bs_children[0]->b_loffset);
984263bc
MD
373 end_lbn = start_lbn + len - 1;
374#ifdef DIAGNOSTIC
375 for (i = 0; i < len; i++)
376 if (!ffs_checkblk(ip,
54078292 377 dofftofsb(fs, buflist->bs_children[i]->b_bio2.bio_offset), fs->fs_bsize))
984263bc 378 panic("ffs_reallocblks: unallocated block 1");
54078292
MD
379 for (i = 1; i < len; i++) {
380 if (buflist->bs_children[i]->b_loffset != lblktodoff(fs, start_lbn) + lblktodoff(fs, i))
984263bc 381 panic("ffs_reallocblks: non-logical cluster");
54078292
MD
382 }
383 boffset = buflist->bs_children[0]->b_bio2.bio_offset;
384 ssize = (int)fsbtodoff(fs, fs->fs_frag);
984263bc 385 for (i = 1; i < len - 1; i++)
54078292 386 if (buflist->bs_children[i]->b_bio2.bio_offset != boffset + (i * ssize))
984263bc
MD
387 panic("ffs_reallocblks: non-physical cluster %d", i);
388#endif
389 /*
390 * If the latest allocation is in a new cylinder group, assume that
391 * the filesystem has decided to move and do not force it back to
392 * the previous cylinder group.
393 */
54078292
MD
394 if (dtog(fs, dofftofsb(fs, buflist->bs_children[0]->b_bio2.bio_offset)) !=
395 dtog(fs, dofftofsb(fs, buflist->bs_children[len - 1]->b_bio2.bio_offset)))
984263bc
MD
396 return (ENOSPC);
397 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
398 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
399 return (ENOSPC);
400 /*
d490cb23
MD
401 * Get the starting offset and block map for the first block and
402 * the number of blocks that will fit into sbap starting at soff.
984263bc
MD
403 */
404 if (start_lvl == 0) {
405 sbap = &ip->i_db[0];
406 soff = start_lbn;
d490cb23 407 slen = NDADDR - soff;
984263bc
MD
408 } else {
409 idp = &start_ap[start_lvl - 1];
54078292 410 if (bread(vp, lblktodoff(fs, idp->in_lbn), (int)fs->fs_bsize, &sbp)) {
984263bc
MD
411 brelse(sbp);
412 return (ENOSPC);
413 }
414 sbap = (ufs_daddr_t *)sbp->b_data;
415 soff = idp->in_off;
d490cb23 416 slen = fs->fs_nindir - soff;
984263bc
MD
417 }
418 /*
419 * Find the preferred location for the cluster.
420 */
421 pref = ffs_blkpref(ip, start_lbn, soff, sbap);
422 /*
423 * If the block range spans two block maps, get the second map.
424 */
425 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
426 ssize = len;
427 } else {
428#ifdef DIAGNOSTIC
429 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn)
430 panic("ffs_reallocblk: start == end");
431#endif
432 ssize = len - (idp->in_off + 1);
54078292 433 if (bread(vp, lblktodoff(fs, idp->in_lbn), (int)fs->fs_bsize, &ebp))
984263bc
MD
434 goto fail;
435 ebap = (ufs_daddr_t *)ebp->b_data;
436 }
d490cb23
MD
437
438 /*
439 * Make sure we aren't spanning more then two blockmaps. ssize is
440 * our calculation of the span we have to scan in the first blockmap,
441 * while slen is our calculation of the number of entries available
442 * in the first blockmap (from soff).
443 */
444 if (ssize > slen) {
445 panic("ffs_reallocblks: range spans more then two blockmaps!"
446 " start_lbn %ld len %d (%d/%d)",
447 (long)start_lbn, len, slen, ssize);
448 }
984263bc
MD
449 /*
450 * Search the block map looking for an allocation of the desired size.
451 */
452 if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref,
453 len, ffs_clusteralloc)) == 0)
454 goto fail;
455 /*
456 * We have found a new contiguous block.
457 *
458 * First we have to replace the old block pointers with the new
459 * block pointers in the inode and indirect blocks associated
460 * with the file.
461 */
462#ifdef DEBUG
463 if (prtrealloc)
464 printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number,
465 start_lbn, end_lbn);
466#endif
467 blkno = newblk;
468 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) {
469 if (i == ssize) {
470 bap = ebap;
471 soff = -i;
472 }
473#ifdef DIAGNOSTIC
474 if (!ffs_checkblk(ip,
54078292 475 dofftofsb(fs, buflist->bs_children[i]->b_bio2.bio_offset), fs->fs_bsize))
984263bc 476 panic("ffs_reallocblks: unallocated block 2");
54078292 477 if (dofftofsb(fs, buflist->bs_children[i]->b_bio2.bio_offset) != *bap)
984263bc
MD
478 panic("ffs_reallocblks: alloc mismatch");
479#endif
480#ifdef DEBUG
481 if (prtrealloc)
482 printf(" %d,", *bap);
483#endif
484 if (DOINGSOFTDEP(vp)) {
485 if (sbap == &ip->i_db[0] && i < ssize)
486 softdep_setup_allocdirect(ip, start_lbn + i,
487 blkno, *bap, fs->fs_bsize, fs->fs_bsize,
488 buflist->bs_children[i]);
489 else
490 softdep_setup_allocindir_page(ip, start_lbn + i,
491 i < ssize ? sbp : ebp, soff + i, blkno,
492 *bap, buflist->bs_children[i]);
493 }
494 *bap++ = blkno;
495 }
496 /*
497 * Next we must write out the modified inode and indirect blocks.
498 * For strict correctness, the writes should be synchronous since
499 * the old block values may have been written to disk. In practise
500 * they are almost never written, but if we are concerned about
501 * strict correctness, the `doasyncfree' flag should be set to zero.
502 *
503 * The test on `doasyncfree' should be changed to test a flag
504 * that shows whether the associated buffers and inodes have
505 * been written. The flag should be set when the cluster is
506 * started and cleared whenever the buffer or inode is flushed.
507 * We can then check below to see if it is set, and do the
508 * synchronous write only when it has been cleared.
509 */
510 if (sbap != &ip->i_db[0]) {
511 if (doasyncfree)
512 bdwrite(sbp);
513 else
514 bwrite(sbp);
515 } else {
516 ip->i_flag |= IN_CHANGE | IN_UPDATE;
517 if (!doasyncfree)
ac690a1d 518 ffs_update(vp, 1);
984263bc
MD
519 }
520 if (ssize < len) {
521 if (doasyncfree)
522 bdwrite(ebp);
523 else
524 bwrite(ebp);
525 }
526 /*
527 * Last, free the old blocks and assign the new blocks to the buffers.
528 */
529#ifdef DEBUG
530 if (prtrealloc)
531 printf("\n\tnew:");
532#endif
533 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) {
534 if (!DOINGSOFTDEP(vp))
535 ffs_blkfree(ip,
54078292 536 dofftofsb(fs, buflist->bs_children[i]->b_bio2.bio_offset),
984263bc 537 fs->fs_bsize);
54078292 538 buflist->bs_children[i]->b_bio2.bio_offset = fsbtodoff(fs, blkno);
984263bc
MD
539#ifdef DIAGNOSTIC
540 if (!ffs_checkblk(ip,
54078292 541 dofftofsb(fs, buflist->bs_children[i]->b_bio2.bio_offset), fs->fs_bsize))
984263bc
MD
542 panic("ffs_reallocblks: unallocated block 3");
543#endif
544#ifdef DEBUG
545 if (prtrealloc)
546 printf(" %d,", blkno);
547#endif
548 }
549#ifdef DEBUG
550 if (prtrealloc) {
551 prtrealloc--;
552 printf("\n");
553 }
554#endif
555 return (0);
556
557fail:
558 if (ssize < len)
559 brelse(ebp);
560 if (sbap != &ip->i_db[0])
561 brelse(sbp);
562 return (ENOSPC);
563}
564
565/*
f719c866 566 * Allocate an inode in the filesystem.
984263bc
MD
567 *
568 * If allocating a directory, use ffs_dirpref to select the inode.
569 * If allocating in a directory, the following hierarchy is followed:
570 * 1) allocate the preferred inode.
571 * 2) allocate an inode in the same cylinder group.
572 * 3) quadradically rehash into other cylinder groups, until an
573 * available inode is located.
574 * If no inode preference is given the following heirarchy is used
575 * to allocate an inode:
576 * 1) allocate an inode in cylinder group 0.
577 * 2) quadradically rehash into other cylinder groups, until an
578 * available inode is located.
579 */
580int
0973c589 581ffs_valloc(struct vnode *pvp, int mode, struct ucred *cred, struct vnode **vpp)
984263bc 582{
3ff2135f
RG
583 struct inode *pip;
584 struct fs *fs;
585 struct inode *ip;
984263bc
MD
586 ino_t ino, ipref;
587 int cg, error;
588
589 *vpp = NULL;
590 pip = VTOI(pvp);
591 fs = pip->i_fs;
592 if (fs->fs_cstotal.cs_nifree == 0)
593 goto noinodes;
594
595 if ((mode & IFMT) == IFDIR)
596 ipref = ffs_dirpref(pip);
597 else
598 ipref = pip->i_number;
599 if (ipref >= fs->fs_ncg * fs->fs_ipg)
600 ipref = 0;
601 cg = ino_to_cg(fs, ipref);
602 /*
603 * Track number of dirs created one after another
604 * in a same cg without intervening by files.
605 */
606 if ((mode & IFMT) == IFDIR) {
607 if (fs->fs_contigdirs[cg] < 255)
608 fs->fs_contigdirs[cg]++;
609 } else {
610 if (fs->fs_contigdirs[cg] > 0)
611 fs->fs_contigdirs[cg]--;
612 }
613 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode,
614 (allocfcn_t *)ffs_nodealloccg);
615 if (ino == 0)
616 goto noinodes;
617 error = VFS_VGET(pvp->v_mount, ino, vpp);
618 if (error) {
ac690a1d 619 ffs_vfree(pvp, ino, mode);
984263bc
MD
620 return (error);
621 }
622 ip = VTOI(*vpp);
623 if (ip->i_mode) {
624 printf("mode = 0%o, inum = %lu, fs = %s\n",
625 ip->i_mode, (u_long)ip->i_number, fs->fs_fsmnt);
626 panic("ffs_valloc: dup alloc");
627 }
628 if (ip->i_blocks) { /* XXX */
629 printf("free inode %s/%lu had %ld blocks\n",
630 fs->fs_fsmnt, (u_long)ino, (long)ip->i_blocks);
631 ip->i_blocks = 0;
632 }
633 ip->i_flags = 0;
634 /*
635 * Set up a new generation number for this inode.
636 */
637 if (ip->i_gen == 0 || ++ip->i_gen == 0)
cddfb7bb 638 ip->i_gen = krandom() / 2 + 1;
984263bc
MD
639 return (0);
640noinodes:
641 ffs_fserr(fs, cred->cr_uid, "out of inodes");
642 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt);
643 return (ENOSPC);
644}
645
646/*
647 * Find a cylinder group to place a directory.
648 *
649 * The policy implemented by this algorithm is to allocate a
650 * directory inode in the same cylinder group as its parent
651 * directory, but also to reserve space for its files inodes
652 * and data. Restrict the number of directories which may be
653 * allocated one after another in the same cylinder group
654 * without intervening allocation of files.
655 *
656 * If we allocate a first level directory then force allocation
657 * in another cylinder group.
658 */
659static ino_t
0973c589 660ffs_dirpref(struct inode *pip)
984263bc 661{
3ff2135f 662 struct fs *fs;
984263bc 663 int cg, prefcg, dirsize, cgsize;
06a1dad1 664 int64_t dirsize64;
984263bc
MD
665 int avgifree, avgbfree, avgndir, curdirsize;
666 int minifree, minbfree, maxndir;
667 int mincg, minndir;
668 int maxcontigdirs;
669
670 fs = pip->i_fs;
671
672 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
673 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
674 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg;
675
676 /*
677 * Force allocation in another cg if creating a first level dir.
678 */
679 if (ITOV(pip)->v_flag & VROOT) {
0ced1954 680 prefcg = karc4random() % fs->fs_ncg;
984263bc
MD
681 mincg = prefcg;
682 minndir = fs->fs_ipg;
683 for (cg = prefcg; cg < fs->fs_ncg; cg++)
684 if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
685 fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
686 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
687 mincg = cg;
688 minndir = fs->fs_cs(fs, cg).cs_ndir;
689 }
690 for (cg = 0; cg < prefcg; cg++)
691 if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
692 fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
693 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
694 mincg = cg;
695 minndir = fs->fs_cs(fs, cg).cs_ndir;
696 }
697 return ((ino_t)(fs->fs_ipg * mincg));
698 }
699
700 /*
701 * Count various limits which used for
702 * optimal allocation of a directory inode.
703 */
704 maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg);
04052b0e
DR
705 minifree = avgifree - avgifree / 4;
706 if (minifree < 1)
707 minifree = 1;
708 minbfree = avgbfree - avgbfree / 4;
709 if (minbfree < 1)
710 minbfree = 1;
984263bc 711 cgsize = fs->fs_fsize * fs->fs_fpg;
06a1dad1
MD
712
713 /*
714 * fs_avgfilesize and fs_avgfpdir are user-settable entities and
715 * multiplying them may overflow a 32 bit integer.
716 */
717 dirsize64 = fs->fs_avgfilesize * (int64_t)fs->fs_avgfpdir;
718 if (dirsize64 > 0x7fffffff) {
984263bc 719 maxcontigdirs = 1;
06a1dad1
MD
720 } else {
721 dirsize = (int)dirsize64;
722 curdirsize = avgndir ?
723 (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0;
724 if (dirsize < curdirsize)
725 dirsize = curdirsize;
726 maxcontigdirs = min((avgbfree * fs->fs_bsize) / dirsize, 255);
727 if (fs->fs_avgfpdir > 0)
728 maxcontigdirs = min(maxcontigdirs,
729 fs->fs_ipg / fs->fs_avgfpdir);
730 if (maxcontigdirs == 0)
731 maxcontigdirs = 1;
732 }
984263bc
MD
733
734 /*
735 * Limit number of dirs in one cg and reserve space for
736 * regular files, but only if we have no deficit in
737 * inodes or space.
738 */
739 prefcg = ino_to_cg(fs, pip->i_number);
740 for (cg = prefcg; cg < fs->fs_ncg; cg++)
741 if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
742 fs->fs_cs(fs, cg).cs_nifree >= minifree &&
743 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
744 if (fs->fs_contigdirs[cg] < maxcontigdirs)
745 return ((ino_t)(fs->fs_ipg * cg));
746 }
747 for (cg = 0; cg < prefcg; cg++)
748 if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
749 fs->fs_cs(fs, cg).cs_nifree >= minifree &&
750 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
751 if (fs->fs_contigdirs[cg] < maxcontigdirs)
752 return ((ino_t)(fs->fs_ipg * cg));
753 }
754 /*
755 * This is a backstop when we have deficit in space.
756 */
757 for (cg = prefcg; cg < fs->fs_ncg; cg++)
758 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
759 return ((ino_t)(fs->fs_ipg * cg));
760 for (cg = 0; cg < prefcg; cg++)
761 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
762 break;
763 return ((ino_t)(fs->fs_ipg * cg));
764}
765
766/*
767 * Select the desired position for the next block in a file. The file is
768 * logically divided into sections. The first section is composed of the
769 * direct blocks. Each additional section contains fs_maxbpg blocks.
770 *
771 * If no blocks have been allocated in the first section, the policy is to
772 * request a block in the same cylinder group as the inode that describes
773 * the file. If no blocks have been allocated in any other section, the
774 * policy is to place the section in a cylinder group with a greater than
775 * average number of free blocks. An appropriate cylinder group is found
776 * by using a rotor that sweeps the cylinder groups. When a new group of
777 * blocks is needed, the sweep begins in the cylinder group following the
778 * cylinder group from which the previous allocation was made. The sweep
779 * continues until a cylinder group with greater than the average number
780 * of free blocks is found. If the allocation is for the first block in an
781 * indirect block, the information on the previous allocation is unavailable;
782 * here a best guess is made based upon the logical block number being
783 * allocated.
784 *
785 * If a section is already partially allocated, the policy is to
786 * contiguously allocate fs_maxcontig blocks. The end of one of these
787 * contiguous blocks and the beginning of the next is physically separated
788 * so that the disk head will be in transit between them for at least
789 * fs_rotdelay milliseconds. This is to allow time for the processor to
790 * schedule another I/O transfer.
791 */
792ufs_daddr_t
0973c589 793ffs_blkpref(struct inode *ip, ufs_daddr_t lbn, int indx, ufs_daddr_t *bap)
984263bc 794{
3ff2135f
RG
795 struct fs *fs;
796 int cg;
984263bc
MD
797 int avgbfree, startcg;
798 ufs_daddr_t nextblk;
799
800 fs = ip->i_fs;
801 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
802 if (lbn < NDADDR + NINDIR(fs)) {
803 cg = ino_to_cg(fs, ip->i_number);
804 return (fs->fs_fpg * cg + fs->fs_frag);
805 }
806 /*
807 * Find a cylinder with greater than average number of
808 * unused data blocks.
809 */
810 if (indx == 0 || bap[indx - 1] == 0)
811 startcg =
812 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
813 else
814 startcg = dtog(fs, bap[indx - 1]) + 1;
815 startcg %= fs->fs_ncg;
816 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
817 for (cg = startcg; cg < fs->fs_ncg; cg++)
818 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
819 fs->fs_cgrotor = cg;
820 return (fs->fs_fpg * cg + fs->fs_frag);
821 }
822 for (cg = 0; cg <= startcg; cg++)
823 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
824 fs->fs_cgrotor = cg;
825 return (fs->fs_fpg * cg + fs->fs_frag);
826 }
827 return (0);
828 }
829 /*
830 * One or more previous blocks have been laid out. If less
831 * than fs_maxcontig previous blocks are contiguous, the
832 * next block is requested contiguously, otherwise it is
833 * requested rotationally delayed by fs_rotdelay milliseconds.
834 */
835 nextblk = bap[indx - 1] + fs->fs_frag;
836 if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig ||
837 bap[indx - fs->fs_maxcontig] +
838 blkstofrags(fs, fs->fs_maxcontig) != nextblk)
839 return (nextblk);
840 /*
841 * Here we convert ms of delay to frags as:
842 * (frags) = (ms) * (rev/sec) * (sect/rev) /
843 * ((sect/frag) * (ms/sec))
844 * then round up to the next block.
845 */
846 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect /
847 (NSPF(fs) * 1000), fs->fs_frag);
848 return (nextblk);
849}
850
851/*
852 * Implement the cylinder overflow algorithm.
853 *
854 * The policy implemented by this algorithm is:
855 * 1) allocate the block in its requested cylinder group.
856 * 2) quadradically rehash on the cylinder group number.
857 * 3) brute force search for a free block.
858 */
859/*VARARGS5*/
860static u_long
0973c589
CP
861ffs_hashalloc(struct inode *ip, int cg, long pref,
862 int size, /* size for data blocks, mode for inodes */
863 allocfcn_t *allocator)
984263bc 864{
3ff2135f 865 struct fs *fs;
984263bc
MD
866 long result; /* XXX why not same type as we return? */
867 int i, icg = cg;
868
869 fs = ip->i_fs;
870 /*
871 * 1: preferred cylinder group
872 */
873 result = (*allocator)(ip, cg, pref, size);
874 if (result)
875 return (result);
876 /*
877 * 2: quadratic rehash
878 */
879 for (i = 1; i < fs->fs_ncg; i *= 2) {
880 cg += i;
881 if (cg >= fs->fs_ncg)
882 cg -= fs->fs_ncg;
883 result = (*allocator)(ip, cg, 0, size);
884 if (result)
885 return (result);
886 }
887 /*
888 * 3: brute force search
889 * Note that we start at i == 2, since 0 was checked initially,
890 * and 1 is always checked in the quadratic rehash.
891 */
892 cg = (icg + 2) % fs->fs_ncg;
893 for (i = 2; i < fs->fs_ncg; i++) {
894 result = (*allocator)(ip, cg, 0, size);
895 if (result)
896 return (result);
897 cg++;
898 if (cg == fs->fs_ncg)
899 cg = 0;
900 }
901 return (0);
902}
903
904/*
905 * Determine whether a fragment can be extended.
906 *
907 * Check to see if the necessary fragments are available, and
908 * if they are, allocate them.
909 */
910static ufs_daddr_t
0973c589 911ffs_fragextend(struct inode *ip, int cg, long bprev, int osize, int nsize)
984263bc 912{
3ff2135f
RG
913 struct fs *fs;
914 struct cg *cgp;
984263bc
MD
915 struct buf *bp;
916 long bno;
917 int frags, bbase;
918 int i, error;
f719c866 919 uint8_t *blksfree;
984263bc
MD
920
921 fs = ip->i_fs;
922 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
923 return (0);
924 frags = numfrags(fs, nsize);
925 bbase = fragnum(fs, bprev);
926 if (bbase > fragnum(fs, (bprev + frags - 1))) {
927 /* cannot extend across a block boundary */
928 return (0);
929 }
5d5d3444 930 KKASSERT(blknum(fs, bprev) == blknum(fs, bprev + frags - 1));
54078292 931 error = bread(ip->i_devvp, fsbtodoff(fs, cgtod(fs, cg)),
3b568787 932 (int)fs->fs_cgsize, &bp);
984263bc
MD
933 if (error) {
934 brelse(bp);
935 return (0);
936 }
937 cgp = (struct cg *)bp->b_data;
938 if (!cg_chkmagic(cgp)) {
939 brelse(bp);
940 return (0);
941 }
984263bc
MD
942 cgp->cg_time = time_second;
943 bno = dtogd(fs, bprev);
944 blksfree = cg_blksfree(cgp);
5d5d3444 945 for (i = numfrags(fs, osize); i < frags; i++) {
984263bc
MD
946 if (isclr(blksfree, bno + i)) {
947 brelse(bp);
948 return (0);
949 }
5d5d3444
MD
950 }
951
984263bc
MD
952 /*
953 * the current fragment can be extended
954 * deduct the count on fragment being extended into
955 * increase the count on the remaining fragment (if any)
956 * allocate the extended piece
5d5d3444
MD
957 *
958 * ---oooooooooonnnnnnn111----
959 * [-----frags-----]
960 * ^ ^
961 * bbase fs_frag
984263bc 962 */
5d5d3444 963 for (i = frags; i < fs->fs_frag - bbase; i++) {
984263bc
MD
964 if (isclr(blksfree, bno + i))
965 break;
5d5d3444
MD
966 }
967
968 /*
969 * Size of original free frag is [i - numfrags(fs, osize)]
970 * Size of remaining free frag is [i - frags]
971 */
984263bc
MD
972 cgp->cg_frsum[i - numfrags(fs, osize)]--;
973 if (i != frags)
974 cgp->cg_frsum[i - frags]++;
975 for (i = numfrags(fs, osize); i < frags; i++) {
976 clrbit(blksfree, bno + i);
977 cgp->cg_cs.cs_nffree--;
978 fs->fs_cstotal.cs_nffree--;
979 fs->fs_cs(fs, cg).cs_nffree--;
980 }
981 fs->fs_fmod = 1;
982 if (DOINGSOFTDEP(ITOV(ip)))
983 softdep_setup_blkmapdep(bp, fs, bprev);
984 bdwrite(bp);
985 return (bprev);
986}
987
988/*
989 * Determine whether a block can be allocated.
990 *
991 * Check to see if a block of the appropriate size is available,
992 * and if it is, allocate it.
993 */
994static ufs_daddr_t
0973c589 995ffs_alloccg(struct inode *ip, int cg, ufs_daddr_t bpref, int size)
984263bc 996{
3ff2135f
RG
997 struct fs *fs;
998 struct cg *cgp;
984263bc 999 struct buf *bp;
3ff2135f 1000 int i;
984263bc
MD
1001 ufs_daddr_t bno, blkno;
1002 int allocsiz, error, frags;
f719c866 1003 uint8_t *blksfree;
984263bc
MD
1004
1005 fs = ip->i_fs;
1006 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
1007 return (0);
54078292 1008 error = bread(ip->i_devvp, fsbtodoff(fs, cgtod(fs, cg)),
3b568787 1009 (int)fs->fs_cgsize, &bp);
984263bc
MD
1010 if (error) {
1011 brelse(bp);
1012 return (0);
1013 }
1014 cgp = (struct cg *)bp->b_data;
1015 if (!cg_chkmagic(cgp) ||
1016 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
1017 brelse(bp);
1018 return (0);
1019 }
984263bc
MD
1020 cgp->cg_time = time_second;
1021 if (size == fs->fs_bsize) {
1022 bno = ffs_alloccgblk(ip, bp, bpref);
1023 bdwrite(bp);
1024 return (bno);
1025 }
1026 /*
5d5d3444
MD
1027 * Check to see if any fragments of sufficient size are already
1028 * available. Fit the data into a larger fragment if necessary,
1029 * before allocating a whole new block.
984263bc
MD
1030 */
1031 blksfree = cg_blksfree(cgp);
1032 frags = numfrags(fs, size);
5d5d3444 1033 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) {
984263bc
MD
1034 if (cgp->cg_frsum[allocsiz] != 0)
1035 break;
5d5d3444 1036 }
984263bc
MD
1037 if (allocsiz == fs->fs_frag) {
1038 /*
5d5d3444
MD
1039 * No fragments were available, allocate a whole block and
1040 * cut the requested fragment (of size frags) out of it.
984263bc
MD
1041 */
1042 if (cgp->cg_cs.cs_nbfree == 0) {
1043 brelse(bp);
1044 return (0);
1045 }
1046 bno = ffs_alloccgblk(ip, bp, bpref);
1047 bpref = dtogd(fs, bno);
1048 for (i = frags; i < fs->fs_frag; i++)
1049 setbit(blksfree, bpref + i);
5d5d3444
MD
1050
1051 /*
1052 * Calculate the number of free frags still remaining after
1053 * we have cut out the requested allocation. Indicate that
1054 * a fragment of that size is now available for future
1055 * allocation.
1056 */
984263bc
MD
1057 i = fs->fs_frag - frags;
1058 cgp->cg_cs.cs_nffree += i;
1059 fs->fs_cstotal.cs_nffree += i;
1060 fs->fs_cs(fs, cg).cs_nffree += i;
1061 fs->fs_fmod = 1;
1062 cgp->cg_frsum[i]++;
1063 bdwrite(bp);
1064 return (bno);
1065 }
5d5d3444
MD
1066
1067 /*
1068 * cg_frsum[] has told us that a free fragment of allocsiz size is
1069 * available. Find it, then clear the bitmap bits associated with
1070 * the size we want.
1071 */
984263bc
MD
1072 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz);
1073 if (bno < 0) {
1074 brelse(bp);
1075 return (0);
1076 }
1077 for (i = 0; i < frags; i++)
1078 clrbit(blksfree, bno + i);
1079 cgp->cg_cs.cs_nffree -= frags;
1080 fs->fs_cstotal.cs_nffree -= frags;
1081 fs->fs_cs(fs, cg).cs_nffree -= frags;
1082 fs->fs_fmod = 1;
5d5d3444
MD
1083
1084 /*
1085 * Account for the allocation. The original searched size that we
1086 * found is no longer available. If we cut out a smaller piece then
1087 * a smaller fragment is now available.
1088 */
984263bc
MD
1089 cgp->cg_frsum[allocsiz]--;
1090 if (frags != allocsiz)
1091 cgp->cg_frsum[allocsiz - frags]++;
1092 blkno = cg * fs->fs_fpg + bno;
1093 if (DOINGSOFTDEP(ITOV(ip)))
1094 softdep_setup_blkmapdep(bp, fs, blkno);
1095 bdwrite(bp);
1096 return ((u_long)blkno);
1097}
1098
1099/*
1100 * Allocate a block in a cylinder group.
1101 *
1102 * This algorithm implements the following policy:
1103 * 1) allocate the requested block.
1104 * 2) allocate a rotationally optimal block in the same cylinder.
1105 * 3) allocate the next available block on the block rotor for the
1106 * specified cylinder group.
1107 * Note that this routine only allocates fs_bsize blocks; these
1108 * blocks may be fragmented by the routine that allocates them.
1109 */
1110static ufs_daddr_t
0973c589 1111ffs_alloccgblk(struct inode *ip, struct buf *bp, ufs_daddr_t bpref)
984263bc
MD
1112{
1113 struct fs *fs;
1114 struct cg *cgp;
1115 ufs_daddr_t bno, blkno;
1116 int cylno, pos, delta;
1117 short *cylbp;
3ff2135f 1118 int i;
f719c866 1119 uint8_t *blksfree;
984263bc
MD
1120
1121 fs = ip->i_fs;
1122 cgp = (struct cg *)bp->b_data;
1123 blksfree = cg_blksfree(cgp);
1124 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) {
1125 bpref = cgp->cg_rotor;
1126 goto norot;
1127 }
1128 bpref = blknum(fs, bpref);
1129 bpref = dtogd(fs, bpref);
1130 /*
1131 * if the requested block is available, use it
1132 */
1133 if (ffs_isblock(fs, blksfree, fragstoblks(fs, bpref))) {
1134 bno = bpref;
1135 goto gotit;
1136 }
1137 if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) {
1138 /*
1139 * Block layout information is not available.
1140 * Leaving bpref unchanged means we take the
1141 * next available free block following the one
1142 * we just allocated. Hopefully this will at
1143 * least hit a track cache on drives of unknown
1144 * geometry (e.g. SCSI).
1145 */
1146 goto norot;
1147 }
1148 /*
1149 * check for a block available on the same cylinder
1150 */
1151 cylno = cbtocylno(fs, bpref);
1152 if (cg_blktot(cgp)[cylno] == 0)
1153 goto norot;
1154 /*
1155 * check the summary information to see if a block is
1156 * available in the requested cylinder starting at the
1157 * requested rotational position and proceeding around.
1158 */
1159 cylbp = cg_blks(fs, cgp, cylno);
1160 pos = cbtorpos(fs, bpref);
1161 for (i = pos; i < fs->fs_nrpos; i++)
1162 if (cylbp[i] > 0)
1163 break;
1164 if (i == fs->fs_nrpos)
1165 for (i = 0; i < pos; i++)
1166 if (cylbp[i] > 0)
1167 break;
1168 if (cylbp[i] > 0) {
1169 /*
1170 * found a rotational position, now find the actual
1171 * block. A panic if none is actually there.
1172 */
1173 pos = cylno % fs->fs_cpc;
1174 bno = (cylno - pos) * fs->fs_spc / NSPB(fs);
1175 if (fs_postbl(fs, pos)[i] == -1) {
1176 printf("pos = %d, i = %d, fs = %s\n",
1177 pos, i, fs->fs_fsmnt);
1178 panic("ffs_alloccgblk: cyl groups corrupted");
1179 }
1180 for (i = fs_postbl(fs, pos)[i];; ) {
1181 if (ffs_isblock(fs, blksfree, bno + i)) {
1182 bno = blkstofrags(fs, (bno + i));
1183 goto gotit;
1184 }
1185 delta = fs_rotbl(fs)[i];
1186 if (delta <= 0 ||
1187 delta + i > fragstoblks(fs, fs->fs_fpg))
1188 break;
1189 i += delta;
1190 }
1191 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt);
1192 panic("ffs_alloccgblk: can't find blk in cyl");
1193 }
1194norot:
1195 /*
1196 * no blocks in the requested cylinder, so take next
1197 * available one in this cylinder group.
1198 */
1199 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
1200 if (bno < 0)
1201 return (0);
1202 cgp->cg_rotor = bno;
1203gotit:
1204 blkno = fragstoblks(fs, bno);
1205 ffs_clrblock(fs, blksfree, (long)blkno);
1206 ffs_clusteracct(fs, cgp, blkno, -1);
1207 cgp->cg_cs.cs_nbfree--;
1208 fs->fs_cstotal.cs_nbfree--;
1209 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--;
1210 cylno = cbtocylno(fs, bno);
1211 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--;
1212 cg_blktot(cgp)[cylno]--;
1213 fs->fs_fmod = 1;
1214 blkno = cgp->cg_cgx * fs->fs_fpg + bno;
1215 if (DOINGSOFTDEP(ITOV(ip)))
1216 softdep_setup_blkmapdep(bp, fs, blkno);
1217 return (blkno);
1218}
1219
1220/*
1221 * Determine whether a cluster can be allocated.
1222 *
1223 * We do not currently check for optimal rotational layout if there
1224 * are multiple choices in the same cylinder group. Instead we just
1225 * take the first one that we find following bpref.
1226 */
1227static ufs_daddr_t
0973c589 1228ffs_clusteralloc(struct inode *ip, int cg, ufs_daddr_t bpref, int len)
984263bc 1229{
3ff2135f
RG
1230 struct fs *fs;
1231 struct cg *cgp;
984263bc
MD
1232 struct buf *bp;
1233 int i, got, run, bno, bit, map;
1234 u_char *mapp;
1235 int32_t *lp;
f719c866 1236 uint8_t *blksfree;
984263bc
MD
1237
1238 fs = ip->i_fs;
1239 if (fs->fs_maxcluster[cg] < len)
1240 return (0);
54078292
MD
1241 if (bread(ip->i_devvp, fsbtodoff(fs, cgtod(fs, cg)),
1242 (int)fs->fs_cgsize, &bp)) {
984263bc 1243 goto fail;
54078292 1244 }
984263bc
MD
1245 cgp = (struct cg *)bp->b_data;
1246 if (!cg_chkmagic(cgp))
1247 goto fail;
70371608 1248
984263bc
MD
1249 /*
1250 * Check to see if a cluster of the needed size (or bigger) is
1251 * available in this cylinder group.
1252 */
1253 lp = &cg_clustersum(cgp)[len];
1254 for (i = len; i <= fs->fs_contigsumsize; i++)
1255 if (*lp++ > 0)
1256 break;
1257 if (i > fs->fs_contigsumsize) {
1258 /*
1259 * This is the first time looking for a cluster in this
1260 * cylinder group. Update the cluster summary information
1261 * to reflect the true maximum sized cluster so that
1262 * future cluster allocation requests can avoid reading
1263 * the cylinder group map only to find no clusters.
1264 */
1265 lp = &cg_clustersum(cgp)[len - 1];
1266 for (i = len - 1; i > 0; i--)
1267 if (*lp-- > 0)
1268 break;
1269 fs->fs_maxcluster[cg] = i;
1270 goto fail;
1271 }
1272 /*
1273 * Search the cluster map to find a big enough cluster.
1274 * We take the first one that we find, even if it is larger
1275 * than we need as we prefer to get one close to the previous
1276 * block allocation. We do not search before the current
1277 * preference point as we do not want to allocate a block
1278 * that is allocated before the previous one (as we will
1279 * then have to wait for another pass of the elevator
1280 * algorithm before it will be read). We prefer to fail and
1281 * be recalled to try an allocation in the next cylinder group.
1282 */
1283 if (dtog(fs, bpref) != cg)
1284 bpref = 0;
1285 else
1286 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref)));
1287 mapp = &cg_clustersfree(cgp)[bpref / NBBY];
1288 map = *mapp++;
1289 bit = 1 << (bpref % NBBY);
1290 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) {
1291 if ((map & bit) == 0) {
1292 run = 0;
1293 } else {
1294 run++;
1295 if (run == len)
1296 break;
1297 }
1298 if ((got & (NBBY - 1)) != (NBBY - 1)) {
1299 bit <<= 1;
1300 } else {
1301 map = *mapp++;
1302 bit = 1;
1303 }
1304 }
1305 if (got >= cgp->cg_nclusterblks)
1306 goto fail;
1307 /*
1308 * Allocate the cluster that we have found.
1309 */
1310 blksfree = cg_blksfree(cgp);
5d5d3444 1311 for (i = 1; i <= len; i++) {
984263bc
MD
1312 if (!ffs_isblock(fs, blksfree, got - run + i))
1313 panic("ffs_clusteralloc: map mismatch");
5d5d3444 1314 }
984263bc
MD
1315 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1);
1316 if (dtog(fs, bno) != cg)
1317 panic("ffs_clusteralloc: allocated out of group");
1318 len = blkstofrags(fs, len);
5d5d3444 1319 for (i = 0; i < len; i += fs->fs_frag) {
984263bc
MD
1320 if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i)
1321 panic("ffs_clusteralloc: lost block");
5d5d3444 1322 }
984263bc
MD
1323 bdwrite(bp);
1324 return (bno);
1325
1326fail:
1327 brelse(bp);
1328 return (0);
1329}
1330
1331/*
1332 * Determine whether an inode can be allocated.
1333 *
1334 * Check to see if an inode is available, and if it is,
1335 * allocate it using the following policy:
1336 * 1) allocate the requested inode.
1337 * 2) allocate the next available inode after the requested
1338 * inode in the specified cylinder group.
b1f7dd27
MD
1339 * 3) the inode must not already be in the inode hash table. We
1340 * can encounter such a case because the vnode reclamation sequence
1341 * frees the bit
1342 * 3) the inode must not already be in the inode hash, otherwise it
1343 * may be in the process of being deallocated. This can occur
1344 * because the bitmap is updated before the inode is removed from
1345 * hash. If we were to reallocate the inode the caller could wind
1346 * up returning a vnode/inode combination which is in an indeterminate
1347 * state.
984263bc
MD
1348 */
1349static ino_t
0973c589 1350ffs_nodealloccg(struct inode *ip, int cg, ufs_daddr_t ipref, int mode)
984263bc 1351{
3ff2135f
RG
1352 struct fs *fs;
1353 struct cg *cgp;
984263bc 1354 struct buf *bp;
f719c866 1355 uint8_t *inosused;
c3274b0a
MD
1356 uint8_t map;
1357 int error, len, arraysize, i;
b1f7dd27
MD
1358 int icheckmiss;
1359 ufs_daddr_t ibase;
984263bc
MD
1360
1361 fs = ip->i_fs;
1362 if (fs->fs_cs(fs, cg).cs_nifree == 0)
1363 return (0);
54078292
MD
1364 error = bread(ip->i_devvp, fsbtodoff(fs, cgtod(fs, cg)),
1365 (int)fs->fs_cgsize, &bp);
984263bc
MD
1366 if (error) {
1367 brelse(bp);
1368 return (0);
1369 }
1370 cgp = (struct cg *)bp->b_data;
1371 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) {
1372 brelse(bp);
1373 return (0);
1374 }
984263bc 1375 inosused = cg_inosused(cgp);
b1f7dd27
MD
1376 icheckmiss = 0;
1377
1378 /*
1379 * Quick check, reuse the most recently free inode or continue
1380 * a scan from where we left off the last time.
1381 */
1382 ibase = cg * fs->fs_ipg;
984263bc
MD
1383 if (ipref) {
1384 ipref %= fs->fs_ipg;
b1f7dd27
MD
1385 if (isclr(inosused, ipref)) {
1386 if (ufs_ihashcheck(ip->i_dev, ibase + ipref) == 0)
1387 goto gotit;
984263bc
MD
1388 }
1389 }
b1f7dd27
MD
1390
1391 /*
1392 * Scan the inode bitmap starting at irotor, be sure to handle
1393 * the edge case by going back to the beginning of the array.
c3274b0a
MD
1394 *
1395 * If the number of inodes is not byte-aligned, the unused bits
1396 * should be set to 1. This will be sanity checked in gotit. Note
1397 * that we have to be sure not to overlap the beginning and end
1398 * when irotor is in the middle of a byte as this will cause the
1399 * same bitmap byte to be checked twice. To solve this problem we
1400 * just convert everything to a byte index for the loop.
b1f7dd27 1401 */
c3274b0a
MD
1402 ipref = (cgp->cg_irotor % fs->fs_ipg) >> 3; /* byte index */
1403 len = (fs->fs_ipg + 7) >> 3; /* byte size */
1404 arraysize = len;
b1f7dd27
MD
1405
1406 while (len > 0) {
c3274b0a
MD
1407 map = inosused[ipref];
1408 if (map != 255) {
b1f7dd27
MD
1409 for (i = 0; i < NBBY; ++i) {
1410 /*
1411 * If we find a free bit we have to make sure
1412 * that the inode is not in the middle of
1413 * being destroyed. The inode should not exist
1414 * in the inode hash.
1415 *
1416 * Adjust the rotor to try to hit the
1417 * quick-check up above.
1418 */
1419 if ((map & (1 << i)) == 0) {
c3274b0a
MD
1420 if (ufs_ihashcheck(ip->i_dev, ibase + (ipref << 3) + i) == 0) {
1421 ipref = (ipref << 3) + i;
b1f7dd27
MD
1422 cgp->cg_irotor = (ipref + 1) % fs->fs_ipg;
1423 goto gotit;
1424 }
1425 ++icheckmiss;
1426 }
1427 }
1428 }
1429
1430 /*
c3274b0a
MD
1431 * Setup for the next byte, start at the beginning again if
1432 * we hit the end of the array.
b1f7dd27 1433 */
c3274b0a 1434 if (++ipref == arraysize)
b1f7dd27 1435 ipref = 0;
c3274b0a 1436 --len;
b1f7dd27
MD
1437 }
1438 if (icheckmiss == cgp->cg_cs.cs_nifree) {
1439 brelse(bp);
1440 return(0);
984263bc
MD
1441 }
1442 printf("fs = %s\n", fs->fs_fsmnt);
b1f7dd27
MD
1443 panic("ffs_nodealloccg: block not in map, icheckmiss/nfree %d/%d",
1444 icheckmiss, cgp->cg_cs.cs_nifree);
984263bc 1445 /* NOTREACHED */
c3274b0a
MD
1446
1447 /*
1448 * ipref is a bit index as of the gotit label.
1449 */
984263bc 1450gotit:
c3274b0a 1451 KKASSERT(ipref >= 0 && ipref < fs->fs_ipg);
b1f7dd27
MD
1452 if (icheckmiss) {
1453 printf("Warning: inode free race avoided %d times\n",
1454 icheckmiss);
1455 }
b1f7dd27 1456 cgp->cg_time = time_second;
984263bc 1457 if (DOINGSOFTDEP(ITOV(ip)))
b1f7dd27 1458 softdep_setup_inomapdep(bp, ip, ibase + ipref);
984263bc
MD
1459 setbit(inosused, ipref);
1460 cgp->cg_cs.cs_nifree--;
1461 fs->fs_cstotal.cs_nifree--;
1462 fs->fs_cs(fs, cg).cs_nifree--;
1463 fs->fs_fmod = 1;
1464 if ((mode & IFMT) == IFDIR) {
1465 cgp->cg_cs.cs_ndir++;
1466 fs->fs_cstotal.cs_ndir++;
1467 fs->fs_cs(fs, cg).cs_ndir++;
1468 }
1469 bdwrite(bp);
b1f7dd27 1470 return (ibase + ipref);
984263bc
MD
1471}
1472
1473/*
1474 * Free a block or fragment.
1475 *
1476 * The specified block or fragment is placed back in the
1477 * free map. If a fragment is deallocated, a possible
1478 * block reassembly is checked.
1479 */
1480void
0973c589 1481ffs_blkfree(struct inode *ip, ufs_daddr_t bno, long size)
984263bc 1482{
3ff2135f
RG
1483 struct fs *fs;
1484 struct cg *cgp;
984263bc
MD
1485 struct buf *bp;
1486 ufs_daddr_t blkno;
1487 int i, error, cg, blk, frags, bbase;
f719c866 1488 uint8_t *blksfree;
984263bc
MD
1489
1490 fs = ip->i_fs;
54078292 1491 VOP_FREEBLKS(ip->i_devvp, fsbtodoff(fs, bno), size);
f719c866 1492 if ((uint)size > fs->fs_bsize || fragoff(fs, size) != 0 ||
984263bc
MD
1493 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) {
1494 printf("dev=%s, bno = %ld, bsize = %ld, size = %ld, fs = %s\n",
1495 devtoname(ip->i_dev), (long)bno, (long)fs->fs_bsize, size,
1496 fs->fs_fsmnt);
1497 panic("ffs_blkfree: bad size");
1498 }
1499 cg = dtog(fs, bno);
f719c866 1500 if ((uint)bno >= fs->fs_size) {
984263bc
MD
1501 printf("bad block %ld, ino %lu\n",
1502 (long)bno, (u_long)ip->i_number);
1503 ffs_fserr(fs, ip->i_uid, "bad block");
1504 return;
1505 }
5d5d3444
MD
1506
1507 /*
1508 * Load the cylinder group
1509 */
54078292
MD
1510 error = bread(ip->i_devvp, fsbtodoff(fs, cgtod(fs, cg)),
1511 (int)fs->fs_cgsize, &bp);
984263bc
MD
1512 if (error) {
1513 brelse(bp);
1514 return;
1515 }
1516 cgp = (struct cg *)bp->b_data;
1517 if (!cg_chkmagic(cgp)) {
1518 brelse(bp);
1519 return;
1520 }
984263bc
MD
1521 cgp->cg_time = time_second;
1522 bno = dtogd(fs, bno);
1523 blksfree = cg_blksfree(cgp);
5d5d3444 1524
984263bc 1525 if (size == fs->fs_bsize) {
5d5d3444
MD
1526 /*
1527 * Free a whole block
1528 */
984263bc
MD
1529 blkno = fragstoblks(fs, bno);
1530 if (!ffs_isfreeblock(fs, blksfree, blkno)) {
1531 printf("dev = %s, block = %ld, fs = %s\n",
1532 devtoname(ip->i_dev), (long)bno, fs->fs_fsmnt);
1533 panic("ffs_blkfree: freeing free block");
1534 }
1535 ffs_setblock(fs, blksfree, blkno);
1536 ffs_clusteracct(fs, cgp, blkno, 1);
1537 cgp->cg_cs.cs_nbfree++;
1538 fs->fs_cstotal.cs_nbfree++;
1539 fs->fs_cs(fs, cg).cs_nbfree++;
1540 i = cbtocylno(fs, bno);
1541 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++;
1542 cg_blktot(cgp)[i]++;
1543 } else {
984263bc 1544 /*
5d5d3444
MD
1545 * Free a fragment within a block.
1546 *
1547 * bno is the starting block number of the fragment being
1548 * freed.
1549 *
1550 * bbase is the starting block number for the filesystem
1551 * block containing the fragment.
1552 *
1553 * blk is the current bitmap for the fragments within the
1554 * filesystem block containing the fragment.
1555 *
1556 * frags is the number of fragments being freed
1557 *
1558 * Call ffs_fragacct() to account for the removal of all
1559 * current fragments, then adjust the bitmap to free the
1560 * requested fragment, and finally call ffs_fragacct() again
1561 * to regenerate the accounting.
984263bc 1562 */
5d5d3444 1563 bbase = bno - fragnum(fs, bno);
984263bc
MD
1564 blk = blkmap(fs, blksfree, bbase);
1565 ffs_fragacct(fs, blk, cgp->cg_frsum, -1);
984263bc
MD
1566 frags = numfrags(fs, size);
1567 for (i = 0; i < frags; i++) {
1568 if (isset(blksfree, bno + i)) {
1569 printf("dev = %s, block = %ld, fs = %s\n",
1570 devtoname(ip->i_dev), (long)(bno + i),
1571 fs->fs_fsmnt);
1572 panic("ffs_blkfree: freeing free frag");
1573 }
1574 setbit(blksfree, bno + i);
1575 }
1576 cgp->cg_cs.cs_nffree += i;
1577 fs->fs_cstotal.cs_nffree += i;
1578 fs->fs_cs(fs, cg).cs_nffree += i;
5d5d3444 1579
984263bc 1580 /*
5d5d3444 1581 * Add back in counts associated with the new frags
984263bc
MD
1582 */
1583 blk = blkmap(fs, blksfree, bbase);
1584 ffs_fragacct(fs, blk, cgp->cg_frsum, 1);
5d5d3444 1585
984263bc 1586 /*
5d5d3444 1587 * If a complete block has been reassembled, account for it
984263bc
MD
1588 */
1589 blkno = fragstoblks(fs, bbase);
1590 if (ffs_isblock(fs, blksfree, blkno)) {
1591 cgp->cg_cs.cs_nffree -= fs->fs_frag;
1592 fs->fs_cstotal.cs_nffree -= fs->fs_frag;
1593 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
1594 ffs_clusteracct(fs, cgp, blkno, 1);
1595 cgp->cg_cs.cs_nbfree++;
1596 fs->fs_cstotal.cs_nbfree++;
1597 fs->fs_cs(fs, cg).cs_nbfree++;
1598 i = cbtocylno(fs, bbase);
1599 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++;
1600 cg_blktot(cgp)[i]++;
1601 }
1602 }
1603 fs->fs_fmod = 1;
1604 bdwrite(bp);
1605}
1606
1607#ifdef DIAGNOSTIC
1608/*
1609 * Verify allocation of a block or fragment. Returns true if block or
1610 * fragment is allocated, false if it is free.
1611 */
1612static int
0973c589 1613ffs_checkblk(struct inode *ip, ufs_daddr_t bno, long size)
984263bc
MD
1614{
1615 struct fs *fs;
1616 struct cg *cgp;
1617 struct buf *bp;
1618 int i, error, frags, free;
f719c866 1619 uint8_t *blksfree;
984263bc
MD
1620
1621 fs = ip->i_fs;
f719c866 1622 if ((uint)size > fs->fs_bsize || fragoff(fs, size) != 0) {
984263bc
MD
1623 printf("bsize = %ld, size = %ld, fs = %s\n",
1624 (long)fs->fs_bsize, size, fs->fs_fsmnt);
1625 panic("ffs_checkblk: bad size");
1626 }
f719c866 1627 if ((uint)bno >= fs->fs_size)
984263bc 1628 panic("ffs_checkblk: bad block %d", bno);
54078292
MD
1629 error = bread(ip->i_devvp, fsbtodoff(fs, cgtod(fs, dtog(fs, bno))),
1630 (int)fs->fs_cgsize, &bp);
984263bc
MD
1631 if (error)
1632 panic("ffs_checkblk: cg bread failed");
1633 cgp = (struct cg *)bp->b_data;
1634 if (!cg_chkmagic(cgp))
1635 panic("ffs_checkblk: cg magic mismatch");
984263bc
MD
1636 blksfree = cg_blksfree(cgp);
1637 bno = dtogd(fs, bno);
1638 if (size == fs->fs_bsize) {
1639 free = ffs_isblock(fs, blksfree, fragstoblks(fs, bno));
1640 } else {
1641 frags = numfrags(fs, size);
1642 for (free = 0, i = 0; i < frags; i++)
1643 if (isset(blksfree, bno + i))
1644 free++;
1645 if (free != 0 && free != frags)
1646 panic("ffs_checkblk: partially free fragment");
1647 }
1648 brelse(bp);
1649 return (!free);
1650}
1651#endif /* DIAGNOSTIC */
1652
1653/*
1654 * Free an inode.
1655 */
1656int
0973c589 1657ffs_vfree(struct vnode *pvp, ino_t ino, int mode)
984263bc
MD
1658{
1659 if (DOINGSOFTDEP(pvp)) {
1660 softdep_freefile(pvp, ino, mode);
1661 return (0);
1662 }
1663 return (ffs_freefile(pvp, ino, mode));
1664}
1665
1666/*
1667 * Do the actual free operation.
1668 * The specified inode is placed back in the free map.
1669 */
0973c589
CP
1670int
1671ffs_freefile(struct vnode *pvp, ino_t ino, int mode)
984263bc 1672{
3ff2135f
RG
1673 struct fs *fs;
1674 struct cg *cgp;
1675 struct inode *pip;
984263bc
MD
1676 struct buf *bp;
1677 int error, cg;
f719c866 1678 uint8_t *inosused;
984263bc
MD
1679
1680 pip = VTOI(pvp);
1681 fs = pip->i_fs;
f719c866 1682 if ((uint)ino >= fs->fs_ipg * fs->fs_ncg)
f91a71dd 1683 panic("ffs_vfree: range: dev = (%d,%d), ino = %"PRId64", fs = %s",
984263bc
MD
1684 major(pip->i_dev), minor(pip->i_dev), ino, fs->fs_fsmnt);
1685 cg = ino_to_cg(fs, ino);
54078292
MD
1686 error = bread(pip->i_devvp, fsbtodoff(fs, cgtod(fs, cg)),
1687 (int)fs->fs_cgsize, &bp);
984263bc
MD
1688 if (error) {
1689 brelse(bp);
1690 return (error);
1691 }
1692 cgp = (struct cg *)bp->b_data;
1693 if (!cg_chkmagic(cgp)) {
1694 brelse(bp);
1695 return (0);
1696 }
984263bc
MD
1697 cgp->cg_time = time_second;
1698 inosused = cg_inosused(cgp);
1699 ino %= fs->fs_ipg;
1700 if (isclr(inosused, ino)) {
1701 printf("dev = %s, ino = %lu, fs = %s\n",
1702 devtoname(pip->i_dev), (u_long)ino, fs->fs_fsmnt);
1703 if (fs->fs_ronly == 0)
1704 panic("ffs_vfree: freeing free inode");
1705 }
1706 clrbit(inosused, ino);
1707 if (ino < cgp->cg_irotor)
1708 cgp->cg_irotor = ino;
1709 cgp->cg_cs.cs_nifree++;
1710 fs->fs_cstotal.cs_nifree++;
1711 fs->fs_cs(fs, cg).cs_nifree++;
1712 if ((mode & IFMT) == IFDIR) {
1713 cgp->cg_cs.cs_ndir--;
1714 fs->fs_cstotal.cs_ndir--;
1715 fs->fs_cs(fs, cg).cs_ndir--;
1716 }
1717 fs->fs_fmod = 1;
1718 bdwrite(bp);
1719 return (0);
1720}
1721
1722/*
1723 * Find a block of the specified size in the specified cylinder group.
1724 *
1725 * It is a panic if a request is made to find a block if none are
1726 * available.
1727 */
1728static ufs_daddr_t
0973c589 1729ffs_mapsearch(struct fs *fs, struct cg *cgp, ufs_daddr_t bpref, int allocsiz)
984263bc
MD
1730{
1731 ufs_daddr_t bno;
1732 int start, len, loc, i;
1733 int blk, field, subfield, pos;
f719c866 1734 uint8_t *blksfree;
984263bc
MD
1735
1736 /*
1737 * find the fragment by searching through the free block
5d5d3444 1738 * map for an appropriate bit pattern.
984263bc
MD
1739 */
1740 if (bpref)
1741 start = dtogd(fs, bpref) / NBBY;
1742 else
1743 start = cgp->cg_frotor / NBBY;
1744 blksfree = cg_blksfree(cgp);
1745 len = howmany(fs->fs_fpg, NBBY) - start;
f719c866 1746 loc = scanc((uint)len, (u_char *)&blksfree[start],
984263bc
MD
1747 (u_char *)fragtbl[fs->fs_frag],
1748 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
1749 if (loc == 0) {
5d5d3444 1750 len = start + 1; /* XXX why overlap here? */
984263bc 1751 start = 0;
f719c866 1752 loc = scanc((uint)len, (u_char *)&blksfree[0],
984263bc
MD
1753 (u_char *)fragtbl[fs->fs_frag],
1754 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
1755 if (loc == 0) {
1756 printf("start = %d, len = %d, fs = %s\n",
1757 start, len, fs->fs_fsmnt);
1758 panic("ffs_alloccg: map corrupted");
1759 /* NOTREACHED */
1760 }
1761 }
1762 bno = (start + len - loc) * NBBY;
1763 cgp->cg_frotor = bno;
1764 /*
1765 * found the byte in the map
1766 * sift through the bits to find the selected frag
1767 */
1768 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
1769 blk = blkmap(fs, blksfree, bno);
1770 blk <<= 1;
1771 field = around[allocsiz];
1772 subfield = inside[allocsiz];
1773 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
1774 if ((blk & field) == subfield)
1775 return (bno + pos);
1776 field <<= 1;
1777 subfield <<= 1;
1778 }
1779 }
1780 printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt);
1781 panic("ffs_alloccg: block not in map");
1782 return (-1);
1783}
1784
1785/*
1786 * Update the cluster map because of an allocation or free.
1787 *
1788 * Cnt == 1 means free; cnt == -1 means allocating.
1789 */
1790static void
0973c589 1791ffs_clusteracct(struct fs *fs, struct cg *cgp, ufs_daddr_t blkno, int cnt)
984263bc
MD
1792{
1793 int32_t *sump;
1794 int32_t *lp;
1795 u_char *freemapp, *mapp;
1796 int i, start, end, forw, back, map, bit;
1797
1798 if (fs->fs_contigsumsize <= 0)
1799 return;
1800 freemapp = cg_clustersfree(cgp);
1801 sump = cg_clustersum(cgp);
1802 /*
1803 * Allocate or clear the actual block.
1804 */
1805 if (cnt > 0)
1806 setbit(freemapp, blkno);
1807 else
1808 clrbit(freemapp, blkno);
1809 /*
1810 * Find the size of the cluster going forward.
1811 */
1812 start = blkno + 1;
1813 end = start + fs->fs_contigsumsize;
1814 if (end >= cgp->cg_nclusterblks)
1815 end = cgp->cg_nclusterblks;
1816 mapp = &freemapp[start / NBBY];
1817 map = *mapp++;
1818 bit = 1 << (start % NBBY);
1819 for (i = start; i < end; i++) {
1820 if ((map & bit) == 0)
1821 break;
1822 if ((i & (NBBY - 1)) != (NBBY - 1)) {
1823 bit <<= 1;
1824 } else {
1825 map = *mapp++;
1826 bit = 1;
1827 }
1828 }
1829 forw = i - start;
1830 /*
1831 * Find the size of the cluster going backward.
1832 */
1833 start = blkno - 1;
1834 end = start - fs->fs_contigsumsize;
1835 if (end < 0)
1836 end = -1;
1837 mapp = &freemapp[start / NBBY];
1838 map = *mapp--;
1839 bit = 1 << (start % NBBY);
1840 for (i = start; i > end; i--) {
1841 if ((map & bit) == 0)
1842 break;
1843 if ((i & (NBBY - 1)) != 0) {
1844 bit >>= 1;
1845 } else {
1846 map = *mapp--;
1847 bit = 1 << (NBBY - 1);
1848 }
1849 }
1850 back = start - i;
1851 /*
1852 * Account for old cluster and the possibly new forward and
1853 * back clusters.
1854 */
1855 i = back + forw + 1;
1856 if (i > fs->fs_contigsumsize)
1857 i = fs->fs_contigsumsize;
1858 sump[i] += cnt;
1859 if (back > 0)
1860 sump[back] -= cnt;
1861 if (forw > 0)
1862 sump[forw] -= cnt;
1863 /*
1864 * Update cluster summary information.
1865 */
1866 lp = &sump[fs->fs_contigsumsize];
1867 for (i = fs->fs_contigsumsize; i > 0; i--)
1868 if (*lp-- > 0)
1869 break;
1870 fs->fs_maxcluster[cgp->cg_cgx] = i;
1871}
1872
1873/*
f719c866 1874 * Fserr prints the name of a filesystem with an error diagnostic.
984263bc
MD
1875 *
1876 * The form of the error message is:
1877 * fs: error message
1878 */
1879static void
f719c866 1880ffs_fserr(struct fs *fs, uint uid, char *cp)
984263bc 1881{
05edc21a
MD
1882 struct thread *td = curthread;
1883 struct proc *p;
984263bc 1884
05edc21a
MD
1885 if ((p = td->td_proc) != NULL) {
1886 log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1,
1887 p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp);
1888 } else {
1889 log(LOG_ERR, "system thread %p, uid %d on %s: %s\n",
1890 td, uid, fs->fs_fsmnt, cp);
1891 }
984263bc 1892}