libntfs/lcnalloc.c

   1 /*
   2  * lcnalloc.c - Cluster (de)allocation code. Part of the Linux-NTFS project.
   3  *
   4  * Copyright (c) 2002-2003 Anton Altaparmakov
   5  *
   6  * This program/include file is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as published
   8  * by the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program/include file is distributed in the hope that it will be
  12  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program (in the main directory of the Linux-NTFS
  18  * distribution in the file COPYING); if not, write to the Free Software
  19  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  */
  21
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <errno.h>
  25
  26 #include "types.h"
  27 #include "attrib.h"
  28 #include "bitmap.h"
  29 #include "debug.h"
  30 #include "runlist.h"
  31 #include "volume.h"
  32 #include "lcnalloc.h"
  33
  34
  35 /**
  36  * ntfs_cluster_alloc - allocate clusters on an ntfs volume
  37  * @vol:        mounted ntfs volume on which to allocate the clusters
  38  * @count:      number of clusters to allocate
  39  * @start_lcn:  starting lcn at which to allocate the clusters (or -1 if none)
  40  * @zone:       zone from which to allocate the clusters
  41  *
  42  * Allocate @count clusters preferably starting at cluster @start_lcn or at the
  43  * current allocator position if @start_lcn is -1, on the mounted ntfs volume
  44  * @vol. @zone is either DATA_ZONE for allocation of normal clusters and
  45  * MFT_ZONE for allocation of clusters for the master file table, i.e. the
  46  * $MFT/$DATA attribute.
  47  *
  48  * On success return a runlist describing the allocated cluster(s).
  49  *
  50  * On error return NULL with errno set to the error code.
  51  *
  52  * Notes on the allocation algorithm
  53  * =================================
  54  *
  55  * There are two data zones. First is the area between the end of the mft zone
  56  * and the end of the volume, and second is the area between the start of the
  57  * volume and the start of the mft zone. On unmodified/standard NTFS 1.x
  58  * volumes, the second data zone doesn't exist due to the mft zone being
  59  * expanded to cover the start of the volume in order to reserve space for the
  60  * mft bitmap attribute.
  61  *
  62  * This is not the prettiest function but the complexity stems from the need of
  63  * implementing the mft vs data zoned approach and from the fact that we have
  64  * access to the lcn bitmap in portions of up to 8192 bytes at a time, so we
  65  * need to cope with crossing over boundaries of two buffers. Further, the fact
  66  * that the allocator allows for caller supplied hints as to the location of
  67  * where allocation should begin and the fact that the allocator keeps track of
  68  * where in the data zones the next natural allocation should occur, contribute
  69  * to the complexity of the function. But it should all be worthwhile, because
  70  * this allocator should: 1) be a full implementation of the MFT zone approach
  71  * used by Windows, 2) cause reduction in fragmentation as much as possible,
  72  * and 3) be speedy in allocations (the code is not optimized for speed, but
  73  * the algorithm is, so further speed improvements are probably possible).
  74  *
  75  * FIXME: We should be monitoring cluster allocation and increment the MFT zone
  76  * size dynamically but this is something for the future. We will just cause
  77  * heavier fragmentation by not doing it and I am not even sure Windows would
  78  * grow the MFT zone dynamically, so it might even be correct not to do this.
  79  * The overhead in doing dynamic MFT zone expansion would be very large and
  80  * unlikely worth the effort. (AIA)
  81  *
  82  * TODO: I have added in double the required zone position pointer wrap around
  83  * logic which can be optimized to having only one of the two logic sets.
  84  * However, having the double logic will work fine, but if we have only one of
  85  * the sets and we get it wrong somewhere, then we get into trouble, so
  86  * removing the duplicate logic requires _very_ careful consideration of _all_
  87  * possible code paths. So at least for now, I am leaving the double logic -
  88  * better safe than sorry... (AIA)
  89  */
  90 // FIXME: Add a start_vcn parameter if we need it and then instead of setting
  91 // rl[rlpos].vcn = 0; for the first run, add a sparse start element (LCN_HOLE),
  92 // and make rl[rlpos].vcn = start_vcn; for the first non-sparse run. (AIA)
  93 runlist *ntfs_cluster_alloc(ntfs_volume *vol, s64 count, LCN start_lcn,
  94                 const NTFS_CLUSTER_ALLOCATION_ZONES zone)
  95 {
  96         LCN zone_start, zone_end, bmp_pos, bmp_initial_pos, last_read_pos, lcn;
  97         LCN prev_lcn = 0, prev_run_len = 0, mft_zone_size;
  98         s64 clusters, br;
  99         runlist *rl = NULL, *trl;
 100         u8 *buf, *byte;
 101         int err = 0, rlpos, rlsize, buf_size;
 102         u8 pass, done_zones, search_zone, need_writeback, bit;
 103
 104         Dprintf("%s(): Entering with count = 0x%Lx, start_lcn = 0x%Lx, "
 105                         "zone = %s_ZONE.\n", __FUNCTION__, (long long)count,
 106                         (long long)start_lcn,
 107                         zone == MFT_ZONE ? "MFT" : "DATA");
 108         if (!vol || count < 0 || start_lcn < -1 || !vol->lcnbmp_na ||
 109                         zone < FIRST_ZONE || zone > LAST_ZONE) {
 110                 fprintf(stderr, "%s(): Invalid arguments!\n", __FUNCTION__);
 111                 errno = EINVAL;
 112                 return NULL;
 113         }
 114
 115         /* Allocate memory. */
 116         buf = (u8*)malloc(8192);
 117         if (!buf)
 118                 return NULL;
 119         /*
 120          * If no specific @start_lcn was requested, use the current data zone
 121          * position, otherwise use the requested @start_lcn but make sure it
 122          * lies outside the mft zone. Also set done_zones to 0 (no zones done)
 123          * and pass depending on whether we are starting inside a zone (1) or
 124          * at the beginning of a zone (2). If requesting from the MFT_ZONE,
 125          * we either start at the current position within the mft zone or at
 126          * the specified position. If the latter is out of bounds then we start
 127          * at the beginning of the MFT_ZONE.
 128          */
 129         done_zones = 0;
 130         pass = 1;
 131         /*
 132          * zone_start and zone_end are the current search range. search_zone
 133          * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of
 134          * volume) and 4 for data zone 2 (start of volume till start of mft
 135          * zone).
 136          */
 137         zone_start = start_lcn;
 138         if (zone_start < 0) {
 139                 if (zone == DATA_ZONE)
 140                         zone_start = vol->data1_zone_pos;
 141                 else
 142                         zone_start = vol->mft_zone_pos;
 143                 if (!zone_start) {
 144                         /*
 145                          * Zone starts at beginning of volume which means a
 146                          * single pass is sufficient.
 147                          */
 148                         pass = 2;
 149                 }
 150         } else if (zone == DATA_ZONE && zone_start >= vol->mft_zone_start &&
 151                         zone_start < vol->mft_zone_end) {
 152                 zone_start = vol->mft_zone_end;
 153                 /*
 154                  * Starting at beginning of data1_zone which means a single
 155                  * pass in this zone is sufficient.
 156                  */
 157                 pass = 2;
 158         } else if (zone == MFT_ZONE && (zone_start < vol->mft_zone_start ||
 159                         zone_start >= vol->mft_zone_end)) {
 160                 zone_start = vol->mft_lcn;
 161                 if (!vol->mft_zone_end)
 162                         zone_start = 0;
 163                 /*
 164                  * Starting at beginning of volume which means a single pass
 165                  * is sufficient.
 166                  */
 167                 pass = 2;
 168         }
 169         if (zone == MFT_ZONE) {
 170                 zone_end = vol->mft_zone_end;
 171                 search_zone = 1;
 172         } else /* if (zone == DATA_ZONE) */ {
 173                 /* Skip searching the mft zone. */
 174                 done_zones |= 1;
 175                 if (zone_start >= vol->mft_zone_end) {
 176                         zone_end = vol->nr_clusters;
 177                         search_zone = 2;
 178                 } else {
 179                         zone_end = vol->mft_zone_start;
 180                         search_zone = 4;
 181                 }
 182         }
 183         /*
 184          * bmp_pos is the current bit position inside the bitmap. We use
 185          * bmp_initial_pos to determine whether or not to do a zone switch.
 186          */
 187         bmp_pos = bmp_initial_pos = zone_start;
 188
 189         /* Loop until all clusters are allocated, i.e. clusters == 0. */
 190         clusters = count;
 191         rlpos = rlsize = 0;
 192         while (1) {
 193                 Dprintf("%s(): Start of outer while loop: done_zones = 0x%x, "
 194                                 "search_zone = %i, pass = %i, zone_start = "
 195                                 "0x%Lx, zone_end = 0x%Lx, bmp_initial_pos = "
 196                                 "0x%Lx, bmp_pos = 0x%Lx, rlpos = %i, rlsize = "
 197                                 "%i.\n", __FUNCTION__, done_zones, search_zone,
 198                                 pass, (long long)zone_start,
 199                                 (long long)zone_end, (long long)bmp_initial_pos,
 200                                 (long long)bmp_pos, rlpos, rlsize);
 201                 /* Loop until we run out of free clusters. */
 202                 last_read_pos = bmp_pos >> 3;
 203                 Dprintf("%s(): last_read_pos = 0x%Lx.\n", __FUNCTION__,
 204                                 (long long)last_read_pos);
 205                 br = ntfs_attr_pread(vol->lcnbmp_na, last_read_pos, 8192, buf);
 206                 if (br <= 0) {
 207                         if (!br) {
 208                                 /* Reached end of attribute. */
 209                                 Dprintf("%s(): End of attribute reached. "
 210                                                 "Skipping to zone_pass_done.\n",
 211                                                 __FUNCTION__);
 212                                 goto zone_pass_done;
 213                         }
 214                         err = errno;
 215                         Dprintf("%s(): ntfs_attr_pread() failed. Aborting.\n",
 216                                         __FUNCTION__);
 217                         goto err_ret;
 218                 }
 219                 /*
 220                  * We might have read less than 8192 bytes if we are close to
 221                  * the end of the attribute.
 222                  */
 223                 buf_size = (int)br << 3;
 224                 lcn = bmp_pos & 7;
 225                 bmp_pos &= ~7;
 226                 need_writeback = 0;
 227                 Dprintf("%s(): Before inner while loop: buf_size = %i, "
 228                                 "lcn = 0x%Lx, bmp_pos = 0x%Lx, need_writeback "
 229                                 "= %i.\n", __FUNCTION__, buf_size,
 230                                 (long long)lcn, (long long)bmp_pos,
 231                                 need_writeback);
 232                 while (lcn < buf_size && lcn + bmp_pos < zone_end) {
 233                         byte = buf + (lcn >> 3);
 234                         Dprintf("%s(): In inner while loop: buf_size = %i, "
 235                                         "lcn = 0x%Lx, bmp_pos = 0x%Lx, "
 236                                         "need_writeback = %i, byte ofs = 0x%x, "
 237                                         "*byte = 0x%x.\n", __FUNCTION__,
 238                                         buf_size, (long long)lcn,
 239                                         (long long)bmp_pos, need_writeback,
 240                                         lcn >> 3, *byte);
 241                         /* Skip full bytes. */
 242                         if (*byte == 0xff) {
 243                                 lcn += 8;
 244                                 Dprintf("%s(): continuing while loop 1.\n",
 245                                                 __FUNCTION__);
 246                                 continue;
 247                         }
 248                         bit = 1 << (lcn & 7);
 249                         Dprintf("%s(): bit = %i.\n", __FUNCTION__, bit);
 250                         /* If the bit is already set, go onto the next one. */
 251                         if (*byte & bit) {
 252                                 lcn++;
 253                                 Dprintf("%s(): continuing while loop 2.\n",
 254                                                 __FUNCTION__);
 255                                 continue;
 256                         }
 257                         /* Allocate the bitmap bit. */
 258                         *byte |= bit;
 259                         /* We need to write this bitmap buffer back to disk! */
 260                         need_writeback = 1;
 261                         Dprintf("%s(): *byte = 0x%x, need_writeback is set.\n",
 262                                         __FUNCTION__, *byte);
 263                         /* Reallocate memory if necessary. */
 264                         if ((rlpos + 2) * sizeof(runlist) >= rlsize) {
 265                                 Dprintf("%s(): Reallocating space.\n",
 266                                                 __FUNCTION__);
 267                                 /* Setup first free bit return value. */
 268                                 if (!rl) {
 269                                         start_lcn = lcn + bmp_pos;
 270                                         Dprintf("%s(): start_lcn = 0x%Lx.\n",
 271                                                         __FUNCTION__,
 272                                                         (long long)start_lcn);
 273                                 }
 274                                 rlsize += 4096;
 275                                 trl = (runlist*)realloc(rl, rlsize);
 276                                 if (!trl) {
 277                                         err = ENOMEM;
 278                                         Dprintf("%s(): Failed to allocate "
 279                                                         "memory, going to "
 280                                                         "wb_err_ret.\n",
 281                                                         __FUNCTION__);
 282                                         goto wb_err_ret;
 283                                 }
 284                                 rl = trl;
 285                                 Dprintf("%s(): Reallocated memory, rlsize = "
 286                                                 "0x%x.\n", __FUNCTION__,
 287                                                 rlsize);
 288                         }
 289                         /*
 290                          * Coalesce with previous run if adjacent LCNs.
 291                          * Otherwise, append a new run.
 292                          */
 293                         Dprintf("%s(): Adding run (lcn 0x%Lx, len 0x%Lx), "
 294                                         "prev_lcn = 0x%Lx, lcn = 0x%Lx, "
 295                                         "bmp_pos = 0x%Lx, prev_run_len = 0x%x, "
 296                                         "rlpos = %i.\n", __FUNCTION__,
 297                                         (long long)(lcn + bmp_pos), 1LL,
 298                                         (long long)prev_lcn, (long long)lcn,
 299                                         (long long)bmp_pos,
 300                                         (long long)prev_run_len, rlpos);
 301                         if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) {
 302                                 Dprintf("%s(): Coalescing to run (lcn 0x%Lx, "
 303                                                 "len 0x%Lx).\n", __FUNCTION__,
 304                                                 (long long)rl[rlpos - 1].lcn,
 305                                                 (long long)
 306                                                 rl[rlpos - 1].length);
 307                                 rl[rlpos - 1].length = ++prev_run_len;
 308                                 Dprintf("%s(): Run now (lcn 0x%Lx, len 0x%Lx), "
 309                                                 "prev_run_len = 0x%Lx.\n",
 310                                                 __FUNCTION__,
 311                                                 (long long)rl[rlpos - 1].lcn,
 312                                                 (long long)rl[rlpos - 1].length,
 313                                                 (long long)prev_run_len);
 314                         } else {
 315                                 if (rlpos) {
 316                                         Dprintf("%s(): Adding new run, "
 317                                                         "(previous run lcn "
 318                                                         "0x%Lx, len 0x%Lx).\n",
 319                                                         __FUNCTION__,
 320                                                         (long long)
 321                                                         rl[rlpos - 1].lcn,
 322                                                         (long long)
 323                                                         rl[rlpos - 1].length);
 324                                         rl[rlpos].vcn = rl[rlpos - 1].vcn +
 325                                                         prev_run_len;
 326                                 } else {
 327                                         Dprintf("%s(): Adding new run, is "
 328                                                         "first run.\n",
 329                                                         __FUNCTION__);
 330                                         rl[rlpos].vcn = 0;
 331                                 }
 332                                 rl[rlpos].lcn = prev_lcn = lcn + bmp_pos;
 333                                 rl[rlpos].length = prev_run_len = 1;
 334                                 rlpos++;
 335                         }
 336                         /* Done? */
 337                         if (!--clusters) {
 338                                 LCN tc;
 339                                 /*
 340                                  * Update the current zone position. Positions
 341                                  * of already scanned zones have been updated
 342                                  * during the respective zone switches.
 343                                  */
 344                                 tc = lcn + bmp_pos + 1;
 345                                 Dprintf("%s(): Done. Updating current zone "
 346                                                 "position, tc = 0x%Lx, "
 347                                                 "search_zone = %i.\n",
 348                                                 __FUNCTION__, (long long)tc,
 349                                                 search_zone);
 350                                 switch (search_zone) {
 351                                 case 1:
 352                                         Dprintf("%s(): Before checks, "
 353                                                         "vol->mft_zone_pos = "
 354                                                         "0x%Lx.\n",
 355                                                         __FUNCTION__,
 356                                                         (long long)
 357                                                         vol->mft_zone_pos);
 358                                         if (tc >= vol->mft_zone_end) {
 359                                                 vol->mft_zone_pos =
 360                                                                 vol->mft_lcn;
 361                                                 if (!vol->mft_zone_end)
 362                                                         vol->mft_zone_pos = 0;
 363                                         } else if ((bmp_initial_pos >=
 364                                                         vol->mft_zone_pos ||
 365                                                         tc > vol->mft_zone_pos)
 366                                                         && tc >= vol->mft_lcn)
 367                                                 vol->mft_zone_pos = tc;
 368                                         Dprintf("%s(): After checks, "
 369                                                         "vol->mft_zone_pos = "
 370                                                         "0x%Lx.\n",
 371                                                         __FUNCTION__,
 372                                                         (long long)
 373                                                         vol->mft_zone_pos);
 374                                         break;
 375                                 case 2:
 376                                         Dprintf("%s(): Before checks, "
 377                                                         "vol->data1_zone_pos = "
 378                                                         "0x%Lx.\n",
 379                                                         __FUNCTION__,
 380                                                         (long long)
 381                                                         vol->data1_zone_pos);
 382                                         if (tc >= vol->nr_clusters)
 383                                                 vol->data1_zone_pos =
 384                                                              vol->mft_zone_end;
 385                                         else if ((bmp_initial_pos >=
 386                                                     vol->data1_zone_pos ||
 387                                                     tc > vol->data1_zone_pos)
 388                                                     && tc >= vol->mft_zone_end)
 389                                                 vol->data1_zone_pos = tc;
 390                                         Dprintf("%s(): After checks, "
 391                                                         "vol->data1_zone_pos = "
 392                                                         "0x%Lx.\n",
 393                                                         __FUNCTION__,
 394                                                         (long long)
 395                                                         vol->data1_zone_pos);
 396                                         break;
 397                                 case 4:
 398                                         Dprintf("%s(): Before checks, "
 399                                                         "vol->data2_zone_pos = "
 400                                                         "0x%Lx.\n",
 401                                                         __FUNCTION__,
 402                                                         (long long)
 403                                                         vol->data2_zone_pos);
 404                                         if (tc >= vol->mft_zone_start)
 405                                                 vol->data2_zone_pos = 0;
 406                                         else if (bmp_initial_pos >=
 407                                                       vol->data2_zone_pos ||
 408                                                       tc > vol->data2_zone_pos)
 409                                                 vol->data2_zone_pos = tc;
 410                                         Dprintf("%s(): After checks, "
 411                                                         "vol->data2_zone_pos = "
 412                                                         "0x%Lx.\n",
 413                                                         __FUNCTION__,
 414                                                         (long long)
 415                                                         vol->data2_zone_pos);
 416                                         break;
 417                                 default:
 418                                         if (rl)
 419                                                 free(rl);
 420                                         free(buf);
 421                                         NTFS_BUG("switch(search_zone)");
 422                                         return NULL;
 423                                 }
 424                                 Dprintf("%s(): Going to done_ret.\n",
 425                                                 __FUNCTION__);
 426                                 goto done_ret;
 427                         }
 428                         lcn++;
 429                 }
 430                 bmp_pos += buf_size;
 431                 Dprintf("%s(): After inner while loop: buf_size = 0x%x, "
 432                                 "lcn = 0x%Lx, bmp_pos = 0x%Lx, need_writeback "
 433                                 "= %i.\n", __FUNCTION__, buf_size,
 434                                 (long long)lcn, (long long)bmp_pos,
 435                                 need_writeback);
 436                 if (need_writeback) {
 437                         s64 bw;
 438                         Dprintf("%s(): Writing back.\n", __FUNCTION__);
 439                         need_writeback = 0;
 440                         bw = ntfs_attr_pwrite(vol->lcnbmp_na, last_read_pos,
 441                                         br, buf);
 442                         if (bw != br) {
 443                                 if (bw == -1)
 444                                         err = errno;
 445                                 else
 446                                         err = EIO;
 447                                 fprintf(stderr, "%s(): Bitmap writeback "
 448                                                 "failed in read next buffer "
 449                                                 "code path with error code "
 450                                                 "%i.\n", __FUNCTION__, err);
 451                                 goto err_ret;
 452                         }
 453                 }
 454                 if (bmp_pos < zone_end) {
 455                         Dprintf("%s(): Continuing outer while loop, bmp_pos = "
 456                                         "0x%Lx, zone_end = 0x%Lx.\n",
 457                                         __FUNCTION__, (long long)bmp_pos,
 458                                         (long long)zone_end);
 459                         continue;
 460                 }
 461 zone_pass_done: /* Finished with the current zone pass. */
 462                 Dprintf("%s(): At zone_pass_done, pass = %i.\n", __FUNCTION__,
 463                                 pass);
 464                 if (pass == 1) {
 465                         /*
 466                          * Now do pass 2, scanning the first part of the zone
 467                          * we omitted in pass 1.
 468                          */
 469                         pass = 2;
 470                         zone_end = zone_start;
 471                         switch (search_zone) {
 472                         case 1: /* mft_zone */
 473                                 zone_start = vol->mft_zone_start;
 474                                 break;
 475                         case 2: /* data1_zone */
 476                                 zone_start = vol->mft_zone_end;
 477                                 break;
 478                         case 4: /* data2_zone */
 479                                 zone_start = 0;
 480                                 break;
 481                         default:
 482                                 NTFS_BUG("switch(search_zone), 2");
 483                         }
 484                         /* Sanity check. */
 485                         if (zone_end < zone_start)
 486                                 zone_end = zone_start;
 487                         bmp_pos = zone_start;
 488                         Dprintf("%s(): Continuing outer while loop, pass = 2, "
 489                                         "zone_start = 0x%Lx, zone_end = 0x%Lx, "
 490                                         "bmp_pos = 0x%Lx.\n", __FUNCTION__,
 491                                         zone_start, zone_end, bmp_pos);
 492                         continue;
 493                 } /* pass == 2 */
 494 done_zones_check:
 495                 Dprintf("%s(): At done_zones_check, search_zone = %i, "
 496                                 "done_zones before = 0x%x, done_zones after = "
 497                                 "0x%x.\n", __FUNCTION__, search_zone,
 498                                 done_zones, done_zones | search_zone);
 499                 done_zones |= search_zone;
 500                 if (done_zones < 7) {
 501                         Dprintf("%s(): Switching zone.\n", __FUNCTION__);
 502                         /* Now switch to the next zone we haven't done yet. */
 503                         pass = 1;
 504                         switch (search_zone) {
 505                         case 1:
 506                                 Dprintf("%s(): Switching from mft zone to "
 507                                                 "data1 zone.\n", __FUNCTION__);
 508                                 /* Update mft zone position. */
 509                                 if (rlpos) {
 510                                         LCN tc;
 511                                         Dprintf("%s(): Before checks, "
 512                                                         "vol->mft_zone_pos = "
 513                                                         "0x%Lx.\n",
 514                                                         __FUNCTION__,
 515                                                         (long long)
 516                                                         vol->mft_zone_pos);
 517                                         tc = rl[rlpos - 1].lcn +
 518                                                         rl[rlpos - 1].length;
 519                                         if (tc >= vol->mft_zone_end) {
 520                                                 vol->mft_zone_pos =
 521                                                                 vol->mft_lcn;
 522                                                 if (!vol->mft_zone_end)
 523                                                         vol->mft_zone_pos = 0;
 524                                         } else if ((bmp_initial_pos >=
 525                                                         vol->mft_zone_pos ||
 526                                                         tc > vol->mft_zone_pos)
 527                                                         && tc >= vol->mft_lcn)
 528                                                 vol->mft_zone_pos = tc;
 529                                         Dprintf("%s(): After checks, "
 530                                                         "vol->mft_zone_pos = "
 531                                                         "0x%Lx.\n",
 532                                                         __FUNCTION__,
 533                                                         (long long)
 534                                                         vol->mft_zone_pos);
 535                                 }
 536                                 /* Switch from mft zone to data1 zone. */
 537 switch_to_data1_zone:           search_zone = 2;
 538                                 zone_start = bmp_initial_pos =
 539                                                 vol->data1_zone_pos;
 540                                 zone_end = vol->nr_clusters;
 541                                 if (zone_start == vol->mft_zone_end)
 542                                         pass = 2;
 543                                 if (zone_start >= zone_end) {
 544                                         vol->data1_zone_pos = zone_start =
 545                                                         vol->mft_zone_end;
 546                                         pass = 2;
 547                                 }
 548                                 break;
 549                         case 2:
 550                                 Dprintf("%s(): Switching from data1 zone to "
 551                                                 "data2 zone.\n", __FUNCTION__);
 552                                 /* Update data1 zone position. */
 553                                 if (rlpos) {
 554                                         LCN tc;
 555                                         Dprintf("%s(): Before checks, "
 556                                                         "vol->data1_zone_pos = "
 557                                                         "0x%Lx.\n",
 558                                                         __FUNCTION__,
 559                                                         (long long)
 560                                                         vol->data1_zone_pos);
 561                                         tc = rl[rlpos - 1].lcn +
 562                                                         rl[rlpos - 1].length;
 563                                         if (tc >= vol->nr_clusters)
 564                                                 vol->data1_zone_pos =
 565                                                              vol->mft_zone_end;
 566                                         else if ((bmp_initial_pos >=
 567                                                     vol->data1_zone_pos ||
 568                                                     tc > vol->data1_zone_pos)
 569                                                     && tc >= vol->mft_zone_end)
 570                                                 vol->data1_zone_pos = tc;
 571                                         Dprintf("%s(): After checks, "
 572                                                         "vol->data1_zone_pos = "
 573                                                         "0x%Lx.\n",
 574                                                         __FUNCTION__,
 575                                                         (long long)
 576                                                         vol->data1_zone_pos);
 577                                 }
 578                                 /* Switch from data1 zone to data2 zone. */
 579                                 search_zone = 4;
 580                                 zone_start = bmp_initial_pos =
 581                                                 vol->data2_zone_pos;
 582                                 zone_end = vol->mft_zone_start;
 583                                 if (!zone_start)
 584                                         pass = 2;
 585                                 if (zone_start >= zone_end) {
 586                                         vol->data2_zone_pos = zone_start =
 587                                                         bmp_initial_pos = 0;
 588                                         pass = 2;
 589                                 }
 590                                 break;
 591                         case 4:
 592                                 Dprintf("%s(): Switching from data2 zone to "
 593                                                 "data1 zone.\n");
 594                                 /* Update data2 zone position. */
 595                                 if (rlpos) {
 596                                         LCN tc;
 597                                         Dprintf("%s(): Before checks, "
 598                                                         "vol->data2_zone_pos = "
 599                                                         "0x%Lx.\n",
 600                                                         __FUNCTION__,
 601                                                         (long long)
 602                                                         vol->data2_zone_pos);
 603                                         tc = rl[rlpos - 1].lcn +
 604                                                         rl[rlpos - 1].length;
 605                                         if (tc >= vol->mft_zone_start)
 606                                                 vol->data2_zone_pos = 0;
 607                                         else if (bmp_initial_pos >=
 608                                                       vol->data2_zone_pos ||
 609                                                       tc > vol->data2_zone_pos)
 610                                                 vol->data2_zone_pos = tc;
 611                                         Dprintf("%s(): After checks, "
 612                                                         "vol->data2_zone_pos = "
 613                                                         "0x%Lx.\n",
 614                                                         __FUNCTION__,
 615                                                         (long long)
 616                                                         vol->data2_zone_pos);
 617                                 }
 618                                 /* Switch from data2 zone to data1 zone. */
 619                                 goto switch_to_data1_zone; /* See above. */
 620                         default:
 621                                 NTFS_BUG("switch(search_zone) 3");
 622                         }
 623                         Dprintf("%s(): After zone switch, search_zone = %i, "
 624                                         "pass = %i, bmp_initial_pos = 0x%Lx, "
 625                                         "zone_start = 0x%Lx, zone_end = "
 626                                         "0x%Lx.\n", __FUNCTION__, search_zone,
 627                                         pass, (long long)bmp_initial_pos,
 628                                         (long long)zone_start,
 629                                         (long long)zone_end);
 630                         bmp_pos = zone_start;
 631                         if (zone_start == zone_end) {
 632                                 Dprintf("%s(): Empty zone, going to "
 633                                                 "done_zones_check.\n",
 634                                                 __FUNCTION__);
 635                                 /* Empty zone. Don't bother searching it. */
 636                                 goto done_zones_check;
 637                         }
 638                         Dprintf("%s(): Continuing outer while loop.\n",
 639                                         __FUNCTION__);
 640                         continue;
 641                 } /* done_zones == 7 */
 642                 Dprintf("%s(): All zones are finished.\n", __FUNCTION__);
 643                 /*
 644                  * All zones are finished! If DATA_ZONE, shrink mft zone. If
 645                  * MFT_ZONE, we have really run out of space.
 646                  */
 647                 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start;
 648                 Dprintf("%s(): vol->mft_zone_start = 0x%Lx, vol->mft_zone_end "
 649                                 "= 0x%Lx, mft_zone_size = 0x%Lx.\n",
 650                                 __FUNCTION__, (long long)vol->mft_zone_start,
 651                                 (long long)vol->mft_zone_end,
 652                                 (long long)mft_zone_size);
 653                 if (zone == MFT_ZONE || mft_zone_size <= 0) {
 654                         Dprintf("%s(): No free clusters left, going to "
 655                                         "err_ret.\n", __FUNCTION__);
 656                         /* Really no more space left on device. */
 657                         err = ENOSPC;
 658                         goto err_ret;
 659                 } /* zone == DATA_ZONE && mft_zone_size > 0 */
 660                 Dprintf("%s(): Shrinking mft zone.\n", __FUNCTION__);
 661                 zone_end = vol->mft_zone_end;
 662                 mft_zone_size >>= 1;
 663                 if (mft_zone_size > 0)
 664                         vol->mft_zone_end = vol->mft_zone_start + mft_zone_size;
 665                 else /* mft zone and data2 zone no longer exist. */
 666                         vol->data2_zone_pos = vol->mft_zone_start =
 667                                         vol->mft_zone_end = 0;
 668                 if (vol->mft_zone_pos >= vol->mft_zone_end) {
 669                         vol->mft_zone_pos = vol->mft_lcn;
 670                         if (!vol->mft_zone_end)
 671                                 vol->mft_zone_pos = 0;
 672                 }
 673                 bmp_pos = zone_start = bmp_initial_pos =
 674                                 vol->data1_zone_pos = vol->mft_zone_end;
 675                 search_zone = 2;
 676                 pass = 2;
 677                 done_zones &= ~2;
 678                 Dprintf("%s(): After shrinking mft zone, mft_zone_size = "
 679                                 "0x%Lx, vol->mft_zone_start = 0x%Lx, "
 680                                 "vol->mft_zone_end = 0x%Lx, vol->mft_zone_pos "
 681                                 "= 0x%Lx, search_zone = 2, pass = 2, "
 682                                 "dones_zones = 0x%x, zone_start = 0x%Lx, "
 683                                 "zone_end = 0x%Lx, vol->data1_zone_pos = "
 684                                 "0x%Lx, continuing outer while loop.\n",
 685                                 __FUNCTION__, (long long)mft_zone_size,
 686                                 (long long)vol->mft_zone_start,
 687                                 (long long)vol->mft_zone_end,
 688                                 (long long)vol->mft_zone_pos,
 689                                 done_zones, (long long)zone_start,
 690                                 (long long)zone_end,
 691                                 (long long)vol->data1_zone_pos);
 692         }
 693         Dprintf("%s(): After outer while loop.\n");
 694 done_ret:
 695         Dprintf("%s(): At done_ret.\n");
 696         /* Add runlist terminator element. */
 697         rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length;
 698         rl[rlpos].lcn = LCN_ENOENT;
 699         rl[rlpos].length = 0;
 700         if (need_writeback) {
 701                 s64 bw;
 702                 Dprintf("%s(): Writing back.\n", __FUNCTION__);
 703                 need_writeback = 0;
 704                 bw = ntfs_attr_pwrite(vol->lcnbmp_na, last_read_pos, br, buf);
 705                 if (bw != br) {
 706                         if (bw < 0)
 707                                 err = errno;
 708                         else
 709                                 err = EIO;
 710                         fprintf(stderr, "%s(): Bitmap writeback failed "
 711                                         "in done code path with error code "
 712                                         "%i.\n", __FUNCTION__, err);
 713                         goto err_ret;
 714                 }
 715         }
 716 done_err_ret:
 717         Dprintf("%s(): At done_err_ret (follows done_ret).\n");
 718         free(buf);
 719         /* Done! */
 720         if (!err)
 721                 return rl;
 722         Dprintf("%s(): Failed to allocate clusters. Returning with error code "
 723                         "%i.\n", __FUNCTION__, err);
 724         errno = err;
 725         return NULL;
 726 wb_err_ret:
 727         Dprintf("%s(): At wb_err_ret.\n", __FUNCTION__);
 728         if (need_writeback) {
 729                 s64 bw;
 730                 Dprintf("%s(): Writing back.\n", __FUNCTION__);
 731                 need_writeback = 0;
 732                 bw = ntfs_attr_pwrite(vol->lcnbmp_na, last_read_pos, br, buf);
 733                 if (bw != br) {
 734                         if (bw < 0)
 735                                 err = errno;
 736                         else
 737                                 err = EIO;
 738                         fprintf(stderr, "%s(): Bitmap writeback failed "
 739                                         "in error code path with error code "
 740                                         "%i.\n", __FUNCTION__, err);
 741                 }
 742         }
 743 err_ret:
 744         Dprintf("%s(): At err_ret.\n", __FUNCTION__);
 745         if (rl) {
 746                 if (err == ENOSPC) {
 747                         Dprintf("%s(): err = ENOSPC, first free lcn = 0x%Lx, "
 748                                         "could allocate up to = 0x%Lx "
 749                                         "clusters.\n", __FUNCTION__,
 750                                         (long long)rl[0].lcn,
 751                                         (long long)count - clusters);
 752                 }
 753 //FIXME: We don't have an attribute just a run list here! Also rl is not
 754 //       terminated at this moment in time! (AIA)
 755 #if 0
 756                 /* Deallocate all allocated clusters. */
 757                 Dprintf("%s(): Deallocating allocated clusters.\n",
 758                                 __FUNCTION__);
 759                 ntfs_cluster_free(vol, attrib_with_rl, 0, -1);
 760 #endif
 761                 fprintf(stderr, "%s(): Eeek! Leaving inconsistent metadata.\n",
 762                                 __FUNCTION__);
 763                 /* Free the runlist. */
 764                 free(rl);
 765                 rl = NULL;
 766         } else {
 767                 if (err == ENOSPC) {
 768                         Dprintf("%s(): No space left at all, err = ENOSPC, "
 769                                         "first free lcn = 0x%Lx.\n",
 770                                         __FUNCTION__,
 771                                         (long long)vol->data1_zone_pos);
 772                 }
 773         }
 774         Dprintf("%s(): rl = NULL, going to done_err_ret.\n", __FUNCTION__);
 775         goto done_err_ret;
 776 }
 777
 778 /**
 779  * ntfs_cluster_free - free clusters on an ntfs volume
 780  * @vol:        mounted ntfs volume on which to free the clusters
 781  * @na:         attribute whose runlist describes the clusters to free
 782  * @start_vcn:  vcn in @rl at which to start freeing clusters
 783  * @count:      number of clusters to free or -1 for all clusters
 784  *
 785  * Free @count clusters starting at the cluster @start_vcn in the runlist
 786  * described by the attribute @na from the mounted ntfs volume @vol.
 787  *
 788  * If @count is -1, all clusters from @start_vcn to the end of the runlist
 789  * are deallocated.
 790  *
 791  * On success return the number of deallocated clusters (not counting sparse
 792  * clusters) and on error return -1 with errno set to the error code.
 793  */
 794 int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count)
 795 {
 796         runlist *rl;
 797         s64 nr_freed, delta, to_free;
 798
 799         if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 ||
 800                         (count < 0 && count != -1)) {
 801                 fprintf(stderr, "%s(): Invalid arguments!\n", __FUNCTION__);
 802                 errno = EINVAL;
 803                 return -1;
 804         }
 805
 806         rl = ntfs_attr_find_vcn(na, start_vcn);
 807         if (!rl)
 808                 return -1;
 809
 810         if (rl->lcn < 0 && rl->lcn != LCN_HOLE) {
 811                 errno = EIO;
 812                 return -1;
 813         }
 814
 815         /* Find the starting cluster inside the run that needs freeing. */
 816         delta = start_vcn - rl->vcn;
 817
 818         /* The number of clusters in this run that need freeing. */
 819         to_free = rl->length - delta;
 820         if (count >= 0 && to_free > count)
 821                 to_free = count;
 822
 823         if (rl->lcn != LCN_HOLE) {
 824                 /* Do the actual freeing of the clusters in this run. */
 825                 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta,
 826                                 to_free))
 827                         return -1;
 828                 /* We have freed @to_free real clusters. */
 829                 nr_freed = to_free;
 830         } else {
 831                 /* No real clusters were freed. */
 832                 nr_freed = 0;
 833         }
 834
 835         /* Go to the next run and adjust the number of clusters left to free. */
 836         ++rl;
 837         if (count >= 0)
 838                 count -= to_free;
 839
 840         /*
 841          * Loop over the remaining runs, using @count as a capping value, and
 842          * free them.
 843          */
 844         for (; rl->length && count != 0; ++rl) {
 845                 // FIXME: Need to try ntfs_attr_map_runlist() for attribute
 846                 //        list support! (AIA)
 847                 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) {
 848                         // FIXME: Eeek! We need rollback! (AIA)
 849                         fprintf(stderr, "%s(): Eeek! invalid lcn (= %Li). "
 850                                         "Should attempt to map runlist! "
 851                                         "Leaving inconsistent metadata!\n",
 852                                         __FUNCTION__, (long long)rl->lcn);
 853                         errno = EIO;
 854                         return -1;
 855                 }
 856
 857                 /* The number of clusters in this run that need freeing. */
 858                 to_free = rl->length;
 859                 if (count >= 0 && to_free > count)
 860                         to_free = count;
 861
 862                 if (rl->lcn != LCN_HOLE) {
 863                         /* Do the actual freeing of the clusters in the run. */
 864                         if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn,
 865                                         to_free)) {
 866                                 int eo = errno;
 867
 868                                 // FIXME: Eeek! We need rollback! (AIA)
 869                                 fprintf(stderr, "%s(): Eeek! bitmap clear run "
 870                                                 "failed. Leaving inconsistent "
 871                                                 "metadata!\n", __FUNCTION__);
 872                                 errno = eo;
 873                                 return -1;
 874                         }
 875                         /* We have freed @to_free real clusters. */
 876                         nr_freed += to_free;
 877                 }
 878
 879                 if (count >= 0)
 880                         count -= to_free;
 881         }
 882
 883         if (count != -1 && count != 0) {
 884                 // FIXME: Eeek! BUG()
 885                 fprintf(stderr, "%s(): Eeek! count still not zero (= %Li). "
 886                                 "Leaving inconsistent metadata!\n",
 887                                 __FUNCTION__, (long long)count);
 888                 errno = EIO;
 889                 return -1;
 890         }
 891
 892         /* Done. Return the number of actual clusters that were freed. */
 893         return nr_freed;
 894 }
 895