1 /* 2 * Copyright (c) 1982, 1986, 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. 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.18 (Berkeley) 5/26/95 34 * $FreeBSD: src/sys/ufs/ffs/ffs_alloc.c,v 1.64.2.2 2001/09/21 19:15:21 dillon Exp $ 35 * $DragonFly: src/sys/vfs/ufs/ffs_alloc.c,v 1.14 2005/08/14 18:53:42 dillon Exp $ 36 */ 37 38 #include "opt_quota.h" 39 40 #include <sys/param.h> 41 #include <sys/systm.h> 42 #include <sys/buf.h> 43 #include <sys/conf.h> 44 #include <sys/proc.h> 45 #include <sys/vnode.h> 46 #include <sys/mount.h> 47 #include <sys/kernel.h> 48 #include <sys/sysctl.h> 49 #include <sys/syslog.h> 50 51 #include <machine/inttypes.h> 52 53 #include "quota.h" 54 #include "inode.h" 55 #include "ufs_extern.h" 56 #include "ufsmount.h" 57 58 #include "fs.h" 59 #include "ffs_extern.h" 60 61 typedef ufs_daddr_t allocfcn_t (struct inode *ip, int cg, ufs_daddr_t bpref, 62 int size); 63 64 static ufs_daddr_t ffs_alloccg (struct inode *, int, ufs_daddr_t, int); 65 static ufs_daddr_t 66 ffs_alloccgblk (struct inode *, struct buf *, ufs_daddr_t); 67 #ifdef DIAGNOSTIC 68 static int ffs_checkblk (struct inode *, ufs_daddr_t, long); 69 #endif 70 static void ffs_clusteracct (struct fs *, struct cg *, ufs_daddr_t, 71 int); 72 static ufs_daddr_t ffs_clusteralloc (struct inode *, int, ufs_daddr_t, 73 int); 74 static ino_t ffs_dirpref (struct inode *); 75 static ufs_daddr_t ffs_fragextend (struct inode *, int, long, int, int); 76 static void ffs_fserr (struct fs *, uint, char *); 77 static u_long ffs_hashalloc 78 (struct inode *, int, long, int, allocfcn_t *); 79 static ino_t ffs_nodealloccg (struct inode *, int, ufs_daddr_t, int); 80 static ufs_daddr_t ffs_mapsearch (struct fs *, struct cg *, ufs_daddr_t, 81 int); 82 83 /* 84 * Allocate a block in the filesystem. 85 * 86 * The size of the requested block is given, which must be some 87 * multiple of fs_fsize and <= fs_bsize. 88 * A preference may be optionally specified. If a preference is given 89 * the following hierarchy is used to allocate a block: 90 * 1) allocate the requested block. 91 * 2) allocate a rotationally optimal block in the same cylinder. 92 * 3) allocate a block in the same cylinder group. 93 * 4) quadradically rehash into other cylinder groups, until an 94 * available block is located. 95 * If no block preference is given the following heirarchy is used 96 * to allocate a block: 97 * 1) allocate a block in the cylinder group that contains the 98 * inode for the file. 99 * 2) quadradically rehash into other cylinder groups, until an 100 * available block is located. 101 */ 102 int 103 ffs_alloc(struct inode *ip, ufs_daddr_t lbn, ufs_daddr_t bpref, int size, 104 struct ucred *cred, ufs_daddr_t *bnp) 105 { 106 struct fs *fs; 107 ufs_daddr_t bno; 108 int cg; 109 #ifdef QUOTA 110 int error; 111 #endif 112 113 *bnp = 0; 114 fs = ip->i_fs; 115 #ifdef DIAGNOSTIC 116 if ((uint)size > fs->fs_bsize || fragoff(fs, size) != 0) { 117 printf("dev = %s, bsize = %ld, size = %d, fs = %s\n", 118 devtoname(ip->i_dev), (long)fs->fs_bsize, size, 119 fs->fs_fsmnt); 120 panic("ffs_alloc: bad size"); 121 } 122 if (cred == NOCRED) 123 panic("ffs_alloc: missing credential"); 124 #endif /* DIAGNOSTIC */ 125 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 126 goto nospace; 127 if (cred->cr_uid != 0 && 128 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 129 goto nospace; 130 #ifdef QUOTA 131 error = chkdq(ip, (long)btodb(size), cred, 0); 132 if (error) 133 return (error); 134 #endif 135 if (bpref >= fs->fs_size) 136 bpref = 0; 137 if (bpref == 0) 138 cg = ino_to_cg(fs, ip->i_number); 139 else 140 cg = dtog(fs, bpref); 141 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 142 ffs_alloccg); 143 if (bno > 0) { 144 ip->i_blocks += btodb(size); 145 ip->i_flag |= IN_CHANGE | IN_UPDATE; 146 *bnp = bno; 147 return (0); 148 } 149 #ifdef QUOTA 150 /* 151 * Restore user's disk quota because allocation failed. 152 */ 153 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 154 #endif 155 nospace: 156 ffs_fserr(fs, cred->cr_uid, "filesystem full"); 157 uprintf("\n%s: write failed, filesystem is full\n", fs->fs_fsmnt); 158 return (ENOSPC); 159 } 160 161 /* 162 * Reallocate a fragment to a bigger size 163 * 164 * The number and size of the old block is given, and a preference 165 * and new size is also specified. The allocator attempts to extend 166 * the original block. Failing that, the regular block allocator is 167 * invoked to get an appropriate block. 168 */ 169 int 170 ffs_realloccg(struct inode *ip, ufs_daddr_t lbprev, ufs_daddr_t bpref, 171 int osize, int nsize, struct ucred *cred, struct buf **bpp) 172 { 173 struct fs *fs; 174 struct buf *bp; 175 int cg, request, error; 176 ufs_daddr_t bprev, bno; 177 178 *bpp = 0; 179 fs = ip->i_fs; 180 #ifdef DIAGNOSTIC 181 if ((uint)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 182 (uint)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 183 printf( 184 "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n", 185 devtoname(ip->i_dev), (long)fs->fs_bsize, osize, 186 nsize, fs->fs_fsmnt); 187 panic("ffs_realloccg: bad size"); 188 } 189 if (cred == NOCRED) 190 panic("ffs_realloccg: missing credential"); 191 #endif /* DIAGNOSTIC */ 192 if (cred->cr_uid != 0 && 193 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 194 goto nospace; 195 if ((bprev = ip->i_db[lbprev]) == 0) { 196 printf("dev = %s, bsize = %ld, bprev = %ld, fs = %s\n", 197 devtoname(ip->i_dev), (long)fs->fs_bsize, (long)bprev, 198 fs->fs_fsmnt); 199 panic("ffs_realloccg: bad bprev"); 200 } 201 /* 202 * Allocate the extra space in the buffer. 203 */ 204 error = bread(ITOV(ip), lbprev, osize, &bp); 205 if (error) { 206 brelse(bp); 207 return (error); 208 } 209 210 if( bp->b_blkno == bp->b_lblkno) { 211 if( lbprev >= NDADDR) 212 panic("ffs_realloccg: lbprev out of range"); 213 bp->b_blkno = fsbtodb(fs, bprev); 214 } 215 216 #ifdef QUOTA 217 error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 218 if (error) { 219 brelse(bp); 220 return (error); 221 } 222 #endif 223 /* 224 * Check for extension in the existing location. 225 */ 226 cg = dtog(fs, bprev); 227 bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 228 if (bno) { 229 if (bp->b_blkno != fsbtodb(fs, bno)) 230 panic("ffs_realloccg: bad blockno"); 231 ip->i_blocks += btodb(nsize - osize); 232 ip->i_flag |= IN_CHANGE | IN_UPDATE; 233 allocbuf(bp, nsize); 234 bp->b_flags |= B_DONE; 235 bzero((char *)bp->b_data + osize, (uint)nsize - osize); 236 *bpp = bp; 237 return (0); 238 } 239 /* 240 * Allocate a new disk location. 241 */ 242 if (bpref >= fs->fs_size) 243 bpref = 0; 244 switch ((int)fs->fs_optim) { 245 case FS_OPTSPACE: 246 /* 247 * Allocate an exact sized fragment. Although this makes 248 * best use of space, we will waste time relocating it if 249 * the file continues to grow. If the fragmentation is 250 * less than half of the minimum free reserve, we choose 251 * to begin optimizing for time. 252 */ 253 request = nsize; 254 if (fs->fs_minfree <= 5 || 255 fs->fs_cstotal.cs_nffree > 256 (off_t)fs->fs_dsize * fs->fs_minfree / (2 * 100)) 257 break; 258 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 259 fs->fs_fsmnt); 260 fs->fs_optim = FS_OPTTIME; 261 break; 262 case FS_OPTTIME: 263 /* 264 * At this point we have discovered a file that is trying to 265 * grow a small fragment to a larger fragment. To save time, 266 * we allocate a full sized block, then free the unused portion. 267 * If the file continues to grow, the `ffs_fragextend' call 268 * above will be able to grow it in place without further 269 * copying. If aberrant programs cause disk fragmentation to 270 * grow within 2% of the free reserve, we choose to begin 271 * optimizing for space. 272 */ 273 request = fs->fs_bsize; 274 if (fs->fs_cstotal.cs_nffree < 275 (off_t)fs->fs_dsize * (fs->fs_minfree - 2) / 100) 276 break; 277 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 278 fs->fs_fsmnt); 279 fs->fs_optim = FS_OPTSPACE; 280 break; 281 default: 282 printf("dev = %s, optim = %ld, fs = %s\n", 283 devtoname(ip->i_dev), (long)fs->fs_optim, fs->fs_fsmnt); 284 panic("ffs_realloccg: bad optim"); 285 /* NOTREACHED */ 286 } 287 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 288 ffs_alloccg); 289 if (bno > 0) { 290 bp->b_blkno = fsbtodb(fs, bno); 291 if (!DOINGSOFTDEP(ITOV(ip))) 292 ffs_blkfree(ip, bprev, (long)osize); 293 if (nsize < request) 294 ffs_blkfree(ip, bno + numfrags(fs, nsize), 295 (long)(request - nsize)); 296 ip->i_blocks += btodb(nsize - osize); 297 ip->i_flag |= IN_CHANGE | IN_UPDATE; 298 allocbuf(bp, nsize); 299 bp->b_flags |= B_DONE; 300 bzero((char *)bp->b_data + osize, (uint)nsize - osize); 301 *bpp = bp; 302 return (0); 303 } 304 #ifdef QUOTA 305 /* 306 * Restore user's disk quota because allocation failed. 307 */ 308 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 309 #endif 310 brelse(bp); 311 nospace: 312 /* 313 * no space available 314 */ 315 ffs_fserr(fs, cred->cr_uid, "filesystem full"); 316 uprintf("\n%s: write failed, filesystem is full\n", fs->fs_fsmnt); 317 return (ENOSPC); 318 } 319 320 SYSCTL_NODE(_vfs, OID_AUTO, ffs, CTLFLAG_RW, 0, "FFS filesystem"); 321 322 /* 323 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 324 * 325 * The vnode and an array of buffer pointers for a range of sequential 326 * logical blocks to be made contiguous is given. The allocator attempts 327 * to find a range of sequential blocks starting as close as possible to 328 * an fs_rotdelay offset from the end of the allocation for the logical 329 * block immediately preceeding the current range. If successful, the 330 * physical block numbers in the buffer pointers and in the inode are 331 * changed to reflect the new allocation. If unsuccessful, the allocation 332 * is left unchanged. The success in doing the reallocation is returned. 333 * Note that the error return is not reflected back to the user. Rather 334 * the previous block allocation will be used. 335 */ 336 static int doasyncfree = 1; 337 SYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 338 339 static int doreallocblks = 1; 340 SYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 341 342 #ifdef DEBUG 343 static volatile int prtrealloc = 0; 344 #endif 345 346 /* 347 * ffs_reallocblks(struct vnode *a_vp, struct cluster_save *a_buflist) 348 */ 349 int 350 ffs_reallocblks(struct vop_reallocblks_args *ap) 351 { 352 struct fs *fs; 353 struct inode *ip; 354 struct vnode *vp; 355 struct buf *sbp, *ebp; 356 ufs_daddr_t *bap, *sbap, *ebap = 0; 357 struct cluster_save *buflist; 358 ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 359 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 360 int i, len, start_lvl, end_lvl, pref, ssize; 361 362 if (doreallocblks == 0) 363 return (ENOSPC); 364 vp = ap->a_vp; 365 ip = VTOI(vp); 366 fs = ip->i_fs; 367 if (fs->fs_contigsumsize <= 0) 368 return (ENOSPC); 369 buflist = ap->a_buflist; 370 len = buflist->bs_nchildren; 371 start_lbn = buflist->bs_children[0]->b_lblkno; 372 end_lbn = start_lbn + len - 1; 373 #ifdef DIAGNOSTIC 374 for (i = 0; i < len; i++) 375 if (!ffs_checkblk(ip, 376 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 377 panic("ffs_reallocblks: unallocated block 1"); 378 for (i = 1; i < len; i++) 379 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 380 panic("ffs_reallocblks: non-logical cluster"); 381 blkno = buflist->bs_children[0]->b_blkno; 382 ssize = fsbtodb(fs, fs->fs_frag); 383 for (i = 1; i < len - 1; i++) 384 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 385 panic("ffs_reallocblks: non-physical cluster %d", i); 386 #endif 387 /* 388 * If the latest allocation is in a new cylinder group, assume that 389 * the filesystem has decided to move and do not force it back to 390 * the previous cylinder group. 391 */ 392 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 393 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 394 return (ENOSPC); 395 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 396 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 397 return (ENOSPC); 398 /* 399 * Get the starting offset and block map for the first block. 400 */ 401 if (start_lvl == 0) { 402 sbap = &ip->i_db[0]; 403 soff = start_lbn; 404 } else { 405 idp = &start_ap[start_lvl - 1]; 406 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, &sbp)) { 407 brelse(sbp); 408 return (ENOSPC); 409 } 410 sbap = (ufs_daddr_t *)sbp->b_data; 411 soff = idp->in_off; 412 } 413 /* 414 * Find the preferred location for the cluster. 415 */ 416 pref = ffs_blkpref(ip, start_lbn, soff, sbap); 417 /* 418 * If the block range spans two block maps, get the second map. 419 */ 420 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 421 ssize = len; 422 } else { 423 #ifdef DIAGNOSTIC 424 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 425 panic("ffs_reallocblk: start == end"); 426 #endif 427 ssize = len - (idp->in_off + 1); 428 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, &ebp)) 429 goto fail; 430 ebap = (ufs_daddr_t *)ebp->b_data; 431 } 432 /* 433 * Search the block map looking for an allocation of the desired size. 434 */ 435 if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 436 len, ffs_clusteralloc)) == 0) 437 goto fail; 438 /* 439 * We have found a new contiguous block. 440 * 441 * First we have to replace the old block pointers with the new 442 * block pointers in the inode and indirect blocks associated 443 * with the file. 444 */ 445 #ifdef DEBUG 446 if (prtrealloc) 447 printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 448 start_lbn, end_lbn); 449 #endif 450 blkno = newblk; 451 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 452 if (i == ssize) { 453 bap = ebap; 454 soff = -i; 455 } 456 #ifdef DIAGNOSTIC 457 if (!ffs_checkblk(ip, 458 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 459 panic("ffs_reallocblks: unallocated block 2"); 460 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 461 panic("ffs_reallocblks: alloc mismatch"); 462 #endif 463 #ifdef DEBUG 464 if (prtrealloc) 465 printf(" %d,", *bap); 466 #endif 467 if (DOINGSOFTDEP(vp)) { 468 if (sbap == &ip->i_db[0] && i < ssize) 469 softdep_setup_allocdirect(ip, start_lbn + i, 470 blkno, *bap, fs->fs_bsize, fs->fs_bsize, 471 buflist->bs_children[i]); 472 else 473 softdep_setup_allocindir_page(ip, start_lbn + i, 474 i < ssize ? sbp : ebp, soff + i, blkno, 475 *bap, buflist->bs_children[i]); 476 } 477 *bap++ = blkno; 478 } 479 /* 480 * Next we must write out the modified inode and indirect blocks. 481 * For strict correctness, the writes should be synchronous since 482 * the old block values may have been written to disk. In practise 483 * they are almost never written, but if we are concerned about 484 * strict correctness, the `doasyncfree' flag should be set to zero. 485 * 486 * The test on `doasyncfree' should be changed to test a flag 487 * that shows whether the associated buffers and inodes have 488 * been written. The flag should be set when the cluster is 489 * started and cleared whenever the buffer or inode is flushed. 490 * We can then check below to see if it is set, and do the 491 * synchronous write only when it has been cleared. 492 */ 493 if (sbap != &ip->i_db[0]) { 494 if (doasyncfree) 495 bdwrite(sbp); 496 else 497 bwrite(sbp); 498 } else { 499 ip->i_flag |= IN_CHANGE | IN_UPDATE; 500 if (!doasyncfree) 501 UFS_UPDATE(vp, 1); 502 } 503 if (ssize < len) { 504 if (doasyncfree) 505 bdwrite(ebp); 506 else 507 bwrite(ebp); 508 } 509 /* 510 * Last, free the old blocks and assign the new blocks to the buffers. 511 */ 512 #ifdef DEBUG 513 if (prtrealloc) 514 printf("\n\tnew:"); 515 #endif 516 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 517 if (!DOINGSOFTDEP(vp)) 518 ffs_blkfree(ip, 519 dbtofsb(fs, buflist->bs_children[i]->b_blkno), 520 fs->fs_bsize); 521 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 522 #ifdef DIAGNOSTIC 523 if (!ffs_checkblk(ip, 524 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 525 panic("ffs_reallocblks: unallocated block 3"); 526 #endif 527 #ifdef DEBUG 528 if (prtrealloc) 529 printf(" %d,", blkno); 530 #endif 531 } 532 #ifdef DEBUG 533 if (prtrealloc) { 534 prtrealloc--; 535 printf("\n"); 536 } 537 #endif 538 return (0); 539 540 fail: 541 if (ssize < len) 542 brelse(ebp); 543 if (sbap != &ip->i_db[0]) 544 brelse(sbp); 545 return (ENOSPC); 546 } 547 548 /* 549 * Allocate an inode in the filesystem. 550 * 551 * If allocating a directory, use ffs_dirpref to select the inode. 552 * If allocating in a directory, the following hierarchy is followed: 553 * 1) allocate the preferred inode. 554 * 2) allocate an inode in the same cylinder group. 555 * 3) quadradically rehash into other cylinder groups, until an 556 * available inode is located. 557 * If no inode preference is given the following heirarchy is used 558 * to allocate an inode: 559 * 1) allocate an inode in cylinder group 0. 560 * 2) quadradically rehash into other cylinder groups, until an 561 * available inode is located. 562 */ 563 int 564 ffs_valloc(struct vnode *pvp, int mode, struct ucred *cred, struct vnode **vpp) 565 { 566 struct inode *pip; 567 struct fs *fs; 568 struct inode *ip; 569 ino_t ino, ipref; 570 int cg, error; 571 572 *vpp = NULL; 573 pip = VTOI(pvp); 574 fs = pip->i_fs; 575 if (fs->fs_cstotal.cs_nifree == 0) 576 goto noinodes; 577 578 if ((mode & IFMT) == IFDIR) 579 ipref = ffs_dirpref(pip); 580 else 581 ipref = pip->i_number; 582 if (ipref >= fs->fs_ncg * fs->fs_ipg) 583 ipref = 0; 584 cg = ino_to_cg(fs, ipref); 585 /* 586 * Track number of dirs created one after another 587 * in a same cg without intervening by files. 588 */ 589 if ((mode & IFMT) == IFDIR) { 590 if (fs->fs_contigdirs[cg] < 255) 591 fs->fs_contigdirs[cg]++; 592 } else { 593 if (fs->fs_contigdirs[cg] > 0) 594 fs->fs_contigdirs[cg]--; 595 } 596 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 597 (allocfcn_t *)ffs_nodealloccg); 598 if (ino == 0) 599 goto noinodes; 600 error = VFS_VGET(pvp->v_mount, ino, vpp); 601 if (error) { 602 UFS_VFREE(pvp, ino, mode); 603 return (error); 604 } 605 ip = VTOI(*vpp); 606 if (ip->i_mode) { 607 printf("mode = 0%o, inum = %lu, fs = %s\n", 608 ip->i_mode, (u_long)ip->i_number, fs->fs_fsmnt); 609 panic("ffs_valloc: dup alloc"); 610 } 611 if (ip->i_blocks) { /* XXX */ 612 printf("free inode %s/%lu had %ld blocks\n", 613 fs->fs_fsmnt, (u_long)ino, (long)ip->i_blocks); 614 ip->i_blocks = 0; 615 } 616 ip->i_flags = 0; 617 /* 618 * Set up a new generation number for this inode. 619 */ 620 if (ip->i_gen == 0 || ++ip->i_gen == 0) 621 ip->i_gen = random() / 2 + 1; 622 return (0); 623 noinodes: 624 ffs_fserr(fs, cred->cr_uid, "out of inodes"); 625 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 626 return (ENOSPC); 627 } 628 629 /* 630 * Find a cylinder group to place a directory. 631 * 632 * The policy implemented by this algorithm is to allocate a 633 * directory inode in the same cylinder group as its parent 634 * directory, but also to reserve space for its files inodes 635 * and data. Restrict the number of directories which may be 636 * allocated one after another in the same cylinder group 637 * without intervening allocation of files. 638 * 639 * If we allocate a first level directory then force allocation 640 * in another cylinder group. 641 */ 642 static ino_t 643 ffs_dirpref(struct inode *pip) 644 { 645 struct fs *fs; 646 int cg, prefcg, dirsize, cgsize; 647 int64_t dirsize64; 648 int avgifree, avgbfree, avgndir, curdirsize; 649 int minifree, minbfree, maxndir; 650 int mincg, minndir; 651 int maxcontigdirs; 652 653 fs = pip->i_fs; 654 655 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 656 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 657 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg; 658 659 /* 660 * Force allocation in another cg if creating a first level dir. 661 */ 662 if (ITOV(pip)->v_flag & VROOT) { 663 prefcg = arc4random() % fs->fs_ncg; 664 mincg = prefcg; 665 minndir = fs->fs_ipg; 666 for (cg = prefcg; cg < fs->fs_ncg; cg++) 667 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 668 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 669 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 670 mincg = cg; 671 minndir = fs->fs_cs(fs, cg).cs_ndir; 672 } 673 for (cg = 0; cg < prefcg; cg++) 674 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 675 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 676 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 677 mincg = cg; 678 minndir = fs->fs_cs(fs, cg).cs_ndir; 679 } 680 return ((ino_t)(fs->fs_ipg * mincg)); 681 } 682 683 /* 684 * Count various limits which used for 685 * optimal allocation of a directory inode. 686 */ 687 maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg); 688 minifree = avgifree - avgifree / 4; 689 if (minifree < 1) 690 minifree = 1; 691 minbfree = avgbfree - avgbfree / 4; 692 if (minbfree < 1) 693 minbfree = 1; 694 cgsize = fs->fs_fsize * fs->fs_fpg; 695 696 /* 697 * fs_avgfilesize and fs_avgfpdir are user-settable entities and 698 * multiplying them may overflow a 32 bit integer. 699 */ 700 dirsize64 = fs->fs_avgfilesize * (int64_t)fs->fs_avgfpdir; 701 if (dirsize64 > 0x7fffffff) { 702 maxcontigdirs = 1; 703 } else { 704 dirsize = (int)dirsize64; 705 curdirsize = avgndir ? 706 (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0; 707 if (dirsize < curdirsize) 708 dirsize = curdirsize; 709 maxcontigdirs = min((avgbfree * fs->fs_bsize) / dirsize, 255); 710 if (fs->fs_avgfpdir > 0) 711 maxcontigdirs = min(maxcontigdirs, 712 fs->fs_ipg / fs->fs_avgfpdir); 713 if (maxcontigdirs == 0) 714 maxcontigdirs = 1; 715 } 716 717 /* 718 * Limit number of dirs in one cg and reserve space for 719 * regular files, but only if we have no deficit in 720 * inodes or space. 721 */ 722 prefcg = ino_to_cg(fs, pip->i_number); 723 for (cg = prefcg; cg < fs->fs_ncg; cg++) 724 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 725 fs->fs_cs(fs, cg).cs_nifree >= minifree && 726 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 727 if (fs->fs_contigdirs[cg] < maxcontigdirs) 728 return ((ino_t)(fs->fs_ipg * cg)); 729 } 730 for (cg = 0; cg < prefcg; cg++) 731 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 732 fs->fs_cs(fs, cg).cs_nifree >= minifree && 733 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 734 if (fs->fs_contigdirs[cg] < maxcontigdirs) 735 return ((ino_t)(fs->fs_ipg * cg)); 736 } 737 /* 738 * This is a backstop when we have deficit in space. 739 */ 740 for (cg = prefcg; cg < fs->fs_ncg; cg++) 741 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 742 return ((ino_t)(fs->fs_ipg * cg)); 743 for (cg = 0; cg < prefcg; cg++) 744 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 745 break; 746 return ((ino_t)(fs->fs_ipg * cg)); 747 } 748 749 /* 750 * Select the desired position for the next block in a file. The file is 751 * logically divided into sections. The first section is composed of the 752 * direct blocks. Each additional section contains fs_maxbpg blocks. 753 * 754 * If no blocks have been allocated in the first section, the policy is to 755 * request a block in the same cylinder group as the inode that describes 756 * the file. If no blocks have been allocated in any other section, the 757 * policy is to place the section in a cylinder group with a greater than 758 * average number of free blocks. An appropriate cylinder group is found 759 * by using a rotor that sweeps the cylinder groups. When a new group of 760 * blocks is needed, the sweep begins in the cylinder group following the 761 * cylinder group from which the previous allocation was made. The sweep 762 * continues until a cylinder group with greater than the average number 763 * of free blocks is found. If the allocation is for the first block in an 764 * indirect block, the information on the previous allocation is unavailable; 765 * here a best guess is made based upon the logical block number being 766 * allocated. 767 * 768 * If a section is already partially allocated, the policy is to 769 * contiguously allocate fs_maxcontig blocks. The end of one of these 770 * contiguous blocks and the beginning of the next is physically separated 771 * so that the disk head will be in transit between them for at least 772 * fs_rotdelay milliseconds. This is to allow time for the processor to 773 * schedule another I/O transfer. 774 */ 775 ufs_daddr_t 776 ffs_blkpref(struct inode *ip, ufs_daddr_t lbn, int indx, ufs_daddr_t *bap) 777 { 778 struct fs *fs; 779 int cg; 780 int avgbfree, startcg; 781 ufs_daddr_t nextblk; 782 783 fs = ip->i_fs; 784 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 785 if (lbn < NDADDR + NINDIR(fs)) { 786 cg = ino_to_cg(fs, ip->i_number); 787 return (fs->fs_fpg * cg + fs->fs_frag); 788 } 789 /* 790 * Find a cylinder with greater than average number of 791 * unused data blocks. 792 */ 793 if (indx == 0 || bap[indx - 1] == 0) 794 startcg = 795 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 796 else 797 startcg = dtog(fs, bap[indx - 1]) + 1; 798 startcg %= fs->fs_ncg; 799 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 800 for (cg = startcg; cg < fs->fs_ncg; cg++) 801 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 802 fs->fs_cgrotor = cg; 803 return (fs->fs_fpg * cg + fs->fs_frag); 804 } 805 for (cg = 0; cg <= startcg; cg++) 806 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 807 fs->fs_cgrotor = cg; 808 return (fs->fs_fpg * cg + fs->fs_frag); 809 } 810 return (0); 811 } 812 /* 813 * One or more previous blocks have been laid out. If less 814 * than fs_maxcontig previous blocks are contiguous, the 815 * next block is requested contiguously, otherwise it is 816 * requested rotationally delayed by fs_rotdelay milliseconds. 817 */ 818 nextblk = bap[indx - 1] + fs->fs_frag; 819 if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 820 bap[indx - fs->fs_maxcontig] + 821 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 822 return (nextblk); 823 /* 824 * Here we convert ms of delay to frags as: 825 * (frags) = (ms) * (rev/sec) * (sect/rev) / 826 * ((sect/frag) * (ms/sec)) 827 * then round up to the next block. 828 */ 829 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 830 (NSPF(fs) * 1000), fs->fs_frag); 831 return (nextblk); 832 } 833 834 /* 835 * Implement the cylinder overflow algorithm. 836 * 837 * The policy implemented by this algorithm is: 838 * 1) allocate the block in its requested cylinder group. 839 * 2) quadradically rehash on the cylinder group number. 840 * 3) brute force search for a free block. 841 */ 842 /*VARARGS5*/ 843 static u_long 844 ffs_hashalloc(struct inode *ip, int cg, long pref, 845 int size, /* size for data blocks, mode for inodes */ 846 allocfcn_t *allocator) 847 { 848 struct fs *fs; 849 long result; /* XXX why not same type as we return? */ 850 int i, icg = cg; 851 852 fs = ip->i_fs; 853 /* 854 * 1: preferred cylinder group 855 */ 856 result = (*allocator)(ip, cg, pref, size); 857 if (result) 858 return (result); 859 /* 860 * 2: quadratic rehash 861 */ 862 for (i = 1; i < fs->fs_ncg; i *= 2) { 863 cg += i; 864 if (cg >= fs->fs_ncg) 865 cg -= fs->fs_ncg; 866 result = (*allocator)(ip, cg, 0, size); 867 if (result) 868 return (result); 869 } 870 /* 871 * 3: brute force search 872 * Note that we start at i == 2, since 0 was checked initially, 873 * and 1 is always checked in the quadratic rehash. 874 */ 875 cg = (icg + 2) % fs->fs_ncg; 876 for (i = 2; i < fs->fs_ncg; i++) { 877 result = (*allocator)(ip, cg, 0, size); 878 if (result) 879 return (result); 880 cg++; 881 if (cg == fs->fs_ncg) 882 cg = 0; 883 } 884 return (0); 885 } 886 887 /* 888 * Determine whether a fragment can be extended. 889 * 890 * Check to see if the necessary fragments are available, and 891 * if they are, allocate them. 892 */ 893 static ufs_daddr_t 894 ffs_fragextend(struct inode *ip, int cg, long bprev, int osize, int nsize) 895 { 896 struct fs *fs; 897 struct cg *cgp; 898 struct buf *bp; 899 long bno; 900 int frags, bbase; 901 int i, error; 902 uint8_t *blksfree; 903 904 fs = ip->i_fs; 905 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 906 return (0); 907 frags = numfrags(fs, nsize); 908 bbase = fragnum(fs, bprev); 909 if (bbase > fragnum(fs, (bprev + frags - 1))) { 910 /* cannot extend across a block boundary */ 911 return (0); 912 } 913 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 914 (int)fs->fs_cgsize, &bp); 915 if (error) { 916 brelse(bp); 917 return (0); 918 } 919 cgp = (struct cg *)bp->b_data; 920 if (!cg_chkmagic(cgp)) { 921 brelse(bp); 922 return (0); 923 } 924 bp->b_xflags |= BX_BKGRDWRITE; 925 cgp->cg_time = time_second; 926 bno = dtogd(fs, bprev); 927 blksfree = cg_blksfree(cgp); 928 for (i = numfrags(fs, osize); i < frags; i++) 929 if (isclr(blksfree, bno + i)) { 930 brelse(bp); 931 return (0); 932 } 933 /* 934 * the current fragment can be extended 935 * deduct the count on fragment being extended into 936 * increase the count on the remaining fragment (if any) 937 * allocate the extended piece 938 */ 939 for (i = frags; i < fs->fs_frag - bbase; i++) 940 if (isclr(blksfree, bno + i)) 941 break; 942 cgp->cg_frsum[i - numfrags(fs, osize)]--; 943 if (i != frags) 944 cgp->cg_frsum[i - frags]++; 945 for (i = numfrags(fs, osize); i < frags; i++) { 946 clrbit(blksfree, bno + i); 947 cgp->cg_cs.cs_nffree--; 948 fs->fs_cstotal.cs_nffree--; 949 fs->fs_cs(fs, cg).cs_nffree--; 950 } 951 fs->fs_fmod = 1; 952 if (DOINGSOFTDEP(ITOV(ip))) 953 softdep_setup_blkmapdep(bp, fs, bprev); 954 bdwrite(bp); 955 return (bprev); 956 } 957 958 /* 959 * Determine whether a block can be allocated. 960 * 961 * Check to see if a block of the appropriate size is available, 962 * and if it is, allocate it. 963 */ 964 static ufs_daddr_t 965 ffs_alloccg(struct inode *ip, int cg, ufs_daddr_t bpref, int size) 966 { 967 struct fs *fs; 968 struct cg *cgp; 969 struct buf *bp; 970 int i; 971 ufs_daddr_t bno, blkno; 972 int allocsiz, error, frags; 973 uint8_t *blksfree; 974 975 fs = ip->i_fs; 976 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 977 return (0); 978 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 979 (int)fs->fs_cgsize, &bp); 980 if (error) { 981 brelse(bp); 982 return (0); 983 } 984 cgp = (struct cg *)bp->b_data; 985 if (!cg_chkmagic(cgp) || 986 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 987 brelse(bp); 988 return (0); 989 } 990 bp->b_xflags |= BX_BKGRDWRITE; 991 cgp->cg_time = time_second; 992 if (size == fs->fs_bsize) { 993 bno = ffs_alloccgblk(ip, bp, bpref); 994 bdwrite(bp); 995 return (bno); 996 } 997 /* 998 * check to see if any fragments are already available 999 * allocsiz is the size which will be allocated, hacking 1000 * it down to a smaller size if necessary 1001 */ 1002 blksfree = cg_blksfree(cgp); 1003 frags = numfrags(fs, size); 1004 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 1005 if (cgp->cg_frsum[allocsiz] != 0) 1006 break; 1007 if (allocsiz == fs->fs_frag) { 1008 /* 1009 * no fragments were available, so a block will be 1010 * allocated, and hacked up 1011 */ 1012 if (cgp->cg_cs.cs_nbfree == 0) { 1013 brelse(bp); 1014 return (0); 1015 } 1016 bno = ffs_alloccgblk(ip, bp, bpref); 1017 bpref = dtogd(fs, bno); 1018 for (i = frags; i < fs->fs_frag; i++) 1019 setbit(blksfree, bpref + i); 1020 i = fs->fs_frag - frags; 1021 cgp->cg_cs.cs_nffree += i; 1022 fs->fs_cstotal.cs_nffree += i; 1023 fs->fs_cs(fs, cg).cs_nffree += i; 1024 fs->fs_fmod = 1; 1025 cgp->cg_frsum[i]++; 1026 bdwrite(bp); 1027 return (bno); 1028 } 1029 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 1030 if (bno < 0) { 1031 brelse(bp); 1032 return (0); 1033 } 1034 for (i = 0; i < frags; i++) 1035 clrbit(blksfree, bno + i); 1036 cgp->cg_cs.cs_nffree -= frags; 1037 fs->fs_cstotal.cs_nffree -= frags; 1038 fs->fs_cs(fs, cg).cs_nffree -= frags; 1039 fs->fs_fmod = 1; 1040 cgp->cg_frsum[allocsiz]--; 1041 if (frags != allocsiz) 1042 cgp->cg_frsum[allocsiz - frags]++; 1043 blkno = cg * fs->fs_fpg + bno; 1044 if (DOINGSOFTDEP(ITOV(ip))) 1045 softdep_setup_blkmapdep(bp, fs, blkno); 1046 bdwrite(bp); 1047 return ((u_long)blkno); 1048 } 1049 1050 /* 1051 * Allocate a block in a cylinder group. 1052 * 1053 * This algorithm implements the following policy: 1054 * 1) allocate the requested block. 1055 * 2) allocate a rotationally optimal block in the same cylinder. 1056 * 3) allocate the next available block on the block rotor for the 1057 * specified cylinder group. 1058 * Note that this routine only allocates fs_bsize blocks; these 1059 * blocks may be fragmented by the routine that allocates them. 1060 */ 1061 static ufs_daddr_t 1062 ffs_alloccgblk(struct inode *ip, struct buf *bp, ufs_daddr_t bpref) 1063 { 1064 struct fs *fs; 1065 struct cg *cgp; 1066 ufs_daddr_t bno, blkno; 1067 int cylno, pos, delta; 1068 short *cylbp; 1069 int i; 1070 uint8_t *blksfree; 1071 1072 fs = ip->i_fs; 1073 cgp = (struct cg *)bp->b_data; 1074 blksfree = cg_blksfree(cgp); 1075 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 1076 bpref = cgp->cg_rotor; 1077 goto norot; 1078 } 1079 bpref = blknum(fs, bpref); 1080 bpref = dtogd(fs, bpref); 1081 /* 1082 * if the requested block is available, use it 1083 */ 1084 if (ffs_isblock(fs, blksfree, fragstoblks(fs, bpref))) { 1085 bno = bpref; 1086 goto gotit; 1087 } 1088 if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 1089 /* 1090 * Block layout information is not available. 1091 * Leaving bpref unchanged means we take the 1092 * next available free block following the one 1093 * we just allocated. Hopefully this will at 1094 * least hit a track cache on drives of unknown 1095 * geometry (e.g. SCSI). 1096 */ 1097 goto norot; 1098 } 1099 /* 1100 * check for a block available on the same cylinder 1101 */ 1102 cylno = cbtocylno(fs, bpref); 1103 if (cg_blktot(cgp)[cylno] == 0) 1104 goto norot; 1105 /* 1106 * check the summary information to see if a block is 1107 * available in the requested cylinder starting at the 1108 * requested rotational position and proceeding around. 1109 */ 1110 cylbp = cg_blks(fs, cgp, cylno); 1111 pos = cbtorpos(fs, bpref); 1112 for (i = pos; i < fs->fs_nrpos; i++) 1113 if (cylbp[i] > 0) 1114 break; 1115 if (i == fs->fs_nrpos) 1116 for (i = 0; i < pos; i++) 1117 if (cylbp[i] > 0) 1118 break; 1119 if (cylbp[i] > 0) { 1120 /* 1121 * found a rotational position, now find the actual 1122 * block. A panic if none is actually there. 1123 */ 1124 pos = cylno % fs->fs_cpc; 1125 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 1126 if (fs_postbl(fs, pos)[i] == -1) { 1127 printf("pos = %d, i = %d, fs = %s\n", 1128 pos, i, fs->fs_fsmnt); 1129 panic("ffs_alloccgblk: cyl groups corrupted"); 1130 } 1131 for (i = fs_postbl(fs, pos)[i];; ) { 1132 if (ffs_isblock(fs, blksfree, bno + i)) { 1133 bno = blkstofrags(fs, (bno + i)); 1134 goto gotit; 1135 } 1136 delta = fs_rotbl(fs)[i]; 1137 if (delta <= 0 || 1138 delta + i > fragstoblks(fs, fs->fs_fpg)) 1139 break; 1140 i += delta; 1141 } 1142 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 1143 panic("ffs_alloccgblk: can't find blk in cyl"); 1144 } 1145 norot: 1146 /* 1147 * no blocks in the requested cylinder, so take next 1148 * available one in this cylinder group. 1149 */ 1150 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1151 if (bno < 0) 1152 return (0); 1153 cgp->cg_rotor = bno; 1154 gotit: 1155 blkno = fragstoblks(fs, bno); 1156 ffs_clrblock(fs, blksfree, (long)blkno); 1157 ffs_clusteracct(fs, cgp, blkno, -1); 1158 cgp->cg_cs.cs_nbfree--; 1159 fs->fs_cstotal.cs_nbfree--; 1160 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 1161 cylno = cbtocylno(fs, bno); 1162 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 1163 cg_blktot(cgp)[cylno]--; 1164 fs->fs_fmod = 1; 1165 blkno = cgp->cg_cgx * fs->fs_fpg + bno; 1166 if (DOINGSOFTDEP(ITOV(ip))) 1167 softdep_setup_blkmapdep(bp, fs, blkno); 1168 return (blkno); 1169 } 1170 1171 /* 1172 * Determine whether a cluster can be allocated. 1173 * 1174 * We do not currently check for optimal rotational layout if there 1175 * are multiple choices in the same cylinder group. Instead we just 1176 * take the first one that we find following bpref. 1177 */ 1178 static ufs_daddr_t 1179 ffs_clusteralloc(struct inode *ip, int cg, ufs_daddr_t bpref, int len) 1180 { 1181 struct fs *fs; 1182 struct cg *cgp; 1183 struct buf *bp; 1184 int i, got, run, bno, bit, map; 1185 u_char *mapp; 1186 int32_t *lp; 1187 uint8_t *blksfree; 1188 1189 fs = ip->i_fs; 1190 if (fs->fs_maxcluster[cg] < len) 1191 return (0); 1192 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 1193 &bp)) 1194 goto fail; 1195 cgp = (struct cg *)bp->b_data; 1196 if (!cg_chkmagic(cgp)) 1197 goto fail; 1198 bp->b_xflags |= BX_BKGRDWRITE; 1199 /* 1200 * Check to see if a cluster of the needed size (or bigger) is 1201 * available in this cylinder group. 1202 */ 1203 lp = &cg_clustersum(cgp)[len]; 1204 for (i = len; i <= fs->fs_contigsumsize; i++) 1205 if (*lp++ > 0) 1206 break; 1207 if (i > fs->fs_contigsumsize) { 1208 /* 1209 * This is the first time looking for a cluster in this 1210 * cylinder group. Update the cluster summary information 1211 * to reflect the true maximum sized cluster so that 1212 * future cluster allocation requests can avoid reading 1213 * the cylinder group map only to find no clusters. 1214 */ 1215 lp = &cg_clustersum(cgp)[len - 1]; 1216 for (i = len - 1; i > 0; i--) 1217 if (*lp-- > 0) 1218 break; 1219 fs->fs_maxcluster[cg] = i; 1220 goto fail; 1221 } 1222 /* 1223 * Search the cluster map to find a big enough cluster. 1224 * We take the first one that we find, even if it is larger 1225 * than we need as we prefer to get one close to the previous 1226 * block allocation. We do not search before the current 1227 * preference point as we do not want to allocate a block 1228 * that is allocated before the previous one (as we will 1229 * then have to wait for another pass of the elevator 1230 * algorithm before it will be read). We prefer to fail and 1231 * be recalled to try an allocation in the next cylinder group. 1232 */ 1233 if (dtog(fs, bpref) != cg) 1234 bpref = 0; 1235 else 1236 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 1237 mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 1238 map = *mapp++; 1239 bit = 1 << (bpref % NBBY); 1240 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 1241 if ((map & bit) == 0) { 1242 run = 0; 1243 } else { 1244 run++; 1245 if (run == len) 1246 break; 1247 } 1248 if ((got & (NBBY - 1)) != (NBBY - 1)) { 1249 bit <<= 1; 1250 } else { 1251 map = *mapp++; 1252 bit = 1; 1253 } 1254 } 1255 if (got >= cgp->cg_nclusterblks) 1256 goto fail; 1257 /* 1258 * Allocate the cluster that we have found. 1259 */ 1260 blksfree = cg_blksfree(cgp); 1261 for (i = 1; i <= len; i++) 1262 if (!ffs_isblock(fs, blksfree, got - run + i)) 1263 panic("ffs_clusteralloc: map mismatch"); 1264 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 1265 if (dtog(fs, bno) != cg) 1266 panic("ffs_clusteralloc: allocated out of group"); 1267 len = blkstofrags(fs, len); 1268 for (i = 0; i < len; i += fs->fs_frag) 1269 if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i) 1270 panic("ffs_clusteralloc: lost block"); 1271 bdwrite(bp); 1272 return (bno); 1273 1274 fail: 1275 brelse(bp); 1276 return (0); 1277 } 1278 1279 /* 1280 * Determine whether an inode can be allocated. 1281 * 1282 * Check to see if an inode is available, and if it is, 1283 * allocate it using the following policy: 1284 * 1) allocate the requested inode. 1285 * 2) allocate the next available inode after the requested 1286 * inode in the specified cylinder group. 1287 * 3) the inode must not already be in the inode hash table. We 1288 * can encounter such a case because the vnode reclamation sequence 1289 * frees the bit 1290 * 3) the inode must not already be in the inode hash, otherwise it 1291 * may be in the process of being deallocated. This can occur 1292 * because the bitmap is updated before the inode is removed from 1293 * hash. If we were to reallocate the inode the caller could wind 1294 * up returning a vnode/inode combination which is in an indeterminate 1295 * state. 1296 */ 1297 static ino_t 1298 ffs_nodealloccg(struct inode *ip, int cg, ufs_daddr_t ipref, int mode) 1299 { 1300 struct fs *fs; 1301 struct cg *cgp; 1302 struct buf *bp; 1303 uint8_t *inosused; 1304 uint8_t map; 1305 int error, len, arraysize, i; 1306 int icheckmiss; 1307 ufs_daddr_t ibase; 1308 1309 fs = ip->i_fs; 1310 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1311 return (0); 1312 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1313 (int)fs->fs_cgsize, &bp); 1314 if (error) { 1315 brelse(bp); 1316 return (0); 1317 } 1318 cgp = (struct cg *)bp->b_data; 1319 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 1320 brelse(bp); 1321 return (0); 1322 } 1323 inosused = cg_inosused(cgp); 1324 icheckmiss = 0; 1325 1326 /* 1327 * Quick check, reuse the most recently free inode or continue 1328 * a scan from where we left off the last time. 1329 */ 1330 ibase = cg * fs->fs_ipg; 1331 if (ipref) { 1332 ipref %= fs->fs_ipg; 1333 if (isclr(inosused, ipref)) { 1334 if (ufs_ihashcheck(ip->i_dev, ibase + ipref) == 0) 1335 goto gotit; 1336 } 1337 } 1338 1339 /* 1340 * Scan the inode bitmap starting at irotor, be sure to handle 1341 * the edge case by going back to the beginning of the array. 1342 * 1343 * If the number of inodes is not byte-aligned, the unused bits 1344 * should be set to 1. This will be sanity checked in gotit. Note 1345 * that we have to be sure not to overlap the beginning and end 1346 * when irotor is in the middle of a byte as this will cause the 1347 * same bitmap byte to be checked twice. To solve this problem we 1348 * just convert everything to a byte index for the loop. 1349 */ 1350 ipref = (cgp->cg_irotor % fs->fs_ipg) >> 3; /* byte index */ 1351 len = (fs->fs_ipg + 7) >> 3; /* byte size */ 1352 arraysize = len; 1353 1354 while (len > 0) { 1355 map = inosused[ipref]; 1356 if (map != 255) { 1357 for (i = 0; i < NBBY; ++i) { 1358 /* 1359 * If we find a free bit we have to make sure 1360 * that the inode is not in the middle of 1361 * being destroyed. The inode should not exist 1362 * in the inode hash. 1363 * 1364 * Adjust the rotor to try to hit the 1365 * quick-check up above. 1366 */ 1367 if ((map & (1 << i)) == 0) { 1368 if (ufs_ihashcheck(ip->i_dev, ibase + (ipref << 3) + i) == 0) { 1369 ipref = (ipref << 3) + i; 1370 cgp->cg_irotor = (ipref + 1) % fs->fs_ipg; 1371 goto gotit; 1372 } 1373 ++icheckmiss; 1374 } 1375 } 1376 } 1377 1378 /* 1379 * Setup for the next byte, start at the beginning again if 1380 * we hit the end of the array. 1381 */ 1382 if (++ipref == arraysize) 1383 ipref = 0; 1384 --len; 1385 } 1386 if (icheckmiss == cgp->cg_cs.cs_nifree) { 1387 brelse(bp); 1388 return(0); 1389 } 1390 printf("fs = %s\n", fs->fs_fsmnt); 1391 panic("ffs_nodealloccg: block not in map, icheckmiss/nfree %d/%d", 1392 icheckmiss, cgp->cg_cs.cs_nifree); 1393 /* NOTREACHED */ 1394 1395 /* 1396 * ipref is a bit index as of the gotit label. 1397 */ 1398 gotit: 1399 KKASSERT(ipref >= 0 && ipref < fs->fs_ipg); 1400 if (icheckmiss) { 1401 printf("Warning: inode free race avoided %d times\n", 1402 icheckmiss); 1403 } 1404 bp->b_xflags |= BX_BKGRDWRITE; 1405 cgp->cg_time = time_second; 1406 if (DOINGSOFTDEP(ITOV(ip))) 1407 softdep_setup_inomapdep(bp, ip, ibase + ipref); 1408 setbit(inosused, ipref); 1409 cgp->cg_cs.cs_nifree--; 1410 fs->fs_cstotal.cs_nifree--; 1411 fs->fs_cs(fs, cg).cs_nifree--; 1412 fs->fs_fmod = 1; 1413 if ((mode & IFMT) == IFDIR) { 1414 cgp->cg_cs.cs_ndir++; 1415 fs->fs_cstotal.cs_ndir++; 1416 fs->fs_cs(fs, cg).cs_ndir++; 1417 } 1418 bdwrite(bp); 1419 return (ibase + ipref); 1420 } 1421 1422 /* 1423 * Free a block or fragment. 1424 * 1425 * The specified block or fragment is placed back in the 1426 * free map. If a fragment is deallocated, a possible 1427 * block reassembly is checked. 1428 */ 1429 void 1430 ffs_blkfree(struct inode *ip, ufs_daddr_t bno, long size) 1431 { 1432 struct fs *fs; 1433 struct cg *cgp; 1434 struct buf *bp; 1435 ufs_daddr_t blkno; 1436 int i, error, cg, blk, frags, bbase; 1437 uint8_t *blksfree; 1438 1439 fs = ip->i_fs; 1440 VOP_FREEBLKS(ip->i_devvp, fsbtodb(fs, bno), size); 1441 if ((uint)size > fs->fs_bsize || fragoff(fs, size) != 0 || 1442 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 1443 printf("dev=%s, bno = %ld, bsize = %ld, size = %ld, fs = %s\n", 1444 devtoname(ip->i_dev), (long)bno, (long)fs->fs_bsize, size, 1445 fs->fs_fsmnt); 1446 panic("ffs_blkfree: bad size"); 1447 } 1448 cg = dtog(fs, bno); 1449 if ((uint)bno >= fs->fs_size) { 1450 printf("bad block %ld, ino %lu\n", 1451 (long)bno, (u_long)ip->i_number); 1452 ffs_fserr(fs, ip->i_uid, "bad block"); 1453 return; 1454 } 1455 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1456 (int)fs->fs_cgsize, &bp); 1457 if (error) { 1458 brelse(bp); 1459 return; 1460 } 1461 cgp = (struct cg *)bp->b_data; 1462 if (!cg_chkmagic(cgp)) { 1463 brelse(bp); 1464 return; 1465 } 1466 bp->b_xflags |= BX_BKGRDWRITE; 1467 cgp->cg_time = time_second; 1468 bno = dtogd(fs, bno); 1469 blksfree = cg_blksfree(cgp); 1470 if (size == fs->fs_bsize) { 1471 blkno = fragstoblks(fs, bno); 1472 if (!ffs_isfreeblock(fs, blksfree, blkno)) { 1473 printf("dev = %s, block = %ld, fs = %s\n", 1474 devtoname(ip->i_dev), (long)bno, fs->fs_fsmnt); 1475 panic("ffs_blkfree: freeing free block"); 1476 } 1477 ffs_setblock(fs, blksfree, blkno); 1478 ffs_clusteracct(fs, cgp, blkno, 1); 1479 cgp->cg_cs.cs_nbfree++; 1480 fs->fs_cstotal.cs_nbfree++; 1481 fs->fs_cs(fs, cg).cs_nbfree++; 1482 i = cbtocylno(fs, bno); 1483 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 1484 cg_blktot(cgp)[i]++; 1485 } else { 1486 bbase = bno - fragnum(fs, bno); 1487 /* 1488 * decrement the counts associated with the old frags 1489 */ 1490 blk = blkmap(fs, blksfree, bbase); 1491 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 1492 /* 1493 * deallocate the fragment 1494 */ 1495 frags = numfrags(fs, size); 1496 for (i = 0; i < frags; i++) { 1497 if (isset(blksfree, bno + i)) { 1498 printf("dev = %s, block = %ld, fs = %s\n", 1499 devtoname(ip->i_dev), (long)(bno + i), 1500 fs->fs_fsmnt); 1501 panic("ffs_blkfree: freeing free frag"); 1502 } 1503 setbit(blksfree, bno + i); 1504 } 1505 cgp->cg_cs.cs_nffree += i; 1506 fs->fs_cstotal.cs_nffree += i; 1507 fs->fs_cs(fs, cg).cs_nffree += i; 1508 /* 1509 * add back in counts associated with the new frags 1510 */ 1511 blk = blkmap(fs, blksfree, bbase); 1512 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 1513 /* 1514 * if a complete block has been reassembled, account for it 1515 */ 1516 blkno = fragstoblks(fs, bbase); 1517 if (ffs_isblock(fs, blksfree, blkno)) { 1518 cgp->cg_cs.cs_nffree -= fs->fs_frag; 1519 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1520 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1521 ffs_clusteracct(fs, cgp, blkno, 1); 1522 cgp->cg_cs.cs_nbfree++; 1523 fs->fs_cstotal.cs_nbfree++; 1524 fs->fs_cs(fs, cg).cs_nbfree++; 1525 i = cbtocylno(fs, bbase); 1526 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 1527 cg_blktot(cgp)[i]++; 1528 } 1529 } 1530 fs->fs_fmod = 1; 1531 bdwrite(bp); 1532 } 1533 1534 #ifdef DIAGNOSTIC 1535 /* 1536 * Verify allocation of a block or fragment. Returns true if block or 1537 * fragment is allocated, false if it is free. 1538 */ 1539 static int 1540 ffs_checkblk(struct inode *ip, ufs_daddr_t bno, long size) 1541 { 1542 struct fs *fs; 1543 struct cg *cgp; 1544 struct buf *bp; 1545 int i, error, frags, free; 1546 uint8_t *blksfree; 1547 1548 fs = ip->i_fs; 1549 if ((uint)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1550 printf("bsize = %ld, size = %ld, fs = %s\n", 1551 (long)fs->fs_bsize, size, fs->fs_fsmnt); 1552 panic("ffs_checkblk: bad size"); 1553 } 1554 if ((uint)bno >= fs->fs_size) 1555 panic("ffs_checkblk: bad block %d", bno); 1556 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 1557 (int)fs->fs_cgsize, &bp); 1558 if (error) 1559 panic("ffs_checkblk: cg bread failed"); 1560 cgp = (struct cg *)bp->b_data; 1561 if (!cg_chkmagic(cgp)) 1562 panic("ffs_checkblk: cg magic mismatch"); 1563 bp->b_xflags |= BX_BKGRDWRITE; 1564 blksfree = cg_blksfree(cgp); 1565 bno = dtogd(fs, bno); 1566 if (size == fs->fs_bsize) { 1567 free = ffs_isblock(fs, blksfree, fragstoblks(fs, bno)); 1568 } else { 1569 frags = numfrags(fs, size); 1570 for (free = 0, i = 0; i < frags; i++) 1571 if (isset(blksfree, bno + i)) 1572 free++; 1573 if (free != 0 && free != frags) 1574 panic("ffs_checkblk: partially free fragment"); 1575 } 1576 brelse(bp); 1577 return (!free); 1578 } 1579 #endif /* DIAGNOSTIC */ 1580 1581 /* 1582 * Free an inode. 1583 */ 1584 int 1585 ffs_vfree(struct vnode *pvp, ino_t ino, int mode) 1586 { 1587 if (DOINGSOFTDEP(pvp)) { 1588 softdep_freefile(pvp, ino, mode); 1589 return (0); 1590 } 1591 return (ffs_freefile(pvp, ino, mode)); 1592 } 1593 1594 /* 1595 * Do the actual free operation. 1596 * The specified inode is placed back in the free map. 1597 */ 1598 int 1599 ffs_freefile(struct vnode *pvp, ino_t ino, int mode) 1600 { 1601 struct fs *fs; 1602 struct cg *cgp; 1603 struct inode *pip; 1604 struct buf *bp; 1605 int error, cg; 1606 uint8_t *inosused; 1607 1608 pip = VTOI(pvp); 1609 fs = pip->i_fs; 1610 if ((uint)ino >= fs->fs_ipg * fs->fs_ncg) 1611 panic("ffs_vfree: range: dev = (%d,%d), ino = %"PRId64", fs = %s", 1612 major(pip->i_dev), minor(pip->i_dev), ino, fs->fs_fsmnt); 1613 cg = ino_to_cg(fs, ino); 1614 error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1615 (int)fs->fs_cgsize, &bp); 1616 if (error) { 1617 brelse(bp); 1618 return (error); 1619 } 1620 cgp = (struct cg *)bp->b_data; 1621 if (!cg_chkmagic(cgp)) { 1622 brelse(bp); 1623 return (0); 1624 } 1625 bp->b_xflags |= BX_BKGRDWRITE; 1626 cgp->cg_time = time_second; 1627 inosused = cg_inosused(cgp); 1628 ino %= fs->fs_ipg; 1629 if (isclr(inosused, ino)) { 1630 printf("dev = %s, ino = %lu, fs = %s\n", 1631 devtoname(pip->i_dev), (u_long)ino, fs->fs_fsmnt); 1632 if (fs->fs_ronly == 0) 1633 panic("ffs_vfree: freeing free inode"); 1634 } 1635 clrbit(inosused, ino); 1636 if (ino < cgp->cg_irotor) 1637 cgp->cg_irotor = ino; 1638 cgp->cg_cs.cs_nifree++; 1639 fs->fs_cstotal.cs_nifree++; 1640 fs->fs_cs(fs, cg).cs_nifree++; 1641 if ((mode & IFMT) == IFDIR) { 1642 cgp->cg_cs.cs_ndir--; 1643 fs->fs_cstotal.cs_ndir--; 1644 fs->fs_cs(fs, cg).cs_ndir--; 1645 } 1646 fs->fs_fmod = 1; 1647 bdwrite(bp); 1648 return (0); 1649 } 1650 1651 /* 1652 * Find a block of the specified size in the specified cylinder group. 1653 * 1654 * It is a panic if a request is made to find a block if none are 1655 * available. 1656 */ 1657 static ufs_daddr_t 1658 ffs_mapsearch(struct fs *fs, struct cg *cgp, ufs_daddr_t bpref, int allocsiz) 1659 { 1660 ufs_daddr_t bno; 1661 int start, len, loc, i; 1662 int blk, field, subfield, pos; 1663 uint8_t *blksfree; 1664 1665 /* 1666 * find the fragment by searching through the free block 1667 * map for an appropriate bit pattern 1668 */ 1669 if (bpref) 1670 start = dtogd(fs, bpref) / NBBY; 1671 else 1672 start = cgp->cg_frotor / NBBY; 1673 blksfree = cg_blksfree(cgp); 1674 len = howmany(fs->fs_fpg, NBBY) - start; 1675 loc = scanc((uint)len, (u_char *)&blksfree[start], 1676 (u_char *)fragtbl[fs->fs_frag], 1677 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1678 if (loc == 0) { 1679 len = start + 1; 1680 start = 0; 1681 loc = scanc((uint)len, (u_char *)&blksfree[0], 1682 (u_char *)fragtbl[fs->fs_frag], 1683 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1684 if (loc == 0) { 1685 printf("start = %d, len = %d, fs = %s\n", 1686 start, len, fs->fs_fsmnt); 1687 panic("ffs_alloccg: map corrupted"); 1688 /* NOTREACHED */ 1689 } 1690 } 1691 bno = (start + len - loc) * NBBY; 1692 cgp->cg_frotor = bno; 1693 /* 1694 * found the byte in the map 1695 * sift through the bits to find the selected frag 1696 */ 1697 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1698 blk = blkmap(fs, blksfree, bno); 1699 blk <<= 1; 1700 field = around[allocsiz]; 1701 subfield = inside[allocsiz]; 1702 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1703 if ((blk & field) == subfield) 1704 return (bno + pos); 1705 field <<= 1; 1706 subfield <<= 1; 1707 } 1708 } 1709 printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 1710 panic("ffs_alloccg: block not in map"); 1711 return (-1); 1712 } 1713 1714 /* 1715 * Update the cluster map because of an allocation or free. 1716 * 1717 * Cnt == 1 means free; cnt == -1 means allocating. 1718 */ 1719 static void 1720 ffs_clusteracct(struct fs *fs, struct cg *cgp, ufs_daddr_t blkno, int cnt) 1721 { 1722 int32_t *sump; 1723 int32_t *lp; 1724 u_char *freemapp, *mapp; 1725 int i, start, end, forw, back, map, bit; 1726 1727 if (fs->fs_contigsumsize <= 0) 1728 return; 1729 freemapp = cg_clustersfree(cgp); 1730 sump = cg_clustersum(cgp); 1731 /* 1732 * Allocate or clear the actual block. 1733 */ 1734 if (cnt > 0) 1735 setbit(freemapp, blkno); 1736 else 1737 clrbit(freemapp, blkno); 1738 /* 1739 * Find the size of the cluster going forward. 1740 */ 1741 start = blkno + 1; 1742 end = start + fs->fs_contigsumsize; 1743 if (end >= cgp->cg_nclusterblks) 1744 end = cgp->cg_nclusterblks; 1745 mapp = &freemapp[start / NBBY]; 1746 map = *mapp++; 1747 bit = 1 << (start % NBBY); 1748 for (i = start; i < end; i++) { 1749 if ((map & bit) == 0) 1750 break; 1751 if ((i & (NBBY - 1)) != (NBBY - 1)) { 1752 bit <<= 1; 1753 } else { 1754 map = *mapp++; 1755 bit = 1; 1756 } 1757 } 1758 forw = i - start; 1759 /* 1760 * Find the size of the cluster going backward. 1761 */ 1762 start = blkno - 1; 1763 end = start - fs->fs_contigsumsize; 1764 if (end < 0) 1765 end = -1; 1766 mapp = &freemapp[start / NBBY]; 1767 map = *mapp--; 1768 bit = 1 << (start % NBBY); 1769 for (i = start; i > end; i--) { 1770 if ((map & bit) == 0) 1771 break; 1772 if ((i & (NBBY - 1)) != 0) { 1773 bit >>= 1; 1774 } else { 1775 map = *mapp--; 1776 bit = 1 << (NBBY - 1); 1777 } 1778 } 1779 back = start - i; 1780 /* 1781 * Account for old cluster and the possibly new forward and 1782 * back clusters. 1783 */ 1784 i = back + forw + 1; 1785 if (i > fs->fs_contigsumsize) 1786 i = fs->fs_contigsumsize; 1787 sump[i] += cnt; 1788 if (back > 0) 1789 sump[back] -= cnt; 1790 if (forw > 0) 1791 sump[forw] -= cnt; 1792 /* 1793 * Update cluster summary information. 1794 */ 1795 lp = &sump[fs->fs_contigsumsize]; 1796 for (i = fs->fs_contigsumsize; i > 0; i--) 1797 if (*lp-- > 0) 1798 break; 1799 fs->fs_maxcluster[cgp->cg_cgx] = i; 1800 } 1801 1802 /* 1803 * Fserr prints the name of a filesystem with an error diagnostic. 1804 * 1805 * The form of the error message is: 1806 * fs: error message 1807 */ 1808 static void 1809 ffs_fserr(struct fs *fs, uint uid, char *cp) 1810 { 1811 struct thread *td = curthread; 1812 struct proc *p; 1813 1814 if ((p = td->td_proc) != NULL) { 1815 log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1, 1816 p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp); 1817 } else { 1818 log(LOG_ERR, "system thread %p, uid %d on %s: %s\n", 1819 td, uid, fs->fs_fsmnt, cp); 1820 } 1821 } 1822