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