fs/ntfs/super.c

   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, "%s(): Entering with *location = 0x%x, "
 643                         "*count = 0x%x, zone = %s_ZONE.\n", __FUNCTION__,
 644                         *location, *count, zone == DATA_ZONE ? "DATA" : "MFT");
 645         buf = (char*)__get_free_page(GFP_NOFS);
 646         if (!buf) {
 647                 ntfs_debug(DEBUG_OTHER, "%s(): Returning -ENOMEM.\n",
 648                                 __FUNCTION__);
 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, "%s(): *count <= 0, "
 725                                 "returning -EINVAL.\n", __FUNCTION__);
 726                 err = -EINVAL;
 727                 goto err_ret;
 728         }
 729         while (1) {
 730                 ntfs_debug(DEBUG_OTHER, "%s(): 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                                 __FUNCTION__, done_zones, search_zone, pass,
 736                                 zone_start, zone_end, initial_location, buf_pos,
 737                                 rlpos, 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, "%s(): last_read_pos = 0x%x.\n",
 744                                 __FUNCTION__, last_read_pos);
 745                 err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
 746                                 &io);
 747                 if (err) {
 748                         ntfs_debug(DEBUG_OTHER, "%s(): ntfs_read_attr failed "
 749                                         "with error code %i, going to "
 750                                         "err_ret.\n", __FUNCTION__, -err);
 751                         goto err_ret;
 752                 }
 753                 if (!io.size) {
 754                         ntfs_debug(DEBUG_OTHER, "%s(): !io.size, going to "
 755                                         "zone_pass_done.\n", __FUNCTION__);
 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, "%s(): Before inner while "
 763                                 "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
 764                                 "0x%x, need_writeback = %i.\n", __FUNCTION__,
 765                                 buf_size, lcn, buf_pos, need_writeback);
 766                 while (lcn < buf_size && lcn + buf_pos < zone_end) {
 767                         byte = buf + (lcn >> 3);
 768                         ntfs_debug(DEBUG_OTHER, "%s(): In inner while loop: "
 769                                         "buf_size = 0x%x, lcn = 0x%x, buf_pos "
 770                                         "= 0x%x, need_writeback = %i, byte ofs "
 771                                         "= 0x%x, *byte = 0x%x.\n", __FUNCTION__,
 772                                         buf_size, lcn, buf_pos, need_writeback,
 773                                         lcn >> 3, *byte);
 774                         /* Skip full bytes. */
 775                         if (*byte == 0xff) {
 776                                 lcn += 8;
 777                                 ntfs_debug(DEBUG_OTHER, "%s(): continuing while"
 778                                             " loop 1.\n", __FUNCTION__);
 779                                 continue;
 780                         }
 781                         bit = 1 << (lcn & 7);
 782                         ntfs_debug(DEBUG_OTHER, "%s(): bit = %i.\n",
 783                                         __FUNCTION__, bit);
 784                         /* If the bit is already set, go onto the next one. */
 785                         if (*byte & bit) {
 786                                 lcn++;
 787                                 ntfs_debug(DEBUG_OTHER, "%s(): continuing while"
 788                                             " loop 2.\n", __FUNCTION__);
 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, "%s(): *byte = 0x%x, "
 796                                         "need_writeback = %i.\n", __FUNCTION__,
 797                                         *byte, need_writeback);
 798                         /* Reallocate memory if necessary. */
 799                         if ((rlpos + 2) * sizeof(ntfs_runlist) >= rlsize) {
 800                                 ntfs_debug(DEBUG_OTHER, "%s(): Reallocating "
 801                                                 "space.\n", __FUNCTION__);
 802                                 /* Setup first free bit return value. */
 803                                 if (!rl2) {
 804                                         *location = lcn + buf_pos;
 805                                         ntfs_debug(DEBUG_OTHER, "%s(): "
 806                                                         "*location = 0x%x.\n",
 807                                                         __FUNCTION__,
 808                                                         *location);
 809                                 }
 810                                 rlsize += PAGE_SIZE;
 811                                 rlt = ntfs_vmalloc(rlsize);
 812                                 if (!rlt) {
 813                                         err = -ENOMEM;
 814                                         ntfs_debug(DEBUG_OTHER, "%s(): Failed "
 815                                                         "to allocate memory, "
 816                                                         "returning -ENOMEM, "
 817                                                         "going to wb_err_ret.\n",
 818                                                         __FUNCTION__);
 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, "%s(): Reallocated "
 828                                                 "memory, rlsize = 0x%x.\n",
 829                                                 __FUNCTION__, rlsize);
 830                         }
 831                         /*
 832                          * Coalesce with previous run if adjacent LCNs.
 833                          * Otherwise, append a new run.
 834                          */
 835                         ntfs_debug(DEBUG_OTHER, "%s(): Adding run (lcn 0x%x, "
 836                                         "len 0x%x), prev_lcn = 0x%x, lcn = "
 837                                         "0x%x, buf_pos = 0x%x, prev_run_len = "
 838                                         "0x%x, rlpos = %i.\n", __FUNCTION__,
 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, "%s(): Coalescing to "
 843                                                 "run (lcn 0x%x, len 0x%x).\n",
 844                                                 __FUNCTION__,
 845                                                 rl2[rlpos - 1].lcn,
 846                                                 rl2[rlpos - 1].len);
 847                                 rl2[rlpos - 1].len = ++prev_run_len;
 848                                 ntfs_debug(DEBUG_OTHER, "%s(): Run now (lcn "
 849                                                 "0x%x, len 0x%x), prev_run_len "
 850                                                 "= 0x%x.\n", __FUNCTION__,
 851                                                 rl2[rlpos - 1].lcn,
 852                                                 rl2[rlpos - 1].len,
 853                                                 prev_run_len);
 854                         } else {
 855                                 if (rlpos)
 856                                         ntfs_debug(DEBUG_OTHER, "%s(): Adding "
 857                                                         "new run, (previous "
 858                                                         "run lcn 0x%x, "
 859                                                         "len 0x%x).\n",
 860                                                         __FUNCTION__,
 861                                                         rl2[rlpos - 1].lcn,
 862                                                         rl2[rlpos - 1].len);
 863                                 else
 864                                         ntfs_debug(DEBUG_OTHER, "%s(): Adding "
 865                                                         "new run, is first "
 866                                                         "run.\n", __FUNCTION__);
 867                                 rl2[rlpos].lcn = prev_lcn = lcn + buf_pos;
 868                                 rl2[rlpos].len = prev_run_len =
 869                                                 (ntfs_cluster_t)1;
 870
 871                                 rlpos++;
 872                         }
 873                         /* Done? */
 874                         if (!--clusters) {
 875                                 ntfs_cluster_t tc;
 876                                 /*
 877                                  * Update the current zone position. Positions
 878                                  * of already scanned zones have been updated
 879                                  * during the respective zone switches.
 880                                  */
 881                                 tc = lcn + buf_pos + 1;
 882                                 ntfs_debug(DEBUG_OTHER, "%s(): Done. Updating "
 883                                                 "current zone position, tc = "
 884                                                 "0x%x, search_zone = %i.\n",
 885                                                 __FUNCTION__, tc, search_zone);
 886                                 switch (search_zone) {
 887                                 case 1:
 888                                         ntfs_debug(DEBUG_OTHER,
 889                                                         "%s(): Before checks, "
 890                                                         "vol->mft_zone_pos = "
 891                                                         "0x%x.\n", __FUNCTION__,
 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,
 905                                                         "%s(): After checks, "
 906                                                         "vol->mft_zone_pos = "
 907                                                         "0x%x.\n", __FUNCTION__,
 908                                                         vol->mft_zone_pos);
 909                                         break;
 910                                 case 2:
 911                                         ntfs_debug(DEBUG_OTHER,
 912                                                         "%s(): Before checks, "
 913                                                         "vol->data1_zone_pos = "
 914                                                         "0x%x.\n", __FUNCTION__,
 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,
 925                                                         "%s(): After checks, "
 926                                                         "vol->data1_zone_pos = "
 927                                                         "0x%x.\n", __FUNCTION__,
 928                                                         vol->data1_zone_pos);
 929                                         break;
 930                                 case 4:
 931                                         ntfs_debug(DEBUG_OTHER,
 932                                                         "%s(): Before checks, "
 933                                                         "vol->data2_zone_pos = "
 934                                                         "0x%x.\n", __FUNCTION__,
 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,
 944                                                         "%s(): After checks, "
 945                                                         "vol->data2_zone_pos = "
 946                                                         "0x%x.\n", __FUNCTION__,
 947                                                         vol->data2_zone_pos);
 948                                         break;
 949                                 default:
 950                                         BUG();
 951                                 }
 952                                 ntfs_debug(DEBUG_OTHER, "%s(): Going to "
 953                                                 "done_ret.\n", __FUNCTION__);
 954                                 goto done_ret;
 955                         }
 956                         lcn++;
 957                 }
 958                 buf_pos += buf_size;
 959                 ntfs_debug(DEBUG_OTHER, "%s(): After inner while "
 960                                 "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
 961                                 "0x%x, need_writeback = %i.\n", __FUNCTION__,
 962                                 buf_size, lcn, buf_pos, need_writeback);
 963                 if (need_writeback) {
 964                         ntfs_debug(DEBUG_OTHER, "%s(): Writing back.\n",
 965                                         __FUNCTION__);
 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("%s(): Bitmap writeback failed "
 973                                                 "in read next buffer code "
 974                                                 "path with error code %i.\n",
 975                                                 __FUNCTION__, -err);
 976                                 goto err_ret;
 977                         }
 978                 }
 979                 if (buf_pos < zone_end) {
 980                         ntfs_debug(DEBUG_OTHER, "%s(): Continuing "
 981                                         "outer while loop, buf_pos = 0x%x, "
 982                                         "zone_end = 0x%x.\n", __FUNCTION__,
 983                                         buf_pos, zone_end);
 984                         continue;
 985                 }
 986 zone_pass_done: /* Finished with the current zone pass. */
 987                 ntfs_debug(DEBUG_OTHER, "%s(): At zone_pass_done, pass = %i.\n",
 988                                 __FUNCTION__, 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, "%s(): Continuing "
1014                                         "outer while loop, pass = 2, "
1015                                         "zone_start = 0x%x, zone_end = 0x%x, "
1016                                         "buf_pos = 0x%x.\n", __FUNCTION__,
1017                                         zone_start, zone_end, buf_pos);
1018                         continue;
1019                 } /* pass == 2 */
1020 done_zones_check:
1021                 ntfs_debug(DEBUG_OTHER, "%s(): At done_zones_check, "
1022                                 "search_zone = %i, done_zones before = 0x%x, "
1023                                 "done_zones after = 0x%x.\n", __FUNCTION__,
1024                                 search_zone, done_zones, done_zones |
1025                                 search_zone);
1026                 done_zones |= search_zone;
1027                 if (done_zones < 7) {
1028                         ntfs_debug(DEBUG_OTHER, "%s(): Switching zone.\n",
1029                                         __FUNCTION__);
1030                         /* Now switch to the next zone we haven't done yet. */
1031                         pass = 1;
1032                         switch (search_zone) {
1033                         case 1:
1034                                 ntfs_debug(DEBUG_OTHER, "%s(): Switching from "
1035                                                 "mft zone to data1 zone.\n",
1036                                                 __FUNCTION__);
1037                                 /* Update mft zone position. */
1038                                 if (rlpos) {
1039                                         ntfs_cluster_t tc;
1040                                         ntfs_debug(DEBUG_OTHER,
1041                                                         "%s(): Before checks, "
1042                                                         "vol->mft_zone_pos = "
1043                                                         "0x%x.\n", __FUNCTION__,
1044                                                         vol->mft_zone_pos);
1045                                         tc = rl2[rlpos - 1].lcn +
1046                                                         rl2[rlpos - 1].len;
1047                                         if (tc >= vol->mft_zone_end) {
1048                                                 vol->mft_zone_pos =
1049                                                                 vol->mft_lcn;
1050                                                 if (!vol->mft_zone_end)
1051                                                         vol->mft_zone_pos =
1052                                                              (ntfs_cluster_t)0;
1053                                         } else if ((initial_location >=
1054                                                         vol->mft_zone_pos ||
1055                                                         tc > vol->mft_zone_pos)
1056                                                         && tc >= vol->mft_lcn)
1057                                                 vol->mft_zone_pos = tc;
1058                                         ntfs_debug(DEBUG_OTHER,
1059                                                         "%s(): After checks, "
1060                                                         "vol->mft_zone_pos = "
1061                                                         "0x%x.\n", __FUNCTION__,
1062                                                         vol->mft_zone_pos);
1063                                 }
1064                                 /* Switch from mft zone to data1 zone. */
1065 switch_to_data1_zone:           search_zone = 2;
1066                                 zone_start = initial_location =
1067                                                 vol->data1_zone_pos;
1068                                 zone_end = vol->nr_clusters;
1069                                 if (zone_start == vol->mft_zone_end)
1070                                         pass = 2;
1071                                 if (zone_start >= zone_end) {
1072                                         vol->data1_zone_pos = zone_start =
1073                                                         vol->mft_zone_end;
1074                                         pass = 2;
1075                                 }
1076                                 break;
1077                         case 2:
1078                                 ntfs_debug(DEBUG_OTHER, "%s(): Switching from "
1079                                                 "data1 zone to data2 zone.\n",
1080                                                 __FUNCTION__);
1081                                 /* Update data1 zone position. */
1082                                 if (rlpos) {
1083                                         ntfs_cluster_t tc;
1084                                         ntfs_debug(DEBUG_OTHER,
1085                                                         "%s(): Before checks, "
1086                                                         "vol->data1_zone_pos = "
1087                                                         "0x%x.\n", __FUNCTION__,
1088                                                         vol->data1_zone_pos);
1089                                         tc = rl2[rlpos - 1].lcn +
1090                                                         rl2[rlpos - 1].len;
1091                                         if (tc >= vol->nr_clusters)
1092                                                 vol->data1_zone_pos =
1093                                                              vol->mft_zone_end;
1094                                         else if ((initial_location >=
1095                                                     vol->data1_zone_pos ||
1096                                                     tc > vol->data1_zone_pos)
1097                                                     && tc >= vol->mft_zone_end)
1098                                                 vol->data1_zone_pos = tc;
1099                                         ntfs_debug(DEBUG_OTHER,
1100                                                         "%s(): After checks, "
1101                                                         "vol->data1_zone_pos = "
1102                                                         "0x%x.\n", __FUNCTION__,
1103                                                         vol->data1_zone_pos);
1104                                 }
1105                                 /* Switch from data1 zone to data2 zone. */
1106                                 search_zone = 4;
1107                                 zone_start = initial_location =
1108                                                 vol->data2_zone_pos;
1109                                 zone_end = vol->mft_zone_start;
1110                                 if (!zone_start)
1111                                         pass = 2;
1112                                 if (zone_start >= zone_end) {
1113                                         vol->data2_zone_pos = zone_start =
1114                                                         initial_location =
1115                                                         (ntfs_cluster_t)0;
1116                                         pass = 2;
1117                                 }
1118                                 break;
1119                         case 4:
1120                                 ntfs_debug(DEBUG_OTHER, "%s(): Switching from "
1121                                                 "data2 zone to data1 zone.\n",
1122                                                 __FUNCTION__);
1123                                 /* Update data2 zone position. */
1124                                 if (rlpos) {
1125                                         ntfs_cluster_t tc;
1126                                         ntfs_debug(DEBUG_OTHER,
1127                                                         "%s(): Before checks, "
1128                                                         "vol->data2_zone_pos = "
1129                                                         "0x%x.\n", __FUNCTION__,
1130                                                         vol->data2_zone_pos);
1131                                         tc = rl2[rlpos - 1].lcn +
1132                                                         rl2[rlpos - 1].len;
1133                                         if (tc >= vol->mft_zone_start)
1134                                                 vol->data2_zone_pos =
1135                                                              (ntfs_cluster_t)0;
1136                                         else if (initial_location >=
1137                                                       vol->data2_zone_pos ||
1138                                                       tc > vol->data2_zone_pos)
1139                                                 vol->data2_zone_pos = tc;
1140                                         ntfs_debug(DEBUG_OTHER,
1141                                                         "%s(): After checks, "
1142                                                         "vol->data2_zone_pos = "
1143                                                         "0x%x.\n", __FUNCTION__,
1144                                                         vol->data2_zone_pos);
1145                                 }
1146                                 /* Switch from data2 zone to data1 zone. */
1147                                 goto switch_to_data1_zone; /* See above. */
1148                         default:
1149                                 BUG();
1150                         }
1151                         ntfs_debug(DEBUG_OTHER, "%s(): After zone switch, "
1152                                         "search_zone = %i, pass = %i, "
1153                                         "initial_location = 0x%x, zone_start "
1154                                         "= 0x%x, zone_end = 0x%x.\n",
1155                                         __FUNCTION__, search_zone, pass,
1156                                         initial_location, zone_start, zone_end);
1157                         buf_pos = zone_start;
1158                         if (zone_start == zone_end) {
1159                                 ntfs_debug(DEBUG_OTHER, "%s(): Empty zone, "
1160                                                 "going to done_zones_check.\n",
1161                                                 __FUNCTION__);
1162                                 /* Empty zone. Don't bother searching it. */
1163                                 goto done_zones_check;
1164                         }
1165                         ntfs_debug(DEBUG_OTHER, "%s(): Continuing outer while "
1166                                         "loop.\n", __FUNCTION__);
1167                         continue;
1168                 } /* done_zones == 7 */
1169                 ntfs_debug(DEBUG_OTHER, "%s(): All zones are finished.\n",
1170                                 __FUNCTION__);
1171                 /*
1172                  * All zones are finished! If DATA_ZONE, shrink mft zone. If
1173                  * MFT_ZONE, we have really run out of space.
1174                  */
1175                 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start;
1176                 ntfs_debug(DEBUG_OTHER, "%s(): vol->mft_zone_start = 0x%x, "
1177                                 "vol->mft_zone_end = 0x%x, mft_zone_size = "
1178                                 "0x%x.\n", __FUNCTION__, vol->mft_zone_start,
1179                                 vol->mft_zone_end, mft_zone_size);
1180                 if (zone == MFT_ZONE || mft_zone_size <= (ntfs_cluster_t)0) {
1181                         ntfs_debug(DEBUG_OTHER, "%s(): No free clusters left, "
1182                                         "returning -ENOSPC, going to "
1183                                         "fail_ret.\n", __FUNCTION__);
1184                         /* Really no more space left on device. */
1185                         err = -ENOSPC;
1186                         goto fail_ret;
1187                 } /* zone == DATA_ZONE && mft_zone_size > 0 */
1188                 ntfs_debug(DEBUG_OTHER, "%s(): Shrinking mft zone.\n",
1189                                 __FUNCTION__);
1190                 zone_end = vol->mft_zone_end;
1191                 mft_zone_size >>= 1;
1192                 if (mft_zone_size > (ntfs_cluster_t)0)
1193                         vol->mft_zone_end = vol->mft_zone_start + mft_zone_size;
1194                 else /* mft zone and data2 zone no longer exist. */
1195                         vol->data2_zone_pos = vol->mft_zone_start =
1196                                         vol->mft_zone_end = (ntfs_cluster_t)0;
1197                 if (vol->mft_zone_pos >= vol->mft_zone_end) {
1198                         vol->mft_zone_pos = vol->mft_lcn;
1199                         if (!vol->mft_zone_end)
1200                                 vol->mft_zone_pos = (ntfs_cluster_t)0;
1201                 }
1202                 buf_pos = zone_start = initial_location =
1203                                 vol->data1_zone_pos = vol->mft_zone_end;
1204                 search_zone = 2;
1205                 pass = 2;
1206                 done_zones &= ~2;
1207                 ntfs_debug(DEBUG_OTHER, "%s(): After shrinking mft "
1208                                 "zone, mft_zone_size = 0x%x, "
1209                                 "vol->mft_zone_start = 0x%x, vol->mft_zone_end "
1210                                 "= 0x%x, vol->mft_zone_pos = 0x%x, search_zone "
1211                                 "= 2, pass = 2, dones_zones = 0x%x, zone_start "
1212                                 "= 0x%x, zone_end = 0x%x, vol->data1_zone_pos "
1213                                 "= 0x%x, continuing outer while loop.\n",
1214                                 __FUNCTION__, mft_zone_size,
1215                                 vol->mft_zone_start, vol->mft_zone_end,
1216                                 vol->mft_zone_pos, done_zones, zone_start,
1217                                 zone_end, vol->data1_zone_pos);
1218         }
1219         ntfs_debug(DEBUG_OTHER, "%s(): After outer while loop.\n",
1220                         __FUNCTION__);
1221 done_ret:
1222         ntfs_debug(DEBUG_OTHER, "%s(): At done_ret.\n", __FUNCTION__);
1223         rl2[rlpos].lcn = (ntfs_cluster_t)-1;
1224         rl2[rlpos].len = (ntfs_cluster_t)0;
1225         *rl = rl2;
1226         *rl_len = rlpos;
1227         if (need_writeback) {
1228                 ntfs_debug(DEBUG_OTHER, "%s(): Writing back.\n", __FUNCTION__);
1229                 need_writeback = 0;
1230                 io.param = buf;
1231                 io.do_read = 0;
1232                 err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
1233                                 &io);
1234                 if (err) {
1235                         ntfs_error("%s(): Bitmap writeback failed in done "
1236                                         "code path with error code %i.\n",
1237                                         __FUNCTION__, -err);
1238                         goto err_ret;
1239                 }
1240                 ntfs_debug(DEBUG_OTHER, "%s(): Wrote 0x%Lx bytes.\n",
1241                                 __FUNCTION__, io.size);
1242         }
1243 done_fail_ret:
1244         ntfs_debug(DEBUG_OTHER, "%s(): At done_fail_ret (follows done_ret).\n",
1245                          __FUNCTION__);
1246         unlock_kernel();
1247         free_page((unsigned long)buf);
1248         if (err)
1249                 ntfs_debug(DEBUG_FILE3, "%s(): Failed to allocate "
1250                                 "clusters. Returning with error code %i.\n",
1251                                 __FUNCTION__, -err);
1252         ntfs_debug(DEBUG_OTHER, "%s(): Syncing $Bitmap inode.\n", __FUNCTION__);
1253         if (ntfs_update_inode(vol->bitmap))
1254                 ntfs_error("%s(): Failed to sync inode $Bitmap. "
1255                                 "Continuing anyway.\n", __FUNCTION__);
1256         ntfs_debug(DEBUG_OTHER, "%s(): Returning with code %i.\n", __FUNCTION__,
1257                         err);
1258         return err;
1259 fail_ret:
1260         ntfs_debug(DEBUG_OTHER, "%s(): At fail_ret.\n", __FUNCTION__);
1261         if (rl2) {
1262                 if (err == -ENOSPC) {
1263                         /* Return first free lcn and count of free clusters. */
1264                         *location = rl2[0].lcn;
1265                         *count -= clusters;
1266                         ntfs_debug(DEBUG_OTHER, "%s(): err = -ENOSPC, "
1267                                         "*location = 0x%x, *count = 0x%x.\n",
1268                                         __FUNCTION__, *location, *count);
1269                 }
1270                 /* Deallocate all allocated clusters. */
1271                 ntfs_debug(DEBUG_OTHER, "%s(): Deallocating allocated "
1272                                 "clusters.\n", __FUNCTION__);
1273                 ntfs_deallocate_clusters(vol, rl2, rlpos);
1274                 /* Free the runlist. */
1275                 ntfs_vfree(rl2);
1276         } else {
1277                 if (err == -ENOSPC) {
1278                         /* Nothing free at all. */
1279                         *location = vol->data1_zone_pos; /* Irrelevant... */
1280                         *count = 0;
1281                         ntfs_debug(DEBUG_OTHER, "%s(): No space left at all, "
1282                                         "err = -ENOSPC, *location = 0x%x, "
1283                                         "*count = 0.\n",
1284                                         __FUNCTION__, *location);
1285                 }
1286         }
1287         *rl = NULL;
1288         *rl_len = 0;
1289         ntfs_debug(DEBUG_OTHER, "%s(): *rl = NULL, *rl_len = 0, "
1290                         "going to done_fail_ret.\n", __FUNCTION__);
1291         goto done_fail_ret;
1292 wb_err_ret:
1293         ntfs_debug(DEBUG_OTHER, "%s(): At wb_err_ret.\n", __FUNCTION__);
1294         if (need_writeback) {
1295                 int __err;
1296                 ntfs_debug(DEBUG_OTHER, "%s(): Writing back.\n", __FUNCTION__);
1297                 io.param = buf;
1298                 io.do_read = 0;
1299                 __err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
1300                                 &io);
1301                 if (__err)
1302                         ntfs_error("%s(): Bitmap writeback failed in error "
1303                                         "code path with error code %i.\n",
1304                                         __FUNCTION__, -__err);
1305                 need_writeback = 0;
1306         }
1307 err_ret:
1308         ntfs_debug(DEBUG_OTHER, "%s(): At err_ret, *location = -1, "
1309                         "*count = 0, going to fail_ret.\n", __FUNCTION__);
1310         *location = -1;
1311         *count = 0;
1312         goto fail_ret;
1313 }
1314
1315 /*
1316  * IMPORTANT: Caller has to hold big kernel lock or the race monster will come
1317  * to get you! (-;
1318  * TODO: Need our own lock for bitmap accesses but BKL is more secure for now,
1319  * considering we might not have covered all places with a lock yet. In that
1320  * case the BKL offers a one way exclusion which is better than no exclusion
1321  * at all... (AIA)
1322  */
1323 static int ntfs_clear_bitrange(ntfs_inode *bitmap,
1324                 const ntfs_cluster_t start_bit, const ntfs_cluster_t count)
1325 {
1326         ntfs_cluster_t buf_size, bit, nr_bits = count;
1327         unsigned char *buf, *byte;
1328         int err;
1329         ntfs_io io;
1330
1331         io.fn_put = ntfs_put;
1332         io.fn_get = ntfs_get;
1333         /* Calculate the required buffer size in bytes. */
1334         buf_size = (ntfs_cluster_t)((start_bit & 7) + nr_bits + 7) >> 3;
1335         if (buf_size <= (ntfs_cluster_t)(64 * 1024))
1336                 buf = ntfs_malloc(buf_size);
1337         else
1338                 buf = ntfs_vmalloc(buf_size);
1339         if (!buf)
1340                 return -ENOMEM;
1341         /* Read the bitmap from the data attribute. */
1342         io.param = byte = buf;
1343         io.size = buf_size;
1344         err = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
1345                         &io);
1346         if (err || io.size != buf_size)
1347                 goto err_out;
1348         /* Now clear the bits in the read bitmap. */
1349         bit = start_bit & 7;
1350         while (bit && nr_bits) { /* Process first partial byte, if present. */
1351                 *byte &= ~(1 << bit++);
1352                 nr_bits--;
1353                 bit &= 7;
1354                 if (!bit)
1355                         byte++;
1356         }
1357         while (nr_bits >= 8) { /* Process full bytes. */
1358                 *byte = 0;
1359                 nr_bits -= 8;
1360                 byte++;
1361         }
1362         bit = 0;
1363         while (nr_bits) { /* Process last partial byte, if present. */
1364                 *byte &= ~(1 << bit);
1365                 nr_bits--;
1366                 bit++;
1367         }
1368         /* Write the modified bitmap back to disk. */
1369         io.param = buf;
1370         io.size = buf_size;
1371         err = ntfs_write_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
1372                         &io);
1373 err_out:
1374         if (buf_size <= (ntfs_cluster_t)(64 * 1024))
1375                 ntfs_free(buf);
1376         else
1377                 ntfs_vfree(buf);
1378         if (!err && io.size != buf_size)
1379                 err = -EIO;
1380         return err;
1381 }
1382
1383 /*
1384  * See comments for lack of zone adjustments below in the description of the
1385  * function ntfs_deallocate_clusters().
1386  */
1387 int ntfs_deallocate_cluster_run(const ntfs_volume *vol,
1388                 const ntfs_cluster_t lcn, const ntfs_cluster_t len)
1389 {
1390         int err;
1391
1392         lock_kernel();
1393         err = ntfs_clear_bitrange(vol->bitmap, lcn, len);
1394         unlock_kernel();
1395         return err;
1396 }
1397
1398 /*
1399  * This is inefficient, but logically trivial, so will do for now. Note, we
1400  * do not touch the mft nor the data zones here because we want to minimize
1401  * recycling of clusters to enhance the chances of data being undeleteable.
1402  * Also we don't want the overhead. Instead we do one additional sweep of the
1403  * current data zone during cluster allocation to check for freed clusters.
1404  */
1405 int ntfs_deallocate_clusters(const ntfs_volume *vol, const ntfs_runlist *rl,
1406                 const int rl_len)
1407 {
1408         int i, err;
1409
1410         lock_kernel();
1411         for (i = err = 0; i < rl_len && !err; i++)
1412                 err = ntfs_clear_bitrange(vol->bitmap, rl[i].lcn, rl[i].len);
1413         unlock_kernel();
1414         return err;
1415 }
1416