1 /* $NetBSD: ext2fs_alloc.c,v 1.21 2003/10/05 17:48:49 bouyer Exp $ */ 2 3 /* 4 * Copyright (c) 1982, 1986, 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * @(#)ffs_alloc.c 8.11 (Berkeley) 10/27/94 32 * Modified for ext2fs by Manuel Bouyer. 33 */ 34 35 /* 36 * Copyright (c) 1997 Manuel Bouyer. 37 * 38 * Redistribution and use in source and binary forms, with or without 39 * modification, are permitted provided that the following conditions 40 * are met: 41 * 1. Redistributions of source code must retain the above copyright 42 * notice, this list of conditions and the following disclaimer. 43 * 2. Redistributions in binary form must reproduce the above copyright 44 * notice, this list of conditions and the following disclaimer in the 45 * documentation and/or other materials provided with the distribution. 46 * 3. All advertising materials mentioning features or use of this software 47 * must display the following acknowledgement: 48 * This product includes software developed by Manuel Bouyer. 49 * 4. The name of the author may not be used to endorse or promote products 50 * derived from this software without specific prior written permission. 51 * 52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 62 * SUCH DAMAGE. 63 * 64 * @(#)ffs_alloc.c 8.11 (Berkeley) 10/27/94 65 * Modified for ext2fs by Manuel Bouyer. 66 */ 67 68 #include <sys/cdefs.h> 69 __KERNEL_RCSID(0, "$NetBSD: ext2fs_alloc.c,v 1.21 2003/10/05 17:48:49 bouyer Exp $"); 70 71 #include <sys/param.h> 72 #include <sys/systm.h> 73 #include <sys/buf.h> 74 #include <sys/proc.h> 75 #include <sys/vnode.h> 76 #include <sys/mount.h> 77 #include <sys/kernel.h> 78 #include <sys/syslog.h> 79 80 #include <ufs/ufs/inode.h> 81 #include <ufs/ufs/ufs_extern.h> 82 83 #include <ufs/ext2fs/ext2fs.h> 84 #include <ufs/ext2fs/ext2fs_extern.h> 85 86 u_long ext2gennumber; 87 88 static daddr_t ext2fs_alloccg __P((struct inode *, int, daddr_t, int)); 89 static u_long ext2fs_dirpref __P((struct m_ext2fs *)); 90 static void ext2fs_fserr __P((struct m_ext2fs *, u_int, char *)); 91 static u_long ext2fs_hashalloc __P((struct inode *, int, long, int, 92 daddr_t (*)(struct inode *, int, daddr_t, 93 int))); 94 static daddr_t ext2fs_nodealloccg __P((struct inode *, int, daddr_t, int)); 95 static daddr_t ext2fs_mapsearch __P((struct m_ext2fs *, char *, daddr_t)); 96 97 /* 98 * Allocate a block in the file system. 99 * 100 * A preference may be optionally specified. If a preference is given 101 * the following hierarchy is used to allocate a block: 102 * 1) allocate the requested block. 103 * 2) allocate a rotationally optimal block in the same cylinder. 104 * 3) allocate a block in the same cylinder group. 105 * 4) quadradically rehash into other cylinder groups, until an 106 * available block is located. 107 * If no block preference is given the following hierarchy is used 108 * to allocate a block: 109 * 1) allocate a block in the cylinder group that contains the 110 * inode for the file. 111 * 2) quadradically rehash into other cylinder groups, until an 112 * available block is located. 113 */ 114 int 115 ext2fs_alloc(ip, lbn, bpref, cred, bnp) 116 struct inode *ip; 117 daddr_t lbn, bpref; 118 struct ucred *cred; 119 daddr_t *bnp; 120 { 121 struct m_ext2fs *fs; 122 daddr_t bno; 123 int cg; 124 125 *bnp = 0; 126 fs = ip->i_e2fs; 127 #ifdef DIAGNOSTIC 128 if (cred == NOCRED) 129 panic("ext2fs_alloc: missing credential"); 130 #endif /* DIAGNOSTIC */ 131 if (fs->e2fs.e2fs_fbcount == 0) 132 goto nospace; 133 if (cred->cr_uid != 0 && freespace(fs) <= 0) 134 goto nospace; 135 if (bpref >= fs->e2fs.e2fs_bcount) 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 = (daddr_t)ext2fs_hashalloc(ip, cg, bpref, fs->e2fs_bsize, 142 ext2fs_alloccg); 143 if (bno > 0) { 144 ip->i_e2fs_nblock += btodb(fs->e2fs_bsize); 145 ip->i_flag |= IN_CHANGE | IN_UPDATE; 146 *bnp = bno; 147 return (0); 148 } 149 nospace: 150 ext2fs_fserr(fs, cred->cr_uid, "file system full"); 151 uprintf("\n%s: write failed, file system is full\n", fs->e2fs_fsmnt); 152 return (ENOSPC); 153 } 154 155 /* 156 * Allocate an inode in the file system. 157 * 158 * If allocating a directory, use ext2fs_dirpref to select the inode. 159 * If allocating in a directory, the following hierarchy is followed: 160 * 1) allocate the preferred inode. 161 * 2) allocate an inode in the same cylinder group. 162 * 3) quadradically rehash into other cylinder groups, until an 163 * available inode is located. 164 * If no inode preference is given the following hierarchy is used 165 * to allocate an inode: 166 * 1) allocate an inode in cylinder group 0. 167 * 2) quadradically rehash into other cylinder groups, until an 168 * available inode is located. 169 */ 170 int 171 ext2fs_valloc(v) 172 void *v; 173 { 174 struct vop_valloc_args /* { 175 struct vnode *a_pvp; 176 int a_mode; 177 struct ucred *a_cred; 178 struct vnode **a_vpp; 179 } */ *ap = v; 180 struct vnode *pvp = ap->a_pvp; 181 struct inode *pip; 182 struct m_ext2fs *fs; 183 struct inode *ip; 184 mode_t mode = ap->a_mode; 185 ino_t ino, ipref; 186 int cg, error; 187 188 *ap->a_vpp = NULL; 189 pip = VTOI(pvp); 190 fs = pip->i_e2fs; 191 if (fs->e2fs.e2fs_ficount == 0) 192 goto noinodes; 193 194 if ((mode & IFMT) == IFDIR) 195 cg = ext2fs_dirpref(fs); 196 else 197 cg = ino_to_cg(fs, pip->i_number); 198 ipref = cg * fs->e2fs.e2fs_ipg + 1; 199 ino = (ino_t)ext2fs_hashalloc(pip, cg, (long)ipref, mode, ext2fs_nodealloccg); 200 if (ino == 0) 201 goto noinodes; 202 error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 203 if (error) { 204 VOP_VFREE(pvp, ino, mode); 205 return (error); 206 } 207 ip = VTOI(*ap->a_vpp); 208 if (ip->i_e2fs_mode && ip->i_e2fs_nlink != 0) { 209 printf("mode = 0%o, nlinks %d, inum = %d, fs = %s\n", 210 ip->i_e2fs_mode, ip->i_e2fs_nlink, ip->i_number, fs->e2fs_fsmnt); 211 panic("ext2fs_valloc: dup alloc"); 212 } 213 214 memset(ip->i_din.e2fs_din, 0, sizeof(struct ext2fs_dinode)); 215 216 /* 217 * Set up a new generation number for this inode. 218 */ 219 if (++ext2gennumber < (u_long)time.tv_sec) 220 ext2gennumber = time.tv_sec; 221 ip->i_e2fs_gen = ext2gennumber; 222 return (0); 223 noinodes: 224 ext2fs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 225 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt); 226 return (ENOSPC); 227 } 228 229 /* 230 * Find a cylinder to place a directory. 231 * 232 * The policy implemented by this algorithm is to select from 233 * among those cylinder groups with above the average number of 234 * free inodes, the one with the smallest number of directories. 235 */ 236 static u_long 237 ext2fs_dirpref(fs) 238 struct m_ext2fs *fs; 239 { 240 int cg, maxspace, mincg, avgifree; 241 242 avgifree = fs->e2fs.e2fs_ficount / fs->e2fs_ncg; 243 maxspace = 0; 244 mincg = -1; 245 for (cg = 0; cg < fs->e2fs_ncg; cg++) 246 if ( fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree) { 247 if (mincg == -1 || fs->e2fs_gd[cg].ext2bgd_nbfree > maxspace) { 248 mincg = cg; 249 maxspace = fs->e2fs_gd[cg].ext2bgd_nbfree; 250 } 251 } 252 return mincg; 253 } 254 255 /* 256 * Select the desired position for the next block in a file. The file is 257 * logically divided into sections. The first section is composed of the 258 * direct blocks. Each additional section contains fs_maxbpg blocks. 259 * 260 * If no blocks have been allocated in the first section, the policy is to 261 * request a block in the same cylinder group as the inode that describes 262 * the file. Otherwise, the policy is to try to allocate the blocks 263 * contigously. The two fields of the ext2 inode extension (see 264 * ufs/ufs/inode.h) help this. 265 */ 266 daddr_t 267 ext2fs_blkpref(ip, lbn, indx, bap) 268 struct inode *ip; 269 daddr_t lbn; 270 int indx; 271 int32_t *bap; /* XXX ondisk32 */ 272 { 273 struct m_ext2fs *fs; 274 int cg, i; 275 276 fs = ip->i_e2fs; 277 /* 278 * if we are doing contigous lbn allocation, try to alloc blocks 279 * contigously on disk 280 */ 281 282 if ( ip->i_e2fs_last_blk && lbn == ip->i_e2fs_last_lblk + 1) { 283 return ip->i_e2fs_last_blk + 1; 284 } 285 286 /* 287 * bap, if provided, gives us a list of blocks to which we want to 288 * stay close 289 */ 290 291 if (bap) { 292 for (i = indx; i >= 0 ; i--) { 293 if (bap[i]) { 294 return fs2h32(bap[i]) + 1; 295 } 296 } 297 } 298 299 /* fall back to the first block of the cylinder containing the inode */ 300 301 cg = ino_to_cg(fs, ip->i_number); 302 return fs->e2fs.e2fs_bpg * cg + fs->e2fs.e2fs_first_dblock + 1; 303 } 304 305 /* 306 * Implement the cylinder overflow algorithm. 307 * 308 * The policy implemented by this algorithm is: 309 * 1) allocate the block in its requested cylinder group. 310 * 2) quadradically rehash on the cylinder group number. 311 * 3) brute force search for a free block. 312 */ 313 static u_long 314 ext2fs_hashalloc(ip, cg, pref, size, allocator) 315 struct inode *ip; 316 int cg; 317 long pref; 318 int size; /* size for data blocks, mode for inodes */ 319 daddr_t (*allocator) __P((struct inode *, int, daddr_t, int)); 320 { 321 struct m_ext2fs *fs; 322 long result; 323 int i, icg = cg; 324 325 fs = ip->i_e2fs; 326 /* 327 * 1: preferred cylinder group 328 */ 329 result = (*allocator)(ip, cg, pref, size); 330 if (result) 331 return (result); 332 /* 333 * 2: quadratic rehash 334 */ 335 for (i = 1; i < fs->e2fs_ncg; i *= 2) { 336 cg += i; 337 if (cg >= fs->e2fs_ncg) 338 cg -= fs->e2fs_ncg; 339 result = (*allocator)(ip, cg, 0, size); 340 if (result) 341 return (result); 342 } 343 /* 344 * 3: brute force search 345 * Note that we start at i == 2, since 0 was checked initially, 346 * and 1 is always checked in the quadratic rehash. 347 */ 348 cg = (icg + 2) % fs->e2fs_ncg; 349 for (i = 2; i < fs->e2fs_ncg; i++) { 350 result = (*allocator)(ip, cg, 0, size); 351 if (result) 352 return (result); 353 cg++; 354 if (cg == fs->e2fs_ncg) 355 cg = 0; 356 } 357 return (0); 358 } 359 360 /* 361 * Determine whether a block can be allocated. 362 * 363 * Check to see if a block of the appropriate size is available, 364 * and if it is, allocate it. 365 */ 366 367 static daddr_t 368 ext2fs_alloccg(ip, cg, bpref, size) 369 struct inode *ip; 370 int cg; 371 daddr_t bpref; 372 int size; 373 { 374 struct m_ext2fs *fs; 375 char *bbp; 376 struct buf *bp; 377 /* XXX ondisk32 */ 378 int error, bno, start, end, loc; 379 380 fs = ip->i_e2fs; 381 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) 382 return (0); 383 error = bread(ip->i_devvp, fsbtodb(fs, 384 fs->e2fs_gd[cg].ext2bgd_b_bitmap), 385 (int)fs->e2fs_bsize, NOCRED, &bp); 386 if (error) { 387 brelse(bp); 388 return (0); 389 } 390 bbp = (char *)bp->b_data; 391 392 if (dtog(fs, bpref) != cg) 393 bpref = 0; 394 if (bpref != 0) { 395 bpref = dtogd(fs, bpref); 396 /* 397 * if the requested block is available, use it 398 */ 399 if (isclr(bbp, bpref)) { 400 bno = bpref; 401 goto gotit; 402 } 403 } 404 /* 405 * no blocks in the requested cylinder, so take next 406 * available one in this cylinder group. 407 * first try to get 8 contigous blocks, then fall back to a single 408 * block. 409 */ 410 if (bpref) 411 start = dtogd(fs, bpref) / NBBY; 412 else 413 start = 0; 414 end = howmany(fs->e2fs.e2fs_fpg, NBBY) - start; 415 for (loc = start; loc < end; loc++) { 416 if (bbp[loc] == 0) { 417 bno = loc * NBBY; 418 goto gotit; 419 } 420 } 421 for (loc = 0; loc < start; loc++) { 422 if (bbp[loc] == 0) { 423 bno = loc * NBBY; 424 goto gotit; 425 } 426 } 427 428 bno = ext2fs_mapsearch(fs, bbp, bpref); 429 if (bno < 0) 430 return (0); 431 gotit: 432 #ifdef DIAGNOSTIC 433 if (isset(bbp, (daddr_t)bno)) { 434 printf("ext2fs_alloccgblk: cg=%d bno=%d fs=%s\n", 435 cg, bno, fs->e2fs_fsmnt); 436 panic("ext2fs_alloccg: dup alloc"); 437 } 438 #endif 439 setbit(bbp, (daddr_t)bno); 440 fs->e2fs.e2fs_fbcount--; 441 fs->e2fs_gd[cg].ext2bgd_nbfree--; 442 fs->e2fs_fmod = 1; 443 bdwrite(bp); 444 return (cg * fs->e2fs.e2fs_fpg + fs->e2fs.e2fs_first_dblock + bno); 445 } 446 447 /* 448 * Determine whether an inode can be allocated. 449 * 450 * Check to see if an inode is available, and if it is, 451 * allocate it using the following policy: 452 * 1) allocate the requested inode. 453 * 2) allocate the next available inode after the requested 454 * inode in the specified cylinder group. 455 */ 456 static daddr_t 457 ext2fs_nodealloccg(ip, cg, ipref, mode) 458 struct inode *ip; 459 int cg; 460 daddr_t ipref; 461 int mode; 462 { 463 struct m_ext2fs *fs; 464 char *ibp; 465 struct buf *bp; 466 int error, start, len, loc, map, i; 467 468 ipref--; /* to avoid a lot of (ipref -1) */ 469 fs = ip->i_e2fs; 470 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) 471 return (0); 472 error = bread(ip->i_devvp, fsbtodb(fs, 473 fs->e2fs_gd[cg].ext2bgd_i_bitmap), 474 (int)fs->e2fs_bsize, NOCRED, &bp); 475 if (error) { 476 brelse(bp); 477 return (0); 478 } 479 ibp = (char *)bp->b_data; 480 if (ipref) { 481 ipref %= fs->e2fs.e2fs_ipg; 482 if (isclr(ibp, ipref)) 483 goto gotit; 484 } 485 start = ipref / NBBY; 486 len = howmany(fs->e2fs.e2fs_ipg - ipref, NBBY); 487 loc = skpc(0xff, len, &ibp[start]); 488 if (loc == 0) { 489 len = start + 1; 490 start = 0; 491 loc = skpc(0xff, len, &ibp[0]); 492 if (loc == 0) { 493 printf("cg = %d, ipref = %lld, fs = %s\n", 494 cg, (long long)ipref, fs->e2fs_fsmnt); 495 panic("ext2fs_nodealloccg: map corrupted"); 496 /* NOTREACHED */ 497 } 498 } 499 i = start + len - loc; 500 map = ibp[i]; 501 ipref = i * NBBY; 502 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 503 if ((map & i) == 0) { 504 goto gotit; 505 } 506 } 507 printf("fs = %s\n", fs->e2fs_fsmnt); 508 panic("ext2fs_nodealloccg: block not in map"); 509 /* NOTREACHED */ 510 gotit: 511 setbit(ibp, ipref); 512 fs->e2fs.e2fs_ficount--; 513 fs->e2fs_gd[cg].ext2bgd_nifree--; 514 fs->e2fs_fmod = 1; 515 if ((mode & IFMT) == IFDIR) { 516 fs->e2fs_gd[cg].ext2bgd_ndirs++; 517 } 518 bdwrite(bp); 519 return (cg * fs->e2fs.e2fs_ipg + ipref +1); 520 } 521 522 /* 523 * Free a block. 524 * 525 * The specified block is placed back in the 526 * free map. 527 */ 528 void 529 ext2fs_blkfree(ip, bno) 530 struct inode *ip; 531 daddr_t bno; 532 { 533 struct m_ext2fs *fs; 534 char *bbp; 535 struct buf *bp; 536 int error, cg; 537 538 fs = ip->i_e2fs; 539 cg = dtog(fs, bno); 540 if ((u_int)bno >= fs->e2fs.e2fs_bcount) { 541 printf("bad block %lld, ino %d\n", (long long)bno, 542 ip->i_number); 543 ext2fs_fserr(fs, ip->i_e2fs_uid, "bad block"); 544 return; 545 } 546 error = bread(ip->i_devvp, 547 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap), 548 (int)fs->e2fs_bsize, NOCRED, &bp); 549 if (error) { 550 brelse(bp); 551 return; 552 } 553 bbp = (char *)bp->b_data; 554 bno = dtogd(fs, bno); 555 if (isclr(bbp, bno)) { 556 printf("dev = 0x%x, block = %lld, fs = %s\n", 557 ip->i_dev, (long long)bno, fs->e2fs_fsmnt); 558 panic("blkfree: freeing free block"); 559 } 560 clrbit(bbp, bno); 561 fs->e2fs.e2fs_fbcount++; 562 fs->e2fs_gd[cg].ext2bgd_nbfree++; 563 564 fs->e2fs_fmod = 1; 565 bdwrite(bp); 566 } 567 568 /* 569 * Free an inode. 570 * 571 * The specified inode is placed back in the free map. 572 */ 573 int 574 ext2fs_vfree(v) 575 void *v; 576 { 577 struct vop_vfree_args /* { 578 struct vnode *a_pvp; 579 ino_t a_ino; 580 int a_mode; 581 } */ *ap = v; 582 struct m_ext2fs *fs; 583 char *ibp; 584 struct inode *pip; 585 ino_t ino = ap->a_ino; 586 struct buf *bp; 587 int error, cg; 588 589 pip = VTOI(ap->a_pvp); 590 fs = pip->i_e2fs; 591 if ((u_int)ino >= fs->e2fs.e2fs_icount || (u_int)ino < EXT2_FIRSTINO) 592 panic("ifree: range: dev = 0x%x, ino = %d, fs = %s", 593 pip->i_dev, ino, fs->e2fs_fsmnt); 594 cg = ino_to_cg(fs, ino); 595 error = bread(pip->i_devvp, 596 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_i_bitmap), 597 (int)fs->e2fs_bsize, NOCRED, &bp); 598 if (error) { 599 brelse(bp); 600 return (0); 601 } 602 ibp = (char *)bp->b_data; 603 ino = (ino - 1) % fs->e2fs.e2fs_ipg; 604 if (isclr(ibp, ino)) { 605 printf("dev = 0x%x, ino = %d, fs = %s\n", 606 pip->i_dev, ino, fs->e2fs_fsmnt); 607 if (fs->e2fs_ronly == 0) 608 panic("ifree: freeing free inode"); 609 } 610 clrbit(ibp, ino); 611 fs->e2fs.e2fs_ficount++; 612 fs->e2fs_gd[cg].ext2bgd_nifree++; 613 if ((ap->a_mode & IFMT) == IFDIR) { 614 fs->e2fs_gd[cg].ext2bgd_ndirs--; 615 } 616 fs->e2fs_fmod = 1; 617 bdwrite(bp); 618 return (0); 619 } 620 621 /* 622 * Find a block in the specified cylinder group. 623 * 624 * It is a panic if a request is made to find a block if none are 625 * available. 626 */ 627 628 static daddr_t 629 ext2fs_mapsearch(fs, bbp, bpref) 630 struct m_ext2fs *fs; 631 char *bbp; 632 daddr_t bpref; 633 { 634 daddr_t bno; 635 int start, len, loc, i, map; 636 637 /* 638 * find the fragment by searching through the free block 639 * map for an appropriate bit pattern 640 */ 641 if (bpref) 642 start = dtogd(fs, bpref) / NBBY; 643 else 644 start = 0; 645 len = howmany(fs->e2fs.e2fs_fpg, NBBY) - start; 646 loc = skpc(0xff, len, &bbp[start]); 647 if (loc == 0) { 648 len = start + 1; 649 start = 0; 650 loc = skpc(0xff, len, &bbp[start]); 651 if (loc == 0) { 652 printf("start = %d, len = %d, fs = %s\n", 653 start, len, fs->e2fs_fsmnt); 654 panic("ext2fs_alloccg: map corrupted"); 655 /* NOTREACHED */ 656 } 657 } 658 i = start + len - loc; 659 map = bbp[i]; 660 bno = i * NBBY; 661 for (i = 1; i < (1 << NBBY); i <<= 1, bno++) { 662 if ((map & i) == 0) 663 return (bno); 664 } 665 printf("fs = %s\n", fs->e2fs_fsmnt); 666 panic("ext2fs_mapsearch: block not in map"); 667 /* NOTREACHED */ 668 } 669 670 /* 671 * Fserr prints the name of a file system with an error diagnostic. 672 * 673 * The form of the error message is: 674 * fs: error message 675 */ 676 static void 677 ext2fs_fserr(fs, uid, cp) 678 struct m_ext2fs *fs; 679 u_int uid; 680 char *cp; 681 { 682 683 log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->e2fs_fsmnt, cp); 684 } 685