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