home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume8 / packdisk / packdisk.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-10-08  |  11.1 KB  |  487 lines
  1. /*
  2.  *
  3.  * This program takes a disk and makes all the files and directories,
  4.  * and the free list, contiguous.
  5.  *
  6.  *                         Andrew Fyfe
  7.  *                        7 October 1989
  8.  *
  9.  *                        andy@csvax.caltech.edu
  10.  */
  11.  
  12. #include <sys/filsys.h>
  13. #include <sys/ino.h>
  14. #include <sys/stat.h>
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17.  
  18. #define NUM_ADDR    13
  19. #define FIRST_INDIR    10   /* 0-9 direct, 10 single, 11 double, 12 triple */
  20. #define NUM_INDIR    (NUM_ADDR - FIRST_INDIR)
  21.  
  22. char *cmd_name;
  23. int disk, dev;
  24.  
  25. struct filsys filsys;
  26.  
  27. struct dinode ino;    /* current working inode, and its number */
  28. ino_t w_ino;
  29.  
  30. char *inode_block;    /* block containing last read/written inode */
  31. daddr_t w_ino_blk;    /* and its number */
  32.  
  33. char *indir[NUM_INDIR];        /* current working indirect blocks */
  34. daddr_t w_indir[NUM_INDIR];    /* and their numbers */
  35.  
  36. daddr_t next_fill;    /* next (sequential) block to fill */
  37.  
  38. char *inode_table;    /* a cache of the entire inode section of the disk */
  39.  
  40. long *map;    /* a map from block numbers to referencing inode/indir block */
  41.  
  42. static void read_superblk(void);
  43. static void write_superblk(void);
  44. static void map_inode(ino_t inode);
  45. static void update_map(long map_entry, daddr_t block, int level);
  46. static void read_block(daddr_t block, void *buf);
  47. static void write_block(daddr_t block, void *buf);
  48. static void read_inode(ino_t inode, struct dinode *buf);
  49. static void write_inode(ino_t inode, struct dinode *buf);
  50. static void move_block(daddr_t from, daddr_t to);
  51. static void move_inode(ino_t inode);
  52. static void move_indirect(daddr_t block, int level);
  53. static void make_hole(void);
  54. static void rebuild_free_list(void);
  55.  
  56. extern void l3tol(long *, char *, int length);
  57. extern void ltol3(char *, long *, int length);
  58.  
  59. void
  60. main(int argc, char *argv[])
  61. {
  62.     ino_t inode, total_inodes;
  63.     daddr_t block;
  64.     int i;
  65.     char *ctime(long *);
  66. #ifndef DEBUG
  67.     struct stat statb;
  68.     extern int stat(const char *, struct stat *);
  69. #endif
  70.  
  71.     cmd_name = argv[0];
  72.  
  73.     if (argc != 2) {
  74.     fprintf(stderr, "%s: Usage: %s <file system>\n",
  75.         cmd_name, cmd_name);
  76.     exit(1);
  77.     }
  78.  
  79. #ifndef DEBUG
  80.     if (stat(argv[1], &statb) < 0) {
  81.     fprintf(stderr, "%s: can't stat %s: ", cmd_name, argv[1]);
  82.     perror("");
  83.     exit(1);
  84.     }
  85.     if ((statb.st_mode & S_IFMT) != S_IFCHR) {
  86.     fprintf(stderr, "%s: %s is not a character device\n",
  87.         cmd_name, argv[1]);
  88.     exit(1);
  89.     }
  90. #endif
  91.  
  92.     disk = open(argv[1], 2, 0);
  93.     if (disk < 0) {
  94.     fprintf(stderr, "%s: can't open %s: ", cmd_name, argv[1]);
  95.     perror("");
  96.     exit(1);
  97.     }
  98.  
  99.     read_superblk();
  100.  
  101.     total_inodes = (filsys.s_isize - FsITOD(dev, ROOTINO)) * FsINOPB(dev);
  102.     fprintf(stderr, "File system: name: \"%.6s\", pack: \"%.6s\"\n",
  103.     filsys.s_fname, filsys.s_fpack);
  104.     fprintf(stderr, "\tlast modified on %s", ctime(&filsys.s_time));
  105.     fprintf(stderr,
  106.     "\ttotal inodes = %d, data blocks = %d, total = %d blocks\n",
  107.     total_inodes, filsys.s_fsize - filsys.s_isize, filsys.s_fsize);
  108.     fprintf(stderr, "\tfree blocks = %d, free inodes = %d\n",
  109.     filsys.s_tfree, filsys.s_tinode);
  110.  
  111.     for (i = 0; i < NUM_INDIR; ++i) {
  112.     w_indir[i] = 0;
  113.     indir[i] = malloc(FsBSIZE(dev));
  114.     if (indir[i] == 0) {
  115.         fprintf(stderr, "%s: can't malloc indir buffer space: ", cmd_name);
  116.         perror("");
  117.         exit(1);
  118.     }
  119.     }
  120.     w_ino = 0;
  121.  
  122.     map = calloc(filsys.s_fsize, sizeof(*map));
  123.     if (map == 0) {
  124.     fprintf(stderr, "%s: can't calloc map: ", cmd_name);
  125.     perror("");
  126.     exit(1);
  127.     }
  128.  
  129.     inode_table = malloc(filsys.s_isize * FsBSIZE(dev));
  130.     if (inode_table == 0) {
  131.     fprintf(stderr, "%s: can't malloc space for inode table\n", cmd_name);
  132.     w_ino_blk = 0;
  133.     inode_block = malloc(FsBSIZE(dev));
  134.     if (inode_block == 0) {
  135.         fprintf(stderr, "%s: can't malloc inode buffer space: ", cmd_name);
  136.         perror("");
  137.         exit(1);
  138.     }
  139.     }
  140.     else
  141.     for (block = FsITOD(dev, ROOTINO); block < filsys.s_isize; ++block)
  142.         read_block(block, &inode_table[block * FsBSIZE(dev)]);
  143.  
  144.     fprintf(stderr, "mapping...");
  145.     for (inode = ROOTINO; inode <= total_inodes; ++inode)
  146.     map_inode(inode);
  147.     fprintf(stderr, "done\n");
  148.  
  149.     next_fill = filsys.s_isize;
  150.     for (inode = ROOTINO; inode <= total_inodes; ++inode)
  151.     move_inode(inode);
  152.  
  153.     fprintf(stderr, "\nrebuilding the free list\n");
  154.     rebuild_free_list();
  155.  
  156.     fprintf(stderr, "*** Run fsck to check out the disk!!!\n");
  157.  
  158.     close(disk);
  159.     exit(0);
  160. }
  161.  
  162. static void
  163. read_superblk(void)
  164. {
  165.     if (lseek(disk, SUPERBOFF, 0) != SUPERBOFF) {
  166.     fprintf(stderr, "%s: can't seek to superblock: ", cmd_name);
  167.     perror("");
  168.     exit(1);
  169.     }
  170.     if (read(disk, &filsys, sizeof(filsys)) != sizeof(filsys)) {
  171.     fprintf(stderr, "%s: can't read superblock: ", cmd_name);
  172.     perror("");
  173.     exit(1);
  174.     }
  175.     if (filsys.s_magic != FsMAGIC) {
  176.     fprintf(stderr, "%s: invalid superblock magic number\n", cmd_name);
  177.     exit(1);
  178.     }
  179.     dev = (filsys.s_type == Fs2b) ? Fs2BLK : 0;
  180. }
  181.  
  182. static void
  183. write_superblk(void)
  184. {
  185.     lseek(disk, SUPERBOFF, 0);
  186.     if (write(disk, &filsys, sizeof(filsys)) != sizeof(filsys)) {
  187.     fprintf(stderr, "%s: can't write superblock: ", cmd_name);
  188.     perror("");
  189.     exit(1);
  190.     }
  191. }
  192.  
  193. static void
  194. map_inode(ino_t inode)
  195. {
  196.     int type, i;
  197.     long block[NUM_ADDR];
  198.  
  199.     read_inode(inode, &ino);
  200.     if (ino.di_mode == 0)
  201.     return;
  202.     type = ino.di_mode & S_IFMT;
  203.     if (type == S_IFCHR || type == S_IFBLK)
  204.     return;
  205.  
  206.     l3tol(block, ino.di_addr, NUM_ADDR);
  207.     for (i = 0; i < NUM_ADDR; ++i)
  208.     if (block[i] != 0)
  209.         update_map(inode, block[i],
  210.         (i < FIRST_INDIR) ? 0 : (i - FIRST_INDIR + 1));
  211. }
  212.  
  213. static void
  214. update_map(long map_entry, daddr_t block, int level)
  215. {
  216.     int i;
  217.  
  218.     if (map[block] != 0) {
  219.     fprintf(stderr, "%s: duplicate block %d in %d and %d\n",
  220.         cmd_name, block, map[block], map_entry);
  221.     exit(1);
  222.     }
  223.     map[block] = map_entry;
  224.  
  225.     if (level == 0)
  226.     return;
  227.  
  228.     --level;
  229.     read_block(block, indir[level]);
  230.     for (i = 0; i < FsNINDIR(dev); ++i)
  231.     if (((daddr_t *)indir[level])[i] != 0)
  232.         update_map(-block, ((daddr_t *)indir[level])[i], level);
  233. }
  234.  
  235. static void
  236. read_block(daddr_t block, void *buf)
  237. {
  238.     lseek(disk, block * FsBSIZE(dev), 0);
  239.     if (read(disk, buf, FsBSIZE(dev)) != FsBSIZE(dev)) {
  240.     fprintf(stderr, "%s: can't read block %d: ", cmd_name, block);
  241.     perror("");
  242.     exit(1);
  243.     }
  244. }
  245.  
  246. static void
  247. write_block(daddr_t block, void *buf)
  248. {
  249.     lseek(disk, block * FsBSIZE(dev), 0);
  250.     if (write(disk, buf, FsBSIZE(dev)) != FsBSIZE(dev)) {
  251.     fprintf(stderr, "%s: can't write block %d: ", cmd_name, block);
  252.     perror("");
  253.     exit(1);
  254.     }
  255. }
  256.  
  257. static void
  258. read_inode(ino_t inode, struct dinode *ino)
  259. {
  260.     daddr_t block;
  261.  
  262.     block = FsITOD(dev, inode);
  263.     if (inode_table == 0) {
  264.     if (w_ino_blk != block) {
  265.         w_ino_blk = block;
  266.         read_block(block, inode_block);
  267.     }
  268.     *ino = ((struct dinode *)inode_block)[FsITOO(dev, inode)];
  269.     }
  270.     else {
  271.     *ino = ((struct dinode *)&inode_table[block * FsBSIZE(dev)])
  272.         [FsITOO(dev, inode)];
  273.     }
  274. }
  275.  
  276. static void
  277. write_inode(ino_t inode, struct dinode *ino)
  278. {
  279.     daddr_t block;
  280.  
  281.     block = FsITOD(dev, inode);
  282.     if (inode_table == 0) {
  283.     if (w_ino_blk != block) {
  284.         w_ino_blk = block;
  285.         read_block(block, inode_block);
  286.     }
  287.     ((struct dinode *)inode_block)[FsITOO(dev, inode)] = *ino;
  288.     write_block(block, inode_block);
  289.     }
  290.     else {
  291.     ((struct dinode *)&inode_table[block * FsBSIZE(dev)])
  292.         [FsITOO(dev, inode)] = *ino;
  293.     write_block(block, &inode_table[block * FsBSIZE(dev)]);
  294.     }
  295. }
  296.  
  297. static void
  298. move_block(daddr_t from, daddr_t to)
  299. {
  300.     char buffer[FsBSIZE(dev)];
  301.     daddr_t block;
  302.  
  303.     if (map[to] != 0)
  304.     make_hole();
  305.  
  306.     read_block(from, buffer);
  307.     write_block(to, buffer);
  308.  
  309.     map[to] = map[from];
  310.     map[from] = 0;
  311.  
  312.     for (block = filsys.s_isize; block < filsys.s_fsize; ++block)
  313.     if (map[block] == -from)
  314.         map[block] = -to;
  315. }
  316.  
  317. static void
  318. move_inode(ino_t inode)
  319. {
  320.     int type, i;
  321.     long block[NUM_ADDR];
  322.  
  323.     read_inode(inode, &ino);
  324.     w_ino = inode;
  325.     if (ino.di_mode == 0)
  326.     return;
  327.     type = ino.di_mode & S_IFMT;
  328.     if (type == S_IFCHR || type == S_IFBLK)
  329.     return;
  330.     
  331.     fprintf(stderr, "moving inode %d (size %d)                         \r",
  332.     inode, ino.di_size);
  333.  
  334.     l3tol(block, ino.di_addr, NUM_ADDR);
  335.     for (i = 0; i < NUM_ADDR; ++i) {
  336.     if (block[i] == 0)
  337.         continue;
  338.     if (block[i] != next_fill) {
  339.         move_block(block[i], next_fill);
  340.         l3tol(block, ino.di_addr, NUM_ADDR);
  341.         block[i] = next_fill;
  342.         ltol3(ino.di_addr, block, NUM_ADDR);
  343.         write_inode(inode, &ino);
  344.     }
  345.     ++next_fill;
  346.     }
  347.     
  348.     for (i = FIRST_INDIR; i < NUM_ADDR; ++i)
  349.     move_indirect(block[i], i-FIRST_INDIR);
  350. }
  351.  
  352. static void
  353. move_indirect(daddr_t block, int level)
  354. {
  355.     int i;
  356.  
  357.     if (block == 0)
  358.     return;
  359.  
  360.     read_block(block, indir[level]);
  361.     w_indir[level] = block;
  362.  
  363.     for (i = 0; i < FsNINDIR(dev); ++i) {
  364.     if (((daddr_t *)indir[level])[i] == 0)
  365.         continue;
  366.     if (((daddr_t *)indir[level])[i] != next_fill) {
  367.         move_block(((daddr_t *)indir[level])[i], next_fill);
  368.         ((daddr_t *)indir[level])[i] = next_fill;
  369.         write_block(block, indir[level]);
  370.     }
  371.     ++next_fill;
  372.     }
  373.  
  374.     if (level == 0)
  375.     return;
  376.  
  377.     for (i = 0; i < FsNINDIR(dev); ++i)
  378.     move_indirect(((daddr_t *)indir[level])[i], level-1);
  379. }
  380.  
  381. static void
  382. make_hole(void)
  383. {
  384.     char t_indir[FsBSIZE(dev)];
  385.     daddr_t *p_indir;
  386.     struct dinode t_ino, *p_ino;
  387.     long block[NUM_ADDR];
  388.     daddr_t back;
  389.     int i;
  390.  
  391.     back = filsys.s_fsize - 1;
  392.     while (next_fill < back && map[back] != 0)
  393.     --back;
  394.  
  395.     if (next_fill >= back) {
  396.     fprintf(stderr, "%s: can't find a free block for %d\n",
  397.         cmd_name, next_fill);
  398.     exit(1);
  399.     }
  400.  
  401.     move_block(next_fill, back);
  402.  
  403.     if (map[back] < 0) {
  404.     block[0] = -map[back];
  405.     for (i = 0; i < NUM_INDIR; ++i)
  406.         if (block[0] == w_indir[i])
  407.         break;
  408.     if (i < NUM_INDIR) {
  409.         p_indir = (daddr_t *)indir[i];
  410.     }
  411.     else {
  412.         p_indir = (daddr_t *)t_indir;
  413.         read_block(block[0], t_indir);
  414.     }
  415.     for (i = 0; i < FsNINDIR(dev); ++i) {
  416.         if (p_indir[i] == next_fill) {
  417.         p_indir[i] = back;
  418.         break;
  419.         }
  420.     }
  421.     if (i == FsNINDIR(dev)) {
  422.         fprintf(stderr,
  423.         "%s: panic: can't find %d in indirect block %d\n",
  424.         cmd_name, next_fill, -map[back]);
  425.         exit(1);
  426.     }
  427.     write_block(block[0], p_indir);
  428.     }
  429.     else {
  430.     if (map[back] == w_ino) {
  431.         p_ino = &ino;
  432.     }
  433.     else {
  434.         p_ino = &t_ino;
  435.         read_inode(map[back], &t_ino);
  436.     }
  437.     l3tol(block, p_ino->di_addr, NUM_ADDR);
  438.     for (i = 0; i < NUM_ADDR; ++i) {
  439.         if (block[i] == next_fill) {
  440.         block[i] = back;
  441.         ltol3(p_ino->di_addr, block, NUM_ADDR);
  442.         break;
  443.         }
  444.     }
  445.     if (i == NUM_ADDR) {
  446.         fprintf(stderr, "%s: panic: can't find %d in inode %d\n",
  447.         cmd_name, next_fill, map[back]);
  448.         exit(1);
  449.     }
  450.     write_inode(map[back], p_ino);
  451.     }
  452. }
  453.  
  454. static void
  455. rebuild_free_list(void)
  456. {
  457.     int free_size, nfree;
  458.     daddr_t free[NICFREE], block;
  459.     char buf[FsBSIZE(dev)];
  460.  
  461.     free_size = filsys.s_fsize - next_fill;
  462.     if (free_size != filsys.s_tfree) {
  463.     fprintf(stderr, "%s: free list changed size from %d to %d\n",
  464.         cmd_name, filsys.s_tfree, free_size);
  465.     exit(1);
  466.     }
  467.  
  468.     nfree = 1;
  469.     memset(free, 0, sizeof(free));
  470.     memset(buf, 0, sizeof(buf));
  471.  
  472.     for (block = filsys.s_fsize - 1; block >= next_fill; --block) {
  473.     if (nfree == NICFREE) {
  474.         ((daddr_t *)buf)[0] = nfree;
  475.         memcpy(&((daddr_t *)buf)[1], free, sizeof(free));
  476.         write_block(block, buf);
  477.         nfree = 0;
  478.         memset(free, 0, sizeof(free));
  479.     }
  480.     free[nfree++] = block;
  481.     }
  482.  
  483.     filsys.s_nfree = nfree;
  484.     memcpy(&filsys.s_free, free, sizeof(free));
  485.     write_superblk();
  486. }
  487.