Lines Matching +full:scan +full:- +full:count
1 // SPDX-License-Identifier: GPL-2.0
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
9 * In extreme case code reads on-disk bitmap to find free clusters.
32 struct rb_node_key count; /* Tree sorted by len. */ member
46 return ntfs_enode_cachep ? 0 : -ENOMEM; in ntfs3_init_bitmap()
57 * b_pos + b_len - biggest fragment.
58 * Scan range [wpos wbits) window @buf.
60 * Return: -1 if not found.
73 *b_pos = wbit - *prev_tail; in wnd_scan()
78 return -1; in wnd_scan()
84 *b_pos = wbit - *prev_tail; in wnd_scan()
94 end = wpos + to_alloc - *prev_tail; in wnd_scan()
97 free_len = *prev_tail + free_bits - wpos; in wnd_scan()
100 *b_pos = wbit + wpos - *prev_tail; in wnd_scan()
105 return wbit + wpos - *prev_tail; in wnd_scan()
108 *prev_tail += free_bits - wpos; in wnd_scan()
109 return -1; in wnd_scan()
117 return -1; in wnd_scan()
121 * wnd_close - Frees all resources.
127 kvfree(wnd->free_bits); in wnd_close()
128 wnd->free_bits = NULL; in wnd_close()
129 run_close(&wnd->run); in wnd_close()
131 node = rb_first(&wnd->start_tree); in wnd_close()
135 rb_erase(node, &wnd->start_tree); in wnd_close()
144 struct rb_node **p = &root->rb_node; in rb_lookup()
151 if (v < k->key) { in rb_lookup()
152 p = &(*p)->rb_left; in rb_lookup()
153 } else if (v > k->key) { in rb_lookup()
154 r = &k->node; in rb_lookup()
155 p = &(*p)->rb_right; in rb_lookup()
157 return &k->node; in rb_lookup()
165 * rb_insert_count - Helper function to insert special kind of 'count' tree.
169 struct rb_node **p = &root->rb_node; in rb_insert_count()
171 size_t e_ckey = e->count.key; in rb_insert_count()
172 size_t e_skey = e->start.key; in rb_insert_count()
176 rb_entry(parent = *p, struct e_node, count.node); in rb_insert_count()
178 if (e_ckey > k->count.key) { in rb_insert_count()
179 p = &(*p)->rb_left; in rb_insert_count()
180 } else if (e_ckey < k->count.key) { in rb_insert_count()
181 p = &(*p)->rb_right; in rb_insert_count()
182 } else if (e_skey < k->start.key) { in rb_insert_count()
183 p = &(*p)->rb_left; in rb_insert_count()
184 } else if (e_skey > k->start.key) { in rb_insert_count()
185 p = &(*p)->rb_right; in rb_insert_count()
192 rb_link_node(&e->count.node, parent, p); in rb_insert_count()
193 rb_insert_color(&e->count.node, root); in rb_insert_count()
198 * rb_insert_start - Helper function to insert special kind of 'count' tree.
202 struct rb_node **p = &root->rb_node; in rb_insert_start()
204 size_t e_skey = e->start.key; in rb_insert_start()
212 if (e_skey < k->start.key) { in rb_insert_start()
213 p = &(*p)->rb_left; in rb_insert_start()
214 } else if (e_skey > k->start.key) { in rb_insert_start()
215 p = &(*p)->rb_right; in rb_insert_start()
222 rb_link_node(&e->start.node, parent, p); in rb_insert_start()
223 rb_insert_color(&e->start.node, root); in rb_insert_start()
228 * wnd_add_free_ext - Adds a new extent of free space.
240 if (wnd->count >= NTFS_MAX_WND_EXTENTS && in wnd_add_free_ext()
241 len <= wnd->extent_min) { in wnd_add_free_ext()
242 wnd->uptodated = -1; in wnd_add_free_ext()
247 n = rb_lookup(&wnd->start_tree, bit); in wnd_add_free_ext()
250 n = rb_first(&wnd->start_tree); in wnd_add_free_ext()
254 if (e->start.key + e->count.key == bit) { in wnd_add_free_ext()
256 bit = e->start.key; in wnd_add_free_ext()
257 len += e->count.key; in wnd_add_free_ext()
258 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
259 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
260 wnd->count -= 1; in wnd_add_free_ext()
269 next_end = e->start.key + e->count.key; in wnd_add_free_ext()
270 if (e->start.key > end_in) in wnd_add_free_ext()
275 len += next_end - end_in; in wnd_add_free_ext()
277 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
278 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
279 wnd->count -= 1; in wnd_add_free_ext()
287 if (wnd->uptodated != 1) { in wnd_add_free_ext()
289 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
290 bit < wnd->zone_end ? in wnd_add_free_ext()
292 wnd->zone_end; in wnd_add_free_ext()
294 while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) { in wnd_add_free_ext()
295 bit -= 1; in wnd_add_free_ext()
300 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
301 end_in > wnd->zone_bit ? in wnd_add_free_ext()
302 wnd->nbits : in wnd_add_free_ext()
303 wnd->zone_bit; in wnd_add_free_ext()
312 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_add_free_ext()
316 wnd->uptodated = -1; in wnd_add_free_ext()
319 n = rb_last(&wnd->count_tree); in wnd_add_free_ext()
320 e = rb_entry(n, struct e_node, count.node); in wnd_add_free_ext()
321 if (len <= e->count.key) in wnd_add_free_ext()
328 e2 = rb_entry(n, struct e_node, count.node); in wnd_add_free_ext()
329 /* Smallest fragment will be 'e2->count.key'. */ in wnd_add_free_ext()
330 wnd->extent_min = e2->count.key; in wnd_add_free_ext()
334 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
335 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
336 wnd->count -= 1; in wnd_add_free_ext()
340 wnd->uptodated = -1; in wnd_add_free_ext()
344 if (build && len <= wnd->extent_min) in wnd_add_free_ext()
345 wnd->extent_min = len; in wnd_add_free_ext()
347 e->start.key = bit; in wnd_add_free_ext()
348 e->count.key = len; in wnd_add_free_ext()
349 if (len > wnd->extent_max) in wnd_add_free_ext()
350 wnd->extent_max = len; in wnd_add_free_ext()
352 rb_insert_start(&wnd->start_tree, e); in wnd_add_free_ext()
353 rb_insert_count(&wnd->count_tree, e); in wnd_add_free_ext()
354 wnd->count += 1; in wnd_add_free_ext()
360 * wnd_remove_free_ext - Remove a run from the cached free space.
370 n = rb_lookup(&wnd->start_tree, bit); in wnd_remove_free_ext()
376 end = e->start.key + e->count.key; in wnd_remove_free_ext()
379 len = e->count.key; in wnd_remove_free_ext()
382 if (e->start.key > bit) in wnd_remove_free_ext()
387 new_len = end - end_in; in wnd_remove_free_ext()
388 len = bit - e->start.key; in wnd_remove_free_ext()
396 if (e3->start.key >= end_in) in wnd_remove_free_ext()
399 if (e3->count.key == wnd->extent_max) in wnd_remove_free_ext()
402 end3 = e3->start.key + e3->count.key; in wnd_remove_free_ext()
404 e3->start.key = end_in; in wnd_remove_free_ext()
405 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
406 e3->count.key = end3 - end_in; in wnd_remove_free_ext()
407 rb_insert_count(&wnd->count_tree, e3); in wnd_remove_free_ext()
412 rb_erase(&e3->start.node, &wnd->start_tree); in wnd_remove_free_ext()
413 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
414 wnd->count -= 1; in wnd_remove_free_ext()
419 n3 = rb_first(&wnd->count_tree); in wnd_remove_free_ext()
420 wnd->extent_max = in wnd_remove_free_ext()
421 n3 ? rb_entry(n3, struct e_node, count.node)->count.key : in wnd_remove_free_ext()
426 if (e->count.key != wnd->extent_max) { in wnd_remove_free_ext()
428 } else if (rb_prev(&e->count.node)) { in wnd_remove_free_ext()
431 n3 = rb_next(&e->count.node); in wnd_remove_free_ext()
434 wnd->extent_max = max_new_len; in wnd_remove_free_ext()
436 e3 = rb_entry(n3, struct e_node, count.node); in wnd_remove_free_ext()
437 wnd->extent_max = max(e3->count.key, max_new_len); in wnd_remove_free_ext()
443 e->start.key = new_key; in wnd_remove_free_ext()
444 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
445 e->count.key = new_len; in wnd_remove_free_ext()
446 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
448 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
449 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
450 wnd->count -= 1; in wnd_remove_free_ext()
455 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
456 e->count.key = len; in wnd_remove_free_ext()
457 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
462 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_remove_free_ext()
463 wnd->uptodated = -1; in wnd_remove_free_ext()
466 e = rb_entry(rb_last(&wnd->count_tree), struct e_node, in wnd_remove_free_ext()
467 count.node); in wnd_remove_free_ext()
468 if (e->count.key > new_len) in wnd_remove_free_ext()
472 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
473 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
474 wnd->count -= 1; in wnd_remove_free_ext()
478 wnd->uptodated = -1; in wnd_remove_free_ext()
482 e->start.key = new_key; in wnd_remove_free_ext()
483 e->count.key = new_len; in wnd_remove_free_ext()
484 rb_insert_start(&wnd->start_tree, e); in wnd_remove_free_ext()
485 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
486 wnd->count += 1; in wnd_remove_free_ext()
490 if (!wnd->count && 1 != wnd->uptodated) in wnd_remove_free_ext()
495 * wnd_rescan - Scan all bitmap. Used while initialization.
501 struct super_block *sb = wnd->sb; in wnd_rescan()
502 struct ntfs_sb_info *sbi = sb->s_fs_info; in wnd_rescan()
504 u32 blocksize = sb->s_blocksize; in wnd_rescan()
505 u8 cluster_bits = sbi->cluster_bits; in wnd_rescan()
506 u32 wbits = 8 * sb->s_blocksize; in wnd_rescan()
512 wnd->uptodated = 0; in wnd_rescan()
513 wnd->extent_max = 0; in wnd_rescan()
514 wnd->extent_min = MINUS_ONE_T; in wnd_rescan()
515 wnd->total_zeroes = 0; in wnd_rescan()
519 for (iw = 0; iw < wnd->nwnd; iw++) { in wnd_rescan()
520 if (iw + 1 == wnd->nwnd) in wnd_rescan()
521 wbits = wnd->bits_last; in wnd_rescan()
523 if (wnd->inited) { in wnd_rescan()
524 if (!wnd->free_bits[iw]) { in wnd_rescan()
528 vbo * 8 - prev_tail, in wnd_rescan()
534 if (wbits == wnd->free_bits[iw]) { in wnd_rescan()
537 wnd->total_zeroes += wbits; in wnd_rescan()
543 u32 off = vbo & sbi->cluster_mask; in wnd_rescan()
545 if (!run_lookup_entry(&wnd->run, vbo >> cluster_bits, in wnd_rescan()
547 err = -ENOENT; in wnd_rescan()
552 len = ((u64)clen << cluster_bits) - off; in wnd_rescan()
555 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); in wnd_rescan()
557 err = -EIO; in wnd_rescan()
561 used = ntfs_bitmap_weight_le(bh->b_data, wbits); in wnd_rescan()
563 frb = wbits - used; in wnd_rescan()
564 wnd->free_bits[iw] = frb; in wnd_rescan()
565 wnd->total_zeroes += frb; in wnd_rescan()
571 if (wbit + wbits > wnd->nbits) in wnd_rescan()
572 wbits = wnd->nbits - wbit; in wnd_rescan()
575 used = find_next_zero_bit_le(bh->b_data, wbits, wpos); in wnd_rescan()
578 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
591 frb = find_next_bit_le(bh->b_data, wbits, wpos); in wnd_rescan()
594 prev_tail += frb - wpos; in wnd_rescan()
598 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
599 frb + prev_tail - wpos, true); in wnd_rescan()
615 len -= blocksize; in wnd_rescan()
622 wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true); in wnd_rescan()
625 * Before init cycle wnd->uptodated was 0. in wnd_rescan()
627 * wnd->uptodated will be -1. in wnd_rescan()
630 if (!wnd->uptodated) in wnd_rescan()
631 wnd->uptodated = 1; in wnd_rescan()
633 if (wnd->zone_bit != wnd->zone_end) { in wnd_rescan()
634 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_rescan()
636 wnd->zone_end = wnd->zone_bit; in wnd_rescan()
637 wnd_zone_set(wnd, wnd->zone_bit, zlen); in wnd_rescan()
647 u32 blocksize = sb->s_blocksize; in wnd_init()
650 init_rwsem(&wnd->rw_lock); in wnd_init()
652 wnd->sb = sb; in wnd_init()
653 wnd->nbits = nbits; in wnd_init()
654 wnd->total_zeroes = nbits; in wnd_init()
655 wnd->extent_max = MINUS_ONE_T; in wnd_init()
656 wnd->zone_bit = wnd->zone_end = 0; in wnd_init()
657 wnd->nwnd = bytes_to_block(sb, ntfs3_bitmap_size(nbits)); in wnd_init()
658 wnd->bits_last = nbits & (wbits - 1); in wnd_init()
659 if (!wnd->bits_last) in wnd_init()
660 wnd->bits_last = wbits; in wnd_init()
662 wnd->free_bits = in wnd_init()
663 kvmalloc_array(wnd->nwnd, sizeof(u16), GFP_KERNEL | __GFP_ZERO); in wnd_init()
665 if (!wnd->free_bits) in wnd_init()
666 return -ENOMEM; in wnd_init()
672 wnd->inited = true; in wnd_init()
678 * wnd_map - Call sb_bread for requested window.
684 struct super_block *sb = wnd->sb; in wnd_map()
689 sbi = sb->s_fs_info; in wnd_map()
690 vbo = (u64)iw << sb->s_blocksize_bits; in wnd_map()
692 if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen, in wnd_map()
694 return ERR_PTR(-ENOENT); in wnd_map()
697 lbo = ((u64)lcn << sbi->cluster_bits) + (vbo & sbi->cluster_mask); in wnd_map()
699 bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits); in wnd_map()
701 return ERR_PTR(-EIO); in wnd_map()
707 * wnd_set_free - Mark the bits range from bit to bit + bits as free.
712 struct super_block *sb = wnd->sb; in wnd_set_free()
713 u32 wbits = 8 * sb->s_blocksize; in wnd_set_free()
714 size_t iw = bit >> (sb->s_blocksize_bits + 3); in wnd_set_free()
715 u32 wbit = bit & (wbits - 1); in wnd_set_free()
719 for (; iw < wnd->nwnd && bits; iw++, bit += op, bits -= op, wbit = 0) { in wnd_set_free()
720 if (iw + 1 == wnd->nwnd) in wnd_set_free()
721 wbits = wnd->bits_last; in wnd_set_free()
723 op = min_t(u32, wbits - wbit, bits); in wnd_set_free()
733 ntfs_bitmap_clear_le(bh->b_data, wbit, op); in wnd_set_free()
735 wnd->free_bits[iw] += op; in wnd_set_free()
736 wnd->total_zeroes += op; in wnd_set_free()
749 * wnd_set_used - Mark the bits range from bit to bit + bits as used.
754 struct super_block *sb = wnd->sb; in wnd_set_used()
755 size_t iw = bit >> (sb->s_blocksize_bits + 3); in wnd_set_used()
756 u32 wbits = 8 * sb->s_blocksize; in wnd_set_used()
757 u32 wbit = bit & (wbits - 1); in wnd_set_used()
761 for (; iw < wnd->nwnd && bits; iw++, bit += op, bits -= op, wbit = 0) { in wnd_set_used()
762 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_set_used()
763 wbits = wnd->bits_last; in wnd_set_used()
765 op = min_t(u32, wbits - wbit, bits); in wnd_set_used()
775 ntfs_bitmap_set_le(bh->b_data, wbit, op); in wnd_set_used()
776 wnd->free_bits[iw] -= op; in wnd_set_used()
777 wnd->total_zeroes -= op; in wnd_set_used()
784 if (!RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_set_used()
791 * wnd_set_used_safe - Mark the bits range from bit to bit + bits as used.
795 * @done - how many bits were marked as used.
835 struct super_block *sb = wnd->sb; in wnd_is_free_hlp()
836 size_t iw = bit >> (sb->s_blocksize_bits + 3); in wnd_is_free_hlp()
837 u32 wbits = 8 * sb->s_blocksize; in wnd_is_free_hlp()
838 u32 wbit = bit & (wbits - 1); in wnd_is_free_hlp()
841 for (; iw < wnd->nwnd && bits; iw++, bits -= op, wbit = 0) { in wnd_is_free_hlp()
842 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_free_hlp()
843 wbits = wnd->bits_last; in wnd_is_free_hlp()
845 op = min_t(u32, wbits - wbit, bits); in wnd_is_free_hlp()
847 if (wbits != wnd->free_bits[iw]) { in wnd_is_free_hlp()
854 ret = are_bits_clear(bh->b_data, wbit, op); in wnd_is_free_hlp()
877 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_free()
880 n = rb_lookup(&wnd->start_tree, bit); in wnd_is_free()
886 end = e->start.key + e->count.key; in wnd_is_free()
905 struct super_block *sb = wnd->sb; in wnd_is_used()
906 size_t iw = bit >> (sb->s_blocksize_bits + 3); in wnd_is_used()
907 u32 wbits = 8 * sb->s_blocksize; in wnd_is_used()
908 u32 wbit = bit & (wbits - 1); in wnd_is_used()
914 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_used()
918 n = rb_lookup(&wnd->start_tree, end - 1); in wnd_is_used()
923 if (e->start.key + e->count.key > bit) in wnd_is_used()
927 for (; iw < wnd->nwnd && bits; iw++, bits -= op, wbit = 0) { in wnd_is_used()
928 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_used()
929 wbits = wnd->bits_last; in wnd_is_used()
931 op = min_t(u32, wbits - wbit, bits); in wnd_is_used()
933 if (wnd->free_bits[iw]) { in wnd_is_used()
940 ret = are_bits_set(bh->b_data, wbit, op); in wnd_is_used()
953 * wnd_find - Look for free space.
955 * - flags - BITMAP_FIND_XXX flags
977 zeroes -= wnd->zone_end - wnd->zone_bit; in wnd_find()
981 if (to_alloc0 > wnd->extent_max) in wnd_find()
984 if (to_alloc > wnd->extent_max) in wnd_find()
985 to_alloc = wnd->extent_max; in wnd_find()
988 if (wnd->zone_bit <= hint && hint < wnd->zone_end) in wnd_find()
989 hint = wnd->zone_end; in wnd_find()
991 max_alloc = wnd->nbits; in wnd_find()
997 if (RB_EMPTY_ROOT(&wnd->start_tree)) { in wnd_find()
998 if (wnd->uptodated == 1) { in wnd_find()
999 /* Extents tree is updated -> No free space. */ in wnd_find()
1011 cr = wnd->start_tree.rb_node; in wnd_find()
1016 if (e->start.key == hint) in wnd_find()
1019 if (e->start.key < hint) { in wnd_find()
1021 cr = cr->rb_right; in wnd_find()
1027 cr = cr->rb_left; in wnd_find()
1037 if (e->start.key + e->count.key > hint) { in wnd_find()
1039 size_t len = e->start.key + e->count.key - hint; in wnd_find()
1060 e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); in wnd_find()
1061 if (e->count.key != wnd->extent_max) in wnd_find()
1062 wnd->extent_max = e->count.key; in wnd_find()
1064 if (e->count.key < max_alloc) { in wnd_find()
1065 if (e->count.key >= to_alloc) { in wnd_find()
1068 if (e->count.key < to_alloc0) { in wnd_find()
1072 to_alloc = e->count.key; in wnd_find()
1073 } else if (-1 != wnd->uptodated) { in wnd_find()
1074 to_alloc = e->count.key; in wnd_find()
1080 memcpy(&start_tree, &wnd->start_tree, in wnd_find()
1082 memset(&wnd->start_tree, 0, sizeof(struct rb_root)); in wnd_find()
1084 max_check = e->start.key + to_alloc; in wnd_find()
1087 for (op = e->start.key + e->count.key; op < max_check; in wnd_find()
1092 memcpy(&wnd->start_tree, &start_tree, in wnd_find()
1094 to_alloc = op - e->start.key; in wnd_find()
1098 fnd = e->start.key; in wnd_find()
1099 if (e->start.key + to_alloc > max_alloc) in wnd_find()
1100 to_alloc = max_alloc - e->start.key; in wnd_find()
1104 if (wnd->uptodated == 1) { in wnd_find()
1105 /* Extents tree is updated -> no free space. */ in wnd_find()
1109 b_len = e->count.key; in wnd_find()
1110 b_pos = e->start.key; in wnd_find()
1113 sb = wnd->sb; in wnd_find()
1114 log2_bits = sb->s_blocksize_bits + 3; in wnd_find()
1121 wbits = sb->s_blocksize * 8; in wnd_find()
1122 wpos = hint & (wbits - 1); in wnd_find()
1126 if (max_alloc == wnd->nbits) { in wnd_find()
1127 nwnd = wnd->nwnd; in wnd_find()
1129 size_t t = max_alloc + wbits - 1; in wnd_find()
1131 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; in wnd_find()
1138 if (!wnd->free_bits[iw]) { in wnd_find()
1140 b_pos = wbit - prev_tail; in wnd_find()
1151 if (max_alloc == wnd->nbits) { in wnd_find()
1152 wbits = wnd->bits_last; in wnd_find()
1154 size_t t = max_alloc & (wbits - 1); in wnd_find()
1163 if (wnd->zone_end > wnd->zone_bit) { in wnd_find()
1165 zbit = max(wnd->zone_bit, wbit); in wnd_find()
1166 zend = min(wnd->zone_end, ebit); in wnd_find()
1172 wzbit = zbit - wbit; in wnd_find()
1173 wzend = zend - wbit; in wnd_find()
1176 if (wnd->free_bits[iw] == wzend - wzbit) { in wnd_find()
1182 /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */ in wnd_find()
1192 /* Scan range [wbit, zbit). */ in wnd_find()
1194 /* Scan range [wpos, zbit). */ in wnd_find()
1195 fnd = wnd_scan(bh->b_data, wbit, wpos, in wnd_find()
1207 /* Scan range [zend, ebit). */ in wnd_find()
1209 fnd = wnd_scan(bh->b_data, wbit, in wnd_find()
1226 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { in wnd_find()
1229 fnd = wbit + wpos - prev_tail; in wnd_find()
1248 /* Scan range [wpos, eBits). */ in wnd_find()
1249 fnd = wnd_scan(bh->b_data, wbit, wpos, wbits, to_alloc, in wnd_find()
1259 b_pos = max_alloc - prev_tail; in wnd_find()
1265 * Prepare to scan range [0 hint + to_alloc). in wnd_find()
1278 wnd->extent_max = b_len; in wnd_find()
1291 } else if (wnd->extent_max != MINUS_ONE_T && in wnd_find()
1292 to_alloc > wnd->extent_max) { in wnd_find()
1293 wnd->extent_max = to_alloc; in wnd_find()
1304 * wnd_extend - Extend bitmap ($MFT bitmap).
1309 struct super_block *sb = wnd->sb; in wnd_extend()
1310 struct ntfs_sb_info *sbi = sb->s_fs_info; in wnd_extend()
1311 u32 blocksize = sb->s_blocksize; in wnd_extend()
1315 size_t old_bits = wnd->nbits; in wnd_extend()
1319 return -EINVAL; in wnd_extend()
1323 new_last = new_bits & (wbits - 1); in wnd_extend()
1327 if (new_wnd != wnd->nwnd) { in wnd_extend()
1330 return -ENOMEM; in wnd_extend()
1332 memcpy(new_free, wnd->free_bits, wnd->nwnd * sizeof(short)); in wnd_extend()
1333 memset(new_free + wnd->nwnd, 0, in wnd_extend()
1334 (new_wnd - wnd->nwnd) * sizeof(short)); in wnd_extend()
1335 kvfree(wnd->free_bits); in wnd_extend()
1336 wnd->free_bits = new_free; in wnd_extend()
1340 bits = new_bits - old_bits; in wnd_extend()
1341 b0 = old_bits & (wbits - 1); in wnd_extend()
1343 for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) { in wnd_extend()
1352 op = b0 + bits > wbits ? wbits - b0 : bits; in wnd_extend()
1355 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); in wnd_extend()
1359 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); in wnd_extend()
1361 return -EIO; in wnd_extend()
1365 ntfs_bitmap_clear_le(bh->b_data, b0, blocksize * 8 - b0); in wnd_extend()
1366 frb = wbits - ntfs_bitmap_weight_le(bh->b_data, wbits); in wnd_extend()
1367 wnd->total_zeroes += frb - wnd->free_bits[iw]; in wnd_extend()
1368 wnd->free_bits[iw] = frb; in wnd_extend()
1376 bits -= op; in wnd_extend()
1379 wnd->nbits = new_bits; in wnd_extend()
1380 wnd->nwnd = new_wnd; in wnd_extend()
1381 wnd->bits_last = new_last; in wnd_extend()
1383 wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); in wnd_extend()
1390 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_zone_set()
1393 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); in wnd_zone_set()
1395 if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) in wnd_zone_set()
1398 wnd->zone_bit = lcn; in wnd_zone_set()
1399 wnd->zone_end = lcn + len; in wnd_zone_set()
1405 struct super_block *sb = sbi->sb; in ntfs_trim_fs()
1406 struct wnd_bitmap *wnd = &sbi->used.bitmap; in ntfs_trim_fs()
1407 u32 wbits = 8 * sb->s_blocksize; in ntfs_trim_fs()
1409 CLST minlen = bytes_to_cluster(sbi, range->minlen); in ntfs_trim_fs()
1410 CLST lcn_from = bytes_to_cluster(sbi, range->start); in ntfs_trim_fs()
1411 size_t iw = lcn_from >> (sb->s_blocksize_bits + 3); in ntfs_trim_fs()
1412 u32 wbit = lcn_from & (wbits - 1); in ntfs_trim_fs()
1418 if (range->len == (u64)-1) in ntfs_trim_fs()
1419 lcn_to = wnd->nbits; in ntfs_trim_fs()
1421 lcn_to = bytes_to_cluster(sbi, range->start + range->len); in ntfs_trim_fs()
1423 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); in ntfs_trim_fs()
1425 for (; iw < wnd->nwnd; iw++, wbit = 0) { in ntfs_trim_fs()
1432 if (!wnd->free_bits[iw]) in ntfs_trim_fs()
1435 if (iw + 1 == wnd->nwnd) in ntfs_trim_fs()
1436 wbits = wnd->bits_last; in ntfs_trim_fs()
1439 wbits = lcn_to - lcn_wnd; in ntfs_trim_fs()
1448 if (!test_bit_le(wbit, bh->b_data)) { in ntfs_trim_fs()
1474 range->len = (u64)done << sbi->cluster_bits; in ntfs_trim_fs()
1476 up_read(&wnd->rw_lock); in ntfs_trim_fs()
1495 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); in ntfs_bitmap_set_le()
1498 while (len - bits_to_set >= 0) { in ntfs_bitmap_set_le()
1500 len -= bits_to_set; in ntfs_bitmap_set_le()
1515 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); in ntfs_bitmap_clear_le()
1518 while (len - bits_to_clear >= 0) { in ntfs_bitmap_clear_le()
1520 len -= bits_to_clear; in ntfs_bitmap_clear_le()