home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / mint / filesy~1 / mfsdefrg.zoo / defrag.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-18  |  13.3 KB  |  580 lines
  1. /*
  2.  * defrag.c - the Linux file system degragmenter.
  3.  * defrag.c,v 1.7 1993/01/07 14:48:48 linux Exp
  4.  *
  5.  * Copyright (C) 1992, 1993 Stephen Tweedie (sct@dcs.ed.ac.uk)
  6.  *
  7.  * Copyright (C) 1992 Remy Card (card@masi.ibp.fr) 
  8.  *
  9.  * Copyright (C) 1991 Linus Torvalds (torvalds@kruuna.helsinki.fi)
  10.  * 
  11.  * This file may be redistributed under the terms of the GNU General
  12.  * Public License.
  13.  *
  14.  * Based on efsck 0.9 alpha by Remy Card and Linus Torvalds.
  15.  * 
  16.  */
  17.  
  18. /* Modified for Minixfs/MiNT by S N Henson. 1993. */
  19.  
  20.  
  21. #include <stdlib.h>
  22. #include <stdio.h>
  23. #include <unistd.h>
  24. #include <string.h>
  25. #include <termios.h>
  26. #include <getopt.h>
  27. #include <fcntl.h>
  28. #include <sys/stat.h>
  29.  
  30. #include "defrag.h"
  31. #include "version.h"
  32.  
  33. #ifndef NODEBUG
  34. int debug = 0;
  35. #endif
  36.  
  37. char * device_name = NULL;
  38. int IN;
  39. int verbose = 0; 
  40. int show = 0;
  41. int show_version = 0;
  42. int test_disk = 0;
  43. int salvage = 0;
  44. int no_bad_inode = 0;
  45. int badblocks = 0;
  46. int readonly = 0;
  47. int changed = 0;
  48. int blocks_until_sync = 0;
  49.  
  50. Block next_block_to_fill = 0, first_zone = 0;
  51. unsigned int zones = 0, block_size = 0;
  52.  
  53. /* Global buffer variables */
  54. char * inode_buffer = NULL;
  55. char super_block_buffer[BLOCK_SIZE];
  56. char * inode_map = NULL;
  57. Block *inode_average_map = NULL;
  58. int *inode_order_map = NULL;
  59. #ifdef EXTFS
  60. char * bad_map = NULL;
  61. #endif
  62. Block *n2d_map = NULL, *d2n_map = NULL;
  63.  
  64. /* Local variables */
  65. static float sum_inode_zones;
  66. static int count_inode_blocks;
  67. static int used_inodes = 0;
  68.  
  69. /* optimise_zone : find the next destination block for the optimised data,
  70.    and swap the zone with the old contents of that block if necessary.
  71.    Only modify the relocation maps and (if necessary) the zone
  72.    pointer; don't move any data just yet. */
  73. void optimise_zone (Block *znr)
  74. {
  75.     Block ox, oy, nx, ny;
  76.  
  77.     if (debug)
  78.         printf ("DEBUG: optimise_zone (&%d)\n", *znr);
  79.     changed = 1;
  80.  
  81.     ox = *znr;
  82.     check_zone_nr(ox);
  83.  
  84. #ifdef EXTFS
  85.     /* Don't attempt to relocate a bad block! */
  86.     if (zone_is_bad(*znr))
  87.         return;
  88.     while (zone_is_bad(next_block_to_fill))
  89.         next_block_to_fill++;
  90. #endif
  91.  
  92.     ny = next_block_to_fill++;
  93.     check_zone_nr(ny);
  94.  
  95.     nx = d2n(ox);
  96.     oy = n2d(ny);
  97.  
  98.     /* Update the zone maps. */
  99.     d2n(ox) = ny;
  100.     if (oy)
  101.         d2n(oy) = nx;
  102.     n2d(nx) = oy;
  103.     n2d(ny) = ox;
  104.     if (!readonly)
  105.         *znr = ny;
  106. }
  107.  
  108. #ifndef NODEBUG
  109. void validate_relocation_maps()
  110. {
  111.     int i;
  112.     
  113.     for (i=first_zone; i < zones; i++)
  114.     {
  115.         if (n2d(i))
  116.             assert (d2n(n2d(i)) == i);
  117.         if (d2n(i))
  118.             assert (n2d(d2n(i)) == i);
  119.     }
  120. }
  121. #endif
  122.  
  123. /* walk_[ind_/dind_/tind_]zone - perform a tree walk over inode data zones.
  124.    return true iff the block is relocated.
  125.    Depending on the mode:
  126.    mode == WZ_BAD_BLOCKS: scan bad block inode to create bad zone map.
  127.    mode == WZ_SCAN:      scan inode to determine average occupied block.
  128.    mode == WZ_REMAP_IND:  optimise inode indirection zones
  129.    mode == WZ_REMAP_DATA: optimise inode data zones - by this time the inode
  130.               indirection zones will have been modified to
  131.               point to the new zone locations, although
  132.               the zones will not have moved; hence,
  133.               lookups through the indirection blocks will
  134.               have to be passed through the n2d
  135.               translation.
  136.  
  137.    Note - there is NEVER any need to perform that n2d lookup if we are
  138.    in readonly mode, since in that case the zone number changes never
  139.    get written to disk.
  140. */
  141.  
  142. static inline void update_inode_average (Block n)
  143. {
  144.     sum_inode_zones += n;
  145.     count_inode_blocks++;
  146. }
  147.  
  148. static int walk_zone (Block * znr, enum walk_zone_mode mode)
  149. {
  150.     if (!*znr)
  151.         return 0;
  152.     if (debug)
  153.         printf ("DEBUG: walk_zone(&%d, %d)\n", *znr, mode);
  154.     check_zone_nr(*znr);
  155.  
  156.     if (mode == WZ_SCAN)
  157.         update_inode_average(*znr);
  158.     
  159.     switch (mode)
  160.     {
  161. #ifdef EXTFS
  162.     case WZ_BAD_BLOCKS:
  163.         mark_bad(*znr);
  164. #endif
  165.     case WZ_SCAN:
  166.     case WZ_REMAP_IND:
  167.         break;
  168.     case WZ_REMAP_DATA:
  169.         optimise_zone(znr);
  170.         return 1;
  171.     }
  172.     return 0;
  173. }
  174.  
  175. static int walk_zone_ind (Block * znr, enum walk_zone_mode mode)
  176. {
  177.     static char blk[BLOCK_SIZE];
  178.     int i, result = 0, blk_chg = 0;
  179.  
  180.     if (!*znr)
  181.         return 0;
  182.     if (debug)
  183.         printf ("DEBUG: walk_zone_ind (&%d, %d)\n", *znr, mode);
  184.     check_zone_nr (*znr);
  185.  
  186.     if (mode == WZ_SCAN)
  187.         update_inode_average(*znr);
  188.     
  189.     if (mode == WZ_REMAP_DATA && !readonly)
  190.         read_current_block(n2d(*znr), blk);
  191.     else
  192.         read_current_block(*znr, blk);
  193.  
  194.     if (mode == WZ_REMAP_IND)
  195.     {
  196.         optimise_zone(znr);
  197.         result = 1;
  198.     }
  199.     
  200.     for (i = 0; i < INODES_PER_BLOCK; i++)
  201.         blk_chg |= walk_zone (i + (Block *) blk,
  202.                       mode);
  203.     /* The nodes beneath the single indirection block are data 
  204.        blocks, so the block will only be changed when mode == 
  205.        WZ_REMAP_DATA; in this case we need to pass the current 
  206.        "virtual" zone number through n2d_map to find the real zone 
  207.        number */
  208.     if (blk_chg && !readonly)
  209.         write_current_block (n2d(*znr), blk);
  210.     if (mode != WZ_REMAP_IND)
  211.         assert (!result);
  212.     if (mode != WZ_REMAP_DATA)
  213.         assert (!blk_chg);
  214.     return result;
  215. }
  216.  
  217. static int walk_zone_dind (Block * znr, enum walk_zone_mode mode)
  218. {
  219.     static char blk[BLOCK_SIZE];
  220.     int i, result = 0, blk_chg = 0;
  221.  
  222.     if (!*znr)
  223.         return 0;
  224.     if (debug)
  225.         printf ("DEBUG: walk_zone_dind (&%d, %d)\n", *znr, mode);
  226.     check_zone_nr (*znr);
  227.  
  228.     if (mode == WZ_SCAN)
  229.         update_inode_average(*znr);
  230.     
  231.     if (mode == WZ_REMAP_DATA && !readonly)
  232.         read_current_block(n2d(*znr), blk);
  233.     else
  234.         read_current_block(*znr, blk);
  235.     
  236.     if (mode == WZ_REMAP_IND)
  237.     {
  238.         optimise_zone(znr);
  239.         result = 1;
  240.     }
  241.  
  242.     for (i = 0; i < INODES_PER_BLOCK; i++)
  243.         blk_chg |= walk_zone_ind (i + (Block *) blk,
  244.                       mode);
  245.     /* By the time (during the WZ_REMAP_IND pass) that we come to 
  246.        rewrite this block after reallocating children indblocks, 
  247.        this current zone will have been optimised - so convert 
  248.        back to real disk blocks using the n2d map.  This also
  249.        applies to optimising triple indirection blocks below. */
  250.     if (blk_chg && !readonly)
  251.         write_current_block (n2d(*znr), blk);
  252.     if (mode != WZ_REMAP_IND)
  253.         assert ((!blk_chg) && (!result));
  254.     return result;
  255. }
  256.  
  257. #ifdef EXTFS
  258. static int walk_zone_tind (Block * znr, enum walk_zone_mode mode)
  259. {
  260.     static char blk[BLOCK_SIZE];
  261.     int i, result = 0, blk_chg = 0;
  262.  
  263.     if (!*znr)
  264.         return 0;
  265.     if (debug)
  266.         printf ("DEBUG: walk_zone_tind (&%d, %d)\n", *znr, mode);
  267.     check_zone_nr (*znr);
  268.  
  269.     if (mode == WZ_SCAN)
  270.         update_inode_average(*znr);
  271.     
  272.     if (mode == WZ_REMAP_DATA && !readonly)
  273.         read_current_block(n2d(*znr), blk);
  274.     else
  275.         read_current_block(*znr, blk);
  276.  
  277.     if (mode == WZ_REMAP_IND)
  278.     {
  279.         optimise_zone(znr);
  280.         result = 1;
  281.     }
  282.  
  283.     for (i = 0; i < INODES_PER_BLOCK; i++)
  284.         blk_chg |= walk_zone_dind (i + (Block *) blk, mode);
  285.     if (blk_chg && !readonly)
  286.         write_current_block (n2d(*znr), blk);
  287.     if (mode != WZ_REMAP_IND)
  288.         assert ((!blk_chg) && (!result));
  289.     return result;
  290. }
  291. #endif /* EXTFS */
  292.  
  293. void walk_inode (struct d_inode *inode, enum walk_zone_mode mode)
  294. {
  295.     int i;
  296.     
  297.     for (i = 0; i < DIRECT_ZONES ; i++)
  298.         walk_zone (i + inode->i_zone, mode);
  299.     walk_zone_ind (DIRECT_ZONES + inode->i_zone, mode);
  300.     walk_zone_dind ((DIRECT_ZONES+1) + inode->i_zone, mode);
  301. #ifdef EXTFS
  302.     walk_zone_tind ((DIRECT_ZONES+2) + inode->i_zone, mode);
  303. #endif
  304. }
  305.  
  306. #ifdef EXTFS
  307. void read_bad_zones (void)
  308. {
  309.     struct d_inode * inode = Inode + BAD_INO;
  310.  
  311.     if (debug)
  312.         printf ("DEBUG: read_bad_zones()\n");
  313.     if (inode->i_mode || inode->i_nlinks)
  314.         die ("disk does not have a badblock inode.");
  315.     if (!inode_in_use (BAD_INO))
  316.         die ("The badblock inode is on the free list.");
  317.  
  318.     walk_inode(inode, WZ_BAD_BLOCKS);
  319. }
  320. #endif /* EXTFS */
  321.  
  322. void optimise_inode (unsigned int i, int scan)
  323. {
  324.     struct d_inode * inode;
  325.  
  326.     if (debug)
  327.         printf ("DEBUG: optimise_inode(%d, %d)\n", i, scan);
  328.     inode = Inode + i;
  329.     if (!S_ISDIR (inode->i_mode) && !S_ISREG (inode->i_mode) &&
  330.         !S_ISLNK (inode->i_mode)
  331. #ifdef EXTFS
  332.         && (i != BAD_INO)
  333. #endif
  334.         )
  335.     {
  336.         inode_average_map[i] = 0;
  337.         return;
  338.     }
  339.     if (verbose > 1)
  340.     {
  341.         if (scan)
  342.             printf ("Scanning inode %d...", i);
  343.         else
  344.             printf ("Relocating inode %d...", i);
  345.     }
  346.     if (scan)
  347.     {
  348.         sum_inode_zones = 0.0;
  349.         count_inode_blocks = 0;
  350.         walk_inode(inode, WZ_SCAN);
  351.         if (count_inode_blocks)
  352.             inode_average_map[i] = 
  353.                 (Block) (sum_inode_zones / 
  354.                      (float) count_inode_blocks);
  355.         else
  356.             inode_average_map[i] = 0;
  357.     }
  358.     else
  359.     {
  360.         walk_inode(inode, WZ_REMAP_IND);
  361.         walk_inode(inode, WZ_REMAP_DATA);
  362.     }
  363.     if (verbose > 1)
  364.     {
  365.         if (scan)
  366.             printf (" %d block%s.", 
  367.                 count_inode_blocks,
  368.                 count_inode_blocks==1 ? "" : "s");
  369.         printf ("\n");
  370.     }
  371. }
  372.  
  373.  
  374. /* Scan the disk map.  For each inode, calculate the average of all
  375.    zone numbers occupied by that inode. */
  376. void scan_used_inodes()
  377. {
  378.     int i;
  379.  
  380.     if (debug)
  381.         printf ("DEBUG: scan_used_inodes()\n");
  382.     if (verbose)
  383.         printf ("Scanning inode zones...\n");
  384.     optimise_inode (ROOT_INO, 1);
  385.     for (i=FIRST_USER_INODE; i<=INODES; i++)
  386.           if (inode_in_use(i))
  387.             optimise_inode(i, 1);
  388. }
  389.  
  390. /* Optimise the disk map.  This involves passing twice over the
  391.    zone tree for each inode; once to allocate the new block to each
  392.    indirection block, once to allocate data blocks (and at the same
  393.    time modifying the indirection blocks to reflect the new map - but
  394.    we don't actually MOVE any data yet). */
  395. void optimise_used_inodes()
  396. {
  397.     int i;
  398.  
  399.     if (debug)
  400.         printf ("DEBUG: optimise_used_inodes()\n");
  401.     if (verbose)
  402.         printf ("Creating data relocation maps...\n");
  403.     for (i=0; i<used_inodes; i++)
  404.         optimise_inode(inode_order_map[i], 0);
  405. }
  406.  
  407. /* Sort the inodes in ascending order of average occupied block.  
  408.    Optimising inodes in this order should lead to blocks having to be
  409.    moved, on average, shorter distances on the disk.  This reduces the
  410.    typical time between rescuing a block and writing it to its final
  411.    destination, reducing the average size of the rescue pool. */
  412. static int compare_inodes (const void *a, const void *b)
  413. {
  414.     Block ave_a = inode_average_map[*((int*) a)];
  415.     Block ave_b = inode_average_map[*((int*) b)];
  416.     if (ave_a < ave_b)
  417.         return -1;
  418.     if (ave_a == ave_b)
  419.         return 0;
  420.     return 1;
  421. }
  422.  
  423. void sort_inodes (void)
  424. {
  425.     int i;
  426.  
  427.     if (debug)
  428.         printf ("DEBUG: sort_inodes()\n");
  429.     if (verbose)
  430.         printf ("Sorting inodes...\n");
  431.     
  432.     /* Initialise the inode order. */
  433.     used_inodes = 0;
  434.     inode_order_map[used_inodes++] = ROOT_INO;
  435. #ifdef EXTFS
  436.     inode_order_map[used_inodes++] = BAD_INO;
  437. #endif
  438.     for (i=FIRST_USER_INODE; i<=INODES; i++)
  439.     {
  440.         if (inode_in_use(i))
  441.             inode_order_map[used_inodes++] = i;
  442.     }
  443.     /* Artificially give root inode high priority; it will be the
  444.        first thing on the disk */
  445.     inode_average_map[ROOT_INO] = 0;
  446. #ifdef EXTFS
  447.     /* For extfs, we want the bad block inode's indirection blocks next */
  448.     inode_average_map[BAD_INO] = 1;
  449. #endif
  450.  
  451.     /* And sort... */
  452.     qsort (inode_order_map, used_inodes,
  453.            sizeof(*inode_order_map),
  454.            compare_inodes);
  455. }
  456.  
  457. int main (int argc, char ** argv)
  458. {
  459.     int i;
  460.     char c;
  461.  
  462.     printf ("%s %s\n", program_name, version);
  463.     if (argc && *argv)
  464.         program_name = *argv;
  465.     while ((c = getopt (argc, argv, 
  466.                 "vVrsp:"
  467. #ifndef NODEBUG
  468.                 "d"
  469. #endif
  470.                 )) != EOF)
  471.         switch (c)
  472.         {
  473.             case 'v': verbose++; break;
  474.             case 'V': show_version=1; break;
  475.             case 'r': readonly=1; show=1; break;
  476.             case 's': show=1; break;
  477.             case 'p': 
  478.             {
  479.                 pool_size = strtoul(optarg,0,10); 
  480.                 if (pool_size < 20)
  481.                     pool_size = 20;
  482.                 break;
  483.             }
  484. #ifndef NODEBUG
  485.             case 'd': debug=1; break;
  486. #endif
  487.             default: usage();
  488.         }
  489.     if (show_version)
  490.     {
  491.         printf ("CVS version %s\n", CVSID);
  492.     }
  493.     
  494.     if (optind != argc - 1)
  495.     {
  496.         if (show_version)
  497.             exit(0);
  498.         usage ();
  499.     }
  500.  
  501.     device_name = argv[optind];
  502.     if (readonly)
  503.         IN = open (device_name, O_RDONLY);
  504.     else
  505.         IN = open (device_name, O_RDWR);
  506.     if (IN < 0)
  507.         die("unable to open '%s'");
  508.     for (i = 0 ; i < 3; i++)
  509.         sync();
  510.     read_tables ();
  511.     init_buffer_tables ();
  512.     init_zone_maps ();
  513.     init_inode_bitmap ();
  514. #ifdef EXTFS
  515.     read_bad_zones ();
  516. #endif
  517.     next_block_to_fill = FIRSTZONE;
  518.     scan_used_inodes ();
  519.     sort_inodes ();
  520.     optimise_used_inodes ();
  521. #ifndef NODEBUG
  522.     validate_relocation_maps ();
  523. #endif
  524.     remap_disk_blocks ();
  525.     if (!readonly)
  526.     {
  527.         salvage_free_zones ();
  528.         write_tables ();
  529.         sync ();
  530.     }
  531.     if (show)
  532.     {
  533.         int free;
  534.  
  535. #ifdef MINIXFS
  536.         for (i=1,free=0 ; i<INODES ; i++)
  537.             if (!inode_in_use(i))
  538.                 free++;
  539. #else
  540.         free = FREEINODESCOUNT;
  541. #endif
  542.         printf ("\n%6d inode%s used (%d%%)\n", (INODES - free),
  543.             ((INODES - free) != 1) ? "s" : "",
  544.             100 * (INODES - free) / INODES);
  545.  
  546. #ifdef MINIXFS
  547.         for (i=FIRSTZONE,free=0 ; i<ZONES ; i++)
  548.             if (!zone_in_use(i))
  549.                 free++;
  550. #else
  551.         free = FREEBLOCKSCOUNT;
  552. #endif
  553.         printf ("%6d zone%s used (%d%%)\n"
  554. #ifdef EXTFS               
  555.             "%6d bad block%s\n"
  556. #endif
  557.             , (ZONES - free),
  558.             ((ZONES - free) != 1) ? "s" : "",
  559.             100 * (ZONES - free) / ZONES
  560. #ifdef EXTFS
  561.             , badblocks,
  562.             badblocks != 1 ? "s" : ""
  563. #endif
  564.             );
  565.  
  566.         printf ("\nRelocation statistics:\n");
  567.         printf ("%d buffer reads in %d group%s, of which:\n",
  568.             count_buffer_reads, count_read_groups,
  569.             count_read_groups==1 ? "" : "s");
  570.         printf ("  %d read-aheads.\n",
  571.             count_buffer_read_aheads);
  572.         printf ("%d buffer writes in %d group%s, of which:\n",
  573.             count_buffer_writes, count_write_groups,
  574.             count_write_groups==1 ? "" : "s");
  575.         printf ("  %d migrations, %d forces.\n",
  576.             count_buffer_migrates, count_buffer_forces);
  577.     }
  578.     return (0);
  579. }
  580.