ext2_alloc.c revision 261313
1158782Sume/*- 2269867Sume * modified for Lites 1.1 3158782Sume * 4158782Sume * Aug 1995, Godmar Back (gback@cs.utah.edu) 5158782Sume * University of Utah, Department of Computer Science 6158782Sume */ 7158782Sume/*- 8158782Sume * Copyright (c) 1982, 1986, 1989, 1993 9158782Sume * The Regents of the University of California. All rights reserved. 10158782Sume * 11158782Sume * Redistribution and use in source and binary forms, with or without 12158782Sume * modification, are permitted provided that the following conditions 13158782Sume * are met: 14158782Sume * 1. Redistributions of source code must retain the above copyright 15158782Sume * notice, this list of conditions and the following disclaimer. 16158782Sume * 2. Redistributions in binary form must reproduce the above copyright 17158782Sume * notice, this list of conditions and the following disclaimer in the 18158782Sume * documentation and/or other materials provided with the distribution. 19158782Sume * 4. Neither the name of the University nor the names of its contributors 20158782Sume * may be used to endorse or promote products derived from this software 21158782Sume * without specific prior written permission. 22170244Sume * 23170244Sume * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24158782Sume * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25170244Sume * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26158782Sume * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27158782Sume * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28158787Sume * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29158787Sume * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30158787Sume * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31158782Sume * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32158782Sume * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33158782Sume * SUCH DAMAGE. 34158782Sume * 35158782Sume * @(#)ffs_alloc.c 8.8 (Berkeley) 2/21/94 36158782Sume * $FreeBSD: stable/10/sys/fs/ext2fs/ext2_alloc.c 261313 2014-01-31 04:05:25Z pfg $ 37158782Sume */ 38158782Sume 39158782Sume#include <sys/param.h> 40158782Sume#include <sys/systm.h> 41158782Sume#include <sys/conf.h> 42158782Sume#include <sys/vnode.h> 43158782Sume#include <sys/stat.h> 44158782Sume#include <sys/mount.h> 45158782Sume#include <sys/sysctl.h> 46158782Sume#include <sys/syslog.h> 47158782Sume#include <sys/buf.h> 48158782Sume 49158782Sume#include <fs/ext2fs/fs.h> 50158782Sume#include <fs/ext2fs/inode.h> 51158782Sume#include <fs/ext2fs/ext2_mount.h> 52158782Sume#include <fs/ext2fs/ext2fs.h> 53158782Sume#include <fs/ext2fs/ext2_extern.h> 54158782Sume 55158782Sumestatic daddr_t ext2_alloccg(struct inode *, int, daddr_t, int); 56170244Sumestatic daddr_t ext2_clusteralloc(struct inode *, int, daddr_t, int); 57158782Sumestatic u_long ext2_dirpref(struct inode *); 58158782Sumestatic void ext2_fserr(struct m_ext2fs *, uid_t, char *); 59158782Sumestatic u_long ext2_hashalloc(struct inode *, int, long, int, 60158782Sume daddr_t (*)(struct inode *, int, daddr_t, 61158782Sume int)); 62158782Sumestatic daddr_t ext2_nodealloccg(struct inode *, int, daddr_t, int); 63158782Sumestatic daddr_t ext2_mapsearch(struct m_ext2fs *, char *, daddr_t); 64158782Sume 65158782Sume/* 66158782Sume * Allocate a block in the filesystem. 67158782Sume * 68158782Sume * A preference may be optionally specified. If a preference is given 69158782Sume * the following hierarchy is used to allocate a block: 70158782Sume * 1) allocate the requested block. 71158782Sume * 2) allocate a rotationally optimal block in the same cylinder. 72158782Sume * 3) allocate a block in the same cylinder group. 73158782Sume * 4) quadradically rehash into other cylinder groups, until an 74158782Sume * available block is located. 75158782Sume * If no block preference is given the following hierarchy is used 76158782Sume * to allocate a block: 77158782Sume * 1) allocate a block in the cylinder group that contains the 78158782Sume * inode for the file. 79158782Sume * 2) quadradically rehash into other cylinder groups, until an 80158782Sume * available block is located. 81158782Sume */ 82158782Sumeint 83158782Sumeext2_alloc(struct inode *ip, daddr_t lbn, e4fs_daddr_t bpref, int size, 84158782Sume struct ucred *cred, e4fs_daddr_t *bnp) 85158782Sume{ 86158782Sume struct m_ext2fs *fs; 87158782Sume struct ext2mount *ump; 88158782Sume int32_t bno; 89158782Sume int cg; 90158782Sume *bnp = 0; 91158782Sume fs = ip->i_e2fs; 92158782Sume ump = ip->i_ump; 93158782Sume mtx_assert(EXT2_MTX(ump), MA_OWNED); 94158782Sume#ifdef INVARIANTS 95158782Sume if ((u_int)size > fs->e2fs_bsize || blkoff(fs, size) != 0) { 96158782Sume vn_printf(ip->i_devvp, "bsize = %lu, size = %d, fs = %s\n", 97158782Sume (long unsigned int)fs->e2fs_bsize, size, fs->e2fs_fsmnt); 98158782Sume panic("ext2_alloc: bad size"); 99158782Sume } 100158782Sume if (cred == NOCRED) 101158782Sume panic("ext2_alloc: missing credential"); 102158782Sume#endif /* INVARIANTS */ 103158782Sume if (size == fs->e2fs_bsize && fs->e2fs->e2fs_fbcount == 0) 104158782Sume goto nospace; 105158782Sume if (cred->cr_uid != 0 && 106158782Sume fs->e2fs->e2fs_fbcount < fs->e2fs->e2fs_rbcount) 107158782Sume goto nospace; 108158782Sume if (bpref >= fs->e2fs->e2fs_bcount) 109158782Sume bpref = 0; 110158782Sume if (bpref == 0) 111158782Sume cg = ino_to_cg(fs, ip->i_number); 112158782Sume else 113158782Sume cg = dtog(fs, bpref); 114158782Sume bno = (daddr_t)ext2_hashalloc(ip, cg, bpref, fs->e2fs_bsize, 115158782Sume ext2_alloccg); 116158782Sume if (bno > 0) { 117158782Sume /* set next_alloc fields as done in block_getblk */ 118158782Sume ip->i_next_alloc_block = lbn; 119158782Sume ip->i_next_alloc_goal = bno; 120158782Sume 121158782Sume ip->i_blocks += btodb(fs->e2fs_bsize); 122158782Sume ip->i_flag |= IN_CHANGE | IN_UPDATE; 123158782Sume *bnp = bno; 124158782Sume return (0); 125158782Sume } 126158782Sumenospace: 127158782Sume EXT2_UNLOCK(ump); 128158782Sume ext2_fserr(fs, cred->cr_uid, "filesystem full"); 129158782Sume uprintf("\n%s: write failed, filesystem is full\n", fs->e2fs_fsmnt); 130158782Sume return (ENOSPC); 131158782Sume} 132158782Sume 133158782Sume/* 134158782Sume * Reallocate a sequence of blocks into a contiguous sequence of blocks. 135158782Sume * 136158782Sume * The vnode and an array of buffer pointers for a range of sequential 137158782Sume * logical blocks to be made contiguous is given. The allocator attempts 138158782Sume * to find a range of sequential blocks starting as close as possible to 139158782Sume * an fs_rotdelay offset from the end of the allocation for the logical 140158782Sume * block immediately preceding the current range. If successful, the 141158782Sume * physical block numbers in the buffer pointers and in the inode are 142158782Sume * changed to reflect the new allocation. If unsuccessful, the allocation 143158782Sume * is left unchanged. The success in doing the reallocation is returned. 144158782Sume * Note that the error return is not reflected back to the user. Rather 145158782Sume * the previous block allocation will be used. 146158782Sume */ 147158782Sume 148158782Sumestatic SYSCTL_NODE(_vfs, OID_AUTO, ext2fs, CTLFLAG_RW, 0, "EXT2FS filesystem"); 149158782Sume 150158782Sumestatic int doasyncfree = 1; 151158782SumeSYSCTL_INT(_vfs_ext2fs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, 152158782Sume "Use asychronous writes to update block pointers when freeing blocks"); 153158782Sume 154158782Sumestatic int doreallocblks = 1; 155158782SumeSYSCTL_INT(_vfs_ext2fs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 156158782Sume 157158782Sumeint 158158782Sumeext2_reallocblks(struct vop_reallocblks_args *ap) 159158782Sume{ 160158782Sume struct m_ext2fs *fs; 161158782Sume struct inode *ip; 162158782Sume struct vnode *vp; 163158782Sume struct buf *sbp, *ebp; 164158782Sume uint32_t *bap, *sbap, *ebap = 0; 165158782Sume struct ext2mount *ump; 166158782Sume struct cluster_save *buflist; 167158782Sume struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 168158782Sume e2fs_lbn_t start_lbn, end_lbn; 169158782Sume int soff; 170158782Sume e2fs_daddr_t newblk, blkno; 171158782Sume int i, len, start_lvl, end_lvl, pref, ssize; 172158782Sume 173158787Sume if (doreallocblks == 0) 174158787Sume return (ENOSPC); 175158787Sume 176158787Sume vp = ap->a_vp; 177158787Sume ip = VTOI(vp); 178158787Sume fs = ip->i_e2fs; 179158782Sume ump = ip->i_ump; 180158782Sume 181158787Sume if (fs->e2fs_contigsumsize <= 0) 182158787Sume return (ENOSPC); 183158782Sume 184158782Sume buflist = ap->a_buflist; 185158782Sume len = buflist->bs_nchildren; 186158782Sume start_lbn = buflist->bs_children[0]->b_lblkno; 187158782Sume end_lbn = start_lbn + len - 1; 188158782Sume#ifdef INVARIANTS 189158782Sume for (i = 1; i < len; i++) 190158782Sume if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 191158782Sume panic("ext2_reallocblks: non-cluster"); 192158782Sume#endif 193158782Sume /* 194158782Sume * If the cluster crosses the boundary for the first indirect 195158782Sume * block, leave space for the indirect block. Indirect blocks 196158782Sume * are initially laid out in a position after the last direct 197158782Sume * block. Block reallocation would usually destroy locality by 198158782Sume * moving the indirect block out of the way to make room for 199158782Sume * data blocks if we didn't compensate here. We should also do 200158782Sume * this for other indirect block boundaries, but it is only 201158782Sume * important for the first one. 202158782Sume */ 203158782Sume if (start_lbn < NDADDR && end_lbn >= NDADDR) 204158782Sume return (ENOSPC); 205158782Sume /* 206158782Sume * If the latest allocation is in a new cylinder group, assume that 207158782Sume * the filesystem has decided to move and do not force it back to 208158782Sume * the previous cylinder group. 209158782Sume */ 210158782Sume if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 211158782Sume dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 212158782Sume return (ENOSPC); 213158782Sume if (ext2_getlbns(vp, start_lbn, start_ap, &start_lvl) || 214158782Sume ext2_getlbns(vp, end_lbn, end_ap, &end_lvl)) 215158782Sume return (ENOSPC); 216158782Sume /* 217158782Sume * Get the starting offset and block map for the first block. 218158782Sume */ 219158782Sume if (start_lvl == 0) { 220158782Sume sbap = &ip->i_db[0]; 221158782Sume soff = start_lbn; 222158782Sume } else { 223 idp = &start_ap[start_lvl - 1]; 224 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &sbp)) { 225 brelse(sbp); 226 return (ENOSPC); 227 } 228 sbap = (u_int *)sbp->b_data; 229 soff = idp->in_off; 230 } 231 /* 232 * If the block range spans two block maps, get the second map. 233 */ 234 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 235 ssize = len; 236 } else { 237#ifdef INVARIANTS 238 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 239 panic("ext2_reallocblks: start == end"); 240#endif 241 ssize = len - (idp->in_off + 1); 242 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp)) 243 goto fail; 244 ebap = (u_int *)ebp->b_data; 245 } 246 /* 247 * Find the preferred location for the cluster. 248 */ 249 EXT2_LOCK(ump); 250 pref = ext2_blkpref(ip, start_lbn, soff, sbap, 0); 251 /* 252 * Search the block map looking for an allocation of the desired size. 253 */ 254 if ((newblk = (e2fs_daddr_t)ext2_hashalloc(ip, dtog(fs, pref), pref, 255 len, ext2_clusteralloc)) == 0){ 256 EXT2_UNLOCK(ump); 257 goto fail; 258 } 259 /* 260 * We have found a new contiguous block. 261 * 262 * First we have to replace the old block pointers with the new 263 * block pointers in the inode and indirect blocks associated 264 * with the file. 265 */ 266#ifdef DEBUG 267 printf("realloc: ino %d, lbns %jd-%jd\n\told:", ip->i_number, 268 (intmax_t)start_lbn, (intmax_t)end_lbn); 269#endif /* DEBUG */ 270 blkno = newblk; 271 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->e2fs_fpb) { 272 if (i == ssize) { 273 bap = ebap; 274 soff = -i; 275 } 276#ifdef INVARIANTS 277 if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap)) 278 panic("ext2_reallocblks: alloc mismatch"); 279#endif 280#ifdef DEBUG 281 printf(" %d,", *bap); 282#endif /* DEBUG */ 283 *bap++ = blkno; 284 } 285 /* 286 * Next we must write out the modified inode and indirect blocks. 287 * For strict correctness, the writes should be synchronous since 288 * the old block values may have been written to disk. In practise 289 * they are almost never written, but if we are concerned about 290 * strict correctness, the `doasyncfree' flag should be set to zero. 291 * 292 * The test on `doasyncfree' should be changed to test a flag 293 * that shows whether the associated buffers and inodes have 294 * been written. The flag should be set when the cluster is 295 * started and cleared whenever the buffer or inode is flushed. 296 * We can then check below to see if it is set, and do the 297 * synchronous write only when it has been cleared. 298 */ 299 if (sbap != &ip->i_db[0]) { 300 if (doasyncfree) 301 bdwrite(sbp); 302 else 303 bwrite(sbp); 304 } else { 305 ip->i_flag |= IN_CHANGE | IN_UPDATE; 306 if (!doasyncfree) 307 ext2_update(vp, 1); 308 } 309 if (ssize < len) { 310 if (doasyncfree) 311 bdwrite(ebp); 312 else 313 bwrite(ebp); 314 } 315 /* 316 * Last, free the old blocks and assign the new blocks to the buffers. 317 */ 318#ifdef DEBUG 319 printf("\n\tnew:"); 320#endif /* DEBUG */ 321 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->e2fs_fpb) { 322 ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 323 fs->e2fs_bsize); 324 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 325#ifdef DEBUG 326 printf(" %d,", blkno); 327#endif /* DEBUG */ 328 } 329#ifdef DEBUG 330 printf("\n"); 331#endif /* DEBUG */ 332 return (0); 333 334fail: 335 if (ssize < len) 336 brelse(ebp); 337 if (sbap != &ip->i_db[0]) 338 brelse(sbp); 339 return (ENOSPC); 340} 341 342/* 343 * Allocate an inode in the filesystem. 344 * 345 */ 346int 347ext2_valloc(struct vnode *pvp, int mode, struct ucred *cred, struct vnode **vpp) 348{ 349 struct timespec ts; 350 struct inode *pip; 351 struct m_ext2fs *fs; 352 struct inode *ip; 353 struct ext2mount *ump; 354 ino_t ino, ipref; 355 int i, error, cg; 356 357 *vpp = NULL; 358 pip = VTOI(pvp); 359 fs = pip->i_e2fs; 360 ump = pip->i_ump; 361 362 EXT2_LOCK(ump); 363 if (fs->e2fs->e2fs_ficount == 0) 364 goto noinodes; 365 /* 366 * If it is a directory then obtain a cylinder group based on 367 * ext2_dirpref else obtain it using ino_to_cg. The preferred inode is 368 * always the next inode. 369 */ 370 if ((mode & IFMT) == IFDIR) { 371 cg = ext2_dirpref(pip); 372 if (fs->e2fs_contigdirs[cg] < 255) 373 fs->e2fs_contigdirs[cg]++; 374 } else { 375 cg = ino_to_cg(fs, pip->i_number); 376 if (fs->e2fs_contigdirs[cg] > 0) 377 fs->e2fs_contigdirs[cg]--; 378 } 379 ipref = cg * fs->e2fs->e2fs_ipg + 1; 380 ino = (ino_t)ext2_hashalloc(pip, cg, (long)ipref, mode, ext2_nodealloccg); 381 382 if (ino == 0) 383 goto noinodes; 384 error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp); 385 if (error) { 386 ext2_vfree(pvp, ino, mode); 387 return (error); 388 } 389 ip = VTOI(*vpp); 390 391 /* 392 * The question is whether using VGET was such good idea at all: 393 * Linux doesn't read the old inode in when it is allocating a 394 * new one. I will set at least i_size and i_blocks to zero. 395 */ 396 ip->i_size = 0; 397 ip->i_blocks = 0; 398 ip->i_mode = 0; 399 ip->i_flags = 0; 400 /* now we want to make sure that the block pointers are zeroed out */ 401 for (i = 0; i < NDADDR; i++) 402 ip->i_db[i] = 0; 403 for (i = 0; i < NIADDR; i++) 404 ip->i_ib[i] = 0; 405 406 /* 407 * Set up a new generation number for this inode. 408 * XXX check if this makes sense in ext2 409 */ 410 if (ip->i_gen == 0 || ++ip->i_gen == 0) 411 ip->i_gen = random() / 2 + 1; 412 413 vfs_timestamp(&ts); 414 ip->i_birthtime = ts.tv_sec; 415 ip->i_birthnsec = ts.tv_nsec; 416 417/* 418printf("ext2_valloc: allocated inode %d\n", ino); 419*/ 420 return (0); 421noinodes: 422 EXT2_UNLOCK(ump); 423 ext2_fserr(fs, cred->cr_uid, "out of inodes"); 424 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt); 425 return (ENOSPC); 426} 427 428/* 429 * Find a cylinder to place a directory. 430 * 431 * The policy implemented by this algorithm is to allocate a 432 * directory inode in the same cylinder group as its parent 433 * directory, but also to reserve space for its files inodes 434 * and data. Restrict the number of directories which may be 435 * allocated one after another in the same cylinder group 436 * without intervening allocation of files. 437 * 438 * If we allocate a first level directory then force allocation 439 * in another cylinder group. 440 * 441 */ 442static u_long 443ext2_dirpref(struct inode *pip) 444{ 445 struct m_ext2fs *fs; 446 int cg, prefcg, dirsize, cgsize; 447 u_int avgifree, avgbfree, avgndir, curdirsize; 448 u_int minifree, minbfree, maxndir; 449 u_int mincg, minndir; 450 u_int maxcontigdirs; 451 452 mtx_assert(EXT2_MTX(pip->i_ump), MA_OWNED); 453 fs = pip->i_e2fs; 454 455 avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount; 456 avgbfree = fs->e2fs->e2fs_fbcount / fs->e2fs_gcount; 457 avgndir = fs->e2fs_total_dir / fs->e2fs_gcount; 458 459 /* 460 * Force allocation in another cg if creating a first level dir. 461 */ 462 ASSERT_VOP_LOCKED(ITOV(pip), "ext2fs_dirpref"); 463 if (ITOV(pip)->v_vflag & VV_ROOT) { 464 prefcg = arc4random() % fs->e2fs_gcount; 465 mincg = prefcg; 466 minndir = fs->e2fs_ipg; 467 for (cg = prefcg; cg < fs->e2fs_gcount; cg++) 468 if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir && 469 fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree && 470 fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) { 471 mincg = cg; 472 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs; 473 } 474 for (cg = 0; cg < prefcg; cg++) 475 if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir && 476 fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree && 477 fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) { 478 mincg = cg; 479 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs; 480 } 481 482 return (mincg); 483 } 484 485 /* 486 * Count various limits which used for 487 * optimal allocation of a directory inode. 488 */ 489 maxndir = min(avgndir + fs->e2fs_ipg / 16, fs->e2fs_ipg); 490 minifree = avgifree - avgifree / 4; 491 if (minifree < 1) 492 minifree = 1; 493 minbfree = avgbfree - avgbfree / 4; 494 if (minbfree < 1) 495 minbfree = 1; 496 cgsize = fs->e2fs_fsize * fs->e2fs_fpg; 497 dirsize = AVGDIRSIZE; 498 curdirsize = avgndir ? (cgsize - avgbfree * fs->e2fs_bsize) / avgndir : 0; 499 if (dirsize < curdirsize) 500 dirsize = curdirsize; 501 if (dirsize <= 0) 502 maxcontigdirs = 0; /* dirsize overflowed */ 503 else 504 maxcontigdirs = min((avgbfree * fs->e2fs_bsize) / dirsize, 255); 505 maxcontigdirs = min(maxcontigdirs, fs->e2fs_ipg / AFPDIR); 506 if (maxcontigdirs == 0) 507 maxcontigdirs = 1; 508 509 /* 510 * Limit number of dirs in one cg and reserve space for 511 * regular files, but only if we have no deficit in 512 * inodes or space. 513 */ 514 prefcg = ino_to_cg(fs, pip->i_number); 515 for (cg = prefcg; cg < fs->e2fs_gcount; cg++) 516 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir && 517 fs->e2fs_gd[cg].ext2bgd_nifree >= minifree && 518 fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) { 519 if (fs->e2fs_contigdirs[cg] < maxcontigdirs) 520 return (cg); 521 } 522 for (cg = 0; cg < prefcg; cg++) 523 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir && 524 fs->e2fs_gd[cg].ext2bgd_nifree >= minifree && 525 fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) { 526 if (fs->e2fs_contigdirs[cg] < maxcontigdirs) 527 return (cg); 528 } 529 /* 530 * This is a backstop when we have deficit in space. 531 */ 532 for (cg = prefcg; cg < fs->e2fs_gcount; cg++) 533 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree) 534 return (cg); 535 for (cg = 0; cg < prefcg; cg++) 536 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree) 537 break; 538 return (cg); 539} 540 541/* 542 * Select the desired position for the next block in a file. 543 * 544 * we try to mimic what Remy does in inode_getblk/block_getblk 545 * 546 * we note: blocknr == 0 means that we're about to allocate either 547 * a direct block or a pointer block at the first level of indirection 548 * (In other words, stuff that will go in i_db[] or i_ib[]) 549 * 550 * blocknr != 0 means that we're allocating a block that is none 551 * of the above. Then, blocknr tells us the number of the block 552 * that will hold the pointer 553 */ 554e4fs_daddr_t 555ext2_blkpref(struct inode *ip, e2fs_lbn_t lbn, int indx, e2fs_daddr_t *bap, 556 e2fs_daddr_t blocknr) 557{ 558 int tmp; 559 mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED); 560 561 /* if the next block is actually what we thought it is, 562 then set the goal to what we thought it should be 563 */ 564 if (ip->i_next_alloc_block == lbn && ip->i_next_alloc_goal != 0) 565 return ip->i_next_alloc_goal; 566 567 /* now check whether we were provided with an array that basically 568 tells us previous blocks to which we want to stay closeby 569 */ 570 if (bap) 571 for (tmp = indx - 1; tmp >= 0; tmp--) 572 if (bap[tmp]) 573 return bap[tmp]; 574 575 /* else let's fall back to the blocknr, or, if there is none, 576 follow the rule that a block should be allocated near its inode 577 */ 578 return blocknr ? blocknr : 579 (e2fs_daddr_t)(ip->i_block_group * 580 EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) + 581 ip->i_e2fs->e2fs->e2fs_first_dblock; 582} 583 584/* 585 * Implement the cylinder overflow algorithm. 586 * 587 * The policy implemented by this algorithm is: 588 * 1) allocate the block in its requested cylinder group. 589 * 2) quadradically rehash on the cylinder group number. 590 * 3) brute force search for a free block. 591 */ 592static u_long 593ext2_hashalloc(struct inode *ip, int cg, long pref, int size, 594 daddr_t (*allocator)(struct inode *, int, daddr_t, int)) 595{ 596 struct m_ext2fs *fs; 597 ino_t result; 598 int i, icg = cg; 599 600 mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED); 601 fs = ip->i_e2fs; 602 /* 603 * 1: preferred cylinder group 604 */ 605 result = (*allocator)(ip, cg, pref, size); 606 if (result) 607 return (result); 608 /* 609 * 2: quadratic rehash 610 */ 611 for (i = 1; i < fs->e2fs_gcount; i *= 2) { 612 cg += i; 613 if (cg >= fs->e2fs_gcount) 614 cg -= fs->e2fs_gcount; 615 result = (*allocator)(ip, cg, 0, size); 616 if (result) 617 return (result); 618 } 619 /* 620 * 3: brute force search 621 * Note that we start at i == 2, since 0 was checked initially, 622 * and 1 is always checked in the quadratic rehash. 623 */ 624 cg = (icg + 2) % fs->e2fs_gcount; 625 for (i = 2; i < fs->e2fs_gcount; i++) { 626 result = (*allocator)(ip, cg, 0, size); 627 if (result) 628 return (result); 629 cg++; 630 if (cg == fs->e2fs_gcount) 631 cg = 0; 632 } 633 return (0); 634} 635 636/* 637 * Determine whether a block can be allocated. 638 * 639 * Check to see if a block of the appropriate size is available, 640 * and if it is, allocate it. 641 */ 642static daddr_t 643ext2_alloccg(struct inode *ip, int cg, daddr_t bpref, int size) 644{ 645 struct m_ext2fs *fs; 646 struct buf *bp; 647 struct ext2mount *ump; 648 daddr_t bno, runstart, runlen; 649 int bit, loc, end, error, start; 650 char *bbp; 651 /* XXX ondisk32 */ 652 fs = ip->i_e2fs; 653 ump = ip->i_ump; 654 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) 655 return (0); 656 EXT2_UNLOCK(ump); 657 error = bread(ip->i_devvp, fsbtodb(fs, 658 fs->e2fs_gd[cg].ext2bgd_b_bitmap), 659 (int)fs->e2fs_bsize, NOCRED, &bp); 660 if (error) { 661 brelse(bp); 662 EXT2_LOCK(ump); 663 return (0); 664 } 665 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) { 666 /* 667 * Another thread allocated the last block in this 668 * group while we were waiting for the buffer. 669 */ 670 brelse(bp); 671 EXT2_LOCK(ump); 672 return (0); 673 } 674 bbp = (char *)bp->b_data; 675 676 if (dtog(fs, bpref) != cg) 677 bpref = 0; 678 if (bpref != 0) { 679 bpref = dtogd(fs, bpref); 680 /* 681 * if the requested block is available, use it 682 */ 683 if (isclr(bbp, bpref)) { 684 bno = bpref; 685 goto gotit; 686 } 687 } 688 /* 689 * no blocks in the requested cylinder, so take next 690 * available one in this cylinder group. 691 * first try to get 8 contigous blocks, then fall back to a single 692 * block. 693 */ 694 if (bpref) 695 start = dtogd(fs, bpref) / NBBY; 696 else 697 start = 0; 698 end = howmany(fs->e2fs->e2fs_fpg, NBBY) - start; 699retry: 700 runlen = 0; 701 runstart = 0; 702 for (loc = start; loc < end; loc++) { 703 if (bbp[loc] == (char)0xff) { 704 runlen = 0; 705 continue; 706 } 707 708 /* Start of a run, find the number of high clear bits. */ 709 if (runlen == 0) { 710 bit = fls(bbp[loc]); 711 runlen = NBBY - bit; 712 runstart = loc * NBBY + bit; 713 } else if (bbp[loc] == 0) { 714 /* Continue a run. */ 715 runlen += NBBY; 716 } else { 717 /* 718 * Finish the current run. If it isn't long 719 * enough, start a new one. 720 */ 721 bit = ffs(bbp[loc]) - 1; 722 runlen += bit; 723 if (runlen >= 8) { 724 bno = runstart; 725 goto gotit; 726 } 727 728 /* Run was too short, start a new one. */ 729 bit = fls(bbp[loc]); 730 runlen = NBBY - bit; 731 runstart = loc * NBBY + bit; 732 } 733 734 /* If the current run is long enough, use it. */ 735 if (runlen >= 8) { 736 bno = runstart; 737 goto gotit; 738 } 739 } 740 if (start != 0) { 741 end = start; 742 start = 0; 743 goto retry; 744 } 745 746 bno = ext2_mapsearch(fs, bbp, bpref); 747 if (bno < 0){ 748 brelse(bp); 749 EXT2_LOCK(ump); 750 return (0); 751 } 752gotit: 753#ifdef INVARIANTS 754 if (isset(bbp, bno)) { 755 printf("ext2fs_alloccgblk: cg=%d bno=%jd fs=%s\n", 756 cg, (intmax_t)bno, fs->e2fs_fsmnt); 757 panic("ext2fs_alloccg: dup alloc"); 758 } 759#endif 760 setbit(bbp, bno); 761 EXT2_LOCK(ump); 762 ext2_clusteracct(fs, bbp, cg, bno, -1); 763 fs->e2fs->e2fs_fbcount--; 764 fs->e2fs_gd[cg].ext2bgd_nbfree--; 765 fs->e2fs_fmod = 1; 766 EXT2_UNLOCK(ump); 767 bdwrite(bp); 768 return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno); 769} 770 771/* 772 * Determine whether a cluster can be allocated. 773 */ 774static daddr_t 775ext2_clusteralloc(struct inode *ip, int cg, daddr_t bpref, int len) 776{ 777 struct m_ext2fs *fs; 778 struct ext2mount *ump; 779 struct buf *bp; 780 char *bbp; 781 int bit, error, got, i, loc, run; 782 int32_t *lp; 783 daddr_t bno; 784 785 fs = ip->i_e2fs; 786 ump = ip->i_ump; 787 788 if (fs->e2fs_maxcluster[cg] < len) 789 return (0); 790 791 EXT2_UNLOCK(ump); 792 error = bread(ip->i_devvp, 793 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap), 794 (int)fs->e2fs_bsize, NOCRED, &bp); 795 if (error) 796 goto fail_lock; 797 798 bbp = (char *)bp->b_data; 799 EXT2_LOCK(ump); 800 /* 801 * Check to see if a cluster of the needed size (or bigger) is 802 * available in this cylinder group. 803 */ 804 lp = &fs->e2fs_clustersum[cg].cs_sum[len]; 805 for (i = len; i <= fs->e2fs_contigsumsize; i++) 806 if (*lp++ > 0) 807 break; 808 if (i > fs->e2fs_contigsumsize) { 809 /* 810 * Update the cluster summary information to reflect 811 * the true maximum-sized cluster so that future cluster 812 * allocation requests can avoid reading the bitmap only 813 * to find no cluster. 814 */ 815 lp = &fs->e2fs_clustersum[cg].cs_sum[len - 1]; 816 for (i = len - 1; i > 0; i--) 817 if (*lp-- > 0) 818 break; 819 fs->e2fs_maxcluster[cg] = i; 820 goto fail; 821 } 822 EXT2_UNLOCK(ump); 823 824 /* Search the bitmap to find a big enough cluster like in FFS. */ 825 if (dtog(fs, bpref) != cg) 826 bpref = 0; 827 if (bpref != 0) 828 bpref = dtogd(fs, bpref); 829 loc = bpref / NBBY; 830 bit = 1 << (bpref % NBBY); 831 for (run = 0, got = bpref; got < fs->e2fs->e2fs_fpg; got++) { 832 if ((bbp[loc] & bit) != 0) 833 run = 0; 834 else { 835 run++; 836 if (run == len) 837 break; 838 } 839 if ((got & (NBBY - 1)) != (NBBY - 1)) 840 bit <<= 1; 841 else { 842 loc++; 843 bit = 1; 844 } 845 } 846 847 if (got >= fs->e2fs->e2fs_fpg) 848 goto fail_lock; 849 850 /* Allocate the cluster that we found. */ 851 for (i = 1; i < len; i++) 852 if (!isclr(bbp, got - run + i)) 853 panic("ext2_clusteralloc: map mismatch"); 854 855 bno = got - run + 1; 856 if (bno >= fs->e2fs->e2fs_fpg) 857 panic("ext2_clusteralloc: allocated out of group"); 858 859 EXT2_LOCK(ump); 860 for (i = 0; i < len; i += fs->e2fs_fpb) { 861 setbit(bbp, bno + i); 862 ext2_clusteracct(fs, bbp, cg, bno + i, -1); 863 fs->e2fs->e2fs_fbcount--; 864 fs->e2fs_gd[cg].ext2bgd_nbfree--; 865 } 866 fs->e2fs_fmod = 1; 867 EXT2_UNLOCK(ump); 868 869 bdwrite(bp); 870 return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno); 871 872fail_lock: 873 EXT2_LOCK(ump); 874fail: 875 brelse(bp); 876 return (0); 877} 878 879/* 880 * Determine whether an inode can be allocated. 881 * 882 * Check to see if an inode is available, and if it is, 883 * allocate it using tode in the specified cylinder group. 884 */ 885static daddr_t 886ext2_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode) 887{ 888 struct m_ext2fs *fs; 889 struct buf *bp; 890 struct ext2mount *ump; 891 int error, start, len; 892 char *ibp, *loc; 893 ipref--; /* to avoid a lot of (ipref -1) */ 894 if (ipref == -1) 895 ipref = 0; 896 fs = ip->i_e2fs; 897 ump = ip->i_ump; 898 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) 899 return (0); 900 EXT2_UNLOCK(ump); 901 error = bread(ip->i_devvp, fsbtodb(fs, 902 fs->e2fs_gd[cg].ext2bgd_i_bitmap), 903 (int)fs->e2fs_bsize, NOCRED, &bp); 904 if (error) { 905 brelse(bp); 906 EXT2_LOCK(ump); 907 return (0); 908 } 909 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) { 910 /* 911 * Another thread allocated the last i-node in this 912 * group while we were waiting for the buffer. 913 */ 914 brelse(bp); 915 EXT2_LOCK(ump); 916 return (0); 917 } 918 ibp = (char *)bp->b_data; 919 if (ipref) { 920 ipref %= fs->e2fs->e2fs_ipg; 921 if (isclr(ibp, ipref)) 922 goto gotit; 923 } 924 start = ipref / NBBY; 925 len = howmany(fs->e2fs->e2fs_ipg - ipref, NBBY); 926 loc = memcchr(&ibp[start], 0xff, len); 927 if (loc == NULL) { 928 len = start + 1; 929 start = 0; 930 loc = memcchr(&ibp[start], 0xff, len); 931 if (loc == NULL) { 932 printf("cg = %d, ipref = %lld, fs = %s\n", 933 cg, (long long)ipref, fs->e2fs_fsmnt); 934 panic("ext2fs_nodealloccg: map corrupted"); 935 /* NOTREACHED */ 936 } 937 } 938 ipref = (loc - ibp) * NBBY + ffs(~*loc) - 1; 939gotit: 940 setbit(ibp, ipref); 941 EXT2_LOCK(ump); 942 fs->e2fs_gd[cg].ext2bgd_nifree--; 943 fs->e2fs->e2fs_ficount--; 944 fs->e2fs_fmod = 1; 945 if ((mode & IFMT) == IFDIR) { 946 fs->e2fs_gd[cg].ext2bgd_ndirs++; 947 fs->e2fs_total_dir++; 948 } 949 EXT2_UNLOCK(ump); 950 bdwrite(bp); 951 return (cg * fs->e2fs->e2fs_ipg + ipref +1); 952} 953 954/* 955 * Free a block or fragment. 956 * 957 */ 958void 959ext2_blkfree(struct inode *ip, e4fs_daddr_t bno, long size) 960{ 961 struct m_ext2fs *fs; 962 struct buf *bp; 963 struct ext2mount *ump; 964 int cg, error; 965 char *bbp; 966 967 fs = ip->i_e2fs; 968 ump = ip->i_ump; 969 cg = dtog(fs, bno); 970 if ((u_int)bno >= fs->e2fs->e2fs_bcount) { 971 printf("bad block %lld, ino %llu\n", (long long)bno, 972 (unsigned long long)ip->i_number); 973 ext2_fserr(fs, ip->i_uid, "bad block"); 974 return; 975 } 976 error = bread(ip->i_devvp, 977 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap), 978 (int)fs->e2fs_bsize, NOCRED, &bp); 979 if (error) { 980 brelse(bp); 981 return; 982 } 983 bbp = (char *)bp->b_data; 984 bno = dtogd(fs, bno); 985 if (isclr(bbp, bno)) { 986 printf("block = %lld, fs = %s\n", 987 (long long)bno, fs->e2fs_fsmnt); 988 panic("ext2_blkfree: freeing free block"); 989 } 990 clrbit(bbp, bno); 991 EXT2_LOCK(ump); 992 ext2_clusteracct(fs, bbp, cg, bno, 1); 993 fs->e2fs->e2fs_fbcount++; 994 fs->e2fs_gd[cg].ext2bgd_nbfree++; 995 fs->e2fs_fmod = 1; 996 EXT2_UNLOCK(ump); 997 bdwrite(bp); 998} 999 1000/* 1001 * Free an inode. 1002 * 1003 */ 1004int 1005ext2_vfree(struct vnode *pvp, ino_t ino, int mode) 1006{ 1007 struct m_ext2fs *fs; 1008 struct inode *pip; 1009 struct buf *bp; 1010 struct ext2mount *ump; 1011 int error, cg; 1012 char * ibp; 1013 1014 pip = VTOI(pvp); 1015 fs = pip->i_e2fs; 1016 ump = pip->i_ump; 1017 if ((u_int)ino > fs->e2fs_ipg * fs->e2fs_gcount) 1018 panic("ext2_vfree: range: devvp = %p, ino = %ju, fs = %s", 1019 pip->i_devvp, (uintmax_t)ino, fs->e2fs_fsmnt); 1020 1021 cg = ino_to_cg(fs, ino); 1022 error = bread(pip->i_devvp, 1023 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_i_bitmap), 1024 (int)fs->e2fs_bsize, NOCRED, &bp); 1025 if (error) { 1026 brelse(bp); 1027 return (0); 1028 } 1029 ibp = (char *)bp->b_data; 1030 ino = (ino - 1) % fs->e2fs->e2fs_ipg; 1031 if (isclr(ibp, ino)) { 1032 printf("ino = %llu, fs = %s\n", 1033 (unsigned long long)ino, fs->e2fs_fsmnt); 1034 if (fs->e2fs_ronly == 0) 1035 panic("ext2_vfree: freeing free inode"); 1036 } 1037 clrbit(ibp, ino); 1038 EXT2_LOCK(ump); 1039 fs->e2fs->e2fs_ficount++; 1040 fs->e2fs_gd[cg].ext2bgd_nifree++; 1041 if ((mode & IFMT) == IFDIR) { 1042 fs->e2fs_gd[cg].ext2bgd_ndirs--; 1043 fs->e2fs_total_dir--; 1044 } 1045 fs->e2fs_fmod = 1; 1046 EXT2_UNLOCK(ump); 1047 bdwrite(bp); 1048 return (0); 1049} 1050 1051/* 1052 * Find a block in the specified cylinder group. 1053 * 1054 * It is a panic if a request is made to find a block if none are 1055 * available. 1056 */ 1057static daddr_t 1058ext2_mapsearch(struct m_ext2fs *fs, char *bbp, daddr_t bpref) 1059{ 1060 char *loc; 1061 int start, len; 1062 1063 /* 1064 * find the fragment by searching through the free block 1065 * map for an appropriate bit pattern 1066 */ 1067 if (bpref) 1068 start = dtogd(fs, bpref) / NBBY; 1069 else 1070 start = 0; 1071 len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start; 1072 loc = memcchr(&bbp[start], 0xff, len); 1073 if (loc == NULL) { 1074 len = start + 1; 1075 start = 0; 1076 loc = memcchr(&bbp[start], 0xff, len); 1077 if (loc == NULL) { 1078 printf("start = %d, len = %d, fs = %s\n", 1079 start, len, fs->e2fs_fsmnt); 1080 panic("ext2_mapsearch: map corrupted"); 1081 /* NOTREACHED */ 1082 } 1083 } 1084 return ((loc - bbp) * NBBY + ffs(~*loc) - 1); 1085} 1086 1087/* 1088 * Fserr prints the name of a filesystem with an error diagnostic. 1089 * 1090 * The form of the error message is: 1091 * fs: error message 1092 */ 1093static void 1094ext2_fserr(struct m_ext2fs *fs, uid_t uid, char *cp) 1095{ 1096 1097 log(LOG_ERR, "uid %u on %s: %s\n", uid, fs->e2fs_fsmnt, cp); 1098} 1099 1100int 1101cg_has_sb(int i) 1102{ 1103 int a3, a5, a7; 1104 1105 if (i == 0 || i == 1) 1106 return 1; 1107 for (a3 = 3, a5 = 5, a7 = 7; 1108 a3 <= i || a5 <= i || a7 <= i; 1109 a3 *= 3, a5 *= 5, a7 *= 7) 1110 if (i == a3 || i == a5 || i == a7) 1111 return 1; 1112 return 0; 1113} 1114