1 /*- 2 * Copyright (c) 1992 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)library.c 5.8 (Berkeley) 12/18/92"; 10 #endif /* not lint */ 11 12 #include <sys/param.h> 13 #include <sys/time.h> 14 #include <sys/stat.h> 15 #include <sys/mount.h> 16 #include <sys/types.h> 17 #include <sys/mman.h> 18 19 #include <ufs/ufs/dinode.h> 20 #include <ufs/lfs/lfs.h> 21 22 #include <fcntl.h> 23 #include <stdio.h> 24 #include <unistd.h> 25 #include <stdlib.h> 26 #include <string.h> 27 #include "clean.h" 28 29 void add_blocks __P((FS_INFO *, BLOCK_INFO *, int *, SEGSUM *, caddr_t, 30 daddr_t, daddr_t)); 31 void add_inodes __P((FS_INFO *, BLOCK_INFO *, int *, SEGSUM *, caddr_t, 32 daddr_t)); 33 int bi_compare __P((const void *, const void *)); 34 int bi_toss __P((const void *, const void *, const void *)); 35 void get_ifile __P((FS_INFO *, int)); 36 int get_superblock __P((FS_INFO *, struct lfs *)); 37 int pseg_valid __P((FS_INFO *, SEGSUM *)); 38 39 /* 40 * This function will get information on all mounted file systems 41 * of a given type. 42 */ 43 int 44 fs_getmntinfo(buf, type) 45 struct statfs **buf; 46 int type; 47 { 48 struct statfs *tstatfsp; 49 struct statfs *sbp; 50 int count, i, tcount; 51 52 tcount = getmntinfo(&tstatfsp, MNT_NOWAIT); 53 54 if (tcount < 0) { 55 err(0, "getmntinfo failed"); 56 return (-1); 57 } 58 59 for (count = 0, i = 0; i < tcount ; ++i) 60 if (tstatfsp[i].f_type == type) 61 ++count; 62 63 if (count) { 64 if (!(*buf = (struct statfs *) 65 malloc(count * sizeof(struct statfs)))) 66 err(1, "fs_getmntinfo: out of space"); 67 for (i = 0, sbp = *buf; i < tcount ; ++i) { 68 if (tstatfsp[i].f_type == type) { 69 *sbp = tstatfsp[i]; 70 ++sbp; 71 } 72 } 73 } 74 return (count); 75 } 76 77 /* 78 * Get all the information available on an LFS file system. 79 * Returns an array of FS_INFO structures, NULL on error. 80 */ 81 FS_INFO * 82 get_fs_info (lstatfsp, count, use_mmap) 83 struct statfs *lstatfsp; /* IN: array of statfs structs */ 84 int count; /* IN: number of file systems */ 85 int use_mmap; /* IN: mmap or read */ 86 { 87 FS_INFO *fp, *fsp; 88 int i; 89 90 fsp = (FS_INFO *)calloc(count, sizeof(FS_INFO)); 91 92 for (fp = fsp, i = 0; i < count; ++i, ++fp) { 93 fp->fi_statfsp = lstatfsp++; 94 if (get_superblock (fp, &fp->fi_lfs)) 95 err(1, "get_fs_info: get_superblock failed"); 96 fp->fi_daddr_shift = 97 fp->fi_lfs.lfs_bshift - fp->fi_lfs.lfs_fsbtodb; 98 get_ifile (fp, use_mmap); 99 } 100 return (fsp); 101 } 102 103 /* 104 * If we are reading the ifile then we need to refresh it. Even if 105 * we are mmapping it, it might have grown. Finally, we need to 106 * refresh the file system information (statfs) info. 107 */ 108 void 109 reread_fs_info(fsp, count, use_mmap) 110 FS_INFO *fsp; /* IN: array of fs_infos to free */ 111 int count; /* IN: number of file systems */ 112 { 113 int i; 114 115 for (i = 0; i < count; ++i, ++fsp) { 116 if (statfs(fsp->fi_statfsp->f_mntonname, fsp->fi_statfsp)) 117 err(0, "reread_fs_info: statfs failed"); 118 get_ifile (fsp, use_mmap); 119 } 120 } 121 122 /* 123 * Gets the superblock from disk (possibly in face of errors) 124 */ 125 int 126 get_superblock (fsp, sbp) 127 FS_INFO *fsp; /* local file system info structure */ 128 struct lfs *sbp; 129 { 130 char mntfromname[MNAMELEN+1]; 131 int fid; 132 133 strcpy(mntfromname, "/dev/r"); 134 strcat(mntfromname, fsp->fi_statfsp->f_mntfromname+5); 135 136 if ((fid = open(mntfromname, O_RDONLY, (mode_t)0)) < 0) { 137 err(0, "get_superblock: bad open"); 138 return (-1); 139 } 140 141 get(fid, LFS_LABELPAD, sbp, sizeof(struct lfs)); 142 close (fid); 143 144 return (0); 145 } 146 147 /* 148 * This function will map the ifile into memory. It causes a 149 * fatal error on failure. 150 */ 151 void 152 get_ifile (fsp, use_mmap) 153 FS_INFO *fsp; 154 int use_mmap; 155 156 { 157 struct stat file_stat; 158 caddr_t ifp; 159 char *ifile_name; 160 int count, fid; 161 162 ifp = NULL; 163 ifile_name = malloc(strlen(fsp->fi_statfsp->f_mntonname) + 164 strlen(IFILE_NAME)+2); 165 strcat(strcat(strcpy(ifile_name, fsp->fi_statfsp->f_mntonname), "/"), 166 IFILE_NAME); 167 168 if ((fid = open(ifile_name, O_RDWR, (mode_t)0)) < 0) 169 err(1, "get_ifile: bad open"); 170 171 if (fstat (fid, &file_stat)) 172 err(1, "get_ifile: fstat failed"); 173 174 if (use_mmap && file_stat.st_size == fsp->fi_ifile_length) { 175 (void) close(fid); 176 return; 177 } 178 179 /* get the ifile */ 180 if (use_mmap) { 181 if (fsp->fi_cip) 182 munmap((caddr_t)fsp->fi_cip, fsp->fi_ifile_length); 183 ifp = mmap ((caddr_t)0, file_stat.st_size, 184 PROT_READ|PROT_WRITE, 0, fid, (off_t)0); 185 if (ifp == (caddr_t)(-1)) 186 err(1, "get_ifile: mmap failed"); 187 } else { 188 if (fsp->fi_cip) 189 free(fsp->fi_cip); 190 if (!(ifp = malloc (file_stat.st_size))) 191 err (1, "get_ifile: malloc failed"); 192 redo_read: 193 count = read (fid, ifp, (size_t) file_stat.st_size); 194 195 if (count < 0) 196 err(1, "get_ifile: bad ifile read"); 197 else if (count < file_stat.st_size) { 198 err(0, "get_ifile"); 199 if (lseek(fid, 0, SEEK_SET) < 0) 200 err(1, "get_ifile: bad ifile lseek"); 201 goto redo_read; 202 } 203 } 204 fsp->fi_ifile_length = file_stat.st_size; 205 close (fid); 206 207 fsp->fi_cip = (CLEANERINFO *)ifp; 208 fsp->fi_segusep = (SEGUSE *)(ifp + CLEANSIZE(fsp)); 209 fsp->fi_ifilep = (IFILE *)((caddr_t)fsp->fi_segusep + SEGTABSIZE(fsp)); 210 211 /* 212 * The number of ifile entries is equal to the number of blocks 213 * blocks in the ifile minus the ones allocated to cleaner info 214 * and segment usage table multiplied by the number of ifile 215 * entries per page. 216 */ 217 fsp->fi_ifile_count = (fsp->fi_ifile_length >> fsp->fi_lfs.lfs_bshift - 218 fsp->fi_lfs.lfs_cleansz - fsp->fi_lfs.lfs_segtabsz) * 219 fsp->fi_lfs.lfs_ifpb; 220 221 free (ifile_name); 222 } 223 224 /* 225 * This function will scan a segment and return a list of 226 * <inode, blocknum> pairs which indicate which blocks were 227 * contained as live data within the segment when the segment 228 * summary was read (it may have "died" since then). Any given 229 * pair will be listed at most once. 230 */ 231 int 232 lfs_segmapv(fsp, seg, seg_buf, blocks, bcount) 233 FS_INFO *fsp; /* pointer to local file system information */ 234 int seg; /* the segment number */ 235 caddr_t seg_buf; /* the buffer containing the segment's data */ 236 BLOCK_INFO **blocks; /* OUT: array of block_info for live blocks */ 237 int *bcount; /* OUT: number of active blocks in segment */ 238 { 239 BLOCK_INFO *bip; 240 SEGSUM *sp; 241 SEGUSE *sup; 242 FINFO *fip; 243 struct lfs *lfsp; 244 caddr_t s, segend; 245 daddr_t pseg_addr, seg_addr; 246 int i, nelem, nblocks, sumsize; 247 time_t timestamp; 248 249 lfsp = &fsp->fi_lfs; 250 nelem = 2 * lfsp->lfs_ssize; 251 if (!(bip = malloc(nelem * sizeof(BLOCK_INFO)))) 252 goto err0; 253 254 sup = SEGUSE_ENTRY(lfsp, fsp->fi_segusep, seg); 255 s = seg_buf + (sup->su_flags & SEGUSE_SUPERBLOCK ? LFS_SBPAD : 0); 256 seg_addr = sntoda(lfsp, seg); 257 pseg_addr = seg_addr + (sup->su_flags & SEGUSE_SUPERBLOCK ? btodb(LFS_SBPAD) : 0); 258 #ifdef VERBOSE 259 printf("\tsegment buffer at: 0x%x\tseg_addr 0x%x\n", s, seg_addr); 260 #endif /* VERBOSE */ 261 262 *bcount = 0; 263 for (segend = seg_buf + seg_size(lfsp), timestamp = 0; s < segend; ) { 264 sp = (SEGSUM *)s; 265 266 #ifdef VERBOSE 267 printf("\tpartial at: 0x%x\n", pseg_addr); 268 print_SEGSUM(lfsp, sp); 269 fflush(stdout); 270 #endif /* VERBOSE */ 271 272 nblocks = pseg_valid(fsp, sp); 273 if (nblocks <= 0) 274 break; 275 276 /* Check if we have hit old data */ 277 if (timestamp > ((SEGSUM*)s)->ss_create) 278 break; 279 timestamp = ((SEGSUM*)s)->ss_create; 280 281 #ifdef DIAGNOSTIC 282 /* Verfiy size of summary block */ 283 sumsize = sizeof(SEGSUM) + 284 (sp->ss_ninos + INOPB(lfsp) - 1) / INOPB(lfsp); 285 for (fip = (FINFO *)(sp + 1); i < sp->ss_nfinfo; ++i) { 286 sumsize += sizeof(FINFO) + 287 (fip->fi_nblocks - 1) * sizeof(daddr_t); 288 fip = (FINFO *)(&fip->fi_blocks[fip->fi_nblocks]); 289 } 290 if (sumsize > LFS_SUMMARY_SIZE) { 291 fprintf(stderr, 292 "Segment %d summary block too big: %d\n", 293 seg, sumsize); 294 exit(1); 295 } 296 #endif 297 298 if (*bcount + nblocks + sp->ss_ninos > nelem) { 299 nelem = *bcount + nblocks + sp->ss_ninos; 300 bip = realloc (bip, nelem * sizeof(BLOCK_INFO)); 301 if (!bip) 302 goto err0; 303 } 304 add_blocks(fsp, bip, bcount, sp, seg_buf, seg_addr, pseg_addr); 305 add_inodes(fsp, bip, bcount, sp, seg_buf, seg_addr); 306 pseg_addr += fsbtodb(lfsp, nblocks) + 307 bytetoda(fsp, LFS_SUMMARY_SIZE); 308 s += (nblocks << lfsp->lfs_bshift) + LFS_SUMMARY_SIZE; 309 } 310 qsort(bip, *bcount, sizeof(BLOCK_INFO), bi_compare); 311 toss(bip, bcount, sizeof(BLOCK_INFO), bi_toss, NULL); 312 #ifdef VERBOSE 313 { 314 BLOCK_INFO *_bip; 315 int i; 316 317 printf("BLOCK INFOS\n"); 318 for (_bip = bip, i=0; i < *bcount; ++_bip, ++i) 319 PRINT_BINFO(_bip); 320 } 321 #endif 322 *blocks = bip; 323 return (0); 324 325 err0: *bcount = 0; 326 return (-1); 327 328 } 329 330 /* 331 * This will parse a partial segment and fill in BLOCK_INFO structures 332 * for each block described in the segment summary. It will not include 333 * blocks or inodes from files with new version numbers. 334 */ 335 void 336 add_blocks (fsp, bip, countp, sp, seg_buf, segaddr, psegaddr) 337 FS_INFO *fsp; /* pointer to super block */ 338 BLOCK_INFO *bip; /* Block info array */ 339 int *countp; /* IN/OUT: number of blocks in array */ 340 SEGSUM *sp; /* segment summmary pointer */ 341 caddr_t seg_buf; /* buffer containing segment */ 342 daddr_t segaddr; /* address of this segment */ 343 daddr_t psegaddr; /* address of this partial segment */ 344 { 345 IFILE *ifp; 346 FINFO *fip; 347 caddr_t bp; 348 daddr_t *dp, *iaddrp; 349 int db_per_block, i, j; 350 u_long page_size; 351 352 #ifdef VERBOSE 353 printf("FILE INFOS\n"); 354 #endif 355 db_per_block = fsbtodb(&fsp->fi_lfs, 1); 356 page_size = fsp->fi_lfs.lfs_bsize; 357 bp = seg_buf + datobyte(fsp, psegaddr - segaddr) + LFS_SUMMARY_SIZE; 358 bip += *countp; 359 psegaddr += bytetoda(fsp, LFS_SUMMARY_SIZE); 360 iaddrp = (daddr_t *)((caddr_t)sp + LFS_SUMMARY_SIZE); 361 --iaddrp; 362 for (fip = (FINFO *)(sp + 1), i = 0; i < sp->ss_nfinfo; 363 ++i, fip = (FINFO *)(&fip->fi_blocks[fip->fi_nblocks])) { 364 365 ifp = IFILE_ENTRY(&fsp->fi_lfs, fsp->fi_ifilep, fip->fi_ino); 366 PRINT_FINFO(fip, ifp); 367 if (ifp->if_version > fip->fi_version) 368 continue; 369 dp = &(fip->fi_blocks[0]); 370 for (j = 0; j < fip->fi_nblocks; j++, dp++) { 371 while (psegaddr == *iaddrp) { 372 psegaddr += db_per_block; 373 bp += page_size; 374 --iaddrp; 375 } 376 bip->bi_inode = fip->fi_ino; 377 bip->bi_lbn = *dp; 378 bip->bi_daddr = psegaddr; 379 bip->bi_segcreate = (time_t)(sp->ss_create); 380 bip->bi_bp = bp; 381 bip->bi_version = ifp->if_version; 382 psegaddr += db_per_block; 383 bp += page_size; 384 ++bip; 385 ++(*countp); 386 } 387 } 388 } 389 390 /* 391 * For a particular segment summary, reads the inode blocks and adds 392 * INODE_INFO structures to the array. Returns the number of inodes 393 * actually added. 394 */ 395 void 396 add_inodes (fsp, bip, countp, sp, seg_buf, seg_addr) 397 FS_INFO *fsp; /* pointer to super block */ 398 BLOCK_INFO *bip; /* block info array */ 399 int *countp; /* pointer to current number of inodes */ 400 SEGSUM *sp; /* segsum pointer */ 401 caddr_t seg_buf; /* the buffer containing the segment's data */ 402 daddr_t seg_addr; /* disk address of seg_buf */ 403 { 404 struct dinode *di; 405 struct lfs *lfsp; 406 IFILE *ifp; 407 BLOCK_INFO *bp; 408 daddr_t *daddrp; 409 ino_t inum; 410 int i; 411 412 if (sp->ss_ninos <= 0) 413 return; 414 415 bp = bip + *countp; 416 lfsp = &fsp->fi_lfs; 417 #ifdef VERBOSE 418 (void) printf("INODES:\n"); 419 #endif 420 daddrp = (daddr_t *)((caddr_t)sp + LFS_SUMMARY_SIZE); 421 for (i = 0; i < sp->ss_ninos; ++i) { 422 if (i % INOPB(lfsp) == 0) { 423 --daddrp; 424 di = (struct dinode *)(seg_buf + 425 ((*daddrp - seg_addr) << fsp->fi_daddr_shift)); 426 } else 427 ++di; 428 429 inum = di->di_inumber; 430 bp->bi_lbn = LFS_UNUSED_LBN; 431 bp->bi_inode = inum; 432 bp->bi_daddr = *daddrp; 433 bp->bi_bp = di; 434 bp->bi_segcreate = sp->ss_create; 435 436 if (inum == LFS_IFILE_INUM) { 437 bp->bi_version = 1; /* Ifile version should be 1 */ 438 bp++; 439 ++(*countp); 440 PRINT_INODE(1, bp); 441 } else { 442 ifp = IFILE_ENTRY(lfsp, fsp->fi_ifilep, inum); 443 PRINT_INODE(ifp->if_daddr == *daddrp, bp); 444 bp->bi_version = ifp->if_version; 445 if (ifp->if_daddr == *daddrp) { 446 bp++; 447 ++(*countp); 448 } 449 } 450 } 451 } 452 453 /* 454 * Checks the summary checksum and the data checksum to determine if the 455 * segment is valid or not. Returns the size of the partial segment if it 456 * is valid, * and 0 otherwise. Use dump_summary to figure out size of the 457 * the partial as well as whether or not the checksum is valid. 458 */ 459 int 460 pseg_valid (fsp, ssp) 461 FS_INFO *fsp; /* pointer to file system info */ 462 SEGSUM *ssp; /* pointer to segment summary block */ 463 { 464 caddr_t p; 465 int i, nblocks; 466 u_long *datap; 467 SEGUSE *sup; 468 469 if ((nblocks = dump_summary(&fsp->fi_lfs, ssp, 0, NULL)) <= 0 || 470 nblocks > fsp->fi_lfs.lfs_ssize - 1) 471 return(0); 472 473 /* check data/inode block(s) checksum too */ 474 datap = (u_long *)malloc(nblocks * sizeof(u_long)); 475 p = (caddr_t)ssp + LFS_SUMMARY_SIZE; 476 for (i = 0; i < nblocks; ++i) { 477 datap[i] = *((u_long *)p); 478 p += fsp->fi_lfs.lfs_bsize; 479 } 480 if (cksum ((void *)datap, nblocks * sizeof(u_long)) != ssp->ss_datasum) 481 return (0); 482 483 return (nblocks); 484 } 485 486 487 /* #define MMAP_SEGMENT */ 488 /* 489 * read a segment into a memory buffer 490 */ 491 int 492 mmap_segment (fsp, segment, segbuf, use_mmap) 493 FS_INFO *fsp; /* file system information */ 494 int segment; /* segment number */ 495 caddr_t *segbuf; /* pointer to buffer area */ 496 int use_mmap; /* mmap instead of read */ 497 { 498 struct lfs *lfsp; 499 int fid; /* fildes for file system device */ 500 daddr_t seg_daddr; /* base disk address of segment */ 501 off_t seg_byte; 502 size_t ssize; 503 char mntfromname[MNAMELEN+2]; 504 505 lfsp = &fsp->fi_lfs; 506 507 /* get the disk address of the beginning of the segment */ 508 seg_daddr = sntoda(lfsp, segment); 509 seg_byte = datobyte(fsp, seg_daddr); 510 ssize = seg_size(lfsp); 511 512 strcpy(mntfromname, "/dev/r"); 513 strcat(mntfromname, fsp->fi_statfsp->f_mntfromname+5); 514 515 if ((fid = open(mntfromname, O_RDONLY, (mode_t)0)) < 0) { 516 err(0, "mmap_segment: bad open"); 517 return (-1); 518 } 519 520 if (use_mmap) { 521 *segbuf = mmap ((caddr_t)0, seg_size(lfsp), PROT_READ, 522 0, fid, seg_byte); 523 if (*(long *)segbuf < 0) { 524 err(0, "mmap_segment: mmap failed"); 525 return (NULL); 526 } 527 } else { 528 #ifdef VERBOSE 529 printf("mmap_segment\tseg_daddr: %lu\tseg_size: %lu\tseg_offset: %qu\n", 530 seg_daddr, ssize, seg_byte); 531 #endif 532 /* malloc the space for the buffer */ 533 *segbuf = malloc(ssize); 534 if (!*segbuf) { 535 err(0, "mmap_segment: malloc failed"); 536 return(NULL); 537 } 538 539 /* read the segment data into the buffer */ 540 if (lseek (fid, seg_byte, SEEK_SET) != seg_byte) { 541 err (0, "mmap_segment: bad lseek"); 542 free(*segbuf); 543 return (-1); 544 } 545 546 if (read (fid, *segbuf, ssize) != ssize) { 547 err (0, "mmap_segment: bad read"); 548 free(*segbuf); 549 return (-1); 550 } 551 } 552 close (fid); 553 554 return (0); 555 } 556 557 void 558 munmap_segment (fsp, seg_buf, use_mmap) 559 FS_INFO *fsp; /* file system information */ 560 caddr_t seg_buf; /* pointer to buffer area */ 561 int use_mmap; /* mmap instead of read/write */ 562 { 563 if (use_mmap) 564 munmap (seg_buf, seg_size(&fsp->fi_lfs)); 565 else 566 free (seg_buf); 567 } 568 569 570 /* 571 * USEFUL DEBUGGING TOOLS: 572 */ 573 void 574 print_SEGSUM (lfsp, p) 575 struct lfs *lfsp; 576 SEGSUM *p; 577 { 578 if (p) 579 (void) dump_summary(lfsp, p, DUMP_ALL, NULL); 580 else printf("0x0"); 581 fflush(stdout); 582 } 583 584 int 585 bi_compare(a, b) 586 const void *a; 587 const void *b; 588 { 589 const BLOCK_INFO *ba, *bb; 590 int diff; 591 592 ba = a; 593 bb = b; 594 595 if (diff = (int)(ba->bi_inode - bb->bi_inode)) 596 return (diff); 597 if (diff = (int)(ba->bi_lbn - bb->bi_lbn)) { 598 if (ba->bi_lbn == LFS_UNUSED_LBN) 599 return(-1); 600 else if (bb->bi_lbn == LFS_UNUSED_LBN) 601 return(1); 602 else if (ba->bi_lbn < 0 && bb->bi_lbn >= 0) 603 return(1); 604 else if (bb->bi_lbn < 0 && ba->bi_lbn >= 0) 605 return(-1); 606 else 607 return (diff); 608 } 609 if (diff = (int)(ba->bi_segcreate - bb->bi_segcreate)) 610 return (diff); 611 diff = (int)(ba->bi_daddr - bb->bi_daddr); 612 return (diff); 613 } 614 615 int 616 bi_toss(dummy, a, b) 617 const void *dummy; 618 const void *a; 619 const void *b; 620 { 621 const BLOCK_INFO *ba, *bb; 622 623 ba = a; 624 bb = b; 625 626 return(ba->bi_inode == bb->bi_inode && ba->bi_lbn == bb->bi_lbn); 627 } 628 629 void 630 toss(p, nump, size, dotoss, client) 631 void *p; 632 int *nump; 633 size_t size; 634 int (*dotoss) __P((const void *, const void *, const void *)); 635 void *client; 636 { 637 int i; 638 void *p1; 639 640 if (*nump == 0) 641 return; 642 643 for (i = *nump; --i > 0;) { 644 p1 = p + size; 645 if (dotoss(client, p, p1)) { 646 bcopy(p1, p, i * size); 647 --(*nump); 648 } else 649 p += size; 650 } 651 } 652