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