"Fossies" - the Fresh Open Source Software Archive

Member "ntfsprogs-1.12.1/ntfsprogs/ntfsresize.c" (7 Oct 2005, 62318 Bytes) of package /linux/misc/old/ntfsprogs-1.12.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ntfsresize.c" see the Fossies "Dox" file reference documentation.

    1 /**
    2  * ntfsresize - Part of the Linux-NTFS project.
    3  *
    4  * Copyright (c) 2002-2005 Szabolcs Szakacsits
    5  * Copyright (c) 2002-2005 Anton Altaparmakov
    6  * Copyright (c) 2002-2003 Richard Russon
    7  *
    8  * This utility will resize an NTFS volume without data loss.
    9  *
   10  * WARNING FOR DEVELOPERS!!! Several external tools grep for text messages
   11  * to control execution thus if you would like to change any message
   12  * then PLEASE think twice before doing so then don't modify it. Thanks!
   13  *
   14  * This program is free software; you can redistribute it and/or modify
   15  * it under the terms of the GNU General Public License as published by
   16  * the Free Software Foundation; either version 2 of the License, or
   17  * (at your option) any later version.
   18  *
   19  * This program is distributed in the hope that it will be useful,
   20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   22  * GNU General Public License for more details.
   23  *
   24  * You should have received a copy of the GNU General Public License
   25  * along with this program (in the main directory of the Linux-NTFS
   26  * distribution in the file COPYING); if not, write to the Free Software
   27  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   28  */
   29 
   30 #include "config.h"
   31 
   32 #ifdef HAVE_UNISTD_H
   33 #include <unistd.h>
   34 #endif
   35 #ifdef HAVE_STDLIB_H
   36 #include <stdlib.h>
   37 #endif
   38 #ifdef HAVE_STDIO_H
   39 #include <stdio.h>
   40 #endif
   41 #ifdef HAVE_STDARG_H
   42 #include <stdarg.h>
   43 #endif
   44 #ifdef HAVE_STRING_H
   45 #include <string.h>
   46 #endif
   47 #ifdef HAVE_ERRNO_H
   48 #include <errno.h>
   49 #endif
   50 #ifdef HAVE_GETOPT_H
   51 #include <getopt.h>
   52 #endif
   53 
   54 #include "debug.h"
   55 #include "types.h"
   56 #include "support.h"
   57 #include "endians.h"
   58 #include "bootsect.h"
   59 #include "device.h"
   60 #include "attrib.h"
   61 #include "volume.h"
   62 #include "mft.h"
   63 #include "bitmap.h"
   64 #include "inode.h"
   65 #include "runlist.h"
   66 #include "utils.h"
   67 #include "version.h"
   68 
   69 static const char *EXEC_NAME = "ntfsresize";
   70 
   71 static const char *resize_warning_msg =
   72 "WARNING: Every sanity check passed and only the dangerous operations left.\n"
   73 "Make sure that important data has been backed up! Power outage or computer\n"
   74 "crash may result major data loss!\n";
   75 
   76 static const char *resize_important_msg =
   77 "You can go on to shrink the device for example with Linux fdisk.\n"
   78 "IMPORTANT: When recreating the partition, make sure that you\n"
   79 "  1)  create it at the same disk sector (use sector as the unit!)\n"
   80 "  2)  create it with the same partition type (usually 7, HPFS/NTFS)\n"
   81 "  3)  do not make it smaller than the new NTFS filesystem size\n"
   82 "  4)  set the bootable flag for the partition if it existed before\n"
   83 "Otherwise you won't be able to access NTFS or can't boot from the disk!\n"
   84 "If you make a mistake and don't have a partition table backup then you\n"
   85 "can recover the partition table by TestDisk or Parted's rescue mode.\n";
   86 
   87 static const char *invalid_ntfs_msg =
   88 "The device '%s' doesn't have a valid NTFS.\n"
   89 "Maybe you selected the wrong partition? Or the whole disk instead of a\n"
   90 "partition (e.g. /dev/hda, not /dev/hda1)? This error might also occur\n"
   91 "if the disk was incorrectly repartitioned (see the ntfsresize FAQ).\n";
   92 
   93 static const char *corrupt_volume_msg =
   94 "This software has detected that your NTFS is corrupted. Please run chkdsk /f\n"
   95 "on Windows then reboot it TWICE! Important, don't forget the /f parameter!\n"
   96 "Afterwards you can run ntfsresize. No modification was made to NTFS.\n";
   97 
   98 static const char *hibernated_volume_msg =
   99 "The NTFS partition is hibernated. Windows must be resumed and turned off\n"
  100 "properly, so resizing could be done safely.\n";
  101 
  102 static const char *unclean_journal_msg =
  103 "The NTFS journal file is unclean. Please shutdown Windows properly before\n"
  104 "using this software! Note, if you have run chkdsk previously then boot\n"
  105 "Windows again which will automatically initialize the journal correctly.\n";
  106 
  107 static const char *bad_sectors_warning_msg =
  108 "****************************************************************************\n"
  109 "* WARNING: The disk has bad sector. This means physical damage on the disk *\n"
  110 "* surface caused by deterioration, manufacturing faults or other reason.   *\n"
  111 "* The reliability of the disk may stay stable or degrade fast. We suggest  *\n"
  112 "* making a full backup urgently by running 'ntfsclone --rescue ...' then   *\n"
  113 "* run 'chkdsk /f /r' on Windows and rebooot it TWICE! Then you can resize  *\n"
  114 "* NTFS safely by additionally using the --bad-sectors option of ntfsresize.*\n"
  115 "****************************************************************************\n";
  116 
  117 struct {
  118     int verbose;
  119     int debug;
  120     int ro_flag;
  121     int force;
  122     int info;
  123     int show_progress;
  124     int badsectors;
  125     s64 bytes;
  126     char *volume;
  127 } opt;
  128 
  129 struct bitmap {
  130     s64 size;
  131     u8 *bm;
  132     u8 padding[4];      /* Unused: padding to 64 bit. */
  133 };
  134 
  135 #define NTFS_PROGBAR        0x0001
  136 #define NTFS_PROGBAR_SUPPRESS   0x0002
  137 
  138 struct progress_bar {
  139     u64 start;
  140     u64 stop;
  141     int resolution;
  142     int flags;
  143     float unit;
  144     u8 padding[4];      /* Unused: padding to 64 bit. */
  145 };
  146 
  147 struct llcn_t {
  148     s64 lcn;    /* last used LCN for a "special" file/attr type */
  149     s64 inode;  /* inode using it */
  150 };
  151 
  152 #define NTFSCK_PROGBAR      0x0001
  153 
  154 typedef struct {
  155     ntfs_inode *ni;          /* inode being processed */
  156     ntfs_attr_search_ctx *ctx;   /* inode attribute being processed */
  157     s64 inuse;           /* num of clusters in use */
  158     int multi_ref;           /* num of clusters referenced many times */
  159     int outsider;            /* num of clusters outside the volume */
  160     int show_outsider;       /* controls showing the above information */
  161     int flags;
  162     struct bitmap lcn_bitmap;
  163 } ntfsck_t;
  164 
  165 typedef struct {
  166     ntfs_volume *vol;
  167     ntfs_inode *ni;          /* inode being processed */
  168     s64 new_volume_size;         /* in clusters; 0 = --info w/o --size */
  169     MFT_REF mref;                /* mft reference */
  170     MFT_RECORD *mrec;            /* mft record */
  171     ntfs_attr_search_ctx *ctx;   /* inode attribute being processed */
  172     u64 relocations;         /* num of clusters to relocate */
  173     s64 inuse;           /* num of clusters in use */
  174     runlist mftmir_rl;       /* $MFTMirr AT_DATA's new position */
  175     s64 mftmir_old;          /* $MFTMirr AT_DATA's old LCN */
  176     int dirty_inode;         /* some inode data got relocated */
  177     int shrink;          /* shrink = 1, enlarge = 0 */
  178     s64 badclusters;         /* num of physically dead clusters */
  179     VCN mft_highest_vcn;         /* used for relocating the $MFT */
  180     struct progress_bar progress;
  181     struct bitmap lcn_bitmap;
  182     /* Temporary statistics until all case is supported */
  183     struct llcn_t last_mft;
  184     struct llcn_t last_mftmir;
  185     struct llcn_t last_multi_mft;
  186     struct llcn_t last_sparse;
  187     struct llcn_t last_compressed;
  188     struct llcn_t last_lcn;
  189     s64 last_unsupp;         /* last unsupported cluster */
  190 } ntfs_resize_t;
  191 
  192 /* FIXME: This, lcn_bitmap and pos from find_free_cluster() will make a cluster
  193    allocation related structure, attached to ntfs_resize_t */
  194 s64 max_free_cluster_range = 0;
  195 
  196 #define NTFS_MBYTE (1000 * 1000)
  197 
  198 /* WARNING: don't modify the text, external tools grep for it */
  199 #define ERR_PREFIX   "ERROR"
  200 #define PERR_PREFIX  ERR_PREFIX "(%d): "
  201 #define NERR_PREFIX  ERR_PREFIX ": "
  202 
  203 #define DIRTY_NONE      (0)
  204 #define DIRTY_INODE     (1)
  205 #define DIRTY_ATTRIB        (2)
  206 
  207 #define NTFS_MAX_CLUSTER_SIZE   (65536)
  208 
  209 GEN_PRINTF(Eprintf, stderr, NULL,         FALSE)
  210 GEN_PRINTF(Vprintf, stdout, &opt.verbose, TRUE)
  211 GEN_PRINTF(Qprintf, stdout, NULL,         FALSE)
  212 
  213 static s64 rounded_up_division(s64 numer, s64 denom)
  214 {
  215     return (numer + (denom - 1)) / denom;
  216 }
  217 
  218 /**
  219  * perr_printf
  220  *
  221  * Print an error message.
  222  */
  223 static void perr_printf(const char *fmt, ...)
  224         __attribute__((format(printf, 1, 2)));
  225 static void perr_printf(const char *fmt, ...)
  226 {
  227     va_list ap;
  228     int eo = errno;
  229 
  230     fprintf(stdout, PERR_PREFIX, eo);
  231     va_start(ap, fmt);
  232     vfprintf(stdout, fmt, ap);
  233     va_end(ap);
  234     fprintf(stdout, ": %s\n", strerror(eo));
  235     fflush(stdout);
  236     fflush(stderr);
  237 }
  238 
  239 static void err_printf(const char *fmt, ...)
  240         __attribute__((format(printf, 1, 2)));
  241 static void err_printf(const char *fmt, ...)
  242 {
  243     va_list ap;
  244 
  245     fprintf(stdout, NERR_PREFIX);
  246     va_start(ap, fmt);
  247     vfprintf(stdout, fmt, ap);
  248     va_end(ap);
  249     fflush(stdout);
  250     fflush(stderr);
  251 }
  252 
  253 /**
  254  * err_exit
  255  *
  256  * Print and error message and exit the program.
  257  */
  258 static int err_exit(const char *fmt, ...)
  259         __attribute__((noreturn))
  260         __attribute__((format(printf, 1, 2)));
  261 static int err_exit(const char *fmt, ...)
  262 {
  263     va_list ap;
  264 
  265     fprintf(stdout, NERR_PREFIX);
  266     va_start(ap, fmt);
  267     vfprintf(stdout, fmt, ap);
  268     va_end(ap);
  269     fflush(stdout);
  270     fflush(stderr);
  271     exit(1);
  272 }
  273 
  274 /**
  275  * perr_exit
  276  *
  277  * Print and error message and exit the program
  278  */
  279 static int perr_exit(const char *fmt, ...)
  280         __attribute__((noreturn))
  281         __attribute__((format(printf, 1, 2)));
  282 static int perr_exit(const char *fmt, ...)
  283 {
  284     va_list ap;
  285     int eo = errno;
  286 
  287     fprintf(stdout, PERR_PREFIX, eo);
  288     va_start(ap, fmt);
  289     vfprintf(stdout, fmt, ap);
  290     va_end(ap);
  291     printf(": %s\n", strerror(eo));
  292     fflush(stdout);
  293     fflush(stderr);
  294     exit(1);
  295 }
  296 
  297 /**
  298  * usage - Print a list of the parameters to the program
  299  *
  300  * Print a list of the parameters and options for the program.
  301  *
  302  * Return:  none
  303  */
  304 static void usage(void) __attribute__((noreturn));
  305 static void usage(void)
  306 {
  307 
  308     printf ("\nUsage: %s [OPTIONS] DEVICE\n"
  309         "    Resize an NTFS volume non-destructively, safely move any data if needed.\n"
  310         "\n"
  311         "    -i, --info             Estimate the smallest shrunken size possible\n"
  312         "    -s, --size SIZE        Resize volume to SIZE[k|M|G] bytes\n"
  313         "\n"
  314         "    -n, --no-action        Do not write to disk\n"
  315         "    -b, --bad-sectors      Support disks having bad sectors\n"
  316         "    -f, --force            Force to progress\n"
  317         "    -P, --no-progress-bar  Don't show progress bar\n"
  318         "    -v, --verbose          More output\n"
  319         "    -V, --version          Display version information\n"
  320         "    -h, --help             Display this help\n"
  321 #ifdef DEBUG
  322         "    -d, --debug            Show debug information\n"
  323 #endif
  324         "\n"
  325         "    The options -i and -s are mutually exclusive. If both options are\n"
  326         "    omitted then the NTFS volume will be enlarged to the DEVICE size.\n"
  327         "\n", EXEC_NAME);
  328     printf ("%s%s", ntfs_bugs, ntfs_home);
  329     printf ("Ntfsresize FAQ: http://linux-ntfs.sourceforge.net/info/ntfsresize.html\n");
  330     exit(1);
  331 }
  332 
  333 /**
  334  * proceed_question
  335  *
  336  * Force the user to confirm an action before performing it.
  337  * Copy-paste from e2fsprogs
  338  */
  339 static void proceed_question(void)
  340 {
  341     char buf[256];
  342     const char *short_yes = "yY";
  343 
  344     fflush(stdout);
  345     fflush(stderr);
  346     printf("Are you sure you want to proceed (y/[n])? ");
  347     buf[0] = 0;
  348     fgets(buf, sizeof(buf), stdin);
  349     if (strchr(short_yes, buf[0]) == 0) {
  350         printf("OK quitting. NO CHANGES have been made to your "
  351                 "NTFS volume.\n");
  352         exit(1);
  353     }
  354 }
  355 
  356 /**
  357  * version - Print version information about the program
  358  *
  359  * Print a copyright statement and a brief description of the program.
  360  *
  361  * Return:  none
  362  */
  363 static void version (void)
  364 {
  365     printf ("\nResize an NTFS Volume, without data loss.\n\n");
  366     printf ("Copyright (c) 2002-2005  Szabolcs Szakacsits\n");
  367     printf ("Copyright (c) 2002-2004  Anton Altaparmakov\n");
  368     printf ("Copyright (c) 2002-2003  Richard Russon\n");
  369     printf ("\n%s\n%s%s", ntfs_gpl, ntfs_bugs, ntfs_home);
  370 }
  371 
  372 /**
  373  * get_new_volume_size
  374  *
  375  * Convert a user-supplied string into a size.  Without any suffix the number
  376  * will be assumed to be in bytes.  If the number has a suffix of k, M or G it
  377  * will be scaled up by 1000, 1000000, or 1000000000.
  378  */
  379 static s64 get_new_volume_size(char *s)
  380 {
  381     s64 size;
  382     char *suffix;
  383     int prefix_kind = 1000;
  384 
  385     size = strtoll(s, &suffix, 10);
  386     if (size <= 0 || errno == ERANGE)
  387         err_exit("Illegal new volume size\n");
  388 
  389     if (!*suffix)
  390         return size;
  391 
  392     if (strlen(suffix) == 2 && suffix[1] == 'i')
  393         prefix_kind = 1024;
  394     else if (strlen(suffix) > 1)
  395         usage();
  396 
  397     /* We follow the SI prefixes:
  398        http://physics.nist.gov/cuu/Units/prefixes.html
  399        http://physics.nist.gov/cuu/Units/binary.html
  400        Disk partitioning tools use prefixes as,
  401                            k        M          G
  402        fdisk 2.11x-      2^10     2^20      10^3*2^20
  403        fdisk 2.11y+     10^3     10^6       10^9
  404        cfdisk           10^3     10^6       10^9
  405        sfdisk            2^10     2^20
  406        parted            2^10     2^20  (may change)
  407        fdisk (DOS)       2^10     2^20
  408     */
  409     /* FIXME: check for overflow */
  410     switch (*suffix) {
  411     case 'G':
  412         size *= prefix_kind;
  413     case 'M':
  414         size *= prefix_kind;
  415     case 'k':
  416         size *= prefix_kind;
  417         break;
  418     default:
  419         usage();
  420     }
  421 
  422     return size;
  423 }
  424 
  425 /**
  426  * parse_options - Read and validate the programs command line
  427  *
  428  * Read the command line, verify the syntax and parse the options.
  429  * This function is very long, but quite simple.
  430  *
  431  * Return:  1 Success
  432  *      0 Error, one or more problems
  433  */
  434 static int parse_options(int argc, char **argv)
  435 {
  436     static const char *sopt = "-bdfhinPs:vV";
  437     static const struct option lopt[] = {
  438         { "bad-sectors",no_argument,        NULL, 'b' },
  439 #ifdef DEBUG
  440         { "debug",  no_argument,        NULL, 'd' },
  441 #endif
  442         { "force",  no_argument,        NULL, 'f' },
  443         { "help",   no_argument,        NULL, 'h' },
  444         { "info",   no_argument,        NULL, 'i' },
  445         { "no-action",  no_argument,        NULL, 'n' },
  446         { "no-progress-bar", no_argument,   NULL, 'P' },
  447         { "size",   required_argument,  NULL, 's' },
  448         { "verbose",    no_argument,        NULL, 'v' },
  449         { "version",    no_argument,        NULL, 'V' },
  450         { NULL, 0, NULL, 0 }
  451     };
  452 
  453     char c;
  454     int err  = 0;
  455     int ver  = 0;
  456     int help = 0;
  457 
  458     memset(&opt, 0, sizeof(opt));
  459     opt.show_progress = 1;
  460 
  461     while ((c = getopt_long (argc, argv, sopt, lopt, NULL)) != (char)-1) {
  462         switch (c) {
  463         case 1: /* A non-option argument */
  464             if (!err && !opt.volume)
  465                 opt.volume = argv[optind-1];
  466             else
  467                 err++;
  468             break;
  469         case 'b':
  470             opt.badsectors++;
  471             break;
  472         case 'd':
  473             opt.debug++;
  474             break;
  475         case 'f':
  476             opt.force++;
  477             break;
  478         case 'h':
  479         case '?':
  480             help++;
  481             break;
  482         case 'i':
  483             opt.info++;
  484             break;
  485         case 'n':
  486             opt.ro_flag = MS_RDONLY;
  487             break;
  488         case 'P':
  489             opt.show_progress = 0;
  490             break;
  491         case 's':
  492             if (!err && (opt.bytes == 0))
  493                 opt.bytes = get_new_volume_size(optarg);
  494             else
  495                 err++;
  496             break;
  497         case 'v':
  498             opt.verbose++;
  499             break;
  500         case 'V':
  501             ver++;
  502             break;
  503         default:
  504             if (optopt == 's') {
  505                 Eprintf("Option '%s' requires an argument.\n", argv[optind-1]);
  506             } else {
  507                 Eprintf("Unknown option '%s'.\n", argv[optind-1]);
  508             }
  509             err++;
  510             break;
  511         }
  512     }
  513 
  514     if (!help && !ver) {
  515         if (opt.volume == NULL) {
  516             if (argc > 1)
  517                 Eprintf("You must specify exactly one device.\n");
  518             err++;
  519         }
  520         if (opt.info) {
  521             opt.ro_flag = MS_RDONLY;
  522             if (opt.bytes) {
  523                 Eprintf(NERR_PREFIX "Options --info and --size "
  524                     "can't be used together.\n");
  525                 usage();
  526             }
  527         }
  528     }
  529 
  530     stderr = stdout;
  531 
  532 #ifdef DEBUG
  533     if (!opt.debug)
  534         if (!(stderr = fopen("/dev/null", "rw")))
  535             perr_exit("Couldn't open /dev/null");
  536 #endif
  537 
  538     if (ver)
  539         version();
  540     if (help || err)
  541         usage();
  542 
  543     return (!err && !help && !ver);
  544 }
  545 
  546 static void print_advise(ntfs_volume *vol, s64 supp_lcn)
  547 {
  548     s64 old_b, new_b, freed_b, old_mb, new_mb, freed_mb;
  549 
  550     old_b = vol->nr_clusters * vol->cluster_size;
  551     old_mb = rounded_up_division(old_b, NTFS_MBYTE);
  552 
  553     /* Take the next supported cluster (free or relocatable)
  554        plus reserve a cluster for the backup boot sector */
  555     supp_lcn += 2;
  556 
  557     if (supp_lcn > vol->nr_clusters) {
  558         err_printf("Very rare fragmentation type detected. "
  559                "Sorry, it's not supported yet.\n"
  560                "Try to defragment your NTFS, perhaps it helps.\n");
  561         exit(1);
  562     }
  563 
  564     new_b = supp_lcn * vol->cluster_size;
  565     new_mb = rounded_up_division(new_b, NTFS_MBYTE);
  566     freed_b = (vol->nr_clusters - supp_lcn + 1) * vol->cluster_size;
  567     freed_mb = freed_b / NTFS_MBYTE;
  568 
  569     /* WARNING: don't modify the text, external tools grep for it */
  570     printf("You might resize at %lld bytes ", (long long)new_b);
  571     if ((new_mb * NTFS_MBYTE) < old_b)
  572         printf("or %lld MB ", (long long)new_mb);
  573 
  574     printf("(freeing ");
  575     if (freed_mb && (old_mb - new_mb))
  576         printf("%lld MB", (long long)(old_mb - new_mb));
  577     else
  578         printf("%lld bytes", (long long)freed_b);
  579     printf(").\n");
  580 
  581     printf("Please make a test run using both the -n and -s options "
  582            "before real resizing!\n");
  583 }
  584 
  585 static void rl_set(runlist *rl, VCN vcn, LCN lcn, s64 len)
  586 {
  587     rl->vcn = vcn;
  588     rl->lcn = lcn;
  589     rl->length = len;
  590 }
  591 
  592 static int rl_items(runlist *rl)
  593 {
  594     int i = 0;
  595 
  596     while (rl[i++].length)
  597         ;
  598 
  599     return i;
  600 }
  601 
  602 static void dump_run(runlist_element *r)
  603 {
  604     Vprintf(" %8lld  %8lld (0x%08llx)  %lld\n", (long long)r->vcn,
  605             (long long)r->lcn, (long long)r->lcn,
  606             (long long)r->length);
  607 }
  608 
  609 static void dump_runlist(runlist *rl)
  610 {
  611     while (rl->length)
  612         dump_run(rl++);
  613 }
  614 
  615 /**
  616  * nr_clusters_to_bitmap_byte_size
  617  *
  618  * Take the number of clusters in the volume and calculate the size of $Bitmap.
  619  * The size must be always a multiple of 8 bytes.
  620  */
  621 static s64 nr_clusters_to_bitmap_byte_size(s64 nr_clusters)
  622 {
  623     s64 bm_bsize;
  624 
  625     bm_bsize = rounded_up_division(nr_clusters, 8);
  626     bm_bsize = (bm_bsize + 7) & ~7;
  627 
  628     return bm_bsize;
  629 }
  630 
  631 static int str2unicode(const char *aname, ntfschar **ustr, int *len)
  632 {
  633     if (aname && ((*len = ntfs_mbstoucs(aname, ustr, 0)) == -1)) {
  634         perr_printf("Couldn't convert string to Unicode");
  635         return -1;
  636     }
  637 
  638     if (!*ustr || !*len) {
  639         *ustr = AT_UNNAMED;
  640         *len = 0;
  641     }
  642 
  643     return 0;
  644 }
  645 
  646 static int has_bad_sectors(ntfs_resize_t *resize, int is_inode)
  647 {
  648     int len, ret = 0;
  649     ntfschar *ustr = NULL;
  650     ATTR_RECORD *a = resize->ctx->attr;
  651 
  652     if (is_inode) {
  653         if (resize->ni->mft_no != FILE_BadClus)
  654             return 0;
  655     } else {
  656         if (resize->mref != FILE_BadClus)
  657             return 0;
  658     }
  659 
  660     if (str2unicode("$Bad", &ustr, &len) == -1)
  661         return -1;
  662 
  663     if (ustr && ntfs_names_are_equal(ustr, len,
  664             (ntfschar*)((u8*)a + le16_to_cpu(a->name_offset)),
  665             a->name_length, 0, NULL, 0))
  666         ret = 1;
  667 
  668     if (ustr != AT_UNNAMED)
  669         free(ustr);
  670 
  671     return ret;
  672 }
  673 
  674 static void collect_resize_constraints(ntfs_resize_t *resize, runlist *rl)
  675 {
  676     s64 inode, last_lcn;
  677     ATTR_FLAGS flags;
  678     ATTR_TYPES atype;
  679     struct llcn_t *llcn = NULL;
  680     int ret, supported = 0;
  681 
  682     last_lcn = rl->lcn + (rl->length - 1);
  683 
  684     inode = resize->ni->mft_no;
  685     flags = resize->ctx->attr->flags;
  686     atype = resize->ctx->attr->type;
  687 
  688     if ((ret = has_bad_sectors(resize, 1)) != 0) {
  689         if (ret == -1)
  690             exit(1);
  691         if (NInoAttrList(resize->ni))
  692             err_exit("Hopelessly many bad sectors! Not supported.");
  693         if (resize->badclusters == 0)
  694             printf("WARNING: The disk has bad sector! "
  695                    "This can cause reliability problems!\n");
  696         resize->badclusters += last_lcn - rl->lcn + 1;
  697         Vprintf("Bad clusters: %8lld - %lld\n", rl->lcn, last_lcn);
  698         return;
  699     }
  700     
  701     if (inode == FILE_Bitmap) {
  702         llcn = &resize->last_lcn;
  703         if (atype == AT_DATA && NInoAttrList(resize->ni))
  704             err_exit("Highly fragmented $Bitmap isn't supported yet.");
  705 
  706         supported = 1;
  707 
  708     } else if (inode == FILE_MFT) {
  709         llcn = &resize->last_mft;
  710         /*
  711          *  First run of $MFT AT_DATA isn't supported yet.
  712          */
  713         if (atype != AT_DATA || rl->vcn)
  714             supported = 1;
  715 
  716     } else if (NInoAttrList(resize->ni)) {
  717         llcn = &resize->last_multi_mft;
  718 
  719         if (inode != FILE_MFTMirr)
  720             supported = 1;
  721 
  722     } else if (flags & ATTR_IS_SPARSE) {
  723         llcn = &resize->last_sparse;
  724         supported = 1;
  725 
  726     } else if (flags & ATTR_IS_COMPRESSED) {
  727         llcn = &resize->last_compressed;
  728         supported = 1;
  729 
  730     } else if (inode == FILE_MFTMirr) {
  731         llcn = &resize->last_mftmir;
  732         supported = 1;
  733 
  734         /* Fragmented $MFTMirr DATA attribute isn't supported yet */
  735         if (atype == AT_DATA)
  736             if (rl[1].length != 0 || rl->vcn)
  737                 supported = 0;
  738     } else {
  739         llcn = &resize->last_lcn;
  740         supported = 1;
  741     }
  742 
  743     if (llcn->lcn < last_lcn) {
  744         llcn->lcn = last_lcn;
  745         llcn->inode = inode;
  746     }
  747 
  748     if (supported)
  749         return;
  750 
  751     if (resize->last_unsupp < last_lcn)
  752         resize->last_unsupp = last_lcn;
  753 }
  754 
  755 
  756 static void collect_relocation_info(ntfs_resize_t *resize, runlist *rl)
  757 {
  758     s64 lcn, lcn_length, start, len, inode;
  759     s64 new_vol_size;   /* (last LCN on the volume) + 1 */
  760 
  761     lcn = rl->lcn;
  762     lcn_length = rl->length;
  763     inode = resize->ni->mft_no;
  764     new_vol_size = resize->new_volume_size;
  765 
  766     if (lcn + lcn_length <= new_vol_size)
  767         return;
  768 
  769     if (inode == FILE_Bitmap && resize->ctx->attr->type == AT_DATA)
  770         return;
  771     
  772     start = lcn;
  773     len = lcn_length;
  774 
  775     if (lcn < new_vol_size) {
  776         start = new_vol_size;
  777         len = lcn_length - (new_vol_size - lcn);
  778 
  779         if (!opt.info && (inode == FILE_MFTMirr)) {
  780             err_printf("$MFTMirr can't be split up yet. Please try "
  781                    "a different size.\n");
  782             print_advise(resize->vol, lcn + lcn_length - 1);
  783             exit(1);
  784         }
  785     }
  786 
  787     resize->relocations += len;
  788 
  789     if (!opt.info || !resize->new_volume_size)
  790         return;
  791 
  792     printf("Relocation needed for inode %8lld attr 0x%x LCN 0x%08llx "
  793             "length %6lld\n", (long long)inode,
  794             (unsigned int)le32_to_cpu(resize->ctx->attr->type),
  795             (unsigned long long)start, (long long)len);
  796 }
  797 
  798 /**
  799  * build_lcn_usage_bitmap
  800  *
  801  * lcn_bitmap has one bit for each cluster on the disk.  Initially, lcn_bitmap
  802  * has no bits set.  As each attribute record is read the bits in lcn_bitmap are
  803  * checked to ensure that no other file already references that cluster.
  804  *
  805  * This serves as a rudimentary "chkdsk" operation.
  806  */
  807 static void build_lcn_usage_bitmap(ntfs_volume *vol, ntfsck_t *fsck)
  808 {
  809     s64 inode;
  810     ATTR_RECORD *a;
  811     runlist *rl;
  812     int i, j;
  813     struct bitmap *lcn_bitmap = &fsck->lcn_bitmap;
  814 
  815     a = fsck->ctx->attr;
  816     inode = fsck->ni->mft_no;
  817 
  818     if (!a->non_resident)
  819         return;
  820 
  821     if (!(rl = ntfs_mapping_pairs_decompress(vol, a, NULL))) {
  822         int err = errno;
  823         perr_printf("ntfs_decompress_mapping_pairs");
  824         if (err == EIO)
  825             printf("%s", corrupt_volume_msg);
  826         exit(1);
  827     }
  828 
  829 
  830     for (i = 0; rl[i].length; i++) {
  831         s64 lcn = rl[i].lcn;
  832         s64 lcn_length = rl[i].length;
  833 
  834         /* CHECKME: LCN_RL_NOT_MAPPED check isn't needed */
  835         if (lcn == LCN_HOLE || lcn == LCN_RL_NOT_MAPPED)
  836             continue;
  837 
  838         /* FIXME: ntfs_mapping_pairs_decompress should return error */
  839         if (lcn < 0 || lcn_length <= 0)
  840             err_exit("Corrupt runlist in inode %lld attr %x LCN "
  841                  "%llx length %llx\n", inode,
  842                  (unsigned int)le32_to_cpu(a->type), lcn,
  843                  lcn_length);
  844 
  845         for (j = 0; j < lcn_length; j++) {
  846 
  847             u64 k = (u64)lcn + j;
  848 
  849             if (k >= (u64)vol->nr_clusters) {
  850 
  851                 long long outsiders = lcn_length - j;
  852 
  853                 fsck->outsider += outsiders;
  854 
  855                 if (++fsck->show_outsider <= 10 || opt.verbose)
  856                     printf("Outside of the volume reference"
  857                            " for inode %lld at %lld:%lld\n",
  858                            inode, (long long)k, outsiders);
  859 
  860                 break;
  861             }
  862 
  863             if (ntfs_bit_get_and_set(lcn_bitmap->bm, k, 1)) {
  864                 if (++fsck->multi_ref <= 10 || opt.verbose)
  865                     printf("Cluster %lld is referenced "
  866                            "multiply times!\n",
  867                            (long long)k);
  868                 continue;
  869             }
  870         }
  871         fsck->inuse += lcn_length;
  872     }
  873     free(rl);
  874 }
  875 
  876 
  877 static ntfs_attr_search_ctx *attr_get_search_ctx(ntfs_inode *ni, MFT_RECORD *mrec)
  878 {
  879     ntfs_attr_search_ctx *ret;
  880 
  881     if ((ret = ntfs_attr_get_search_ctx(ni, mrec)) == NULL)
  882         perr_printf("ntfs_attr_get_search_ctx");
  883 
  884     return ret;
  885 }
  886 
  887 /**
  888  * walk_attributes
  889  *
  890  * For a given MFT Record, iterate through all its attributes.  Any non-resident
  891  * data runs will be marked in lcn_bitmap.
  892  */
  893 static int walk_attributes(ntfs_volume *vol, ntfsck_t *fsck)
  894 {
  895     if (!(fsck->ctx = attr_get_search_ctx(fsck->ni, NULL)))
  896         return -1;
  897 
  898     while (!ntfs_attrs_walk(fsck->ctx)) {
  899         if (fsck->ctx->attr->type == AT_END)
  900             break;
  901         build_lcn_usage_bitmap(vol, fsck);
  902     }
  903 
  904     ntfs_attr_put_search_ctx(fsck->ctx);
  905     return 0;
  906 }
  907 
  908 /**
  909  * compare_bitmaps
  910  *
  911  * Compare two bitmaps.  In this case, $Bitmap as read from the disk and
  912  * lcn_bitmap which we built from the MFT Records.
  913  */
  914 static void compare_bitmaps(ntfs_volume *vol, struct bitmap *a)
  915 {
  916     s64 i, pos, count;
  917     int mismatch = 0;
  918     int backup_boot = 0;
  919     u8 bm[NTFS_BUF_SIZE];
  920 
  921     printf("Accounting clusters ...\n");
  922 
  923     pos = 0;
  924     while (1) {
  925         count = ntfs_attr_pread(vol->lcnbmp_na, pos, NTFS_BUF_SIZE, bm);
  926         if (count == -1)
  927             perr_exit("Couldn't get $Bitmap $DATA");
  928 
  929         if (count == 0) {
  930             if (a->size > pos)
  931                 err_exit("$Bitmap size is smaller than expected"
  932                      " (%lld != %lld)\n", a->size, pos);
  933             break;
  934         }
  935 
  936         for (i = 0; i < count; i++, pos++) {
  937             s64 cl;  /* current cluster */
  938 
  939             if (a->size <= pos)
  940                 goto done;
  941 
  942             if (a->bm[pos] == bm[i])
  943                 continue;
  944 
  945             for (cl = pos * 8; cl < (pos + 1) * 8; cl++) {
  946                 char bit;
  947 
  948                 bit = ntfs_bit_get(a->bm, cl);
  949                 if (bit == ntfs_bit_get(bm, i * 8 + cl % 8))
  950                     continue;
  951 
  952                 if (!mismatch && !bit && !backup_boot &&
  953                         cl == vol->nr_clusters / 2) {
  954                     /* FIXME: call also boot sector check */
  955                     backup_boot = 1;
  956                     printf("Found backup boot sector in "
  957                            "the middle of the volume.\n");
  958                     continue;
  959                 }
  960 
  961                 if (++mismatch > 10)
  962                     continue;
  963 
  964                 printf("Cluster accounting failed at %lld "
  965                         "(0x%llx): %s cluster in "
  966                         "$Bitmap\n", (long long)cl,
  967                         (unsigned long long)cl,
  968                         bit ? "missing" : "extra");
  969             }
  970         }
  971     }
  972 done:
  973     if (mismatch) {
  974         err_printf("Filesystem check failed! Totally %d cluster "
  975                "accounting mismatches.\n", mismatch);
  976         printf("%s", corrupt_volume_msg);
  977         exit(1);
  978     }
  979 }
  980 
  981 /**
  982  * progress_init
  983  *
  984  * Create and scale our progress bar.
  985  */
  986 static void progress_init(struct progress_bar *p, u64 start, u64 stop, int flags)
  987 {
  988     p->start = start;
  989     p->stop = stop;
  990     p->unit = 100.0 / (stop - start);
  991     p->resolution = 100;
  992     p->flags = flags;
  993 }
  994 
  995 /**
  996  * progress_update
  997  *
  998  * Update the progress bar and tell the user.
  999  */
 1000 static void progress_update(struct progress_bar *p, u64 current)
 1001 {
 1002     float percent;
 1003 
 1004     if (!(p->flags & NTFS_PROGBAR))
 1005         return;
 1006     if (p->flags & NTFS_PROGBAR_SUPPRESS)
 1007         return;
 1008 
 1009     /* WARNING: don't modify the texts, external tools grep for them */
 1010     percent = p->unit * current;
 1011     if (current != p->stop) {
 1012         if ((current - p->start) % p->resolution)
 1013             return;
 1014         printf("%6.2f percent completed\r", percent);
 1015     } else
 1016         printf("100.00 percent completed\n");
 1017     fflush(stdout);
 1018 }
 1019 
 1020 static int inode_close(ntfs_inode *ni)
 1021 {
 1022     if (ntfs_inode_close(ni)) {
 1023         perr_printf("ntfs_inode_close for inode %llu",
 1024                 (unsigned long long)ni->mft_no);
 1025         return -1;
 1026     }
 1027     return 0;
 1028 }
 1029 
 1030 /**
 1031  * walk_inodes
 1032  *
 1033  * Read each record in the MFT, skipping the unused ones, and build up a bitmap
 1034  * from all the non-resident attributes.
 1035  */
 1036 static int build_allocation_bitmap(ntfs_volume *vol, ntfsck_t *fsck)
 1037 {
 1038     s64 nr_mft_records, inode = 0;
 1039     ntfs_inode *ni;
 1040     struct progress_bar progress;
 1041     int pb_flags = 0;   /* progress bar flags */
 1042 
 1043     /* WARNING: don't modify the text, external tools grep for it */
 1044     printf("Checking filesystem consistency ...\n");
 1045 
 1046     if (fsck->flags & NTFSCK_PROGBAR)
 1047         pb_flags |= NTFS_PROGBAR;
 1048 
 1049     nr_mft_records = vol->mft_na->initialized_size >>
 1050             vol->mft_record_size_bits;
 1051 
 1052     progress_init(&progress, inode, nr_mft_records - 1, pb_flags);
 1053 
 1054     for (; inode < nr_mft_records; inode++) {
 1055         progress_update(&progress, inode);
 1056 
 1057         if ((ni = ntfs_inode_open(vol, (MFT_REF)inode)) == NULL) {
 1058             /* FIXME: continue only if it make sense, e.g.
 1059                MFT record not in use based on $MFT bitmap */
 1060             if (errno == EIO || errno == ENOENT)
 1061                 continue;
 1062             perr_printf("Reading inode %lld failed", inode);
 1063             return -1;
 1064         }
 1065 
 1066         if (ni->mrec->base_mft_record)
 1067             goto close_inode;
 1068 
 1069         fsck->ni = ni;
 1070         if (walk_attributes(vol, fsck) != 0) {
 1071             inode_close(ni);
 1072             return -1;
 1073         }
 1074 close_inode:
 1075         if (inode_close(ni) != 0)
 1076             return -1;
 1077     }
 1078     return 0;
 1079 }
 1080 
 1081 static void build_resize_constraints(ntfs_resize_t *resize)
 1082 {
 1083     s64 i;
 1084     runlist *rl;
 1085 
 1086     if (!resize->ctx->attr->non_resident)
 1087         return;
 1088 
 1089     if (!(rl = ntfs_mapping_pairs_decompress(resize->vol,
 1090                          resize->ctx->attr, NULL)))
 1091         perr_exit("ntfs_decompress_mapping_pairs");
 1092 
 1093     for (i = 0; rl[i].length; i++) {
 1094         /* CHECKME: LCN_RL_NOT_MAPPED check isn't needed */
 1095         if (rl[i].lcn == LCN_HOLE || rl[i].lcn == LCN_RL_NOT_MAPPED)
 1096             continue;
 1097 
 1098         collect_resize_constraints(resize, rl + i);
 1099         if (resize->shrink)
 1100             collect_relocation_info(resize, rl + i);
 1101     }
 1102     free(rl);
 1103 }
 1104 
 1105 static void resize_constraints_by_attributes(ntfs_resize_t *resize)
 1106 {
 1107     if (!(resize->ctx = attr_get_search_ctx(resize->ni, NULL)))
 1108         exit(1);
 1109 
 1110     while (!ntfs_attrs_walk(resize->ctx)) {
 1111         if (resize->ctx->attr->type == AT_END)
 1112             break;
 1113         build_resize_constraints(resize);
 1114     }
 1115 
 1116     ntfs_attr_put_search_ctx(resize->ctx);
 1117 }
 1118 
 1119 static void set_resize_constraints(ntfs_resize_t *resize)
 1120 {
 1121     s64 nr_mft_records, inode;
 1122     ntfs_inode *ni;
 1123 
 1124     printf("Collecting resizing constraints ...\n");
 1125 
 1126     nr_mft_records = resize->vol->mft_na->initialized_size >>
 1127             resize->vol->mft_record_size_bits;
 1128 
 1129     for (inode = 0; inode < nr_mft_records; inode++) {
 1130 
 1131         ni = ntfs_inode_open(resize->vol, (MFT_REF)inode);
 1132         if (ni == NULL) {
 1133             if (errno == EIO || errno == ENOENT)
 1134                 continue;
 1135             perr_exit("Reading inode %lld failed", inode);
 1136         }
 1137 
 1138         if (ni->mrec->base_mft_record)
 1139             goto close_inode;
 1140 
 1141         resize->ni = ni;
 1142         resize_constraints_by_attributes(resize);
 1143 close_inode:
 1144         if (inode_close(ni) != 0)
 1145             exit(1);
 1146     }
 1147 }
 1148 
 1149 static void rl_fixup(runlist **rl)
 1150 {
 1151     runlist *tmp = *rl;
 1152 
 1153     if (tmp->lcn == LCN_RL_NOT_MAPPED) {
 1154         s64 unmapped_len = tmp->length;
 1155 
 1156         Vprintf("Skip unmapped run at the beginning ...\n");
 1157 
 1158         if (!tmp->length)
 1159             err_exit("Empty unmapped runlist! Please report!\n");
 1160         (*rl)++;
 1161         for (tmp = *rl; tmp->length; tmp++)
 1162             tmp->vcn -= unmapped_len;
 1163     }
 1164 
 1165     for (tmp = *rl; tmp->length; tmp++) {
 1166         if (tmp->lcn == LCN_RL_NOT_MAPPED) {
 1167             Vprintf("Skip unmapped run at the end  ...\n");
 1168 
 1169             if (tmp[1].length)
 1170                 err_exit("Unmapped runlist in the middle! "
 1171                      "Please report!\n");
 1172             tmp->lcn = LCN_ENOENT;
 1173             tmp->length = 0;
 1174         }
 1175     }
 1176 }
 1177 
 1178 static void replace_attribute_runlist(ntfs_volume *vol,
 1179                       ntfs_attr_search_ctx *ctx,
 1180                       runlist *rl)
 1181 {
 1182     int mp_size, l;
 1183     void *mp;
 1184     ATTR_RECORD *a = ctx->attr;
 1185 
 1186     rl_fixup(&rl);
 1187 
 1188     if ((mp_size = ntfs_get_size_for_mapping_pairs(vol, rl, 0)) == -1)
 1189         perr_exit("ntfs_get_size_for_mapping_pairs");
 1190 
 1191     if (a->name_length) {
 1192         u16 name_offs = le16_to_cpu(a->name_offset);
 1193         u16 mp_offs = le16_to_cpu(a->mapping_pairs_offset);
 1194 
 1195         if (name_offs >= mp_offs)
 1196             err_exit("Attribute name is after mapping pairs! "
 1197                  "Please report!\n");
 1198     }
 1199 
 1200     /* CHECKME: don't trust mapping_pairs is always the last item in the
 1201        attribute, instead check for the real size/space */
 1202     l = (int)le32_to_cpu(a->length) - le16_to_cpu(a->mapping_pairs_offset);
 1203     if (mp_size > l) {
 1204         s64 remains_size;
 1205         char *next_attr;
 1206 
 1207         Vprintf("Enlarging attribute header ...\n");
 1208 
 1209         mp_size = (mp_size + 7) & ~7;
 1210 
 1211         Vprintf("Old mp size      : %d\n", l);
 1212         Vprintf("New mp size      : %d\n", mp_size);
 1213         Vprintf("Bytes in use     : %u\n", (unsigned int)
 1214                 le32_to_cpu(ctx->mrec->bytes_in_use));
 1215 
 1216         next_attr = (char *)a + le16_to_cpu(a->length);
 1217         l = mp_size - l;
 1218 
 1219         Vprintf("Bytes in use new : %u\n", l + (unsigned int)
 1220                 le32_to_cpu(ctx->mrec->bytes_in_use));
 1221         Vprintf("Bytes allocated  : %u\n", (unsigned int)
 1222                 le32_to_cpu(ctx->mrec->bytes_allocated));
 1223 
 1224         remains_size = le32_to_cpu(ctx->mrec->bytes_in_use);
 1225         remains_size -= (next_attr - (char *)ctx->mrec);
 1226 
 1227         Vprintf("increase         : %d\n", l);
 1228         Vprintf("shift            : %lld\n", (long long)remains_size);
 1229 
 1230         if (le32_to_cpu(ctx->mrec->bytes_in_use) + l >
 1231                 le32_to_cpu(ctx->mrec->bytes_allocated))
 1232             err_exit("Extended record needed (%u > %u), not yet "
 1233                  "supported!\nPlease try to free less space.\n",
 1234                  (unsigned int)le32_to_cpu(ctx->mrec->
 1235                     bytes_in_use) + l,
 1236                  (unsigned int)le32_to_cpu(ctx->mrec->
 1237                     bytes_allocated));
 1238 
 1239         memmove(next_attr + l, next_attr, remains_size);
 1240         ctx->mrec->bytes_in_use = cpu_to_le32(l +
 1241                 le32_to_cpu(ctx->mrec->bytes_in_use));
 1242         a->length += l;
 1243     }
 1244 
 1245     if (!(mp = calloc(1, mp_size)))
 1246         perr_exit("Couldn't get memory");
 1247 
 1248     if (ntfs_mapping_pairs_build(vol, mp, mp_size, rl, 0, NULL))
 1249         perr_exit("ntfs_mapping_pairs_build");
 1250 
 1251     memmove((u8*)a + le16_to_cpu(a->mapping_pairs_offset), mp, mp_size);
 1252 
 1253     free(mp);
 1254 }
 1255 
 1256 static void set_bitmap_range(struct bitmap *bm, s64 pos, s64 length, u8 bit)
 1257 {
 1258     while (length--)
 1259         ntfs_bit_set(bm->bm, pos++, bit);
 1260 }
 1261 
 1262 static void set_bitmap_clusters(struct bitmap *bm, runlist *rl, u8 bit)
 1263 {
 1264     for (; rl->length; rl++)
 1265         set_bitmap_range(bm, rl->lcn, rl->length, bit);
 1266 }
 1267 
 1268 static void release_bitmap_clusters(struct bitmap *bm, runlist *rl)
 1269 {
 1270     max_free_cluster_range = 0;
 1271     set_bitmap_clusters(bm, rl, 0);
 1272 }
 1273 
 1274 static void set_max_free_zone(s64 length, s64 end, runlist_element *rle)
 1275 {
 1276     if (length > rle->length) {
 1277         rle->lcn = end - length;
 1278         rle->length = length;
 1279     }
 1280 }
 1281 
 1282 static int find_free_cluster(struct bitmap *bm,
 1283                  runlist_element *rle,
 1284                  s64 nr_vol_clusters,
 1285                  int hint)
 1286 {
 1287     /* FIXME: get rid of this 'static' variable */
 1288     static s64 pos = 0;
 1289     s64 i, items = rle->length;
 1290     s64 free_zone = 0;
 1291 
 1292     if (pos >= nr_vol_clusters)
 1293         pos = 0;
 1294     if (!max_free_cluster_range)
 1295         max_free_cluster_range = nr_vol_clusters;
 1296     rle->lcn = rle->length = 0;
 1297     if (hint)
 1298         pos = nr_vol_clusters / 2;
 1299     i = pos;
 1300 
 1301     do {
 1302         if (!ntfs_bit_get(bm->bm, i)) {
 1303             if (++free_zone == items) {
 1304                 set_max_free_zone(free_zone, i + 1, rle);
 1305                 break;
 1306             }
 1307         } else {
 1308             set_max_free_zone(free_zone, i, rle);
 1309             free_zone = 0;
 1310         }
 1311         if (++i == nr_vol_clusters) {
 1312             set_max_free_zone(free_zone, i, rle);
 1313             i = free_zone = 0;
 1314         }
 1315         if (rle->length == max_free_cluster_range)
 1316             break;
 1317     } while (i != pos);
 1318 
 1319     if (i)
 1320         set_max_free_zone(free_zone, i, rle);
 1321 
 1322     if (!rle->lcn) {
 1323         errno = ENOSPC;
 1324         return -1;
 1325     }
 1326     if (rle->length < items && rle->length < max_free_cluster_range) {
 1327         max_free_cluster_range = rle->length;
 1328         Vprintf("Max free range: %7lld     \n",
 1329                 (long long)max_free_cluster_range);
 1330     }
 1331     pos = rle->lcn + items;
 1332     if (pos == nr_vol_clusters)
 1333         pos = 0;
 1334 
 1335     set_bitmap_range(bm, rle->lcn, rle->length, 1);
 1336     return 0;
 1337 }
 1338 
 1339 static runlist *alloc_cluster(struct bitmap *bm,
 1340                   s64 items,
 1341                   s64 nr_vol_clusters,
 1342                   int hint)
 1343 {
 1344     runlist_element rle;
 1345     runlist *rl = NULL;
 1346     int rl_size, runs = 0;
 1347     s64 vcn = 0;
 1348 
 1349     if (items <= 0) {
 1350         errno = EINVAL;
 1351         return NULL;
 1352     }
 1353 
 1354     while (items > 0) {
 1355 
 1356         if (runs)
 1357             hint = 0;
 1358         rle.length = items;
 1359         if (find_free_cluster(bm, &rle, nr_vol_clusters, hint) == -1)
 1360             return NULL;
 1361 
 1362         rl_size = (runs + 2) * sizeof(runlist_element);
 1363         if (!(rl = (runlist *)realloc(rl, rl_size)))
 1364             return NULL;
 1365 
 1366         rl_set(rl + runs, vcn, rle.lcn, rle.length);
 1367 
 1368         vcn += rle.length;
 1369         items -= rle.length;
 1370         runs++;
 1371     }
 1372 
 1373     rl_set(rl + runs, vcn, -1LL, 0LL);
 1374 
 1375     if (runs > 1) {
 1376         Vprintf("Multi-run allocation:    \n");
 1377         dump_runlist(rl);
 1378     }
 1379     return rl;
 1380 }
 1381 
 1382 static int read_all(struct ntfs_device *dev, void *buf, int count)
 1383 {
 1384     int i;
 1385 
 1386     while (count > 0) {
 1387 
 1388         i = count;
 1389         if (!NDevReadOnly(dev))
 1390             i = dev->d_ops->read(dev, buf, count);
 1391 
 1392         if (i < 0) {
 1393             if (errno != EAGAIN && errno != EINTR)
 1394                 return -1;
 1395         } else if (i > 0) {
 1396             count -= i;
 1397             buf = i + (char *)buf;
 1398         } else
 1399             err_exit("Unexpected end of file!\n");
 1400     }
 1401     return 0;
 1402 }
 1403 
 1404 static int write_all(struct ntfs_device *dev, void *buf, int count)
 1405 {
 1406     int i;
 1407 
 1408     while (count > 0) {
 1409 
 1410         i = count;
 1411         if (!NDevReadOnly(dev))
 1412             i = dev->d_ops->write(dev, buf, count);
 1413 
 1414         if (i < 0) {
 1415             if (errno != EAGAIN && errno != EINTR)
 1416                 return -1;
 1417         } else {
 1418             count -= i;
 1419             buf = i + (char *)buf;
 1420         }
 1421     }
 1422     return 0;
 1423 }
 1424 
 1425 /**
 1426  * write_mft_record
 1427  *
 1428  * Write an MFT Record back to the disk.  If the read-only command line option
 1429  * was given, this function will do nothing.
 1430  */
 1431 static int write_mft_record(ntfs_volume *v, const MFT_REF mref, MFT_RECORD *buf)
 1432 {
 1433     if (ntfs_mft_record_write(v, mref, buf))
 1434         perr_exit("ntfs_mft_record_write");
 1435 
 1436 //  if (v->dev->d_ops->sync(v->dev) == -1)
 1437 //      perr_exit("Failed to sync device");
 1438 
 1439     return 0;
 1440 }
 1441 
 1442 static void lseek_to_cluster(ntfs_volume *vol, s64 lcn)
 1443 {
 1444     off_t pos;
 1445 
 1446     pos = (off_t)(lcn * vol->cluster_size);
 1447 
 1448     if (vol->dev->d_ops->seek(vol->dev, pos, SEEK_SET) == (off_t)-1)
 1449         perr_exit("seek failed to position %lld", lcn);
 1450 }
 1451 
 1452 static void copy_clusters(ntfs_resize_t *resize, s64 dest, s64 src, s64 len)
 1453 {
 1454     s64 i;
 1455     char buff[NTFS_MAX_CLUSTER_SIZE]; /* overflow checked at mount time */
 1456     ntfs_volume *vol = resize->vol;
 1457 
 1458     for (i = 0; i < len; i++) {
 1459 
 1460         lseek_to_cluster(vol, src + i);
 1461 
 1462         if (read_all(vol->dev, buff, vol->cluster_size) == -1)
 1463             perr_exit("read_all");
 1464 
 1465         lseek_to_cluster(vol, dest + i);
 1466 
 1467         if (write_all(vol->dev, buff, vol->cluster_size) == -1)
 1468             perr_exit("write_all");
 1469 
 1470         resize->relocations++;
 1471         progress_update(&resize->progress, resize->relocations);
 1472     }
 1473 }
 1474 
 1475 static void relocate_clusters(ntfs_resize_t *r, runlist *dest_rl, s64 src_lcn)
 1476 {
 1477     /* collect_shrink_constraints() ensured $MFTMir DATA is one run */
 1478     if (r->mref == FILE_MFTMirr && r->ctx->attr->type == AT_DATA) {
 1479         if (!r->mftmir_old) {
 1480             r->mftmir_rl.lcn = dest_rl->lcn;
 1481             r->mftmir_rl.length = dest_rl->length;
 1482             r->mftmir_old = src_lcn;
 1483         } else
 1484             err_exit("Multi-run $MFTMirr. Please report!\n");
 1485     }
 1486 
 1487     for (; dest_rl->length; src_lcn += dest_rl->length, dest_rl++)
 1488         copy_clusters(r, dest_rl->lcn, src_lcn, dest_rl->length);
 1489 }
 1490 
 1491 static void rl_split_run(runlist **rl, int run, s64 pos)
 1492 {
 1493     runlist *rl_new, *rle_new, *rle;
 1494     int items, new_size, size_head, size_tail;
 1495     s64 len_head, len_tail;
 1496 
 1497     items = rl_items(*rl);
 1498     new_size = (items + 1) * sizeof(runlist_element);
 1499     size_head = run * sizeof(runlist_element);
 1500     size_tail = (items - run - 1) * sizeof(runlist_element);
 1501 
 1502     if (!(rl_new = (runlist *)malloc(new_size)))
 1503         perr_exit("malloc");
 1504 
 1505     rle_new = rl_new + run;
 1506     rle = *rl + run;
 1507 
 1508     memmove(rl_new, *rl, size_head);
 1509     memmove(rle_new + 2, rle + 1, size_tail);
 1510 
 1511     len_tail = rle->length - (pos - rle->lcn);
 1512     len_head = rle->length - len_tail;
 1513 
 1514     rl_set(rle_new, rle->vcn, rle->lcn, len_head);
 1515     rl_set(rle_new + 1, rle->vcn + len_head, rle->lcn + len_head, len_tail);
 1516 
 1517     Vprintf("Splitting run at cluster %lld:\n", (long long)pos);
 1518     dump_run(rle); dump_run(rle_new); dump_run(rle_new + 1);
 1519 
 1520     free(*rl);
 1521     *rl = rl_new;
 1522 }
 1523 
 1524 static void rl_insert_at_run(runlist **rl, int run, runlist *ins)
 1525 {
 1526     int items, ins_items;
 1527     int new_size, size_tail;
 1528     runlist *rle;
 1529     s64 vcn;
 1530 
 1531     items  = rl_items(*rl);
 1532     ins_items = rl_items(ins) - 1;
 1533     new_size = ((items - 1) + ins_items) * sizeof(runlist_element);
 1534     size_tail = (items - run - 1) * sizeof(runlist_element);
 1535 
 1536     if (!(*rl = (runlist *)realloc(*rl, new_size)))
 1537         perr_exit("realloc");
 1538 
 1539     rle = *rl + run;
 1540 
 1541     memmove(rle + ins_items, rle + 1, size_tail);
 1542 
 1543     for (vcn = rle->vcn; ins->length; rle++, vcn += ins->length, ins++) {
 1544         rl_set(rle, vcn, ins->lcn, ins->length);
 1545 //      dump_run(rle);
 1546     }
 1547 
 1548     return;
 1549 
 1550     /* FIXME: fast path if ins_items = 1 */
 1551 //  (*rl + run)->lcn = ins->lcn;
 1552 }
 1553 
 1554 static void relocate_run(ntfs_resize_t *resize, runlist **rl, int run)
 1555 {
 1556     s64 lcn, lcn_length;
 1557     s64 new_vol_size;   /* (last LCN on the volume) + 1 */
 1558     runlist *relocate_rl;   /* relocate runlist to relocate_rl */
 1559     int hint;
 1560 
 1561     lcn = (*rl + run)->lcn;
 1562     lcn_length = (*rl + run)->length;
 1563     new_vol_size = resize->new_volume_size;
 1564 
 1565     if (lcn + lcn_length <= new_vol_size)
 1566         return;
 1567 
 1568     if (lcn < new_vol_size) {
 1569         rl_split_run(rl, run, new_vol_size);
 1570         return;
 1571     }
 1572 
 1573     hint = (resize->mref == FILE_MFTMirr) ? 1 : 0;
 1574     if (!(relocate_rl = alloc_cluster(&resize->lcn_bitmap, lcn_length,
 1575                       new_vol_size, hint)))
 1576         perr_exit("Cluster allocation failed for %llu:%lld",
 1577               resize->mref, lcn_length);
 1578 
 1579     /* FIXME: check $MFTMirr DATA isn't multi-run (or support it) */
 1580     Vprintf("Relocate inode %7llu:0x%x:%08lld:0x%08llx --> 0x%08llx\n",
 1581             (unsigned long long)resize->mref,
 1582             (unsigned int)le32_to_cpu(resize->ctx->attr->type),
 1583             (long long)lcn_length, (unsigned long long)lcn,
 1584             (unsigned long long)relocate_rl->lcn);
 1585 
 1586     relocate_clusters(resize, relocate_rl, lcn);
 1587     rl_insert_at_run(rl, run, relocate_rl);
 1588 
 1589     /* We don't release old clusters in the bitmap, that area isn't
 1590        used by the allocator and will be truncated later on */
 1591     free(relocate_rl);
 1592 
 1593     resize->dirty_inode = DIRTY_ATTRIB;
 1594 }
 1595 
 1596 static void relocate_attribute(ntfs_resize_t *resize)
 1597 {
 1598     ATTR_RECORD *a;
 1599     runlist *rl;
 1600     int i;
 1601 
 1602     a = resize->ctx->attr;
 1603 
 1604     if (!a->non_resident)
 1605         return;
 1606 
 1607     if (!(rl = ntfs_mapping_pairs_decompress(resize->vol, a, NULL)))
 1608         perr_exit("ntfs_decompress_mapping_pairs");
 1609 
 1610     for (i = 0; rl[i].length; i++) {
 1611         s64 lcn = rl[i].lcn;
 1612         s64 lcn_length = rl[i].length;
 1613 
 1614         if (lcn == LCN_HOLE || lcn == LCN_RL_NOT_MAPPED)
 1615             continue;
 1616 
 1617         /* FIXME: ntfs_mapping_pairs_decompress should return error */
 1618         if (lcn < 0 || lcn_length <= 0)
 1619             err_exit("Corrupt runlist in MTF %llu attr %x LCN "
 1620                  "%llx length %llx\n", resize->mref,
 1621                  (unsigned int)le32_to_cpu(a->type),
 1622                  lcn, lcn_length);
 1623 
 1624         relocate_run(resize, &rl, i);
 1625     }
 1626 
 1627     if (resize->dirty_inode == DIRTY_ATTRIB) {
 1628         replace_attribute_runlist(resize->vol, resize->ctx, rl);
 1629         resize->dirty_inode = DIRTY_INODE;
 1630     }
 1631 
 1632     free(rl);
 1633 }
 1634 
 1635 static int is_mftdata(ntfs_resize_t *resize)
 1636 {
 1637     if (resize->ctx->attr->type != AT_DATA)
 1638         return 0;
 1639 
 1640     if (resize->mref == 0)
 1641         return 1;
 1642     
 1643     if (  MREF(resize->mrec->base_mft_record) == 0  &&
 1644         MSEQNO(resize->mrec->base_mft_record) != 0)
 1645         return 1;
 1646     
 1647     return 0;
 1648 }
 1649 
 1650 static int handle_mftdata(ntfs_resize_t *resize, int do_mftdata)
 1651 {
 1652     ATTR_RECORD *attr = resize->ctx->attr;
 1653     VCN highest_vcn, lowest_vcn;
 1654     
 1655     if (do_mftdata) {
 1656         
 1657         if (!is_mftdata(resize))
 1658             return 0;
 1659         
 1660         highest_vcn = sle64_to_cpu(attr->highest_vcn);
 1661         lowest_vcn  = sle64_to_cpu(attr->lowest_vcn);
 1662         
 1663         if (resize->mft_highest_vcn != highest_vcn)
 1664             return 0;
 1665         
 1666         if (lowest_vcn == 0)
 1667             resize->mft_highest_vcn = lowest_vcn;
 1668         else
 1669             resize->mft_highest_vcn = lowest_vcn - 1;
 1670 
 1671     } else if (is_mftdata(resize)) {
 1672         
 1673         highest_vcn = sle64_to_cpu(attr->highest_vcn);
 1674         
 1675         if (resize->mft_highest_vcn < highest_vcn)
 1676             resize->mft_highest_vcn = highest_vcn;
 1677         
 1678         return 0;
 1679     }
 1680 
 1681     return 1;
 1682 }
 1683 
 1684 static void relocate_attributes(ntfs_resize_t *resize, int do_mftdata)
 1685 {
 1686     int ret;
 1687 
 1688     if (!(resize->ctx = attr_get_search_ctx(NULL, resize->mrec)))
 1689         exit(1);
 1690 
 1691     while (!ntfs_attrs_walk(resize->ctx)) {
 1692         if (resize->ctx->attr->type == AT_END)
 1693             break;
 1694         
 1695         if (handle_mftdata(resize, do_mftdata) == 0)
 1696             continue;
 1697             
 1698         ret = has_bad_sectors(resize, 0);
 1699         if (ret == -1)
 1700             exit(1);
 1701         else if (ret == 1)
 1702             continue;
 1703 
 1704         if (resize->mref == FILE_Bitmap &&
 1705             resize->ctx->attr->type == AT_DATA)
 1706             continue;
 1707 
 1708         relocate_attribute(resize);
 1709     }
 1710 
 1711     ntfs_attr_put_search_ctx(resize->ctx);
 1712 }
 1713 
 1714 static void relocate_inode(ntfs_resize_t *resize, MFT_REF mref, int do_mftdata)
 1715 {
 1716     if (ntfs_file_record_read(resize->vol, mref, &resize->mrec, NULL)) {
 1717         /* FIXME: continue only if it make sense, e.g.
 1718            MFT record not in use based on $MFT bitmap */
 1719         if (errno == EIO || errno == ENOENT)
 1720             return;
 1721         perr_exit("ntfs_file_record_record");
 1722     }
 1723 
 1724     if (!(resize->mrec->flags & MFT_RECORD_IN_USE))
 1725         return;
 1726 
 1727     resize->mref = mref;
 1728     resize->dirty_inode = DIRTY_NONE;
 1729 
 1730     relocate_attributes(resize, do_mftdata);
 1731 
 1732     if (resize->dirty_inode == DIRTY_INODE) {
 1733 //      if (vol->dev->d_ops->sync(vol->dev) == -1)
 1734 //          perr_exit("Failed to sync device");
 1735         if (write_mft_record(resize->vol, mref, resize->mrec))
 1736             perr_exit("Couldn't update inode %llu", mref);
 1737     }
 1738 }
 1739 
 1740 static void relocate_inodes(ntfs_resize_t *resize)
 1741 {
 1742     s64 nr_mft_records;
 1743     MFT_REF mref;
 1744     VCN highest_vcn;
 1745 
 1746     printf("Relocating needed data ...\n");
 1747 
 1748     progress_init(&resize->progress, 0, resize->relocations, resize->progress.flags);
 1749     resize->relocations = 0;
 1750 
 1751     resize->mrec = (MFT_RECORD *)malloc(resize->vol->mft_record_size);
 1752     if (!resize->mrec)
 1753         perr_exit("malloc failed");
 1754 
 1755     nr_mft_records = resize->vol->mft_na->initialized_size >>
 1756             resize->vol->mft_record_size_bits;
 1757 
 1758     for (mref = 0; mref < (MFT_REF)nr_mft_records; mref++)
 1759         relocate_inode(resize, mref, 0);
 1760 
 1761     while(1) {
 1762         highest_vcn = resize->mft_highest_vcn;
 1763         mref = nr_mft_records;
 1764         do {
 1765             relocate_inode(resize, --mref, 1);
 1766             if (resize->mft_highest_vcn == 0)
 1767                 goto done;
 1768         } while (mref);
 1769 
 1770         if (highest_vcn == resize->mft_highest_vcn)
 1771             err_exit("Sanity check failed! Highest_vcn = %lld. "
 1772                  "Please report!", highest_vcn);
 1773     }
 1774 done:
 1775     if (resize->mrec)
 1776         free(resize->mrec);
 1777 }
 1778 
 1779 static void print_hint(ntfs_volume *vol, const char *s, struct llcn_t llcn)
 1780 {
 1781     s64 runs_b, runs_mb;
 1782 
 1783     if (llcn.lcn == 0)
 1784         return;
 1785 
 1786     runs_b = llcn.lcn * vol->cluster_size;
 1787     runs_mb = rounded_up_division(runs_b, NTFS_MBYTE);
 1788     printf("%-19s: %9lld MB      %8lld\n", s, (long long)runs_mb,
 1789             (long long)llcn.inode);
 1790 }
 1791 
 1792 /**
 1793  * advise_on_resize
 1794  *
 1795  * The metadata file $Bitmap has one bit for each cluster on disk.  This has
 1796  * already been read into lcn_bitmap.  By looking for the last used cluster on
 1797  * the disk, we can work out by how much we can shrink the volume.
 1798  */
 1799 static void advise_on_resize(ntfs_resize_t *resize)
 1800 {
 1801     ntfs_volume *vol = resize->vol;
 1802 
 1803     if (opt.verbose) {
 1804         printf("Estimating smallest shrunken size supported ...\n");
 1805         printf("File feature         Last used at      By inode\n");
 1806         print_hint(vol, "$MFT",     resize->last_mft);
 1807         print_hint(vol, "Multi-Record", resize->last_multi_mft);
 1808         print_hint(vol, "$MFTMirr",     resize->last_mftmir);
 1809         print_hint(vol, "Compressed",   resize->last_compressed);
 1810         print_hint(vol, "Sparse",   resize->last_sparse);
 1811         print_hint(vol, "Ordinary",     resize->last_lcn);
 1812     }
 1813 
 1814     print_advise(vol, resize->last_unsupp);
 1815 }
 1816 
 1817 
 1818 static void rl_expand(runlist **rl, const VCN last_vcn)
 1819 {
 1820     int len;
 1821     runlist *p = *rl;
 1822 
 1823     len = rl_items(p) - 1;
 1824     if (len <= 0)
 1825         err_exit("rl_expand: bad runlist length: %d\n", len);
 1826 
 1827     if (p[len].vcn > last_vcn)
 1828         err_exit("rl_expand: length is already more than requested "
 1829              "(%lld > %lld)\n", p[len].vcn, last_vcn);
 1830 
 1831     if (p[len - 1].lcn == LCN_HOLE) {
 1832 
 1833         p[len - 1].length += last_vcn - p[len].vcn;
 1834         p[len].vcn = last_vcn;
 1835 
 1836     } else if (p[len - 1].lcn >= 0) {
 1837 
 1838         p = realloc(*rl, (++len + 1) * sizeof(runlist_element));
 1839         if (!p)
 1840             perr_exit("rl_expand: realloc");
 1841 
 1842         p[len - 1].lcn = LCN_HOLE;
 1843         p[len - 1].length = last_vcn - p[len - 1].vcn;
 1844         rl_set(p + len, last_vcn, LCN_ENOENT, 0LL);
 1845         *rl = p;
 1846 
 1847     } else
 1848         err_exit("rl_expand: bad LCN: %lld\n", p[len - 1].lcn);
 1849 }
 1850 
 1851 static void rl_truncate(runlist **rl, const VCN last_vcn)
 1852 {
 1853     int len;
 1854     VCN vcn;
 1855     
 1856     len = rl_items(*rl) - 1;
 1857     if (len <= 0)
 1858         err_exit("rl_truncate: bad runlist length: %d\n", len);
 1859 
 1860     vcn = (*rl)[len].vcn;
 1861     
 1862     if (vcn < last_vcn)
 1863         rl_expand(rl, last_vcn);
 1864     
 1865     else if (vcn > last_vcn)
 1866         if (ntfs_rl_truncate(rl, last_vcn) == -1)
 1867             perr_exit("ntfs_rl_truncate");
 1868 }
 1869 
 1870 /**
 1871  * bitmap_file_data_fixup
 1872  *
 1873  * $Bitmap can overlap the end of the volume. Any bits in this region
 1874  * must be set. This region also encompasses the backup boot sector.
 1875  */
 1876 static void bitmap_file_data_fixup(s64 cluster, struct bitmap *bm)
 1877 {
 1878     for (; cluster < bm->size << 3; cluster++)
 1879         ntfs_bit_set(bm->bm, (u64)cluster, 1);
 1880 }
 1881 
 1882 /**
 1883  * truncate_badclust_bad_attr
 1884  *
 1885  * The metadata file $BadClus needs to be shrunk.
 1886  *
 1887  * FIXME: this function should go away and instead using a generalized
 1888  * "truncate_bitmap_data_attr()"
 1889  */
 1890 static void truncate_badclust_bad_attr(ntfs_resize_t *resize)
 1891 {
 1892     ATTR_RECORD *a;
 1893     runlist *rl_bad;
 1894     s64 nr_clusters = resize->new_volume_size;
 1895     ntfs_volume *vol = resize->vol;
 1896 
 1897     a = resize->ctx->attr;
 1898     if (!a->non_resident)
 1899         /* FIXME: handle resident attribute value */
 1900         err_exit("Resident attribute in $BadClust isn't supported!\n");
 1901 
 1902     if (!(rl_bad = ntfs_mapping_pairs_decompress(vol, a, NULL)))
 1903         perr_exit("ntfs_mapping_pairs_decompress");
 1904     
 1905     rl_truncate(&rl_bad, nr_clusters);
 1906 
 1907     a->highest_vcn = cpu_to_le64(nr_clusters - 1LL);
 1908     a->allocated_size = cpu_to_le64(nr_clusters * vol->cluster_size);
 1909     a->data_size = cpu_to_le64(nr_clusters * vol->cluster_size);
 1910 
 1911     replace_attribute_runlist(vol, resize->ctx, rl_bad);
 1912 
 1913     free(rl_bad);
 1914 }
 1915 
 1916 /**
 1917  * realloc_bitmap_data_attr
 1918  *
 1919  * Reallocate the metadata file $Bitmap.  It must be large enough for one bit
 1920  * per cluster of the shrunken volume.  Also it must be a of 8 bytes in size.
 1921  */
 1922 static void realloc_bitmap_data_attr(ntfs_resize_t *resize,
 1923                      runlist **rl,
 1924                      s64 nr_bm_clusters)
 1925 {
 1926     s64 i;
 1927     ntfs_volume *vol = resize->vol;
 1928     ATTR_RECORD *a = resize->ctx->attr;
 1929     s64 new_size = resize->new_volume_size;
 1930     struct bitmap *bm = &resize->lcn_bitmap;
 1931 
 1932     if (!(*rl = ntfs_mapping_pairs_decompress(vol, a, NULL)))
 1933         perr_exit("ntfs_mapping_pairs_decompress");
 1934 
 1935     release_bitmap_clusters(bm, *rl);
 1936     free(*rl);
 1937 
 1938     for (i = vol->nr_clusters; i < new_size; i++)
 1939         ntfs_bit_set(bm->bm, i, 0);
 1940 
 1941     if (!(*rl = alloc_cluster(bm, nr_bm_clusters, new_size, 0)))
 1942         perr_exit("Couldn't allocate $Bitmap clusters");
 1943 }
 1944 
 1945 static void realloc_lcn_bitmap(ntfs_resize_t *resize, s64 bm_bsize)
 1946 {
 1947     u8 *tmp;
 1948 
 1949     if (!(tmp = realloc(resize->lcn_bitmap.bm, bm_bsize)))
 1950         perr_exit("realloc");
 1951     
 1952     resize->lcn_bitmap.bm = tmp;
 1953     resize->lcn_bitmap.size = bm_bsize;
 1954     bitmap_file_data_fixup(resize->new_volume_size, &resize->lcn_bitmap);
 1955 }
 1956 
 1957 /**
 1958  * truncate_bitmap_data_attr
 1959  */
 1960 static void truncate_bitmap_data_attr(ntfs_resize_t *resize)
 1961 {
 1962     ATTR_RECORD *a;
 1963     runlist *rl;
 1964     s64 bm_bsize, size;
 1965     s64 nr_bm_clusters;
 1966     ntfs_volume *vol = resize->vol;
 1967 
 1968     a = resize->ctx->attr;
 1969     if (!a->non_resident)
 1970         /* FIXME: handle resident attribute value */
 1971         err_exit("Resident attribute in $Bitmap isn't supported!\n");
 1972 
 1973     bm_bsize = nr_clusters_to_bitmap_byte_size(resize->new_volume_size);
 1974     nr_bm_clusters = rounded_up_division(bm_bsize, vol->cluster_size);
 1975 
 1976     if (resize->shrink) {
 1977         realloc_bitmap_data_attr(resize, &rl, nr_bm_clusters);
 1978         realloc_lcn_bitmap(resize, bm_bsize);
 1979     } else {
 1980         realloc_lcn_bitmap(resize, bm_bsize);
 1981         realloc_bitmap_data_attr(resize, &rl, nr_bm_clusters);
 1982     }
 1983 
 1984     a->highest_vcn = cpu_to_le64(nr_bm_clusters - 1LL);
 1985     a->allocated_size = cpu_to_le64(nr_bm_clusters * vol->cluster_size);
 1986     a->data_size = cpu_to_le64(bm_bsize);
 1987     a->initialized_size = cpu_to_le64(bm_bsize);
 1988 
 1989     replace_attribute_runlist(vol, resize->ctx, rl);
 1990 
 1991     /*
 1992      * FIXME: update allocated/data sizes and timestamps in $FILE_NAME
 1993      * attribute too, for now chkdsk will do this for us.
 1994      */
 1995 
 1996     size = ntfs_rl_pwrite(vol, rl, 0, bm_bsize, resize->lcn_bitmap.bm);
 1997     if (bm_bsize != size) {
 1998         if (size == -1)
 1999             perr_exit("Couldn't write $Bitmap");
 2000         err_exit("Couldn't write full $Bitmap file (%lld from %lld)\n",
 2001                 (long long)size, (long long)bm_bsize);
 2002     }
 2003 
 2004     free(rl);
 2005 }
 2006 
 2007 /**
 2008  * lookup_data_attr
 2009  *
 2010  * Find the $DATA attribute (with or without a name) for the given MFT reference
 2011  * (inode number).
 2012  */
 2013 static void lookup_data_attr(ntfs_volume *vol,
 2014                  MFT_REF mref,
 2015                  const char *aname,
 2016                  ntfs_attr_search_ctx **ctx)
 2017 {
 2018     ntfs_inode *ni;
 2019     ntfschar *ustr = NULL;
 2020     int len = 0;
 2021 
 2022     if (!(ni = ntfs_inode_open(vol, mref)))
 2023         perr_exit("ntfs_open_inode");
 2024 
 2025     if (!(*ctx = attr_get_search_ctx(ni, NULL)))
 2026         exit(1);
 2027 
 2028     if (str2unicode(aname, &ustr, &len) == -1)
 2029         exit(1);
 2030 
 2031     if (ntfs_attr_lookup(AT_DATA, ustr, len, 0, 0, NULL, 0, *ctx))
 2032         perr_exit("ntfs_lookup_attr");
 2033 
 2034     if (ustr != AT_UNNAMED)
 2035         free(ustr);
 2036 }
 2037 
 2038 /**
 2039  * truncate_badclust_file
 2040  *
 2041  * Shrink the $BadClus file to match the new volume size.
 2042  */
 2043 static void truncate_badclust_file(ntfs_resize_t *resize)
 2044 {
 2045     printf("Updating $BadClust file ...\n");
 2046 
 2047     lookup_data_attr(resize->vol, FILE_BadClus, "$Bad", &resize->ctx);
 2048     /* FIXME: sanity_check_attr(ctx->attr); */
 2049     truncate_badclust_bad_attr(resize);
 2050 
 2051     if (write_mft_record(resize->vol, resize->ctx->ntfs_ino->mft_no,
 2052                  resize->ctx->mrec))
 2053         perr_exit("Couldn't update $BadClust");
 2054 
 2055     ntfs_attr_put_search_ctx(resize->ctx);
 2056 }
 2057 
 2058 /**
 2059  * truncate_bitmap_file
 2060  *
 2061  * Shrink the $Bitmap file to match the new volume size.
 2062  */
 2063 static void truncate_bitmap_file(ntfs_resize_t *resize)
 2064 {
 2065     printf("Updating $Bitmap file ...\n");
 2066 
 2067     lookup_data_attr(resize->vol, FILE_Bitmap, NULL, &resize->ctx);
 2068     truncate_bitmap_data_attr(resize);
 2069 
 2070     if (write_mft_record(resize->vol, resize->ctx->ntfs_ino->mft_no,
 2071                  resize->ctx->mrec))
 2072         perr_exit("Couldn't update $Bitmap");
 2073 
 2074     ntfs_attr_put_search_ctx(resize->ctx);
 2075 }
 2076 
 2077 /**
 2078  * setup_lcn_bitmap
 2079  *
 2080  * Allocate a block of memory with one bit for each cluster of the disk.
 2081  * All the bits are set to 0, except those representing the region beyond the
 2082  * end of the disk.
 2083  */
 2084 static int setup_lcn_bitmap(struct bitmap *bm, s64 nr_clusters)
 2085 {
 2086     /* Determine lcn bitmap byte size and allocate it. */
 2087     bm->size = rounded_up_division(nr_clusters, 8);
 2088 
 2089     if (!(bm->bm = (unsigned char *)calloc(1, bm->size)))
 2090         return -1;
 2091 
 2092     bitmap_file_data_fixup(nr_clusters, bm);
 2093     return 0;
 2094 }
 2095 
 2096 /**
 2097  * update_bootsector
 2098  *
 2099  * FIXME: should be done using ntfs_* functions
 2100  */
 2101 static void update_bootsector(ntfs_resize_t *r)
 2102 {
 2103     NTFS_BOOT_SECTOR bs;
 2104     s64  bs_size = sizeof(NTFS_BOOT_SECTOR);
 2105     ntfs_volume *vol = r->vol;
 2106 
 2107     printf("Updating Boot record ...\n");
 2108 
 2109     if (vol->dev->d_ops->seek(vol->dev, 0, SEEK_SET) == (off_t)-1)
 2110         perr_exit("lseek");
 2111 
 2112     if (vol->dev->d_ops->read(vol->dev, &bs, bs_size) == -1)
 2113         perr_exit("read() error");
 2114 
 2115     bs.number_of_sectors = cpu_to_sle64(r->new_volume_size *
 2116             bs.bpb.sectors_per_cluster);
 2117 
 2118     if (r->mftmir_old) {
 2119         r->progress.flags |= NTFS_PROGBAR_SUPPRESS;
 2120         copy_clusters(r, r->mftmir_rl.lcn, r->mftmir_old,
 2121                   r->mftmir_rl.length);
 2122         bs.mftmirr_lcn = cpu_to_le64(r->mftmir_rl.lcn);
 2123         r->progress.flags &= ~NTFS_PROGBAR_SUPPRESS;
 2124     }
 2125 
 2126     if (vol->dev->d_ops->seek(vol->dev, 0, SEEK_SET) == (off_t)-1)
 2127         perr_exit("lseek");
 2128 
 2129     if (!opt.ro_flag)
 2130         if (vol->dev->d_ops->write(vol->dev, &bs, bs_size) == -1)
 2131             perr_exit("write() error");
 2132 }
 2133 
 2134 /**
 2135  * vol_size
 2136  */
 2137 static s64 vol_size(ntfs_volume *v, s64 nr_clusters)
 2138 {
 2139     /* add one sector_size for the backup boot sector */
 2140     return nr_clusters * v->cluster_size + v->sector_size;
 2141 }
 2142 
 2143 /**
 2144  * print_vol_size
 2145  *
 2146  * Print the volume size in bytes and decimal megabytes.
 2147  */
 2148 static void print_vol_size(const char *str, s64 bytes)
 2149 {
 2150     printf("%s: %lld bytes (%lld MB)\n", str, (long long)bytes,
 2151             (long long)rounded_up_division(bytes, NTFS_MBYTE));
 2152 }
 2153 
 2154 /**
 2155  * print_disk_usage
 2156  *
 2157  * Display the amount of disk space in use.
 2158  */
 2159 static void print_disk_usage(ntfs_volume *vol, s64 nr_used_clusters)
 2160 {
 2161     s64 total, used;
 2162 
 2163     total = vol->nr_clusters * vol->cluster_size;
 2164     used = nr_used_clusters * vol->cluster_size;
 2165 
 2166     /* WARNING: don't modify the text, external tools grep for it */
 2167     printf("Space in use       : %lld MB (%.1f%%)\n",
 2168            (long long)rounded_up_division(used, NTFS_MBYTE),
 2169            100.0 * ((float)used / total));
 2170 }
 2171 
 2172 static void print_num_of_relocations(ntfs_resize_t *resize)
 2173 {
 2174     s64 relocations = resize->relocations * resize->vol->cluster_size;
 2175 
 2176     printf("Needed relocations : %lld (%lld MB)\n",
 2177             (long long)resize->relocations, (long long)
 2178             rounded_up_division(relocations, NTFS_MBYTE));
 2179 }
 2180 
 2181 /**
 2182  * mount_volume
 2183  *
 2184  * First perform some checks to determine if the volume is already mounted, or
 2185  * is dirty (Windows wasn't shutdown properly).  If everything is OK, then mount
 2186  * the volume (load the metadata into memory).
 2187  */
 2188 static ntfs_volume *mount_volume(void)
 2189 {
 2190     unsigned long mntflag;
 2191     ntfs_volume *vol = NULL;
 2192 
 2193     if (ntfs_check_if_mounted(opt.volume, &mntflag)) {
 2194         perr_printf("Failed to check '%s' mount state", opt.volume);
 2195         printf("Probably /etc/mtab is missing. It's too risky to "
 2196                "continue. You might try\nan another Linux distro.\n");
 2197         exit(1);
 2198     }
 2199     if (mntflag & NTFS_MF_MOUNTED) {
 2200         if (!(mntflag & NTFS_MF_READONLY))
 2201             err_exit("Device '%s' is mounted read-write. "
 2202                  "You must 'umount' it first.\n", opt.volume);
 2203         if (!opt.ro_flag)
 2204             err_exit("Device '%s' is mounted. "
 2205                  "You must 'umount' it first.\n", opt.volume);
 2206     }
 2207 
 2208     if (!(vol = ntfs_mount(opt.volume, opt.ro_flag))) {
 2209 
 2210         int err = errno;
 2211 
 2212         perr_printf("Opening '%s' as NTFS failed", opt.volume);
 2213         if (err == EINVAL)
 2214             printf(invalid_ntfs_msg, opt.volume);
 2215         else if (err == EIO)
 2216             printf("%s", corrupt_volume_msg);
 2217         else if (err == EPERM)
 2218             printf("%s", hibernated_volume_msg);
 2219             else if (err == EOPNOTSUPP)
 2220             printf("%s", unclean_journal_msg);
 2221         exit(1);
 2222     }
 2223 
 2224     if (vol->flags & VOLUME_IS_DIRTY)
 2225         if (opt.force-- <= 0)
 2226             err_exit("Volume is scheduled for check.\nRun chkdsk /f"
 2227                  " and please try again, or see option -f.\n");
 2228 
 2229     if (NTFS_MAX_CLUSTER_SIZE < vol->cluster_size)
 2230         err_exit("Cluster size %u is too large!\n",
 2231             (unsigned int)vol->cluster_size);
 2232 
 2233     printf("Device name        : %s\n", opt.volume);
 2234     printf("NTFS volume version: %d.%d\n", vol->major_ver, vol->minor_ver);
 2235     if (ntfs_version_is_supported(vol))
 2236         perr_exit("Unknown NTFS version");
 2237 
 2238     printf("Cluster size       : %u bytes\n",
 2239             (unsigned int)vol->cluster_size);
 2240     print_vol_size("Current volume size", vol_size(vol, vol->nr_clusters));
 2241 
 2242     return vol;
 2243 }
 2244 
 2245 /**
 2246  * prepare_volume_fixup
 2247  *
 2248  * Set the volume's dirty flag and wipe the filesystem journal.  When Windows
 2249  * boots it will automatically run chkdsk to check for any problems.  If the
 2250  * read-only command line option was given, this function will do nothing.
 2251  */
 2252 static void prepare_volume_fixup(ntfs_volume *vol)
 2253 {
 2254     u16 flags;
 2255 
 2256     flags = vol->flags | VOLUME_IS_DIRTY;
 2257     if (vol->major_ver >= 2)
 2258         flags |= VOLUME_MOUNTED_ON_NT4;
 2259 
 2260     printf("Schedule chkdsk for NTFS consistency check at Windows "
 2261         "boot time ...\n");
 2262 
 2263     if (ntfs_volume_write_flags(vol, flags))
 2264         perr_exit("Failed to set $Volume dirty");
 2265 
 2266     if (vol->dev->d_ops->sync(vol->dev) == -1)
 2267         perr_exit("Failed to sync device");
 2268 
 2269     printf("Resetting $LogFile ... (this might take a while)\n");
 2270 
 2271     if (ntfs_logfile_reset(vol))
 2272         perr_exit("Failed to reset $LogFile");
 2273 
 2274     if (vol->dev->d_ops->sync(vol->dev) == -1)
 2275         perr_exit("Failed to sync device");
 2276 }
 2277 
 2278 
 2279 static void set_disk_usage_constraint(ntfs_resize_t *resize)
 2280 {
 2281     /* last lcn for a filled up volume (no empty space) */
 2282     s64 last = resize->inuse - 1;
 2283 
 2284     if (resize->last_unsupp < last)
 2285         resize->last_unsupp = last;
 2286 }
 2287 
 2288 static void check_resize_constraints(ntfs_resize_t *resize)
 2289 {
 2290     s64 new_size = resize->new_volume_size;
 2291 
 2292     if (resize->badclusters) {
 2293         printf("%sThe NTFS volume has at least %lld bad sector%s.\n",
 2294                !opt.badsectors ? NERR_PREFIX : "",
 2295                resize->badclusters,
 2296                resize->badclusters  - 1 ? "s" : "");
 2297         if (!opt.badsectors) {
 2298             printf("%s", bad_sectors_warning_msg);
 2299             exit(1);
 2300         }
 2301     }
 2302         
 2303     /* FIXME: resize.shrink true also if only -i is used */
 2304     if (!resize->shrink)
 2305         return;
 2306 
 2307     if (resize->inuse == resize->vol->nr_clusters)
 2308         err_exit("Volume is full. To shrink it, "
 2309              "delete unused files.\n");
 2310 
 2311     if (opt.info)
 2312         return;
 2313 
 2314     /* FIXME: reserve some extra space so Windows can boot ... */
 2315     if (new_size < resize->inuse)
 2316         err_exit("New size can't be less than the space already"
 2317              " occupied by data.\nYou either need to delete unused"
 2318              " files or see the -i option.\n");
 2319 
 2320     if (new_size <= resize->last_unsupp)
 2321         err_exit("The fragmentation type, you have, isn't "
 2322              "supported yet. Rerun ntfsresize\nwith "
 2323              "the -i option to estimate the smallest "
 2324              "shrunken volume size supported.\n");
 2325 
 2326     print_num_of_relocations(resize);
 2327 }
 2328 
 2329 
 2330 int main(int argc, char **argv)
 2331 {
 2332     ntfsck_t fsck;
 2333     ntfs_resize_t resize;
 2334     s64 new_size = 0;   /* in clusters; 0 = --info w/o --size */
 2335     s64 device_size;        /* in bytes */
 2336     ntfs_volume *vol;
 2337 
 2338     printf("%s v%s (libntfs %s)\n", EXEC_NAME, VERSION,
 2339             ntfs_libntfs_version());
 2340 
 2341     if (!parse_options(argc, argv))
 2342         return 1;
 2343 
 2344     utils_set_locale();
 2345 
 2346     if ((vol = mount_volume()) == NULL)
 2347         err_exit("Couldn't open volume '%s'!\n", opt.volume);
 2348 
 2349     device_size = ntfs_device_size_get(vol->dev, vol->sector_size);
 2350     device_size *= vol->sector_size;
 2351     if (device_size <= 0)
 2352         err_exit("Couldn't get device size (%lld)!\n", device_size);
 2353 
 2354     print_vol_size("Current device size", device_size);
 2355 
 2356     if (device_size < vol->nr_clusters * vol->cluster_size)
 2357         err_exit("Current NTFS volume size is bigger than the device "
 2358              "size!\nCorrupt partition table or incorrect device "
 2359              "partitioning?\n");
 2360 
 2361     if (!opt.bytes && !opt.info)
 2362         opt.bytes = device_size;
 2363 
 2364     /* Take the integer part: don't make the volume bigger than requested */
 2365     new_size = opt.bytes / vol->cluster_size;
 2366 
 2367     /* Backup boot sector at the end of device isn't counted in NTFS
 2368        volume size thus we have to reserve space for it. */
 2369     if (new_size)
 2370         --new_size;
 2371 
 2372     if (!opt.info) {
 2373         print_vol_size("New volume size    ", vol_size(vol, new_size));
 2374         if (device_size < opt.bytes)
 2375             err_exit("New size can't be bigger than the device size"
 2376                  ".\nIf you want to enlarge NTFS then first "
 2377                  "enlarge the device size by e.g. fdisk.\n");
 2378     }
 2379 
 2380     if (!opt.info && (new_size == vol->nr_clusters ||
 2381               (opt.bytes == device_size &&
 2382                new_size == vol->nr_clusters - 1))) {
 2383         printf("Nothing to do: NTFS volume size is already OK.\n");
 2384         exit(0);
 2385     }
 2386 
 2387     memset(&fsck, 0, sizeof(fsck));
 2388     if (opt.show_progress)
 2389         fsck.flags |= NTFSCK_PROGBAR;
 2390 
 2391     if (setup_lcn_bitmap(&fsck.lcn_bitmap, vol->nr_clusters) != 0)
 2392         perr_exit("Failed to setup allocation bitmap");
 2393     if (build_allocation_bitmap(vol, &fsck) != 0)
 2394         exit(1);
 2395     if (fsck.outsider || fsck.multi_ref) {
 2396         err_printf("Filesystem check failed!\n");
 2397         if (fsck.outsider)
 2398             err_printf("%d clusters are referenced outside "
 2399                    "of the volume.\n", fsck.outsider);
 2400         if (fsck.multi_ref)
 2401             err_printf("%d clusters are referenced multiply"
 2402                    " times.\n", fsck.multi_ref);
 2403         printf("%s", corrupt_volume_msg);
 2404         exit(1);
 2405     }
 2406     compare_bitmaps(vol, &fsck.lcn_bitmap);
 2407 
 2408     print_disk_usage(vol, fsck.inuse);
 2409 
 2410     memset(&resize, 0, sizeof(resize));
 2411     resize.new_volume_size = new_size;
 2412     resize.inuse = fsck.inuse;
 2413     resize.lcn_bitmap = fsck.lcn_bitmap;
 2414     resize.vol = vol;
 2415     if (opt.show_progress)
 2416         resize.progress.flags |= NTFS_PROGBAR;
 2417 
 2418     /* This is also true if --info was used w/o --size (new_size = 0) */
 2419     if (new_size < vol->nr_clusters)
 2420         resize.shrink = 1;
 2421 
 2422     set_resize_constraints(&resize);
 2423     set_disk_usage_constraint(&resize);
 2424     check_resize_constraints(&resize);
 2425 
 2426     if (opt.info) {
 2427             advise_on_resize(&resize);
 2428         exit(0);
 2429     }
 2430 
 2431     if (opt.force-- <= 0 && !opt.ro_flag) {
 2432         printf("%s", resize_warning_msg);
 2433         proceed_question();
 2434     }
 2435 
 2436     /* FIXME: performance - relocate logfile here if it's needed */
 2437     prepare_volume_fixup(vol);
 2438 
 2439     if (resize.relocations)
 2440         relocate_inodes(&resize);
 2441 
 2442     truncate_badclust_file(&resize);
 2443     truncate_bitmap_file(&resize);
 2444     update_bootsector(&resize);
 2445 
 2446     /* We don't create backup boot sector because we don't know where the
 2447        partition will be split. The scheduled chkdsk will fix it */
 2448 
 2449     if (opt.ro_flag) {
 2450         printf("The read-only test run ended successfully.\n");
 2451         exit(0);
 2452     }
 2453 
 2454     /* WARNING: don't modify the texts, external tools grep for them */
 2455     printf("Syncing device ...\n");
 2456     if (vol->dev->d_ops->sync(vol->dev) == -1)
 2457         perr_exit("fsync");
 2458 
 2459     printf("Successfully resized NTFS on device '%s'.\n", vol->dev->d_name);
 2460     if (resize.shrink)
 2461         printf("%s", resize_important_msg);
 2462 
 2463     return 0;
 2464 }