| 1 | /* |
| 2 | * Copyright (c) 1991 Regents of the University of California. |
| 3 | * All rights reserved. |
| 4 | * |
| 5 | * %sccs.include.redist.c% |
| 6 | * |
| 7 | * @(#)lfs_segment.c 7.11 (Berkeley) %G% |
| 8 | */ |
| 9 | |
| 10 | #include <sys/param.h> |
| 11 | #include <sys/systm.h> |
| 12 | #include <sys/namei.h> |
| 13 | #include <sys/kernel.h> |
| 14 | #include <sys/resourcevar.h> |
| 15 | #include <sys/file.h> |
| 16 | #include <sys/stat.h> |
| 17 | #include <sys/buf.h> |
| 18 | #include <sys/proc.h> |
| 19 | #include <sys/conf.h> |
| 20 | #include <sys/vnode.h> |
| 21 | #include <sys/specdev.h> |
| 22 | #include <sys/fifo.h> |
| 23 | #include <sys/malloc.h> |
| 24 | #include <sys/mount.h> |
| 25 | |
| 26 | #include <ufs/ufs/quota.h> |
| 27 | #include <ufs/ufs/inode.h> |
| 28 | #include <ufs/ufs/dir.h> |
| 29 | #include <ufs/ufs/ufsmount.h> |
| 30 | |
| 31 | #include <ufs/lfs/lfs.h> |
| 32 | #include <ufs/lfs/lfs_extern.h> |
| 33 | |
| 34 | /* In-memory description of a segment about to be written. */ |
| 35 | struct segment { |
| 36 | struct buf **bpp; /* pointer to buffer array */ |
| 37 | struct buf **cbpp; /* pointer to next available bp */ |
| 38 | struct buf *ibp; /* buffer pointer to inode page */ |
| 39 | struct finfo *fip; /* current fileinfo pointer */ |
| 40 | void *segsum; /* segment summary info */ |
| 41 | u_long ninodes; /* number of inodes in this segment */ |
| 42 | u_long seg_bytes_left; /* bytes left in segment */ |
| 43 | u_long sum_bytes_left; /* bytes left in summary block */ |
| 44 | u_long seg_number; /* number of this segment */ |
| 45 | #define SEGM_CKP 0x01 /* doing a checkpoint */ |
| 46 | u_long seg_flags; /* run-time flags for this segment */ |
| 47 | }; |
| 48 | |
| 49 | /* |
| 50 | * Determine if it's OK to start a partial in this segment, or if we need |
| 51 | * to go on to a new segment. |
| 52 | */ |
| 53 | #define LFS_PARTIAL_FITS(fs) \ |
| 54 | ((fs)->lfs_dbpseg - ((fs)->lfs_offset - (fs)->lfs_curseg) > \ |
| 55 | 1 << (fs)->lfs_fsbtodb) |
| 56 | |
| 57 | int lfs_callback __P((struct buf *)); |
| 58 | void lfs_gather __P((struct lfs *, struct segment *, |
| 59 | struct vnode *, int (*) __P((struct lfs *, struct buf *)))); |
| 60 | void lfs_initseg __P((struct lfs *, struct segment *)); |
| 61 | void lfs_iset __P((struct inode *, daddr_t, time_t)); |
| 62 | int lfs_match_data __P((struct lfs *, struct buf *)); |
| 63 | int lfs_match_dindir __P((struct lfs *, struct buf *)); |
| 64 | int lfs_match_indir __P((struct lfs *, struct buf *)); |
| 65 | int lfs_match_tindir __P((struct lfs *, struct buf *)); |
| 66 | struct buf * |
| 67 | lfs_newbuf __P((struct lfs *, struct segment *, daddr_t, size_t)); |
| 68 | void lfs_newseg __P((struct lfs *)); |
| 69 | void lfs_shellsort __P((struct buf **, daddr_t *, register int)); |
| 70 | void lfs_updatemeta __P((struct lfs *, |
| 71 | struct segment *, struct vnode *, daddr_t *, struct buf **, int)); |
| 72 | void lfs_writefile __P((struct lfs *, struct segment *, struct vnode *)); |
| 73 | void lfs_writeinode __P((struct lfs *, struct segment *, struct inode *)); |
| 74 | void lfs_writeseg __P((struct lfs *, struct segment *)); |
| 75 | void lfs_writesuper __P((struct lfs *, struct segment *)); |
| 76 | |
| 77 | int lfs_allclean_wakeup; /* Cleaner wakeup address. */ |
| 78 | |
| 79 | /* |
| 80 | * Ifile and meta data blocks are not marked busy, so segment writes MUST be |
| 81 | * single threaded. Currently, there are two paths into lfs_segwrite, sync() |
| 82 | * and getnewbuf(). They both mark the file system busy. Lfs_vflush() |
| 83 | * explicitly marks the file system busy. So lfs_segwrite is safe. I think. |
| 84 | */ |
| 85 | |
| 86 | int |
| 87 | lfs_vflush(vp) |
| 88 | struct vnode *vp; |
| 89 | { |
| 90 | struct inode *ip; |
| 91 | struct lfs *fs; |
| 92 | struct mount *mp; |
| 93 | struct segment *sp; |
| 94 | int error, s; |
| 95 | |
| 96 | #ifdef VERBOSE |
| 97 | printf("lfs_vflush\n"); |
| 98 | #endif |
| 99 | mp = vp->v_mount; |
| 100 | fs = VFSTOUFS(mp)->um_lfs; |
| 101 | |
| 102 | /* |
| 103 | * XXX |
| 104 | * check flags? |
| 105 | * mp->mnt_flag & (MNT_MLOCK|MNT_RDONLY|MNT_MPBUSY) || |
| 106 | */ |
| 107 | if (vfs_busy(mp)) |
| 108 | return (0); |
| 109 | |
| 110 | /* |
| 111 | * Allocate a segment structure and enough space to hold pointers to |
| 112 | * the maximum possible number of buffers which can be described in a |
| 113 | * single summary block. |
| 114 | */ |
| 115 | sp = malloc(sizeof(struct segment), M_SEGMENT, M_WAITOK); |
| 116 | sp->bpp = malloc(((LFS_SUMMARY_SIZE - sizeof(SEGSUM)) / |
| 117 | sizeof(daddr_t) + 1) * sizeof(struct buf *), M_SEGMENT, M_WAITOK); |
| 118 | sp->seg_flags = SEGM_CKP; |
| 119 | lfs_initseg(fs, sp); |
| 120 | |
| 121 | /* |
| 122 | * Keep a cumulative count of the outstanding I/O operations. If the |
| 123 | * disk drive catches up with us it could go to zero before we finish, |
| 124 | * so we artificially increment it by one until we've scheduled all of |
| 125 | * the writes we intend to do. |
| 126 | */ |
| 127 | s = splbio(); |
| 128 | fs->lfs_iocount = 1; |
| 129 | splx(s); |
| 130 | |
| 131 | if (vp->v_dirtyblkhd != NULL) |
| 132 | lfs_writefile(fs, sp, vp); |
| 133 | ip = VTOI(vp); |
| 134 | lfs_writeinode(fs, sp, ip); |
| 135 | ip->i_flags &= ~(IMOD | IACC | IUPD | ICHG); |
| 136 | |
| 137 | lfs_writeseg(fs, sp); |
| 138 | |
| 139 | /* |
| 140 | * If the I/O count is non-zero, sleep until it reaches zero. At the |
| 141 | * moment, the user's process hangs around so we can sleep. |
| 142 | */ |
| 143 | s = splbio(); |
| 144 | if (--fs->lfs_iocount && (error = |
| 145 | tsleep((caddr_t)&fs->lfs_iocount, PRIBIO + 1, "lfs vflush", 0))) |
| 146 | return (error); |
| 147 | splx(s); |
| 148 | vfs_unbusy(mp); |
| 149 | |
| 150 | free(sp->bpp, M_SEGMENT); |
| 151 | free(sp, M_SEGMENT); |
| 152 | |
| 153 | return (0); |
| 154 | } |
| 155 | |
| 156 | int |
| 157 | lfs_segwrite(mp, do_ckp) |
| 158 | struct mount *mp; |
| 159 | int do_ckp; /* Do a checkpoint. */ |
| 160 | { |
| 161 | struct inode *ip; |
| 162 | struct lfs *fs; |
| 163 | struct segment *sp; |
| 164 | struct vnode *vp; |
| 165 | int error, islocked, s; |
| 166 | |
| 167 | #ifdef VERBOSE |
| 168 | printf("lfs_segwrite\n"); |
| 169 | #endif |
| 170 | fs = VFSTOUFS(mp)->um_lfs; |
| 171 | |
| 172 | /* |
| 173 | * Allocate a segment structure and enough space to hold pointers to |
| 174 | * the maximum possible number of buffers which can be described in a |
| 175 | * single summary block. |
| 176 | */ |
| 177 | sp = malloc(sizeof(struct segment), M_SEGMENT, M_WAITOK); |
| 178 | sp->bpp = malloc(((LFS_SUMMARY_SIZE - sizeof(SEGSUM)) / |
| 179 | sizeof(daddr_t) + 1) * sizeof(struct buf *), M_SEGMENT, M_WAITOK); |
| 180 | sp->seg_flags = do_ckp ? SEGM_CKP : 0; |
| 181 | lfs_initseg(fs, sp); |
| 182 | |
| 183 | /* |
| 184 | * If doing a checkpoint, we keep a cumulative count of the outstanding |
| 185 | * I/O operations. If the disk drive catches up with us it could go to |
| 186 | * zero before we finish, so we artificially increment it by one until |
| 187 | * we've scheduled all of the writes we intend to do. |
| 188 | */ |
| 189 | if (do_ckp) { |
| 190 | s = splbio(); |
| 191 | fs->lfs_iocount = 1; |
| 192 | splx(s); |
| 193 | } |
| 194 | |
| 195 | loop: for (vp = mp->mnt_mounth; vp; vp = vp->v_mountf) { |
| 196 | /* |
| 197 | * If the vnode that we are about to sync is no longer |
| 198 | * associated with this mount point, start over. |
| 199 | */ |
| 200 | if (vp->v_mount != mp) |
| 201 | goto loop; |
| 202 | |
| 203 | islocked = VOP_ISLOCKED(vp); |
| 204 | |
| 205 | /* |
| 206 | * XXX |
| 207 | * This is wrong, I think -- we should just wait until we |
| 208 | * get the vnode and go on. Probably going to reschedule |
| 209 | * all of the writes we already scheduled... |
| 210 | */ |
| 211 | if (islocked) |
| 212 | VREF(vp); |
| 213 | else if (vget(vp)) |
| 214 | { |
| 215 | printf("lfs_segment: failed to get vnode (tell Keith)!\n"); |
| 216 | goto loop; |
| 217 | } |
| 218 | /* |
| 219 | * Write the inode/file if dirty and it's not the |
| 220 | * the IFILE. |
| 221 | */ |
| 222 | ip = VTOI(vp); |
| 223 | if ((ip->i_flag & (IMOD | IACC | IUPD | ICHG) || |
| 224 | vp->v_dirtyblkhd != NULL) && |
| 225 | ip->i_number != LFS_IFILE_INUM) { |
| 226 | if (vp->v_dirtyblkhd != NULL) |
| 227 | lfs_writefile(fs, sp, vp); |
| 228 | lfs_writeinode(fs, sp, ip); |
| 229 | ip->i_flags &= ~(IMOD | IACC | IUPD | ICHG); |
| 230 | } |
| 231 | if (islocked) |
| 232 | vrele(vp); |
| 233 | else |
| 234 | vput(vp); |
| 235 | } |
| 236 | if (do_ckp) { |
| 237 | vp = fs->lfs_ivnode; |
| 238 | while (vget(vp)); |
| 239 | ip = VTOI(vp); |
| 240 | if (vp->v_dirtyblkhd != NULL) |
| 241 | lfs_writefile(fs, sp, vp); |
| 242 | lfs_writeinode(fs, sp, ip); |
| 243 | ip->i_flags &= ~(IMOD | IACC | IUPD | ICHG); |
| 244 | vput(vp); |
| 245 | } |
| 246 | lfs_writeseg(fs, sp); |
| 247 | |
| 248 | /* |
| 249 | * If the I/O count is non-zero, sleep until it reaches zero. At the |
| 250 | * moment, the user's process hangs around so we can sleep. |
| 251 | */ |
| 252 | if (do_ckp) { |
| 253 | s = splbio(); |
| 254 | if (--fs->lfs_iocount && |
| 255 | (error = tsleep((caddr_t)&fs->lfs_iocount, PRIBIO + 1, |
| 256 | "lfs sync", 0))) |
| 257 | return (error); |
| 258 | splx(s); |
| 259 | lfs_writesuper(fs, sp); |
| 260 | } |
| 261 | |
| 262 | free(sp->bpp, M_SEGMENT); |
| 263 | free(sp, M_SEGMENT); |
| 264 | |
| 265 | /* Wake up any cleaning processes waiting on this file system. */ |
| 266 | wakeup((caddr_t)&fs->lfs_nextseg); |
| 267 | wakeup((caddr_t)&lfs_allclean_wakeup); |
| 268 | |
| 269 | return (0); |
| 270 | } |
| 271 | |
| 272 | /* |
| 273 | * Write the dirty blocks associated with a vnode. |
| 274 | */ |
| 275 | void |
| 276 | lfs_writefile(fs, sp, vp) |
| 277 | struct lfs *fs; |
| 278 | struct segment *sp; |
| 279 | struct vnode *vp; |
| 280 | { |
| 281 | struct buf *bp; |
| 282 | struct finfo *fip; |
| 283 | IFILE *ifp; |
| 284 | |
| 285 | #ifdef VERBOSE |
| 286 | printf("lfs_writefile\n"); |
| 287 | #endif |
| 288 | if (sp->seg_bytes_left < fs->lfs_bsize || |
| 289 | sp->sum_bytes_left < sizeof(struct finfo)) { |
| 290 | lfs_writeseg(fs, sp); |
| 291 | lfs_initseg(fs, sp); |
| 292 | } |
| 293 | sp->sum_bytes_left -= sizeof(struct finfo) - sizeof(daddr_t); |
| 294 | |
| 295 | fip = sp->fip; |
| 296 | fip->fi_nblocks = 0; |
| 297 | fip->fi_ino = VTOI(vp)->i_number; |
| 298 | LFS_IENTRY(ifp, fs, fip->fi_ino, bp); |
| 299 | fip->fi_version = ifp->if_version; |
| 300 | brelse(bp); |
| 301 | |
| 302 | /* |
| 303 | * It may not be necessary to write the meta-data blocks at this point, |
| 304 | * as the roll-forward recovery code should be able to reconstruct the |
| 305 | * list. |
| 306 | */ |
| 307 | lfs_gather(fs, sp, vp, lfs_match_data); |
| 308 | lfs_gather(fs, sp, vp, lfs_match_indir); |
| 309 | lfs_gather(fs, sp, vp, lfs_match_dindir); |
| 310 | #ifdef TRIPLE |
| 311 | lfs_gather(fs, sp, vp, lfs_match_tindir); |
| 312 | #endif |
| 313 | |
| 314 | fip = sp->fip; |
| 315 | #ifdef META |
| 316 | printf("lfs_writefile: adding %d blocks\n", fip->fi_nblocks); |
| 317 | #endif |
| 318 | if (fip->fi_nblocks != 0) { |
| 319 | ++((SEGSUM *)(sp->segsum))->ss_nfinfo; |
| 320 | sp->fip = |
| 321 | (struct finfo *)((caddr_t)fip + sizeof(struct finfo) + |
| 322 | sizeof(daddr_t) * (fip->fi_nblocks - 1)); |
| 323 | } |
| 324 | } |
| 325 | |
| 326 | void |
| 327 | lfs_writeinode(fs, sp, ip) |
| 328 | struct lfs *fs; |
| 329 | struct segment *sp; |
| 330 | struct inode *ip; |
| 331 | { |
| 332 | struct buf *bp, *ibp; |
| 333 | IFILE *ifp; |
| 334 | daddr_t next_addr; |
| 335 | ino_t ino; |
| 336 | int ndx; |
| 337 | |
| 338 | #ifdef VERBOSE |
| 339 | printf("lfs_writeinode\n"); |
| 340 | #endif |
| 341 | /* Allocate a new inode block if necessary. */ |
| 342 | if (sp->ibp == NULL) { |
| 343 | /* Allocate a new segment if necessary. */ |
| 344 | if (sp->seg_bytes_left < fs->lfs_bsize || |
| 345 | sp->sum_bytes_left < sizeof(daddr_t)) { |
| 346 | lfs_writeseg(fs, sp); |
| 347 | lfs_initseg(fs, sp); |
| 348 | } |
| 349 | |
| 350 | /* Get next inode block. */ |
| 351 | next_addr = fs->lfs_offset; |
| 352 | fs->lfs_offset += fsbtodb(fs, 1); |
| 353 | sp->ibp = *sp->cbpp++ = |
| 354 | lfs_newbuf(fs, sp, next_addr, fs->lfs_bsize); |
| 355 | |
| 356 | /* Set remaining space counter. */ |
| 357 | sp->seg_bytes_left -= fs->lfs_bsize; |
| 358 | sp->sum_bytes_left -= sizeof(daddr_t); |
| 359 | ndx = LFS_SUMMARY_SIZE / sizeof(daddr_t) - |
| 360 | sp->ninodes / INOPB(fs) - 1; |
| 361 | ((daddr_t *)(sp->segsum))[ndx] = next_addr; |
| 362 | } |
| 363 | |
| 364 | /* Update the inode times and copy the inode onto the inode page. */ |
| 365 | ITIMES(ip, &time, &time); |
| 366 | bp = sp->ibp; |
| 367 | bp->b_un.b_dino[sp->ninodes % INOPB(fs)] = ip->i_din; |
| 368 | |
| 369 | /* Increment inode count in segment summary block. */ |
| 370 | ++((SEGSUM *)(sp->segsum))->ss_ninos; |
| 371 | |
| 372 | /* If this page is full, set flag to allocate a new page. */ |
| 373 | if (++sp->ninodes % INOPB(fs) == 0) |
| 374 | sp->ibp = NULL; |
| 375 | |
| 376 | /* |
| 377 | * If updating the ifile, update the super-block. Update the disk |
| 378 | * address and access times for this inode in the ifile. |
| 379 | */ |
| 380 | ino = ip->i_number; |
| 381 | if (ino == LFS_IFILE_INUM) |
| 382 | fs->lfs_idaddr = bp->b_blkno; |
| 383 | |
| 384 | LFS_IENTRY(ifp, fs, ino, ibp); |
| 385 | ifp->if_daddr = bp->b_blkno; |
| 386 | LFS_UBWRITE(ibp); |
| 387 | } |
| 388 | |
| 389 | void |
| 390 | lfs_gather(fs, sp, vp, match) |
| 391 | struct lfs *fs; |
| 392 | struct segment *sp; |
| 393 | struct vnode *vp; |
| 394 | int (*match) __P((struct lfs *, struct buf *)); |
| 395 | { |
| 396 | struct buf **bpp, *bp, *nbp; |
| 397 | struct finfo *fip; |
| 398 | struct inode *ip; |
| 399 | daddr_t *lbp, *start_lbp; |
| 400 | u_long version; |
| 401 | int s; |
| 402 | |
| 403 | #ifdef VERBOSE |
| 404 | printf("lfs_gather\n"); |
| 405 | #endif |
| 406 | ip = VTOI(vp); |
| 407 | bpp = sp->cbpp; |
| 408 | fip = sp->fip; |
| 409 | start_lbp = lbp = &fip->fi_blocks[fip->fi_nblocks]; |
| 410 | |
| 411 | s = splbio(); |
| 412 | for (bp = vp->v_dirtyblkhd; bp; bp = nbp) { |
| 413 | nbp = bp->b_blockf; |
| 414 | /* |
| 415 | * XXX |
| 416 | * Should probably sleep on any BUSY buffer if |
| 417 | * doing an fsync? |
| 418 | */ |
| 419 | if (bp->b_flags & B_BUSY || !match(fs, bp)) |
| 420 | continue; |
| 421 | |
| 422 | #ifdef DIAGNOSTIC |
| 423 | if (!(bp->b_flags & B_DELWRI)) |
| 424 | panic("lfs_gather: bp not B_DELWRI"); |
| 425 | if (!(bp->b_flags & B_LOCKED)) |
| 426 | panic("lfs_gather: bp not B_LOCKED"); |
| 427 | #endif |
| 428 | /* Insert into the buffer list, update the FINFO block. */ |
| 429 | *sp->cbpp++ = bp; |
| 430 | ++fip->fi_nblocks; |
| 431 | *lbp++ = bp->b_lblkno; |
| 432 | |
| 433 | /* |
| 434 | * If full, finish this segment. We may be doing I/O, so |
| 435 | * release and reacquire the splbio(). |
| 436 | */ |
| 437 | sp->sum_bytes_left -= sizeof(daddr_t); |
| 438 | sp->seg_bytes_left -= bp->b_bufsize; |
| 439 | if (sp->sum_bytes_left < sizeof(daddr_t) || |
| 440 | sp->seg_bytes_left < fs->lfs_bsize) { |
| 441 | splx(s); |
| 442 | lfs_updatemeta(fs, |
| 443 | sp, vp, start_lbp, bpp, lbp - start_lbp); |
| 444 | |
| 445 | /* Add the current file to the segment summary. */ |
| 446 | ++((SEGSUM *)(sp->segsum))->ss_nfinfo; |
| 447 | |
| 448 | version = fip->fi_version; |
| 449 | lfs_writeseg(fs, sp); |
| 450 | lfs_initseg(fs, sp); |
| 451 | |
| 452 | fip = sp->fip; |
| 453 | fip->fi_version = version; |
| 454 | fip->fi_ino = ip->i_number; |
| 455 | start_lbp = lbp = fip->fi_blocks; |
| 456 | |
| 457 | bpp = sp->cbpp; |
| 458 | s = splbio(); |
| 459 | } |
| 460 | } |
| 461 | splx(s); |
| 462 | lfs_updatemeta(fs, sp, vp, start_lbp, bpp, lbp - start_lbp); |
| 463 | } |
| 464 | |
| 465 | /* |
| 466 | * Update the metadata that points to the blocks listed in the FINFO |
| 467 | * array. |
| 468 | */ |
| 469 | void |
| 470 | lfs_updatemeta(fs, sp, vp, lbp, bpp, nblocks) |
| 471 | struct lfs *fs; |
| 472 | struct segment *sp; |
| 473 | struct vnode *vp; |
| 474 | daddr_t *lbp; |
| 475 | struct buf **bpp; |
| 476 | int nblocks; |
| 477 | { |
| 478 | SEGUSE *sup; |
| 479 | struct buf *bp; |
| 480 | INDIR a[NIADDR], *ap; |
| 481 | struct inode *ip; |
| 482 | daddr_t daddr, lbn, off; |
| 483 | int db_per_fsb, error, i, num; |
| 484 | |
| 485 | #ifdef VERBOSE |
| 486 | printf("lfs_updatemeta\n"); |
| 487 | #endif |
| 488 | if (nblocks == 0) |
| 489 | return; |
| 490 | |
| 491 | /* Sort the blocks. */ |
| 492 | lfs_shellsort(bpp, lbp, nblocks); |
| 493 | |
| 494 | /* |
| 495 | * Assign disk addresses, and update references to the logical |
| 496 | * block and the segment usage information. |
| 497 | */ |
| 498 | db_per_fsb = fsbtodb(fs, 1); |
| 499 | for (i = nblocks; i--; ++bpp) { |
| 500 | lbn = *lbp++; |
| 501 | (*bpp)->b_blkno = off = fs->lfs_offset; |
| 502 | fs->lfs_offset += db_per_fsb; |
| 503 | |
| 504 | if (error = lfs_bmaparray(vp, lbn, &daddr, a, &num)) |
| 505 | panic("lfs_updatemeta: lfs_bmaparray %d", error); |
| 506 | ip = VTOI(vp); |
| 507 | switch (num) { |
| 508 | case 0: |
| 509 | ip->i_db[lbn] = off; |
| 510 | break; |
| 511 | case 1: |
| 512 | ip->i_ib[a[0].in_off] = off; |
| 513 | break; |
| 514 | default: |
| 515 | ap = &a[num - 1]; |
| 516 | if (bread(vp, ap->in_lbn, fs->lfs_bsize, NOCRED, &bp)) |
| 517 | panic("lfs_updatemeta: bread bno %d", |
| 518 | ap->in_lbn); |
| 519 | bp->b_un.b_daddr[ap->in_off] = off; |
| 520 | lfs_bwrite(bp); |
| 521 | } |
| 522 | |
| 523 | /* Update segment usage information. */ |
| 524 | if (daddr != UNASSIGNED) { |
| 525 | LFS_SEGENTRY(sup, fs, datosn(fs, daddr), bp); |
| 526 | sup->su_lastmod = time.tv_sec; |
| 527 | #ifdef DIAGNOSTIC |
| 528 | if (sup->su_nbytes < fs->lfs_bsize) |
| 529 | panic("lfs: negative bytes (segment %d)\n", |
| 530 | datosn(fs, daddr)); |
| 531 | #endif |
| 532 | sup->su_nbytes -= fs->lfs_bsize; |
| 533 | LFS_UBWRITE(bp); |
| 534 | } |
| 535 | } |
| 536 | } |
| 537 | |
| 538 | /* |
| 539 | * Start a new segment. |
| 540 | */ |
| 541 | void |
| 542 | lfs_initseg(fs, sp) |
| 543 | struct lfs *fs; |
| 544 | struct segment *sp; |
| 545 | { |
| 546 | SEGUSE *sup; |
| 547 | SEGSUM *ssp; |
| 548 | struct buf *bp; |
| 549 | daddr_t lbn, *lbnp; |
| 550 | |
| 551 | #ifdef VERBOSE |
| 552 | printf("lfs_initseg\n"); |
| 553 | #endif |
| 554 | /* Advance to the next segment. */ |
| 555 | if (!LFS_PARTIAL_FITS(fs)) { |
| 556 | lfs_newseg(fs); |
| 557 | fs->lfs_offset = fs->lfs_curseg; |
| 558 | sp->seg_number = datosn(fs, fs->lfs_curseg); |
| 559 | sp->seg_bytes_left = fs->lfs_dbpseg * DEV_BSIZE; |
| 560 | |
| 561 | /* |
| 562 | * If the segment contains a superblock, update the offset |
| 563 | * and summary address to skip over it. |
| 564 | */ |
| 565 | LFS_SEGENTRY(sup, fs, sp->seg_number, bp); |
| 566 | if (sup->su_flags & SEGUSE_SUPERBLOCK) { |
| 567 | fs->lfs_offset += LFS_SBPAD / DEV_BSIZE; |
| 568 | sp->seg_bytes_left -= LFS_SBPAD; |
| 569 | } |
| 570 | brelse(bp); |
| 571 | } else { |
| 572 | sp->seg_number = datosn(fs, fs->lfs_curseg); |
| 573 | sp->seg_bytes_left = (fs->lfs_dbpseg - |
| 574 | (fs->lfs_offset - fs->lfs_curseg)) * DEV_BSIZE; |
| 575 | } |
| 576 | |
| 577 | sp->ibp = NULL; |
| 578 | sp->ninodes = 0; |
| 579 | |
| 580 | /* Get a new buffer for SEGSUM and enter it into the buffer list. */ |
| 581 | sp->cbpp = sp->bpp; |
| 582 | *sp->cbpp = lfs_newbuf(fs, sp, fs->lfs_offset, LFS_SUMMARY_SIZE); |
| 583 | sp->segsum = (*sp->cbpp)->b_un.b_addr; |
| 584 | ++sp->cbpp; |
| 585 | fs->lfs_offset += LFS_SUMMARY_SIZE / DEV_BSIZE; |
| 586 | |
| 587 | /* Set point to SEGSUM, initialize it. */ |
| 588 | ssp = sp->segsum; |
| 589 | ssp->ss_next = fs->lfs_nextseg; |
| 590 | ssp->ss_nfinfo = ssp->ss_ninos = 0; |
| 591 | |
| 592 | /* Set pointer to first FINFO, initialize it. */ |
| 593 | sp->fip = (struct finfo *)(sp->segsum + sizeof(SEGSUM)); |
| 594 | sp->fip->fi_nblocks = 0; |
| 595 | |
| 596 | sp->seg_bytes_left -= LFS_SUMMARY_SIZE; |
| 597 | sp->sum_bytes_left = LFS_SUMMARY_SIZE - sizeof(SEGSUM); |
| 598 | } |
| 599 | |
| 600 | /* |
| 601 | * Return the next segment to write. |
| 602 | */ |
| 603 | void |
| 604 | lfs_newseg(fs) |
| 605 | struct lfs *fs; |
| 606 | { |
| 607 | CLEANERINFO *cip; |
| 608 | SEGUSE *sup; |
| 609 | struct buf *bp; |
| 610 | int curseg, isdirty, sn; |
| 611 | |
| 612 | #ifdef VERBOSE |
| 613 | printf("lfs_newseg\n"); |
| 614 | #endif |
| 615 | /* |
| 616 | * Turn off the active bit for the current segment, turn on the |
| 617 | * active and dirty bits for the next segment, update the cleaner |
| 618 | * info. Set the current segment to the next segment, get a new |
| 619 | * next segment. |
| 620 | */ |
| 621 | LFS_SEGENTRY(sup, fs, datosn(fs, fs->lfs_curseg), bp); |
| 622 | sup->su_flags &= ~SEGUSE_ACTIVE; |
| 623 | LFS_UBWRITE(bp); |
| 624 | |
| 625 | LFS_SEGENTRY(sup, fs, datosn(fs, fs->lfs_nextseg), bp); |
| 626 | sup->su_flags |= SEGUSE_ACTIVE | SEGUSE_DIRTY; |
| 627 | LFS_UBWRITE(bp); |
| 628 | |
| 629 | LFS_CLEANERINFO(cip, fs, bp); |
| 630 | --cip->clean; |
| 631 | ++cip->dirty; |
| 632 | LFS_UBWRITE(bp); |
| 633 | |
| 634 | fs->lfs_lastseg = fs->lfs_curseg; |
| 635 | fs->lfs_curseg = fs->lfs_nextseg; |
| 636 | for (sn = curseg = datosn(fs, fs->lfs_curseg);;) { |
| 637 | sn = (sn + 1) % fs->lfs_nseg; |
| 638 | if (sn == curseg) |
| 639 | panic("lfs_nextseg: no clean segments"); |
| 640 | LFS_SEGENTRY(sup, fs, sn, bp); |
| 641 | isdirty = sup->su_flags & SEGUSE_DIRTY; |
| 642 | brelse(bp); |
| 643 | if (!isdirty) |
| 644 | break; |
| 645 | } |
| 646 | fs->lfs_nextseg = sntoda(fs, sn); |
| 647 | } |
| 648 | |
| 649 | void |
| 650 | lfs_writeseg(fs, sp) |
| 651 | struct lfs *fs; |
| 652 | struct segment *sp; |
| 653 | { |
| 654 | struct buf **bpp, *bp; |
| 655 | SEGUSE *sup; |
| 656 | SEGSUM *ssp; |
| 657 | dev_t i_dev; |
| 658 | u_long *datap, *dp; |
| 659 | void *pmeta; |
| 660 | int flags, i, nblocks, s, (*strategy)__P((struct buf *)); |
| 661 | |
| 662 | #ifdef VERBOSE |
| 663 | printf("lfs_writeseg\n"); |
| 664 | #endif |
| 665 | if ((nblocks = sp->cbpp - sp->bpp) == 0) |
| 666 | return; |
| 667 | |
| 668 | /* Update the segment usage information. */ |
| 669 | LFS_SEGENTRY(sup, fs, sp->seg_number, bp); |
| 670 | sup->su_nbytes += nblocks - 1 << fs->lfs_bshift; |
| 671 | sup->su_lastmod = time.tv_sec; |
| 672 | LFS_UBWRITE(bp); |
| 673 | |
| 674 | /* |
| 675 | * Compute checksum across data and then across summary; the first |
| 676 | * block (the summary block) is skipped. Set the create time here |
| 677 | * so that it's guaranteed to be later than the inode mod times. |
| 678 | * |
| 679 | * XXX |
| 680 | * Fix this to do it inline, instead of malloc/copy. |
| 681 | */ |
| 682 | datap = dp = malloc(nblocks * sizeof(u_long), M_SEGMENT, M_WAITOK); |
| 683 | for (bpp = sp->bpp, i = nblocks - 1; i--;) |
| 684 | *dp++ = (*++bpp)->b_un.b_words[0]; |
| 685 | ssp = (SEGSUM *)sp->segsum; |
| 686 | ssp->ss_create = time.tv_sec; |
| 687 | ssp->ss_datasum = cksum(datap, nblocks * sizeof(u_long)); |
| 688 | ssp->ss_sumsum = |
| 689 | cksum(&ssp->ss_datasum, LFS_SUMMARY_SIZE - sizeof(ssp->ss_sumsum)); |
| 690 | free(datap, M_SEGMENT); |
| 691 | |
| 692 | /* |
| 693 | * When we gathered the blocks for I/O we did not mark them busy or |
| 694 | * remove them from the freelist. As we do this, turn off the B_LOCKED |
| 695 | * bit so the future brelse will put them on the LRU list, and add the |
| 696 | * B_CALL flags if we're doing a checkpoint so we can count I/O's. LFS |
| 697 | * requires that the super blocks (on checkpoint) be written after all |
| 698 | * the segment data. |
| 699 | */ |
| 700 | i_dev = VTOI(fs->lfs_ivnode)->i_dev; |
| 701 | strategy = VTOI(fs->lfs_ivnode)->i_devvp->v_op->vop_strategy; |
| 702 | |
| 703 | s = splbio(); |
| 704 | if (sp->seg_flags & SEGM_CKP) { |
| 705 | fs->lfs_iocount += nblocks; |
| 706 | flags = B_ASYNC | B_BUSY | B_CALL; |
| 707 | } else |
| 708 | flags = B_ASYNC | B_BUSY; |
| 709 | for (bpp = sp->bpp, i = nblocks; i--;) { |
| 710 | bp = *bpp++; |
| 711 | bp->b_flags |= flags; |
| 712 | bp->b_flags &= |
| 713 | ~(B_DONE | B_ERROR | B_READ | B_DELWRI | B_LOCKED); |
| 714 | bp->b_dev = i_dev; |
| 715 | bp->b_iodone = lfs_callback; |
| 716 | if (!(bp->b_flags & B_NOCACHE)) { |
| 717 | bremfree(bp); |
| 718 | reassignbuf(bp, bp->b_vp); |
| 719 | } |
| 720 | } |
| 721 | splx(s); |
| 722 | |
| 723 | for (bpp = sp->bpp, i = nblocks; i--;) |
| 724 | (strategy)(*bpp++); |
| 725 | } |
| 726 | |
| 727 | void |
| 728 | lfs_writesuper(fs, sp) |
| 729 | struct lfs *fs; |
| 730 | struct segment *sp; |
| 731 | { |
| 732 | struct buf *bp; |
| 733 | dev_t i_dev; |
| 734 | int (*strategy) __P((struct buf *)); |
| 735 | |
| 736 | #ifdef VERBOSE |
| 737 | printf("lfs_writesuper\n"); |
| 738 | #endif |
| 739 | i_dev = VTOI(fs->lfs_ivnode)->i_dev; |
| 740 | strategy = VTOI(fs->lfs_ivnode)->i_devvp->v_op->vop_strategy; |
| 741 | |
| 742 | /* Checksum the superblock and copy it into a buffer. */ |
| 743 | fs->lfs_cksum = cksum(fs, sizeof(struct lfs) - sizeof(fs->lfs_cksum)); |
| 744 | bp = lfs_newbuf(fs, sp, fs->lfs_sboffs[0], LFS_SBPAD); |
| 745 | *bp->b_un.b_lfs = *fs; |
| 746 | |
| 747 | /* Write the first superblock (wait). */ |
| 748 | bp->b_dev = i_dev; |
| 749 | bp->b_flags |= B_BUSY; |
| 750 | bp->b_flags &= ~(B_DONE | B_ERROR | B_READ | B_DELWRI); |
| 751 | (strategy)(bp); |
| 752 | biowait(bp); |
| 753 | |
| 754 | /* Write the second superblock (don't wait). */ |
| 755 | bp->b_blkno = bp->b_lblkno = fs->lfs_sboffs[1]; |
| 756 | bp->b_flags |= B_ASYNC | B_BUSY; |
| 757 | bp->b_flags &= ~(B_DONE | B_ERROR | B_READ | B_DELWRI); |
| 758 | (strategy)(bp); |
| 759 | } |
| 760 | |
| 761 | /* |
| 762 | * Logical block number match routines used when traversing the dirty block |
| 763 | * chain. |
| 764 | */ |
| 765 | int |
| 766 | lfs_match_data(fs, bp) |
| 767 | struct lfs *fs; |
| 768 | struct buf *bp; |
| 769 | { |
| 770 | return (bp->b_lblkno >= 0); |
| 771 | } |
| 772 | |
| 773 | int |
| 774 | lfs_match_indir(fs, bp) |
| 775 | struct lfs *fs; |
| 776 | struct buf *bp; |
| 777 | { |
| 778 | int lbn; |
| 779 | |
| 780 | lbn = bp->b_lblkno; |
| 781 | return (lbn < 0 && (-lbn - NDADDR) % NINDIR(fs) == 0); |
| 782 | } |
| 783 | |
| 784 | int |
| 785 | lfs_match_dindir(fs, bp) |
| 786 | struct lfs *fs; |
| 787 | struct buf *bp; |
| 788 | { |
| 789 | int lbn; |
| 790 | |
| 791 | lbn = bp->b_lblkno; |
| 792 | return (lbn < 0 && (-lbn - NDADDR) % NINDIR(fs) == 1); |
| 793 | } |
| 794 | |
| 795 | int |
| 796 | lfs_match_tindir(fs, bp) |
| 797 | struct lfs *fs; |
| 798 | struct buf *bp; |
| 799 | { |
| 800 | int lbn; |
| 801 | |
| 802 | lbn = bp->b_lblkno; |
| 803 | return (lbn < 0 && (-lbn - NDADDR) % NINDIR(fs) == 2); |
| 804 | } |
| 805 | |
| 806 | /* |
| 807 | * Allocate a new buffer header. |
| 808 | */ |
| 809 | struct buf * |
| 810 | lfs_newbuf(fs, sp, daddr, size) |
| 811 | struct lfs *fs; |
| 812 | struct segment *sp; |
| 813 | daddr_t daddr; |
| 814 | size_t size; |
| 815 | { |
| 816 | struct buf *bp; |
| 817 | |
| 818 | #ifdef VERBOSE |
| 819 | printf("lfs_newbuf\n"); |
| 820 | #endif |
| 821 | bp = getnewbuf(); |
| 822 | bremhash(bp); |
| 823 | bgetvp(fs->lfs_ivnode, bp); |
| 824 | bp->b_bcount = 0; |
| 825 | bp->b_lblkno = daddr; |
| 826 | bp->b_blkno = daddr; |
| 827 | bp->b_error = 0; |
| 828 | bp->b_resid = 0; |
| 829 | allocbuf(bp, size); |
| 830 | bp->b_flags |= B_NOCACHE; |
| 831 | binshash(bp, &bfreelist[BQ_AGE]); |
| 832 | return (bp); |
| 833 | } |
| 834 | |
| 835 | int /* XXX should be void */ |
| 836 | lfs_callback(bp) |
| 837 | struct buf *bp; |
| 838 | { |
| 839 | struct lfs *fs; |
| 840 | |
| 841 | fs = VFSTOUFS(bp->b_vp->v_mount)->um_lfs; |
| 842 | #ifdef DIAGNOSTIC |
| 843 | if (fs->lfs_iocount == 0) |
| 844 | panic("lfs_callback: zero iocount\n"); |
| 845 | #endif |
| 846 | if (--fs->lfs_iocount == 0) |
| 847 | wakeup((caddr_t)&fs->lfs_iocount); |
| 848 | |
| 849 | brelse(bp); |
| 850 | } |
| 851 | |
| 852 | /* |
| 853 | * Shellsort (diminishing increment sort) from Data Structures and |
| 854 | * Algorithms, Aho, Hopcraft and Ullman, 1983 Edition, page 290; |
| 855 | * see also Knuth Vol. 3, page 84. The increments are selected from |
| 856 | * formula (8), page 95. Roughly O(N^3/2). |
| 857 | */ |
| 858 | /* |
| 859 | * This is our own private copy of shellsort because we want to sort |
| 860 | * two parallel arrays (the array of buffer pointers and the array of |
| 861 | * logical block numbers) simultaneously. Note that we cast the array |
| 862 | * of logical block numbers to a unsigned in this routine so that the |
| 863 | * negative block numbers (meta data blocks) sort AFTER the data blocks. |
| 864 | */ |
| 865 | void |
| 866 | lfs_shellsort(bp_array, lb_array, nmemb) |
| 867 | struct buf **bp_array; |
| 868 | daddr_t *lb_array; |
| 869 | register int nmemb; |
| 870 | { |
| 871 | static int __rsshell_increments[] = { 4, 1, 0 }; |
| 872 | register int incr, *incrp, t1, t2; |
| 873 | struct buf *bp_temp; |
| 874 | u_long lb_temp; |
| 875 | |
| 876 | for (incrp = __rsshell_increments; incr = *incrp++;) |
| 877 | for (t1 = incr; t1 < nmemb; ++t1) |
| 878 | for (t2 = t1 - incr; t2 >= 0;) |
| 879 | if (lb_array[t2] > lb_array[t2 + incr]) { |
| 880 | lb_temp = lb_array[t2]; |
| 881 | lb_array[t2] = lb_array[t2 + incr]; |
| 882 | lb_array[t2 + incr] = lb_temp; |
| 883 | bp_temp = bp_array[t2]; |
| 884 | bp_array[t2] = bp_array[t2 + incr]; |
| 885 | bp_array[t2 + incr] = bp_temp; |
| 886 | t2 -= incr; |
| 887 | } else |
| 888 | break; |
| 889 | } |