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