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