1 /*- 2 * modified for Lites 1.1 3 * 4 * Aug 1995, Godmar Back (gback@cs.utah.edu) 5 * University of Utah, Department of Computer Science 6 */ 7 /*- 8 * SPDX-License-Identifier: BSD-3-Clause 9 * 10 * Copyright (c) 1982, 1986, 1989, 1993 11 * The Regents of the University of California. All rights reserved. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. Neither the name of the University nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 * 37 * @(#)ffs_alloc.c 8.8 (Berkeley) 2/21/94 38 * $FreeBSD$ 39 */ 40 41 #include <sys/param.h> 42 #include <sys/systm.h> 43 #include <sys/conf.h> 44 #include <sys/vnode.h> 45 #include <sys/stat.h> 46 #include <sys/mount.h> 47 #include <sys/sysctl.h> 48 #include <sys/syslog.h> 49 #include <sys/buf.h> 50 #include <sys/endian.h> 51 52 #include <fs/ext2fs/fs.h> 53 #include <fs/ext2fs/inode.h> 54 #include <fs/ext2fs/ext2_mount.h> 55 #include <fs/ext2fs/ext2fs.h> 56 #include <fs/ext2fs/ext2_extern.h> 57 58 static daddr_t ext2_alloccg(struct inode *, int, daddr_t, int); 59 static daddr_t ext2_clusteralloc(struct inode *, int, daddr_t, int); 60 static u_long ext2_dirpref(struct inode *); 61 static e4fs_daddr_t ext2_hashalloc(struct inode *, int, long, int, 62 daddr_t (*)(struct inode *, int, daddr_t, 63 int)); 64 static daddr_t ext2_nodealloccg(struct inode *, int, daddr_t, int); 65 static daddr_t ext2_mapsearch(struct m_ext2fs *, char *, daddr_t); 66 67 /* 68 * Allocate a block in the filesystem. 69 * 70 * A preference may be optionally specified. If a preference is given 71 * the following hierarchy is used to allocate a block: 72 * 1) allocate the requested block. 73 * 2) allocate a rotationally optimal block in the same cylinder. 74 * 3) allocate a block in the same cylinder group. 75 * 4) quadradically rehash into other cylinder groups, until an 76 * available block is located. 77 * If no block preference is given the following hierarchy is used 78 * to allocate a block: 79 * 1) allocate a block in the cylinder group that contains the 80 * inode for the file. 81 * 2) quadradically rehash into other cylinder groups, until an 82 * available block is located. 83 */ 84 int 85 ext2_alloc(struct inode *ip, daddr_t lbn, e4fs_daddr_t bpref, int size, 86 struct ucred *cred, e4fs_daddr_t *bnp) 87 { 88 struct m_ext2fs *fs; 89 struct ext2mount *ump; 90 e4fs_daddr_t bno; 91 int cg; 92 93 *bnp = 0; 94 fs = ip->i_e2fs; 95 ump = ip->i_ump; 96 mtx_assert(EXT2_MTX(ump), MA_OWNED); 97 #ifdef INVARIANTS 98 if ((u_int)size > fs->e2fs_bsize || blkoff(fs, size) != 0) { 99 vn_printf(ip->i_devvp, "bsize = %lu, size = %d, fs = %s\n", 100 (long unsigned int)fs->e2fs_bsize, size, fs->e2fs_fsmnt); 101 panic("ext2_alloc: bad size"); 102 } 103 if (cred == NOCRED) 104 panic("ext2_alloc: missing credential"); 105 #endif /* INVARIANTS */ 106 if (size == fs->e2fs_bsize && fs->e2fs->e2fs_fbcount == 0) 107 goto nospace; 108 if (cred->cr_uid != 0 && 109 fs->e2fs->e2fs_fbcount < fs->e2fs->e2fs_rbcount) 110 goto nospace; 111 if (bpref >= fs->e2fs->e2fs_bcount) 112 bpref = 0; 113 if (bpref == 0) 114 cg = ino_to_cg(fs, ip->i_number); 115 else 116 cg = dtog(fs, bpref); 117 bno = (daddr_t)ext2_hashalloc(ip, cg, bpref, fs->e2fs_bsize, 118 ext2_alloccg); 119 if (bno > 0) { 120 /* set next_alloc fields as done in block_getblk */ 121 ip->i_next_alloc_block = lbn; 122 ip->i_next_alloc_goal = bno; 123 124 ip->i_blocks += btodb(fs->e2fs_bsize); 125 ip->i_flag |= IN_CHANGE | IN_UPDATE; 126 *bnp = bno; 127 return (0); 128 } 129 nospace: 130 EXT2_UNLOCK(ump); 131 ext2_fserr(fs, cred->cr_uid, "filesystem full"); 132 uprintf("\n%s: write failed, filesystem is full\n", fs->e2fs_fsmnt); 133 return (ENOSPC); 134 } 135 136 /* 137 * Allocate EA's block for inode. 138 */ 139 e4fs_daddr_t 140 ext2_alloc_meta(struct inode *ip) 141 { 142 struct m_ext2fs *fs; 143 daddr_t blk; 144 145 fs = ip->i_e2fs; 146 147 EXT2_LOCK(ip->i_ump); 148 blk = ext2_hashalloc(ip, ino_to_cg(fs, ip->i_number), 0, fs->e2fs_bsize, 149 ext2_alloccg); 150 if (0 == blk) 151 EXT2_UNLOCK(ip->i_ump); 152 153 return (blk); 154 } 155 156 /* 157 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 158 * 159 * The vnode and an array of buffer pointers for a range of sequential 160 * logical blocks to be made contiguous is given. The allocator attempts 161 * to find a range of sequential blocks starting as close as possible to 162 * an fs_rotdelay offset from the end of the allocation for the logical 163 * block immediately preceding the current range. If successful, the 164 * physical block numbers in the buffer pointers and in the inode are 165 * changed to reflect the new allocation. If unsuccessful, the allocation 166 * is left unchanged. The success in doing the reallocation is returned. 167 * Note that the error return is not reflected back to the user. Rather 168 * the previous block allocation will be used. 169 */ 170 171 static SYSCTL_NODE(_vfs, OID_AUTO, ext2fs, CTLFLAG_RW, 0, "EXT2FS filesystem"); 172 173 static int doasyncfree = 1; 174 175 SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, 176 "Use asychronous writes to update block pointers when freeing blocks"); 177 178 static int doreallocblks = 0; 179 180 SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 181 182 int 183 ext2_reallocblks(struct vop_reallocblks_args *ap) 184 { 185 struct m_ext2fs *fs; 186 struct inode *ip; 187 struct vnode *vp; 188 struct buf *sbp, *ebp; 189 uint32_t *bap, *sbap, *ebap; 190 struct ext2mount *ump; 191 struct cluster_save *buflist; 192 struct indir start_ap[EXT2_NIADDR + 1], end_ap[EXT2_NIADDR + 1], *idp; 193 e2fs_lbn_t start_lbn, end_lbn; 194 int soff; 195 e2fs_daddr_t newblk, blkno; 196 int i, len, start_lvl, end_lvl, pref, ssize; 197 198 if (doreallocblks == 0) 199 return (ENOSPC); 200 201 vp = ap->a_vp; 202 ip = VTOI(vp); 203 fs = ip->i_e2fs; 204 ump = ip->i_ump; 205 206 if (fs->e2fs_contigsumsize <= 0 || ip->i_flag & IN_E4EXTENTS) 207 return (ENOSPC); 208 209 buflist = ap->a_buflist; 210 len = buflist->bs_nchildren; 211 start_lbn = buflist->bs_children[0]->b_lblkno; 212 end_lbn = start_lbn + len - 1; 213 #ifdef INVARIANTS 214 for (i = 1; i < len; i++) 215 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 216 panic("ext2_reallocblks: non-cluster"); 217 #endif 218 /* 219 * If the cluster crosses the boundary for the first indirect 220 * block, leave space for the indirect block. Indirect blocks 221 * are initially laid out in a position after the last direct 222 * block. Block reallocation would usually destroy locality by 223 * moving the indirect block out of the way to make room for 224 * data blocks if we didn't compensate here. We should also do 225 * this for other indirect block boundaries, but it is only 226 * important for the first one. 227 */ 228 if (start_lbn < EXT2_NDADDR && end_lbn >= EXT2_NDADDR) 229 return (ENOSPC); 230 /* 231 * If the latest allocation is in a new cylinder group, assume that 232 * the filesystem has decided to move and do not force it back to 233 * the previous cylinder group. 234 */ 235 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 236 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 237 return (ENOSPC); 238 if (ext2_getlbns(vp, start_lbn, start_ap, &start_lvl) || 239 ext2_getlbns(vp, end_lbn, end_ap, &end_lvl)) 240 return (ENOSPC); 241 /* 242 * Get the starting offset and block map for the first block. 243 */ 244 if (start_lvl == 0) { 245 sbap = &ip->i_db[0]; 246 soff = start_lbn; 247 } else { 248 idp = &start_ap[start_lvl - 1]; 249 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &sbp)) { 250 brelse(sbp); 251 return (ENOSPC); 252 } 253 sbap = (u_int *)sbp->b_data; 254 soff = idp->in_off; 255 } 256 /* 257 * If the block range spans two block maps, get the second map. 258 */ 259 ebap = NULL; 260 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 261 ssize = len; 262 } else { 263 #ifdef INVARIANTS 264 if (start_ap[start_lvl - 1].in_lbn == idp->in_lbn) 265 panic("ext2_reallocblks: start == end"); 266 #endif 267 ssize = len - (idp->in_off + 1); 268 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp)) 269 goto fail; 270 ebap = (u_int *)ebp->b_data; 271 } 272 /* 273 * Find the preferred location for the cluster. 274 */ 275 EXT2_LOCK(ump); 276 pref = ext2_blkpref(ip, start_lbn, soff, sbap, 0); 277 /* 278 * Search the block map looking for an allocation of the desired size. 279 */ 280 if ((newblk = (e2fs_daddr_t)ext2_hashalloc(ip, dtog(fs, pref), pref, 281 len, ext2_clusteralloc)) == 0) { 282 EXT2_UNLOCK(ump); 283 goto fail; 284 } 285 /* 286 * We have found a new contiguous block. 287 * 288 * First we have to replace the old block pointers with the new 289 * block pointers in the inode and indirect blocks associated 290 * with the file. 291 */ 292 #ifdef DEBUG 293 printf("realloc: ino %ju, lbns %jd-%jd\n\told:", 294 (uintmax_t)ip->i_number, (intmax_t)start_lbn, (intmax_t)end_lbn); 295 #endif /* DEBUG */ 296 blkno = newblk; 297 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->e2fs_fpb) { 298 if (i == ssize) { 299 bap = ebap; 300 soff = -i; 301 } 302 #ifdef INVARIANTS 303 if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap)) 304 panic("ext2_reallocblks: alloc mismatch"); 305 #endif 306 #ifdef DEBUG 307 printf(" %d,", *bap); 308 #endif /* DEBUG */ 309 *bap++ = blkno; 310 } 311 /* 312 * Next we must write out the modified inode and indirect blocks. 313 * For strict correctness, the writes should be synchronous since 314 * the old block values may have been written to disk. In practise 315 * they are almost never written, but if we are concerned about 316 * strict correctness, the `doasyncfree' flag should be set to zero. 317 * 318 * The test on `doasyncfree' should be changed to test a flag 319 * that shows whether the associated buffers and inodes have 320 * been written. The flag should be set when the cluster is 321 * started and cleared whenever the buffer or inode is flushed. 322 * We can then check below to see if it is set, and do the 323 * synchronous write only when it has been cleared. 324 */ 325 if (sbap != &ip->i_db[0]) { 326 if (doasyncfree) 327 bdwrite(sbp); 328 else 329 bwrite(sbp); 330 } else { 331 ip->i_flag |= IN_CHANGE | IN_UPDATE; 332 if (!doasyncfree) 333 ext2_update(vp, 1); 334 } 335 if (ssize < len) { 336 if (doasyncfree) 337 bdwrite(ebp); 338 else 339 bwrite(ebp); 340 } 341 /* 342 * Last, free the old blocks and assign the new blocks to the buffers. 343 */ 344 #ifdef DEBUG 345 printf("\n\tnew:"); 346 #endif /* DEBUG */ 347 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->e2fs_fpb) { 348 ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 349 fs->e2fs_bsize); 350 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 351 #ifdef DEBUG 352 printf(" %d,", blkno); 353 #endif /* DEBUG */ 354 } 355 #ifdef DEBUG 356 printf("\n"); 357 #endif /* DEBUG */ 358 return (0); 359 360 fail: 361 if (ssize < len) 362 brelse(ebp); 363 if (sbap != &ip->i_db[0]) 364 brelse(sbp); 365 return (ENOSPC); 366 } 367 368 /* 369 * Allocate an inode in the filesystem. 370 * 371 */ 372 int 373 ext2_valloc(struct vnode *pvp, int mode, struct ucred *cred, struct vnode **vpp) 374 { 375 struct timespec ts; 376 struct inode *pip; 377 struct m_ext2fs *fs; 378 struct inode *ip; 379 struct ext2mount *ump; 380 ino_t ino, ipref; 381 int error, cg; 382 383 *vpp = NULL; 384 pip = VTOI(pvp); 385 fs = pip->i_e2fs; 386 ump = pip->i_ump; 387 388 EXT2_LOCK(ump); 389 if (fs->e2fs->e2fs_ficount == 0) 390 goto noinodes; 391 /* 392 * If it is a directory then obtain a cylinder group based on 393 * ext2_dirpref else obtain it using ino_to_cg. The preferred inode is 394 * always the next inode. 395 */ 396 if ((mode & IFMT) == IFDIR) { 397 cg = ext2_dirpref(pip); 398 if (fs->e2fs_contigdirs[cg] < 255) 399 fs->e2fs_contigdirs[cg]++; 400 } else { 401 cg = ino_to_cg(fs, pip->i_number); 402 if (fs->e2fs_contigdirs[cg] > 0) 403 fs->e2fs_contigdirs[cg]--; 404 } 405 ipref = cg * fs->e2fs->e2fs_ipg + 1; 406 ino = (ino_t)ext2_hashalloc(pip, cg, (long)ipref, mode, ext2_nodealloccg); 407 408 if (ino == 0) 409 goto noinodes; 410 error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp); 411 if (error) { 412 ext2_vfree(pvp, ino, mode); 413 return (error); 414 } 415 ip = VTOI(*vpp); 416 417 /* 418 * The question is whether using VGET was such good idea at all: 419 * Linux doesn't read the old inode in when it is allocating a 420 * new one. I will set at least i_size and i_blocks to zero. 421 */ 422 ip->i_flag = 0; 423 ip->i_size = 0; 424 ip->i_blocks = 0; 425 ip->i_mode = 0; 426 ip->i_flags = 0; 427 if (EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_EXTENTS) 428 && (S_ISREG(mode) || S_ISDIR(mode))) 429 ext4_ext_tree_init(ip); 430 else 431 memset(ip->i_data, 0, sizeof(ip->i_data)); 432 433 434 /* 435 * Set up a new generation number for this inode. 436 * Avoid zero values. 437 */ 438 do { 439 ip->i_gen = arc4random(); 440 } while (ip->i_gen == 0); 441 442 vfs_timestamp(&ts); 443 ip->i_birthtime = ts.tv_sec; 444 ip->i_birthnsec = ts.tv_nsec; 445 446 /* 447 printf("ext2_valloc: allocated inode %d\n", ino); 448 */ 449 return (0); 450 noinodes: 451 EXT2_UNLOCK(ump); 452 ext2_fserr(fs, cred->cr_uid, "out of inodes"); 453 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt); 454 return (ENOSPC); 455 } 456 457 /* 458 * Find a cylinder to place a directory. 459 * 460 * The policy implemented by this algorithm is to allocate a 461 * directory inode in the same cylinder group as its parent 462 * directory, but also to reserve space for its files inodes 463 * and data. Restrict the number of directories which may be 464 * allocated one after another in the same cylinder group 465 * without intervening allocation of files. 466 * 467 * If we allocate a first level directory then force allocation 468 * in another cylinder group. 469 * 470 */ 471 static u_long 472 ext2_dirpref(struct inode *pip) 473 { 474 struct m_ext2fs *fs; 475 int cg, prefcg, cgsize; 476 u_int avgifree, avgbfree, avgndir, curdirsize; 477 u_int minifree, minbfree, maxndir; 478 u_int mincg, minndir; 479 u_int dirsize, maxcontigdirs; 480 481 mtx_assert(EXT2_MTX(pip->i_ump), MA_OWNED); 482 fs = pip->i_e2fs; 483 484 avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount; 485 avgbfree = fs->e2fs->e2fs_fbcount / fs->e2fs_gcount; 486 avgndir = fs->e2fs_total_dir / fs->e2fs_gcount; 487 488 /* 489 * Force allocation in another cg if creating a first level dir. 490 */ 491 ASSERT_VOP_LOCKED(ITOV(pip), "ext2fs_dirpref"); 492 if (ITOV(pip)->v_vflag & VV_ROOT) { 493 prefcg = arc4random() % fs->e2fs_gcount; 494 mincg = prefcg; 495 minndir = fs->e2fs_ipg; 496 for (cg = prefcg; cg < fs->e2fs_gcount; cg++) 497 if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir && 498 fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree && 499 fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) { 500 mincg = cg; 501 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs; 502 } 503 for (cg = 0; cg < prefcg; cg++) 504 if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir && 505 fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree && 506 fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) { 507 mincg = cg; 508 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs; 509 } 510 return (mincg); 511 } 512 /* 513 * Count various limits which used for 514 * optimal allocation of a directory inode. 515 */ 516 maxndir = min(avgndir + fs->e2fs_ipg / 16, fs->e2fs_ipg); 517 minifree = avgifree - avgifree / 4; 518 if (minifree < 1) 519 minifree = 1; 520 minbfree = avgbfree - avgbfree / 4; 521 if (minbfree < 1) 522 minbfree = 1; 523 cgsize = fs->e2fs_fsize * fs->e2fs_fpg; 524 dirsize = AVGDIRSIZE; 525 curdirsize = avgndir ? (cgsize - avgbfree * fs->e2fs_bsize) / avgndir : 0; 526 if (dirsize < curdirsize) 527 dirsize = curdirsize; 528 maxcontigdirs = min((avgbfree * fs->e2fs_bsize) / dirsize, 255); 529 maxcontigdirs = min(maxcontigdirs, fs->e2fs_ipg / AFPDIR); 530 if (maxcontigdirs == 0) 531 maxcontigdirs = 1; 532 533 /* 534 * Limit number of dirs in one cg and reserve space for 535 * regular files, but only if we have no deficit in 536 * inodes or space. 537 */ 538 prefcg = ino_to_cg(fs, pip->i_number); 539 for (cg = prefcg; cg < fs->e2fs_gcount; cg++) 540 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir && 541 fs->e2fs_gd[cg].ext2bgd_nifree >= minifree && 542 fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) { 543 if (fs->e2fs_contigdirs[cg] < maxcontigdirs) 544 return (cg); 545 } 546 for (cg = 0; cg < prefcg; cg++) 547 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir && 548 fs->e2fs_gd[cg].ext2bgd_nifree >= minifree && 549 fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) { 550 if (fs->e2fs_contigdirs[cg] < maxcontigdirs) 551 return (cg); 552 } 553 /* 554 * This is a backstop when we have deficit in space. 555 */ 556 for (cg = prefcg; cg < fs->e2fs_gcount; cg++) 557 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree) 558 return (cg); 559 for (cg = 0; cg < prefcg; cg++) 560 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree) 561 break; 562 return (cg); 563 } 564 565 /* 566 * Select the desired position for the next block in a file. 567 * 568 * we try to mimic what Remy does in inode_getblk/block_getblk 569 * 570 * we note: blocknr == 0 means that we're about to allocate either 571 * a direct block or a pointer block at the first level of indirection 572 * (In other words, stuff that will go in i_db[] or i_ib[]) 573 * 574 * blocknr != 0 means that we're allocating a block that is none 575 * of the above. Then, blocknr tells us the number of the block 576 * that will hold the pointer 577 */ 578 e4fs_daddr_t 579 ext2_blkpref(struct inode *ip, e2fs_lbn_t lbn, int indx, e2fs_daddr_t *bap, 580 e2fs_daddr_t blocknr) 581 { 582 struct m_ext2fs *fs; 583 int tmp; 584 585 fs = ip->i_e2fs; 586 587 mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED); 588 589 /* 590 * If the next block is actually what we thought it is, then set the 591 * goal to what we thought it should be. 592 */ 593 if (ip->i_next_alloc_block == lbn && ip->i_next_alloc_goal != 0) 594 return ip->i_next_alloc_goal; 595 596 /* 597 * Now check whether we were provided with an array that basically 598 * tells us previous blocks to which we want to stay close. 599 */ 600 if (bap) 601 for (tmp = indx - 1; tmp >= 0; tmp--) 602 if (bap[tmp]) 603 return bap[tmp]; 604 605 /* 606 * Else lets fall back to the blocknr or, if there is none, follow 607 * the rule that a block should be allocated near its inode. 608 */ 609 return (blocknr ? blocknr : 610 (e2fs_daddr_t)(ip->i_block_group * 611 EXT2_BLOCKS_PER_GROUP(fs)) + fs->e2fs->e2fs_first_dblock); 612 } 613 614 /* 615 * Implement the cylinder overflow algorithm. 616 * 617 * The policy implemented by this algorithm is: 618 * 1) allocate the block in its requested cylinder group. 619 * 2) quadradically rehash on the cylinder group number. 620 * 3) brute force search for a free block. 621 */ 622 static e4fs_daddr_t 623 ext2_hashalloc(struct inode *ip, int cg, long pref, int size, 624 daddr_t (*allocator) (struct inode *, int, daddr_t, int)) 625 { 626 struct m_ext2fs *fs; 627 e4fs_daddr_t result; 628 int i, icg = cg; 629 630 mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED); 631 fs = ip->i_e2fs; 632 /* 633 * 1: preferred cylinder group 634 */ 635 result = (*allocator)(ip, cg, pref, size); 636 if (result) 637 return (result); 638 /* 639 * 2: quadratic rehash 640 */ 641 for (i = 1; i < fs->e2fs_gcount; i *= 2) { 642 cg += i; 643 if (cg >= fs->e2fs_gcount) 644 cg -= fs->e2fs_gcount; 645 result = (*allocator)(ip, cg, 0, size); 646 if (result) 647 return (result); 648 } 649 /* 650 * 3: brute force search 651 * Note that we start at i == 2, since 0 was checked initially, 652 * and 1 is always checked in the quadratic rehash. 653 */ 654 cg = (icg + 2) % fs->e2fs_gcount; 655 for (i = 2; i < fs->e2fs_gcount; i++) { 656 result = (*allocator)(ip, cg, 0, size); 657 if (result) 658 return (result); 659 cg++; 660 if (cg == fs->e2fs_gcount) 661 cg = 0; 662 } 663 return (0); 664 } 665 666 static unsigned long 667 ext2_cg_num_gdb(struct m_ext2fs *fs, int cg) 668 { 669 int gd_per_block, metagroup, first, last; 670 671 gd_per_block = fs->e2fs_bsize / sizeof(struct ext2_gd); 672 metagroup = cg / gd_per_block; 673 first = metagroup * gd_per_block; 674 last = first + gd_per_block - 1; 675 676 if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_META_BG) || 677 metagroup < fs->e2fs->e3fs_first_meta_bg) { 678 if (!ext2_cg_has_sb(fs, cg)) 679 return (0); 680 if (EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_META_BG)) 681 return (fs->e2fs->e3fs_first_meta_bg); 682 return (fs->e2fs_gdbcount); 683 } 684 685 if (cg == first || cg == first + 1 || cg == last) 686 return (1); 687 return (0); 688 689 } 690 691 static int 692 ext2_num_base_meta_blocks(struct m_ext2fs *fs, int cg) 693 { 694 int num, gd_per_block; 695 696 gd_per_block = fs->e2fs_bsize / sizeof(struct ext2_gd); 697 num = ext2_cg_has_sb(fs, cg); 698 699 if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_META_BG) || 700 cg < fs->e2fs->e3fs_first_meta_bg * gd_per_block) { 701 if (num) { 702 num += ext2_cg_num_gdb(fs, cg); 703 num += fs->e2fs->e2fs_reserved_ngdb; 704 } 705 } else { 706 num += ext2_cg_num_gdb(fs, cg); 707 } 708 709 return (num); 710 } 711 712 static int 713 ext2_get_cg_number(struct m_ext2fs *fs, daddr_t blk) 714 { 715 int cg; 716 717 if (fs->e2fs->e2fs_bpg == fs->e2fs_bsize * 8) 718 cg = (blk - fs->e2fs->e2fs_first_dblock) / (fs->e2fs_bsize * 8); 719 else 720 cg = blk - fs->e2fs->e2fs_first_dblock; 721 722 return (cg); 723 } 724 725 static void 726 ext2_mark_bitmap_end(int start_bit, int end_bit, char *bitmap) 727 { 728 int i; 729 730 if (start_bit >= end_bit) 731 return; 732 733 for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++) 734 setbit(bitmap, i); 735 if (i < end_bit) 736 memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3); 737 } 738 739 static int 740 ext2_cg_block_bitmap_init(struct m_ext2fs *fs, int cg, struct buf *bp) 741 { 742 int bit, bit_max, inodes_per_block; 743 uint32_t start, tmp; 744 745 if (!EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM) || 746 !(fs->e2fs_gd[cg].ext4bgd_flags & EXT2_BG_BLOCK_UNINIT)) 747 return (0); 748 749 memset(bp->b_data, 0, fs->e2fs_bsize); 750 751 bit_max = ext2_num_base_meta_blocks(fs, cg); 752 if ((bit_max >> 3) >= fs->e2fs_bsize) 753 return (EINVAL); 754 755 for (bit = 0; bit < bit_max; bit++) 756 setbit(bp->b_data, bit); 757 758 start = cg * fs->e2fs->e2fs_bpg + fs->e2fs->e2fs_first_dblock; 759 760 /* Set bits for block and inode bitmaps, and inode table */ 761 tmp = fs->e2fs_gd[cg].ext2bgd_b_bitmap; 762 if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_FLEX_BG) || 763 tmp == ext2_get_cg_number(fs, cg)) 764 setbit(bp->b_data, tmp - start); 765 766 tmp = fs->e2fs_gd[cg].ext2bgd_i_bitmap; 767 if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_FLEX_BG) || 768 tmp == ext2_get_cg_number(fs, cg)) 769 setbit(bp->b_data, tmp - start); 770 771 tmp = fs->e2fs_gd[cg].ext2bgd_i_tables; 772 inodes_per_block = fs->e2fs_bsize/EXT2_INODE_SIZE(fs); 773 while( tmp < fs->e2fs_gd[cg].ext2bgd_i_tables + 774 fs->e2fs->e2fs_ipg / inodes_per_block ) { 775 if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_FLEX_BG) || 776 tmp == ext2_get_cg_number(fs, cg)) 777 setbit(bp->b_data, tmp - start); 778 tmp++; 779 } 780 781 /* 782 * Also if the number of blocks within the group is less than 783 * the blocksize * 8 ( which is the size of bitmap ), set rest 784 * of the block bitmap to 1 785 */ 786 ext2_mark_bitmap_end(fs->e2fs->e2fs_bpg, fs->e2fs_bsize * 8, 787 bp->b_data); 788 789 /* Clean the flag */ 790 fs->e2fs_gd[cg].ext4bgd_flags &= ~EXT2_BG_BLOCK_UNINIT; 791 792 return (0); 793 } 794 795 /* 796 * Determine whether a block can be allocated. 797 * 798 * Check to see if a block of the appropriate size is available, 799 * and if it is, allocate it. 800 */ 801 static daddr_t 802 ext2_alloccg(struct inode *ip, int cg, daddr_t bpref, int size) 803 { 804 struct m_ext2fs *fs; 805 struct buf *bp; 806 struct ext2mount *ump; 807 daddr_t bno, runstart, runlen; 808 int bit, loc, end, error, start; 809 char *bbp; 810 /* XXX ondisk32 */ 811 fs = ip->i_e2fs; 812 ump = ip->i_ump; 813 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) 814 return (0); 815 EXT2_UNLOCK(ump); 816 error = bread(ip->i_devvp, fsbtodb(fs, 817 fs->e2fs_gd[cg].ext2bgd_b_bitmap), 818 (int)fs->e2fs_bsize, NOCRED, &bp); 819 if (error) { 820 brelse(bp); 821 EXT2_LOCK(ump); 822 return (0); 823 } 824 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM)) { 825 error = ext2_cg_block_bitmap_init(fs, cg, bp); 826 if (error) { 827 brelse(bp); 828 EXT2_LOCK(ump); 829 return (0); 830 } 831 } 832 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) { 833 /* 834 * Another thread allocated the last block in this 835 * group while we were waiting for the buffer. 836 */ 837 brelse(bp); 838 EXT2_LOCK(ump); 839 return (0); 840 } 841 bbp = (char *)bp->b_data; 842 843 if (dtog(fs, bpref) != cg) 844 bpref = 0; 845 if (bpref != 0) { 846 bpref = dtogd(fs, bpref); 847 /* 848 * if the requested block is available, use it 849 */ 850 if (isclr(bbp, bpref)) { 851 bno = bpref; 852 goto gotit; 853 } 854 } 855 /* 856 * no blocks in the requested cylinder, so take next 857 * available one in this cylinder group. 858 * first try to get 8 contigous blocks, then fall back to a single 859 * block. 860 */ 861 if (bpref) 862 start = dtogd(fs, bpref) / NBBY; 863 else 864 start = 0; 865 end = howmany(fs->e2fs->e2fs_fpg, NBBY) - start; 866 retry: 867 runlen = 0; 868 runstart = 0; 869 for (loc = start; loc < end; loc++) { 870 if (bbp[loc] == (char)0xff) { 871 runlen = 0; 872 continue; 873 } 874 875 /* Start of a run, find the number of high clear bits. */ 876 if (runlen == 0) { 877 bit = fls(bbp[loc]); 878 runlen = NBBY - bit; 879 runstart = loc * NBBY + bit; 880 } else if (bbp[loc] == 0) { 881 /* Continue a run. */ 882 runlen += NBBY; 883 } else { 884 /* 885 * Finish the current run. If it isn't long 886 * enough, start a new one. 887 */ 888 bit = ffs(bbp[loc]) - 1; 889 runlen += bit; 890 if (runlen >= 8) { 891 bno = runstart; 892 goto gotit; 893 } 894 895 /* Run was too short, start a new one. */ 896 bit = fls(bbp[loc]); 897 runlen = NBBY - bit; 898 runstart = loc * NBBY + bit; 899 } 900 901 /* If the current run is long enough, use it. */ 902 if (runlen >= 8) { 903 bno = runstart; 904 goto gotit; 905 } 906 } 907 if (start != 0) { 908 end = start; 909 start = 0; 910 goto retry; 911 } 912 bno = ext2_mapsearch(fs, bbp, bpref); 913 if (bno < 0) { 914 brelse(bp); 915 EXT2_LOCK(ump); 916 return (0); 917 } 918 gotit: 919 #ifdef INVARIANTS 920 if (isset(bbp, bno)) { 921 printf("ext2fs_alloccgblk: cg=%d bno=%jd fs=%s\n", 922 cg, (intmax_t)bno, fs->e2fs_fsmnt); 923 panic("ext2fs_alloccg: dup alloc"); 924 } 925 #endif 926 setbit(bbp, bno); 927 EXT2_LOCK(ump); 928 ext2_clusteracct(fs, bbp, cg, bno, -1); 929 fs->e2fs->e2fs_fbcount--; 930 fs->e2fs_gd[cg].ext2bgd_nbfree--; 931 fs->e2fs_fmod = 1; 932 EXT2_UNLOCK(ump); 933 bdwrite(bp); 934 return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno); 935 } 936 937 /* 938 * Determine whether a cluster can be allocated. 939 */ 940 static daddr_t 941 ext2_clusteralloc(struct inode *ip, int cg, daddr_t bpref, int len) 942 { 943 struct m_ext2fs *fs; 944 struct ext2mount *ump; 945 struct buf *bp; 946 char *bbp; 947 int bit, error, got, i, loc, run; 948 int32_t *lp; 949 daddr_t bno; 950 951 fs = ip->i_e2fs; 952 ump = ip->i_ump; 953 954 if (fs->e2fs_maxcluster[cg] < len) 955 return (0); 956 957 EXT2_UNLOCK(ump); 958 error = bread(ip->i_devvp, 959 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap), 960 (int)fs->e2fs_bsize, NOCRED, &bp); 961 if (error) 962 goto fail_lock; 963 964 bbp = (char *)bp->b_data; 965 EXT2_LOCK(ump); 966 /* 967 * Check to see if a cluster of the needed size (or bigger) is 968 * available in this cylinder group. 969 */ 970 lp = &fs->e2fs_clustersum[cg].cs_sum[len]; 971 for (i = len; i <= fs->e2fs_contigsumsize; i++) 972 if (*lp++ > 0) 973 break; 974 if (i > fs->e2fs_contigsumsize) { 975 /* 976 * Update the cluster summary information to reflect 977 * the true maximum-sized cluster so that future cluster 978 * allocation requests can avoid reading the bitmap only 979 * to find no cluster. 980 */ 981 lp = &fs->e2fs_clustersum[cg].cs_sum[len - 1]; 982 for (i = len - 1; i > 0; i--) 983 if (*lp-- > 0) 984 break; 985 fs->e2fs_maxcluster[cg] = i; 986 goto fail; 987 } 988 EXT2_UNLOCK(ump); 989 990 /* Search the bitmap to find a big enough cluster like in FFS. */ 991 if (dtog(fs, bpref) != cg) 992 bpref = 0; 993 if (bpref != 0) 994 bpref = dtogd(fs, bpref); 995 loc = bpref / NBBY; 996 bit = 1 << (bpref % NBBY); 997 for (run = 0, got = bpref; got < fs->e2fs->e2fs_fpg; got++) { 998 if ((bbp[loc] & bit) != 0) 999 run = 0; 1000 else { 1001 run++; 1002 if (run == len) 1003 break; 1004 } 1005 if ((got & (NBBY - 1)) != (NBBY - 1)) 1006 bit <<= 1; 1007 else { 1008 loc++; 1009 bit = 1; 1010 } 1011 } 1012 1013 if (got >= fs->e2fs->e2fs_fpg) 1014 goto fail_lock; 1015 1016 /* Allocate the cluster that we found. */ 1017 for (i = 1; i < len; i++) 1018 if (!isclr(bbp, got - run + i)) 1019 panic("ext2_clusteralloc: map mismatch"); 1020 1021 bno = got - run + 1; 1022 if (bno >= fs->e2fs->e2fs_fpg) 1023 panic("ext2_clusteralloc: allocated out of group"); 1024 1025 EXT2_LOCK(ump); 1026 for (i = 0; i < len; i += fs->e2fs_fpb) { 1027 setbit(bbp, bno + i); 1028 ext2_clusteracct(fs, bbp, cg, bno + i, -1); 1029 fs->e2fs->e2fs_fbcount--; 1030 fs->e2fs_gd[cg].ext2bgd_nbfree--; 1031 } 1032 fs->e2fs_fmod = 1; 1033 EXT2_UNLOCK(ump); 1034 1035 bdwrite(bp); 1036 return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno); 1037 1038 fail_lock: 1039 EXT2_LOCK(ump); 1040 fail: 1041 brelse(bp); 1042 return (0); 1043 } 1044 1045 static int 1046 ext2_zero_inode_table(struct inode *ip, int cg) 1047 { 1048 struct m_ext2fs *fs; 1049 struct buf *bp; 1050 int i, all_blks, used_blks; 1051 1052 fs = ip->i_e2fs; 1053 1054 if (fs->e2fs_gd[cg].ext4bgd_flags & EXT2_BG_INODE_ZEROED) 1055 return (0); 1056 1057 all_blks = fs->e2fs->e2fs_inode_size * fs->e2fs->e2fs_ipg / 1058 fs->e2fs_bsize; 1059 1060 used_blks = howmany(fs->e2fs->e2fs_ipg - 1061 fs->e2fs_gd[cg].ext4bgd_i_unused, 1062 fs->e2fs_bsize / EXT2_INODE_SIZE(fs)); 1063 1064 for (i = 0; i < all_blks - used_blks; i++) { 1065 bp = getblk(ip->i_devvp, fsbtodb(fs, 1066 fs->e2fs_gd[cg].ext2bgd_i_tables + used_blks + i), 1067 fs->e2fs_bsize, 0, 0, 0); 1068 if (!bp) 1069 return (EIO); 1070 1071 vfs_bio_bzero_buf(bp, 0, fs->e2fs_bsize); 1072 bawrite(bp); 1073 } 1074 1075 fs->e2fs_gd[cg].ext4bgd_flags |= EXT2_BG_INODE_ZEROED; 1076 1077 return (0); 1078 } 1079 1080 /* 1081 * Determine whether an inode can be allocated. 1082 * 1083 * Check to see if an inode is available, and if it is, 1084 * allocate it using tode in the specified cylinder group. 1085 */ 1086 static daddr_t 1087 ext2_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode) 1088 { 1089 struct m_ext2fs *fs; 1090 struct buf *bp; 1091 struct ext2mount *ump; 1092 int error, start, len; 1093 char *ibp, *loc; 1094 1095 ipref--; /* to avoid a lot of (ipref -1) */ 1096 if (ipref == -1) 1097 ipref = 0; 1098 fs = ip->i_e2fs; 1099 ump = ip->i_ump; 1100 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) 1101 return (0); 1102 EXT2_UNLOCK(ump); 1103 error = bread(ip->i_devvp, fsbtodb(fs, 1104 fs->e2fs_gd[cg].ext2bgd_i_bitmap), 1105 (int)fs->e2fs_bsize, NOCRED, &bp); 1106 if (error) { 1107 brelse(bp); 1108 EXT2_LOCK(ump); 1109 return (0); 1110 } 1111 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM)) { 1112 if (fs->e2fs_gd[cg].ext4bgd_flags & EXT2_BG_INODE_UNINIT) { 1113 memset(bp->b_data, 0, fs->e2fs_bsize); 1114 fs->e2fs_gd[cg].ext4bgd_flags &= ~EXT2_BG_INODE_UNINIT; 1115 } 1116 error = ext2_zero_inode_table(ip, cg); 1117 if (error) { 1118 brelse(bp); 1119 EXT2_LOCK(ump); 1120 return (0); 1121 } 1122 } 1123 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) { 1124 /* 1125 * Another thread allocated the last i-node in this 1126 * group while we were waiting for the buffer. 1127 */ 1128 brelse(bp); 1129 EXT2_LOCK(ump); 1130 return (0); 1131 } 1132 ibp = (char *)bp->b_data; 1133 if (ipref) { 1134 ipref %= fs->e2fs->e2fs_ipg; 1135 if (isclr(ibp, ipref)) 1136 goto gotit; 1137 } 1138 start = ipref / NBBY; 1139 len = howmany(fs->e2fs->e2fs_ipg - ipref, NBBY); 1140 loc = memcchr(&ibp[start], 0xff, len); 1141 if (loc == NULL) { 1142 len = start + 1; 1143 start = 0; 1144 loc = memcchr(&ibp[start], 0xff, len); 1145 if (loc == NULL) { 1146 printf("cg = %d, ipref = %lld, fs = %s\n", 1147 cg, (long long)ipref, fs->e2fs_fsmnt); 1148 panic("ext2fs_nodealloccg: map corrupted"); 1149 /* NOTREACHED */ 1150 } 1151 } 1152 ipref = (loc - ibp) * NBBY + ffs(~*loc) - 1; 1153 gotit: 1154 setbit(ibp, ipref); 1155 EXT2_LOCK(ump); 1156 fs->e2fs_gd[cg].ext2bgd_nifree--; 1157 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM)) 1158 fs->e2fs_gd[cg].ext4bgd_i_unused--; 1159 fs->e2fs->e2fs_ficount--; 1160 fs->e2fs_fmod = 1; 1161 if ((mode & IFMT) == IFDIR) { 1162 fs->e2fs_gd[cg].ext2bgd_ndirs++; 1163 fs->e2fs_total_dir++; 1164 } 1165 EXT2_UNLOCK(ump); 1166 bdwrite(bp); 1167 return (cg * fs->e2fs->e2fs_ipg + ipref + 1); 1168 } 1169 1170 /* 1171 * Free a block or fragment. 1172 * 1173 */ 1174 void 1175 ext2_blkfree(struct inode *ip, e4fs_daddr_t bno, long size) 1176 { 1177 struct m_ext2fs *fs; 1178 struct buf *bp; 1179 struct ext2mount *ump; 1180 int cg, error; 1181 char *bbp; 1182 1183 fs = ip->i_e2fs; 1184 ump = ip->i_ump; 1185 cg = dtog(fs, bno); 1186 if (bno >= fs->e2fs->e2fs_bcount) { 1187 printf("bad block %lld, ino %ju\n", (long long)bno, 1188 (uintmax_t)ip->i_number); 1189 ext2_fserr(fs, ip->i_uid, "bad block"); 1190 return; 1191 } 1192 error = bread(ip->i_devvp, 1193 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap), 1194 (int)fs->e2fs_bsize, NOCRED, &bp); 1195 if (error) { 1196 brelse(bp); 1197 return; 1198 } 1199 bbp = (char *)bp->b_data; 1200 bno = dtogd(fs, bno); 1201 if (isclr(bbp, bno)) { 1202 printf("block = %lld, fs = %s\n", 1203 (long long)bno, fs->e2fs_fsmnt); 1204 panic("ext2_blkfree: freeing free block"); 1205 } 1206 clrbit(bbp, bno); 1207 EXT2_LOCK(ump); 1208 ext2_clusteracct(fs, bbp, cg, bno, 1); 1209 fs->e2fs->e2fs_fbcount++; 1210 fs->e2fs_gd[cg].ext2bgd_nbfree++; 1211 fs->e2fs_fmod = 1; 1212 EXT2_UNLOCK(ump); 1213 bdwrite(bp); 1214 } 1215 1216 /* 1217 * Free an inode. 1218 * 1219 */ 1220 int 1221 ext2_vfree(struct vnode *pvp, ino_t ino, int mode) 1222 { 1223 struct m_ext2fs *fs; 1224 struct inode *pip; 1225 struct buf *bp; 1226 struct ext2mount *ump; 1227 int error, cg; 1228 char *ibp; 1229 1230 pip = VTOI(pvp); 1231 fs = pip->i_e2fs; 1232 ump = pip->i_ump; 1233 if ((u_int)ino > fs->e2fs_ipg * fs->e2fs_gcount) 1234 panic("ext2_vfree: range: devvp = %p, ino = %ju, fs = %s", 1235 pip->i_devvp, (uintmax_t)ino, fs->e2fs_fsmnt); 1236 1237 cg = ino_to_cg(fs, ino); 1238 error = bread(pip->i_devvp, 1239 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_i_bitmap), 1240 (int)fs->e2fs_bsize, NOCRED, &bp); 1241 if (error) { 1242 brelse(bp); 1243 return (0); 1244 } 1245 ibp = (char *)bp->b_data; 1246 ino = (ino - 1) % fs->e2fs->e2fs_ipg; 1247 if (isclr(ibp, ino)) { 1248 printf("ino = %llu, fs = %s\n", 1249 (unsigned long long)ino, fs->e2fs_fsmnt); 1250 if (fs->e2fs_ronly == 0) 1251 panic("ext2_vfree: freeing free inode"); 1252 } 1253 clrbit(ibp, ino); 1254 EXT2_LOCK(ump); 1255 fs->e2fs->e2fs_ficount++; 1256 fs->e2fs_gd[cg].ext2bgd_nifree++; 1257 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM)) 1258 fs->e2fs_gd[cg].ext4bgd_i_unused++; 1259 if ((mode & IFMT) == IFDIR) { 1260 fs->e2fs_gd[cg].ext2bgd_ndirs--; 1261 fs->e2fs_total_dir--; 1262 } 1263 fs->e2fs_fmod = 1; 1264 EXT2_UNLOCK(ump); 1265 bdwrite(bp); 1266 return (0); 1267 } 1268 1269 /* 1270 * Find a block in the specified cylinder group. 1271 * 1272 * It is a panic if a request is made to find a block if none are 1273 * available. 1274 */ 1275 static daddr_t 1276 ext2_mapsearch(struct m_ext2fs *fs, char *bbp, daddr_t bpref) 1277 { 1278 char *loc; 1279 int start, len; 1280 1281 /* 1282 * find the fragment by searching through the free block 1283 * map for an appropriate bit pattern 1284 */ 1285 if (bpref) 1286 start = dtogd(fs, bpref) / NBBY; 1287 else 1288 start = 0; 1289 len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start; 1290 loc = memcchr(&bbp[start], 0xff, len); 1291 if (loc == NULL) { 1292 len = start + 1; 1293 start = 0; 1294 loc = memcchr(&bbp[start], 0xff, len); 1295 if (loc == NULL) { 1296 printf("start = %d, len = %d, fs = %s\n", 1297 start, len, fs->e2fs_fsmnt); 1298 panic("ext2_mapsearch: map corrupted"); 1299 /* NOTREACHED */ 1300 } 1301 } 1302 return ((loc - bbp) * NBBY + ffs(~*loc) - 1); 1303 } 1304 1305 /* 1306 * Fserr prints the name of a filesystem with an error diagnostic. 1307 * 1308 * The form of the error message is: 1309 * fs: error message 1310 */ 1311 void 1312 ext2_fserr(struct m_ext2fs *fs, uid_t uid, char *cp) 1313 { 1314 1315 log(LOG_ERR, "uid %u on %s: %s\n", uid, fs->e2fs_fsmnt, cp); 1316 } 1317 1318 int 1319 ext2_cg_has_sb(struct m_ext2fs *fs, int cg) 1320 { 1321 int a3, a5, a7; 1322 1323 if (cg == 0) 1324 return (1); 1325 1326 if (EXT2_HAS_COMPAT_FEATURE(fs, EXT2F_COMPAT_SPARSESUPER2)) { 1327 if (cg == fs->e2fs->e4fs_backup_bgs[0] || 1328 cg == fs->e2fs->e4fs_backup_bgs[1]) 1329 return (1); 1330 return (0); 1331 } 1332 1333 if ((cg <= 1) || 1334 !EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_SPARSESUPER)) 1335 return (1); 1336 1337 if (!(cg & 1)) 1338 return (0); 1339 1340 for (a3 = 3, a5 = 5, a7 = 7; 1341 a3 <= cg || a5 <= cg || a7 <= cg; 1342 a3 *= 3, a5 *= 5, a7 *= 7) 1343 if (cg == a3 || cg == a5 || cg == a7) 1344 return (1); 1345 return (0); 1346 } 1347