fs/ntfs3/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  *
   4  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
   5  *
   6  * This code builds two trees of free clusters extents.
   7  * Trees are sorted by start of extent and by length of extent.
   8  * NTFS_MAX_WND_EXTENTS defines the maximum number of elements in trees.
   9  * In extreme case code reads on-disk bitmap to find free clusters.
  10  *
  11  */
  12
  13 #include <linux/buffer_head.h>
  14 #include <linux/fs.h>
  15 #include <linux/kernel.h>
  16
  17 #include "ntfs.h"
  18 #include "ntfs_fs.h"
  19
  20 /*
  21  * Maximum number of extents in tree.
  22  */
  23 #define NTFS_MAX_WND_EXTENTS (32u * 1024u)
  24
  25 struct rb_node_key {
  26         struct rb_node node;
  27         size_t key;
  28 };
  29
  30 struct e_node {
  31         struct rb_node_key start; /* Tree sorted by start. */
  32         struct rb_node_key count; /* Tree sorted by len. */
  33 };
  34
  35 static int wnd_rescan(struct wnd_bitmap *wnd);
  36 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw);
  37 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits);
  38
  39 static struct kmem_cache *ntfs_enode_cachep;
  40
  41 int __init ntfs3_init_bitmap(void)
  42 {
  43         ntfs_enode_cachep =
  44                 kmem_cache_create("ntfs3_enode_cache", sizeof(struct e_node), 0,
  45                                   SLAB_RECLAIM_ACCOUNT, NULL);
  46         return ntfs_enode_cachep ? 0 : -ENOMEM;
  47 }
  48
  49 void ntfs3_exit_bitmap(void)
  50 {
  51         kmem_cache_destroy(ntfs_enode_cachep);
  52 }
  53
  54 static inline u32 wnd_bits(const struct wnd_bitmap *wnd, size_t i)
  55 {
  56         return i + 1 == wnd->nwnd ? wnd->bits_last : wnd->sb->s_blocksize * 8;
  57 }
  58
  59 /*
  60  * wnd_scan
  61  *
  62  * b_pos + b_len - biggest fragment.
  63  * Scan range [wpos wbits) window @buf.
  64  *
  65  * Return: -1 if not found.
  66  */
  67 static size_t wnd_scan(const ulong *buf, size_t wbit, u32 wpos, u32 wend,
  68                        size_t to_alloc, size_t *prev_tail, size_t *b_pos,
  69                        size_t *b_len)
  70 {
  71         while (wpos < wend) {
  72                 size_t free_len;
  73                 u32 free_bits, end;
  74                 u32 used = find_next_zero_bit(buf, wend, wpos);
  75
  76                 if (used >= wend) {
  77                         if (*b_len < *prev_tail) {
  78                                 *b_pos = wbit - *prev_tail;
  79                                 *b_len = *prev_tail;
  80                         }
  81
  82                         *prev_tail = 0;
  83                         return -1;
  84                 }
  85
  86                 if (used > wpos) {
  87                         wpos = used;
  88                         if (*b_len < *prev_tail) {
  89                                 *b_pos = wbit - *prev_tail;
  90                                 *b_len = *prev_tail;
  91                         }
  92
  93                         *prev_tail = 0;
  94                 }
  95
  96                 /*
  97                  * Now we have a fragment [wpos, wend) staring with 0.
  98                  */
  99                 end = wpos + to_alloc - *prev_tail;
 100                 free_bits = find_next_bit(buf, min(end, wend), wpos);
 101
 102                 free_len = *prev_tail + free_bits - wpos;
 103
 104                 if (*b_len < free_len) {
 105                         *b_pos = wbit + wpos - *prev_tail;
 106                         *b_len = free_len;
 107                 }
 108
 109                 if (free_len >= to_alloc)
 110                         return wbit + wpos - *prev_tail;
 111
 112                 if (free_bits >= wend) {
 113                         *prev_tail += free_bits - wpos;
 114                         return -1;
 115                 }
 116
 117                 wpos = free_bits + 1;
 118
 119                 *prev_tail = 0;
 120         }
 121
 122         return -1;
 123 }
 124
 125 /*
 126  * wnd_close - Frees all resources.
 127  */
 128 void wnd_close(struct wnd_bitmap *wnd)
 129 {
 130         struct rb_node *node, *next;
 131
 132         kfree(wnd->free_bits);
 133         run_close(&wnd->run);
 134
 135         node = rb_first(&wnd->start_tree);
 136
 137         while (node) {
 138                 next = rb_next(node);
 139                 rb_erase(node, &wnd->start_tree);
 140                 kmem_cache_free(ntfs_enode_cachep,
 141                                 rb_entry(node, struct e_node, start.node));
 142                 node = next;
 143         }
 144 }
 145
 146 static struct rb_node *rb_lookup(struct rb_root *root, size_t v)
 147 {
 148         struct rb_node **p = &root->rb_node;
 149         struct rb_node *r = NULL;
 150
 151         while (*p) {
 152                 struct rb_node_key *k;
 153
 154                 k = rb_entry(*p, struct rb_node_key, node);
 155                 if (v < k->key) {
 156                         p = &(*p)->rb_left;
 157                 } else if (v > k->key) {
 158                         r = &k->node;
 159                         p = &(*p)->rb_right;
 160                 } else {
 161                         return &k->node;
 162                 }
 163         }
 164
 165         return r;
 166 }
 167
 168 /*
 169  * rb_insert_count - Helper function to insert special kind of 'count' tree.
 170  */
 171 static inline bool rb_insert_count(struct rb_root *root, struct e_node *e)
 172 {
 173         struct rb_node **p = &root->rb_node;
 174         struct rb_node *parent = NULL;
 175         size_t e_ckey = e->count.key;
 176         size_t e_skey = e->start.key;
 177
 178         while (*p) {
 179                 struct e_node *k =
 180                         rb_entry(parent = *p, struct e_node, count.node);
 181
 182                 if (e_ckey > k->count.key) {
 183                         p = &(*p)->rb_left;
 184                 } else if (e_ckey < k->count.key) {
 185                         p = &(*p)->rb_right;
 186                 } else if (e_skey < k->start.key) {
 187                         p = &(*p)->rb_left;
 188                 } else if (e_skey > k->start.key) {
 189                         p = &(*p)->rb_right;
 190                 } else {
 191                         WARN_ON(1);
 192                         return false;
 193                 }
 194         }
 195
 196         rb_link_node(&e->count.node, parent, p);
 197         rb_insert_color(&e->count.node, root);
 198         return true;
 199 }
 200
 201 /*
 202  * rb_insert_start - Helper function to insert special kind of 'count' tree.
 203  */
 204 static inline bool rb_insert_start(struct rb_root *root, struct e_node *e)
 205 {
 206         struct rb_node **p = &root->rb_node;
 207         struct rb_node *parent = NULL;
 208         size_t e_skey = e->start.key;
 209
 210         while (*p) {
 211                 struct e_node *k;
 212
 213                 parent = *p;
 214
 215                 k = rb_entry(parent, struct e_node, start.node);
 216                 if (e_skey < k->start.key) {
 217                         p = &(*p)->rb_left;
 218                 } else if (e_skey > k->start.key) {
 219                         p = &(*p)->rb_right;
 220                 } else {
 221                         WARN_ON(1);
 222                         return false;
 223                 }
 224         }
 225
 226         rb_link_node(&e->start.node, parent, p);
 227         rb_insert_color(&e->start.node, root);
 228         return true;
 229 }
 230
 231 /*
 232  * wnd_add_free_ext - Adds a new extent of free space.
 233  * @build:      1 when building tree.
 234  */
 235 static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len,
 236                              bool build)
 237 {
 238         struct e_node *e, *e0 = NULL;
 239         size_t ib, end_in = bit + len;
 240         struct rb_node *n;
 241
 242         if (build) {
 243                 /* Use extent_min to filter too short extents. */
 244                 if (wnd->count >= NTFS_MAX_WND_EXTENTS &&
 245                     len <= wnd->extent_min) {
 246                         wnd->uptodated = -1;
 247                         return;
 248                 }
 249         } else {
 250                 /* Try to find extent before 'bit'. */
 251                 n = rb_lookup(&wnd->start_tree, bit);
 252
 253                 if (!n) {
 254                         n = rb_first(&wnd->start_tree);
 255                 } else {
 256                         e = rb_entry(n, struct e_node, start.node);
 257                         n = rb_next(n);
 258                         if (e->start.key + e->count.key == bit) {
 259                                 /* Remove left. */
 260                                 bit = e->start.key;
 261                                 len += e->count.key;
 262                                 rb_erase(&e->start.node, &wnd->start_tree);
 263                                 rb_erase(&e->count.node, &wnd->count_tree);
 264                                 wnd->count -= 1;
 265                                 e0 = e;
 266                         }
 267                 }
 268
 269                 while (n) {
 270                         size_t next_end;
 271
 272                         e = rb_entry(n, struct e_node, start.node);
 273                         next_end = e->start.key + e->count.key;
 274                         if (e->start.key > end_in)
 275                                 break;
 276
 277                         /* Remove right. */
 278                         n = rb_next(n);
 279                         len += next_end - end_in;
 280                         end_in = next_end;
 281                         rb_erase(&e->start.node, &wnd->start_tree);
 282                         rb_erase(&e->count.node, &wnd->count_tree);
 283                         wnd->count -= 1;
 284
 285                         if (!e0)
 286                                 e0 = e;
 287                         else
 288                                 kmem_cache_free(ntfs_enode_cachep, e);
 289                 }
 290
 291                 if (wnd->uptodated != 1) {
 292                         /* Check bits before 'bit'. */
 293                         ib = wnd->zone_bit == wnd->zone_end ||
 294                                              bit < wnd->zone_end
 295                                      ? 0
 296                                      : wnd->zone_end;
 297
 298                         while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) {
 299                                 bit -= 1;
 300                                 len += 1;
 301                         }
 302
 303                         /* Check bits after 'end_in'. */
 304                         ib = wnd->zone_bit == wnd->zone_end ||
 305                                              end_in > wnd->zone_bit
 306                                      ? wnd->nbits
 307                                      : wnd->zone_bit;
 308
 309                         while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) {
 310                                 end_in += 1;
 311                                 len += 1;
 312                         }
 313                 }
 314         }
 315         /* Insert new fragment. */
 316         if (wnd->count >= NTFS_MAX_WND_EXTENTS) {
 317                 if (e0)
 318                         kmem_cache_free(ntfs_enode_cachep, e0);
 319
 320                 wnd->uptodated = -1;
 321
 322                 /* Compare with smallest fragment. */
 323                 n = rb_last(&wnd->count_tree);
 324                 e = rb_entry(n, struct e_node, count.node);
 325                 if (len <= e->count.key)
 326                         goto out; /* Do not insert small fragments. */
 327
 328                 if (build) {
 329                         struct e_node *e2;
 330
 331                         n = rb_prev(n);
 332                         e2 = rb_entry(n, struct e_node, count.node);
 333                         /* Smallest fragment will be 'e2->count.key'. */
 334                         wnd->extent_min = e2->count.key;
 335                 }
 336
 337                 /* Replace smallest fragment by new one. */
 338                 rb_erase(&e->start.node, &wnd->start_tree);
 339                 rb_erase(&e->count.node, &wnd->count_tree);
 340                 wnd->count -= 1;
 341         } else {
 342                 e = e0 ? e0 : kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC);
 343                 if (!e) {
 344                         wnd->uptodated = -1;
 345                         goto out;
 346                 }
 347
 348                 if (build && len <= wnd->extent_min)
 349                         wnd->extent_min = len;
 350         }
 351         e->start.key = bit;
 352         e->count.key = len;
 353         if (len > wnd->extent_max)
 354                 wnd->extent_max = len;
 355
 356         rb_insert_start(&wnd->start_tree, e);
 357         rb_insert_count(&wnd->count_tree, e);
 358         wnd->count += 1;
 359
 360 out:;
 361 }
 362
 363 /*
 364  * wnd_remove_free_ext - Remove a run from the cached free space.
 365  */
 366 static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len)
 367 {
 368         struct rb_node *n, *n3;
 369         struct e_node *e, *e3;
 370         size_t end_in = bit + len;
 371         size_t end3, end, new_key, new_len, max_new_len;
 372
 373         /* Try to find extent before 'bit'. */
 374         n = rb_lookup(&wnd->start_tree, bit);
 375
 376         if (!n)
 377                 return;
 378
 379         e = rb_entry(n, struct e_node, start.node);
 380         end = e->start.key + e->count.key;
 381
 382         new_key = new_len = 0;
 383         len = e->count.key;
 384
 385         /* Range [bit,end_in) must be inside 'e' or outside 'e' and 'n'. */
 386         if (e->start.key > bit)
 387                 ;
 388         else if (end_in <= end) {
 389                 /* Range [bit,end_in) inside 'e'. */
 390                 new_key = end_in;
 391                 new_len = end - end_in;
 392                 len = bit - e->start.key;
 393         } else if (bit > end) {
 394                 bool bmax = false;
 395
 396                 n3 = rb_next(n);
 397
 398                 while (n3) {
 399                         e3 = rb_entry(n3, struct e_node, start.node);
 400                         if (e3->start.key >= end_in)
 401                                 break;
 402
 403                         if (e3->count.key == wnd->extent_max)
 404                                 bmax = true;
 405
 406                         end3 = e3->start.key + e3->count.key;
 407                         if (end3 > end_in) {
 408                                 e3->start.key = end_in;
 409                                 rb_erase(&e3->count.node, &wnd->count_tree);
 410                                 e3->count.key = end3 - end_in;
 411                                 rb_insert_count(&wnd->count_tree, e3);
 412                                 break;
 413                         }
 414
 415                         n3 = rb_next(n3);
 416                         rb_erase(&e3->start.node, &wnd->start_tree);
 417                         rb_erase(&e3->count.node, &wnd->count_tree);
 418                         wnd->count -= 1;
 419                         kmem_cache_free(ntfs_enode_cachep, e3);
 420                 }
 421                 if (!bmax)
 422                         return;
 423                 n3 = rb_first(&wnd->count_tree);
 424                 wnd->extent_max =
 425                         n3 ? rb_entry(n3, struct e_node, count.node)->count.key
 426                            : 0;
 427                 return;
 428         }
 429
 430         if (e->count.key != wnd->extent_max) {
 431                 ;
 432         } else if (rb_prev(&e->count.node)) {
 433                 ;
 434         } else {
 435                 n3 = rb_next(&e->count.node);
 436                 max_new_len = max(len, new_len);
 437                 if (!n3) {
 438                         wnd->extent_max = max_new_len;
 439                 } else {
 440                         e3 = rb_entry(n3, struct e_node, count.node);
 441                         wnd->extent_max = max(e3->count.key, max_new_len);
 442                 }
 443         }
 444
 445         if (!len) {
 446                 if (new_len) {
 447                         e->start.key = new_key;
 448                         rb_erase(&e->count.node, &wnd->count_tree);
 449                         e->count.key = new_len;
 450                         rb_insert_count(&wnd->count_tree, e);
 451                 } else {
 452                         rb_erase(&e->start.node, &wnd->start_tree);
 453                         rb_erase(&e->count.node, &wnd->count_tree);
 454                         wnd->count -= 1;
 455                         kmem_cache_free(ntfs_enode_cachep, e);
 456                 }
 457                 goto out;
 458         }
 459         rb_erase(&e->count.node, &wnd->count_tree);
 460         e->count.key = len;
 461         rb_insert_count(&wnd->count_tree, e);
 462
 463         if (!new_len)
 464                 goto out;
 465
 466         if (wnd->count >= NTFS_MAX_WND_EXTENTS) {
 467                 wnd->uptodated = -1;
 468
 469                 /* Get minimal extent. */
 470                 e = rb_entry(rb_last(&wnd->count_tree), struct e_node,
 471                              count.node);
 472                 if (e->count.key > new_len)
 473                         goto out;
 474
 475                 /* Replace minimum. */
 476                 rb_erase(&e->start.node, &wnd->start_tree);
 477                 rb_erase(&e->count.node, &wnd->count_tree);
 478                 wnd->count -= 1;
 479         } else {
 480                 e = kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC);
 481                 if (!e)
 482                         wnd->uptodated = -1;
 483         }
 484
 485         if (e) {
 486                 e->start.key = new_key;
 487                 e->count.key = new_len;
 488                 rb_insert_start(&wnd->start_tree, e);
 489                 rb_insert_count(&wnd->count_tree, e);
 490                 wnd->count += 1;
 491         }
 492
 493 out:
 494         if (!wnd->count && 1 != wnd->uptodated)
 495                 wnd_rescan(wnd);
 496 }
 497
 498 /*
 499  * wnd_rescan - Scan all bitmap. Used while initialization.
 500  */
 501 static int wnd_rescan(struct wnd_bitmap *wnd)
 502 {
 503         int err = 0;
 504         size_t prev_tail = 0;
 505         struct super_block *sb = wnd->sb;
 506         struct ntfs_sb_info *sbi = sb->s_fs_info;
 507         u64 lbo, len = 0;
 508         u32 blocksize = sb->s_blocksize;
 509         u8 cluster_bits = sbi->cluster_bits;
 510         u32 wbits = 8 * sb->s_blocksize;
 511         u32 used, frb;
 512         const ulong *buf;
 513         size_t wpos, wbit, iw, vbo;
 514         struct buffer_head *bh = NULL;
 515         CLST lcn, clen;
 516
 517         wnd->uptodated = 0;
 518         wnd->extent_max = 0;
 519         wnd->extent_min = MINUS_ONE_T;
 520         wnd->total_zeroes = 0;
 521
 522         vbo = 0;
 523
 524         for (iw = 0; iw < wnd->nwnd; iw++) {
 525                 if (iw + 1 == wnd->nwnd)
 526                         wbits = wnd->bits_last;
 527
 528                 if (wnd->inited) {
 529                         if (!wnd->free_bits[iw]) {
 530                                 /* All ones. */
 531                                 if (prev_tail) {
 532                                         wnd_add_free_ext(wnd,
 533                                                          vbo * 8 - prev_tail,
 534                                                          prev_tail, true);
 535                                         prev_tail = 0;
 536                                 }
 537                                 goto next_wnd;
 538                         }
 539                         if (wbits == wnd->free_bits[iw]) {
 540                                 /* All zeroes. */
 541                                 prev_tail += wbits;
 542                                 wnd->total_zeroes += wbits;
 543                                 goto next_wnd;
 544                         }
 545                 }
 546
 547                 if (!len) {
 548                         u32 off = vbo & sbi->cluster_mask;
 549
 550                         if (!run_lookup_entry(&wnd->run, vbo >> cluster_bits,
 551                                               &lcn, &clen, NULL)) {
 552                                 err = -ENOENT;
 553                                 goto out;
 554                         }
 555
 556                         lbo = ((u64)lcn << cluster_bits) + off;
 557                         len = ((u64)clen << cluster_bits) - off;
 558                 }
 559
 560                 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits);
 561                 if (!bh) {
 562                         err = -EIO;
 563                         goto out;
 564                 }
 565
 566                 buf = (ulong *)bh->b_data;
 567
 568                 used = __bitmap_weight(buf, wbits);
 569                 if (used < wbits) {
 570                         frb = wbits - used;
 571                         wnd->free_bits[iw] = frb;
 572                         wnd->total_zeroes += frb;
 573                 }
 574
 575                 wpos = 0;
 576                 wbit = vbo * 8;
 577
 578                 if (wbit + wbits > wnd->nbits)
 579                         wbits = wnd->nbits - wbit;
 580
 581                 do {
 582                         used = find_next_zero_bit(buf, wbits, wpos);
 583
 584                         if (used > wpos && prev_tail) {
 585                                 wnd_add_free_ext(wnd, wbit + wpos - prev_tail,
 586                                                  prev_tail, true);
 587                                 prev_tail = 0;
 588                         }
 589
 590                         wpos = used;
 591
 592                         if (wpos >= wbits) {
 593                                 /* No free blocks. */
 594                                 prev_tail = 0;
 595                                 break;
 596                         }
 597
 598                         frb = find_next_bit(buf, wbits, wpos);
 599                         if (frb >= wbits) {
 600                                 /* Keep last free block. */
 601                                 prev_tail += frb - wpos;
 602                                 break;
 603                         }
 604
 605                         wnd_add_free_ext(wnd, wbit + wpos - prev_tail,
 606                                          frb + prev_tail - wpos, true);
 607
 608                         /* Skip free block and first '1'. */
 609                         wpos = frb + 1;
 610                         /* Reset previous tail. */
 611                         prev_tail = 0;
 612                 } while (wpos < wbits);
 613
 614 next_wnd:
 615
 616                 if (bh)
 617                         put_bh(bh);
 618                 bh = NULL;
 619
 620                 vbo += blocksize;
 621                 if (len) {
 622                         len -= blocksize;
 623                         lbo += blocksize;
 624                 }
 625         }
 626
 627         /* Add last block. */
 628         if (prev_tail)
 629                 wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true);
 630
 631         /*
 632          * Before init cycle wnd->uptodated was 0.
 633          * If any errors or limits occurs while initialization then
 634          * wnd->uptodated will be -1.
 635          * If 'uptodated' is still 0 then Tree is really updated.
 636          */
 637         if (!wnd->uptodated)
 638                 wnd->uptodated = 1;
 639
 640         if (wnd->zone_bit != wnd->zone_end) {
 641                 size_t zlen = wnd->zone_end - wnd->zone_bit;
 642
 643                 wnd->zone_end = wnd->zone_bit;
 644                 wnd_zone_set(wnd, wnd->zone_bit, zlen);
 645         }
 646
 647 out:
 648         return err;
 649 }
 650
 651 int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits)
 652 {
 653         int err;
 654         u32 blocksize = sb->s_blocksize;
 655         u32 wbits = blocksize * 8;
 656
 657         init_rwsem(&wnd->rw_lock);
 658
 659         wnd->sb = sb;
 660         wnd->nbits = nbits;
 661         wnd->total_zeroes = nbits;
 662         wnd->extent_max = MINUS_ONE_T;
 663         wnd->zone_bit = wnd->zone_end = 0;
 664         wnd->nwnd = bytes_to_block(sb, bitmap_size(nbits));
 665         wnd->bits_last = nbits & (wbits - 1);
 666         if (!wnd->bits_last)
 667                 wnd->bits_last = wbits;
 668
 669         wnd->free_bits =
 670                 kcalloc(wnd->nwnd, sizeof(u16), GFP_NOFS | __GFP_NOWARN);
 671         if (!wnd->free_bits)
 672                 return -ENOMEM;
 673
 674         err = wnd_rescan(wnd);
 675         if (err)
 676                 return err;
 677
 678         wnd->inited = true;
 679
 680         return 0;
 681 }
 682
 683 /*
 684  * wnd_map - Call sb_bread for requested window.
 685  */
 686 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw)
 687 {
 688         size_t vbo;
 689         CLST lcn, clen;
 690         struct super_block *sb = wnd->sb;
 691         struct ntfs_sb_info *sbi;
 692         struct buffer_head *bh;
 693         u64 lbo;
 694
 695         sbi = sb->s_fs_info;
 696         vbo = (u64)iw << sb->s_blocksize_bits;
 697
 698         if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen,
 699                               NULL)) {
 700                 return ERR_PTR(-ENOENT);
 701         }
 702
 703         lbo = ((u64)lcn << sbi->cluster_bits) + (vbo & sbi->cluster_mask);
 704
 705         bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits);
 706         if (!bh)
 707                 return ERR_PTR(-EIO);
 708
 709         return bh;
 710 }
 711
 712 /*
 713  * wnd_set_free - Mark the bits range from bit to bit + bits as free.
 714  */
 715 int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits)
 716 {
 717         int err = 0;
 718         struct super_block *sb = wnd->sb;
 719         size_t bits0 = bits;
 720         u32 wbits = 8 * sb->s_blocksize;
 721         size_t iw = bit >> (sb->s_blocksize_bits + 3);
 722         u32 wbit = bit & (wbits - 1);
 723         struct buffer_head *bh;
 724
 725         while (iw < wnd->nwnd && bits) {
 726                 u32 tail, op;
 727                 ulong *buf;
 728
 729                 if (iw + 1 == wnd->nwnd)
 730                         wbits = wnd->bits_last;
 731
 732                 tail = wbits - wbit;
 733                 op = min_t(u32, tail, bits);
 734
 735                 bh = wnd_map(wnd, iw);
 736                 if (IS_ERR(bh)) {
 737                         err = PTR_ERR(bh);
 738                         break;
 739                 }
 740
 741                 buf = (ulong *)bh->b_data;
 742
 743                 lock_buffer(bh);
 744
 745                 __bitmap_clear(buf, wbit, op);
 746
 747                 wnd->free_bits[iw] += op;
 748
 749                 set_buffer_uptodate(bh);
 750                 mark_buffer_dirty(bh);
 751                 unlock_buffer(bh);
 752                 put_bh(bh);
 753
 754                 wnd->total_zeroes += op;
 755                 bits -= op;
 756                 wbit = 0;
 757                 iw += 1;
 758         }
 759
 760         wnd_add_free_ext(wnd, bit, bits0, false);
 761
 762         return err;
 763 }
 764
 765 /*
 766  * wnd_set_used - Mark the bits range from bit to bit + bits as used.
 767  */
 768 int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits)
 769 {
 770         int err = 0;
 771         struct super_block *sb = wnd->sb;
 772         size_t bits0 = bits;
 773         size_t iw = bit >> (sb->s_blocksize_bits + 3);
 774         u32 wbits = 8 * sb->s_blocksize;
 775         u32 wbit = bit & (wbits - 1);
 776         struct buffer_head *bh;
 777
 778         while (iw < wnd->nwnd && bits) {
 779                 u32 tail, op;
 780                 ulong *buf;
 781
 782                 if (unlikely(iw + 1 == wnd->nwnd))
 783                         wbits = wnd->bits_last;
 784
 785                 tail = wbits - wbit;
 786                 op = min_t(u32, tail, bits);
 787
 788                 bh = wnd_map(wnd, iw);
 789                 if (IS_ERR(bh)) {
 790                         err = PTR_ERR(bh);
 791                         break;
 792                 }
 793                 buf = (ulong *)bh->b_data;
 794
 795                 lock_buffer(bh);
 796
 797                 __bitmap_set(buf, wbit, op);
 798                 wnd->free_bits[iw] -= op;
 799
 800                 set_buffer_uptodate(bh);
 801                 mark_buffer_dirty(bh);
 802                 unlock_buffer(bh);
 803                 put_bh(bh);
 804
 805                 wnd->total_zeroes -= op;
 806                 bits -= op;
 807                 wbit = 0;
 808                 iw += 1;
 809         }
 810
 811         if (!RB_EMPTY_ROOT(&wnd->start_tree))
 812                 wnd_remove_free_ext(wnd, bit, bits0);
 813
 814         return err;
 815 }
 816
 817 /*
 818  * wnd_is_free_hlp
 819  *
 820  * Return: True if all clusters [bit, bit+bits) are free (bitmap only).
 821  */
 822 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits)
 823 {
 824         struct super_block *sb = wnd->sb;
 825         size_t iw = bit >> (sb->s_blocksize_bits + 3);
 826         u32 wbits = 8 * sb->s_blocksize;
 827         u32 wbit = bit & (wbits - 1);
 828
 829         while (iw < wnd->nwnd && bits) {
 830                 u32 tail, op;
 831
 832                 if (unlikely(iw + 1 == wnd->nwnd))
 833                         wbits = wnd->bits_last;
 834
 835                 tail = wbits - wbit;
 836                 op = min_t(u32, tail, bits);
 837
 838                 if (wbits != wnd->free_bits[iw]) {
 839                         bool ret;
 840                         struct buffer_head *bh = wnd_map(wnd, iw);
 841
 842                         if (IS_ERR(bh))
 843                                 return false;
 844
 845                         ret = are_bits_clear((ulong *)bh->b_data, wbit, op);
 846
 847                         put_bh(bh);
 848                         if (!ret)
 849                                 return false;
 850                 }
 851
 852                 bits -= op;
 853                 wbit = 0;
 854                 iw += 1;
 855         }
 856
 857         return true;
 858 }
 859
 860 /*
 861  * wnd_is_free
 862  *
 863  * Return: True if all clusters [bit, bit+bits) are free.
 864  */
 865 bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits)
 866 {
 867         bool ret;
 868         struct rb_node *n;
 869         size_t end;
 870         struct e_node *e;
 871
 872         if (RB_EMPTY_ROOT(&wnd->start_tree))
 873                 goto use_wnd;
 874
 875         n = rb_lookup(&wnd->start_tree, bit);
 876         if (!n)
 877                 goto use_wnd;
 878
 879         e = rb_entry(n, struct e_node, start.node);
 880
 881         end = e->start.key + e->count.key;
 882
 883         if (bit < end && bit + bits <= end)
 884                 return true;
 885
 886 use_wnd:
 887         ret = wnd_is_free_hlp(wnd, bit, bits);
 888
 889         return ret;
 890 }
 891
 892 /*
 893  * wnd_is_used
 894  *
 895  * Return: True if all clusters [bit, bit+bits) are used.
 896  */
 897 bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits)
 898 {
 899         bool ret = false;
 900         struct super_block *sb = wnd->sb;
 901         size_t iw = bit >> (sb->s_blocksize_bits + 3);
 902         u32 wbits = 8 * sb->s_blocksize;
 903         u32 wbit = bit & (wbits - 1);
 904         size_t end;
 905         struct rb_node *n;
 906         struct e_node *e;
 907
 908         if (RB_EMPTY_ROOT(&wnd->start_tree))
 909                 goto use_wnd;
 910
 911         end = bit + bits;
 912         n = rb_lookup(&wnd->start_tree, end - 1);
 913         if (!n)
 914                 goto use_wnd;
 915
 916         e = rb_entry(n, struct e_node, start.node);
 917         if (e->start.key + e->count.key > bit)
 918                 return false;
 919
 920 use_wnd:
 921         while (iw < wnd->nwnd && bits) {
 922                 u32 tail, op;
 923
 924                 if (unlikely(iw + 1 == wnd->nwnd))
 925                         wbits = wnd->bits_last;
 926
 927                 tail = wbits - wbit;
 928                 op = min_t(u32, tail, bits);
 929
 930                 if (wnd->free_bits[iw]) {
 931                         bool ret;
 932                         struct buffer_head *bh = wnd_map(wnd, iw);
 933
 934                         if (IS_ERR(bh))
 935                                 goto out;
 936
 937                         ret = are_bits_set((ulong *)bh->b_data, wbit, op);
 938                         put_bh(bh);
 939                         if (!ret)
 940                                 goto out;
 941                 }
 942
 943                 bits -= op;
 944                 wbit = 0;
 945                 iw += 1;
 946         }
 947         ret = true;
 948
 949 out:
 950         return ret;
 951 }
 952
 953 /*
 954  * wnd_find - Look for free space.
 955  *
 956  * - flags - BITMAP_FIND_XXX flags
 957  *
 958  * Return: 0 if not found.
 959  */
 960 size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint,
 961                 size_t flags, size_t *allocated)
 962 {
 963         struct super_block *sb;
 964         u32 wbits, wpos, wzbit, wzend;
 965         size_t fnd, max_alloc, b_len, b_pos;
 966         size_t iw, prev_tail, nwnd, wbit, ebit, zbit, zend;
 967         size_t to_alloc0 = to_alloc;
 968         const ulong *buf;
 969         const struct e_node *e;
 970         const struct rb_node *pr, *cr;
 971         u8 log2_bits;
 972         bool fbits_valid;
 973         struct buffer_head *bh;
 974
 975         /* Fast checking for available free space. */
 976         if (flags & BITMAP_FIND_FULL) {
 977                 size_t zeroes = wnd_zeroes(wnd);
 978
 979                 zeroes -= wnd->zone_end - wnd->zone_bit;
 980                 if (zeroes < to_alloc0)
 981                         goto no_space;
 982
 983                 if (to_alloc0 > wnd->extent_max)
 984                         goto no_space;
 985         } else {
 986                 if (to_alloc > wnd->extent_max)
 987                         to_alloc = wnd->extent_max;
 988         }
 989
 990         if (wnd->zone_bit <= hint && hint < wnd->zone_end)
 991                 hint = wnd->zone_end;
 992
 993         max_alloc = wnd->nbits;
 994         b_len = b_pos = 0;
 995
 996         if (hint >= max_alloc)
 997                 hint = 0;
 998
 999         if (RB_EMPTY_ROOT(&wnd->start_tree)) {
1000                 if (wnd->uptodated == 1) {
1001                         /* Extents tree is updated -> No free space. */
1002                         goto no_space;
1003                 }
1004                 goto scan_bitmap;
1005         }
1006
1007         e = NULL;
1008         if (!hint)
1009                 goto allocate_biggest;
1010
1011         /* Use hint: Enumerate extents by start >= hint. */
1012         pr = NULL;
1013         cr = wnd->start_tree.rb_node;
1014
1015         for (;;) {
1016                 e = rb_entry(cr, struct e_node, start.node);
1017
1018                 if (e->start.key == hint)
1019                         break;
1020
1021                 if (e->start.key < hint) {
1022                         pr = cr;
1023                         cr = cr->rb_right;
1024                         if (!cr)
1025                                 break;
1026                         continue;
1027                 }
1028
1029                 cr = cr->rb_left;
1030                 if (!cr) {
1031                         e = pr ? rb_entry(pr, struct e_node, start.node) : NULL;
1032                         break;
1033                 }
1034         }
1035
1036         if (!e)
1037                 goto allocate_biggest;
1038
1039         if (e->start.key + e->count.key > hint) {
1040                 /* We have found extension with 'hint' inside. */
1041                 size_t len = e->start.key + e->count.key - hint;
1042
1043                 if (len >= to_alloc && hint + to_alloc <= max_alloc) {
1044                         fnd = hint;
1045                         goto found;
1046                 }
1047
1048                 if (!(flags & BITMAP_FIND_FULL)) {
1049                         if (len > to_alloc)
1050                                 len = to_alloc;
1051
1052                         if (hint + len <= max_alloc) {
1053                                 fnd = hint;
1054                                 to_alloc = len;
1055                                 goto found;
1056                         }
1057                 }
1058         }
1059
1060 allocate_biggest:
1061         /* Allocate from biggest free extent. */
1062         e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node);
1063         if (e->count.key != wnd->extent_max)
1064                 wnd->extent_max = e->count.key;
1065
1066         if (e->count.key < max_alloc) {
1067                 if (e->count.key >= to_alloc) {
1068                         ;
1069                 } else if (flags & BITMAP_FIND_FULL) {
1070                         if (e->count.key < to_alloc0) {
1071                                 /* Biggest free block is less then requested. */
1072                                 goto no_space;
1073                         }
1074                         to_alloc = e->count.key;
1075                 } else if (-1 != wnd->uptodated) {
1076                         to_alloc = e->count.key;
1077                 } else {
1078                         /* Check if we can use more bits. */
1079                         size_t op, max_check;
1080                         struct rb_root start_tree;
1081
1082                         memcpy(&start_tree, &wnd->start_tree,
1083                                sizeof(struct rb_root));
1084                         memset(&wnd->start_tree, 0, sizeof(struct rb_root));
1085
1086                         max_check = e->start.key + to_alloc;
1087                         if (max_check > max_alloc)
1088                                 max_check = max_alloc;
1089                         for (op = e->start.key + e->count.key; op < max_check;
1090                              op++) {
1091                                 if (!wnd_is_free(wnd, op, 1))
1092                                         break;
1093                         }
1094                         memcpy(&wnd->start_tree, &start_tree,
1095                                sizeof(struct rb_root));
1096                         to_alloc = op - e->start.key;
1097                 }
1098
1099                 /* Prepare to return. */
1100                 fnd = e->start.key;
1101                 if (e->start.key + to_alloc > max_alloc)
1102                         to_alloc = max_alloc - e->start.key;
1103                 goto found;
1104         }
1105
1106         if (wnd->uptodated == 1) {
1107                 /* Extents tree is updated -> no free space. */
1108                 goto no_space;
1109         }
1110
1111         b_len = e->count.key;
1112         b_pos = e->start.key;
1113
1114 scan_bitmap:
1115         sb = wnd->sb;
1116         log2_bits = sb->s_blocksize_bits + 3;
1117
1118         /* At most two ranges [hint, max_alloc) + [0, hint). */
1119 Again:
1120
1121         /* TODO: Optimize request for case nbits > wbits. */
1122         iw = hint >> log2_bits;
1123         wbits = sb->s_blocksize * 8;
1124         wpos = hint & (wbits - 1);
1125         prev_tail = 0;
1126         fbits_valid = true;
1127
1128         if (max_alloc == wnd->nbits) {
1129                 nwnd = wnd->nwnd;
1130         } else {
1131                 size_t t = max_alloc + wbits - 1;
1132
1133                 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd;
1134         }
1135
1136         /* Enumerate all windows. */
1137         for (; iw < nwnd; iw++) {
1138                 wbit = iw << log2_bits;
1139
1140                 if (!wnd->free_bits[iw]) {
1141                         if (prev_tail > b_len) {
1142                                 b_pos = wbit - prev_tail;
1143                                 b_len = prev_tail;
1144                         }
1145
1146                         /* Skip full used window. */
1147                         prev_tail = 0;
1148                         wpos = 0;
1149                         continue;
1150                 }
1151
1152                 if (unlikely(iw + 1 == nwnd)) {
1153                         if (max_alloc == wnd->nbits) {
1154                                 wbits = wnd->bits_last;
1155                         } else {
1156                                 size_t t = max_alloc & (wbits - 1);
1157
1158                                 if (t) {
1159                                         wbits = t;
1160                                         fbits_valid = false;
1161                                 }
1162                         }
1163                 }
1164
1165                 if (wnd->zone_end > wnd->zone_bit) {
1166                         ebit = wbit + wbits;
1167                         zbit = max(wnd->zone_bit, wbit);
1168                         zend = min(wnd->zone_end, ebit);
1169
1170                         /* Here we have a window [wbit, ebit) and zone [zbit, zend). */
1171                         if (zend <= zbit) {
1172                                 /* Zone does not overlap window. */
1173                         } else {
1174                                 wzbit = zbit - wbit;
1175                                 wzend = zend - wbit;
1176
1177                                 /* Zone overlaps window. */
1178                                 if (wnd->free_bits[iw] == wzend - wzbit) {
1179                                         prev_tail = 0;
1180                                         wpos = 0;
1181                                         continue;
1182                                 }
1183
1184                                 /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */
1185                                 bh = wnd_map(wnd, iw);
1186
1187                                 if (IS_ERR(bh)) {
1188                                         /* TODO: Error */
1189                                         prev_tail = 0;
1190                                         wpos = 0;
1191                                         continue;
1192                                 }
1193
1194                                 buf = (ulong *)bh->b_data;
1195
1196                                 /* Scan range [wbit, zbit). */
1197                                 if (wpos < wzbit) {
1198                                         /* Scan range [wpos, zbit). */
1199                                         fnd = wnd_scan(buf, wbit, wpos, wzbit,
1200                                                        to_alloc, &prev_tail,
1201                                                        &b_pos, &b_len);
1202                                         if (fnd != MINUS_ONE_T) {
1203                                                 put_bh(bh);
1204                                                 goto found;
1205                                         }
1206                                 }
1207
1208                                 prev_tail = 0;
1209
1210                                 /* Scan range [zend, ebit). */
1211                                 if (wzend < wbits) {
1212                                         fnd = wnd_scan(buf, wbit,
1213                                                        max(wzend, wpos), wbits,
1214                                                        to_alloc, &prev_tail,
1215                                                        &b_pos, &b_len);
1216                                         if (fnd != MINUS_ONE_T) {
1217                                                 put_bh(bh);
1218                                                 goto found;
1219                                         }
1220                                 }
1221
1222                                 wpos = 0;
1223                                 put_bh(bh);
1224                                 continue;
1225                         }
1226                 }
1227
1228                 /* Current window does not overlap zone. */
1229                 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) {
1230                         /* Window is empty. */
1231                         if (prev_tail + wbits >= to_alloc) {
1232                                 fnd = wbit + wpos - prev_tail;
1233                                 goto found;
1234                         }
1235
1236                         /* Increase 'prev_tail' and process next window. */
1237                         prev_tail += wbits;
1238                         wpos = 0;
1239                         continue;
1240                 }
1241
1242                 /* Read window. */
1243                 bh = wnd_map(wnd, iw);
1244                 if (IS_ERR(bh)) {
1245                         // TODO: Error.
1246                         prev_tail = 0;
1247                         wpos = 0;
1248                         continue;
1249                 }
1250
1251                 buf = (ulong *)bh->b_data;
1252
1253                 /* Scan range [wpos, eBits). */
1254                 fnd = wnd_scan(buf, wbit, wpos, wbits, to_alloc, &prev_tail,
1255                                &b_pos, &b_len);
1256                 put_bh(bh);
1257                 if (fnd != MINUS_ONE_T)
1258                         goto found;
1259         }
1260
1261         if (b_len < prev_tail) {
1262                 /* The last fragment. */
1263                 b_len = prev_tail;
1264                 b_pos = max_alloc - prev_tail;
1265         }
1266
1267         if (hint) {
1268                 /*
1269                  * We have scanned range [hint max_alloc).
1270                  * Prepare to scan range [0 hint + to_alloc).
1271                  */
1272                 size_t nextmax = hint + to_alloc;
1273
1274                 if (likely(nextmax >= hint) && nextmax < max_alloc)
1275                         max_alloc = nextmax;
1276                 hint = 0;
1277                 goto Again;
1278         }
1279
1280         if (!b_len)
1281                 goto no_space;
1282
1283         wnd->extent_max = b_len;
1284
1285         if (flags & BITMAP_FIND_FULL)
1286                 goto no_space;
1287
1288         fnd = b_pos;
1289         to_alloc = b_len;
1290
1291 found:
1292         if (flags & BITMAP_FIND_MARK_AS_USED) {
1293                 /* TODO: Optimize remove extent (pass 'e'?). */
1294                 if (wnd_set_used(wnd, fnd, to_alloc))
1295                         goto no_space;
1296         } else if (wnd->extent_max != MINUS_ONE_T &&
1297                    to_alloc > wnd->extent_max) {
1298                 wnd->extent_max = to_alloc;
1299         }
1300
1301         *allocated = fnd;
1302         return to_alloc;
1303
1304 no_space:
1305         return 0;
1306 }
1307
1308 /*
1309  * wnd_extend - Extend bitmap ($MFT bitmap).
1310  */
1311 int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits)
1312 {
1313         int err;
1314         struct super_block *sb = wnd->sb;
1315         struct ntfs_sb_info *sbi = sb->s_fs_info;
1316         u32 blocksize = sb->s_blocksize;
1317         u32 wbits = blocksize * 8;
1318         u32 b0, new_last;
1319         size_t bits, iw, new_wnd;
1320         size_t old_bits = wnd->nbits;
1321         u16 *new_free;
1322
1323         if (new_bits <= old_bits)
1324                 return -EINVAL;
1325
1326         /* Align to 8 byte boundary. */
1327         new_wnd = bytes_to_block(sb, bitmap_size(new_bits));
1328         new_last = new_bits & (wbits - 1);
1329         if (!new_last)
1330                 new_last = wbits;
1331
1332         if (new_wnd != wnd->nwnd) {
1333                 new_free = kmalloc(new_wnd * sizeof(u16), GFP_NOFS);
1334                 if (!new_free)
1335                         return -ENOMEM;
1336
1337                 if (new_free != wnd->free_bits)
1338                         memcpy(new_free, wnd->free_bits,
1339                                wnd->nwnd * sizeof(short));
1340                 memset(new_free + wnd->nwnd, 0,
1341                        (new_wnd - wnd->nwnd) * sizeof(short));
1342                 kfree(wnd->free_bits);
1343                 wnd->free_bits = new_free;
1344         }
1345
1346         /* Zero bits [old_bits,new_bits). */
1347         bits = new_bits - old_bits;
1348         b0 = old_bits & (wbits - 1);
1349
1350         for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) {
1351                 u32 op;
1352                 size_t frb;
1353                 u64 vbo, lbo, bytes;
1354                 struct buffer_head *bh;
1355                 ulong *buf;
1356
1357                 if (iw + 1 == new_wnd)
1358                         wbits = new_last;
1359
1360                 op = b0 + bits > wbits ? wbits - b0 : bits;
1361                 vbo = (u64)iw * blocksize;
1362
1363                 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes);
1364                 if (err)
1365                         break;
1366
1367                 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits);
1368                 if (!bh)
1369                         return -EIO;
1370
1371                 lock_buffer(bh);
1372                 buf = (ulong *)bh->b_data;
1373
1374                 __bitmap_clear(buf, b0, blocksize * 8 - b0);
1375                 frb = wbits - __bitmap_weight(buf, wbits);
1376                 wnd->total_zeroes += frb - wnd->free_bits[iw];
1377                 wnd->free_bits[iw] = frb;
1378
1379                 set_buffer_uptodate(bh);
1380                 mark_buffer_dirty(bh);
1381                 unlock_buffer(bh);
1382                 /* err = sync_dirty_buffer(bh); */
1383
1384                 b0 = 0;
1385                 bits -= op;
1386         }
1387
1388         wnd->nbits = new_bits;
1389         wnd->nwnd = new_wnd;
1390         wnd->bits_last = new_last;
1391
1392         wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false);
1393
1394         return 0;
1395 }
1396
1397 void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len)
1398 {
1399         size_t zlen;
1400
1401         zlen = wnd->zone_end - wnd->zone_bit;
1402         if (zlen)
1403                 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false);
1404
1405         if (!RB_EMPTY_ROOT(&wnd->start_tree) && len)
1406                 wnd_remove_free_ext(wnd, lcn, len);
1407
1408         wnd->zone_bit = lcn;
1409         wnd->zone_end = lcn + len;
1410 }
1411
1412 int ntfs_trim_fs(struct ntfs_sb_info *sbi, struct fstrim_range *range)
1413 {
1414         int err = 0;
1415         struct super_block *sb = sbi->sb;
1416         struct wnd_bitmap *wnd = &sbi->used.bitmap;
1417         u32 wbits = 8 * sb->s_blocksize;
1418         CLST len = 0, lcn = 0, done = 0;
1419         CLST minlen = bytes_to_cluster(sbi, range->minlen);
1420         CLST lcn_from = bytes_to_cluster(sbi, range->start);
1421         size_t iw = lcn_from >> (sb->s_blocksize_bits + 3);
1422         u32 wbit = lcn_from & (wbits - 1);
1423         const ulong *buf;
1424         CLST lcn_to;
1425
1426         if (!minlen)
1427                 minlen = 1;
1428
1429         if (range->len == (u64)-1)
1430                 lcn_to = wnd->nbits;
1431         else
1432                 lcn_to = bytes_to_cluster(sbi, range->start + range->len);
1433
1434         down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS);
1435
1436         for (; iw < wnd->nwnd; iw++, wbit = 0) {
1437                 CLST lcn_wnd = iw * wbits;
1438                 struct buffer_head *bh;
1439
1440                 if (lcn_wnd > lcn_to)
1441                         break;
1442
1443                 if (!wnd->free_bits[iw])
1444                         continue;
1445
1446                 if (iw + 1 == wnd->nwnd)
1447                         wbits = wnd->bits_last;
1448
1449                 if (lcn_wnd + wbits > lcn_to)
1450                         wbits = lcn_to - lcn_wnd;
1451
1452                 bh = wnd_map(wnd, iw);
1453                 if (IS_ERR(bh)) {
1454                         err = PTR_ERR(bh);
1455                         break;
1456                 }
1457
1458                 buf = (ulong *)bh->b_data;
1459
1460                 for (; wbit < wbits; wbit++) {
1461                         if (!test_bit(wbit, buf)) {
1462                                 if (!len)
1463                                         lcn = lcn_wnd + wbit;
1464                                 len += 1;
1465                                 continue;
1466                         }
1467                         if (len >= minlen) {
1468                                 err = ntfs_discard(sbi, lcn, len);
1469                                 if (err)
1470                                         goto out;
1471                                 done += len;
1472                         }
1473                         len = 0;
1474                 }
1475                 put_bh(bh);
1476         }
1477
1478         /* Process the last fragment. */
1479         if (len >= minlen) {
1480                 err = ntfs_discard(sbi, lcn, len);
1481                 if (err)
1482                         goto out;
1483                 done += len;
1484         }
1485
1486 out:
1487         range->len = (u64)done << sbi->cluster_bits;
1488
1489         up_read(&wnd->rw_lock);
1490
1491         return err;
1492 }