The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/ntfs/super.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * super.c
    3  *
    4  * Copyright (C) 1995-1997, 1999 Martin von Löwis
    5  * Copyright (C) 1996-1997 Régis Duchesne
    6  * Copyright (C) 1999 Steve Dodd
    7  * Copyright (C) 2000-2001 Anton Altparmakov (AIA)
    8  */
    9 
   10 #include <linux/ntfs_fs.h>
   11 #include <linux/errno.h>
   12 #include <linux/bitops.h>
   13 #include <linux/module.h>
   14 #include "ntfstypes.h"
   15 #include "struct.h"
   16 #include "super.h"
   17 #include "macros.h"
   18 #include "inode.h"
   19 #include "support.h"
   20 #include "util.h"
   21 #include <linux/smp_lock.h>
   22 
   23 /* All important structures in NTFS use 2 consistency checks:
   24  * . a magic structure identifier (FILE, INDX, RSTR, RCRD...)
   25  * . a fixup technique : the last word of each sector (called a fixup) of a
   26  *   structure's record should end with the word at offset <n> of the first
   27  *   sector, and if it is the case, must be replaced with the words following
   28  *   <n>. The value of <n> and the number of fixups is taken from the fields
   29  *   at the offsets 4 and 6. Note that the sector size is defined as
   30  *   NTFS_SECTOR_SIZE and not as the hardware sector size (this is concordant
   31  *   with what the Windows NTFS driver does).
   32  *
   33  * This function performs these 2 checks, and _fails_ if:
   34  * . the input size is invalid
   35  * . the fixup header is invalid
   36  * . the size does not match the number of sectors
   37  * . the magic identifier is wrong
   38  * . a fixup is invalid
   39  */
   40 int ntfs_fixup_record(char *record, char *magic, int size)
   41 {
   42         int start, count, offset;
   43         ntfs_u16 fixup;
   44 
   45         if (!IS_MAGIC(record, magic))
   46                 return 0;
   47         start = NTFS_GETU16(record + 4);
   48         count = NTFS_GETU16(record + 6) - 1;
   49         if (size & (NTFS_SECTOR_SIZE - 1) || start & 1 ||
   50                         start + count * 2 > size || size >> 9 != count) {
   51                 if (size <= 0)
   52                         printk(KERN_ERR "NTFS: BUG: ntfs_fixup_record() got "
   53                                         "zero size! Please report this to "
   54                                         "linux-ntfs-dev@lists.sf.net\n");
   55                 return 0;
   56         }
   57         fixup = NTFS_GETU16(record + start);
   58         start += 2;
   59         offset = NTFS_SECTOR_SIZE - 2;
   60         while (count--) {
   61                 if (NTFS_GETU16(record + offset) != fixup)
   62                         return 0;
   63                 NTFS_PUTU16(record + offset, NTFS_GETU16(record + start));
   64                 start += 2;
   65                 offset += NTFS_SECTOR_SIZE;
   66         }
   67         return 1;
   68 }
   69 
   70 /*
   71  * Get vital informations about the ntfs partition from the boot sector.
   72  * Return 0 on success or -1 on error.
   73  */
   74 int ntfs_init_volume(ntfs_volume *vol, char *boot)
   75 {
   76         int sectors_per_cluster_bits;
   77         __s64 ll;
   78         ntfs_cluster_t mft_zone_size, tc;
   79 
   80         /* System defined default values, in case we don't load $AttrDef. */
   81         vol->at_standard_information = 0x10;
   82         vol->at_attribute_list = 0x20;
   83         vol->at_file_name = 0x30;
   84         vol->at_volume_version = 0x40;
   85         vol->at_security_descriptor = 0x50;
   86         vol->at_volume_name = 0x60;
   87         vol->at_volume_information = 0x70;
   88         vol->at_data = 0x80;
   89         vol->at_index_root = 0x90;
   90         vol->at_index_allocation = 0xA0;
   91         vol->at_bitmap = 0xB0;
   92         vol->at_symlink = 0xC0;
   93         /* Sector size. */
   94         vol->sector_size = NTFS_GETU16(boot + 0xB);
   95         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->sector_size = 0x%x\n",
   96                                 vol->sector_size);
   97         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: sectors_per_cluster = "
   98                                 "0x%x\n", NTFS_GETU8(boot + 0xD));
   99         sectors_per_cluster_bits = ffs(NTFS_GETU8(boot + 0xD)) - 1;
  100         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: sectors_per_cluster_bits "
  101                                 "= 0x%x\n", sectors_per_cluster_bits); 
  102         vol->mft_clusters_per_record = NTFS_GETS8(boot + 0x40);
  103         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_clusters_per_record"
  104                                 " = 0x%x\n", vol->mft_clusters_per_record); 
  105         vol->index_clusters_per_record = NTFS_GETS8(boot + 0x44);
  106         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: "
  107                                 "vol->index_clusters_per_record = 0x%x\n",
  108                                 vol->index_clusters_per_record); 
  109         vol->cluster_size = vol->sector_size << sectors_per_cluster_bits;
  110         vol->cluster_size_bits = ffs(vol->cluster_size) - 1;
  111         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->cluster_size = 0x%x\n",
  112                                 vol->cluster_size); 
  113         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->cluster_size_bits = "
  114                                 "0x%x\n", vol->cluster_size_bits); 
  115         if (vol->mft_clusters_per_record > 0)
  116                 vol->mft_record_size = vol->cluster_size <<
  117                                 (ffs(vol->mft_clusters_per_record) - 1);
  118         else
  119                 /*
  120                  * When mft_record_size < cluster_size, mft_clusters_per_record
  121                  * = -log2(mft_record_size) bytes. mft_record_size normaly is
  122                  * 1024 bytes, which is encoded as 0xF6 (-10 in decimal).
  123                  */
  124                 vol->mft_record_size = 1 << -vol->mft_clusters_per_record;
  125         vol->mft_record_size_bits = ffs(vol->mft_record_size) - 1;
  126         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_record_size = 0x%x"
  127                                 "\n", vol->mft_record_size); 
  128         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_record_size_bits = "
  129                                 "0x%x\n", vol->mft_record_size_bits); 
  130         if (vol->index_clusters_per_record > 0)
  131                 vol->index_record_size = vol->cluster_size <<
  132                                 (ffs(vol->index_clusters_per_record) - 1);
  133         else
  134                 /*
  135                  * When index_record_size < cluster_size,
  136                  * index_clusters_per_record = -log2(index_record_size) bytes.
  137                  * index_record_size normaly equals 4096 bytes, which is
  138                  * encoded as 0xF4 (-12 in decimal).
  139                  */
  140                 vol->index_record_size = 1 << -vol->index_clusters_per_record;
  141         vol->index_record_size_bits = ffs(vol->index_record_size) - 1;
  142         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->index_record_size = "
  143                                 "0x%x\n", vol->index_record_size);
  144         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->index_record_size_bits "
  145                                 "= 0x%x\n", vol->index_record_size_bits);
  146         /*
  147          * Get the size of the volume in clusters (ofs 0x28 is nr_sectors) and
  148          * check for 64-bit-ness. Windows currently only uses 32 bits to save
  149          * the clusters so we do the same as it is much faster on 32-bit CPUs.
  150          */
  151         ll = NTFS_GETS64(boot + 0x28) >> sectors_per_cluster_bits;
  152         if (ll >= (__s64)1 << 31) {
  153                 ntfs_error("Cannot handle 64-bit clusters. Please inform "
  154                                 "linux-ntfs-dev@lists.sf.net that you got this "
  155                                 "error.\n");
  156                 return -1;
  157         }
  158         vol->nr_clusters = (ntfs_cluster_t)ll;
  159         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->nr_clusters = 0x%x\n",
  160                         vol->nr_clusters);
  161         vol->mft_lcn = (ntfs_cluster_t)NTFS_GETS64(boot + 0x30);
  162         vol->mft_mirr_lcn = (ntfs_cluster_t)NTFS_GETS64(boot + 0x38);
  163         /* Determine MFT zone size. */
  164         mft_zone_size = vol->nr_clusters;
  165         switch (vol->mft_zone_multiplier) {  /* % of volume size in clusters */
  166         case 4:
  167                 mft_zone_size >>= 1;                    /* 50%   */
  168                 break;
  169         case 3:
  170                 mft_zone_size = mft_zone_size * 3 >> 3; /* 37.5% */
  171                 break;
  172         case 2:
  173                 mft_zone_size >>= 2;                    /* 25%   */
  174                 break;
  175         /* case 1: */
  176         default:
  177                 mft_zone_size >>= 3;                    /* 12.5% */
  178                 break;
  179         }
  180         /* Setup mft zone. */
  181         vol->mft_zone_start = vol->mft_zone_pos = vol->mft_lcn;
  182         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_pos = %x\n",
  183                         vol->mft_zone_pos);
  184         /*
  185          * Calculate the mft_lcn for an unmodified NTFS volume (see mkntfs
  186          * source) and if the actual mft_lcn is in the expected place or even
  187          * further to the front of the volume, extend the mft_zone to cover the
  188          * beginning of the volume as well. This is in order to protect the
  189          * area reserved for the mft bitmap as well within the mft_zone itself.
  190          * On non-standard volumes we don't protect it as well as the overhead
  191          * would be higher than the speed increase we would get by doing it.
  192          */
  193         tc = (8192 + 2 * vol->cluster_size - 1) / vol->cluster_size;
  194         if (tc * vol->cluster_size < 16 * 1024)
  195                 tc = (16 * 1024 + vol->cluster_size - 1) / vol->cluster_size;
  196         if (vol->mft_zone_start <= tc)
  197                 vol->mft_zone_start = (ntfs_cluster_t)0;
  198         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_start = %x\n",
  199                         vol->mft_zone_start);
  200         /*
  201          * Need to cap the mft zone on non-standard volumes so that it does
  202          * not point outside the boundaries of the volume, we do this by
  203          * halving the zone size until we are inside the volume.
  204          */
  205         vol->mft_zone_end = vol->mft_lcn + mft_zone_size;
  206         while (vol->mft_zone_end >= vol->nr_clusters) {
  207                 mft_zone_size >>= 1;
  208                 vol->mft_zone_end = vol->mft_lcn + mft_zone_size;
  209         }
  210         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_end = %x\n",
  211                         vol->mft_zone_end);
  212         /*
  213          * Set the current position within each data zone to the start of the
  214          * respective zone.
  215          */
  216         vol->data1_zone_pos = vol->mft_zone_end;
  217         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->data1_zone_pos = %x\n",
  218                         vol->data1_zone_pos);
  219         vol->data2_zone_pos = (ntfs_cluster_t)0;
  220         ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->data2_zone_pos = %x\n",
  221                         vol->data2_zone_pos);
  222         /* Set the mft data allocation position to mft record 24. */
  223         vol->mft_data_pos = 24UL;
  224         /* This will be initialized later. */
  225         vol->upcase = 0;
  226         vol->upcase_length = 0;
  227         vol->mft_ino = 0;
  228         return 0;
  229 }
  230 
  231 static void ntfs_init_upcase(ntfs_inode *upcase)
  232 {
  233         ntfs_io io;
  234 #define UPCASE_LENGTH  256
  235         upcase->vol->upcase = ntfs_malloc(UPCASE_LENGTH << 1);
  236         if (!upcase->vol->upcase)
  237                 return;
  238         io.fn_put = ntfs_put;
  239         io.fn_get = 0;
  240         io.param = (char*)upcase->vol->upcase;
  241         io.size = UPCASE_LENGTH << 1;
  242         ntfs_read_attr(upcase, upcase->vol->at_data, 0, 0, &io);
  243         upcase->vol->upcase_length = io.size >> 1;
  244 }
  245 
  246 static int process_attrdef(ntfs_inode* attrdef, ntfs_u8* def)
  247 {
  248         int type = NTFS_GETU32(def+0x80);
  249         int check_type = 0;
  250         ntfs_volume *vol = attrdef->vol;
  251         ntfs_u16* name = (ntfs_u16*)def;
  252 
  253         if (!type) {
  254                 ntfs_debug(DEBUG_OTHER, "process_atrdef: finished processing "
  255                                                         "and returning 1\n");
  256                 return 1;
  257         }
  258         if (ntfs_ua_strncmp(name, "$STANDARD_INFORMATION", 64) == 0) {
  259                 vol->at_standard_information = type;
  260                 check_type = 0x10;
  261         } else if (ntfs_ua_strncmp(name, "$ATTRIBUTE_LIST", 64) == 0) {
  262                 vol->at_attribute_list = type;
  263                 check_type = 0x20;
  264         } else if (ntfs_ua_strncmp(name, "$FILE_NAME", 64) == 0) {
  265                 vol->at_file_name = type;
  266                 check_type = 0x30;
  267         } else if (ntfs_ua_strncmp(name, "$VOLUME_VERSION", 64) == 0) {
  268                 vol->at_volume_version = type;
  269                 check_type = 0x40;
  270         } else if (ntfs_ua_strncmp(name, "$SECURITY_DESCRIPTOR", 64) == 0) {
  271                 vol->at_security_descriptor = type;
  272                 check_type = 0x50;
  273         } else if (ntfs_ua_strncmp(name, "$VOLUME_NAME", 64) == 0) {
  274                 vol->at_volume_name = type;
  275                 check_type = 0x60;
  276         } else if (ntfs_ua_strncmp(name, "$VOLUME_INFORMATION", 64) == 0) {
  277                 vol->at_volume_information = type;
  278                 check_type = 0x70;
  279         } else if (ntfs_ua_strncmp(name, "$DATA", 64) == 0) {
  280                 vol->at_data = type;
  281                 check_type = 0x80;
  282         } else if (ntfs_ua_strncmp(name, "$INDEX_ROOT", 64) == 0) {
  283                 vol->at_index_root = type;
  284                 check_type = 0x90;
  285         } else if (ntfs_ua_strncmp(name, "$INDEX_ALLOCATION", 64) == 0) {
  286                 vol->at_index_allocation = type;
  287                 check_type = 0xA0;
  288         } else if (ntfs_ua_strncmp(name, "$BITMAP", 64) == 0) {
  289                 vol->at_bitmap = type;
  290                 check_type = 0xB0;
  291         } else if (ntfs_ua_strncmp(name, "$SYMBOLIC_LINK", 64) == 0 ||
  292                  ntfs_ua_strncmp(name, "$REPARSE_POINT", 64) == 0) {
  293                 vol->at_symlink = type;
  294                 check_type = 0xC0;
  295         }
  296         if (check_type && check_type != type) {
  297                 ntfs_error("process_attrdef: unexpected type 0x%x for 0x%x\n",
  298                                                         type, check_type);
  299                 return -EINVAL;
  300         }
  301         ntfs_debug(DEBUG_OTHER, "process_attrdef: found %s attribute of type "
  302                         "0x%x\n", check_type ? "known" : "unknown", type);
  303         return 0;
  304 }
  305 
  306 int ntfs_init_attrdef(ntfs_inode* attrdef)
  307 {
  308         ntfs_u8 *buf;
  309         ntfs_io io;
  310         __s64 offset;
  311         unsigned i;
  312         int error;
  313         ntfs_attribute *data;
  314 
  315         ntfs_debug(DEBUG_BSD, "Entered ntfs_init_attrdef()\n");
  316         buf = ntfs_malloc(4050); /* 90*45 */
  317         if (!buf)
  318                 return -ENOMEM;
  319         io.fn_put = ntfs_put;
  320         io.fn_get = ntfs_get;
  321         io.do_read = 1;
  322         offset = 0;
  323         data = ntfs_find_attr(attrdef, attrdef->vol->at_data, 0);
  324         ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after call to "
  325                         "ntfs_find_attr.\n");
  326         if (!data) {
  327                 ntfs_free(buf);
  328                 return -EINVAL;
  329         }
  330         do {
  331                 io.param = buf;
  332                 io.size = 4050;
  333                 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() going to call "
  334                                 "ntfs_readwrite_attr.\n");
  335                 error = ntfs_readwrite_attr(attrdef, data, offset, &io);
  336                 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after call to "
  337                                 "ntfs_readwrite_attr.\n");
  338                 for (i = 0; !error && i <= io.size - 0xA0; i += 0xA0) {
  339                         ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() going "
  340                                         "to call process_attrdef.\n");
  341                         error = process_attrdef(attrdef, buf + i);
  342                         ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after "
  343                                         "call to process_attrdef.\n");
  344                 }
  345                 offset += 4096;
  346         } while (!error && io.size);
  347         ntfs_debug(DEBUG_BSD, "Exiting ntfs_init_attrdef()\n");
  348         ntfs_free(buf);
  349         return error == 1 ? 0 : error;
  350 }
  351 
  352 /* ntfs_get_version will determine the NTFS version of the volume and will
  353  * return the version in a BCD format, with the MSB being the major version
  354  * number and the LSB the minor one. Otherwise return <0 on error.
  355  * Example: version 3.1 will be returned as 0x0301. This has the obvious
  356  * limitation of not coping with version numbers above 0x80 but that shouldn't
  357  * be a problem... */
  358 int ntfs_get_version(ntfs_inode* volume)
  359 {
  360         ntfs_attribute *volinfo;
  361 
  362         volinfo = ntfs_find_attr(volume, volume->vol->at_volume_information, 0);
  363         if (!volinfo) 
  364                 return -EINVAL;
  365         if (!volinfo->resident) {
  366                 ntfs_error("Volume information attribute is not resident!\n");
  367                 return -EINVAL;
  368         }
  369         return ((ntfs_u8*)volinfo->d.data)[8] << 8 | 
  370                ((ntfs_u8*)volinfo->d.data)[9];
  371 }
  372 
  373 int ntfs_load_special_files(ntfs_volume *vol)
  374 {
  375         int error;
  376         ntfs_inode upcase, attrdef, volume;
  377 
  378         vol->mft_ino = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
  379         vol->mftmirr = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
  380         vol->bitmap = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
  381         vol->ino_flags = 4 | 2 | 1;
  382         error = -ENOMEM;
  383         ntfs_debug(DEBUG_BSD, "Going to load MFT\n");
  384         if (!vol->mft_ino || (error = ntfs_init_inode(vol->mft_ino, vol,
  385                         FILE_Mft))) {
  386                 ntfs_error("Problem loading MFT\n");
  387                 return error;
  388         }
  389         ntfs_debug(DEBUG_BSD, "Going to load MIRR\n");
  390         if ((error = ntfs_init_inode(vol->mftmirr, vol, FILE_MftMirr))) {
  391                 ntfs_error("Problem %d loading MFTMirr\n", error);
  392                 return error;
  393         }
  394         ntfs_debug(DEBUG_BSD, "Going to load BITMAP\n");
  395         if ((error = ntfs_init_inode(vol->bitmap, vol, FILE_BitMap))) {
  396                 ntfs_error("Problem loading Bitmap\n");
  397                 return error;
  398         }
  399         ntfs_debug(DEBUG_BSD, "Going to load UPCASE\n");
  400         error = ntfs_init_inode(&upcase, vol, FILE_UpCase);
  401         if (error)
  402                 return error;
  403         ntfs_init_upcase(&upcase);
  404         ntfs_clear_inode(&upcase);
  405         ntfs_debug(DEBUG_BSD, "Going to load ATTRDEF\n");
  406         error = ntfs_init_inode(&attrdef, vol, FILE_AttrDef);
  407         if (error)
  408                 return error;
  409         error = ntfs_init_attrdef(&attrdef);
  410         ntfs_clear_inode(&attrdef);
  411         if (error)
  412                 return error;
  413 
  414         /* Check for NTFS version and if Win2k version (ie. 3.0+) do not allow
  415          * write access since the driver write support is broken. */
  416         ntfs_debug(DEBUG_BSD, "Going to load VOLUME\n");
  417         error = ntfs_init_inode(&volume, vol, FILE_Volume);
  418         if (error)
  419                 return error;
  420         if ((error = ntfs_get_version(&volume)) >= 0x0300 &&
  421             !(NTFS_SB(vol)->s_flags & MS_RDONLY)) {
  422                 NTFS_SB(vol)->s_flags |= MS_RDONLY;
  423                 ntfs_error("Warning! NTFS volume version is Win2k+: Mounting "
  424                            "read-only\n");
  425         }
  426         ntfs_clear_inode(&volume);
  427         if (error < 0)
  428                 return error;
  429         ntfs_debug(DEBUG_BSD, "NTFS volume is v%d.%d\n", error >> 8,
  430                         error & 0xff);
  431         return 0;
  432 }
  433 
  434 int ntfs_release_volume(ntfs_volume *vol)
  435 {
  436         if (((vol->ino_flags & 1) == 1) && vol->mft_ino) {
  437                 ntfs_clear_inode(vol->mft_ino);
  438                 ntfs_free(vol->mft_ino);
  439                 vol->mft_ino = 0;
  440         }
  441         if (((vol->ino_flags & 2) == 2) && vol->mftmirr) {
  442                 ntfs_clear_inode(vol->mftmirr);
  443                 ntfs_free(vol->mftmirr);
  444                 vol->mftmirr = 0;
  445         }
  446         if (((vol->ino_flags & 4) == 4) && vol->bitmap) {
  447                 ntfs_clear_inode(vol->bitmap);
  448                 ntfs_free(vol->bitmap);
  449                 vol->bitmap = 0;
  450         }
  451         ntfs_free(vol->mft);
  452         ntfs_free(vol->upcase);
  453         return 0;
  454 }
  455 
  456 /*
  457  * Writes the volume size (units of clusters) into vol_size.
  458  * Returns 0 if successful or error.
  459  */
  460 int ntfs_get_volumesize(ntfs_volume *vol, ntfs_s64 *vol_size)
  461 {
  462         ntfs_io io;
  463         char *cluster0;
  464 
  465         if (!vol_size)
  466                 return -EFAULT;
  467         cluster0 = ntfs_malloc(vol->cluster_size);
  468         if (!cluster0)
  469                 return -ENOMEM;
  470         io.fn_put = ntfs_put;
  471         io.fn_get = ntfs_get;
  472         io.param = cluster0;
  473         io.do_read = 1;
  474         io.size = vol->cluster_size;
  475         ntfs_getput_clusters(vol, 0, 0, &io);
  476         *vol_size = NTFS_GETU64(cluster0 + 0x28) >>
  477                                         (ffs(NTFS_GETU8(cluster0 + 0xD)) - 1);
  478         ntfs_free(cluster0);
  479         return 0;
  480 }
  481 
  482 static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
  483 
  484 int ntfs_get_free_cluster_count(ntfs_inode *bitmap)
  485 {
  486         ntfs_io io;
  487         int offset, error, clusters;
  488         unsigned char *bits = ntfs_malloc(2048);
  489         if (!bits)
  490                 return -ENOMEM;
  491         offset = clusters = 0;
  492         io.fn_put = ntfs_put;
  493         io.fn_get = ntfs_get;
  494         while (1) {
  495                 register int i;
  496                 io.param = bits;
  497                 io.size = 2048;
  498                 error = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, offset,
  499                                                                         &io);
  500                 if (error || io.size == 0)
  501                         break;
  502                 /* I never thought I would do loop unrolling some day */
  503                 for (i = 0; i < io.size - 8; ) {
  504                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  505                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  506                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  507                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  508                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  509                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  510                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  511                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  512                 }
  513                 while (i < io.size) {
  514                         clusters += nc[bits[i] >> 4];
  515                         clusters += nc[bits[i++] & 0xF];
  516                 }
  517                 offset += io.size;
  518         }
  519         ntfs_free(bits);
  520         return clusters;
  521 }
  522 
  523 /*
  524  * Insert the fixups for the record. The number and location of the fixes
  525  * is obtained from the record header but we double check with @rec_size and
  526  * use that as the upper boundary, if necessary overwriting the count value in
  527  * the record header.
  528  *
  529  * We return 0 on success or -1 if fixup header indicated the beginning of the
  530  * update sequence array to be beyond the valid limit.
  531  */
  532 int ntfs_insert_fixups(unsigned char *rec, int rec_size)
  533 {
  534         int first;
  535         int count;
  536         int offset = -2;
  537         ntfs_u16 fix;
  538         
  539         first = NTFS_GETU16(rec + 4);
  540         count = (rec_size >> NTFS_SECTOR_BITS) + 1;
  541         if (first + count * 2 > NTFS_SECTOR_SIZE - 2) {
  542                 printk(KERN_CRIT "NTFS: ntfs_insert_fixups() detected corrupt "
  543                                 "NTFS record update sequence array position. - "
  544                                 "Cannot hotfix.\n");
  545                 return -1;
  546         }
  547         if (count != NTFS_GETU16(rec + 6)) {
  548                 printk(KERN_ERR "NTFS: ntfs_insert_fixups() detected corrupt "
  549                                 "NTFS record update sequence array size. - "
  550                                 "Applying hotfix.\n");
  551                 NTFS_PUTU16(rec + 6, count);
  552         }
  553         fix = (NTFS_GETU16(rec + first) + 1) & 0xffff;
  554         if (fix == 0xffff || !fix)
  555                 fix = 1;
  556         NTFS_PUTU16(rec + first, fix);
  557         count--;
  558         while (count--) {
  559                 first += 2;
  560                 offset += NTFS_SECTOR_SIZE;
  561                 NTFS_PUTU16(rec + first, NTFS_GETU16(rec + offset));
  562                 NTFS_PUTU16(rec + offset, fix);
  563         }
  564         return 0;
  565 }
  566 
  567 /**
  568  * ntfs_allocate_clusters - allocate logical clusters on an ntfs volume
  569  * @vol:        volume on which to allocate clusters
  570  * @location:   preferred location for first allocated cluster
  571  * @count:      number of clusters to allocate
  572  * @rl:         address of pointer in which to return the allocated run list
  573  * @rl_len:     the number of elements returned in @*rl
  574  *
  575  * Allocate @*count clusters (LCNs), preferably beginning at @*location in the
  576  * bitmap of the volume @vol. If @*location is -1, it does not matter where the
  577  * clusters are. @rl is the address of a ntfs_runlist pointer which this
  578  * function will allocate and fill with the runlist of the allocated clusters.
  579  * It is the callers responsibility to ntfs_vfree() @*rl after she is finished
  580  * with it. If the function was not successful, @*rl will be set to NULL.
  581  * @*rl_len will contain the number of ntfs_runlist elements in @*rl or 0 if
  582  * @*rl is NULL.
  583  *
  584  * Return 0 on success, or -errno on error. On success, @*location and @*count
  585  * say what was really allocated. On -ENOSPC, @*location and @*count say what
  586  * could have been allocated. If nothing could be allocated or a different
  587  * error occured, @*location = -1 and @*count = 0.
  588  *
  589  * There are two data zones. First is the area between the end of the mft zone
  590  * and the end of the volume, and second is the area between the start of the
  591  * volume and the start of the mft zone. On unmodified/standard volumes, the
  592  * second mft zone doesn't exist due to the mft zone being expanded to cover
  593  * the start of volume in order to reserve space for the mft bitmap attribute.
  594  *
  595  * This is not the prettiest function but the complexity stems from the need of
  596  * implementing the mft vs data zoned approach and from the fact that we have
  597  * access to the lcn bitmap in portions of PAGE_SIZE bytes at a time, so we
  598  * need to cope with crossing over boundaries of two pages. Further, the fact
  599  * that the allocator allows for caller supplied hints as to the location of
  600  * where allocation should begin and the fact that the allocator keeps track of
  601  * where in the data zones the next natural allocation should occur, contribute
  602  * to the complexity of the function. But it should all be worthwhile, because
  603  * this allocator should: 1) be a full implementation of the MFT zone approach
  604  * used by Windows, 2) cause reduction in fragmentation as much as possible,
  605  * and 3) be speedy in allocations (the code is not optimized for speed, but
  606  * the algorithm is, so further speed improvements are probably possible).
  607  *
  608  * FIXME: Really need finer-grained locking but this will do for the moment. I
  609  * just want to kill all races and have a working allocator. When that is done,
  610  * we can beautify... (AIA)
  611  * 
  612  * FIXME: We should be monitoring cluster allocation and increment the MFT zone
  613  * size dynamically but this is something for the future. We will just cause
  614  * heavier fragmentation by not doing it and I am not even sure Windows would
  615  * grow the MFT zone dynamically, so might even be correct not doing this. The
  616  * overhead in doing dynamic MFT zone expansion would be very large and unlikely
  617  * worth the effort. (AIA)
  618  *
  619  * TODO: I have added in double the required zone position pointer wrap around
  620  * logic which can be optimized to having only one of the two logic sets.
  621  * However, having the double logic will work fine, but if we have only one of
  622  * the sets and we get it wrong somewhere, then we get into trouble, so
  623  * removing the duplicate logic requires _very_ careful consideration of _all_
  624  * possible code paths. So at least for now, I am leaving the double logic -
  625  * better safe than sorry... (AIA)
  626  */
  627 int ntfs_allocate_clusters(ntfs_volume *vol, ntfs_cluster_t *location,
  628                 ntfs_cluster_t *count, ntfs_runlist **rl, int *rl_len,
  629                 const NTFS_CLUSTER_ALLOCATION_ZONES zone)
  630 {
  631         ntfs_runlist *rl2 = NULL, *rlt;
  632         ntfs_attribute *data;
  633         ntfs_cluster_t buf_pos, zone_start, zone_end, mft_zone_size;
  634         ntfs_cluster_t lcn, last_read_pos, prev_lcn = (ntfs_cluster_t)0;
  635         ntfs_cluster_t initial_location, prev_run_len = (ntfs_cluster_t)0;
  636         ntfs_cluster_t clusters = (ntfs_cluster_t)0;
  637         unsigned char *buf, *byte, bit, search_zone, done_zones;
  638         unsigned char pass, need_writeback;
  639         int rlpos = 0, rlsize, buf_size, err = 0;
  640         ntfs_io io;
  641 
  642         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Entering with *location = "
  643                         "0x%x, *count = 0x%x, zone = %s_ZONE.\n", *location,
  644                         *count, zone == DATA_ZONE ? "DATA" : "MFT");
  645         buf = (char*)__get_free_page(GFP_NOFS);
  646         if (!buf) {
  647                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Returning "
  648                                 "-ENOMEM.\n");
  649                 return -ENOMEM;
  650         }
  651         io.fn_put = ntfs_put;
  652         io.fn_get = ntfs_get;
  653         lock_kernel();
  654         /* Get the $DATA attribute of $Bitmap. */
  655         data = ntfs_find_attr(vol->bitmap, vol->at_data, 0);
  656         if (!data) {
  657                 err = -EINVAL;
  658                 goto err_ret;
  659         }
  660         /*
  661          * If no specific location was requested, use the current data zone
  662          * position, otherwise use the requested location but make sure it lies
  663          * outside the mft zone. Also set done_zones to 0 (no zones done) and
  664          * pass depending on whether we are starting inside a zone (1) or
  665          * at the beginning of a zone (2). If requesting from the MFT_ZONE, then
  666          * we either start at the current position within the mft zone or at the
  667          * specified position and if the latter is out of bounds then we start
  668          * at the beginning of the MFT_ZONE.
  669          */
  670         done_zones = 0;
  671         pass = 1;
  672         /*
  673          * zone_start and zone_end are the current search range. search_zone
  674          * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of
  675          * volume) and 4 for data zone 2 (start of volume till start of mft
  676          * zone).
  677          */
  678         zone_start = *location;
  679         if (zone_start < 0) {
  680                 if (zone == DATA_ZONE)
  681                         zone_start = vol->data1_zone_pos;
  682                 else
  683                         zone_start = vol->mft_zone_pos;
  684                 if (!zone_start)
  685                         /*
  686                          * Zone starts at beginning of volume which means a
  687                          * single pass is sufficient.
  688                          */
  689                         pass = 2;
  690         } else if (zone_start >= vol->mft_zone_start && zone_start <
  691                         vol->mft_zone_end && zone == DATA_ZONE) {
  692                 zone_start = vol->mft_zone_end;
  693                 pass = 2;
  694         } else if ((zone_start < vol->mft_zone_start || zone_start >=
  695                         vol->mft_zone_end) && zone == MFT_ZONE) {
  696                 zone_start = vol->mft_lcn;
  697                 if (!vol->mft_zone_end)
  698                         zone_start = (ntfs_cluster_t)0;
  699                 pass = 2;
  700         }
  701         if (zone == DATA_ZONE) {
  702                 /* Skip searching the mft zone. */
  703                 done_zones |= 1;
  704                 if (zone_start >= vol->mft_zone_end) {
  705                         zone_end = vol->nr_clusters;
  706                         search_zone = 2;
  707                 } else {
  708                         zone_end = vol->mft_zone_start;
  709                         search_zone = 4;
  710                 }
  711         } else /* if (zone == MFT_ZONE) */ {
  712                 zone_end = vol->mft_zone_end;
  713                 search_zone = 1;
  714         }
  715         /*
  716          * buf_pos is the current bit position inside the bitmap. We use
  717          * initial_location to determine whether or not to do a zone switch.
  718          */
  719         buf_pos = initial_location = zone_start;
  720         /* Loop until all clusters are allocated, i.e. clusters == 0. */
  721         clusters = *count;
  722         rlpos = rlsize = 0;
  723         if (*count <= 0) {
  724                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *count <= 0, "
  725                                 "returning -EINVAL.\n");
  726                 err = -EINVAL;
  727                 goto err_ret;
  728         }
  729         while (1) {
  730                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Start of outer while "
  731                                 "loop: done_zones = 0x%x, search_zone = %i, "
  732                                 "pass = %i, zone_start = 0x%x, zone_end = "
  733                                 "0x%x, initial_location = 0x%x, buf_pos = "
  734                                 "0x%x, rlpos = %i, rlsize = %i.\n",
  735                                 done_zones, search_zone, pass, zone_start,
  736                                 zone_end, initial_location, buf_pos, rlpos,
  737                                 rlsize);
  738                 /* Loop until we run out of free clusters. */
  739                 io.param = buf;
  740                 io.size = PAGE_SIZE;
  741                 io.do_read = 1;
  742                 last_read_pos = buf_pos >> 3;
  743                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): last_read_pos = "
  744                                 "0x%x.\n", last_read_pos);
  745                 err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
  746                                 &io);
  747                 if (err) {
  748                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  749                                         "ntfs_read_attr failed with error "
  750                                         "code %i, going to err_ret.\n", -err);
  751                         goto err_ret;
  752                 }
  753                 if (!io.size) {
  754                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): !io.size, "
  755                                         "going to zone_pass_done.\n");
  756                         goto zone_pass_done;
  757                 }
  758                 buf_size = io.size << 3;
  759                 lcn = buf_pos & 7;
  760                 buf_pos &= ~7;
  761                 need_writeback = 0;
  762                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Before inner while "
  763                                 "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
  764                                 "0x%x, need_writeback = %i.\n", buf_size, lcn,
  765                                 buf_pos, need_writeback);
  766                 while (lcn < buf_size && lcn + buf_pos < zone_end) {
  767                         byte = buf + (lcn >> 3);
  768                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): In inner "
  769                                         "while loop: buf_size = 0x%x, lcn = "
  770                                         "0x%x, buf_pos = 0x%x, need_writeback "
  771                                         "= %i, byte ofs = 0x%x, *byte = "
  772                                         "0x%x.\n", buf_size, lcn, buf_pos,
  773                                         need_writeback, lcn >> 3, *byte);
  774                         /* Skip full bytes. */
  775                         if (*byte == 0xff) {
  776                                 lcn += 8;
  777                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  778                                                 "continuing while loop 1.\n");
  779                                 continue;
  780                         }
  781                         bit = 1 << (lcn & 7);
  782                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): bit = %i.\n",
  783                                         bit);
  784                         /* If the bit is already set, go onto the next one. */
  785                         if (*byte & bit) {
  786                                 lcn++;
  787                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  788                                                 "continuing while loop 2.\n");
  789                                 continue;
  790                         }
  791                         /* Allocate the bitmap bit. */
  792                         *byte |= bit;
  793                         /* We need to write this bitmap buffer back to disk! */
  794                         need_writeback = 1;
  795                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *byte = "
  796                                         "0x%x, need_writeback = %i.\n", *byte,
  797                                         need_writeback);
  798                         /* Reallocate memory if necessary. */
  799                         if ((rlpos + 2) * sizeof(ntfs_runlist) >= rlsize) {
  800                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  801                                                 "Reallocating space.\n");
  802                                 /* Setup first free bit return value. */
  803                                 if (!rl2) {
  804                                         *location = lcn + buf_pos;
  805                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  806                                                         "(): *location = "
  807                                                         "0x%x.\n", *location);
  808                                 }
  809                                 rlsize += PAGE_SIZE;
  810                                 rlt = ntfs_vmalloc(rlsize);
  811                                 if (!rlt) {
  812                                         err = -ENOMEM;
  813                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  814                                                         "(): Failed to "
  815                                                         "allocate memory, "
  816                                                         "returning -ENOMEM, "
  817                                                         "going to "
  818                                                         "wb_err_ret.\n");
  819                                         goto wb_err_ret;
  820                                 }
  821                                 if (rl2) {
  822                                         ntfs_memcpy(rlt, rl2, rlsize -
  823                                                         PAGE_SIZE);
  824                                         ntfs_vfree(rl2);
  825                                 }
  826                                 rl2 = rlt;
  827                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  828                                                 "Reallocated memory, rlsize = "
  829                                                 "0x%x.\n", rlsize);
  830                         }
  831                         /*
  832                          * Coalesce with previous run if adjacent LCNs.
  833                          * Otherwise, append a new run.
  834                          */
  835                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Adding run "
  836                                         "(lcn 0x%x, len 0x%x), prev_lcn = "
  837                                         "0x%x, lcn = 0x%x, buf_pos = 0x%x, "
  838                                         "prev_run_len = 0x%x, rlpos = %i.\n",
  839                                         lcn + buf_pos, 1, prev_lcn, lcn,
  840                                         buf_pos, prev_run_len, rlpos);
  841                         if (prev_lcn == lcn + buf_pos - prev_run_len && rlpos) {
  842                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  843                                                 "Coalescing to run (lcn 0x%x, "
  844                                                 "len 0x%x).\n",
  845                                                 rl2[rlpos - 1].lcn,
  846                                                 rl2[rlpos - 1].len);
  847                                 rl2[rlpos - 1].len = ++prev_run_len;
  848                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  849                                                 "Run now (lcn 0x%x, len 0x%x), "
  850                                                 "prev_run_len = 0x%x.\n",
  851                                                 rl2[rlpos - 1].lcn,
  852                                                 rl2[rlpos - 1].len,
  853                                                 prev_run_len);
  854                         } else {
  855                                 if (rlpos)
  856                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  857                                                         "(): Adding new run, "
  858                                                         "(previous run lcn "
  859                                                         "0x%x, len 0x%x).\n",
  860                                                         rl2[rlpos - 1].lcn,
  861                                                         rl2[rlpos - 1].len);
  862                                 else
  863                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  864                                                         "(): Adding new run, "
  865                                                         "is first run.\n");
  866                                 rl2[rlpos].lcn = prev_lcn = lcn + buf_pos;
  867                                 rl2[rlpos].len = prev_run_len =
  868                                                 (ntfs_cluster_t)1;
  869                                 
  870                                 rlpos++;
  871                         }
  872                         /* Done? */
  873                         if (!--clusters) {
  874                                 ntfs_cluster_t tc;
  875                                 /*
  876                                  * Update the current zone position. Positions
  877                                  * of already scanned zones have been updated
  878                                  * during the respective zone switches.
  879                                  */
  880                                 tc = lcn + buf_pos + 1;
  881                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  882                                                 "Done. Updating current zone "
  883                                                 "position, tc = 0x%x, "
  884                                                 "search_zone = %i.\n", tc,
  885                                                 search_zone);
  886                                 switch (search_zone) {
  887                                 case 1:
  888                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  889                                                         "(): Before checks, "
  890                                                         "vol->mft_zone_pos = "
  891                                                         "0x%x.\n",
  892                                                         vol->mft_zone_pos);
  893                                         if (tc >= vol->mft_zone_end) {
  894                                                 vol->mft_zone_pos =
  895                                                                 vol->mft_lcn;
  896                                                 if (!vol->mft_zone_end)
  897                                                         vol->mft_zone_pos =
  898                                                              (ntfs_cluster_t)0;
  899                                         } else if ((initial_location >=
  900                                                         vol->mft_zone_pos ||
  901                                                         tc > vol->mft_zone_pos)
  902                                                         && tc >= vol->mft_lcn)
  903                                                 vol->mft_zone_pos = tc;
  904                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  905                                                         "(): After checks, "
  906                                                         "vol->mft_zone_pos = "
  907                                                         "0x%x.\n",
  908                                                         vol->mft_zone_pos);
  909                                         break;
  910                                 case 2:
  911                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  912                                                         "(): Before checks, "
  913                                                         "vol->data1_zone_pos = "
  914                                                         "0x%x.\n",
  915                                                         vol->data1_zone_pos);
  916                                         if (tc >= vol->nr_clusters)
  917                                                 vol->data1_zone_pos =
  918                                                              vol->mft_zone_end;
  919                                         else if ((initial_location >=
  920                                                     vol->data1_zone_pos ||
  921                                                     tc > vol->data1_zone_pos)
  922                                                     && tc >= vol->mft_zone_end)
  923                                                 vol->data1_zone_pos = tc;
  924                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  925                                                         "(): After checks, "
  926                                                         "vol->data1_zone_pos = "
  927                                                         "0x%x.\n",
  928                                                         vol->data1_zone_pos);
  929                                         break;
  930                                 case 4:
  931                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  932                                                         "(): Before checks, "
  933                                                         "vol->data2_zone_pos = "
  934                                                         "0x%x.\n",
  935                                                         vol->data2_zone_pos);
  936                                         if (tc >= vol->mft_zone_start)
  937                                                 vol->data2_zone_pos =
  938                                                         (ntfs_cluster_t)0;
  939                                         else if (initial_location >=
  940                                                       vol->data2_zone_pos ||
  941                                                       tc > vol->data2_zone_pos)
  942                                                 vol->data2_zone_pos = tc;
  943                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
  944                                                         "(): After checks, "
  945                                                         "vol->data2_zone_pos = "
  946                                                         "0x%x.\n",
  947                                                         vol->data2_zone_pos);
  948                                         break;
  949                                 default:
  950                                         BUG();
  951                                 }
  952                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  953                                                 "Going to done_ret.\n");
  954                                 goto done_ret;
  955                         }
  956                         lcn++;
  957                 }
  958                 buf_pos += buf_size;
  959                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After inner while "
  960                                 "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
  961                                 "0x%x, need_writeback = %i.\n", buf_size, lcn,
  962                                 buf_pos, need_writeback);
  963                 if (need_writeback) {
  964                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing "
  965                                         "back.\n");
  966                         need_writeback = 0;
  967                         io.param = buf;
  968                         io.do_read = 0;
  969                         err = ntfs_readwrite_attr(vol->bitmap, data,
  970                                         last_read_pos, &io);
  971                         if (err) {
  972                                 ntfs_error(__FUNCTION__ "(): Bitmap writeback "
  973                                                 "failed in read next buffer "
  974                                                 "code path with error code "
  975                                                 "%i.\n", -err);
  976                                 goto err_ret;
  977                         }
  978                 }
  979                 if (buf_pos < zone_end) {
  980                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
  981                                         "outer while loop, buf_pos = 0x%x, "
  982                                         "zone_end = 0x%x.\n", buf_pos,
  983                                         zone_end);
  984                         continue;
  985                 }
  986 zone_pass_done: /* Finished with the current zone pass. */
  987                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At zone_pass_done, "
  988                                 "pass = %i.\n", pass);
  989                 if (pass == 1) {
  990                         /*
  991                          * Now do pass 2, scanning the first part of the zone
  992                          * we omitted in pass 1.
  993                          */
  994                         pass = 2;
  995                         zone_end = zone_start;
  996                         switch (search_zone) {
  997                         case 1: /* mft_zone */
  998                                 zone_start = vol->mft_zone_start;
  999                                 break;
 1000                         case 2: /* data1_zone */
 1001                                 zone_start = vol->mft_zone_end;
 1002                                 break;
 1003                         case 4: /* data2_zone */
 1004                                 zone_start = (ntfs_cluster_t)0;
 1005                                 break;
 1006                         default:
 1007                                 BUG();
 1008                         }
 1009                         /* Sanity check. */
 1010                         if (zone_end < zone_start)
 1011                                 zone_end = zone_start;
 1012                         buf_pos = zone_start;
 1013                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
 1014                                         "outer while loop, pass = 2, "
 1015                                         "zone_start = 0x%x, zone_end = 0x%x, "
 1016                                         "buf_pos = 0x%x.\n");
 1017                         continue;
 1018                 } /* pass == 2 */
 1019 done_zones_check:
 1020                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_zones_check, "
 1021                                 "search_zone = %i, done_zones before = 0x%x, "
 1022                                 "done_zones after = 0x%x.\n",
 1023                                 search_zone, done_zones, done_zones |
 1024                                 search_zone);
 1025                 done_zones |= search_zone;
 1026                 if (done_zones < 7) {
 1027                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Switching "
 1028                                         "zone.\n");
 1029                         /* Now switch to the next zone we haven't done yet. */
 1030                         pass = 1;
 1031                         switch (search_zone) {
 1032                         case 1:
 1033                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
 1034                                                 "Switching from mft zone to "
 1035                                                 "data1 zone.\n");
 1036                                 /* Update mft zone position. */
 1037                                 if (rlpos) {
 1038                                         ntfs_cluster_t tc;
 1039                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
 1040                                                         "(): Before checks, "
 1041                                                         "vol->mft_zone_pos = "
 1042                                                         "0x%x.\n",
 1043                                                         vol->mft_zone_pos);
 1044                                         tc = rl2[rlpos - 1].lcn +
 1045                                                         rl2[rlpos - 1].len;
 1046                                         if (tc >= vol->mft_zone_end) {
 1047                                                 vol->mft_zone_pos =
 1048                                                                 vol->mft_lcn;
 1049                                                 if (!vol->mft_zone_end)
 1050                                                         vol->mft_zone_pos =
 1051                                                              (ntfs_cluster_t)0;
 1052                                         } else if ((initial_location >=
 1053                                                         vol->mft_zone_pos ||
 1054                                                         tc > vol->mft_zone_pos)
 1055                                                         && tc >= vol->mft_lcn)
 1056                                                 vol->mft_zone_pos = tc;
 1057                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
 1058                                                         "(): After checks, "
 1059                                                         "vol->mft_zone_pos = "
 1060                                                         "0x%x.\n",
 1061                                                         vol->mft_zone_pos);
 1062                                 }
 1063                                 /* Switch from mft zone to data1 zone. */
 1064 switch_to_data1_zone:           search_zone = 2;
 1065                                 zone_start = initial_location =
 1066                                                 vol->data1_zone_pos;
 1067                                 zone_end = vol->nr_clusters;
 1068                                 if (zone_start == vol->mft_zone_end)
 1069                                         pass = 2;
 1070                                 if (zone_start >= zone_end) {
 1071                                         vol->data1_zone_pos = zone_start =
 1072                                                         vol->mft_zone_end;
 1073                                         pass = 2;
 1074                                 }
 1075                                 break;
 1076                         case 2:
 1077                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
 1078                                                 "Switching from data1 zone to "
 1079                                                 "data2 zone.\n");
 1080                                 /* Update data1 zone position. */
 1081                                 if (rlpos) {
 1082                                         ntfs_cluster_t tc;
 1083                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
 1084                                                         "(): Before checks, "
 1085                                                         "vol->data1_zone_pos = "
 1086                                                         "0x%x.\n",
 1087                                                         vol->data1_zone_pos);
 1088                                         tc = rl2[rlpos - 1].lcn +
 1089                                                         rl2[rlpos - 1].len;
 1090                                         if (tc >= vol->nr_clusters)
 1091                                                 vol->data1_zone_pos =
 1092                                                              vol->mft_zone_end;
 1093                                         else if ((initial_location >=
 1094                                                     vol->data1_zone_pos ||
 1095                                                     tc > vol->data1_zone_pos)
 1096                                                     && tc >= vol->mft_zone_end)
 1097                                                 vol->data1_zone_pos = tc;
 1098                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
 1099                                                         "(): After checks, "
 1100                                                         "vol->data1_zone_pos = "
 1101                                                         "0x%x.\n",
 1102                                                         vol->data1_zone_pos);
 1103                                 }
 1104                                 /* Switch from data1 zone to data2 zone. */
 1105                                 search_zone = 4;
 1106                                 zone_start = initial_location =
 1107                                                 vol->data2_zone_pos;
 1108                                 zone_end = vol->mft_zone_start;
 1109                                 if (!zone_start)
 1110                                         pass = 2;
 1111                                 if (zone_start >= zone_end) {
 1112                                         vol->data2_zone_pos = zone_start =
 1113                                                         initial_location =
 1114                                                         (ntfs_cluster_t)0;
 1115                                         pass = 2;
 1116                                 }
 1117                                 break;
 1118                         case 4:
 1119                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
 1120                                                 "Switching from data2 zone to "
 1121                                                 "data1 zone.\n");
 1122                                 /* Update data2 zone position. */
 1123                                 if (rlpos) {
 1124                                         ntfs_cluster_t tc;
 1125                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
 1126                                                         "(): Before checks, "
 1127                                                         "vol->data2_zone_pos = "
 1128                                                         "0x%x.\n",
 1129                                                         vol->data2_zone_pos);
 1130                                         tc = rl2[rlpos - 1].lcn +
 1131                                                         rl2[rlpos - 1].len;
 1132                                         if (tc >= vol->mft_zone_start)
 1133                                                 vol->data2_zone_pos =
 1134                                                              (ntfs_cluster_t)0;
 1135                                         else if (initial_location >=
 1136                                                       vol->data2_zone_pos ||
 1137                                                       tc > vol->data2_zone_pos)
 1138                                                 vol->data2_zone_pos = tc;
 1139                                         ntfs_debug(DEBUG_OTHER, __FUNCTION__
 1140                                                         "(): After checks, "
 1141                                                         "vol->data2_zone_pos = "
 1142                                                         "0x%x.\n",
 1143                                                         vol->data2_zone_pos);
 1144                                 }
 1145                                 /* Switch from data2 zone to data1 zone. */
 1146                                 goto switch_to_data1_zone; /* See above. */
 1147                         default:
 1148                                 BUG();
 1149                         }
 1150                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After zone "
 1151                                         "switch, search_zone = %i, pass = %i, "
 1152                                         "initial_location = 0x%x, zone_start "
 1153                                         "= 0x%x, zone_end = 0x%x.\n",
 1154                                         search_zone, pass, initial_location,
 1155                                         zone_start, zone_end);
 1156                         buf_pos = zone_start;
 1157                         if (zone_start == zone_end) {
 1158                                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
 1159                                                 "Empty zone, going to "
 1160                                                 "done_zones_check.\n");
 1161                                 /* Empty zone. Don't bother searching it. */
 1162                                 goto done_zones_check;
 1163                         }
 1164                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
 1165                                         "outer while loop.\n");
 1166                         continue;
 1167                 } /* done_zones == 7 */
 1168                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): All zones are "
 1169                                 "finished.\n");
 1170                 /*
 1171                  * All zones are finished! If DATA_ZONE, shrink mft zone. If
 1172                  * MFT_ZONE, we have really run out of space.
 1173                  */
 1174                 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start;
 1175                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): vol->mft_zone_start "
 1176                                 "= 0x%x, vol->mft_zone_end = 0x%x, "
 1177                                 "mft_zone_size = 0x%x.\n", vol->mft_zone_start,
 1178                                 vol->mft_zone_end, mft_zone_size);
 1179                 if (zone == MFT_ZONE || mft_zone_size <= (ntfs_cluster_t)0) {
 1180                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): No free "
 1181                                         "clusters left, returning -ENOSPC, "
 1182                                         "going to fail_ret.\n");
 1183                         /* Really no more space left on device. */
 1184                         err = -ENOSPC;
 1185                         goto fail_ret;
 1186                 } /* zone == DATA_ZONE && mft_zone_size > 0 */
 1187                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Shrinking mft "
 1188                                 "zone.\n");
 1189                 zone_end = vol->mft_zone_end;
 1190                 mft_zone_size >>= 1;
 1191                 if (mft_zone_size > (ntfs_cluster_t)0)
 1192                         vol->mft_zone_end = vol->mft_zone_start + mft_zone_size;
 1193                 else /* mft zone and data2 zone no longer exist. */
 1194                         vol->data2_zone_pos = vol->mft_zone_start =
 1195                                         vol->mft_zone_end = (ntfs_cluster_t)0;
 1196                 if (vol->mft_zone_pos >= vol->mft_zone_end) {
 1197                         vol->mft_zone_pos = vol->mft_lcn;
 1198                         if (!vol->mft_zone_end)
 1199                                 vol->mft_zone_pos = (ntfs_cluster_t)0;
 1200                 }
 1201                 buf_pos = zone_start = initial_location =
 1202                                 vol->data1_zone_pos = vol->mft_zone_end;
 1203                 search_zone = 2;
 1204                 pass = 2;
 1205                 done_zones &= ~2;
 1206                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After shrinking mft "
 1207                                 "zone, mft_zone_size = 0x%x, "
 1208                                 "vol->mft_zone_start = 0x%x, vol->mft_zone_end "
 1209                                 "= 0x%x, vol->mft_zone_pos = 0x%x, search_zone "
 1210                                 "= 2, pass = 2, dones_zones = 0x%x, zone_start "
 1211                                 "= 0x%x, zone_end = 0x%x, vol->data1_zone_pos "
 1212                                 "= 0x%x, continuing outer while loop.\n",
 1213                                 mft_zone_size, vol->mft_zone_start,
 1214                                 vol->mft_zone_end, vol->mft_zone_pos,
 1215                                 search_zone, pass, done_zones, zone_start,
 1216                                 zone_end, vol->data1_zone_pos);
 1217         }
 1218         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After outer while loop.\n");
 1219 done_ret:
 1220         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_ret.\n");
 1221         rl2[rlpos].lcn = (ntfs_cluster_t)-1;
 1222         rl2[rlpos].len = (ntfs_cluster_t)0;
 1223         *rl = rl2;
 1224         *rl_len = rlpos;
 1225         if (need_writeback) {
 1226                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing back.\n");
 1227                 need_writeback = 0;
 1228                 io.param = buf;
 1229                 io.do_read = 0;
 1230                 err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
 1231                                 &io);
 1232                 if (err) {
 1233                         ntfs_error(__FUNCTION__ "(): Bitmap writeback failed "
 1234                                         "in done code path with error code "
 1235                                         "%i.\n", -err);
 1236                         goto err_ret;
 1237                 }
 1238                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Wrote 0x%Lx bytes.\n",
 1239                                 io.size);
 1240         }
 1241 done_fail_ret:
 1242         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_fail_ret (follows "
 1243                         "done_ret).\n");
 1244         unlock_kernel();
 1245         free_page((unsigned long)buf);
 1246         if (err)
 1247                 ntfs_debug(DEBUG_FILE3, __FUNCTION__ "(): Failed to allocate "
 1248                                 "clusters. Returning with error code %i.\n",
 1249                                 -err);
 1250         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Syncing $Bitmap inode.\n");
 1251         if (ntfs_update_inode(vol->bitmap))
 1252                 ntfs_error(__FUNCTION__ "(): Failed to sync inode $Bitmap. "
 1253                                 "Continuing anyway.\n");
 1254         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Returning with code %i.\n",
 1255                         err);
 1256         return err;
 1257 fail_ret:
 1258         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At fail_ret.\n");
 1259         if (rl2) {
 1260                 if (err == -ENOSPC) {
 1261                         /* Return first free lcn and count of free clusters. */
 1262                         *location = rl2[0].lcn;
 1263                         *count -= clusters;
 1264                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): err = "
 1265                                         "-ENOSPC, *location = 0x%x, *count = "
 1266                                         "0x%x.\n", *location, *count);
 1267                 }
 1268                 /* Deallocate all allocated clusters. */
 1269                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Deallocating "
 1270                                 "allocated clusters.\n");
 1271                 ntfs_deallocate_clusters(vol, rl2, rlpos);
 1272                 /* Free the runlist. */
 1273                 ntfs_vfree(rl2);
 1274         } else {
 1275                 if (err == -ENOSPC) {
 1276                         /* Nothing free at all. */
 1277                         *location = vol->data1_zone_pos; /* Irrelevant... */
 1278                         *count = 0;
 1279                         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): No space "
 1280                                         "left at all, err = -ENOSPC, *location "
 1281                                         "= 0x%x, *count = 0.\n", *location);
 1282                 }
 1283         }
 1284         *rl = NULL;
 1285         *rl_len = 0;
 1286         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *rl = NULL, *rl_len = 0, "
 1287                         "going to done_fail_ret.\n");
 1288         goto done_fail_ret;
 1289 wb_err_ret:
 1290         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At wb_err_ret.\n");
 1291         if (need_writeback) {
 1292                 int __err;
 1293                 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing back.\n");
 1294                 io.param = buf;
 1295                 io.do_read = 0;
 1296                 __err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
 1297                                 &io);
 1298                 if (__err)
 1299                         ntfs_error(__FUNCTION__ "(): Bitmap writeback failed "
 1300                                         "in error code path with error code "
 1301                                         "%i.\n", -__err);
 1302                 need_writeback = 0;
 1303         }
 1304 err_ret:
 1305         ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At err_ret, *location = -1, "
 1306                         "*count = 0, going to fail_ret.\n");
 1307         *location = -1;
 1308         *count = 0;
 1309         goto fail_ret;
 1310 }
 1311 
 1312 /*
 1313  * IMPORTANT: Caller has to hold big kernel lock or the race monster will come
 1314  * to get you! (-;
 1315  * TODO: Need our own lock for bitmap accesses but BKL is more secure for now,
 1316  * considering we might not have covered all places with a lock yet. In that
 1317  * case the BKL offers a one way exclusion which is better than no exclusion
 1318  * at all... (AIA)
 1319  */
 1320 static int ntfs_clear_bitrange(ntfs_inode *bitmap,
 1321                 const ntfs_cluster_t start_bit, const ntfs_cluster_t count)
 1322 {
 1323         ntfs_cluster_t buf_size, bit, nr_bits = count;
 1324         unsigned char *buf, *byte;
 1325         int err;
 1326         ntfs_io io;
 1327 
 1328         io.fn_put = ntfs_put;
 1329         io.fn_get = ntfs_get;
 1330         /* Calculate the required buffer size in bytes. */
 1331         buf_size = (ntfs_cluster_t)((start_bit & 7) + nr_bits + 7) >> 3;
 1332         if (buf_size <= (ntfs_cluster_t)(64 * 1024))
 1333                 buf = ntfs_malloc(buf_size);
 1334         else
 1335                 buf = ntfs_vmalloc(buf_size);
 1336         if (!buf)
 1337                 return -ENOMEM;
 1338         /* Read the bitmap from the data attribute. */
 1339         io.param = byte = buf;
 1340         io.size = buf_size;
 1341         err = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
 1342                         &io);
 1343         if (err || io.size != buf_size)
 1344                 goto err_out;
 1345         /* Now clear the bits in the read bitmap. */
 1346         bit = start_bit & 7;
 1347         while (bit && nr_bits) { /* Process first partial byte, if present. */
 1348                 *byte &= ~(1 << bit++);
 1349                 nr_bits--;
 1350                 bit &= 7;
 1351                 if (!bit)
 1352                         byte++;
 1353         }
 1354         while (nr_bits >= 8) { /* Process full bytes. */
 1355                 *byte = 0;
 1356                 nr_bits -= 8;
 1357                 byte++;
 1358         }
 1359         bit = 0;
 1360         while (nr_bits) { /* Process last partial byte, if present. */
 1361                 *byte &= ~(1 << bit);
 1362                 nr_bits--;
 1363                 bit++;
 1364         }
 1365         /* Write the modified bitmap back to disk. */
 1366         io.param = buf;
 1367         io.size = buf_size;
 1368         err = ntfs_write_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
 1369                         &io);
 1370 err_out:
 1371         if (buf_size <= (ntfs_cluster_t)(64 * 1024))
 1372                 ntfs_free(buf);
 1373         else
 1374                 ntfs_vfree(buf);
 1375         if (!err && io.size != buf_size)
 1376                 err = -EIO;
 1377         return err;
 1378 }
 1379 
 1380 /*
 1381  * See comments for lack of zone adjustments below in the description of the
 1382  * function ntfs_deallocate_clusters().
 1383  */
 1384 int ntfs_deallocate_cluster_run(const ntfs_volume *vol,
 1385                 const ntfs_cluster_t lcn, const ntfs_cluster_t len)
 1386 {
 1387         int err;
 1388 
 1389         lock_kernel();
 1390         err = ntfs_clear_bitrange(vol->bitmap, lcn, len);
 1391         unlock_kernel();
 1392         return err;
 1393 }
 1394 
 1395 /*
 1396  * This is inefficient, but logically trivial, so will do for now. Note, we
 1397  * do not touch the mft nor the data zones here because we want to minimize
 1398  * recycling of clusters to enhance the chances of data being undeleteable.
 1399  * Also we don't want the overhead. Instead we do one additional sweep of the
 1400  * current data zone during cluster allocation to check for freed clusters.
 1401  */
 1402 int ntfs_deallocate_clusters(const ntfs_volume *vol, const ntfs_runlist *rl,
 1403                 const int rl_len)
 1404 {
 1405         int i, err;
 1406 
 1407         lock_kernel();
 1408         for (i = err = 0; i < rl_len && !err; i++)
 1409                 err = ntfs_clear_bitrange(vol->bitmap, rl[i].lcn, rl[i].len);
 1410         unlock_kernel();
 1411         return err;
 1412 }
 1413 

Cache object: e08a09397848054bcb431e461d57f48b


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.