2 * modified for Lites 1.1
4 * Aug 1995, Godmar Back (gback@cs.utah.edu)
5 * University of Utah, Department of Computer Science
8 * Copyright (c) 1982, 1986, 1989, 1993
9 * The Regents of the University of California. All rights reserved.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
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 * 4. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * @(#)ffs_alloc.c 8.8 (Berkeley) 2/21/94
39 #include <sys/param.h>
40 #include <sys/systm.h>
42 #include <sys/vnode.h>
44 #include <sys/mount.h>
45 #include <sys/syslog.h>
48 #include <fs/ext2fs/inode.h>
49 #include <fs/ext2fs/ext2_mount.h>
50 #include <fs/ext2fs/ext2fs.h>
51 #include <fs/ext2fs/fs.h>
52 #include <fs/ext2fs/ext2_extern.h>
54 static daddr_t ext2_alloccg(struct inode *, int, daddr_t, int);
55 static u_long ext2_dirpref(struct inode *);
56 static void ext2_fserr(struct m_ext2fs *, uid_t, char *);
57 static u_long ext2_hashalloc(struct inode *, int, long, int,
58 daddr_t (*)(struct inode *, int, daddr_t,
60 static daddr_t ext2_nodealloccg(struct inode *, int, daddr_t, int);
61 static daddr_t ext2_mapsearch(struct m_ext2fs *, char *, daddr_t);
63 * Allocate a block in the file system.
65 * A preference may be optionally specified. If a preference is given
66 * the following hierarchy is used to allocate a block:
67 * 1) allocate the requested block.
68 * 2) allocate a rotationally optimal block in the same cylinder.
69 * 3) allocate a block in the same cylinder group.
70 * 4) quadradically rehash into other cylinder groups, until an
71 * available block is located.
72 * If no block preference is given the following hierarchy is used
73 * to allocate a block:
74 * 1) allocate a block in the cylinder group that contains the
76 * 2) quadradically rehash into other cylinder groups, until an
77 * available block is located.
81 ext2_alloc(ip, lbn, bpref, size, cred, bnp)
89 struct ext2mount *ump;
95 mtx_assert(EXT2_MTX(ump), MA_OWNED);
97 if ((u_int)size > fs->e2fs_bsize || blkoff(fs, size) != 0) {
98 vn_printf(ip->i_devvp, "bsize = %lu, size = %d, fs = %s\n",
99 (long unsigned int)fs->e2fs_bsize, size, fs->e2fs_fsmnt);
100 panic("ext2_alloc: bad size");
103 panic("ext2_alloc: missing credential");
104 #endif /* DIAGNOSTIC */
105 if (size == fs->e2fs_bsize && fs->e2fs->e2fs_fbcount == 0)
107 if (cred->cr_uid != 0 &&
108 fs->e2fs->e2fs_fbcount < fs->e2fs->e2fs_rbcount)
110 if (bpref >= fs->e2fs->e2fs_bcount)
113 cg = ino_to_cg(fs, ip->i_number);
115 cg = dtog(fs, bpref);
116 bno = (daddr_t)ext2_hashalloc(ip, cg, bpref, fs->e2fs_bsize,
119 ip->i_blocks += btodb(fs->e2fs_bsize);
120 ip->i_flag |= IN_CHANGE | IN_UPDATE;
126 ext2_fserr(fs, cred->cr_uid, "file system full");
127 uprintf("\n%s: write failed, file system is full\n", fs->e2fs_fsmnt);
132 * Reallocate a sequence of blocks into a contiguous sequence of blocks.
134 * The vnode and an array of buffer pointers for a range of sequential
135 * logical blocks to be made contiguous is given. The allocator attempts
136 * to find a range of sequential blocks starting as close as possible to
137 * an fs_rotdelay offset from the end of the allocation for the logical
138 * block immediately preceding the current range. If successful, the
139 * physical block numbers in the buffer pointers and in the inode are
140 * changed to reflect the new allocation. If unsuccessful, the allocation
141 * is left unchanged. The success in doing the reallocation is returned.
142 * Note that the error return is not reflected back to the user. Rather
143 * the previous block allocation will be used.
147 #include <sys/sysctl.h>
148 static int doasyncfree = 1;
149 static int doreallocblks = 1;
152 SYSCTL_INT(_debug, 14, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, "");
153 #endif /* OPT_DEBUG */
158 struct vop_reallocblks_args /* {
160 struct cluster_save *a_buflist;
163 #ifndef FANCY_REALLOC
164 /* printf("ext2_reallocblks not implemented\n"); */
171 struct buf *sbp, *ebp;
172 int32_t *bap, *sbap, *ebap = 0;
173 struct ext2mount *ump;
174 struct cluster_save *buflist;
175 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
176 int32_t start_lbn, end_lbn, soff, newblk, blkno =0;
177 int i, len, start_lvl, end_lvl, pref, ssize;
184 if (fs->fs_contigsumsize <= 0)
187 buflist = ap->a_buflist;
188 len = buflist->bs_nchildren;
189 start_lbn = buflist->bs_children[0]->b_lblkno;
190 end_lbn = start_lbn + len - 1;
192 for (i = 1; i < len; i++)
193 if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
194 panic("ext2_reallocblks: non-cluster");
197 * If the latest allocation is in a new cylinder group, assume that
198 * the filesystem has decided to move and do not force it back to
199 * the previous cylinder group.
201 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
202 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
204 if (ext2_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
205 ext2_getlbns(vp, end_lbn, end_ap, &end_lvl))
208 * Get the starting offset and block map for the first block.
210 if (start_lvl == 0) {
214 idp = &start_ap[start_lvl - 1];
215 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &sbp)) {
219 sbap = (int32_t *)sbp->b_data;
223 * Find the preferred location for the cluster.
226 pref = ext2_blkpref(ip, start_lbn, soff, sbap, blkno);
228 * If the block range spans two block maps, get the second map.
230 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
234 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn)
235 panic("ext2_reallocblk: start == end");
237 ssize = len - (idp->in_off + 1);
238 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp)){
242 ebap = (int32_t *)ebp->b_data;
245 * Search the block map looking for an allocation of the desired size.
247 if ((newblk = (int32_t)ext2_hashalloc(ip, dtog(fs, pref), pref,
248 len, ext2_clusteralloc)) == 0){
253 * We have found a new contiguous block.
255 * First we have to replace the old block pointers with the new
256 * block pointers in the inode and indirect blocks associated
260 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
265 if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap))
266 panic("ext2_reallocblks: alloc mismatch");
271 * Next we must write out the modified inode and indirect blocks.
272 * For strict correctness, the writes should be synchronous since
273 * the old block values may have been written to disk. In practise
274 * they are almost never written, but if we are concerned about
275 * strict correctness, the `doasyncfree' flag should be set to zero.
277 * The test on `doasyncfree' should be changed to test a flag
278 * that shows whether the associated buffers and inodes have
279 * been written. The flag should be set when the cluster is
280 * started and cleared whenever the buffer or inode is flushed.
281 * We can then check below to see if it is set, and do the
282 * synchronous write only when it has been cleared.
284 if (sbap != &ip->i_db[0]) {
290 ip->i_flag |= IN_CHANGE | IN_UPDATE;
301 * Last, free the old blocks and assign the new blocks to the buffers.
303 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
304 ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
306 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
313 if (sbap != &ip->i_db[0])
317 #endif /* FANCY_REALLOC */
321 * Allocate an inode in the file system.
325 ext2_valloc(pvp, mode, cred, vpp)
334 struct ext2mount *ump;
344 if (fs->e2fs->e2fs_ficount == 0)
347 * If it is a directory then obtain a cylinder group based on
348 * ext2_dirpref else obtain it using ino_to_cg. The preferred inode is
349 * always the next inode.
351 if((mode & IFMT) == IFDIR) {
352 cg = ext2_dirpref(pip);
353 if (fs->e2fs_contigdirs[cg] < 255)
354 fs->e2fs_contigdirs[cg]++;
356 cg = ino_to_cg(fs, pip->i_number);
357 if (fs->e2fs_contigdirs[cg] > 0)
358 fs->e2fs_contigdirs[cg]--;
360 ipref = cg * fs->e2fs->e2fs_ipg + 1;
361 ino = (ino_t)ext2_hashalloc(pip, cg, (long)ipref, mode, ext2_nodealloccg);
365 error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp);
367 ext2_vfree(pvp, ino, mode);
373 the question is whether using VGET was such good idea at all -
374 Linux doesn't read the old inode in when it's allocating a
375 new one. I will set at least i_size & i_blocks the zero.
381 /* now we want to make sure that the block pointers are zeroed out */
382 for (i = 0; i < NDADDR; i++)
384 for (i = 0; i < NIADDR; i++)
388 * Set up a new generation number for this inode.
389 * XXX check if this makes sense in ext2
391 if (ip->i_gen == 0 || ++ip->i_gen == 0)
392 ip->i_gen = random() / 2 + 1;
394 printf("ext2_valloc: allocated inode %d\n", ino);
399 ext2_fserr(fs, cred->cr_uid, "out of inodes");
400 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt);
405 * Find a cylinder to place a directory.
407 * The policy implemented by this algorithm is to allocate a
408 * directory inode in the same cylinder group as its parent
409 * directory, but also to reserve space for its files inodes
410 * and data. Restrict the number of directories which may be
411 * allocated one after another in the same cylinder group
412 * without intervening allocation of files.
414 * If we allocate a first level directory then force allocation
415 * in another cylinder group.
419 ext2_dirpref(struct inode *pip)
422 int cg, prefcg, dirsize, cgsize;
423 int avgifree, avgbfree, avgndir, curdirsize;
424 int minifree, minbfree, maxndir;
428 mtx_assert(EXT2_MTX(pip->i_ump), MA_OWNED);
431 avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount;
432 avgbfree = fs->e2fs->e2fs_fbcount / fs->e2fs_gcount;
433 avgndir = fs->e2fs_total_dir / fs->e2fs_gcount;
436 * Force allocation in another cg if creating a first level dir.
438 ASSERT_VOP_LOCKED(ITOV(pip), "ext2fs_dirpref");
439 if (ITOV(pip)->v_vflag & VV_ROOT) {
440 prefcg = arc4random() % fs->e2fs_gcount;
442 minndir = fs->e2fs_ipg;
443 for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
444 if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
445 fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
446 fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
448 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
450 for (cg = 0; cg < prefcg; cg++)
451 if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
452 fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
453 fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
455 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
462 * Count various limits which used for
463 * optimal allocation of a directory inode.
465 maxndir = min(avgndir + fs->e2fs_ipg / 16, fs->e2fs_ipg);
466 minifree = avgifree - avgifree / 4;
469 minbfree = avgbfree - avgbfree / 4;
472 cgsize = fs->e2fs_fsize * fs->e2fs_fpg;
473 dirsize = AVGDIRSIZE;
474 curdirsize = avgndir ? (cgsize - avgbfree * fs->e2fs_bsize) / avgndir : 0;
475 if (dirsize < curdirsize)
476 dirsize = curdirsize;
478 maxcontigdirs = 0; /* dirsize overflowed */
480 maxcontigdirs = min((avgbfree * fs->e2fs_bsize) / dirsize, 255);
481 maxcontigdirs = min(maxcontigdirs, fs->e2fs_ipg / AFPDIR);
482 if (maxcontigdirs == 0)
486 * Limit number of dirs in one cg and reserve space for
487 * regular files, but only if we have no deficit in
490 prefcg = ino_to_cg(fs, pip->i_number);
491 for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
492 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
493 fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
494 fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
495 if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
498 for (cg = 0; cg < prefcg; cg++)
499 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
500 fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
501 fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
502 if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
506 * This is a backstop when we have deficit in space.
508 for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
509 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
511 for (cg = 0; cg < prefcg; cg++)
512 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
518 * Select the desired position for the next block in a file.
520 * we try to mimic what Remy does in inode_getblk/block_getblk
522 * we note: blocknr == 0 means that we're about to allocate either
523 * a direct block or a pointer block at the first level of indirection
524 * (In other words, stuff that will go in i_db[] or i_ib[])
526 * blocknr != 0 means that we're allocating a block that is none
527 * of the above. Then, blocknr tells us the number of the block
528 * that will hold the pointer
531 ext2_blkpref(ip, lbn, indx, bap, blocknr)
539 mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED);
541 /* if the next block is actually what we thought it is,
542 then set the goal to what we thought it should be
544 if(ip->i_next_alloc_block == lbn && ip->i_next_alloc_goal != 0)
545 return ip->i_next_alloc_goal;
547 /* now check whether we were provided with an array that basically
548 tells us previous blocks to which we want to stay closeby
551 for (tmp = indx - 1; tmp >= 0; tmp--)
555 /* else let's fall back to the blocknr, or, if there is none,
556 follow the rule that a block should be allocated near its inode
558 return blocknr ? blocknr :
559 (int32_t)(ip->i_block_group *
560 EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) +
561 ip->i_e2fs->e2fs->e2fs_first_dblock;
565 * Implement the cylinder overflow algorithm.
567 * The policy implemented by this algorithm is:
568 * 1) allocate the block in its requested cylinder group.
569 * 2) quadradically rehash on the cylinder group number.
570 * 3) brute force search for a free block.
573 ext2_hashalloc(struct inode *ip, int cg, long pref, int size,
574 daddr_t (*allocator)(struct inode *, int, daddr_t, int))
580 mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED);
583 * 1: preferred cylinder group
585 result = (*allocator)(ip, cg, pref, size);
589 * 2: quadratic rehash
591 for (i = 1; i < fs->e2fs_gcount; i *= 2) {
593 if (cg >= fs->e2fs_gcount)
594 cg -= fs->e2fs_gcount;
595 result = (*allocator)(ip, cg, 0, size);
600 * 3: brute force search
601 * Note that we start at i == 2, since 0 was checked initially,
602 * and 1 is always checked in the quadratic rehash.
604 cg = (icg + 2) % fs->e2fs_gcount;
605 for (i = 2; i < fs->e2fs_gcount; i++) {
606 result = (*allocator)(ip, cg, 0, size);
610 if (cg == fs->e2fs_gcount)
617 * Determine whether a block can be allocated.
619 * Check to see if a block of the appropriate size is available,
620 * and if it is, allocate it.
623 ext2_alloccg(struct inode *ip, int cg, daddr_t bpref, int size)
627 struct ext2mount *ump;
628 int error, bno, start, end, loc;
633 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0)
636 error = bread(ip->i_devvp, fsbtodb(fs,
637 fs->e2fs_gd[cg].ext2bgd_b_bitmap),
638 (int)fs->e2fs_bsize, NOCRED, &bp);
644 bbp = (char *)bp->b_data;
646 if (dtog(fs, bpref) != cg)
649 bpref = dtogd(fs, bpref);
651 * if the requested block is available, use it
653 if (isclr(bbp, bpref)) {
659 * no blocks in the requested cylinder, so take next
660 * available one in this cylinder group.
661 * first try to get 8 contigous blocks, then fall back to a single
665 start = dtogd(fs, bpref) / NBBY;
668 end = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
669 for (loc = start; loc < end; loc++) {
675 for (loc = 0; loc < start; loc++) {
682 bno = ext2_mapsearch(fs, bbp, bpref);
690 if (isset(bbp, (daddr_t)bno)) {
691 printf("ext2fs_alloccgblk: cg=%d bno=%d fs=%s\n",
692 cg, bno, fs->e2fs_fsmnt);
693 panic("ext2fs_alloccg: dup alloc");
696 setbit(bbp, (daddr_t)bno);
698 fs->e2fs->e2fs_fbcount--;
699 fs->e2fs_gd[cg].ext2bgd_nbfree--;
703 return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
707 * Determine whether an inode can be allocated.
709 * Check to see if an inode is available, and if it is,
710 * allocate it using tode in the specified cylinder group.
713 ext2_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode)
717 struct ext2mount *ump;
718 int error, start, len, loc, map, i;
720 ipref--; /* to avoid a lot of (ipref -1) */
725 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0)
728 error = bread(ip->i_devvp, fsbtodb(fs,
729 fs->e2fs_gd[cg].ext2bgd_i_bitmap),
730 (int)fs->e2fs_bsize, NOCRED, &bp);
736 ibp = (char *)bp->b_data;
738 ipref %= fs->e2fs->e2fs_ipg;
739 if (isclr(ibp, ipref))
742 start = ipref / NBBY;
743 len = howmany(fs->e2fs->e2fs_ipg - ipref, NBBY);
744 loc = skpc(0xff, len, &ibp[start]);
748 loc = skpc(0xff, len, &ibp[0]);
750 printf("cg = %d, ipref = %lld, fs = %s\n",
751 cg, (long long)ipref, fs->e2fs_fsmnt);
752 panic("ext2fs_nodealloccg: map corrupted");
756 i = start + len - loc;
759 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
760 if ((map & i) == 0) {
764 printf("fs = %s\n", fs->e2fs_fsmnt);
765 panic("ext2fs_nodealloccg: block not in map");
770 fs->e2fs_gd[cg].ext2bgd_nifree--;
771 fs->e2fs->e2fs_ficount--;
773 if ((mode & IFMT) == IFDIR) {
774 fs->e2fs_gd[cg].ext2bgd_ndirs++;
775 fs->e2fs_total_dir++;
779 return (cg * fs->e2fs->e2fs_ipg + ipref +1);
783 * Free a block or fragment.
787 ext2_blkfree(ip, bno, size)
794 struct ext2mount *ump;
801 if ((u_int)bno >= fs->e2fs->e2fs_bcount) {
802 printf("bad block %lld, ino %llu\n", (long long)bno,
803 (unsigned long long)ip->i_number);
804 ext2_fserr(fs, ip->i_uid, "bad block");
807 error = bread(ip->i_devvp,
808 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap),
809 (int)fs->e2fs_bsize, NOCRED, &bp);
814 bbp = (char *)bp->b_data;
815 bno = dtogd(fs, bno);
816 if (isclr(bbp, bno)) {
817 printf("block = %lld, fs = %s\n",
818 (long long)bno, fs->e2fs_fsmnt);
819 panic("blkfree: freeing free block");
823 fs->e2fs->e2fs_fbcount++;
824 fs->e2fs_gd[cg].ext2bgd_nbfree++;
835 ext2_vfree(pvp, ino, mode)
843 struct ext2mount *ump;
846 /* mode_t save_i_mode; */
851 if ((u_int)ino > fs->e2fs_ipg * fs->e2fs_gcount)
852 panic("ext2_vfree: range: devvp = %p, ino = %d, fs = %s",
853 pip->i_devvp, ino, fs->e2fs_fsmnt);
855 cg = ino_to_cg(fs, ino);
856 error = bread(pip->i_devvp,
857 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_i_bitmap),
858 (int)fs->e2fs_bsize, NOCRED, &bp);
863 ibp = (char *)bp->b_data;
864 ino = (ino - 1) % fs->e2fs->e2fs_ipg;
865 if (isclr(ibp, ino)) {
866 printf("ino = %llu, fs = %s\n",
867 (unsigned long long)ino, fs->e2fs_fsmnt);
868 if (fs->e2fs_ronly == 0)
869 panic("ifree: freeing free inode");
873 fs->e2fs->e2fs_ficount++;
874 fs->e2fs_gd[cg].ext2bgd_nifree++;
875 if ((mode & IFMT) == IFDIR) {
876 fs->e2fs_gd[cg].ext2bgd_ndirs--;
877 fs->e2fs_total_dir--;
886 * Find a block in the specified cylinder group.
888 * It is a panic if a request is made to find a block if none are
892 ext2_mapsearch(struct m_ext2fs *fs, char *bbp, daddr_t bpref)
895 int start, len, loc, i, map;
898 * find the fragment by searching through the free block
899 * map for an appropriate bit pattern
902 start = dtogd(fs, bpref) / NBBY;
905 len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
906 loc = skpc(0xff, len, &bbp[start]);
910 loc = skpc(0xff, len, &bbp[start]);
912 printf("start = %d, len = %d, fs = %s\n",
913 start, len, fs->e2fs_fsmnt);
914 panic("ext2fs_alloccg: map corrupted");
918 i = start + len - loc;
921 for (i = 1; i < (1 << NBBY); i <<= 1, bno++) {
925 printf("fs = %s\n", fs->e2fs_fsmnt);
926 panic("ext2fs_mapsearch: block not in map");
931 * Fserr prints the name of a file system with an error diagnostic.
933 * The form of the error message is:
937 ext2_fserr(fs, uid, cp)
943 log(LOG_ERR, "uid %u on %s: %s\n", uid, fs->e2fs_fsmnt, cp);
951 if (i == 0 || i == 1)
953 for (a3 = 3, a5 = 5, a7 = 7;
954 a3 <= i || a5 <= i || a7 <= i;
955 a3 *= 3, a5 *= 5, a7 *= 7)
956 if (i == a3 || i == a5 || i == a7)